1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
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"
89 static struct datadep_stats
91 int num_dependence_tests;
92 int num_dependence_dependent;
93 int num_dependence_independent;
94 int num_dependence_undetermined;
96 int num_subscript_tests;
97 int num_subscript_undetermined;
98 int num_same_subscript_function;
101 int num_ziv_independent;
102 int num_ziv_dependent;
103 int num_ziv_unimplemented;
106 int num_siv_independent;
107 int num_siv_dependent;
108 int num_siv_unimplemented;
111 int num_miv_independent;
112 int num_miv_dependent;
113 int num_miv_unimplemented;
116 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
117 struct data_reference *,
118 struct data_reference *,
120 /* Returns true iff A divides B. */
123 tree_fold_divides_p (const_tree a, const_tree b)
125 gcc_assert (TREE_CODE (a) == INTEGER_CST);
126 gcc_assert (TREE_CODE (b) == INTEGER_CST);
127 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a));
130 /* Returns true iff A divides B. */
133 int_divides_p (int a, int b)
135 return ((b % a) == 0);
140 /* Dump into FILE all the data references from DATAREFS. */
143 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
146 struct data_reference *dr;
148 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
149 dump_data_reference (file, dr);
152 /* Dump into STDERR all the data references from DATAREFS. */
155 debug_data_references (VEC (data_reference_p, heap) *datarefs)
157 dump_data_references (stderr, datarefs);
160 /* Dump to STDERR all the dependence relations from DDRS. */
163 debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs)
165 dump_data_dependence_relations (stderr, ddrs);
168 /* Dump into FILE all the dependence relations from DDRS. */
171 dump_data_dependence_relations (FILE *file,
172 VEC (ddr_p, heap) *ddrs)
175 struct data_dependence_relation *ddr;
177 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
178 dump_data_dependence_relation (file, ddr);
181 /* Print to STDERR the data_reference DR. */
184 debug_data_reference (struct data_reference *dr)
186 dump_data_reference (stderr, dr);
189 /* Dump function for a DATA_REFERENCE structure. */
192 dump_data_reference (FILE *outf,
193 struct data_reference *dr)
197 fprintf (outf, "#(Data Ref: \n");
198 fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
199 fprintf (outf, "# stmt: ");
200 print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
201 fprintf (outf, "# ref: ");
202 print_generic_stmt (outf, DR_REF (dr), 0);
203 fprintf (outf, "# base_object: ");
204 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
206 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
208 fprintf (outf, "# Access function %d: ", i);
209 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
211 fprintf (outf, "#)\n");
214 /* Dumps the affine function described by FN to the file OUTF. */
217 dump_affine_function (FILE *outf, affine_fn fn)
222 print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
223 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
225 fprintf (outf, " + ");
226 print_generic_expr (outf, coef, TDF_SLIM);
227 fprintf (outf, " * x_%u", i);
231 /* Dumps the conflict function CF to the file OUTF. */
234 dump_conflict_function (FILE *outf, conflict_function *cf)
238 if (cf->n == NO_DEPENDENCE)
239 fprintf (outf, "no dependence\n");
240 else if (cf->n == NOT_KNOWN)
241 fprintf (outf, "not known\n");
244 for (i = 0; i < cf->n; i++)
247 dump_affine_function (outf, cf->fns[i]);
248 fprintf (outf, "]\n");
253 /* Dump function for a SUBSCRIPT structure. */
256 dump_subscript (FILE *outf, struct subscript *subscript)
258 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
260 fprintf (outf, "\n (subscript \n");
261 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
262 dump_conflict_function (outf, cf);
263 if (CF_NONTRIVIAL_P (cf))
265 tree last_iteration = SUB_LAST_CONFLICT (subscript);
266 fprintf (outf, " last_conflict: ");
267 print_generic_stmt (outf, last_iteration, 0);
270 cf = SUB_CONFLICTS_IN_B (subscript);
271 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
272 dump_conflict_function (outf, cf);
273 if (CF_NONTRIVIAL_P (cf))
275 tree last_iteration = SUB_LAST_CONFLICT (subscript);
276 fprintf (outf, " last_conflict: ");
277 print_generic_stmt (outf, last_iteration, 0);
280 fprintf (outf, " (Subscript distance: ");
281 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
282 fprintf (outf, " )\n");
283 fprintf (outf, " )\n");
286 /* Print the classic direction vector DIRV to OUTF. */
289 print_direction_vector (FILE *outf,
295 for (eq = 0; eq < length; eq++)
297 enum data_dependence_direction dir = ((enum data_dependence_direction)
303 fprintf (outf, " +");
306 fprintf (outf, " -");
309 fprintf (outf, " =");
311 case dir_positive_or_equal:
312 fprintf (outf, " +=");
314 case dir_positive_or_negative:
315 fprintf (outf, " +-");
317 case dir_negative_or_equal:
318 fprintf (outf, " -=");
321 fprintf (outf, " *");
324 fprintf (outf, "indep");
328 fprintf (outf, "\n");
331 /* Print a vector of direction vectors. */
334 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
340 FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, v)
341 print_direction_vector (outf, v, length);
344 /* Print out a vector VEC of length N to OUTFILE. */
347 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
351 for (i = 0; i < n; i++)
352 fprintf (outfile, "%3d ", vector[i]);
353 fprintf (outfile, "\n");
356 /* Print a vector of distance vectors. */
359 print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
365 FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, v)
366 print_lambda_vector (outf, v, length);
372 debug_data_dependence_relation (struct data_dependence_relation *ddr)
374 dump_data_dependence_relation (stderr, ddr);
377 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
380 dump_data_dependence_relation (FILE *outf,
381 struct data_dependence_relation *ddr)
383 struct data_reference *dra, *drb;
385 fprintf (outf, "(Data Dep: \n");
387 if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
394 dump_data_reference (outf, dra);
396 fprintf (outf, " (nil)\n");
398 dump_data_reference (outf, drb);
400 fprintf (outf, " (nil)\n");
402 fprintf (outf, " (don't know)\n)\n");
408 dump_data_reference (outf, dra);
409 dump_data_reference (outf, drb);
411 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
412 fprintf (outf, " (no dependence)\n");
414 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
419 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
421 fprintf (outf, " access_fn_A: ");
422 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
423 fprintf (outf, " access_fn_B: ");
424 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
425 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
428 fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
429 fprintf (outf, " loop nest: (");
430 FOR_EACH_VEC_ELT (loop_p, DDR_LOOP_NEST (ddr), i, loopi)
431 fprintf (outf, "%d ", loopi->num);
432 fprintf (outf, ")\n");
434 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
436 fprintf (outf, " distance_vector: ");
437 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
441 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
443 fprintf (outf, " direction_vector: ");
444 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
449 fprintf (outf, ")\n");
452 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
455 dump_data_dependence_direction (FILE *file,
456 enum data_dependence_direction dir)
472 case dir_positive_or_negative:
473 fprintf (file, "+-");
476 case dir_positive_or_equal:
477 fprintf (file, "+=");
480 case dir_negative_or_equal:
481 fprintf (file, "-=");
493 /* Dumps the distance and direction vectors in FILE. DDRS contains
494 the dependence relations, and VECT_SIZE is the size of the
495 dependence vectors, or in other words the number of loops in the
499 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
502 struct data_dependence_relation *ddr;
505 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
506 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
508 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), j, v)
510 fprintf (file, "DISTANCE_V (");
511 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
512 fprintf (file, ")\n");
515 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), j, v)
517 fprintf (file, "DIRECTION_V (");
518 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
519 fprintf (file, ")\n");
523 fprintf (file, "\n\n");
526 /* Dumps the data dependence relations DDRS in FILE. */
529 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
532 struct data_dependence_relation *ddr;
534 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
535 dump_data_dependence_relation (file, ddr);
537 fprintf (file, "\n\n");
540 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
541 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
542 constant of type ssizetype, and returns true. If we cannot do this
543 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
547 split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
548 tree *var, tree *off)
552 enum tree_code ocode = code;
560 *var = build_int_cst (type, 0);
561 *off = fold_convert (ssizetype, op0);
564 case POINTER_PLUS_EXPR:
569 split_constant_offset (op0, &var0, &off0);
570 split_constant_offset (op1, &var1, &off1);
571 *var = fold_build2 (code, type, var0, var1);
572 *off = size_binop (ocode, off0, off1);
576 if (TREE_CODE (op1) != INTEGER_CST)
579 split_constant_offset (op0, &var0, &off0);
580 *var = fold_build2 (MULT_EXPR, type, var0, op1);
581 *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
587 HOST_WIDE_INT pbitsize, pbitpos;
588 enum machine_mode pmode;
589 int punsignedp, pvolatilep;
591 op0 = TREE_OPERAND (op0, 0);
592 base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
593 &pmode, &punsignedp, &pvolatilep, false);
595 if (pbitpos % BITS_PER_UNIT != 0)
597 base = build_fold_addr_expr (base);
598 off0 = ssize_int (pbitpos / BITS_PER_UNIT);
602 split_constant_offset (poffset, &poffset, &off1);
603 off0 = size_binop (PLUS_EXPR, off0, off1);
604 if (POINTER_TYPE_P (TREE_TYPE (base)))
605 base = fold_build_pointer_plus (base, poffset);
607 base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
608 fold_convert (TREE_TYPE (base), poffset));
611 var0 = fold_convert (type, base);
613 /* If variable length types are involved, punt, otherwise casts
614 might be converted into ARRAY_REFs in gimplify_conversion.
615 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
616 possibly no longer appears in current GIMPLE, might resurface.
617 This perhaps could run
618 if (CONVERT_EXPR_P (var0))
620 gimplify_conversion (&var0);
621 // Attempt to fill in any within var0 found ARRAY_REF's
622 // element size from corresponding op embedded ARRAY_REF,
623 // if unsuccessful, just punt.
625 while (POINTER_TYPE_P (type))
626 type = TREE_TYPE (type);
627 if (int_size_in_bytes (type) < 0)
637 gimple def_stmt = SSA_NAME_DEF_STMT (op0);
638 enum tree_code subcode;
640 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
643 var0 = gimple_assign_rhs1 (def_stmt);
644 subcode = gimple_assign_rhs_code (def_stmt);
645 var1 = gimple_assign_rhs2 (def_stmt);
647 return split_constant_offset_1 (type, var0, subcode, var1, var, off);
651 /* We must not introduce undefined overflow, and we must not change the value.
652 Hence we're okay if the inner type doesn't overflow to start with
653 (pointer or signed), the outer type also is an integer or pointer
654 and the outer precision is at least as large as the inner. */
655 tree itype = TREE_TYPE (op0);
656 if ((POINTER_TYPE_P (itype)
657 || (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_UNDEFINED (itype)))
658 && TYPE_PRECISION (type) >= TYPE_PRECISION (itype)
659 && (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type)))
661 split_constant_offset (op0, &var0, off);
662 *var = fold_convert (type, var0);
673 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
674 will be ssizetype. */
677 split_constant_offset (tree exp, tree *var, tree *off)
679 tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
683 *off = ssize_int (0);
686 if (tree_is_chrec (exp)
687 || get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS)
690 otype = TREE_TYPE (exp);
691 code = TREE_CODE (exp);
692 extract_ops_from_tree (exp, &code, &op0, &op1);
693 if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
695 *var = fold_convert (type, e);
700 /* Returns the address ADDR of an object in a canonical shape (without nop
701 casts, and with type of pointer to the object). */
704 canonicalize_base_object_address (tree addr)
710 /* The base address may be obtained by casting from integer, in that case
712 if (!POINTER_TYPE_P (TREE_TYPE (addr)))
715 if (TREE_CODE (addr) != ADDR_EXPR)
718 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
721 /* Analyzes the behavior of the memory reference DR in the innermost loop or
722 basic block that contains it. Returns true if analysis succeed or false
726 dr_analyze_innermost (struct data_reference *dr, struct loop *nest)
728 gimple stmt = DR_STMT (dr);
729 struct loop *loop = loop_containing_stmt (stmt);
730 tree ref = DR_REF (dr);
731 HOST_WIDE_INT pbitsize, pbitpos;
733 enum machine_mode pmode;
734 int punsignedp, pvolatilep;
735 affine_iv base_iv, offset_iv;
736 tree init, dinit, step;
737 bool in_loop = (loop && loop->num);
739 if (dump_file && (dump_flags & TDF_DETAILS))
740 fprintf (dump_file, "analyze_innermost: ");
742 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
743 &pmode, &punsignedp, &pvolatilep, false);
744 gcc_assert (base != NULL_TREE);
746 if (pbitpos % BITS_PER_UNIT != 0)
748 if (dump_file && (dump_flags & TDF_DETAILS))
749 fprintf (dump_file, "failed: bit offset alignment.\n");
753 if (TREE_CODE (base) == MEM_REF)
755 if (!integer_zerop (TREE_OPERAND (base, 1)))
759 double_int moff = mem_ref_offset (base);
760 poffset = double_int_to_tree (sizetype, moff);
763 poffset = size_binop (PLUS_EXPR, poffset, TREE_OPERAND (base, 1));
765 base = TREE_OPERAND (base, 0);
768 base = build_fold_addr_expr (base);
772 if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
777 if (dump_file && (dump_flags & TDF_DETAILS))
778 fprintf (dump_file, "failed: evolution of base is not"
785 base_iv.step = ssize_int (0);
786 base_iv.no_overflow = true;
793 base_iv.step = ssize_int (0);
794 base_iv.no_overflow = true;
799 offset_iv.base = ssize_int (0);
800 offset_iv.step = ssize_int (0);
806 offset_iv.base = poffset;
807 offset_iv.step = ssize_int (0);
809 else if (!simple_iv (loop, loop_containing_stmt (stmt),
810 poffset, &offset_iv, false))
814 if (dump_file && (dump_flags & TDF_DETAILS))
815 fprintf (dump_file, "failed: evolution of offset is not"
821 offset_iv.base = poffset;
822 offset_iv.step = ssize_int (0);
827 init = ssize_int (pbitpos / BITS_PER_UNIT);
828 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
829 init = size_binop (PLUS_EXPR, init, dinit);
830 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
831 init = size_binop (PLUS_EXPR, init, dinit);
833 step = size_binop (PLUS_EXPR,
834 fold_convert (ssizetype, base_iv.step),
835 fold_convert (ssizetype, offset_iv.step));
837 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
839 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
843 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
845 if (dump_file && (dump_flags & TDF_DETAILS))
846 fprintf (dump_file, "success.\n");
851 /* Determines the base object and the list of indices of memory reference
852 DR, analyzed in LOOP and instantiated in loop nest NEST. */
855 dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
857 VEC (tree, heap) *access_fns = NULL;
859 tree base, off, access_fn;
860 basic_block before_loop;
862 /* If analyzing a basic-block there are no indices to analyze
863 and thus no access functions. */
866 DR_BASE_OBJECT (dr) = DR_REF (dr);
867 DR_ACCESS_FNS (dr) = NULL;
871 ref = unshare_expr (DR_REF (dr));
872 before_loop = block_before_loop (nest);
874 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
875 into a two element array with a constant index. The base is
876 then just the immediate underlying object. */
877 if (TREE_CODE (ref) == REALPART_EXPR)
879 ref = TREE_OPERAND (ref, 0);
880 VEC_safe_push (tree, heap, access_fns, integer_zero_node);
882 else if (TREE_CODE (ref) == IMAGPART_EXPR)
884 ref = TREE_OPERAND (ref, 0);
885 VEC_safe_push (tree, heap, access_fns, integer_one_node);
888 /* Analyze access functions of dimensions we know to be independent. */
890 while (handled_component_p (*aref))
892 if (TREE_CODE (*aref) == ARRAY_REF)
894 op = TREE_OPERAND (*aref, 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);
898 /* For ARRAY_REFs the base is the reference with the index replaced
899 by zero if we can not strip it as the outermost component. */
902 *aref = TREE_OPERAND (*aref, 0);
906 TREE_OPERAND (*aref, 1) = build_int_cst (TREE_TYPE (op), 0);
909 aref = &TREE_OPERAND (*aref, 0);
912 /* If the address operand of a MEM_REF base has an evolution in the
913 analyzed nest, add it as an additional independent access-function. */
914 if (TREE_CODE (*aref) == MEM_REF)
916 op = TREE_OPERAND (*aref, 0);
917 access_fn = analyze_scalar_evolution (loop, op);
918 access_fn = instantiate_scev (before_loop, loop, access_fn);
919 if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
922 base = initial_condition (access_fn);
923 orig_type = TREE_TYPE (base);
924 STRIP_USELESS_TYPE_CONVERSION (base);
925 split_constant_offset (base, &base, &off);
926 /* Fold the MEM_REF offset into the evolutions initial
927 value to make more bases comparable. */
928 if (!integer_zerop (TREE_OPERAND (*aref, 1)))
930 off = size_binop (PLUS_EXPR, off,
931 fold_convert (ssizetype,
932 TREE_OPERAND (*aref, 1)));
933 TREE_OPERAND (*aref, 1)
934 = build_int_cst (TREE_TYPE (TREE_OPERAND (*aref, 1)), 0);
936 access_fn = chrec_replace_initial_condition
937 (access_fn, fold_convert (orig_type, off));
938 *aref = fold_build2_loc (EXPR_LOCATION (*aref),
939 MEM_REF, TREE_TYPE (*aref),
940 base, TREE_OPERAND (*aref, 1));
941 VEC_safe_push (tree, heap, access_fns, access_fn);
945 DR_BASE_OBJECT (dr) = ref;
946 DR_ACCESS_FNS (dr) = access_fns;
949 /* Extracts the alias analysis information from the memory reference DR. */
952 dr_analyze_alias (struct data_reference *dr)
954 tree ref = DR_REF (dr);
955 tree base = get_base_address (ref), addr;
957 if (INDIRECT_REF_P (base)
958 || TREE_CODE (base) == MEM_REF)
960 addr = TREE_OPERAND (base, 0);
961 if (TREE_CODE (addr) == SSA_NAME)
962 DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
966 /* Frees data reference DR. */
969 free_data_ref (data_reference_p dr)
971 VEC_free (tree, heap, DR_ACCESS_FNS (dr));
975 /* Analyzes memory reference MEMREF accessed in STMT. The reference
976 is read if IS_READ is true, write otherwise. Returns the
977 data_reference description of MEMREF. NEST is the outermost loop
978 in which the reference should be instantiated, LOOP is the loop in
979 which the data reference should be analyzed. */
981 struct data_reference *
982 create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
985 struct data_reference *dr;
987 if (dump_file && (dump_flags & TDF_DETAILS))
989 fprintf (dump_file, "Creating dr for ");
990 print_generic_expr (dump_file, memref, TDF_SLIM);
991 fprintf (dump_file, "\n");
994 dr = XCNEW (struct data_reference);
996 DR_REF (dr) = memref;
997 DR_IS_READ (dr) = is_read;
999 dr_analyze_innermost (dr, nest);
1000 dr_analyze_indices (dr, nest, loop);
1001 dr_analyze_alias (dr);
1003 if (dump_file && (dump_flags & TDF_DETAILS))
1006 fprintf (dump_file, "\tbase_address: ");
1007 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1008 fprintf (dump_file, "\n\toffset from base address: ");
1009 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1010 fprintf (dump_file, "\n\tconstant offset from base address: ");
1011 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1012 fprintf (dump_file, "\n\tstep: ");
1013 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1014 fprintf (dump_file, "\n\taligned to: ");
1015 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1016 fprintf (dump_file, "\n\tbase_object: ");
1017 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1018 fprintf (dump_file, "\n");
1019 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
1021 fprintf (dump_file, "\tAccess function %d: ", i);
1022 print_generic_stmt (dump_file, DR_ACCESS_FN (dr, i), TDF_SLIM);
1029 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1032 dr_equal_offsets_p1 (tree offset1, tree offset2)
1036 STRIP_NOPS (offset1);
1037 STRIP_NOPS (offset2);
1039 if (offset1 == offset2)
1042 if (TREE_CODE (offset1) != TREE_CODE (offset2)
1043 || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
1046 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
1047 TREE_OPERAND (offset2, 0));
1049 if (!res || !BINARY_CLASS_P (offset1))
1052 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
1053 TREE_OPERAND (offset2, 1));
1058 /* Check if DRA and DRB have equal offsets. */
1060 dr_equal_offsets_p (struct data_reference *dra,
1061 struct data_reference *drb)
1063 tree offset1, offset2;
1065 offset1 = DR_OFFSET (dra);
1066 offset2 = DR_OFFSET (drb);
1068 return dr_equal_offsets_p1 (offset1, offset2);
1071 /* Returns true if FNA == FNB. */
1074 affine_function_equal_p (affine_fn fna, affine_fn fnb)
1076 unsigned i, n = VEC_length (tree, fna);
1078 if (n != VEC_length (tree, fnb))
1081 for (i = 0; i < n; i++)
1082 if (!operand_equal_p (VEC_index (tree, fna, i),
1083 VEC_index (tree, fnb, i), 0))
1089 /* If all the functions in CF are the same, returns one of them,
1090 otherwise returns NULL. */
1093 common_affine_function (conflict_function *cf)
1098 if (!CF_NONTRIVIAL_P (cf))
1103 for (i = 1; i < cf->n; i++)
1104 if (!affine_function_equal_p (comm, cf->fns[i]))
1110 /* Returns the base of the affine function FN. */
1113 affine_function_base (affine_fn fn)
1115 return VEC_index (tree, fn, 0);
1118 /* Returns true if FN is a constant. */
1121 affine_function_constant_p (affine_fn fn)
1126 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
1127 if (!integer_zerop (coef))
1133 /* Returns true if FN is the zero constant function. */
1136 affine_function_zero_p (affine_fn fn)
1138 return (integer_zerop (affine_function_base (fn))
1139 && affine_function_constant_p (fn));
1142 /* Returns a signed integer type with the largest precision from TA
1146 signed_type_for_types (tree ta, tree tb)
1148 if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
1149 return signed_type_for (ta);
1151 return signed_type_for (tb);
1154 /* Applies operation OP on affine functions FNA and FNB, and returns the
1158 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
1164 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
1166 n = VEC_length (tree, fna);
1167 m = VEC_length (tree, fnb);
1171 n = VEC_length (tree, fnb);
1172 m = VEC_length (tree, fna);
1175 ret = VEC_alloc (tree, heap, m);
1176 for (i = 0; i < n; i++)
1178 tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)),
1179 TREE_TYPE (VEC_index (tree, fnb, i)));
1181 VEC_quick_push (tree, ret,
1182 fold_build2 (op, type,
1183 VEC_index (tree, fna, i),
1184 VEC_index (tree, fnb, i)));
1187 for (; VEC_iterate (tree, fna, i, coef); i++)
1188 VEC_quick_push (tree, ret,
1189 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1190 coef, integer_zero_node));
1191 for (; VEC_iterate (tree, fnb, i, coef); i++)
1192 VEC_quick_push (tree, ret,
1193 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1194 integer_zero_node, coef));
1199 /* Returns the sum of affine functions FNA and FNB. */
1202 affine_fn_plus (affine_fn fna, affine_fn fnb)
1204 return affine_fn_op (PLUS_EXPR, fna, fnb);
1207 /* Returns the difference of affine functions FNA and FNB. */
1210 affine_fn_minus (affine_fn fna, affine_fn fnb)
1212 return affine_fn_op (MINUS_EXPR, fna, fnb);
1215 /* Frees affine function FN. */
1218 affine_fn_free (affine_fn fn)
1220 VEC_free (tree, heap, fn);
1223 /* Determine for each subscript in the data dependence relation DDR
1227 compute_subscript_distance (struct data_dependence_relation *ddr)
1229 conflict_function *cf_a, *cf_b;
1230 affine_fn fn_a, fn_b, diff;
1232 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1236 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1238 struct subscript *subscript;
1240 subscript = DDR_SUBSCRIPT (ddr, i);
1241 cf_a = SUB_CONFLICTS_IN_A (subscript);
1242 cf_b = SUB_CONFLICTS_IN_B (subscript);
1244 fn_a = common_affine_function (cf_a);
1245 fn_b = common_affine_function (cf_b);
1248 SUB_DISTANCE (subscript) = chrec_dont_know;
1251 diff = affine_fn_minus (fn_a, fn_b);
1253 if (affine_function_constant_p (diff))
1254 SUB_DISTANCE (subscript) = affine_function_base (diff);
1256 SUB_DISTANCE (subscript) = chrec_dont_know;
1258 affine_fn_free (diff);
1263 /* Returns the conflict function for "unknown". */
1265 static conflict_function *
1266 conflict_fn_not_known (void)
1268 conflict_function *fn = XCNEW (conflict_function);
1274 /* Returns the conflict function for "independent". */
1276 static conflict_function *
1277 conflict_fn_no_dependence (void)
1279 conflict_function *fn = XCNEW (conflict_function);
1280 fn->n = NO_DEPENDENCE;
1285 /* Returns true if the address of OBJ is invariant in LOOP. */
1288 object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
1290 while (handled_component_p (obj))
1292 if (TREE_CODE (obj) == ARRAY_REF)
1294 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1295 need to check the stride and the lower bound of the reference. */
1296 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1298 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1302 else if (TREE_CODE (obj) == COMPONENT_REF)
1304 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1308 obj = TREE_OPERAND (obj, 0);
1311 if (!INDIRECT_REF_P (obj)
1312 && TREE_CODE (obj) != MEM_REF)
1315 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1319 /* Returns false if we can prove that data references A and B do not alias,
1320 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1324 dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
1327 tree addr_a = DR_BASE_OBJECT (a);
1328 tree addr_b = DR_BASE_OBJECT (b);
1330 /* If we are not processing a loop nest but scalar code we
1331 do not need to care about possible cross-iteration dependences
1332 and thus can process the full original reference. Do so,
1333 similar to how loop invariant motion applies extra offset-based
1337 aff_tree off1, off2;
1338 double_int size1, size2;
1339 get_inner_reference_aff (DR_REF (a), &off1, &size1);
1340 get_inner_reference_aff (DR_REF (b), &off2, &size2);
1341 aff_combination_scale (&off1, double_int_minus_one);
1342 aff_combination_add (&off2, &off1);
1343 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1347 if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
1348 return refs_output_dependent_p (addr_a, addr_b);
1349 else if (DR_IS_READ (a) && DR_IS_WRITE (b))
1350 return refs_anti_dependent_p (addr_a, addr_b);
1351 return refs_may_alias_p (addr_a, addr_b);
1354 /* Initialize a data dependence relation between data accesses A and
1355 B. NB_LOOPS is the number of loops surrounding the references: the
1356 size of the classic distance/direction vectors. */
1358 struct data_dependence_relation *
1359 initialize_data_dependence_relation (struct data_reference *a,
1360 struct data_reference *b,
1361 VEC (loop_p, heap) *loop_nest)
1363 struct data_dependence_relation *res;
1366 res = XNEW (struct data_dependence_relation);
1369 DDR_LOOP_NEST (res) = NULL;
1370 DDR_REVERSED_P (res) = false;
1371 DDR_SUBSCRIPTS (res) = NULL;
1372 DDR_DIR_VECTS (res) = NULL;
1373 DDR_DIST_VECTS (res) = NULL;
1375 if (a == NULL || b == NULL)
1377 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1381 /* If the data references do not alias, then they are independent. */
1382 if (!dr_may_alias_p (a, b, loop_nest != NULL))
1384 DDR_ARE_DEPENDENT (res) = chrec_known;
1388 /* When the references are exactly the same, don't spend time doing
1389 the data dependence tests, just initialize the ddr and return. */
1390 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
1393 && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1394 DR_BASE_OBJECT (a)))
1396 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1399 DDR_AFFINE_P (res) = true;
1400 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1401 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1402 DDR_LOOP_NEST (res) = loop_nest;
1403 DDR_INNER_LOOP (res) = 0;
1404 DDR_SELF_REFERENCE (res) = true;
1405 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1407 struct subscript *subscript;
1409 subscript = XNEW (struct subscript);
1410 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1411 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1412 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1413 SUB_DISTANCE (subscript) = chrec_dont_know;
1414 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1419 /* If the references do not access the same object, we do not know
1420 whether they alias or not. */
1421 if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1423 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1427 /* If the base of the object is not invariant in the loop nest, we cannot
1428 analyze it. TODO -- in fact, it would suffice to record that there may
1429 be arbitrary dependences in the loops where the base object varies. */
1431 && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1432 DR_BASE_OBJECT (a)))
1434 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1438 /* If the number of dimensions of the access to not agree we can have
1439 a pointer access to a component of the array element type and an
1440 array access while the base-objects are still the same. Punt. */
1441 if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1443 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1447 DDR_AFFINE_P (res) = true;
1448 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1449 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1450 DDR_LOOP_NEST (res) = loop_nest;
1451 DDR_INNER_LOOP (res) = 0;
1452 DDR_SELF_REFERENCE (res) = false;
1454 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1456 struct subscript *subscript;
1458 subscript = XNEW (struct subscript);
1459 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1460 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1461 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1462 SUB_DISTANCE (subscript) = chrec_dont_know;
1463 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1469 /* Frees memory used by the conflict function F. */
1472 free_conflict_function (conflict_function *f)
1476 if (CF_NONTRIVIAL_P (f))
1478 for (i = 0; i < f->n; i++)
1479 affine_fn_free (f->fns[i]);
1484 /* Frees memory used by SUBSCRIPTS. */
1487 free_subscripts (VEC (subscript_p, heap) *subscripts)
1492 FOR_EACH_VEC_ELT (subscript_p, subscripts, i, s)
1494 free_conflict_function (s->conflicting_iterations_in_a);
1495 free_conflict_function (s->conflicting_iterations_in_b);
1498 VEC_free (subscript_p, heap, subscripts);
1501 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1505 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1508 if (dump_file && (dump_flags & TDF_DETAILS))
1510 fprintf (dump_file, "(dependence classified: ");
1511 print_generic_expr (dump_file, chrec, 0);
1512 fprintf (dump_file, ")\n");
1515 DDR_ARE_DEPENDENT (ddr) = chrec;
1516 free_subscripts (DDR_SUBSCRIPTS (ddr));
1517 DDR_SUBSCRIPTS (ddr) = NULL;
1520 /* The dependence relation DDR cannot be represented by a distance
1524 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1526 if (dump_file && (dump_flags & TDF_DETAILS))
1527 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1529 DDR_AFFINE_P (ddr) = false;
1534 /* This section contains the classic Banerjee tests. */
1536 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1537 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1540 ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1542 return (evolution_function_is_constant_p (chrec_a)
1543 && evolution_function_is_constant_p (chrec_b));
1546 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1547 variable, i.e., if the SIV (Single Index Variable) test is true. */
1550 siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1552 if ((evolution_function_is_constant_p (chrec_a)
1553 && evolution_function_is_univariate_p (chrec_b))
1554 || (evolution_function_is_constant_p (chrec_b)
1555 && evolution_function_is_univariate_p (chrec_a)))
1558 if (evolution_function_is_univariate_p (chrec_a)
1559 && evolution_function_is_univariate_p (chrec_b))
1561 switch (TREE_CODE (chrec_a))
1563 case POLYNOMIAL_CHREC:
1564 switch (TREE_CODE (chrec_b))
1566 case POLYNOMIAL_CHREC:
1567 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1582 /* Creates a conflict function with N dimensions. The affine functions
1583 in each dimension follow. */
1585 static conflict_function *
1586 conflict_fn (unsigned n, ...)
1589 conflict_function *ret = XCNEW (conflict_function);
1592 gcc_assert (0 < n && n <= MAX_DIM);
1596 for (i = 0; i < n; i++)
1597 ret->fns[i] = va_arg (ap, affine_fn);
1603 /* Returns constant affine function with value CST. */
1606 affine_fn_cst (tree cst)
1608 affine_fn fn = VEC_alloc (tree, heap, 1);
1609 VEC_quick_push (tree, fn, cst);
1613 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1616 affine_fn_univar (tree cst, unsigned dim, tree coef)
1618 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
1621 gcc_assert (dim > 0);
1622 VEC_quick_push (tree, fn, cst);
1623 for (i = 1; i < dim; i++)
1624 VEC_quick_push (tree, fn, integer_zero_node);
1625 VEC_quick_push (tree, fn, coef);
1629 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1630 *OVERLAPS_B are initialized to the functions that describe the
1631 relation between the elements accessed twice by CHREC_A and
1632 CHREC_B. For k >= 0, the following property is verified:
1634 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1637 analyze_ziv_subscript (tree chrec_a,
1639 conflict_function **overlaps_a,
1640 conflict_function **overlaps_b,
1641 tree *last_conflicts)
1643 tree type, difference;
1644 dependence_stats.num_ziv++;
1646 if (dump_file && (dump_flags & TDF_DETAILS))
1647 fprintf (dump_file, "(analyze_ziv_subscript \n");
1649 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1650 chrec_a = chrec_convert (type, chrec_a, NULL);
1651 chrec_b = chrec_convert (type, chrec_b, NULL);
1652 difference = chrec_fold_minus (type, chrec_a, chrec_b);
1654 switch (TREE_CODE (difference))
1657 if (integer_zerop (difference))
1659 /* The difference is equal to zero: the accessed index
1660 overlaps for each iteration in the loop. */
1661 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1662 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1663 *last_conflicts = chrec_dont_know;
1664 dependence_stats.num_ziv_dependent++;
1668 /* The accesses do not overlap. */
1669 *overlaps_a = conflict_fn_no_dependence ();
1670 *overlaps_b = conflict_fn_no_dependence ();
1671 *last_conflicts = integer_zero_node;
1672 dependence_stats.num_ziv_independent++;
1677 /* We're not sure whether the indexes overlap. For the moment,
1678 conservatively answer "don't know". */
1679 if (dump_file && (dump_flags & TDF_DETAILS))
1680 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1682 *overlaps_a = conflict_fn_not_known ();
1683 *overlaps_b = conflict_fn_not_known ();
1684 *last_conflicts = chrec_dont_know;
1685 dependence_stats.num_ziv_unimplemented++;
1689 if (dump_file && (dump_flags & TDF_DETAILS))
1690 fprintf (dump_file, ")\n");
1693 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1694 and only if it fits to the int type. If this is not the case, or the
1695 bound on the number of iterations of LOOP could not be derived, returns
1699 max_stmt_executions_tree (struct loop *loop)
1703 if (!max_stmt_executions (loop, true, &nit))
1704 return chrec_dont_know;
1706 if (!double_int_fits_to_tree_p (unsigned_type_node, nit))
1707 return chrec_dont_know;
1709 return double_int_to_tree (unsigned_type_node, nit);
1712 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1713 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1714 *OVERLAPS_B are initialized to the functions that describe the
1715 relation between the elements accessed twice by CHREC_A and
1716 CHREC_B. For k >= 0, the following property is verified:
1718 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1721 analyze_siv_subscript_cst_affine (tree chrec_a,
1723 conflict_function **overlaps_a,
1724 conflict_function **overlaps_b,
1725 tree *last_conflicts)
1727 bool value0, value1, value2;
1728 tree type, difference, tmp;
1730 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1731 chrec_a = chrec_convert (type, chrec_a, NULL);
1732 chrec_b = chrec_convert (type, chrec_b, NULL);
1733 difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
1735 if (!chrec_is_positive (initial_condition (difference), &value0))
1737 if (dump_file && (dump_flags & TDF_DETAILS))
1738 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1740 dependence_stats.num_siv_unimplemented++;
1741 *overlaps_a = conflict_fn_not_known ();
1742 *overlaps_b = conflict_fn_not_known ();
1743 *last_conflicts = chrec_dont_know;
1748 if (value0 == false)
1750 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1752 if (dump_file && (dump_flags & TDF_DETAILS))
1753 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1755 *overlaps_a = conflict_fn_not_known ();
1756 *overlaps_b = conflict_fn_not_known ();
1757 *last_conflicts = chrec_dont_know;
1758 dependence_stats.num_siv_unimplemented++;
1767 chrec_b = {10, +, 1}
1770 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1772 HOST_WIDE_INT numiter;
1773 struct loop *loop = get_chrec_loop (chrec_b);
1775 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1776 tmp = fold_build2 (EXACT_DIV_EXPR, type,
1777 fold_build1 (ABS_EXPR, type, difference),
1778 CHREC_RIGHT (chrec_b));
1779 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1780 *last_conflicts = integer_one_node;
1783 /* Perform weak-zero siv test to see if overlap is
1784 outside the loop bounds. */
1785 numiter = max_stmt_executions_int (loop, true);
1788 && compare_tree_int (tmp, numiter) > 0)
1790 free_conflict_function (*overlaps_a);
1791 free_conflict_function (*overlaps_b);
1792 *overlaps_a = conflict_fn_no_dependence ();
1793 *overlaps_b = conflict_fn_no_dependence ();
1794 *last_conflicts = integer_zero_node;
1795 dependence_stats.num_siv_independent++;
1798 dependence_stats.num_siv_dependent++;
1802 /* When the step does not divide the difference, there are
1806 *overlaps_a = conflict_fn_no_dependence ();
1807 *overlaps_b = conflict_fn_no_dependence ();
1808 *last_conflicts = integer_zero_node;
1809 dependence_stats.num_siv_independent++;
1818 chrec_b = {10, +, -1}
1820 In this case, chrec_a will not overlap with chrec_b. */
1821 *overlaps_a = conflict_fn_no_dependence ();
1822 *overlaps_b = conflict_fn_no_dependence ();
1823 *last_conflicts = integer_zero_node;
1824 dependence_stats.num_siv_independent++;
1831 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
1833 if (dump_file && (dump_flags & TDF_DETAILS))
1834 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1836 *overlaps_a = conflict_fn_not_known ();
1837 *overlaps_b = conflict_fn_not_known ();
1838 *last_conflicts = chrec_dont_know;
1839 dependence_stats.num_siv_unimplemented++;
1844 if (value2 == false)
1848 chrec_b = {10, +, -1}
1850 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1852 HOST_WIDE_INT numiter;
1853 struct loop *loop = get_chrec_loop (chrec_b);
1855 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1856 tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
1857 CHREC_RIGHT (chrec_b));
1858 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1859 *last_conflicts = integer_one_node;
1861 /* Perform weak-zero siv test to see if overlap is
1862 outside the loop bounds. */
1863 numiter = max_stmt_executions_int (loop, true);
1866 && compare_tree_int (tmp, numiter) > 0)
1868 free_conflict_function (*overlaps_a);
1869 free_conflict_function (*overlaps_b);
1870 *overlaps_a = conflict_fn_no_dependence ();
1871 *overlaps_b = conflict_fn_no_dependence ();
1872 *last_conflicts = integer_zero_node;
1873 dependence_stats.num_siv_independent++;
1876 dependence_stats.num_siv_dependent++;
1880 /* When the step does not divide the difference, there
1884 *overlaps_a = conflict_fn_no_dependence ();
1885 *overlaps_b = conflict_fn_no_dependence ();
1886 *last_conflicts = integer_zero_node;
1887 dependence_stats.num_siv_independent++;
1897 In this case, chrec_a will not overlap with chrec_b. */
1898 *overlaps_a = conflict_fn_no_dependence ();
1899 *overlaps_b = conflict_fn_no_dependence ();
1900 *last_conflicts = integer_zero_node;
1901 dependence_stats.num_siv_independent++;
1909 /* Helper recursive function for initializing the matrix A. Returns
1910 the initial value of CHREC. */
1913 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1917 switch (TREE_CODE (chrec))
1919 case POLYNOMIAL_CHREC:
1920 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
1922 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1923 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1929 tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
1930 tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
1932 return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
1937 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
1938 return chrec_convert (chrec_type (chrec), op, NULL);
1943 /* Handle ~X as -1 - X. */
1944 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
1945 return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
1946 build_int_cst (TREE_TYPE (chrec), -1), op);
1958 #define FLOOR_DIV(x,y) ((x) / (y))
1960 /* Solves the special case of the Diophantine equation:
1961 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1963 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1964 number of iterations that loops X and Y run. The overlaps will be
1965 constructed as evolutions in dimension DIM. */
1968 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1969 affine_fn *overlaps_a,
1970 affine_fn *overlaps_b,
1971 tree *last_conflicts, int dim)
1973 if (((step_a > 0 && step_b > 0)
1974 || (step_a < 0 && step_b < 0)))
1976 int step_overlaps_a, step_overlaps_b;
1977 int gcd_steps_a_b, last_conflict, tau2;
1979 gcd_steps_a_b = gcd (step_a, step_b);
1980 step_overlaps_a = step_b / gcd_steps_a_b;
1981 step_overlaps_b = step_a / gcd_steps_a_b;
1985 tau2 = FLOOR_DIV (niter, step_overlaps_a);
1986 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1987 last_conflict = tau2;
1988 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1991 *last_conflicts = chrec_dont_know;
1993 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
1994 build_int_cst (NULL_TREE,
1996 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
1997 build_int_cst (NULL_TREE,
2003 *overlaps_a = affine_fn_cst (integer_zero_node);
2004 *overlaps_b = affine_fn_cst (integer_zero_node);
2005 *last_conflicts = integer_zero_node;
2009 /* Solves the special case of a Diophantine equation where CHREC_A is
2010 an affine bivariate function, and CHREC_B is an affine univariate
2011 function. For example,
2013 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2015 has the following overlapping functions:
2017 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2018 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2019 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2021 FORNOW: This is a specialized implementation for a case occurring in
2022 a common benchmark. Implement the general algorithm. */
2025 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2026 conflict_function **overlaps_a,
2027 conflict_function **overlaps_b,
2028 tree *last_conflicts)
2030 bool xz_p, yz_p, xyz_p;
2031 int step_x, step_y, step_z;
2032 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
2033 affine_fn overlaps_a_xz, overlaps_b_xz;
2034 affine_fn overlaps_a_yz, overlaps_b_yz;
2035 affine_fn overlaps_a_xyz, overlaps_b_xyz;
2036 affine_fn ova1, ova2, ovb;
2037 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2039 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2040 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2041 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2044 max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
2045 niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
2046 niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b), true);
2048 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
2050 if (dump_file && (dump_flags & TDF_DETAILS))
2051 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2053 *overlaps_a = conflict_fn_not_known ();
2054 *overlaps_b = conflict_fn_not_known ();
2055 *last_conflicts = chrec_dont_know;
2059 niter = MIN (niter_x, niter_z);
2060 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2063 &last_conflicts_xz, 1);
2064 niter = MIN (niter_y, niter_z);
2065 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2068 &last_conflicts_yz, 2);
2069 niter = MIN (niter_x, niter_z);
2070 niter = MIN (niter_y, niter);
2071 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2074 &last_conflicts_xyz, 3);
2076 xz_p = !integer_zerop (last_conflicts_xz);
2077 yz_p = !integer_zerop (last_conflicts_yz);
2078 xyz_p = !integer_zerop (last_conflicts_xyz);
2080 if (xz_p || yz_p || xyz_p)
2082 ova1 = affine_fn_cst (integer_zero_node);
2083 ova2 = affine_fn_cst (integer_zero_node);
2084 ovb = affine_fn_cst (integer_zero_node);
2087 affine_fn t0 = ova1;
2090 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2091 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2092 affine_fn_free (t0);
2093 affine_fn_free (t2);
2094 *last_conflicts = last_conflicts_xz;
2098 affine_fn t0 = ova2;
2101 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2102 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2103 affine_fn_free (t0);
2104 affine_fn_free (t2);
2105 *last_conflicts = last_conflicts_yz;
2109 affine_fn t0 = ova1;
2110 affine_fn t2 = ova2;
2113 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2114 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2115 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2116 affine_fn_free (t0);
2117 affine_fn_free (t2);
2118 affine_fn_free (t4);
2119 *last_conflicts = last_conflicts_xyz;
2121 *overlaps_a = conflict_fn (2, ova1, ova2);
2122 *overlaps_b = conflict_fn (1, ovb);
2126 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2127 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2128 *last_conflicts = integer_zero_node;
2131 affine_fn_free (overlaps_a_xz);
2132 affine_fn_free (overlaps_b_xz);
2133 affine_fn_free (overlaps_a_yz);
2134 affine_fn_free (overlaps_b_yz);
2135 affine_fn_free (overlaps_a_xyz);
2136 affine_fn_free (overlaps_b_xyz);
2139 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2142 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
2145 memcpy (vec2, vec1, size * sizeof (*vec1));
2148 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2151 lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2,
2156 for (i = 0; i < m; i++)
2157 lambda_vector_copy (mat1[i], mat2[i], n);
2160 /* Store the N x N identity matrix in MAT. */
2163 lambda_matrix_id (lambda_matrix mat, int size)
2167 for (i = 0; i < size; i++)
2168 for (j = 0; j < size; j++)
2169 mat[i][j] = (i == j) ? 1 : 0;
2172 /* Return the first nonzero element of vector VEC1 between START and N.
2173 We must have START <= N. Returns N if VEC1 is the zero vector. */
2176 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
2179 while (j < n && vec1[j] == 0)
2184 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2185 R2 = R2 + CONST1 * R1. */
2188 lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1)
2195 for (i = 0; i < n; i++)
2196 mat[r2][i] += const1 * mat[r1][i];
2199 /* Swap rows R1 and R2 in matrix MAT. */
2202 lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2)
2211 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2212 and store the result in VEC2. */
2215 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
2216 int size, int const1)
2221 lambda_vector_clear (vec2, size);
2223 for (i = 0; i < size; i++)
2224 vec2[i] = const1 * vec1[i];
2227 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2230 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
2233 lambda_vector_mult_const (vec1, vec2, size, -1);
2236 /* Negate row R1 of matrix MAT which has N columns. */
2239 lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
2241 lambda_vector_negate (mat[r1], mat[r1], n);
2244 /* Return true if two vectors are equal. */
2247 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
2250 for (i = 0; i < size; i++)
2251 if (vec1[i] != vec2[i])
2256 /* Given an M x N integer matrix A, this function determines an M x
2257 M unimodular matrix U, and an M x N echelon matrix S such that
2258 "U.A = S". This decomposition is also known as "right Hermite".
2260 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2261 Restructuring Compilers" Utpal Banerjee. */
2264 lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
2265 lambda_matrix S, lambda_matrix U)
2269 lambda_matrix_copy (A, S, m, n);
2270 lambda_matrix_id (U, m);
2272 for (j = 0; j < n; j++)
2274 if (lambda_vector_first_nz (S[j], m, i0) < m)
2277 for (i = m - 1; i >= i0; i--)
2279 while (S[i][j] != 0)
2281 int sigma, factor, a, b;
2285 sigma = (a * b < 0) ? -1: 1;
2288 factor = sigma * (a / b);
2290 lambda_matrix_row_add (S, n, i, i-1, -factor);
2291 lambda_matrix_row_exchange (S, i, i-1);
2293 lambda_matrix_row_add (U, m, i, i-1, -factor);
2294 lambda_matrix_row_exchange (U, i, i-1);
2301 /* Determines the overlapping elements due to accesses CHREC_A and
2302 CHREC_B, that are affine functions. This function cannot handle
2303 symbolic evolution functions, ie. when initial conditions are
2304 parameters, because it uses lambda matrices of integers. */
2307 analyze_subscript_affine_affine (tree chrec_a,
2309 conflict_function **overlaps_a,
2310 conflict_function **overlaps_b,
2311 tree *last_conflicts)
2313 unsigned nb_vars_a, nb_vars_b, dim;
2314 HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
2315 lambda_matrix A, U, S;
2316 struct obstack scratch_obstack;
2318 if (eq_evolutions_p (chrec_a, chrec_b))
2320 /* The accessed index overlaps for each iteration in the
2322 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2323 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2324 *last_conflicts = chrec_dont_know;
2327 if (dump_file && (dump_flags & TDF_DETAILS))
2328 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2330 /* For determining the initial intersection, we have to solve a
2331 Diophantine equation. This is the most time consuming part.
2333 For answering to the question: "Is there a dependence?" we have
2334 to prove that there exists a solution to the Diophantine
2335 equation, and that the solution is in the iteration domain,
2336 i.e. the solution is positive or zero, and that the solution
2337 happens before the upper bound loop.nb_iterations. Otherwise
2338 there is no dependence. This function outputs a description of
2339 the iterations that hold the intersections. */
2341 nb_vars_a = nb_vars_in_chrec (chrec_a);
2342 nb_vars_b = nb_vars_in_chrec (chrec_b);
2344 gcc_obstack_init (&scratch_obstack);
2346 dim = nb_vars_a + nb_vars_b;
2347 U = lambda_matrix_new (dim, dim, &scratch_obstack);
2348 A = lambda_matrix_new (dim, 1, &scratch_obstack);
2349 S = lambda_matrix_new (dim, 1, &scratch_obstack);
2351 init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
2352 init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
2353 gamma = init_b - init_a;
2355 /* Don't do all the hard work of solving the Diophantine equation
2356 when we already know the solution: for example,
2359 | gamma = 3 - 3 = 0.
2360 Then the first overlap occurs during the first iterations:
2361 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2365 if (nb_vars_a == 1 && nb_vars_b == 1)
2367 HOST_WIDE_INT step_a, step_b;
2368 HOST_WIDE_INT niter, niter_a, niter_b;
2371 niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
2372 niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b), true);
2373 niter = MIN (niter_a, niter_b);
2374 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2375 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2377 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2380 *overlaps_a = conflict_fn (1, ova);
2381 *overlaps_b = conflict_fn (1, ovb);
2384 else if (nb_vars_a == 2 && nb_vars_b == 1)
2385 compute_overlap_steps_for_affine_1_2
2386 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2388 else if (nb_vars_a == 1 && nb_vars_b == 2)
2389 compute_overlap_steps_for_affine_1_2
2390 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2394 if (dump_file && (dump_flags & TDF_DETAILS))
2395 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2396 *overlaps_a = conflict_fn_not_known ();
2397 *overlaps_b = conflict_fn_not_known ();
2398 *last_conflicts = chrec_dont_know;
2400 goto end_analyze_subs_aa;
2404 lambda_matrix_right_hermite (A, dim, 1, S, U);
2409 lambda_matrix_row_negate (U, dim, 0);
2411 gcd_alpha_beta = S[0][0];
2413 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2414 but that is a quite strange case. Instead of ICEing, answer
2416 if (gcd_alpha_beta == 0)
2418 *overlaps_a = conflict_fn_not_known ();
2419 *overlaps_b = conflict_fn_not_known ();
2420 *last_conflicts = chrec_dont_know;
2421 goto end_analyze_subs_aa;
2424 /* The classic "gcd-test". */
2425 if (!int_divides_p (gcd_alpha_beta, gamma))
2427 /* The "gcd-test" has determined that there is no integer
2428 solution, i.e. there is no dependence. */
2429 *overlaps_a = conflict_fn_no_dependence ();
2430 *overlaps_b = conflict_fn_no_dependence ();
2431 *last_conflicts = integer_zero_node;
2434 /* Both access functions are univariate. This includes SIV and MIV cases. */
2435 else if (nb_vars_a == 1 && nb_vars_b == 1)
2437 /* Both functions should have the same evolution sign. */
2438 if (((A[0][0] > 0 && -A[1][0] > 0)
2439 || (A[0][0] < 0 && -A[1][0] < 0)))
2441 /* The solutions are given by:
2443 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2446 For a given integer t. Using the following variables,
2448 | i0 = u11 * gamma / gcd_alpha_beta
2449 | j0 = u12 * gamma / gcd_alpha_beta
2456 | y0 = j0 + j1 * t. */
2457 HOST_WIDE_INT i0, j0, i1, j1;
2459 i0 = U[0][0] * gamma / gcd_alpha_beta;
2460 j0 = U[0][1] * gamma / gcd_alpha_beta;
2464 if ((i1 == 0 && i0 < 0)
2465 || (j1 == 0 && j0 < 0))
2467 /* There is no solution.
2468 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2469 falls in here, but for the moment we don't look at the
2470 upper bound of the iteration domain. */
2471 *overlaps_a = conflict_fn_no_dependence ();
2472 *overlaps_b = conflict_fn_no_dependence ();
2473 *last_conflicts = integer_zero_node;
2474 goto end_analyze_subs_aa;
2477 if (i1 > 0 && j1 > 0)
2479 HOST_WIDE_INT niter_a = max_stmt_executions_int
2480 (get_chrec_loop (chrec_a), true);
2481 HOST_WIDE_INT niter_b = max_stmt_executions_int
2482 (get_chrec_loop (chrec_b), true);
2483 HOST_WIDE_INT niter = MIN (niter_a, niter_b);
2485 /* (X0, Y0) is a solution of the Diophantine equation:
2486 "chrec_a (X0) = chrec_b (Y0)". */
2487 HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
2489 HOST_WIDE_INT x0 = i1 * tau1 + i0;
2490 HOST_WIDE_INT y0 = j1 * tau1 + j0;
2492 /* (X1, Y1) is the smallest positive solution of the eq
2493 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2494 first conflict occurs. */
2495 HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
2496 HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
2497 HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
2501 HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
2502 FLOOR_DIV (niter - j0, j1));
2503 HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
2505 /* If the overlap occurs outside of the bounds of the
2506 loop, there is no dependence. */
2507 if (x1 >= niter || y1 >= niter)
2509 *overlaps_a = conflict_fn_no_dependence ();
2510 *overlaps_b = conflict_fn_no_dependence ();
2511 *last_conflicts = integer_zero_node;
2512 goto end_analyze_subs_aa;
2515 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2518 *last_conflicts = chrec_dont_know;
2522 affine_fn_univar (build_int_cst (NULL_TREE, x1),
2524 build_int_cst (NULL_TREE, i1)));
2527 affine_fn_univar (build_int_cst (NULL_TREE, y1),
2529 build_int_cst (NULL_TREE, j1)));
2533 /* FIXME: For the moment, the upper bound of the
2534 iteration domain for i and j is not checked. */
2535 if (dump_file && (dump_flags & TDF_DETAILS))
2536 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2537 *overlaps_a = conflict_fn_not_known ();
2538 *overlaps_b = conflict_fn_not_known ();
2539 *last_conflicts = chrec_dont_know;
2544 if (dump_file && (dump_flags & TDF_DETAILS))
2545 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2546 *overlaps_a = conflict_fn_not_known ();
2547 *overlaps_b = conflict_fn_not_known ();
2548 *last_conflicts = chrec_dont_know;
2553 if (dump_file && (dump_flags & TDF_DETAILS))
2554 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2555 *overlaps_a = conflict_fn_not_known ();
2556 *overlaps_b = conflict_fn_not_known ();
2557 *last_conflicts = chrec_dont_know;
2560 end_analyze_subs_aa:
2561 obstack_free (&scratch_obstack, NULL);
2562 if (dump_file && (dump_flags & TDF_DETAILS))
2564 fprintf (dump_file, " (overlaps_a = ");
2565 dump_conflict_function (dump_file, *overlaps_a);
2566 fprintf (dump_file, ")\n (overlaps_b = ");
2567 dump_conflict_function (dump_file, *overlaps_b);
2568 fprintf (dump_file, ")\n");
2569 fprintf (dump_file, ")\n");
2573 /* Returns true when analyze_subscript_affine_affine can be used for
2574 determining the dependence relation between chrec_a and chrec_b,
2575 that contain symbols. This function modifies chrec_a and chrec_b
2576 such that the analysis result is the same, and such that they don't
2577 contain symbols, and then can safely be passed to the analyzer.
2579 Example: The analysis of the following tuples of evolutions produce
2580 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2583 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2584 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2588 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2590 tree diff, type, left_a, left_b, right_b;
2592 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2593 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2594 /* FIXME: For the moment not handled. Might be refined later. */
2597 type = chrec_type (*chrec_a);
2598 left_a = CHREC_LEFT (*chrec_a);
2599 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
2600 diff = chrec_fold_minus (type, left_a, left_b);
2602 if (!evolution_function_is_constant_p (diff))
2605 if (dump_file && (dump_flags & TDF_DETAILS))
2606 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2608 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2609 diff, CHREC_RIGHT (*chrec_a));
2610 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
2611 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2612 build_int_cst (type, 0),
2617 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2618 *OVERLAPS_B are initialized to the functions that describe the
2619 relation between the elements accessed twice by CHREC_A and
2620 CHREC_B. For k >= 0, the following property is verified:
2622 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2625 analyze_siv_subscript (tree chrec_a,
2627 conflict_function **overlaps_a,
2628 conflict_function **overlaps_b,
2629 tree *last_conflicts,
2632 dependence_stats.num_siv++;
2634 if (dump_file && (dump_flags & TDF_DETAILS))
2635 fprintf (dump_file, "(analyze_siv_subscript \n");
2637 if (evolution_function_is_constant_p (chrec_a)
2638 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2639 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2640 overlaps_a, overlaps_b, last_conflicts);
2642 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2643 && evolution_function_is_constant_p (chrec_b))
2644 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2645 overlaps_b, overlaps_a, last_conflicts);
2647 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2648 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2650 if (!chrec_contains_symbols (chrec_a)
2651 && !chrec_contains_symbols (chrec_b))
2653 analyze_subscript_affine_affine (chrec_a, chrec_b,
2654 overlaps_a, overlaps_b,
2657 if (CF_NOT_KNOWN_P (*overlaps_a)
2658 || CF_NOT_KNOWN_P (*overlaps_b))
2659 dependence_stats.num_siv_unimplemented++;
2660 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2661 || CF_NO_DEPENDENCE_P (*overlaps_b))
2662 dependence_stats.num_siv_independent++;
2664 dependence_stats.num_siv_dependent++;
2666 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2669 analyze_subscript_affine_affine (chrec_a, chrec_b,
2670 overlaps_a, overlaps_b,
2673 if (CF_NOT_KNOWN_P (*overlaps_a)
2674 || CF_NOT_KNOWN_P (*overlaps_b))
2675 dependence_stats.num_siv_unimplemented++;
2676 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2677 || CF_NO_DEPENDENCE_P (*overlaps_b))
2678 dependence_stats.num_siv_independent++;
2680 dependence_stats.num_siv_dependent++;
2683 goto siv_subscript_dontknow;
2688 siv_subscript_dontknow:;
2689 if (dump_file && (dump_flags & TDF_DETAILS))
2690 fprintf (dump_file, "siv test failed: unimplemented.\n");
2691 *overlaps_a = conflict_fn_not_known ();
2692 *overlaps_b = conflict_fn_not_known ();
2693 *last_conflicts = chrec_dont_know;
2694 dependence_stats.num_siv_unimplemented++;
2697 if (dump_file && (dump_flags & TDF_DETAILS))
2698 fprintf (dump_file, ")\n");
2701 /* Returns false if we can prove that the greatest common divisor of the steps
2702 of CHREC does not divide CST, false otherwise. */
2705 gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
2707 HOST_WIDE_INT cd = 0, val;
2710 if (!host_integerp (cst, 0))
2712 val = tree_low_cst (cst, 0);
2714 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2716 step = CHREC_RIGHT (chrec);
2717 if (!host_integerp (step, 0))
2719 cd = gcd (cd, tree_low_cst (step, 0));
2720 chrec = CHREC_LEFT (chrec);
2723 return val % cd == 0;
2726 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2727 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2728 functions that describe the relation between the elements accessed
2729 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2732 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2735 analyze_miv_subscript (tree chrec_a,
2737 conflict_function **overlaps_a,
2738 conflict_function **overlaps_b,
2739 tree *last_conflicts,
2740 struct loop *loop_nest)
2742 tree type, difference;
2744 dependence_stats.num_miv++;
2745 if (dump_file && (dump_flags & TDF_DETAILS))
2746 fprintf (dump_file, "(analyze_miv_subscript \n");
2748 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
2749 chrec_a = chrec_convert (type, chrec_a, NULL);
2750 chrec_b = chrec_convert (type, chrec_b, NULL);
2751 difference = chrec_fold_minus (type, chrec_a, chrec_b);
2753 if (eq_evolutions_p (chrec_a, chrec_b))
2755 /* Access functions are the same: all the elements are accessed
2756 in the same order. */
2757 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2758 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2759 *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a));
2760 dependence_stats.num_miv_dependent++;
2763 else if (evolution_function_is_constant_p (difference)
2764 /* For the moment, the following is verified:
2765 evolution_function_is_affine_multivariate_p (chrec_a,
2767 && !gcd_of_steps_may_divide_p (chrec_a, difference))
2769 /* testsuite/.../ssa-chrec-33.c
2770 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2772 The difference is 1, and all the evolution steps are multiples
2773 of 2, consequently there are no overlapping elements. */
2774 *overlaps_a = conflict_fn_no_dependence ();
2775 *overlaps_b = conflict_fn_no_dependence ();
2776 *last_conflicts = integer_zero_node;
2777 dependence_stats.num_miv_independent++;
2780 else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2781 && !chrec_contains_symbols (chrec_a)
2782 && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
2783 && !chrec_contains_symbols (chrec_b))
2785 /* testsuite/.../ssa-chrec-35.c
2786 {0, +, 1}_2 vs. {0, +, 1}_3
2787 the overlapping elements are respectively located at iterations:
2788 {0, +, 1}_x and {0, +, 1}_x,
2789 in other words, we have the equality:
2790 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2793 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2794 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2796 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2797 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2799 analyze_subscript_affine_affine (chrec_a, chrec_b,
2800 overlaps_a, overlaps_b, last_conflicts);
2802 if (CF_NOT_KNOWN_P (*overlaps_a)
2803 || CF_NOT_KNOWN_P (*overlaps_b))
2804 dependence_stats.num_miv_unimplemented++;
2805 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2806 || CF_NO_DEPENDENCE_P (*overlaps_b))
2807 dependence_stats.num_miv_independent++;
2809 dependence_stats.num_miv_dependent++;
2814 /* When the analysis is too difficult, answer "don't know". */
2815 if (dump_file && (dump_flags & TDF_DETAILS))
2816 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2818 *overlaps_a = conflict_fn_not_known ();
2819 *overlaps_b = conflict_fn_not_known ();
2820 *last_conflicts = chrec_dont_know;
2821 dependence_stats.num_miv_unimplemented++;
2824 if (dump_file && (dump_flags & TDF_DETAILS))
2825 fprintf (dump_file, ")\n");
2828 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2829 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2830 OVERLAP_ITERATIONS_B are initialized with two functions that
2831 describe the iterations that contain conflicting elements.
2833 Remark: For an integer k >= 0, the following equality is true:
2835 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2839 analyze_overlapping_iterations (tree chrec_a,
2841 conflict_function **overlap_iterations_a,
2842 conflict_function **overlap_iterations_b,
2843 tree *last_conflicts, struct loop *loop_nest)
2845 unsigned int lnn = loop_nest->num;
2847 dependence_stats.num_subscript_tests++;
2849 if (dump_file && (dump_flags & TDF_DETAILS))
2851 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2852 fprintf (dump_file, " (chrec_a = ");
2853 print_generic_expr (dump_file, chrec_a, 0);
2854 fprintf (dump_file, ")\n (chrec_b = ");
2855 print_generic_expr (dump_file, chrec_b, 0);
2856 fprintf (dump_file, ")\n");
2859 if (chrec_a == NULL_TREE
2860 || chrec_b == NULL_TREE
2861 || chrec_contains_undetermined (chrec_a)
2862 || chrec_contains_undetermined (chrec_b))
2864 dependence_stats.num_subscript_undetermined++;
2866 *overlap_iterations_a = conflict_fn_not_known ();
2867 *overlap_iterations_b = conflict_fn_not_known ();
2870 /* If they are the same chrec, and are affine, they overlap
2871 on every iteration. */
2872 else if (eq_evolutions_p (chrec_a, chrec_b)
2873 && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2874 || operand_equal_p (chrec_a, chrec_b, 0)))
2876 dependence_stats.num_same_subscript_function++;
2877 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2878 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2879 *last_conflicts = chrec_dont_know;
2882 /* If they aren't the same, and aren't affine, we can't do anything
2884 else if ((chrec_contains_symbols (chrec_a)
2885 || chrec_contains_symbols (chrec_b))
2886 && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2887 || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
2889 dependence_stats.num_subscript_undetermined++;
2890 *overlap_iterations_a = conflict_fn_not_known ();
2891 *overlap_iterations_b = conflict_fn_not_known ();
2894 else if (ziv_subscript_p (chrec_a, chrec_b))
2895 analyze_ziv_subscript (chrec_a, chrec_b,
2896 overlap_iterations_a, overlap_iterations_b,
2899 else if (siv_subscript_p (chrec_a, chrec_b))
2900 analyze_siv_subscript (chrec_a, chrec_b,
2901 overlap_iterations_a, overlap_iterations_b,
2902 last_conflicts, lnn);
2905 analyze_miv_subscript (chrec_a, chrec_b,
2906 overlap_iterations_a, overlap_iterations_b,
2907 last_conflicts, loop_nest);
2909 if (dump_file && (dump_flags & TDF_DETAILS))
2911 fprintf (dump_file, " (overlap_iterations_a = ");
2912 dump_conflict_function (dump_file, *overlap_iterations_a);
2913 fprintf (dump_file, ")\n (overlap_iterations_b = ");
2914 dump_conflict_function (dump_file, *overlap_iterations_b);
2915 fprintf (dump_file, ")\n");
2916 fprintf (dump_file, ")\n");
2920 /* Helper function for uniquely inserting distance vectors. */
2923 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
2928 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, v)
2929 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
2932 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
2935 /* Helper function for uniquely inserting direction vectors. */
2938 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
2943 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), i, v)
2944 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
2947 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
2950 /* Add a distance of 1 on all the loops outer than INDEX. If we
2951 haven't yet determined a distance for this outer loop, push a new
2952 distance vector composed of the previous distance, and a distance
2953 of 1 for this outer loop. Example:
2961 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2962 save (0, 1), then we have to save (1, 0). */
2965 add_outer_distances (struct data_dependence_relation *ddr,
2966 lambda_vector dist_v, int index)
2968 /* For each outer loop where init_v is not set, the accesses are
2969 in dependence of distance 1 in the loop. */
2970 while (--index >= 0)
2972 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2973 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
2975 save_dist_v (ddr, save_v);
2979 /* Return false when fail to represent the data dependence as a
2980 distance vector. INIT_B is set to true when a component has been
2981 added to the distance vector DIST_V. INDEX_CARRY is then set to
2982 the index in DIST_V that carries the dependence. */
2985 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
2986 struct data_reference *ddr_a,
2987 struct data_reference *ddr_b,
2988 lambda_vector dist_v, bool *init_b,
2992 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2994 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2996 tree access_fn_a, access_fn_b;
2997 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2999 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3001 non_affine_dependence_relation (ddr);
3005 access_fn_a = DR_ACCESS_FN (ddr_a, i);
3006 access_fn_b = DR_ACCESS_FN (ddr_b, i);
3008 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3009 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3012 int var_a = CHREC_VARIABLE (access_fn_a);
3013 int var_b = CHREC_VARIABLE (access_fn_b);
3016 || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3018 non_affine_dependence_relation (ddr);
3022 dist = int_cst_value (SUB_DISTANCE (subscript));
3023 index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
3024 *index_carry = MIN (index, *index_carry);
3026 /* This is the subscript coupling test. If we have already
3027 recorded a distance for this loop (a distance coming from
3028 another subscript), it should be the same. For example,
3029 in the following code, there is no dependence:
3036 if (init_v[index] != 0 && dist_v[index] != dist)
3038 finalize_ddr_dependent (ddr, chrec_known);
3042 dist_v[index] = dist;
3046 else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
3048 /* This can be for example an affine vs. constant dependence
3049 (T[i] vs. T[3]) that is not an affine dependence and is
3050 not representable as a distance vector. */
3051 non_affine_dependence_relation (ddr);
3059 /* Return true when the DDR contains only constant access functions. */
3062 constant_access_functions (const struct data_dependence_relation *ddr)
3066 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3067 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
3068 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
3074 /* Helper function for the case where DDR_A and DDR_B are the same
3075 multivariate access function with a constant step. For an example
3079 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3082 tree c_1 = CHREC_LEFT (c_2);
3083 tree c_0 = CHREC_LEFT (c_1);
3084 lambda_vector dist_v;
3087 /* Polynomials with more than 2 variables are not handled yet. When
3088 the evolution steps are parameters, it is not possible to
3089 represent the dependence using classical distance vectors. */
3090 if (TREE_CODE (c_0) != INTEGER_CST
3091 || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
3092 || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
3094 DDR_AFFINE_P (ddr) = false;
3098 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3099 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3101 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3102 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3103 v1 = int_cst_value (CHREC_RIGHT (c_1));
3104 v2 = int_cst_value (CHREC_RIGHT (c_2));
3117 save_dist_v (ddr, dist_v);
3119 add_outer_distances (ddr, dist_v, x_1);
3122 /* Helper function for the case where DDR_A and DDR_B are the same
3123 access functions. */
3126 add_other_self_distances (struct data_dependence_relation *ddr)
3128 lambda_vector dist_v;
3130 int index_carry = DDR_NB_LOOPS (ddr);
3132 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3134 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3136 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3138 if (!evolution_function_is_univariate_p (access_fun))
3140 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3142 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3146 access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
3148 if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
3149 add_multivariate_self_dist (ddr, access_fun);
3151 /* The evolution step is not constant: it varies in
3152 the outer loop, so this cannot be represented by a
3153 distance vector. For example in pr34635.c the
3154 evolution is {0, +, {0, +, 4}_1}_2. */
3155 DDR_AFFINE_P (ddr) = false;
3160 index_carry = MIN (index_carry,
3161 index_in_loop_nest (CHREC_VARIABLE (access_fun),
3162 DDR_LOOP_NEST (ddr)));
3166 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3167 add_outer_distances (ddr, dist_v, index_carry);
3171 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
3173 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3175 dist_v[DDR_INNER_LOOP (ddr)] = 1;
3176 save_dist_v (ddr, dist_v);
3179 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3180 is the case for example when access functions are the same and
3181 equal to a constant, as in:
3188 in which case the distance vectors are (0) and (1). */
3191 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
3195 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3197 subscript_p sub = DDR_SUBSCRIPT (ddr, i);
3198 conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
3199 conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
3201 for (j = 0; j < ca->n; j++)
3202 if (affine_function_zero_p (ca->fns[j]))
3204 insert_innermost_unit_dist_vector (ddr);
3208 for (j = 0; j < cb->n; j++)
3209 if (affine_function_zero_p (cb->fns[j]))
3211 insert_innermost_unit_dist_vector (ddr);
3217 /* Compute the classic per loop distance vector. DDR is the data
3218 dependence relation to build a vector from. Return false when fail
3219 to represent the data dependence as a distance vector. */
3222 build_classic_dist_vector (struct data_dependence_relation *ddr,
3223 struct loop *loop_nest)
3225 bool init_b = false;
3226 int index_carry = DDR_NB_LOOPS (ddr);
3227 lambda_vector dist_v;
3229 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3232 if (same_access_functions (ddr))
3234 /* Save the 0 vector. */
3235 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3236 save_dist_v (ddr, dist_v);
3238 if (constant_access_functions (ddr))
3239 add_distance_for_zero_overlaps (ddr);
3241 if (DDR_NB_LOOPS (ddr) > 1)
3242 add_other_self_distances (ddr);
3247 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3248 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3249 dist_v, &init_b, &index_carry))
3252 /* Save the distance vector if we initialized one. */
3255 /* Verify a basic constraint: classic distance vectors should
3256 always be lexicographically positive.
3258 Data references are collected in the order of execution of
3259 the program, thus for the following loop
3261 | for (i = 1; i < 100; i++)
3262 | for (j = 1; j < 100; j++)
3264 | t = T[j+1][i-1]; // A
3265 | T[j][i] = t + 2; // B
3268 references are collected following the direction of the wind:
3269 A then B. The data dependence tests are performed also
3270 following this order, such that we're looking at the distance
3271 separating the elements accessed by A from the elements later
3272 accessed by B. But in this example, the distance returned by
3273 test_dep (A, B) is lexicographically negative (-1, 1), that
3274 means that the access A occurs later than B with respect to
3275 the outer loop, ie. we're actually looking upwind. In this
3276 case we solve test_dep (B, A) looking downwind to the
3277 lexicographically positive solution, that returns the
3278 distance vector (1, -1). */
3279 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3281 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3282 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3285 compute_subscript_distance (ddr);
3286 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3287 save_v, &init_b, &index_carry))
3289 save_dist_v (ddr, save_v);
3290 DDR_REVERSED_P (ddr) = true;
3292 /* In this case there is a dependence forward for all the
3295 | for (k = 1; k < 100; k++)
3296 | for (i = 1; i < 100; i++)
3297 | for (j = 1; j < 100; j++)
3299 | t = T[j+1][i-1]; // A
3300 | T[j][i] = t + 2; // B
3308 if (DDR_NB_LOOPS (ddr) > 1)
3310 add_outer_distances (ddr, save_v, index_carry);
3311 add_outer_distances (ddr, dist_v, index_carry);
3316 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3317 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3319 if (DDR_NB_LOOPS (ddr) > 1)
3321 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3323 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
3324 DDR_A (ddr), loop_nest))
3326 compute_subscript_distance (ddr);
3327 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3328 opposite_v, &init_b,
3332 save_dist_v (ddr, save_v);
3333 add_outer_distances (ddr, dist_v, index_carry);
3334 add_outer_distances (ddr, opposite_v, index_carry);
3337 save_dist_v (ddr, save_v);
3342 /* There is a distance of 1 on all the outer loops: Example:
3343 there is a dependence of distance 1 on loop_1 for the array A.
3349 add_outer_distances (ddr, dist_v,
3350 lambda_vector_first_nz (dist_v,
3351 DDR_NB_LOOPS (ddr), 0));
3354 if (dump_file && (dump_flags & TDF_DETAILS))
3358 fprintf (dump_file, "(build_classic_dist_vector\n");
3359 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3361 fprintf (dump_file, " dist_vector = (");
3362 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3363 DDR_NB_LOOPS (ddr));
3364 fprintf (dump_file, " )\n");
3366 fprintf (dump_file, ")\n");
3372 /* Return the direction for a given distance.
3373 FIXME: Computing dir this way is suboptimal, since dir can catch
3374 cases that dist is unable to represent. */
3376 static inline enum data_dependence_direction
3377 dir_from_dist (int dist)
3380 return dir_positive;
3382 return dir_negative;
3387 /* Compute the classic per loop direction vector. DDR is the data
3388 dependence relation to build a vector from. */
3391 build_classic_dir_vector (struct data_dependence_relation *ddr)
3394 lambda_vector dist_v;
3396 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v)
3398 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3400 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3401 dir_v[j] = dir_from_dist (dist_v[j]);
3403 save_dir_v (ddr, dir_v);
3407 /* Helper function. Returns true when there is a dependence between
3408 data references DRA and DRB. */
3411 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3412 struct data_reference *dra,
3413 struct data_reference *drb,
3414 struct loop *loop_nest)
3417 tree last_conflicts;
3418 struct subscript *subscript;
3420 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3423 conflict_function *overlaps_a, *overlaps_b;
3425 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3426 DR_ACCESS_FN (drb, i),
3427 &overlaps_a, &overlaps_b,
3428 &last_conflicts, loop_nest);
3430 if (CF_NOT_KNOWN_P (overlaps_a)
3431 || CF_NOT_KNOWN_P (overlaps_b))
3433 finalize_ddr_dependent (ddr, chrec_dont_know);
3434 dependence_stats.num_dependence_undetermined++;
3435 free_conflict_function (overlaps_a);
3436 free_conflict_function (overlaps_b);
3440 else if (CF_NO_DEPENDENCE_P (overlaps_a)
3441 || CF_NO_DEPENDENCE_P (overlaps_b))
3443 finalize_ddr_dependent (ddr, chrec_known);
3444 dependence_stats.num_dependence_independent++;
3445 free_conflict_function (overlaps_a);
3446 free_conflict_function (overlaps_b);
3452 if (SUB_CONFLICTS_IN_A (subscript))
3453 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3454 if (SUB_CONFLICTS_IN_B (subscript))
3455 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3457 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3458 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3459 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3466 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3469 subscript_dependence_tester (struct data_dependence_relation *ddr,
3470 struct loop *loop_nest)
3473 if (dump_file && (dump_flags & TDF_DETAILS))
3474 fprintf (dump_file, "(subscript_dependence_tester \n");
3476 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3477 dependence_stats.num_dependence_dependent++;
3479 compute_subscript_distance (ddr);
3480 if (build_classic_dist_vector (ddr, loop_nest))
3481 build_classic_dir_vector (ddr);
3483 if (dump_file && (dump_flags & TDF_DETAILS))
3484 fprintf (dump_file, ")\n");
3487 /* Returns true when all the access functions of A are affine or
3488 constant with respect to LOOP_NEST. */
3491 access_functions_are_affine_or_constant_p (const struct data_reference *a,
3492 const struct loop *loop_nest)
3495 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3498 FOR_EACH_VEC_ELT (tree, fns, i, t)
3499 if (!evolution_function_is_invariant_p (t, loop_nest->num)
3500 && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3506 /* Initializes an equation for an OMEGA problem using the information
3507 contained in the ACCESS_FUN. Returns true when the operation
3510 PB is the omega constraint system.
3511 EQ is the number of the equation to be initialized.
3512 OFFSET is used for shifting the variables names in the constraints:
3513 a constrain is composed of 2 * the number of variables surrounding
3514 dependence accesses. OFFSET is set either to 0 for the first n variables,
3515 then it is set to n.
3516 ACCESS_FUN is expected to be an affine chrec. */
3519 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3520 unsigned int offset, tree access_fun,
3521 struct data_dependence_relation *ddr)
3523 switch (TREE_CODE (access_fun))
3525 case POLYNOMIAL_CHREC:
3527 tree left = CHREC_LEFT (access_fun);
3528 tree right = CHREC_RIGHT (access_fun);
3529 int var = CHREC_VARIABLE (access_fun);
3532 if (TREE_CODE (right) != INTEGER_CST)
3535 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3536 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3538 /* Compute the innermost loop index. */
3539 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3542 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3543 += int_cst_value (right);
3545 switch (TREE_CODE (left))
3547 case POLYNOMIAL_CHREC:
3548 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3551 pb->eqs[eq].coef[0] += int_cst_value (left);
3560 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3568 /* As explained in the comments preceding init_omega_for_ddr, we have
3569 to set up a system for each loop level, setting outer loops
3570 variation to zero, and current loop variation to positive or zero.
3571 Save each lexico positive distance vector. */
3574 omega_extract_distance_vectors (omega_pb pb,
3575 struct data_dependence_relation *ddr)
3579 struct loop *loopi, *loopj;
3580 enum omega_result res;
3582 /* Set a new problem for each loop in the nest. The basis is the
3583 problem that we have initialized until now. On top of this we
3584 add new constraints. */
3585 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3586 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3589 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3590 DDR_NB_LOOPS (ddr));
3592 omega_copy_problem (copy, pb);
3594 /* For all the outer loops "loop_j", add "dj = 0". */
3596 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3598 eq = omega_add_zero_eq (copy, omega_black);
3599 copy->eqs[eq].coef[j + 1] = 1;
3602 /* For "loop_i", add "0 <= di". */
3603 geq = omega_add_zero_geq (copy, omega_black);
3604 copy->geqs[geq].coef[i + 1] = 1;
3606 /* Reduce the constraint system, and test that the current
3607 problem is feasible. */
3608 res = omega_simplify_problem (copy);
3609 if (res == omega_false
3610 || res == omega_unknown
3611 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3614 for (eq = 0; eq < copy->num_subs; eq++)
3615 if (copy->subs[eq].key == (int) i + 1)
3617 dist = copy->subs[eq].coef[0];
3623 /* Reinitialize problem... */
3624 omega_copy_problem (copy, pb);
3626 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3628 eq = omega_add_zero_eq (copy, omega_black);
3629 copy->eqs[eq].coef[j + 1] = 1;
3632 /* ..., but this time "di = 1". */
3633 eq = omega_add_zero_eq (copy, omega_black);
3634 copy->eqs[eq].coef[i + 1] = 1;
3635 copy->eqs[eq].coef[0] = -1;
3637 res = omega_simplify_problem (copy);
3638 if (res == omega_false
3639 || res == omega_unknown
3640 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3643 for (eq = 0; eq < copy->num_subs; eq++)
3644 if (copy->subs[eq].key == (int) i + 1)
3646 dist = copy->subs[eq].coef[0];
3652 /* Save the lexicographically positive distance vector. */
3655 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3656 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3660 for (eq = 0; eq < copy->num_subs; eq++)
3661 if (copy->subs[eq].key > 0)
3663 dist = copy->subs[eq].coef[0];
3664 dist_v[copy->subs[eq].key - 1] = dist;
3667 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3668 dir_v[j] = dir_from_dist (dist_v[j]);
3670 save_dist_v (ddr, dist_v);
3671 save_dir_v (ddr, dir_v);
3675 omega_free_problem (copy);
3679 /* This is called for each subscript of a tuple of data references:
3680 insert an equality for representing the conflicts. */
3683 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3684 struct data_dependence_relation *ddr,
3685 omega_pb pb, bool *maybe_dependent)
3688 tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3689 TREE_TYPE (access_fun_b));
3690 tree fun_a = chrec_convert (type, access_fun_a, NULL);
3691 tree fun_b = chrec_convert (type, access_fun_b, NULL);
3692 tree difference = chrec_fold_minus (type, fun_a, fun_b);
3695 /* When the fun_a - fun_b is not constant, the dependence is not
3696 captured by the classic distance vector representation. */
3697 if (TREE_CODE (difference) != INTEGER_CST)
3701 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3703 /* There is no dependence. */
3704 *maybe_dependent = false;
3708 minus_one = build_int_cst (type, -1);
3709 fun_b = chrec_fold_multiply (type, fun_b, minus_one);
3711 eq = omega_add_zero_eq (pb, omega_black);
3712 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3713 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3714 /* There is probably a dependence, but the system of
3715 constraints cannot be built: answer "don't know". */
3719 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3720 && !int_divides_p (lambda_vector_gcd
3721 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3722 2 * DDR_NB_LOOPS (ddr)),
3723 pb->eqs[eq].coef[0]))
3725 /* There is no dependence. */
3726 *maybe_dependent = false;
3733 /* Helper function, same as init_omega_for_ddr but specialized for
3734 data references A and B. */
3737 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3738 struct data_dependence_relation *ddr,
3739 omega_pb pb, bool *maybe_dependent)
3744 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3746 /* Insert an equality per subscript. */
3747 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3749 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3750 ddr, pb, maybe_dependent))
3752 else if (*maybe_dependent == false)
3754 /* There is no dependence. */
3755 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3760 /* Insert inequalities: constraints corresponding to the iteration
3761 domain, i.e. the loops surrounding the references "loop_x" and
3762 the distance variables "dx". The layout of the OMEGA
3763 representation is as follows:
3764 - coef[0] is the constant
3765 - coef[1..nb_loops] are the protected variables that will not be
3766 removed by the solver: the "dx"
3767 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3769 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3770 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3772 HOST_WIDE_INT nbi = max_stmt_executions_int (loopi, true);
3775 ineq = omega_add_zero_geq (pb, omega_black);
3776 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3778 /* 0 <= loop_x + dx */
3779 ineq = omega_add_zero_geq (pb, omega_black);
3780 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3781 pb->geqs[ineq].coef[i + 1] = 1;
3785 /* loop_x <= nb_iters */
3786 ineq = omega_add_zero_geq (pb, omega_black);
3787 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3788 pb->geqs[ineq].coef[0] = nbi;
3790 /* loop_x + dx <= nb_iters */
3791 ineq = omega_add_zero_geq (pb, omega_black);
3792 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3793 pb->geqs[ineq].coef[i + 1] = -1;
3794 pb->geqs[ineq].coef[0] = nbi;
3796 /* A step "dx" bigger than nb_iters is not feasible, so
3797 add "0 <= nb_iters + dx", */
3798 ineq = omega_add_zero_geq (pb, omega_black);
3799 pb->geqs[ineq].coef[i + 1] = 1;
3800 pb->geqs[ineq].coef[0] = nbi;
3801 /* and "dx <= nb_iters". */
3802 ineq = omega_add_zero_geq (pb, omega_black);
3803 pb->geqs[ineq].coef[i + 1] = -1;
3804 pb->geqs[ineq].coef[0] = nbi;
3808 omega_extract_distance_vectors (pb, ddr);
3813 /* Sets up the Omega dependence problem for the data dependence
3814 relation DDR. Returns false when the constraint system cannot be
3815 built, ie. when the test answers "don't know". Returns true
3816 otherwise, and when independence has been proved (using one of the
3817 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3818 set MAYBE_DEPENDENT to true.
3820 Example: for setting up the dependence system corresponding to the
3821 conflicting accesses
3826 | ... A[2*j, 2*(i + j)]
3830 the following constraints come from the iteration domain:
3837 where di, dj are the distance variables. The constraints
3838 representing the conflicting elements are:
3841 i + 1 = 2 * (i + di + j + dj)
3843 For asking that the resulting distance vector (di, dj) be
3844 lexicographically positive, we insert the constraint "di >= 0". If
3845 "di = 0" in the solution, we fix that component to zero, and we
3846 look at the inner loops: we set a new problem where all the outer
3847 loop distances are zero, and fix this inner component to be
3848 positive. When one of the components is positive, we save that
3849 distance, and set a new problem where the distance on this loop is
3850 zero, searching for other distances in the inner loops. Here is
3851 the classic example that illustrates that we have to set for each
3852 inner loop a new problem:
3860 we have to save two distances (1, 0) and (0, 1).
3862 Given two array references, refA and refB, we have to set the
3863 dependence problem twice, refA vs. refB and refB vs. refA, and we
3864 cannot do a single test, as refB might occur before refA in the
3865 inner loops, and the contrary when considering outer loops: ex.
3870 | T[{1,+,1}_2][{1,+,1}_1] // refA
3871 | T[{2,+,1}_2][{0,+,1}_1] // refB
3876 refB touches the elements in T before refA, and thus for the same
3877 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3878 but for successive loop_0 iterations, we have (1, -1, 1)
3880 The Omega solver expects the distance variables ("di" in the
3881 previous example) to come first in the constraint system (as
3882 variables to be protected, or "safe" variables), the constraint
3883 system is built using the following layout:
3885 "cst | distance vars | index vars".
3889 init_omega_for_ddr (struct data_dependence_relation *ddr,
3890 bool *maybe_dependent)
3895 *maybe_dependent = true;
3897 if (same_access_functions (ddr))
3900 lambda_vector dir_v;
3902 /* Save the 0 vector. */
3903 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3904 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3905 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3906 dir_v[j] = dir_equal;
3907 save_dir_v (ddr, dir_v);
3909 /* Save the dependences carried by outer loops. */
3910 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3911 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3913 omega_free_problem (pb);
3917 /* Omega expects the protected variables (those that have to be kept
3918 after elimination) to appear first in the constraint system.
3919 These variables are the distance variables. In the following
3920 initialization we declare NB_LOOPS safe variables, and the total
3921 number of variables for the constraint system is 2*NB_LOOPS. */
3922 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3923 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3925 omega_free_problem (pb);
3927 /* Stop computation if not decidable, or no dependence. */
3928 if (res == false || *maybe_dependent == false)
3931 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3932 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3934 omega_free_problem (pb);
3939 /* Return true when DDR contains the same information as that stored
3940 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3943 ddr_consistent_p (FILE *file,
3944 struct data_dependence_relation *ddr,
3945 VEC (lambda_vector, heap) *dist_vects,
3946 VEC (lambda_vector, heap) *dir_vects)
3950 /* If dump_file is set, output there. */
3951 if (dump_file && (dump_flags & TDF_DETAILS))
3954 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3956 lambda_vector b_dist_v;
3957 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3958 VEC_length (lambda_vector, dist_vects),
3959 DDR_NUM_DIST_VECTS (ddr));
3961 fprintf (file, "Banerjee dist vectors:\n");
3962 FOR_EACH_VEC_ELT (lambda_vector, dist_vects, i, b_dist_v)
3963 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3965 fprintf (file, "Omega dist vectors:\n");
3966 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3967 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3969 fprintf (file, "data dependence relation:\n");
3970 dump_data_dependence_relation (file, ddr);
3972 fprintf (file, ")\n");
3976 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3978 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3979 VEC_length (lambda_vector, dir_vects),
3980 DDR_NUM_DIR_VECTS (ddr));
3984 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3986 lambda_vector a_dist_v;
3987 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3989 /* Distance vectors are not ordered in the same way in the DDR
3990 and in the DIST_VECTS: search for a matching vector. */
3991 FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, a_dist_v)
3992 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3995 if (j == VEC_length (lambda_vector, dist_vects))
3997 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3998 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3999 fprintf (file, "not found in Omega dist vectors:\n");
4000 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
4001 fprintf (file, "data dependence relation:\n");
4002 dump_data_dependence_relation (file, ddr);
4003 fprintf (file, ")\n");
4007 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
4009 lambda_vector a_dir_v;
4010 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
4012 /* Direction vectors are not ordered in the same way in the DDR
4013 and in the DIR_VECTS: search for a matching vector. */
4014 FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, a_dir_v)
4015 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
4018 if (j == VEC_length (lambda_vector, dist_vects))
4020 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
4021 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
4022 fprintf (file, "not found in Omega dir vectors:\n");
4023 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
4024 fprintf (file, "data dependence relation:\n");
4025 dump_data_dependence_relation (file, ddr);
4026 fprintf (file, ")\n");
4033 /* This computes the affine dependence relation between A and B with
4034 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4035 independence between two accesses, while CHREC_DONT_KNOW is used
4036 for representing the unknown relation.
4038 Note that it is possible to stop the computation of the dependence
4039 relation the first time we detect a CHREC_KNOWN element for a given
4043 compute_affine_dependence (struct data_dependence_relation *ddr,
4044 struct loop *loop_nest)
4046 struct data_reference *dra = DDR_A (ddr);
4047 struct data_reference *drb = DDR_B (ddr);
4049 if (dump_file && (dump_flags & TDF_DETAILS))
4051 fprintf (dump_file, "(compute_affine_dependence\n");
4052 fprintf (dump_file, " (stmt_a = \n");
4053 print_gimple_stmt (dump_file, DR_STMT (dra), 0, 0);
4054 fprintf (dump_file, ")\n (stmt_b = \n");
4055 print_gimple_stmt (dump_file, DR_STMT (drb), 0, 0);
4056 fprintf (dump_file, ")\n");
4059 /* Analyze only when the dependence relation is not yet known. */
4060 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4062 dependence_stats.num_dependence_tests++;
4064 if (access_functions_are_affine_or_constant_p (dra, loop_nest)
4065 && access_functions_are_affine_or_constant_p (drb, loop_nest))
4067 if (flag_check_data_deps)
4069 /* Compute the dependences using the first algorithm. */
4070 subscript_dependence_tester (ddr, loop_nest);
4072 if (dump_file && (dump_flags & TDF_DETAILS))
4074 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
4075 dump_data_dependence_relation (dump_file, ddr);
4078 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4080 bool maybe_dependent;
4081 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
4083 /* Save the result of the first DD analyzer. */
4084 dist_vects = DDR_DIST_VECTS (ddr);
4085 dir_vects = DDR_DIR_VECTS (ddr);
4087 /* Reset the information. */
4088 DDR_DIST_VECTS (ddr) = NULL;
4089 DDR_DIR_VECTS (ddr) = NULL;
4091 /* Compute the same information using Omega. */
4092 if (!init_omega_for_ddr (ddr, &maybe_dependent))
4093 goto csys_dont_know;
4095 if (dump_file && (dump_flags & TDF_DETAILS))
4097 fprintf (dump_file, "Omega Analyzer\n");
4098 dump_data_dependence_relation (dump_file, ddr);
4101 /* Check that we get the same information. */
4102 if (maybe_dependent)
4103 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
4108 subscript_dependence_tester (ddr, loop_nest);
4111 /* As a last case, if the dependence cannot be determined, or if
4112 the dependence is considered too difficult to determine, answer
4117 dependence_stats.num_dependence_undetermined++;
4119 if (dump_file && (dump_flags & TDF_DETAILS))
4121 fprintf (dump_file, "Data ref a:\n");
4122 dump_data_reference (dump_file, dra);
4123 fprintf (dump_file, "Data ref b:\n");
4124 dump_data_reference (dump_file, drb);
4125 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
4127 finalize_ddr_dependent (ddr, chrec_dont_know);
4131 if (dump_file && (dump_flags & TDF_DETAILS))
4132 fprintf (dump_file, ")\n");
4135 /* This computes the dependence relation for the same data
4136 reference into DDR. */
4139 compute_self_dependence (struct data_dependence_relation *ddr)
4141 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
4144 if (DDR_LOOP_NEST (ddr))
4145 compute_affine_dependence (ddr, VEC_index (loop_p, DDR_LOOP_NEST (ddr), 0));
4148 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4149 the data references in DATAREFS, in the LOOP_NEST. When
4150 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4154 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
4155 VEC (ddr_p, heap) **dependence_relations,
4156 VEC (loop_p, heap) *loop_nest,
4157 bool compute_self_and_rr)
4159 struct data_dependence_relation *ddr;
4160 struct data_reference *a, *b;
4163 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
4164 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
4165 if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
4167 ddr = initialize_data_dependence_relation (a, b, loop_nest);
4168 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4170 compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
4173 if (compute_self_and_rr)
4174 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
4176 ddr = initialize_data_dependence_relation (a, a, loop_nest);
4177 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4179 compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
4183 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4184 true if STMT clobbers memory, false otherwise. */
4187 get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
4189 bool clobbers_memory = false;
4192 enum gimple_code stmt_code = gimple_code (stmt);
4196 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4197 Calls have side-effects, except those to const or pure
4199 if ((stmt_code == GIMPLE_CALL
4200 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
4201 || (stmt_code == GIMPLE_ASM
4202 && gimple_asm_volatile_p (stmt)))
4203 clobbers_memory = true;
4205 if (!gimple_vuse (stmt))
4206 return clobbers_memory;
4208 if (stmt_code == GIMPLE_ASSIGN)
4211 op0 = gimple_assign_lhs_ptr (stmt);
4212 op1 = gimple_assign_rhs1_ptr (stmt);
4215 || (REFERENCE_CLASS_P (*op1)
4216 && (base = get_base_address (*op1))
4217 && TREE_CODE (base) != SSA_NAME))
4219 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4221 ref->is_read = true;
4224 else if (stmt_code == GIMPLE_CALL)
4228 op0 = gimple_call_lhs_ptr (stmt);
4229 n = gimple_call_num_args (stmt);
4230 for (i = 0; i < n; i++)
4232 op1 = gimple_call_arg_ptr (stmt, i);
4235 || (REFERENCE_CLASS_P (*op1) && get_base_address (*op1)))
4237 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4239 ref->is_read = true;
4244 return clobbers_memory;
4248 || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))))
4250 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4252 ref->is_read = false;
4254 return clobbers_memory;
4257 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4258 reference, returns false, otherwise returns true. NEST is the outermost
4259 loop of the loop nest in which the references should be analyzed. */
4262 find_data_references_in_stmt (struct loop *nest, gimple stmt,
4263 VEC (data_reference_p, heap) **datarefs)
4266 VEC (data_ref_loc, heap) *references;
4269 data_reference_p dr;
4271 if (get_references_in_stmt (stmt, &references))
4273 VEC_free (data_ref_loc, heap, references);
4277 FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
4279 dr = create_data_ref (nest, loop_containing_stmt (stmt),
4280 *ref->pos, stmt, ref->is_read);
4281 gcc_assert (dr != NULL);
4282 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4284 VEC_free (data_ref_loc, heap, references);
4288 /* Stores the data references in STMT to DATAREFS. If there is an
4289 unanalyzable reference, returns false, otherwise returns true.
4290 NEST is the outermost loop of the loop nest in which the references
4291 should be instantiated, LOOP is the loop in which the references
4292 should be analyzed. */
4295 graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
4296 VEC (data_reference_p, heap) **datarefs)
4299 VEC (data_ref_loc, heap) *references;
4302 data_reference_p dr;
4304 if (get_references_in_stmt (stmt, &references))
4306 VEC_free (data_ref_loc, heap, references);
4310 FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
4312 dr = create_data_ref (nest, loop, *ref->pos, stmt, ref->is_read);
4313 gcc_assert (dr != NULL);
4314 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4317 VEC_free (data_ref_loc, heap, references);
4321 /* Search the data references in LOOP, and record the information into
4322 DATAREFS. Returns chrec_dont_know when failing to analyze a
4323 difficult case, returns NULL_TREE otherwise. */
4326 find_data_references_in_bb (struct loop *loop, basic_block bb,
4327 VEC (data_reference_p, heap) **datarefs)
4329 gimple_stmt_iterator bsi;
4331 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4333 gimple stmt = gsi_stmt (bsi);
4335 if (!find_data_references_in_stmt (loop, stmt, datarefs))
4337 struct data_reference *res;
4338 res = XCNEW (struct data_reference);
4339 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4341 return chrec_dont_know;
4348 /* Search the data references in LOOP, and record the information into
4349 DATAREFS. Returns chrec_dont_know when failing to analyze a
4350 difficult case, returns NULL_TREE otherwise.
4352 TODO: This function should be made smarter so that it can handle address
4353 arithmetic as if they were array accesses, etc. */
4356 find_data_references_in_loop (struct loop *loop,
4357 VEC (data_reference_p, heap) **datarefs)
4359 basic_block bb, *bbs;
4362 bbs = get_loop_body_in_dom_order (loop);
4364 for (i = 0; i < loop->num_nodes; i++)
4368 if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know)
4371 return chrec_dont_know;
4379 /* Recursive helper function. */
4382 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4384 /* Inner loops of the nest should not contain siblings. Example:
4385 when there are two consecutive loops,
4396 the dependence relation cannot be captured by the distance
4401 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4403 return find_loop_nest_1 (loop->inner, loop_nest);
4407 /* Return false when the LOOP is not well nested. Otherwise return
4408 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4409 contain the loops from the outermost to the innermost, as they will
4410 appear in the classic distance vector. */
4413 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4415 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4417 return find_loop_nest_1 (loop->inner, loop_nest);
4421 /* Returns true when the data dependences have been computed, false otherwise.
4422 Given a loop nest LOOP, the following vectors are returned:
4423 DATAREFS is initialized to all the array elements contained in this loop,
4424 DEPENDENCE_RELATIONS contains the relations between the data references.
4425 Compute read-read and self relations if
4426 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4429 compute_data_dependences_for_loop (struct loop *loop,
4430 bool compute_self_and_read_read_dependences,
4431 VEC (loop_p, heap) **loop_nest,
4432 VEC (data_reference_p, heap) **datarefs,
4433 VEC (ddr_p, heap) **dependence_relations)
4437 memset (&dependence_stats, 0, sizeof (dependence_stats));
4439 /* If the loop nest is not well formed, or one of the data references
4440 is not computable, give up without spending time to compute other
4443 || !find_loop_nest (loop, loop_nest)
4444 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4446 struct data_dependence_relation *ddr;
4448 /* Insert a single relation into dependence_relations:
4450 ddr = initialize_data_dependence_relation (NULL, NULL, *loop_nest);
4451 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4455 compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
4456 compute_self_and_read_read_dependences);
4458 if (dump_file && (dump_flags & TDF_STATS))
4460 fprintf (dump_file, "Dependence tester statistics:\n");
4462 fprintf (dump_file, "Number of dependence tests: %d\n",
4463 dependence_stats.num_dependence_tests);
4464 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4465 dependence_stats.num_dependence_dependent);
4466 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4467 dependence_stats.num_dependence_independent);
4468 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4469 dependence_stats.num_dependence_undetermined);
4471 fprintf (dump_file, "Number of subscript tests: %d\n",
4472 dependence_stats.num_subscript_tests);
4473 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4474 dependence_stats.num_subscript_undetermined);
4475 fprintf (dump_file, "Number of same subscript function: %d\n",
4476 dependence_stats.num_same_subscript_function);
4478 fprintf (dump_file, "Number of ziv tests: %d\n",
4479 dependence_stats.num_ziv);
4480 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4481 dependence_stats.num_ziv_dependent);
4482 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4483 dependence_stats.num_ziv_independent);
4484 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4485 dependence_stats.num_ziv_unimplemented);
4487 fprintf (dump_file, "Number of siv tests: %d\n",
4488 dependence_stats.num_siv);
4489 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4490 dependence_stats.num_siv_dependent);
4491 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4492 dependence_stats.num_siv_independent);
4493 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4494 dependence_stats.num_siv_unimplemented);
4496 fprintf (dump_file, "Number of miv tests: %d\n",
4497 dependence_stats.num_miv);
4498 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4499 dependence_stats.num_miv_dependent);
4500 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4501 dependence_stats.num_miv_independent);
4502 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4503 dependence_stats.num_miv_unimplemented);
4509 /* Returns true when the data dependences for the basic block BB have been
4510 computed, false otherwise.
4511 DATAREFS is initialized to all the array elements contained in this basic
4512 block, DEPENDENCE_RELATIONS contains the relations between the data
4513 references. Compute read-read and self relations if
4514 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4516 compute_data_dependences_for_bb (basic_block bb,
4517 bool compute_self_and_read_read_dependences,
4518 VEC (data_reference_p, heap) **datarefs,
4519 VEC (ddr_p, heap) **dependence_relations)
4521 if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know)
4524 compute_all_dependences (*datarefs, dependence_relations, NULL,
4525 compute_self_and_read_read_dependences);
4529 /* Entry point (for testing only). Analyze all the data references
4530 and the dependence relations in LOOP.
4532 The data references are computed first.
4534 A relation on these nodes is represented by a complete graph. Some
4535 of the relations could be of no interest, thus the relations can be
4538 In the following function we compute all the relations. This is
4539 just a first implementation that is here for:
4540 - for showing how to ask for the dependence relations,
4541 - for the debugging the whole dependence graph,
4542 - for the dejagnu testcases and maintenance.
4544 It is possible to ask only for a part of the graph, avoiding to
4545 compute the whole dependence graph. The computed dependences are
4546 stored in a knowledge base (KB) such that later queries don't
4547 recompute the same information. The implementation of this KB is
4548 transparent to the optimizer, and thus the KB can be changed with a
4549 more efficient implementation, or the KB could be disabled. */
4551 analyze_all_data_dependences (struct loop *loop)
4554 int nb_data_refs = 10;
4555 VEC (data_reference_p, heap) *datarefs =
4556 VEC_alloc (data_reference_p, heap, nb_data_refs);
4557 VEC (ddr_p, heap) *dependence_relations =
4558 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4559 VEC (loop_p, heap) *loop_nest = VEC_alloc (loop_p, heap, 3);
4561 /* Compute DDs on the whole function. */
4562 compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs,
4563 &dependence_relations);
4567 dump_data_dependence_relations (dump_file, dependence_relations);
4568 fprintf (dump_file, "\n\n");
4570 if (dump_flags & TDF_DETAILS)
4571 dump_dist_dir_vectors (dump_file, dependence_relations);
4573 if (dump_flags & TDF_STATS)
4575 unsigned nb_top_relations = 0;
4576 unsigned nb_bot_relations = 0;
4577 unsigned nb_chrec_relations = 0;
4578 struct data_dependence_relation *ddr;
4580 FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
4582 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4585 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4589 nb_chrec_relations++;
4592 gather_stats_on_scev_database ();
4596 VEC_free (loop_p, heap, loop_nest);
4597 free_dependence_relations (dependence_relations);
4598 free_data_refs (datarefs);
4601 /* Computes all the data dependences and check that the results of
4602 several analyzers are the same. */
4605 tree_check_data_deps (void)
4608 struct loop *loop_nest;
4610 FOR_EACH_LOOP (li, loop_nest, 0)
4611 analyze_all_data_dependences (loop_nest);
4614 /* Free the memory used by a data dependence relation DDR. */
4617 free_dependence_relation (struct data_dependence_relation *ddr)
4622 if (DDR_SUBSCRIPTS (ddr))
4623 free_subscripts (DDR_SUBSCRIPTS (ddr));
4624 if (DDR_DIST_VECTS (ddr))
4625 VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
4626 if (DDR_DIR_VECTS (ddr))
4627 VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
4632 /* Free the memory used by the data dependence relations from
4633 DEPENDENCE_RELATIONS. */
4636 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4639 struct data_dependence_relation *ddr;
4641 FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
4643 free_dependence_relation (ddr);
4645 VEC_free (ddr_p, heap, dependence_relations);
4648 /* Free the memory used by the data references from DATAREFS. */
4651 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4654 struct data_reference *dr;
4656 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
4658 VEC_free (data_reference_p, heap, datarefs);
4663 /* Dump vertex I in RDG to FILE. */
4666 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
4668 struct vertex *v = &(rdg->vertices[i]);
4669 struct graph_edge *e;
4671 fprintf (file, "(vertex %d: (%s%s) (in:", i,
4672 RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
4673 RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
4676 for (e = v->pred; e; e = e->pred_next)
4677 fprintf (file, " %d", e->src);
4679 fprintf (file, ") (out:");
4682 for (e = v->succ; e; e = e->succ_next)
4683 fprintf (file, " %d", e->dest);
4685 fprintf (file, ")\n");
4686 print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
4687 fprintf (file, ")\n");
4690 /* Call dump_rdg_vertex on stderr. */
4693 debug_rdg_vertex (struct graph *rdg, int i)
4695 dump_rdg_vertex (stderr, rdg, i);
4698 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4699 dumped vertices to that bitmap. */
4701 void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
4705 fprintf (file, "(%d\n", c);
4707 for (i = 0; i < rdg->n_vertices; i++)
4708 if (rdg->vertices[i].component == c)
4711 bitmap_set_bit (dumped, i);
4713 dump_rdg_vertex (file, rdg, i);
4716 fprintf (file, ")\n");
4719 /* Call dump_rdg_vertex on stderr. */
4722 debug_rdg_component (struct graph *rdg, int c)
4724 dump_rdg_component (stderr, rdg, c, NULL);
4727 /* Dump the reduced dependence graph RDG to FILE. */
4730 dump_rdg (FILE *file, struct graph *rdg)
4733 bitmap dumped = BITMAP_ALLOC (NULL);
4735 fprintf (file, "(rdg\n");
4737 for (i = 0; i < rdg->n_vertices; i++)
4738 if (!bitmap_bit_p (dumped, i))
4739 dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
4741 fprintf (file, ")\n");
4742 BITMAP_FREE (dumped);
4745 /* Call dump_rdg on stderr. */
4748 debug_rdg (struct graph *rdg)
4750 dump_rdg (stderr, rdg);
4754 dot_rdg_1 (FILE *file, struct graph *rdg)
4758 fprintf (file, "digraph RDG {\n");
4760 for (i = 0; i < rdg->n_vertices; i++)
4762 struct vertex *v = &(rdg->vertices[i]);
4763 struct graph_edge *e;
4765 /* Highlight reads from memory. */
4766 if (RDG_MEM_READS_STMT (rdg, i))
4767 fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
4769 /* Highlight stores to memory. */
4770 if (RDG_MEM_WRITE_STMT (rdg, i))
4771 fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
4774 for (e = v->succ; e; e = e->succ_next)
4775 switch (RDGE_TYPE (e))
4778 fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
4782 fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
4786 /* These are the most common dependences: don't print these. */
4787 fprintf (file, "%d -> %d \n", i, e->dest);
4791 fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
4799 fprintf (file, "}\n\n");
4802 /* Display the Reduced Dependence Graph using dotty. */
4803 extern void dot_rdg (struct graph *);
4806 dot_rdg (struct graph *rdg)
4808 /* When debugging, enable the following code. This cannot be used
4809 in production compilers because it calls "system". */
4811 FILE *file = fopen ("/tmp/rdg.dot", "w");
4812 gcc_assert (file != NULL);
4814 dot_rdg_1 (file, rdg);
4817 system ("dotty /tmp/rdg.dot &");
4819 dot_rdg_1 (stderr, rdg);
4823 /* This structure is used for recording the mapping statement index in
4826 struct GTY(()) rdg_vertex_info
4832 /* Returns the index of STMT in RDG. */
4835 rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
4837 struct rdg_vertex_info rvi, *slot;
4840 slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
4848 /* Creates an edge in RDG for each distance vector from DDR. The
4849 order that we keep track of in the RDG is the order in which
4850 statements have to be executed. */
4853 create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
4855 struct graph_edge *e;
4857 data_reference_p dra = DDR_A (ddr);
4858 data_reference_p drb = DDR_B (ddr);
4859 unsigned level = ddr_dependence_level (ddr);
4861 /* For non scalar dependences, when the dependence is REVERSED,
4862 statement B has to be executed before statement A. */
4864 && !DDR_REVERSED_P (ddr))
4866 data_reference_p tmp = dra;
4871 va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
4872 vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
4874 if (va < 0 || vb < 0)
4877 e = add_edge (rdg, va, vb);
4878 e->data = XNEW (struct rdg_edge);
4880 RDGE_LEVEL (e) = level;
4881 RDGE_RELATION (e) = ddr;
4883 /* Determines the type of the data dependence. */
4884 if (DR_IS_READ (dra) && DR_IS_READ (drb))
4885 RDGE_TYPE (e) = input_dd;
4886 else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
4887 RDGE_TYPE (e) = output_dd;
4888 else if (DR_IS_WRITE (dra) && DR_IS_READ (drb))
4889 RDGE_TYPE (e) = flow_dd;
4890 else if (DR_IS_READ (dra) && DR_IS_WRITE (drb))
4891 RDGE_TYPE (e) = anti_dd;
4894 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4895 the index of DEF in RDG. */
4898 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
4900 use_operand_p imm_use_p;
4901 imm_use_iterator iterator;
4903 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
4905 struct graph_edge *e;
4906 int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
4911 e = add_edge (rdg, idef, use);
4912 e->data = XNEW (struct rdg_edge);
4913 RDGE_TYPE (e) = flow_dd;
4914 RDGE_RELATION (e) = NULL;
4918 /* Creates the edges of the reduced dependence graph RDG. */
4921 create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
4924 struct data_dependence_relation *ddr;
4925 def_operand_p def_p;
4928 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
4929 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4930 create_rdg_edge_for_ddr (rdg, ddr);
4932 for (i = 0; i < rdg->n_vertices; i++)
4933 FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
4935 create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
4938 /* Build the vertices of the reduced dependence graph RDG. */
4941 create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
4946 FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
4948 VEC (data_ref_loc, heap) *references;
4950 struct vertex *v = &(rdg->vertices[i]);
4951 struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
4952 struct rdg_vertex_info **slot;
4956 slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
4963 v->data = XNEW (struct rdg_vertex);
4964 RDG_STMT (rdg, i) = stmt;
4966 RDG_MEM_WRITE_STMT (rdg, i) = false;
4967 RDG_MEM_READS_STMT (rdg, i) = false;
4968 if (gimple_code (stmt) == GIMPLE_PHI)
4971 get_references_in_stmt (stmt, &references);
4972 FOR_EACH_VEC_ELT (data_ref_loc, references, j, ref)
4974 RDG_MEM_WRITE_STMT (rdg, i) = true;
4976 RDG_MEM_READS_STMT (rdg, i) = true;
4978 VEC_free (data_ref_loc, heap, references);
4982 /* Initialize STMTS with all the statements of LOOP. When
4983 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4984 which we discover statements is important as
4985 generate_loops_for_partition is using the same traversal for
4986 identifying statements. */
4989 stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
4992 basic_block *bbs = get_loop_body_in_dom_order (loop);
4994 for (i = 0; i < loop->num_nodes; i++)
4996 basic_block bb = bbs[i];
4997 gimple_stmt_iterator bsi;
5000 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
5001 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
5003 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
5005 stmt = gsi_stmt (bsi);
5006 if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
5007 VEC_safe_push (gimple, heap, *stmts, stmt);
5014 /* Returns true when all the dependences are computable. */
5017 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
5022 FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
5023 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
5029 /* Computes a hash function for element ELT. */
5032 hash_stmt_vertex_info (const void *elt)
5034 const struct rdg_vertex_info *const rvi =
5035 (const struct rdg_vertex_info *) elt;
5036 gimple stmt = rvi->stmt;
5038 return htab_hash_pointer (stmt);
5041 /* Compares database elements E1 and E2. */
5044 eq_stmt_vertex_info (const void *e1, const void *e2)
5046 const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
5047 const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
5049 return elt1->stmt == elt2->stmt;
5052 /* Free the element E. */
5055 hash_stmt_vertex_del (void *e)
5060 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5061 statement of the loop nest, and one edge per data dependence or
5062 scalar dependence. */
5065 build_empty_rdg (int n_stmts)
5067 int nb_data_refs = 10;
5068 struct graph *rdg = new_graph (n_stmts);
5070 rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
5071 eq_stmt_vertex_info, hash_stmt_vertex_del);
5075 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5076 statement of the loop nest, and one edge per data dependence or
5077 scalar dependence. */
5080 build_rdg (struct loop *loop,
5081 VEC (loop_p, heap) **loop_nest,
5082 VEC (ddr_p, heap) **dependence_relations,
5083 VEC (data_reference_p, heap) **datarefs)
5085 struct graph *rdg = NULL;
5086 VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
5088 compute_data_dependences_for_loop (loop, false, loop_nest, datarefs,
5089 dependence_relations);
5091 if (known_dependences_p (*dependence_relations))
5093 stmts_from_loop (loop, &stmts);
5094 rdg = build_empty_rdg (VEC_length (gimple, stmts));
5095 create_rdg_vertices (rdg, stmts);
5096 create_rdg_edges (rdg, *dependence_relations);
5099 VEC_free (gimple, heap, stmts);
5103 /* Free the reduced dependence graph RDG. */
5106 free_rdg (struct graph *rdg)
5110 for (i = 0; i < rdg->n_vertices; i++)
5112 struct vertex *v = &(rdg->vertices[i]);
5113 struct graph_edge *e;
5115 for (e = v->succ; e; e = e->succ_next)
5121 htab_delete (rdg->indices);
5125 /* Initialize STMTS with all the statements of LOOP that contain a
5129 stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
5132 basic_block *bbs = get_loop_body_in_dom_order (loop);
5134 for (i = 0; i < loop->num_nodes; i++)
5136 basic_block bb = bbs[i];
5137 gimple_stmt_iterator bsi;
5139 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
5140 if (gimple_vdef (gsi_stmt (bsi)))
5141 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
5147 /* Returns true when the statement at STMT is of the form "A[i] = 0"
5148 that contains a data reference on its LHS with a stride of the same
5149 size as its unit type. */
5152 stmt_with_adjacent_zero_store_dr_p (gimple stmt)
5156 struct data_reference *dr;
5159 || !gimple_vdef (stmt)
5160 || !is_gimple_assign (stmt)
5161 || !gimple_assign_single_p (stmt)
5162 || !(op1 = gimple_assign_rhs1 (stmt))
5163 || !(integer_zerop (op1) || real_zerop (op1)))
5166 dr = XCNEW (struct data_reference);
5167 op0 = gimple_assign_lhs (stmt);
5169 DR_STMT (dr) = stmt;
5172 res = dr_analyze_innermost (dr, loop_containing_stmt (stmt))
5173 && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0));
5179 /* Initialize STMTS with all the statements of LOOP that contain a
5180 store to memory of the form "A[i] = 0". */
5183 stores_zero_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
5187 gimple_stmt_iterator si;
5189 basic_block *bbs = get_loop_body_in_dom_order (loop);
5191 for (i = 0; i < loop->num_nodes; i++)
5192 for (bb = bbs[i], si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5193 if ((stmt = gsi_stmt (si))
5194 && stmt_with_adjacent_zero_store_dr_p (stmt))
5195 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (si));
5200 /* For a data reference REF, return the declaration of its base
5201 address or NULL_TREE if the base is not determined. */
5204 ref_base_address (gimple stmt, data_ref_loc *ref)
5206 tree base = NULL_TREE;
5208 struct data_reference *dr = XCNEW (struct data_reference);
5210 DR_STMT (dr) = stmt;
5211 DR_REF (dr) = *ref->pos;
5212 dr_analyze_innermost (dr, loop_containing_stmt (stmt));
5213 base_address = DR_BASE_ADDRESS (dr);
5218 switch (TREE_CODE (base_address))
5221 base = TREE_OPERAND (base_address, 0);
5225 base = base_address;
5234 /* Determines whether the statement from vertex V of the RDG has a
5235 definition used outside the loop that contains this statement. */
5238 rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
5240 gimple stmt = RDG_STMT (rdg, v);
5241 struct loop *loop = loop_containing_stmt (stmt);
5242 use_operand_p imm_use_p;
5243 imm_use_iterator iterator;
5245 def_operand_p def_p;
5250 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
5252 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
5254 if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
5262 /* Determines whether statements S1 and S2 access to similar memory
5263 locations. Two memory accesses are considered similar when they
5264 have the same base address declaration, i.e. when their
5265 ref_base_address is the same. */
5268 have_similar_memory_accesses (gimple s1, gimple s2)
5272 VEC (data_ref_loc, heap) *refs1, *refs2;
5273 data_ref_loc *ref1, *ref2;
5275 get_references_in_stmt (s1, &refs1);
5276 get_references_in_stmt (s2, &refs2);
5278 FOR_EACH_VEC_ELT (data_ref_loc, refs1, i, ref1)
5280 tree base1 = ref_base_address (s1, ref1);
5283 FOR_EACH_VEC_ELT (data_ref_loc, refs2, j, ref2)
5284 if (base1 == ref_base_address (s2, ref2))
5292 VEC_free (data_ref_loc, heap, refs1);
5293 VEC_free (data_ref_loc, heap, refs2);
5297 /* Helper function for the hashtab. */
5300 have_similar_memory_accesses_1 (const void *s1, const void *s2)
5302 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1),
5303 CONST_CAST_GIMPLE ((const_gimple) s2));
5306 /* Helper function for the hashtab. */
5309 ref_base_address_1 (const void *s)
5311 gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s);
5313 VEC (data_ref_loc, heap) *refs;
5317 get_references_in_stmt (stmt, &refs);
5319 FOR_EACH_VEC_ELT (data_ref_loc, refs, i, ref)
5322 res = htab_hash_pointer (ref_base_address (stmt, ref));
5326 VEC_free (data_ref_loc, heap, refs);
5330 /* Try to remove duplicated write data references from STMTS. */
5333 remove_similar_memory_refs (VEC (gimple, heap) **stmts)
5337 htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1,
5338 have_similar_memory_accesses_1, NULL);
5340 for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); )
5344 slot = htab_find_slot (seen, stmt, INSERT);
5347 VEC_ordered_remove (gimple, *stmts, i);
5350 *slot = (void *) stmt;
5358 /* Returns the index of PARAMETER in the parameters vector of the
5359 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5362 access_matrix_get_index_for_parameter (tree parameter,
5363 struct access_matrix *access_matrix)
5366 VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
5367 tree lambda_parameter;
5369 FOR_EACH_VEC_ELT (tree, lambda_parameters, i, lambda_parameter)
5370 if (lambda_parameter == parameter)
5371 return i + AM_NB_INDUCTION_VARS (access_matrix);