1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass walks a given loop structure searching for array
22 references. The information about the array accesses is recorded
23 in DATA_REFERENCE structures.
25 The basic test for determining the dependences is:
26 given two access functions chrec1 and chrec2 to a same array, and
27 x and y two vectors from the iteration domain, the same element of
28 the array is accessed twice at iterations x and y if and only if:
29 | chrec1 (x) == chrec2 (y).
31 The goals of this analysis are:
33 - to determine the independence: the relation between two
34 independent accesses is qualified with the chrec_known (this
35 information allows a loop parallelization),
37 - when two data references access the same data, to qualify the
38 dependence relation with classic dependence representations:
42 - loop carried level dependence
43 - polyhedron dependence
44 or with the chains of recurrences based representation,
46 - to define a knowledge base for storing the data dependence
49 - to define an interface to access this data.
54 - subscript: given two array accesses a subscript is the tuple
55 composed of the access functions for a given dimension. Example:
56 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
57 (f1, g1), (f2, g2), (f3, g3).
59 - Diophantine equation: an equation whose coefficients and
60 solutions are integer constants, for example the equation
62 has an integer solution x = 1 and y = -1.
66 - "Advanced Compilation for High Performance Computing" by Randy
67 Allen and Ken Kennedy.
68 http://citeseer.ist.psu.edu/goff91practical.html
70 - "Loop Transformations for Restructuring Compilers - The Foundations"
78 #include "coretypes.h"
83 /* These RTL headers are needed for basic-block.h. */
85 #include "basic-block.h"
86 #include "diagnostic.h"
87 #include "tree-flow.h"
88 #include "tree-dump.h"
91 #include "tree-data-ref.h"
92 #include "tree-scalar-evolution.h"
93 #include "tree-pass.h"
94 #include "langhooks.h"
96 static struct datadep_stats
98 int num_dependence_tests;
99 int num_dependence_dependent;
100 int num_dependence_independent;
101 int num_dependence_undetermined;
103 int num_subscript_tests;
104 int num_subscript_undetermined;
105 int num_same_subscript_function;
108 int num_ziv_independent;
109 int num_ziv_dependent;
110 int num_ziv_unimplemented;
113 int num_siv_independent;
114 int num_siv_dependent;
115 int num_siv_unimplemented;
118 int num_miv_independent;
119 int num_miv_dependent;
120 int num_miv_unimplemented;
123 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
124 struct data_reference *,
125 struct data_reference *,
127 /* Returns true iff A divides B. */
130 tree_fold_divides_p (const_tree a, const_tree b)
132 gcc_assert (TREE_CODE (a) == INTEGER_CST);
133 gcc_assert (TREE_CODE (b) == INTEGER_CST);
134 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
137 /* Returns true iff A divides B. */
140 int_divides_p (int a, int b)
142 return ((b % a) == 0);
147 /* Dump into FILE all the data references from DATAREFS. */
150 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
153 struct data_reference *dr;
155 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
156 dump_data_reference (file, dr);
159 /* Dump to STDERR all the dependence relations from DDRS. */
162 debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs)
164 dump_data_dependence_relations (stderr, ddrs);
167 /* Dump into FILE all the dependence relations from DDRS. */
170 dump_data_dependence_relations (FILE *file,
171 VEC (ddr_p, heap) *ddrs)
174 struct data_dependence_relation *ddr;
176 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
177 dump_data_dependence_relation (file, ddr);
180 /* Dump function for a DATA_REFERENCE structure. */
183 dump_data_reference (FILE *outf,
184 struct data_reference *dr)
188 fprintf (outf, "(Data Ref: \n stmt: ");
189 print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
190 fprintf (outf, " ref: ");
191 print_generic_stmt (outf, DR_REF (dr), 0);
192 fprintf (outf, " base_object: ");
193 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
195 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
197 fprintf (outf, " Access function %d: ", i);
198 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
200 fprintf (outf, ")\n");
203 /* Dumps the affine function described by FN to the file OUTF. */
206 dump_affine_function (FILE *outf, affine_fn fn)
211 print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
212 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
214 fprintf (outf, " + ");
215 print_generic_expr (outf, coef, TDF_SLIM);
216 fprintf (outf, " * x_%u", i);
220 /* Dumps the conflict function CF to the file OUTF. */
223 dump_conflict_function (FILE *outf, conflict_function *cf)
227 if (cf->n == NO_DEPENDENCE)
228 fprintf (outf, "no dependence\n");
229 else if (cf->n == NOT_KNOWN)
230 fprintf (outf, "not known\n");
233 for (i = 0; i < cf->n; i++)
236 dump_affine_function (outf, cf->fns[i]);
237 fprintf (outf, "]\n");
242 /* Dump function for a SUBSCRIPT structure. */
245 dump_subscript (FILE *outf, struct subscript *subscript)
247 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
249 fprintf (outf, "\n (subscript \n");
250 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
251 dump_conflict_function (outf, cf);
252 if (CF_NONTRIVIAL_P (cf))
254 tree last_iteration = SUB_LAST_CONFLICT (subscript);
255 fprintf (outf, " last_conflict: ");
256 print_generic_stmt (outf, last_iteration, 0);
259 cf = SUB_CONFLICTS_IN_B (subscript);
260 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
261 dump_conflict_function (outf, cf);
262 if (CF_NONTRIVIAL_P (cf))
264 tree last_iteration = SUB_LAST_CONFLICT (subscript);
265 fprintf (outf, " last_conflict: ");
266 print_generic_stmt (outf, last_iteration, 0);
269 fprintf (outf, " (Subscript distance: ");
270 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
271 fprintf (outf, " )\n");
272 fprintf (outf, " )\n");
275 /* Print the classic direction vector DIRV to OUTF. */
278 print_direction_vector (FILE *outf,
284 for (eq = 0; eq < length; eq++)
286 enum data_dependence_direction dir = dirv[eq];
291 fprintf (outf, " +");
294 fprintf (outf, " -");
297 fprintf (outf, " =");
299 case dir_positive_or_equal:
300 fprintf (outf, " +=");
302 case dir_positive_or_negative:
303 fprintf (outf, " +-");
305 case dir_negative_or_equal:
306 fprintf (outf, " -=");
309 fprintf (outf, " *");
312 fprintf (outf, "indep");
316 fprintf (outf, "\n");
319 /* Print a vector of direction vectors. */
322 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
328 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
329 print_direction_vector (outf, v, length);
332 /* Print a vector of distance vectors. */
335 print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
341 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
342 print_lambda_vector (outf, v, length);
348 debug_data_dependence_relation (struct data_dependence_relation *ddr)
350 dump_data_dependence_relation (stderr, ddr);
353 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
356 dump_data_dependence_relation (FILE *outf,
357 struct data_dependence_relation *ddr)
359 struct data_reference *dra, *drb;
361 fprintf (outf, "(Data Dep: \n");
363 if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
365 fprintf (outf, " (don't know)\n)\n");
371 dump_data_reference (outf, dra);
372 dump_data_reference (outf, drb);
374 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
375 fprintf (outf, " (no dependence)\n");
377 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
382 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
384 fprintf (outf, " access_fn_A: ");
385 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
386 fprintf (outf, " access_fn_B: ");
387 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
388 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
391 fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
392 fprintf (outf, " loop nest: (");
393 for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
394 fprintf (outf, "%d ", loopi->num);
395 fprintf (outf, ")\n");
397 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
399 fprintf (outf, " distance_vector: ");
400 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
404 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
406 fprintf (outf, " direction_vector: ");
407 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
412 fprintf (outf, ")\n");
415 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
418 dump_data_dependence_direction (FILE *file,
419 enum data_dependence_direction dir)
435 case dir_positive_or_negative:
436 fprintf (file, "+-");
439 case dir_positive_or_equal:
440 fprintf (file, "+=");
443 case dir_negative_or_equal:
444 fprintf (file, "-=");
456 /* Dumps the distance and direction vectors in FILE. DDRS contains
457 the dependence relations, and VECT_SIZE is the size of the
458 dependence vectors, or in other words the number of loops in the
462 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
465 struct data_dependence_relation *ddr;
468 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
469 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
471 for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
473 fprintf (file, "DISTANCE_V (");
474 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
475 fprintf (file, ")\n");
478 for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
480 fprintf (file, "DIRECTION_V (");
481 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
482 fprintf (file, ")\n");
486 fprintf (file, "\n\n");
489 /* Dumps the data dependence relations DDRS in FILE. */
492 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
495 struct data_dependence_relation *ddr;
497 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
498 dump_data_dependence_relation (file, ddr);
500 fprintf (file, "\n\n");
503 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
504 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
505 constant of type ssizetype, and returns true. If we cannot do this
506 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
510 split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
511 tree *var, tree *off)
515 enum tree_code ocode = code;
523 *var = build_int_cst (type, 0);
524 *off = fold_convert (ssizetype, op0);
527 case POINTER_PLUS_EXPR:
532 split_constant_offset (op0, &var0, &off0);
533 split_constant_offset (op1, &var1, &off1);
534 *var = fold_build2 (code, type, var0, var1);
535 *off = size_binop (ocode, off0, off1);
539 if (TREE_CODE (op1) != INTEGER_CST)
542 split_constant_offset (op0, &var0, &off0);
543 *var = fold_build2 (MULT_EXPR, type, var0, op1);
544 *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
550 HOST_WIDE_INT pbitsize, pbitpos;
551 enum machine_mode pmode;
552 int punsignedp, pvolatilep;
554 if (!handled_component_p (op0))
557 base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
558 &pmode, &punsignedp, &pvolatilep, false);
560 if (pbitpos % BITS_PER_UNIT != 0)
562 base = build_fold_addr_expr (base);
563 off0 = ssize_int (pbitpos / BITS_PER_UNIT);
567 split_constant_offset (poffset, &poffset, &off1);
568 off0 = size_binop (PLUS_EXPR, off0, off1);
569 if (POINTER_TYPE_P (TREE_TYPE (base)))
570 base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base),
571 base, fold_convert (sizetype, poffset));
573 base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
574 fold_convert (TREE_TYPE (base), poffset));
577 var0 = fold_convert (type, base);
579 /* If variable length types are involved, punt, otherwise casts
580 might be converted into ARRAY_REFs in gimplify_conversion.
581 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
582 possibly no longer appears in current GIMPLE, might resurface.
583 This perhaps could run
584 if (CONVERT_EXPR_P (var0))
586 gimplify_conversion (&var0);
587 // Attempt to fill in any within var0 found ARRAY_REF's
588 // element size from corresponding op embedded ARRAY_REF,
589 // if unsuccessful, just punt.
591 while (POINTER_TYPE_P (type))
592 type = TREE_TYPE (type);
593 if (int_size_in_bytes (type) < 0)
603 gimple def_stmt = SSA_NAME_DEF_STMT (op0);
604 enum tree_code subcode;
606 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
609 var0 = gimple_assign_rhs1 (def_stmt);
610 subcode = gimple_assign_rhs_code (def_stmt);
611 var1 = gimple_assign_rhs2 (def_stmt);
613 return split_constant_offset_1 (type, var0, subcode, var1, var, off);
621 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
622 will be ssizetype. */
625 split_constant_offset (tree exp, tree *var, tree *off)
627 tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
631 *off = ssize_int (0);
634 if (automatically_generated_chrec_p (exp))
637 otype = TREE_TYPE (exp);
638 code = TREE_CODE (exp);
639 extract_ops_from_tree (exp, &code, &op0, &op1);
640 if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
642 *var = fold_convert (type, e);
647 /* Returns the address ADDR of an object in a canonical shape (without nop
648 casts, and with type of pointer to the object). */
651 canonicalize_base_object_address (tree addr)
657 /* The base address may be obtained by casting from integer, in that case
659 if (!POINTER_TYPE_P (TREE_TYPE (addr)))
662 if (TREE_CODE (addr) != ADDR_EXPR)
665 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
668 /* Analyzes the behavior of the memory reference DR in the innermost loop that
672 dr_analyze_innermost (struct data_reference *dr)
674 gimple stmt = DR_STMT (dr);
675 struct loop *loop = loop_containing_stmt (stmt);
676 tree ref = DR_REF (dr);
677 HOST_WIDE_INT pbitsize, pbitpos;
679 enum machine_mode pmode;
680 int punsignedp, pvolatilep;
681 affine_iv base_iv, offset_iv;
682 tree init, dinit, step;
684 if (dump_file && (dump_flags & TDF_DETAILS))
685 fprintf (dump_file, "analyze_innermost: ");
687 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
688 &pmode, &punsignedp, &pvolatilep, false);
689 gcc_assert (base != NULL_TREE);
691 if (pbitpos % BITS_PER_UNIT != 0)
693 if (dump_file && (dump_flags & TDF_DETAILS))
694 fprintf (dump_file, "failed: bit offset alignment.\n");
698 base = build_fold_addr_expr (base);
699 if (!simple_iv (loop, stmt, base, &base_iv, false))
701 if (dump_file && (dump_flags & TDF_DETAILS))
702 fprintf (dump_file, "failed: evolution of base is not affine.\n");
707 offset_iv.base = ssize_int (0);
708 offset_iv.step = ssize_int (0);
710 else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
712 if (dump_file && (dump_flags & TDF_DETAILS))
713 fprintf (dump_file, "failed: evolution of offset is not affine.\n");
717 init = ssize_int (pbitpos / BITS_PER_UNIT);
718 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
719 init = size_binop (PLUS_EXPR, init, dinit);
720 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
721 init = size_binop (PLUS_EXPR, init, dinit);
723 step = size_binop (PLUS_EXPR,
724 fold_convert (ssizetype, base_iv.step),
725 fold_convert (ssizetype, offset_iv.step));
727 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
729 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
733 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
735 if (dump_file && (dump_flags & TDF_DETAILS))
736 fprintf (dump_file, "success.\n");
739 /* Determines the base object and the list of indices of memory reference
740 DR, analyzed in loop nest NEST. */
743 dr_analyze_indices (struct data_reference *dr, struct loop *nest)
745 gimple stmt = DR_STMT (dr);
746 struct loop *loop = loop_containing_stmt (stmt);
747 VEC (tree, heap) *access_fns = NULL;
748 tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
749 tree base, off, access_fn;
750 basic_block before_loop = block_before_loop (nest);
752 while (handled_component_p (aref))
754 if (TREE_CODE (aref) == ARRAY_REF)
756 op = TREE_OPERAND (aref, 1);
757 access_fn = analyze_scalar_evolution (loop, op);
758 access_fn = instantiate_scev (before_loop, loop, access_fn);
759 VEC_safe_push (tree, heap, access_fns, access_fn);
761 TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
764 aref = TREE_OPERAND (aref, 0);
767 if (INDIRECT_REF_P (aref))
769 op = TREE_OPERAND (aref, 0);
770 access_fn = analyze_scalar_evolution (loop, op);
771 access_fn = instantiate_scev (before_loop, loop, access_fn);
772 base = initial_condition (access_fn);
773 split_constant_offset (base, &base, &off);
774 access_fn = chrec_replace_initial_condition (access_fn,
775 fold_convert (TREE_TYPE (base), off));
777 TREE_OPERAND (aref, 0) = base;
778 VEC_safe_push (tree, heap, access_fns, access_fn);
781 DR_BASE_OBJECT (dr) = ref;
782 DR_ACCESS_FNS (dr) = access_fns;
785 /* Extracts the alias analysis information from the memory reference DR. */
788 dr_analyze_alias (struct data_reference *dr)
790 gimple stmt = DR_STMT (dr);
791 tree ref = DR_REF (dr);
792 tree base = get_base_address (ref), addr, smt = NULL_TREE;
799 else if (INDIRECT_REF_P (base))
801 addr = TREE_OPERAND (base, 0);
802 if (TREE_CODE (addr) == SSA_NAME)
804 smt = symbol_mem_tag (SSA_NAME_VAR (addr));
805 DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
809 DR_SYMBOL_TAG (dr) = smt;
811 vops = BITMAP_ALLOC (NULL);
812 FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES)
814 bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op)));
820 /* Returns true if the address of DR is invariant. */
823 dr_address_invariant_p (struct data_reference *dr)
828 for (i = 0; VEC_iterate (tree, DR_ACCESS_FNS (dr), i, idx); i++)
829 if (tree_contains_chrecs (idx, NULL))
835 /* Frees data reference DR. */
838 free_data_ref (data_reference_p dr)
840 BITMAP_FREE (DR_VOPS (dr));
841 VEC_free (tree, heap, DR_ACCESS_FNS (dr));
845 /* Analyzes memory reference MEMREF accessed in STMT. The reference
846 is read if IS_READ is true, write otherwise. Returns the
847 data_reference description of MEMREF. NEST is the outermost loop of the
848 loop nest in that the reference should be analyzed. */
850 struct data_reference *
851 create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read)
853 struct data_reference *dr;
855 if (dump_file && (dump_flags & TDF_DETAILS))
857 fprintf (dump_file, "Creating dr for ");
858 print_generic_expr (dump_file, memref, TDF_SLIM);
859 fprintf (dump_file, "\n");
862 dr = XCNEW (struct data_reference);
864 DR_REF (dr) = memref;
865 DR_IS_READ (dr) = is_read;
867 dr_analyze_innermost (dr);
868 dr_analyze_indices (dr, nest);
869 dr_analyze_alias (dr);
871 if (dump_file && (dump_flags & TDF_DETAILS))
873 fprintf (dump_file, "\tbase_address: ");
874 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
875 fprintf (dump_file, "\n\toffset from base address: ");
876 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
877 fprintf (dump_file, "\n\tconstant offset from base address: ");
878 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
879 fprintf (dump_file, "\n\tstep: ");
880 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
881 fprintf (dump_file, "\n\taligned to: ");
882 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
883 fprintf (dump_file, "\n\tbase_object: ");
884 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
885 fprintf (dump_file, "\n\tsymbol tag: ");
886 print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM);
887 fprintf (dump_file, "\n");
893 /* Returns true if FNA == FNB. */
896 affine_function_equal_p (affine_fn fna, affine_fn fnb)
898 unsigned i, n = VEC_length (tree, fna);
900 if (n != VEC_length (tree, fnb))
903 for (i = 0; i < n; i++)
904 if (!operand_equal_p (VEC_index (tree, fna, i),
905 VEC_index (tree, fnb, i), 0))
911 /* If all the functions in CF are the same, returns one of them,
912 otherwise returns NULL. */
915 common_affine_function (conflict_function *cf)
920 if (!CF_NONTRIVIAL_P (cf))
925 for (i = 1; i < cf->n; i++)
926 if (!affine_function_equal_p (comm, cf->fns[i]))
932 /* Returns the base of the affine function FN. */
935 affine_function_base (affine_fn fn)
937 return VEC_index (tree, fn, 0);
940 /* Returns true if FN is a constant. */
943 affine_function_constant_p (affine_fn fn)
948 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
949 if (!integer_zerop (coef))
955 /* Returns true if FN is the zero constant function. */
958 affine_function_zero_p (affine_fn fn)
960 return (integer_zerop (affine_function_base (fn))
961 && affine_function_constant_p (fn));
964 /* Returns a signed integer type with the largest precision from TA
968 signed_type_for_types (tree ta, tree tb)
970 if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
971 return signed_type_for (ta);
973 return signed_type_for (tb);
976 /* Applies operation OP on affine functions FNA and FNB, and returns the
980 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
986 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
988 n = VEC_length (tree, fna);
989 m = VEC_length (tree, fnb);
993 n = VEC_length (tree, fnb);
994 m = VEC_length (tree, fna);
997 ret = VEC_alloc (tree, heap, m);
998 for (i = 0; i < n; i++)
1000 tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)),
1001 TREE_TYPE (VEC_index (tree, fnb, i)));
1003 VEC_quick_push (tree, ret,
1004 fold_build2 (op, type,
1005 VEC_index (tree, fna, i),
1006 VEC_index (tree, fnb, i)));
1009 for (; VEC_iterate (tree, fna, i, coef); i++)
1010 VEC_quick_push (tree, ret,
1011 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1012 coef, integer_zero_node));
1013 for (; VEC_iterate (tree, fnb, i, coef); i++)
1014 VEC_quick_push (tree, ret,
1015 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1016 integer_zero_node, coef));
1021 /* Returns the sum of affine functions FNA and FNB. */
1024 affine_fn_plus (affine_fn fna, affine_fn fnb)
1026 return affine_fn_op (PLUS_EXPR, fna, fnb);
1029 /* Returns the difference of affine functions FNA and FNB. */
1032 affine_fn_minus (affine_fn fna, affine_fn fnb)
1034 return affine_fn_op (MINUS_EXPR, fna, fnb);
1037 /* Frees affine function FN. */
1040 affine_fn_free (affine_fn fn)
1042 VEC_free (tree, heap, fn);
1045 /* Determine for each subscript in the data dependence relation DDR
1049 compute_subscript_distance (struct data_dependence_relation *ddr)
1051 conflict_function *cf_a, *cf_b;
1052 affine_fn fn_a, fn_b, diff;
1054 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1058 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1060 struct subscript *subscript;
1062 subscript = DDR_SUBSCRIPT (ddr, i);
1063 cf_a = SUB_CONFLICTS_IN_A (subscript);
1064 cf_b = SUB_CONFLICTS_IN_B (subscript);
1066 fn_a = common_affine_function (cf_a);
1067 fn_b = common_affine_function (cf_b);
1070 SUB_DISTANCE (subscript) = chrec_dont_know;
1073 diff = affine_fn_minus (fn_a, fn_b);
1075 if (affine_function_constant_p (diff))
1076 SUB_DISTANCE (subscript) = affine_function_base (diff);
1078 SUB_DISTANCE (subscript) = chrec_dont_know;
1080 affine_fn_free (diff);
1085 /* Returns the conflict function for "unknown". */
1087 static conflict_function *
1088 conflict_fn_not_known (void)
1090 conflict_function *fn = XCNEW (conflict_function);
1096 /* Returns the conflict function for "independent". */
1098 static conflict_function *
1099 conflict_fn_no_dependence (void)
1101 conflict_function *fn = XCNEW (conflict_function);
1102 fn->n = NO_DEPENDENCE;
1107 /* Returns true if the address of OBJ is invariant in LOOP. */
1110 object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
1112 while (handled_component_p (obj))
1114 if (TREE_CODE (obj) == ARRAY_REF)
1116 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1117 need to check the stride and the lower bound of the reference. */
1118 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1120 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1124 else if (TREE_CODE (obj) == COMPONENT_REF)
1126 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1130 obj = TREE_OPERAND (obj, 0);
1133 if (!INDIRECT_REF_P (obj))
1136 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1140 /* Returns true if A and B are accesses to different objects, or to different
1141 fields of the same object. */
1144 disjoint_objects_p (tree a, tree b)
1146 tree base_a, base_b;
1147 VEC (tree, heap) *comp_a = NULL, *comp_b = NULL;
1150 base_a = get_base_address (a);
1151 base_b = get_base_address (b);
1155 && base_a != base_b)
1158 if (!operand_equal_p (base_a, base_b, 0))
1161 /* Compare the component references of A and B. We must start from the inner
1162 ones, so record them to the vector first. */
1163 while (handled_component_p (a))
1165 VEC_safe_push (tree, heap, comp_a, a);
1166 a = TREE_OPERAND (a, 0);
1168 while (handled_component_p (b))
1170 VEC_safe_push (tree, heap, comp_b, b);
1171 b = TREE_OPERAND (b, 0);
1177 if (VEC_length (tree, comp_a) == 0
1178 || VEC_length (tree, comp_b) == 0)
1181 a = VEC_pop (tree, comp_a);
1182 b = VEC_pop (tree, comp_b);
1184 /* Real and imaginary part of a variable do not alias. */
1185 if ((TREE_CODE (a) == REALPART_EXPR
1186 && TREE_CODE (b) == IMAGPART_EXPR)
1187 || (TREE_CODE (a) == IMAGPART_EXPR
1188 && TREE_CODE (b) == REALPART_EXPR))
1194 if (TREE_CODE (a) != TREE_CODE (b))
1197 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1198 DR_BASE_OBJECT are always zero. */
1199 if (TREE_CODE (a) == ARRAY_REF)
1201 else if (TREE_CODE (a) == COMPONENT_REF)
1203 if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0))
1206 /* Different fields of unions may overlap. */
1207 base_a = TREE_OPERAND (a, 0);
1208 if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE)
1211 /* Different fields of structures cannot. */
1219 VEC_free (tree, heap, comp_a);
1220 VEC_free (tree, heap, comp_b);
1225 /* Returns false if we can prove that data references A and B do not alias,
1229 dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
1231 const_tree addr_a = DR_BASE_ADDRESS (a);
1232 const_tree addr_b = DR_BASE_ADDRESS (b);
1233 const_tree type_a, type_b;
1234 const_tree decl_a = NULL_TREE, decl_b = NULL_TREE;
1236 /* If the sets of virtual operands are disjoint, the memory references do not
1238 if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
1241 /* If the accessed objects are disjoint, the memory references do not
1243 if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b)))
1246 if (!addr_a || !addr_b)
1249 /* If the references are based on different static objects, they cannot alias
1250 (PTA should be able to disambiguate such accesses, but often it fails to,
1251 since currently we cannot distinguish between pointer and offset in pointer
1253 if (TREE_CODE (addr_a) == ADDR_EXPR
1254 && TREE_CODE (addr_b) == ADDR_EXPR)
1255 return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0);
1257 /* An instruction writing through a restricted pointer is "independent" of any
1258 instruction reading or writing through a different restricted pointer,
1259 in the same block/scope. */
1261 type_a = TREE_TYPE (addr_a);
1262 type_b = TREE_TYPE (addr_b);
1263 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
1265 if (TREE_CODE (addr_a) == SSA_NAME)
1266 decl_a = SSA_NAME_VAR (addr_a);
1267 if (TREE_CODE (addr_b) == SSA_NAME)
1268 decl_b = SSA_NAME_VAR (addr_b);
1270 if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b)
1271 && (!DR_IS_READ (a) || !DR_IS_READ (b))
1272 && decl_a && DECL_P (decl_a)
1273 && decl_b && DECL_P (decl_b)
1275 && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
1276 && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
1282 static void compute_self_dependence (struct data_dependence_relation *);
1284 /* Initialize a data dependence relation between data accesses A and
1285 B. NB_LOOPS is the number of loops surrounding the references: the
1286 size of the classic distance/direction vectors. */
1288 static struct data_dependence_relation *
1289 initialize_data_dependence_relation (struct data_reference *a,
1290 struct data_reference *b,
1291 VEC (loop_p, heap) *loop_nest)
1293 struct data_dependence_relation *res;
1296 res = XNEW (struct data_dependence_relation);
1299 DDR_LOOP_NEST (res) = NULL;
1300 DDR_REVERSED_P (res) = false;
1301 DDR_SUBSCRIPTS (res) = NULL;
1302 DDR_DIR_VECTS (res) = NULL;
1303 DDR_DIST_VECTS (res) = NULL;
1305 if (a == NULL || b == NULL)
1307 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1311 /* If the data references do not alias, then they are independent. */
1312 if (!dr_may_alias_p (a, b))
1314 DDR_ARE_DEPENDENT (res) = chrec_known;
1318 /* When the references are exactly the same, don't spend time doing
1319 the data dependence tests, just initialize the ddr and return. */
1320 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
1322 DDR_AFFINE_P (res) = true;
1323 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1324 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1325 DDR_LOOP_NEST (res) = loop_nest;
1326 DDR_INNER_LOOP (res) = 0;
1327 DDR_SELF_REFERENCE (res) = true;
1328 compute_self_dependence (res);
1332 /* If the references do not access the same object, we do not know
1333 whether they alias or not. */
1334 if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1336 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1340 /* If the base of the object is not invariant in the loop nest, we cannot
1341 analyze it. TODO -- in fact, it would suffice to record that there may
1342 be arbitrary dependences in the loops where the base object varies. */
1343 if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1344 DR_BASE_OBJECT (a)))
1346 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1350 gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b));
1352 DDR_AFFINE_P (res) = true;
1353 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1354 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1355 DDR_LOOP_NEST (res) = loop_nest;
1356 DDR_INNER_LOOP (res) = 0;
1357 DDR_SELF_REFERENCE (res) = false;
1359 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1361 struct subscript *subscript;
1363 subscript = XNEW (struct subscript);
1364 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1365 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1366 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1367 SUB_DISTANCE (subscript) = chrec_dont_know;
1368 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1374 /* Frees memory used by the conflict function F. */
1377 free_conflict_function (conflict_function *f)
1381 if (CF_NONTRIVIAL_P (f))
1383 for (i = 0; i < f->n; i++)
1384 affine_fn_free (f->fns[i]);
1389 /* Frees memory used by SUBSCRIPTS. */
1392 free_subscripts (VEC (subscript_p, heap) *subscripts)
1397 for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
1399 free_conflict_function (s->conflicting_iterations_in_a);
1400 free_conflict_function (s->conflicting_iterations_in_b);
1402 VEC_free (subscript_p, heap, subscripts);
1405 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1409 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1412 if (dump_file && (dump_flags & TDF_DETAILS))
1414 fprintf (dump_file, "(dependence classified: ");
1415 print_generic_expr (dump_file, chrec, 0);
1416 fprintf (dump_file, ")\n");
1419 DDR_ARE_DEPENDENT (ddr) = chrec;
1420 free_subscripts (DDR_SUBSCRIPTS (ddr));
1421 DDR_SUBSCRIPTS (ddr) = NULL;
1424 /* The dependence relation DDR cannot be represented by a distance
1428 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1430 if (dump_file && (dump_flags & TDF_DETAILS))
1431 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1433 DDR_AFFINE_P (ddr) = false;
1438 /* This section contains the classic Banerjee tests. */
1440 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1441 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1444 ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1446 return (evolution_function_is_constant_p (chrec_a)
1447 && evolution_function_is_constant_p (chrec_b));
1450 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1451 variable, i.e., if the SIV (Single Index Variable) test is true. */
1454 siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1456 if ((evolution_function_is_constant_p (chrec_a)
1457 && evolution_function_is_univariate_p (chrec_b))
1458 || (evolution_function_is_constant_p (chrec_b)
1459 && evolution_function_is_univariate_p (chrec_a)))
1462 if (evolution_function_is_univariate_p (chrec_a)
1463 && evolution_function_is_univariate_p (chrec_b))
1465 switch (TREE_CODE (chrec_a))
1467 case POLYNOMIAL_CHREC:
1468 switch (TREE_CODE (chrec_b))
1470 case POLYNOMIAL_CHREC:
1471 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1486 /* Creates a conflict function with N dimensions. The affine functions
1487 in each dimension follow. */
1489 static conflict_function *
1490 conflict_fn (unsigned n, ...)
1493 conflict_function *ret = XCNEW (conflict_function);
1496 gcc_assert (0 < n && n <= MAX_DIM);
1500 for (i = 0; i < n; i++)
1501 ret->fns[i] = va_arg (ap, affine_fn);
1507 /* Returns constant affine function with value CST. */
1510 affine_fn_cst (tree cst)
1512 affine_fn fn = VEC_alloc (tree, heap, 1);
1513 VEC_quick_push (tree, fn, cst);
1517 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1520 affine_fn_univar (tree cst, unsigned dim, tree coef)
1522 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
1525 gcc_assert (dim > 0);
1526 VEC_quick_push (tree, fn, cst);
1527 for (i = 1; i < dim; i++)
1528 VEC_quick_push (tree, fn, integer_zero_node);
1529 VEC_quick_push (tree, fn, coef);
1533 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1534 *OVERLAPS_B are initialized to the functions that describe the
1535 relation between the elements accessed twice by CHREC_A and
1536 CHREC_B. For k >= 0, the following property is verified:
1538 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1541 analyze_ziv_subscript (tree chrec_a,
1543 conflict_function **overlaps_a,
1544 conflict_function **overlaps_b,
1545 tree *last_conflicts)
1547 tree type, difference;
1548 dependence_stats.num_ziv++;
1550 if (dump_file && (dump_flags & TDF_DETAILS))
1551 fprintf (dump_file, "(analyze_ziv_subscript \n");
1553 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1554 chrec_a = chrec_convert (type, chrec_a, NULL);
1555 chrec_b = chrec_convert (type, chrec_b, NULL);
1556 difference = chrec_fold_minus (type, chrec_a, chrec_b);
1558 switch (TREE_CODE (difference))
1561 if (integer_zerop (difference))
1563 /* The difference is equal to zero: the accessed index
1564 overlaps for each iteration in the loop. */
1565 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1566 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1567 *last_conflicts = chrec_dont_know;
1568 dependence_stats.num_ziv_dependent++;
1572 /* The accesses do not overlap. */
1573 *overlaps_a = conflict_fn_no_dependence ();
1574 *overlaps_b = conflict_fn_no_dependence ();
1575 *last_conflicts = integer_zero_node;
1576 dependence_stats.num_ziv_independent++;
1581 /* We're not sure whether the indexes overlap. For the moment,
1582 conservatively answer "don't know". */
1583 if (dump_file && (dump_flags & TDF_DETAILS))
1584 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1586 *overlaps_a = conflict_fn_not_known ();
1587 *overlaps_b = conflict_fn_not_known ();
1588 *last_conflicts = chrec_dont_know;
1589 dependence_stats.num_ziv_unimplemented++;
1593 if (dump_file && (dump_flags & TDF_DETAILS))
1594 fprintf (dump_file, ")\n");
1597 /* Sets NIT to the estimated number of executions of the statements in
1598 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1599 large as the number of iterations. If we have no reliable estimate,
1600 the function returns false, otherwise returns true. */
1603 estimated_loop_iterations (struct loop *loop, bool conservative,
1606 estimate_numbers_of_iterations_loop (loop);
1609 if (!loop->any_upper_bound)
1612 *nit = loop->nb_iterations_upper_bound;
1616 if (!loop->any_estimate)
1619 *nit = loop->nb_iterations_estimate;
1625 /* Similar to estimated_loop_iterations, but returns the estimate only
1626 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1627 on the number of iterations of LOOP could not be derived, returns -1. */
1630 estimated_loop_iterations_int (struct loop *loop, bool conservative)
1633 HOST_WIDE_INT hwi_nit;
1635 if (!estimated_loop_iterations (loop, conservative, &nit))
1638 if (!double_int_fits_in_shwi_p (nit))
1640 hwi_nit = double_int_to_shwi (nit);
1642 return hwi_nit < 0 ? -1 : hwi_nit;
1645 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1646 and only if it fits to the int type. If this is not the case, or the
1647 estimate on the number of iterations of LOOP could not be derived, returns
1651 estimated_loop_iterations_tree (struct loop *loop, bool conservative)
1656 if (!estimated_loop_iterations (loop, conservative, &nit))
1657 return chrec_dont_know;
1659 type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
1660 if (!double_int_fits_to_tree_p (type, nit))
1661 return chrec_dont_know;
1663 return double_int_to_tree (type, nit);
1666 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1667 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1668 *OVERLAPS_B are initialized to the functions that describe the
1669 relation between the elements accessed twice by CHREC_A and
1670 CHREC_B. For k >= 0, the following property is verified:
1672 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1675 analyze_siv_subscript_cst_affine (tree chrec_a,
1677 conflict_function **overlaps_a,
1678 conflict_function **overlaps_b,
1679 tree *last_conflicts)
1681 bool value0, value1, value2;
1682 tree type, difference, tmp;
1684 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1685 chrec_a = chrec_convert (type, chrec_a, NULL);
1686 chrec_b = chrec_convert (type, chrec_b, NULL);
1687 difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
1689 if (!chrec_is_positive (initial_condition (difference), &value0))
1691 if (dump_file && (dump_flags & TDF_DETAILS))
1692 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1694 dependence_stats.num_siv_unimplemented++;
1695 *overlaps_a = conflict_fn_not_known ();
1696 *overlaps_b = conflict_fn_not_known ();
1697 *last_conflicts = chrec_dont_know;
1702 if (value0 == false)
1704 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1706 if (dump_file && (dump_flags & TDF_DETAILS))
1707 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1709 *overlaps_a = conflict_fn_not_known ();
1710 *overlaps_b = conflict_fn_not_known ();
1711 *last_conflicts = chrec_dont_know;
1712 dependence_stats.num_siv_unimplemented++;
1721 chrec_b = {10, +, 1}
1724 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1726 HOST_WIDE_INT numiter;
1727 struct loop *loop = get_chrec_loop (chrec_b);
1729 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1730 tmp = fold_build2 (EXACT_DIV_EXPR, type,
1731 fold_build1 (ABS_EXPR, type, difference),
1732 CHREC_RIGHT (chrec_b));
1733 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1734 *last_conflicts = integer_one_node;
1737 /* Perform weak-zero siv test to see if overlap is
1738 outside the loop bounds. */
1739 numiter = estimated_loop_iterations_int (loop, false);
1742 && compare_tree_int (tmp, numiter) > 0)
1744 free_conflict_function (*overlaps_a);
1745 free_conflict_function (*overlaps_b);
1746 *overlaps_a = conflict_fn_no_dependence ();
1747 *overlaps_b = conflict_fn_no_dependence ();
1748 *last_conflicts = integer_zero_node;
1749 dependence_stats.num_siv_independent++;
1752 dependence_stats.num_siv_dependent++;
1756 /* When the step does not divide the difference, there are
1760 *overlaps_a = conflict_fn_no_dependence ();
1761 *overlaps_b = conflict_fn_no_dependence ();
1762 *last_conflicts = integer_zero_node;
1763 dependence_stats.num_siv_independent++;
1772 chrec_b = {10, +, -1}
1774 In this case, chrec_a will not overlap with chrec_b. */
1775 *overlaps_a = conflict_fn_no_dependence ();
1776 *overlaps_b = conflict_fn_no_dependence ();
1777 *last_conflicts = integer_zero_node;
1778 dependence_stats.num_siv_independent++;
1785 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
1787 if (dump_file && (dump_flags & TDF_DETAILS))
1788 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1790 *overlaps_a = conflict_fn_not_known ();
1791 *overlaps_b = conflict_fn_not_known ();
1792 *last_conflicts = chrec_dont_know;
1793 dependence_stats.num_siv_unimplemented++;
1798 if (value2 == false)
1802 chrec_b = {10, +, -1}
1804 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1806 HOST_WIDE_INT numiter;
1807 struct loop *loop = get_chrec_loop (chrec_b);
1809 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1810 tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
1811 CHREC_RIGHT (chrec_b));
1812 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1813 *last_conflicts = integer_one_node;
1815 /* Perform weak-zero siv test to see if overlap is
1816 outside the loop bounds. */
1817 numiter = estimated_loop_iterations_int (loop, false);
1820 && compare_tree_int (tmp, numiter) > 0)
1822 free_conflict_function (*overlaps_a);
1823 free_conflict_function (*overlaps_b);
1824 *overlaps_a = conflict_fn_no_dependence ();
1825 *overlaps_b = conflict_fn_no_dependence ();
1826 *last_conflicts = integer_zero_node;
1827 dependence_stats.num_siv_independent++;
1830 dependence_stats.num_siv_dependent++;
1834 /* When the step does not divide the difference, there
1838 *overlaps_a = conflict_fn_no_dependence ();
1839 *overlaps_b = conflict_fn_no_dependence ();
1840 *last_conflicts = integer_zero_node;
1841 dependence_stats.num_siv_independent++;
1851 In this case, chrec_a will not overlap with chrec_b. */
1852 *overlaps_a = conflict_fn_no_dependence ();
1853 *overlaps_b = conflict_fn_no_dependence ();
1854 *last_conflicts = integer_zero_node;
1855 dependence_stats.num_siv_independent++;
1863 /* Helper recursive function for initializing the matrix A. Returns
1864 the initial value of CHREC. */
1867 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1871 switch (TREE_CODE (chrec))
1873 case POLYNOMIAL_CHREC:
1874 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
1876 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1877 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1883 tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
1884 tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
1886 return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
1891 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
1892 return chrec_convert (chrec_type (chrec), op, NULL);
1904 #define FLOOR_DIV(x,y) ((x) / (y))
1906 /* Solves the special case of the Diophantine equation:
1907 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1909 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1910 number of iterations that loops X and Y run. The overlaps will be
1911 constructed as evolutions in dimension DIM. */
1914 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1915 affine_fn *overlaps_a,
1916 affine_fn *overlaps_b,
1917 tree *last_conflicts, int dim)
1919 if (((step_a > 0 && step_b > 0)
1920 || (step_a < 0 && step_b < 0)))
1922 int step_overlaps_a, step_overlaps_b;
1923 int gcd_steps_a_b, last_conflict, tau2;
1925 gcd_steps_a_b = gcd (step_a, step_b);
1926 step_overlaps_a = step_b / gcd_steps_a_b;
1927 step_overlaps_b = step_a / gcd_steps_a_b;
1931 tau2 = FLOOR_DIV (niter, step_overlaps_a);
1932 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1933 last_conflict = tau2;
1934 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1937 *last_conflicts = chrec_dont_know;
1939 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
1940 build_int_cst (NULL_TREE,
1942 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
1943 build_int_cst (NULL_TREE,
1949 *overlaps_a = affine_fn_cst (integer_zero_node);
1950 *overlaps_b = affine_fn_cst (integer_zero_node);
1951 *last_conflicts = integer_zero_node;
1955 /* Solves the special case of a Diophantine equation where CHREC_A is
1956 an affine bivariate function, and CHREC_B is an affine univariate
1957 function. For example,
1959 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1961 has the following overlapping functions:
1963 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1964 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1965 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1967 FORNOW: This is a specialized implementation for a case occurring in
1968 a common benchmark. Implement the general algorithm. */
1971 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1972 conflict_function **overlaps_a,
1973 conflict_function **overlaps_b,
1974 tree *last_conflicts)
1976 bool xz_p, yz_p, xyz_p;
1977 int step_x, step_y, step_z;
1978 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
1979 affine_fn overlaps_a_xz, overlaps_b_xz;
1980 affine_fn overlaps_a_yz, overlaps_b_yz;
1981 affine_fn overlaps_a_xyz, overlaps_b_xyz;
1982 affine_fn ova1, ova2, ovb;
1983 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
1985 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1986 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1987 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1990 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)),
1992 niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false);
1993 niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false);
1995 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
1997 if (dump_file && (dump_flags & TDF_DETAILS))
1998 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2000 *overlaps_a = conflict_fn_not_known ();
2001 *overlaps_b = conflict_fn_not_known ();
2002 *last_conflicts = chrec_dont_know;
2006 niter = MIN (niter_x, niter_z);
2007 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2010 &last_conflicts_xz, 1);
2011 niter = MIN (niter_y, niter_z);
2012 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2015 &last_conflicts_yz, 2);
2016 niter = MIN (niter_x, niter_z);
2017 niter = MIN (niter_y, niter);
2018 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2021 &last_conflicts_xyz, 3);
2023 xz_p = !integer_zerop (last_conflicts_xz);
2024 yz_p = !integer_zerop (last_conflicts_yz);
2025 xyz_p = !integer_zerop (last_conflicts_xyz);
2027 if (xz_p || yz_p || xyz_p)
2029 ova1 = affine_fn_cst (integer_zero_node);
2030 ova2 = affine_fn_cst (integer_zero_node);
2031 ovb = affine_fn_cst (integer_zero_node);
2034 affine_fn t0 = ova1;
2037 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2038 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2039 affine_fn_free (t0);
2040 affine_fn_free (t2);
2041 *last_conflicts = last_conflicts_xz;
2045 affine_fn t0 = ova2;
2048 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2049 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2050 affine_fn_free (t0);
2051 affine_fn_free (t2);
2052 *last_conflicts = last_conflicts_yz;
2056 affine_fn t0 = ova1;
2057 affine_fn t2 = ova2;
2060 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2061 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2062 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2063 affine_fn_free (t0);
2064 affine_fn_free (t2);
2065 affine_fn_free (t4);
2066 *last_conflicts = last_conflicts_xyz;
2068 *overlaps_a = conflict_fn (2, ova1, ova2);
2069 *overlaps_b = conflict_fn (1, ovb);
2073 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2074 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2075 *last_conflicts = integer_zero_node;
2078 affine_fn_free (overlaps_a_xz);
2079 affine_fn_free (overlaps_b_xz);
2080 affine_fn_free (overlaps_a_yz);
2081 affine_fn_free (overlaps_b_yz);
2082 affine_fn_free (overlaps_a_xyz);
2083 affine_fn_free (overlaps_b_xyz);
2086 /* Determines the overlapping elements due to accesses CHREC_A and
2087 CHREC_B, that are affine functions. This function cannot handle
2088 symbolic evolution functions, ie. when initial conditions are
2089 parameters, because it uses lambda matrices of integers. */
2092 analyze_subscript_affine_affine (tree chrec_a,
2094 conflict_function **overlaps_a,
2095 conflict_function **overlaps_b,
2096 tree *last_conflicts)
2098 unsigned nb_vars_a, nb_vars_b, dim;
2099 HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
2100 lambda_matrix A, U, S;
2102 if (eq_evolutions_p (chrec_a, chrec_b))
2104 /* The accessed index overlaps for each iteration in the
2106 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2107 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2108 *last_conflicts = chrec_dont_know;
2111 if (dump_file && (dump_flags & TDF_DETAILS))
2112 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2114 /* For determining the initial intersection, we have to solve a
2115 Diophantine equation. This is the most time consuming part.
2117 For answering to the question: "Is there a dependence?" we have
2118 to prove that there exists a solution to the Diophantine
2119 equation, and that the solution is in the iteration domain,
2120 i.e. the solution is positive or zero, and that the solution
2121 happens before the upper bound loop.nb_iterations. Otherwise
2122 there is no dependence. This function outputs a description of
2123 the iterations that hold the intersections. */
2125 nb_vars_a = nb_vars_in_chrec (chrec_a);
2126 nb_vars_b = nb_vars_in_chrec (chrec_b);
2128 dim = nb_vars_a + nb_vars_b;
2129 U = lambda_matrix_new (dim, dim);
2130 A = lambda_matrix_new (dim, 1);
2131 S = lambda_matrix_new (dim, 1);
2133 init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
2134 init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
2135 gamma = init_b - init_a;
2137 /* Don't do all the hard work of solving the Diophantine equation
2138 when we already know the solution: for example,
2141 | gamma = 3 - 3 = 0.
2142 Then the first overlap occurs during the first iterations:
2143 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2147 if (nb_vars_a == 1 && nb_vars_b == 1)
2149 HOST_WIDE_INT step_a, step_b;
2150 HOST_WIDE_INT niter, niter_a, niter_b;
2153 niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
2155 niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
2157 niter = MIN (niter_a, niter_b);
2158 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2159 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2161 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2164 *overlaps_a = conflict_fn (1, ova);
2165 *overlaps_b = conflict_fn (1, ovb);
2168 else if (nb_vars_a == 2 && nb_vars_b == 1)
2169 compute_overlap_steps_for_affine_1_2
2170 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2172 else if (nb_vars_a == 1 && nb_vars_b == 2)
2173 compute_overlap_steps_for_affine_1_2
2174 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2178 if (dump_file && (dump_flags & TDF_DETAILS))
2179 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2180 *overlaps_a = conflict_fn_not_known ();
2181 *overlaps_b = conflict_fn_not_known ();
2182 *last_conflicts = chrec_dont_know;
2184 goto end_analyze_subs_aa;
2188 lambda_matrix_right_hermite (A, dim, 1, S, U);
2193 lambda_matrix_row_negate (U, dim, 0);
2195 gcd_alpha_beta = S[0][0];
2197 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2198 but that is a quite strange case. Instead of ICEing, answer
2200 if (gcd_alpha_beta == 0)
2202 *overlaps_a = conflict_fn_not_known ();
2203 *overlaps_b = conflict_fn_not_known ();
2204 *last_conflicts = chrec_dont_know;
2205 goto end_analyze_subs_aa;
2208 /* The classic "gcd-test". */
2209 if (!int_divides_p (gcd_alpha_beta, gamma))
2211 /* The "gcd-test" has determined that there is no integer
2212 solution, i.e. there is no dependence. */
2213 *overlaps_a = conflict_fn_no_dependence ();
2214 *overlaps_b = conflict_fn_no_dependence ();
2215 *last_conflicts = integer_zero_node;
2218 /* Both access functions are univariate. This includes SIV and MIV cases. */
2219 else if (nb_vars_a == 1 && nb_vars_b == 1)
2221 /* Both functions should have the same evolution sign. */
2222 if (((A[0][0] > 0 && -A[1][0] > 0)
2223 || (A[0][0] < 0 && -A[1][0] < 0)))
2225 /* The solutions are given by:
2227 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2230 For a given integer t. Using the following variables,
2232 | i0 = u11 * gamma / gcd_alpha_beta
2233 | j0 = u12 * gamma / gcd_alpha_beta
2240 | y0 = j0 + j1 * t. */
2241 HOST_WIDE_INT i0, j0, i1, j1;
2243 i0 = U[0][0] * gamma / gcd_alpha_beta;
2244 j0 = U[0][1] * gamma / gcd_alpha_beta;
2248 if ((i1 == 0 && i0 < 0)
2249 || (j1 == 0 && j0 < 0))
2251 /* There is no solution.
2252 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2253 falls in here, but for the moment we don't look at the
2254 upper bound of the iteration domain. */
2255 *overlaps_a = conflict_fn_no_dependence ();
2256 *overlaps_b = conflict_fn_no_dependence ();
2257 *last_conflicts = integer_zero_node;
2258 goto end_analyze_subs_aa;
2261 if (i1 > 0 && j1 > 0)
2263 HOST_WIDE_INT niter_a = estimated_loop_iterations_int
2264 (get_chrec_loop (chrec_a), false);
2265 HOST_WIDE_INT niter_b = estimated_loop_iterations_int
2266 (get_chrec_loop (chrec_b), false);
2267 HOST_WIDE_INT niter = MIN (niter_a, niter_b);
2269 /* (X0, Y0) is a solution of the Diophantine equation:
2270 "chrec_a (X0) = chrec_b (Y0)". */
2271 HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
2273 HOST_WIDE_INT x0 = i1 * tau1 + i0;
2274 HOST_WIDE_INT y0 = j1 * tau1 + j0;
2276 /* (X1, Y1) is the smallest positive solution of the eq
2277 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2278 first conflict occurs. */
2279 HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
2280 HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
2281 HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
2285 HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
2286 FLOOR_DIV (niter - j0, j1));
2287 HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
2289 /* If the overlap occurs outside of the bounds of the
2290 loop, there is no dependence. */
2291 if (x1 > niter || y1 > niter)
2293 *overlaps_a = conflict_fn_no_dependence ();
2294 *overlaps_b = conflict_fn_no_dependence ();
2295 *last_conflicts = integer_zero_node;
2296 goto end_analyze_subs_aa;
2299 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2302 *last_conflicts = chrec_dont_know;
2306 affine_fn_univar (build_int_cst (NULL_TREE, x1),
2308 build_int_cst (NULL_TREE, i1)));
2311 affine_fn_univar (build_int_cst (NULL_TREE, y1),
2313 build_int_cst (NULL_TREE, j1)));
2317 /* FIXME: For the moment, the upper bound of the
2318 iteration domain for i and j is not checked. */
2319 if (dump_file && (dump_flags & TDF_DETAILS))
2320 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2321 *overlaps_a = conflict_fn_not_known ();
2322 *overlaps_b = conflict_fn_not_known ();
2323 *last_conflicts = chrec_dont_know;
2328 if (dump_file && (dump_flags & TDF_DETAILS))
2329 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2330 *overlaps_a = conflict_fn_not_known ();
2331 *overlaps_b = conflict_fn_not_known ();
2332 *last_conflicts = chrec_dont_know;
2337 if (dump_file && (dump_flags & TDF_DETAILS))
2338 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2339 *overlaps_a = conflict_fn_not_known ();
2340 *overlaps_b = conflict_fn_not_known ();
2341 *last_conflicts = chrec_dont_know;
2344 end_analyze_subs_aa:
2345 if (dump_file && (dump_flags & TDF_DETAILS))
2347 fprintf (dump_file, " (overlaps_a = ");
2348 dump_conflict_function (dump_file, *overlaps_a);
2349 fprintf (dump_file, ")\n (overlaps_b = ");
2350 dump_conflict_function (dump_file, *overlaps_b);
2351 fprintf (dump_file, ")\n");
2352 fprintf (dump_file, ")\n");
2356 /* Returns true when analyze_subscript_affine_affine can be used for
2357 determining the dependence relation between chrec_a and chrec_b,
2358 that contain symbols. This function modifies chrec_a and chrec_b
2359 such that the analysis result is the same, and such that they don't
2360 contain symbols, and then can safely be passed to the analyzer.
2362 Example: The analysis of the following tuples of evolutions produce
2363 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2366 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2367 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2371 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2373 tree diff, type, left_a, left_b, right_b;
2375 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2376 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2377 /* FIXME: For the moment not handled. Might be refined later. */
2380 type = chrec_type (*chrec_a);
2381 left_a = CHREC_LEFT (*chrec_a);
2382 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
2383 diff = chrec_fold_minus (type, left_a, left_b);
2385 if (!evolution_function_is_constant_p (diff))
2388 if (dump_file && (dump_flags & TDF_DETAILS))
2389 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2391 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2392 diff, CHREC_RIGHT (*chrec_a));
2393 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
2394 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2395 build_int_cst (type, 0),
2400 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2401 *OVERLAPS_B are initialized to the functions that describe the
2402 relation between the elements accessed twice by CHREC_A and
2403 CHREC_B. For k >= 0, the following property is verified:
2405 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2408 analyze_siv_subscript (tree chrec_a,
2410 conflict_function **overlaps_a,
2411 conflict_function **overlaps_b,
2412 tree *last_conflicts,
2415 dependence_stats.num_siv++;
2417 if (dump_file && (dump_flags & TDF_DETAILS))
2418 fprintf (dump_file, "(analyze_siv_subscript \n");
2420 if (evolution_function_is_constant_p (chrec_a)
2421 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2422 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2423 overlaps_a, overlaps_b, last_conflicts);
2425 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2426 && evolution_function_is_constant_p (chrec_b))
2427 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2428 overlaps_b, overlaps_a, last_conflicts);
2430 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2431 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2433 if (!chrec_contains_symbols (chrec_a)
2434 && !chrec_contains_symbols (chrec_b))
2436 analyze_subscript_affine_affine (chrec_a, chrec_b,
2437 overlaps_a, overlaps_b,
2440 if (CF_NOT_KNOWN_P (*overlaps_a)
2441 || CF_NOT_KNOWN_P (*overlaps_b))
2442 dependence_stats.num_siv_unimplemented++;
2443 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2444 || CF_NO_DEPENDENCE_P (*overlaps_b))
2445 dependence_stats.num_siv_independent++;
2447 dependence_stats.num_siv_dependent++;
2449 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2452 analyze_subscript_affine_affine (chrec_a, chrec_b,
2453 overlaps_a, overlaps_b,
2456 if (CF_NOT_KNOWN_P (*overlaps_a)
2457 || CF_NOT_KNOWN_P (*overlaps_b))
2458 dependence_stats.num_siv_unimplemented++;
2459 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2460 || CF_NO_DEPENDENCE_P (*overlaps_b))
2461 dependence_stats.num_siv_independent++;
2463 dependence_stats.num_siv_dependent++;
2466 goto siv_subscript_dontknow;
2471 siv_subscript_dontknow:;
2472 if (dump_file && (dump_flags & TDF_DETAILS))
2473 fprintf (dump_file, "siv test failed: unimplemented.\n");
2474 *overlaps_a = conflict_fn_not_known ();
2475 *overlaps_b = conflict_fn_not_known ();
2476 *last_conflicts = chrec_dont_know;
2477 dependence_stats.num_siv_unimplemented++;
2480 if (dump_file && (dump_flags & TDF_DETAILS))
2481 fprintf (dump_file, ")\n");
2484 /* Returns false if we can prove that the greatest common divisor of the steps
2485 of CHREC does not divide CST, false otherwise. */
2488 gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
2490 HOST_WIDE_INT cd = 0, val;
2493 if (!host_integerp (cst, 0))
2495 val = tree_low_cst (cst, 0);
2497 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2499 step = CHREC_RIGHT (chrec);
2500 if (!host_integerp (step, 0))
2502 cd = gcd (cd, tree_low_cst (step, 0));
2503 chrec = CHREC_LEFT (chrec);
2506 return val % cd == 0;
2509 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2510 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2511 functions that describe the relation between the elements accessed
2512 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2515 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2518 analyze_miv_subscript (tree chrec_a,
2520 conflict_function **overlaps_a,
2521 conflict_function **overlaps_b,
2522 tree *last_conflicts,
2523 struct loop *loop_nest)
2525 /* FIXME: This is a MIV subscript, not yet handled.
2526 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2529 In the SIV test we had to solve a Diophantine equation with two
2530 variables. In the MIV case we have to solve a Diophantine
2531 equation with 2*n variables (if the subscript uses n IVs).
2533 tree type, difference;
2535 dependence_stats.num_miv++;
2536 if (dump_file && (dump_flags & TDF_DETAILS))
2537 fprintf (dump_file, "(analyze_miv_subscript \n");
2539 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
2540 chrec_a = chrec_convert (type, chrec_a, NULL);
2541 chrec_b = chrec_convert (type, chrec_b, NULL);
2542 difference = chrec_fold_minus (type, chrec_a, chrec_b);
2544 if (eq_evolutions_p (chrec_a, chrec_b))
2546 /* Access functions are the same: all the elements are accessed
2547 in the same order. */
2548 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2549 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2550 *last_conflicts = estimated_loop_iterations_tree
2551 (get_chrec_loop (chrec_a), true);
2552 dependence_stats.num_miv_dependent++;
2555 else if (evolution_function_is_constant_p (difference)
2556 /* For the moment, the following is verified:
2557 evolution_function_is_affine_multivariate_p (chrec_a,
2559 && !gcd_of_steps_may_divide_p (chrec_a, difference))
2561 /* testsuite/.../ssa-chrec-33.c
2562 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2564 The difference is 1, and all the evolution steps are multiples
2565 of 2, consequently there are no overlapping elements. */
2566 *overlaps_a = conflict_fn_no_dependence ();
2567 *overlaps_b = conflict_fn_no_dependence ();
2568 *last_conflicts = integer_zero_node;
2569 dependence_stats.num_miv_independent++;
2572 else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2573 && !chrec_contains_symbols (chrec_a)
2574 && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
2575 && !chrec_contains_symbols (chrec_b))
2577 /* testsuite/.../ssa-chrec-35.c
2578 {0, +, 1}_2 vs. {0, +, 1}_3
2579 the overlapping elements are respectively located at iterations:
2580 {0, +, 1}_x and {0, +, 1}_x,
2581 in other words, we have the equality:
2582 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2585 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2586 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2588 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2589 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2591 analyze_subscript_affine_affine (chrec_a, chrec_b,
2592 overlaps_a, overlaps_b, last_conflicts);
2594 if (CF_NOT_KNOWN_P (*overlaps_a)
2595 || CF_NOT_KNOWN_P (*overlaps_b))
2596 dependence_stats.num_miv_unimplemented++;
2597 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2598 || CF_NO_DEPENDENCE_P (*overlaps_b))
2599 dependence_stats.num_miv_independent++;
2601 dependence_stats.num_miv_dependent++;
2606 /* When the analysis is too difficult, answer "don't know". */
2607 if (dump_file && (dump_flags & TDF_DETAILS))
2608 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2610 *overlaps_a = conflict_fn_not_known ();
2611 *overlaps_b = conflict_fn_not_known ();
2612 *last_conflicts = chrec_dont_know;
2613 dependence_stats.num_miv_unimplemented++;
2616 if (dump_file && (dump_flags & TDF_DETAILS))
2617 fprintf (dump_file, ")\n");
2620 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2621 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2622 OVERLAP_ITERATIONS_B are initialized with two functions that
2623 describe the iterations that contain conflicting elements.
2625 Remark: For an integer k >= 0, the following equality is true:
2627 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2631 analyze_overlapping_iterations (tree chrec_a,
2633 conflict_function **overlap_iterations_a,
2634 conflict_function **overlap_iterations_b,
2635 tree *last_conflicts, struct loop *loop_nest)
2637 unsigned int lnn = loop_nest->num;
2639 dependence_stats.num_subscript_tests++;
2641 if (dump_file && (dump_flags & TDF_DETAILS))
2643 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2644 fprintf (dump_file, " (chrec_a = ");
2645 print_generic_expr (dump_file, chrec_a, 0);
2646 fprintf (dump_file, ")\n (chrec_b = ");
2647 print_generic_expr (dump_file, chrec_b, 0);
2648 fprintf (dump_file, ")\n");
2651 if (chrec_a == NULL_TREE
2652 || chrec_b == NULL_TREE
2653 || chrec_contains_undetermined (chrec_a)
2654 || chrec_contains_undetermined (chrec_b))
2656 dependence_stats.num_subscript_undetermined++;
2658 *overlap_iterations_a = conflict_fn_not_known ();
2659 *overlap_iterations_b = conflict_fn_not_known ();
2662 /* If they are the same chrec, and are affine, they overlap
2663 on every iteration. */
2664 else if (eq_evolutions_p (chrec_a, chrec_b)
2665 && evolution_function_is_affine_multivariate_p (chrec_a, lnn))
2667 dependence_stats.num_same_subscript_function++;
2668 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2669 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2670 *last_conflicts = chrec_dont_know;
2673 /* If they aren't the same, and aren't affine, we can't do anything
2675 else if ((chrec_contains_symbols (chrec_a)
2676 || chrec_contains_symbols (chrec_b))
2677 && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2678 || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
2680 dependence_stats.num_subscript_undetermined++;
2681 *overlap_iterations_a = conflict_fn_not_known ();
2682 *overlap_iterations_b = conflict_fn_not_known ();
2685 else if (ziv_subscript_p (chrec_a, chrec_b))
2686 analyze_ziv_subscript (chrec_a, chrec_b,
2687 overlap_iterations_a, overlap_iterations_b,
2690 else if (siv_subscript_p (chrec_a, chrec_b))
2691 analyze_siv_subscript (chrec_a, chrec_b,
2692 overlap_iterations_a, overlap_iterations_b,
2693 last_conflicts, lnn);
2696 analyze_miv_subscript (chrec_a, chrec_b,
2697 overlap_iterations_a, overlap_iterations_b,
2698 last_conflicts, loop_nest);
2700 if (dump_file && (dump_flags & TDF_DETAILS))
2702 fprintf (dump_file, " (overlap_iterations_a = ");
2703 dump_conflict_function (dump_file, *overlap_iterations_a);
2704 fprintf (dump_file, ")\n (overlap_iterations_b = ");
2705 dump_conflict_function (dump_file, *overlap_iterations_b);
2706 fprintf (dump_file, ")\n");
2707 fprintf (dump_file, ")\n");
2711 /* Helper function for uniquely inserting distance vectors. */
2714 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
2719 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
2720 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
2723 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
2726 /* Helper function for uniquely inserting direction vectors. */
2729 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
2734 for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
2735 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
2738 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
2741 /* Add a distance of 1 on all the loops outer than INDEX. If we
2742 haven't yet determined a distance for this outer loop, push a new
2743 distance vector composed of the previous distance, and a distance
2744 of 1 for this outer loop. Example:
2752 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2753 save (0, 1), then we have to save (1, 0). */
2756 add_outer_distances (struct data_dependence_relation *ddr,
2757 lambda_vector dist_v, int index)
2759 /* For each outer loop where init_v is not set, the accesses are
2760 in dependence of distance 1 in the loop. */
2761 while (--index >= 0)
2763 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2764 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
2766 save_dist_v (ddr, save_v);
2770 /* Return false when fail to represent the data dependence as a
2771 distance vector. INIT_B is set to true when a component has been
2772 added to the distance vector DIST_V. INDEX_CARRY is then set to
2773 the index in DIST_V that carries the dependence. */
2776 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
2777 struct data_reference *ddr_a,
2778 struct data_reference *ddr_b,
2779 lambda_vector dist_v, bool *init_b,
2783 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2785 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2787 tree access_fn_a, access_fn_b;
2788 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2790 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2792 non_affine_dependence_relation (ddr);
2796 access_fn_a = DR_ACCESS_FN (ddr_a, i);
2797 access_fn_b = DR_ACCESS_FN (ddr_b, i);
2799 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
2800 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
2803 int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
2804 DDR_LOOP_NEST (ddr));
2805 int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
2806 DDR_LOOP_NEST (ddr));
2808 /* The dependence is carried by the outermost loop. Example:
2815 In this case, the dependence is carried by loop_1. */
2816 index = index_a < index_b ? index_a : index_b;
2817 *index_carry = MIN (index, *index_carry);
2819 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2821 non_affine_dependence_relation (ddr);
2825 dist = int_cst_value (SUB_DISTANCE (subscript));
2827 /* This is the subscript coupling test. If we have already
2828 recorded a distance for this loop (a distance coming from
2829 another subscript), it should be the same. For example,
2830 in the following code, there is no dependence:
2837 if (init_v[index] != 0 && dist_v[index] != dist)
2839 finalize_ddr_dependent (ddr, chrec_known);
2843 dist_v[index] = dist;
2847 else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
2849 /* This can be for example an affine vs. constant dependence
2850 (T[i] vs. T[3]) that is not an affine dependence and is
2851 not representable as a distance vector. */
2852 non_affine_dependence_relation (ddr);
2860 /* Return true when the DDR contains only constant access functions. */
2863 constant_access_functions (const struct data_dependence_relation *ddr)
2867 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2868 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
2869 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
2875 /* Helper function for the case where DDR_A and DDR_B are the same
2876 multivariate access function with a constant step. For an example
2880 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
2883 tree c_1 = CHREC_LEFT (c_2);
2884 tree c_0 = CHREC_LEFT (c_1);
2885 lambda_vector dist_v;
2888 /* Polynomials with more than 2 variables are not handled yet. When
2889 the evolution steps are parameters, it is not possible to
2890 represent the dependence using classical distance vectors. */
2891 if (TREE_CODE (c_0) != INTEGER_CST
2892 || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
2893 || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
2895 DDR_AFFINE_P (ddr) = false;
2899 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
2900 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
2902 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2903 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2904 v1 = int_cst_value (CHREC_RIGHT (c_1));
2905 v2 = int_cst_value (CHREC_RIGHT (c_2));
2918 save_dist_v (ddr, dist_v);
2920 add_outer_distances (ddr, dist_v, x_1);
2923 /* Helper function for the case where DDR_A and DDR_B are the same
2924 access functions. */
2927 add_other_self_distances (struct data_dependence_relation *ddr)
2929 lambda_vector dist_v;
2931 int index_carry = DDR_NB_LOOPS (ddr);
2933 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2935 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
2937 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
2939 if (!evolution_function_is_univariate_p (access_fun))
2941 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
2943 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2947 access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
2949 if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
2950 add_multivariate_self_dist (ddr, access_fun);
2952 /* The evolution step is not constant: it varies in
2953 the outer loop, so this cannot be represented by a
2954 distance vector. For example in pr34635.c the
2955 evolution is {0, +, {0, +, 4}_1}_2. */
2956 DDR_AFFINE_P (ddr) = false;
2961 index_carry = MIN (index_carry,
2962 index_in_loop_nest (CHREC_VARIABLE (access_fun),
2963 DDR_LOOP_NEST (ddr)));
2967 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2968 add_outer_distances (ddr, dist_v, index_carry);
2972 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
2974 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2976 dist_v[DDR_INNER_LOOP (ddr)] = 1;
2977 save_dist_v (ddr, dist_v);
2980 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2981 is the case for example when access functions are the same and
2982 equal to a constant, as in:
2989 in which case the distance vectors are (0) and (1). */
2992 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
2996 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2998 subscript_p sub = DDR_SUBSCRIPT (ddr, i);
2999 conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
3000 conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
3002 for (j = 0; j < ca->n; j++)
3003 if (affine_function_zero_p (ca->fns[j]))
3005 insert_innermost_unit_dist_vector (ddr);
3009 for (j = 0; j < cb->n; j++)
3010 if (affine_function_zero_p (cb->fns[j]))
3012 insert_innermost_unit_dist_vector (ddr);
3018 /* Compute the classic per loop distance vector. DDR is the data
3019 dependence relation to build a vector from. Return false when fail
3020 to represent the data dependence as a distance vector. */
3023 build_classic_dist_vector (struct data_dependence_relation *ddr,
3024 struct loop *loop_nest)
3026 bool init_b = false;
3027 int index_carry = DDR_NB_LOOPS (ddr);
3028 lambda_vector dist_v;
3030 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3033 if (same_access_functions (ddr))
3035 /* Save the 0 vector. */
3036 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3037 save_dist_v (ddr, dist_v);
3039 if (constant_access_functions (ddr))
3040 add_distance_for_zero_overlaps (ddr);
3042 if (DDR_NB_LOOPS (ddr) > 1)
3043 add_other_self_distances (ddr);
3048 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3049 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3050 dist_v, &init_b, &index_carry))
3053 /* Save the distance vector if we initialized one. */
3056 /* Verify a basic constraint: classic distance vectors should
3057 always be lexicographically positive.
3059 Data references are collected in the order of execution of
3060 the program, thus for the following loop
3062 | for (i = 1; i < 100; i++)
3063 | for (j = 1; j < 100; j++)
3065 | t = T[j+1][i-1]; // A
3066 | T[j][i] = t + 2; // B
3069 references are collected following the direction of the wind:
3070 A then B. The data dependence tests are performed also
3071 following this order, such that we're looking at the distance
3072 separating the elements accessed by A from the elements later
3073 accessed by B. But in this example, the distance returned by
3074 test_dep (A, B) is lexicographically negative (-1, 1), that
3075 means that the access A occurs later than B with respect to
3076 the outer loop, ie. we're actually looking upwind. In this
3077 case we solve test_dep (B, A) looking downwind to the
3078 lexicographically positive solution, that returns the
3079 distance vector (1, -1). */
3080 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3082 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3083 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3086 compute_subscript_distance (ddr);
3087 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3088 save_v, &init_b, &index_carry))
3090 save_dist_v (ddr, save_v);
3091 DDR_REVERSED_P (ddr) = true;
3093 /* In this case there is a dependence forward for all the
3096 | for (k = 1; k < 100; k++)
3097 | for (i = 1; i < 100; i++)
3098 | for (j = 1; j < 100; j++)
3100 | t = T[j+1][i-1]; // A
3101 | T[j][i] = t + 2; // B
3109 if (DDR_NB_LOOPS (ddr) > 1)
3111 add_outer_distances (ddr, save_v, index_carry);
3112 add_outer_distances (ddr, dist_v, index_carry);
3117 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3118 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3120 if (DDR_NB_LOOPS (ddr) > 1)
3122 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3124 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
3125 DDR_A (ddr), loop_nest))
3127 compute_subscript_distance (ddr);
3128 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3129 opposite_v, &init_b,
3133 save_dist_v (ddr, save_v);
3134 add_outer_distances (ddr, dist_v, index_carry);
3135 add_outer_distances (ddr, opposite_v, index_carry);
3138 save_dist_v (ddr, save_v);
3143 /* There is a distance of 1 on all the outer loops: Example:
3144 there is a dependence of distance 1 on loop_1 for the array A.
3150 add_outer_distances (ddr, dist_v,
3151 lambda_vector_first_nz (dist_v,
3152 DDR_NB_LOOPS (ddr), 0));
3155 if (dump_file && (dump_flags & TDF_DETAILS))
3159 fprintf (dump_file, "(build_classic_dist_vector\n");
3160 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3162 fprintf (dump_file, " dist_vector = (");
3163 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3164 DDR_NB_LOOPS (ddr));
3165 fprintf (dump_file, " )\n");
3167 fprintf (dump_file, ")\n");
3173 /* Return the direction for a given distance.
3174 FIXME: Computing dir this way is suboptimal, since dir can catch
3175 cases that dist is unable to represent. */
3177 static inline enum data_dependence_direction
3178 dir_from_dist (int dist)
3181 return dir_positive;
3183 return dir_negative;
3188 /* Compute the classic per loop direction vector. DDR is the data
3189 dependence relation to build a vector from. */
3192 build_classic_dir_vector (struct data_dependence_relation *ddr)
3195 lambda_vector dist_v;
3197 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
3199 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3201 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3202 dir_v[j] = dir_from_dist (dist_v[j]);
3204 save_dir_v (ddr, dir_v);
3208 /* Helper function. Returns true when there is a dependence between
3209 data references DRA and DRB. */
3212 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3213 struct data_reference *dra,
3214 struct data_reference *drb,
3215 struct loop *loop_nest)
3218 tree last_conflicts;
3219 struct subscript *subscript;
3221 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3224 conflict_function *overlaps_a, *overlaps_b;
3226 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3227 DR_ACCESS_FN (drb, i),
3228 &overlaps_a, &overlaps_b,
3229 &last_conflicts, loop_nest);
3231 if (CF_NOT_KNOWN_P (overlaps_a)
3232 || CF_NOT_KNOWN_P (overlaps_b))
3234 finalize_ddr_dependent (ddr, chrec_dont_know);
3235 dependence_stats.num_dependence_undetermined++;
3236 free_conflict_function (overlaps_a);
3237 free_conflict_function (overlaps_b);
3241 else if (CF_NO_DEPENDENCE_P (overlaps_a)
3242 || CF_NO_DEPENDENCE_P (overlaps_b))
3244 finalize_ddr_dependent (ddr, chrec_known);
3245 dependence_stats.num_dependence_independent++;
3246 free_conflict_function (overlaps_a);
3247 free_conflict_function (overlaps_b);
3253 if (SUB_CONFLICTS_IN_A (subscript))
3254 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3255 if (SUB_CONFLICTS_IN_B (subscript))
3256 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3258 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3259 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3260 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3267 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3270 subscript_dependence_tester (struct data_dependence_relation *ddr,
3271 struct loop *loop_nest)
3274 if (dump_file && (dump_flags & TDF_DETAILS))
3275 fprintf (dump_file, "(subscript_dependence_tester \n");
3277 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3278 dependence_stats.num_dependence_dependent++;
3280 compute_subscript_distance (ddr);
3281 if (build_classic_dist_vector (ddr, loop_nest))
3282 build_classic_dir_vector (ddr);
3284 if (dump_file && (dump_flags & TDF_DETAILS))
3285 fprintf (dump_file, ")\n");
3288 /* Returns true when all the access functions of A are affine or
3289 constant with respect to LOOP_NEST. */
3292 access_functions_are_affine_or_constant_p (const struct data_reference *a,
3293 const struct loop *loop_nest)
3296 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3299 for (i = 0; VEC_iterate (tree, fns, i, t); i++)
3300 if (!evolution_function_is_invariant_p (t, loop_nest->num)
3301 && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3307 /* Return true if we can create an affine data-ref for OP in STMT. */
3310 stmt_simple_memref_p (struct loop *loop, gimple stmt, tree op)
3312 data_reference_p dr;
3314 dr = create_data_ref (loop, op, stmt, true);
3315 if (!access_functions_are_affine_or_constant_p (dr, loop))
3322 /* Initializes an equation for an OMEGA problem using the information
3323 contained in the ACCESS_FUN. Returns true when the operation
3326 PB is the omega constraint system.
3327 EQ is the number of the equation to be initialized.
3328 OFFSET is used for shifting the variables names in the constraints:
3329 a constrain is composed of 2 * the number of variables surrounding
3330 dependence accesses. OFFSET is set either to 0 for the first n variables,
3331 then it is set to n.
3332 ACCESS_FUN is expected to be an affine chrec. */
3335 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3336 unsigned int offset, tree access_fun,
3337 struct data_dependence_relation *ddr)
3339 switch (TREE_CODE (access_fun))
3341 case POLYNOMIAL_CHREC:
3343 tree left = CHREC_LEFT (access_fun);
3344 tree right = CHREC_RIGHT (access_fun);
3345 int var = CHREC_VARIABLE (access_fun);
3348 if (TREE_CODE (right) != INTEGER_CST)
3351 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3352 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3354 /* Compute the innermost loop index. */
3355 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3358 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3359 += int_cst_value (right);
3361 switch (TREE_CODE (left))
3363 case POLYNOMIAL_CHREC:
3364 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3367 pb->eqs[eq].coef[0] += int_cst_value (left);
3376 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3384 /* As explained in the comments preceding init_omega_for_ddr, we have
3385 to set up a system for each loop level, setting outer loops
3386 variation to zero, and current loop variation to positive or zero.
3387 Save each lexico positive distance vector. */
3390 omega_extract_distance_vectors (omega_pb pb,
3391 struct data_dependence_relation *ddr)
3395 struct loop *loopi, *loopj;
3396 enum omega_result res;
3398 /* Set a new problem for each loop in the nest. The basis is the
3399 problem that we have initialized until now. On top of this we
3400 add new constraints. */
3401 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3402 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3405 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3406 DDR_NB_LOOPS (ddr));
3408 omega_copy_problem (copy, pb);
3410 /* For all the outer loops "loop_j", add "dj = 0". */
3412 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3414 eq = omega_add_zero_eq (copy, omega_black);
3415 copy->eqs[eq].coef[j + 1] = 1;
3418 /* For "loop_i", add "0 <= di". */
3419 geq = omega_add_zero_geq (copy, omega_black);
3420 copy->geqs[geq].coef[i + 1] = 1;
3422 /* Reduce the constraint system, and test that the current
3423 problem is feasible. */
3424 res = omega_simplify_problem (copy);
3425 if (res == omega_false
3426 || res == omega_unknown
3427 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3430 for (eq = 0; eq < copy->num_subs; eq++)
3431 if (copy->subs[eq].key == (int) i + 1)
3433 dist = copy->subs[eq].coef[0];
3439 /* Reinitialize problem... */
3440 omega_copy_problem (copy, pb);
3442 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3444 eq = omega_add_zero_eq (copy, omega_black);
3445 copy->eqs[eq].coef[j + 1] = 1;
3448 /* ..., but this time "di = 1". */
3449 eq = omega_add_zero_eq (copy, omega_black);
3450 copy->eqs[eq].coef[i + 1] = 1;
3451 copy->eqs[eq].coef[0] = -1;
3453 res = omega_simplify_problem (copy);
3454 if (res == omega_false
3455 || res == omega_unknown
3456 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3459 for (eq = 0; eq < copy->num_subs; eq++)
3460 if (copy->subs[eq].key == (int) i + 1)
3462 dist = copy->subs[eq].coef[0];
3468 /* Save the lexicographically positive distance vector. */
3471 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3472 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3476 for (eq = 0; eq < copy->num_subs; eq++)
3477 if (copy->subs[eq].key > 0)
3479 dist = copy->subs[eq].coef[0];
3480 dist_v[copy->subs[eq].key - 1] = dist;
3483 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3484 dir_v[j] = dir_from_dist (dist_v[j]);
3486 save_dist_v (ddr, dist_v);
3487 save_dir_v (ddr, dir_v);
3491 omega_free_problem (copy);
3495 /* This is called for each subscript of a tuple of data references:
3496 insert an equality for representing the conflicts. */
3499 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3500 struct data_dependence_relation *ddr,
3501 omega_pb pb, bool *maybe_dependent)
3504 tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3505 TREE_TYPE (access_fun_b));
3506 tree fun_a = chrec_convert (type, access_fun_a, NULL);
3507 tree fun_b = chrec_convert (type, access_fun_b, NULL);
3508 tree difference = chrec_fold_minus (type, fun_a, fun_b);
3510 /* When the fun_a - fun_b is not constant, the dependence is not
3511 captured by the classic distance vector representation. */
3512 if (TREE_CODE (difference) != INTEGER_CST)
3516 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3518 /* There is no dependence. */
3519 *maybe_dependent = false;
3523 fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
3525 eq = omega_add_zero_eq (pb, omega_black);
3526 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3527 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3528 /* There is probably a dependence, but the system of
3529 constraints cannot be built: answer "don't know". */
3533 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3534 && !int_divides_p (lambda_vector_gcd
3535 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3536 2 * DDR_NB_LOOPS (ddr)),
3537 pb->eqs[eq].coef[0]))
3539 /* There is no dependence. */
3540 *maybe_dependent = false;
3547 /* Helper function, same as init_omega_for_ddr but specialized for
3548 data references A and B. */
3551 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3552 struct data_dependence_relation *ddr,
3553 omega_pb pb, bool *maybe_dependent)
3558 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3560 /* Insert an equality per subscript. */
3561 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3563 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3564 ddr, pb, maybe_dependent))
3566 else if (*maybe_dependent == false)
3568 /* There is no dependence. */
3569 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3574 /* Insert inequalities: constraints corresponding to the iteration
3575 domain, i.e. the loops surrounding the references "loop_x" and
3576 the distance variables "dx". The layout of the OMEGA
3577 representation is as follows:
3578 - coef[0] is the constant
3579 - coef[1..nb_loops] are the protected variables that will not be
3580 removed by the solver: the "dx"
3581 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3583 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3584 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3586 HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
3589 ineq = omega_add_zero_geq (pb, omega_black);
3590 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3592 /* 0 <= loop_x + dx */
3593 ineq = omega_add_zero_geq (pb, omega_black);
3594 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3595 pb->geqs[ineq].coef[i + 1] = 1;
3599 /* loop_x <= nb_iters */
3600 ineq = omega_add_zero_geq (pb, omega_black);
3601 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3602 pb->geqs[ineq].coef[0] = nbi;
3604 /* loop_x + dx <= nb_iters */
3605 ineq = omega_add_zero_geq (pb, omega_black);
3606 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3607 pb->geqs[ineq].coef[i + 1] = -1;
3608 pb->geqs[ineq].coef[0] = nbi;
3610 /* A step "dx" bigger than nb_iters is not feasible, so
3611 add "0 <= nb_iters + dx", */
3612 ineq = omega_add_zero_geq (pb, omega_black);
3613 pb->geqs[ineq].coef[i + 1] = 1;
3614 pb->geqs[ineq].coef[0] = nbi;
3615 /* and "dx <= nb_iters". */
3616 ineq = omega_add_zero_geq (pb, omega_black);
3617 pb->geqs[ineq].coef[i + 1] = -1;
3618 pb->geqs[ineq].coef[0] = nbi;
3622 omega_extract_distance_vectors (pb, ddr);
3627 /* Sets up the Omega dependence problem for the data dependence
3628 relation DDR. Returns false when the constraint system cannot be
3629 built, ie. when the test answers "don't know". Returns true
3630 otherwise, and when independence has been proved (using one of the
3631 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3632 set MAYBE_DEPENDENT to true.
3634 Example: for setting up the dependence system corresponding to the
3635 conflicting accesses
3640 | ... A[2*j, 2*(i + j)]
3644 the following constraints come from the iteration domain:
3651 where di, dj are the distance variables. The constraints
3652 representing the conflicting elements are:
3655 i + 1 = 2 * (i + di + j + dj)
3657 For asking that the resulting distance vector (di, dj) be
3658 lexicographically positive, we insert the constraint "di >= 0". If
3659 "di = 0" in the solution, we fix that component to zero, and we
3660 look at the inner loops: we set a new problem where all the outer
3661 loop distances are zero, and fix this inner component to be
3662 positive. When one of the components is positive, we save that
3663 distance, and set a new problem where the distance on this loop is
3664 zero, searching for other distances in the inner loops. Here is
3665 the classic example that illustrates that we have to set for each
3666 inner loop a new problem:
3674 we have to save two distances (1, 0) and (0, 1).
3676 Given two array references, refA and refB, we have to set the
3677 dependence problem twice, refA vs. refB and refB vs. refA, and we
3678 cannot do a single test, as refB might occur before refA in the
3679 inner loops, and the contrary when considering outer loops: ex.
3684 | T[{1,+,1}_2][{1,+,1}_1] // refA
3685 | T[{2,+,1}_2][{0,+,1}_1] // refB
3690 refB touches the elements in T before refA, and thus for the same
3691 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3692 but for successive loop_0 iterations, we have (1, -1, 1)
3694 The Omega solver expects the distance variables ("di" in the
3695 previous example) to come first in the constraint system (as
3696 variables to be protected, or "safe" variables), the constraint
3697 system is built using the following layout:
3699 "cst | distance vars | index vars".
3703 init_omega_for_ddr (struct data_dependence_relation *ddr,
3704 bool *maybe_dependent)
3709 *maybe_dependent = true;
3711 if (same_access_functions (ddr))
3714 lambda_vector dir_v;
3716 /* Save the 0 vector. */
3717 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3718 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3719 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3720 dir_v[j] = dir_equal;
3721 save_dir_v (ddr, dir_v);
3723 /* Save the dependences carried by outer loops. */
3724 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3725 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3727 omega_free_problem (pb);
3731 /* Omega expects the protected variables (those that have to be kept
3732 after elimination) to appear first in the constraint system.
3733 These variables are the distance variables. In the following
3734 initialization we declare NB_LOOPS safe variables, and the total
3735 number of variables for the constraint system is 2*NB_LOOPS. */
3736 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3737 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3739 omega_free_problem (pb);
3741 /* Stop computation if not decidable, or no dependence. */
3742 if (res == false || *maybe_dependent == false)
3745 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3746 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3748 omega_free_problem (pb);
3753 /* Return true when DDR contains the same information as that stored
3754 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3757 ddr_consistent_p (FILE *file,
3758 struct data_dependence_relation *ddr,
3759 VEC (lambda_vector, heap) *dist_vects,
3760 VEC (lambda_vector, heap) *dir_vects)
3764 /* If dump_file is set, output there. */
3765 if (dump_file && (dump_flags & TDF_DETAILS))
3768 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3770 lambda_vector b_dist_v;
3771 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3772 VEC_length (lambda_vector, dist_vects),
3773 DDR_NUM_DIST_VECTS (ddr));
3775 fprintf (file, "Banerjee dist vectors:\n");
3776 for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
3777 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3779 fprintf (file, "Omega dist vectors:\n");
3780 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3781 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3783 fprintf (file, "data dependence relation:\n");
3784 dump_data_dependence_relation (file, ddr);
3786 fprintf (file, ")\n");
3790 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3792 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3793 VEC_length (lambda_vector, dir_vects),
3794 DDR_NUM_DIR_VECTS (ddr));
3798 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3800 lambda_vector a_dist_v;
3801 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3803 /* Distance vectors are not ordered in the same way in the DDR
3804 and in the DIST_VECTS: search for a matching vector. */
3805 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
3806 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3809 if (j == VEC_length (lambda_vector, dist_vects))
3811 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3812 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3813 fprintf (file, "not found in Omega dist vectors:\n");
3814 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3815 fprintf (file, "data dependence relation:\n");
3816 dump_data_dependence_relation (file, ddr);
3817 fprintf (file, ")\n");
3821 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3823 lambda_vector a_dir_v;
3824 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3826 /* Direction vectors are not ordered in the same way in the DDR
3827 and in the DIR_VECTS: search for a matching vector. */
3828 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
3829 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3832 if (j == VEC_length (lambda_vector, dist_vects))
3834 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3835 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3836 fprintf (file, "not found in Omega dir vectors:\n");
3837 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3838 fprintf (file, "data dependence relation:\n");
3839 dump_data_dependence_relation (file, ddr);
3840 fprintf (file, ")\n");
3847 /* This computes the affine dependence relation between A and B with
3848 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3849 independence between two accesses, while CHREC_DONT_KNOW is used
3850 for representing the unknown relation.
3852 Note that it is possible to stop the computation of the dependence
3853 relation the first time we detect a CHREC_KNOWN element for a given
3857 compute_affine_dependence (struct data_dependence_relation *ddr,
3858 struct loop *loop_nest)
3860 struct data_reference *dra = DDR_A (ddr);
3861 struct data_reference *drb = DDR_B (ddr);
3863 if (dump_file && (dump_flags & TDF_DETAILS))
3865 fprintf (dump_file, "(compute_affine_dependence\n");
3866 fprintf (dump_file, " (stmt_a = \n");
3867 print_gimple_stmt (dump_file, DR_STMT (dra), 0, 0);
3868 fprintf (dump_file, ")\n (stmt_b = \n");
3869 print_gimple_stmt (dump_file, DR_STMT (drb), 0, 0);
3870 fprintf (dump_file, ")\n");
3873 /* Analyze only when the dependence relation is not yet known. */
3874 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
3875 && !DDR_SELF_REFERENCE (ddr))
3877 dependence_stats.num_dependence_tests++;
3879 if (access_functions_are_affine_or_constant_p (dra, loop_nest)
3880 && access_functions_are_affine_or_constant_p (drb, loop_nest))
3882 if (flag_check_data_deps)
3884 /* Compute the dependences using the first algorithm. */
3885 subscript_dependence_tester (ddr, loop_nest);
3887 if (dump_file && (dump_flags & TDF_DETAILS))
3889 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3890 dump_data_dependence_relation (dump_file, ddr);
3893 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3895 bool maybe_dependent;
3896 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3898 /* Save the result of the first DD analyzer. */
3899 dist_vects = DDR_DIST_VECTS (ddr);
3900 dir_vects = DDR_DIR_VECTS (ddr);
3902 /* Reset the information. */
3903 DDR_DIST_VECTS (ddr) = NULL;
3904 DDR_DIR_VECTS (ddr) = NULL;
3906 /* Compute the same information using Omega. */
3907 if (!init_omega_for_ddr (ddr, &maybe_dependent))
3908 goto csys_dont_know;
3910 if (dump_file && (dump_flags & TDF_DETAILS))
3912 fprintf (dump_file, "Omega Analyzer\n");
3913 dump_data_dependence_relation (dump_file, ddr);
3916 /* Check that we get the same information. */
3917 if (maybe_dependent)
3918 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3923 subscript_dependence_tester (ddr, loop_nest);
3926 /* As a last case, if the dependence cannot be determined, or if
3927 the dependence is considered too difficult to determine, answer
3932 dependence_stats.num_dependence_undetermined++;
3934 if (dump_file && (dump_flags & TDF_DETAILS))
3936 fprintf (dump_file, "Data ref a:\n");
3937 dump_data_reference (dump_file, dra);
3938 fprintf (dump_file, "Data ref b:\n");
3939 dump_data_reference (dump_file, drb);
3940 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3942 finalize_ddr_dependent (ddr, chrec_dont_know);
3946 if (dump_file && (dump_flags & TDF_DETAILS))
3947 fprintf (dump_file, ")\n");
3950 /* This computes the dependence relation for the same data
3951 reference into DDR. */
3954 compute_self_dependence (struct data_dependence_relation *ddr)
3957 struct subscript *subscript;
3959 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3962 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3965 if (SUB_CONFLICTS_IN_A (subscript))
3966 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3967 if (SUB_CONFLICTS_IN_B (subscript))
3968 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3970 /* The accessed index overlaps for each iteration. */
3971 SUB_CONFLICTS_IN_A (subscript)
3972 = conflict_fn (1, affine_fn_cst (integer_zero_node));
3973 SUB_CONFLICTS_IN_B (subscript)
3974 = conflict_fn (1, affine_fn_cst (integer_zero_node));
3975 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3978 /* The distance vector is the zero vector. */
3979 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3980 save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3983 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3984 the data references in DATAREFS, in the LOOP_NEST. When
3985 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3989 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3990 VEC (ddr_p, heap) **dependence_relations,
3991 VEC (loop_p, heap) *loop_nest,
3992 bool compute_self_and_rr)
3994 struct data_dependence_relation *ddr;
3995 struct data_reference *a, *b;
3998 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3999 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
4000 if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
4002 ddr = initialize_data_dependence_relation (a, b, loop_nest);
4003 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4004 compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
4007 if (compute_self_and_rr)
4008 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4010 ddr = initialize_data_dependence_relation (a, a, loop_nest);
4011 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4012 compute_self_dependence (ddr);
4016 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4017 true if STMT clobbers memory, false otherwise. */
4020 get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
4022 bool clobbers_memory = false;
4025 enum gimple_code stmt_code = gimple_code (stmt);
4029 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4030 Calls have side-effects, except those to const or pure
4032 if ((stmt_code == GIMPLE_CALL
4033 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
4034 || (stmt_code == GIMPLE_ASM
4035 && gimple_asm_volatile_p (stmt)))
4036 clobbers_memory = true;
4038 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
4039 return clobbers_memory;
4041 if (stmt_code == GIMPLE_ASSIGN)
4044 op0 = gimple_assign_lhs_ptr (stmt);
4045 op1 = gimple_assign_rhs1_ptr (stmt);
4048 || (REFERENCE_CLASS_P (*op1)
4049 && (base = get_base_address (*op1))
4050 && TREE_CODE (base) != SSA_NAME))
4052 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4054 ref->is_read = true;
4058 || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4060 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4062 ref->is_read = false;
4065 else if (stmt_code == GIMPLE_CALL)
4067 unsigned i, n = gimple_call_num_args (stmt);
4069 for (i = 0; i < n; i++)
4071 op0 = gimple_call_arg_ptr (stmt, i);
4074 || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4076 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4078 ref->is_read = true;
4083 return clobbers_memory;
4086 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4087 reference, returns false, otherwise returns true. NEST is the outermost
4088 loop of the loop nest in which the references should be analyzed. */
4091 find_data_references_in_stmt (struct loop *nest, gimple stmt,
4092 VEC (data_reference_p, heap) **datarefs)
4095 VEC (data_ref_loc, heap) *references;
4098 data_reference_p dr;
4100 if (get_references_in_stmt (stmt, &references))
4102 VEC_free (data_ref_loc, heap, references);
4106 for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4108 dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
4109 gcc_assert (dr != NULL);
4111 /* FIXME -- data dependence analysis does not work correctly for objects with
4112 invariant addresses. Let us fail here until the problem is fixed. */
4113 if (dr_address_invariant_p (dr))
4116 if (dump_file && (dump_flags & TDF_DETAILS))
4117 fprintf (dump_file, "\tFAILED as dr address is invariant\n");
4122 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4124 VEC_free (data_ref_loc, heap, references);
4128 /* Search the data references in LOOP, and record the information into
4129 DATAREFS. Returns chrec_dont_know when failing to analyze a
4130 difficult case, returns NULL_TREE otherwise.
4132 TODO: This function should be made smarter so that it can handle address
4133 arithmetic as if they were array accesses, etc. */
4136 find_data_references_in_loop (struct loop *loop,
4137 VEC (data_reference_p, heap) **datarefs)
4139 basic_block bb, *bbs;
4141 gimple_stmt_iterator bsi;
4143 bbs = get_loop_body_in_dom_order (loop);
4145 for (i = 0; i < loop->num_nodes; i++)
4149 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4151 gimple stmt = gsi_stmt (bsi);
4153 if (!find_data_references_in_stmt (loop, stmt, datarefs))
4155 struct data_reference *res;
4156 res = XCNEW (struct data_reference);
4157 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4160 return chrec_dont_know;
4169 /* Recursive helper function. */
4172 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4174 /* Inner loops of the nest should not contain siblings. Example:
4175 when there are two consecutive loops,
4186 the dependence relation cannot be captured by the distance
4191 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4193 return find_loop_nest_1 (loop->inner, loop_nest);
4197 /* Return false when the LOOP is not well nested. Otherwise return
4198 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4199 contain the loops from the outermost to the innermost, as they will
4200 appear in the classic distance vector. */
4203 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4205 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4207 return find_loop_nest_1 (loop->inner, loop_nest);
4211 /* Returns true when the data dependences have been computed, false otherwise.
4212 Given a loop nest LOOP, the following vectors are returned:
4213 DATAREFS is initialized to all the array elements contained in this loop,
4214 DEPENDENCE_RELATIONS contains the relations between the data references.
4215 Compute read-read and self relations if
4216 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4219 compute_data_dependences_for_loop (struct loop *loop,
4220 bool compute_self_and_read_read_dependences,
4221 VEC (data_reference_p, heap) **datarefs,
4222 VEC (ddr_p, heap) **dependence_relations)
4225 VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4227 memset (&dependence_stats, 0, sizeof (dependence_stats));
4229 /* If the loop nest is not well formed, or one of the data references
4230 is not computable, give up without spending time to compute other
4233 || !find_loop_nest (loop, &vloops)
4234 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4236 struct data_dependence_relation *ddr;
4238 /* Insert a single relation into dependence_relations:
4240 ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4241 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4245 compute_all_dependences (*datarefs, dependence_relations, vloops,
4246 compute_self_and_read_read_dependences);
4248 if (dump_file && (dump_flags & TDF_STATS))
4250 fprintf (dump_file, "Dependence tester statistics:\n");
4252 fprintf (dump_file, "Number of dependence tests: %d\n",
4253 dependence_stats.num_dependence_tests);
4254 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4255 dependence_stats.num_dependence_dependent);
4256 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4257 dependence_stats.num_dependence_independent);
4258 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4259 dependence_stats.num_dependence_undetermined);
4261 fprintf (dump_file, "Number of subscript tests: %d\n",
4262 dependence_stats.num_subscript_tests);
4263 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4264 dependence_stats.num_subscript_undetermined);
4265 fprintf (dump_file, "Number of same subscript function: %d\n",
4266 dependence_stats.num_same_subscript_function);
4268 fprintf (dump_file, "Number of ziv tests: %d\n",
4269 dependence_stats.num_ziv);
4270 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4271 dependence_stats.num_ziv_dependent);
4272 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4273 dependence_stats.num_ziv_independent);
4274 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4275 dependence_stats.num_ziv_unimplemented);
4277 fprintf (dump_file, "Number of siv tests: %d\n",
4278 dependence_stats.num_siv);
4279 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4280 dependence_stats.num_siv_dependent);
4281 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4282 dependence_stats.num_siv_independent);
4283 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4284 dependence_stats.num_siv_unimplemented);
4286 fprintf (dump_file, "Number of miv tests: %d\n",
4287 dependence_stats.num_miv);
4288 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4289 dependence_stats.num_miv_dependent);
4290 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4291 dependence_stats.num_miv_independent);
4292 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4293 dependence_stats.num_miv_unimplemented);
4299 /* Entry point (for testing only). Analyze all the data references
4300 and the dependence relations in LOOP.
4302 The data references are computed first.
4304 A relation on these nodes is represented by a complete graph. Some
4305 of the relations could be of no interest, thus the relations can be
4308 In the following function we compute all the relations. This is
4309 just a first implementation that is here for:
4310 - for showing how to ask for the dependence relations,
4311 - for the debugging the whole dependence graph,
4312 - for the dejagnu testcases and maintenance.
4314 It is possible to ask only for a part of the graph, avoiding to
4315 compute the whole dependence graph. The computed dependences are
4316 stored in a knowledge base (KB) such that later queries don't
4317 recompute the same information. The implementation of this KB is
4318 transparent to the optimizer, and thus the KB can be changed with a
4319 more efficient implementation, or the KB could be disabled. */
4321 analyze_all_data_dependences (struct loop *loop)
4324 int nb_data_refs = 10;
4325 VEC (data_reference_p, heap) *datarefs =
4326 VEC_alloc (data_reference_p, heap, nb_data_refs);
4327 VEC (ddr_p, heap) *dependence_relations =
4328 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4330 /* Compute DDs on the whole function. */
4331 compute_data_dependences_for_loop (loop, false, &datarefs,
4332 &dependence_relations);
4336 dump_data_dependence_relations (dump_file, dependence_relations);
4337 fprintf (dump_file, "\n\n");
4339 if (dump_flags & TDF_DETAILS)
4340 dump_dist_dir_vectors (dump_file, dependence_relations);
4342 if (dump_flags & TDF_STATS)
4344 unsigned nb_top_relations = 0;
4345 unsigned nb_bot_relations = 0;
4346 unsigned nb_basename_differ = 0;
4347 unsigned nb_chrec_relations = 0;
4348 struct data_dependence_relation *ddr;
4350 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4352 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4355 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4357 struct data_reference *a = DDR_A (ddr);
4358 struct data_reference *b = DDR_B (ddr);
4360 if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
4361 nb_basename_differ++;
4367 nb_chrec_relations++;
4370 gather_stats_on_scev_database ();
4374 free_dependence_relations (dependence_relations);
4375 free_data_refs (datarefs);
4378 /* Computes all the data dependences and check that the results of
4379 several analyzers are the same. */
4382 tree_check_data_deps (void)
4385 struct loop *loop_nest;
4387 FOR_EACH_LOOP (li, loop_nest, 0)
4388 analyze_all_data_dependences (loop_nest);
4391 /* Free the memory used by a data dependence relation DDR. */
4394 free_dependence_relation (struct data_dependence_relation *ddr)
4399 if (DDR_SUBSCRIPTS (ddr))
4400 free_subscripts (DDR_SUBSCRIPTS (ddr));
4401 if (DDR_DIST_VECTS (ddr))
4402 VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
4403 if (DDR_DIR_VECTS (ddr))
4404 VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
4409 /* Free the memory used by the data dependence relations from
4410 DEPENDENCE_RELATIONS. */
4413 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4416 struct data_dependence_relation *ddr;
4417 VEC (loop_p, heap) *loop_nest = NULL;
4419 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4423 if (loop_nest == NULL)
4424 loop_nest = DDR_LOOP_NEST (ddr);
4426 gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4427 || DDR_LOOP_NEST (ddr) == loop_nest);
4428 free_dependence_relation (ddr);
4432 VEC_free (loop_p, heap, loop_nest);
4433 VEC_free (ddr_p, heap, dependence_relations);
4436 /* Free the memory used by the data references from DATAREFS. */
4439 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4442 struct data_reference *dr;
4444 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4446 VEC_free (data_reference_p, heap, datarefs);
4451 /* Dump vertex I in RDG to FILE. */
4454 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
4456 struct vertex *v = &(rdg->vertices[i]);
4457 struct graph_edge *e;
4459 fprintf (file, "(vertex %d: (%s%s) (in:", i,
4460 RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
4461 RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
4464 for (e = v->pred; e; e = e->pred_next)
4465 fprintf (file, " %d", e->src);
4467 fprintf (file, ") (out:");
4470 for (e = v->succ; e; e = e->succ_next)
4471 fprintf (file, " %d", e->dest);
4473 fprintf (file, ") \n");
4474 print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
4475 fprintf (file, ")\n");
4478 /* Call dump_rdg_vertex on stderr. */
4481 debug_rdg_vertex (struct graph *rdg, int i)
4483 dump_rdg_vertex (stderr, rdg, i);
4486 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4487 dumped vertices to that bitmap. */
4489 void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
4493 fprintf (file, "(%d\n", c);
4495 for (i = 0; i < rdg->n_vertices; i++)
4496 if (rdg->vertices[i].component == c)
4499 bitmap_set_bit (dumped, i);
4501 dump_rdg_vertex (file, rdg, i);
4504 fprintf (file, ")\n");
4507 /* Call dump_rdg_vertex on stderr. */
4510 debug_rdg_component (struct graph *rdg, int c)
4512 dump_rdg_component (stderr, rdg, c, NULL);
4515 /* Dump the reduced dependence graph RDG to FILE. */
4518 dump_rdg (FILE *file, struct graph *rdg)
4521 bitmap dumped = BITMAP_ALLOC (NULL);
4523 fprintf (file, "(rdg\n");
4525 for (i = 0; i < rdg->n_vertices; i++)
4526 if (!bitmap_bit_p (dumped, i))
4527 dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
4529 fprintf (file, ")\n");
4530 BITMAP_FREE (dumped);
4533 /* Call dump_rdg on stderr. */
4536 debug_rdg (struct graph *rdg)
4538 dump_rdg (stderr, rdg);
4542 dot_rdg_1 (FILE *file, struct graph *rdg)
4546 fprintf (file, "digraph RDG {\n");
4548 for (i = 0; i < rdg->n_vertices; i++)
4550 struct vertex *v = &(rdg->vertices[i]);
4551 struct graph_edge *e;
4553 /* Highlight reads from memory. */
4554 if (RDG_MEM_READS_STMT (rdg, i))
4555 fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
4557 /* Highlight stores to memory. */
4558 if (RDG_MEM_WRITE_STMT (rdg, i))
4559 fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
4562 for (e = v->succ; e; e = e->succ_next)
4563 switch (RDGE_TYPE (e))
4566 fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
4570 fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
4574 /* These are the most common dependences: don't print these. */
4575 fprintf (file, "%d -> %d \n", i, e->dest);
4579 fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
4587 fprintf (file, "}\n\n");
4590 /* Display SCOP using dotty. */
4593 dot_rdg (struct graph *rdg)
4595 FILE *file = fopen ("/tmp/rdg.dot", "w");
4596 gcc_assert (file != NULL);
4598 dot_rdg_1 (file, rdg);
4601 system ("dotty /tmp/rdg.dot");
4605 /* This structure is used for recording the mapping statement index in
4608 struct rdg_vertex_info GTY(())
4614 /* Returns the index of STMT in RDG. */
4617 rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
4619 struct rdg_vertex_info rvi, *slot;
4622 slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
4630 /* Creates an edge in RDG for each distance vector from DDR. The
4631 order that we keep track of in the RDG is the order in which
4632 statements have to be executed. */
4635 create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
4637 struct graph_edge *e;
4639 data_reference_p dra = DDR_A (ddr);
4640 data_reference_p drb = DDR_B (ddr);
4641 unsigned level = ddr_dependence_level (ddr);
4643 /* For non scalar dependences, when the dependence is REVERSED,
4644 statement B has to be executed before statement A. */
4646 && !DDR_REVERSED_P (ddr))
4648 data_reference_p tmp = dra;
4653 va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
4654 vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
4656 if (va < 0 || vb < 0)
4659 e = add_edge (rdg, va, vb);
4660 e->data = XNEW (struct rdg_edge);
4662 RDGE_LEVEL (e) = level;
4663 RDGE_RELATION (e) = ddr;
4665 /* Determines the type of the data dependence. */
4666 if (DR_IS_READ (dra) && DR_IS_READ (drb))
4667 RDGE_TYPE (e) = input_dd;
4668 else if (!DR_IS_READ (dra) && !DR_IS_READ (drb))
4669 RDGE_TYPE (e) = output_dd;
4670 else if (!DR_IS_READ (dra) && DR_IS_READ (drb))
4671 RDGE_TYPE (e) = flow_dd;
4672 else if (DR_IS_READ (dra) && !DR_IS_READ (drb))
4673 RDGE_TYPE (e) = anti_dd;
4676 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4677 the index of DEF in RDG. */
4680 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
4682 use_operand_p imm_use_p;
4683 imm_use_iterator iterator;
4685 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
4687 struct graph_edge *e;
4688 int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
4693 e = add_edge (rdg, idef, use);
4694 e->data = XNEW (struct rdg_edge);
4695 RDGE_TYPE (e) = flow_dd;
4696 RDGE_RELATION (e) = NULL;
4700 /* Creates the edges of the reduced dependence graph RDG. */
4703 create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
4706 struct data_dependence_relation *ddr;
4707 def_operand_p def_p;
4710 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
4711 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4712 create_rdg_edge_for_ddr (rdg, ddr);
4714 for (i = 0; i < rdg->n_vertices; i++)
4715 FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
4717 create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
4720 /* Build the vertices of the reduced dependence graph RDG. */
4723 create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
4728 for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++)
4730 VEC (data_ref_loc, heap) *references;
4732 struct vertex *v = &(rdg->vertices[i]);
4733 struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
4734 struct rdg_vertex_info **slot;
4738 slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
4745 v->data = XNEW (struct rdg_vertex);
4746 RDG_STMT (rdg, i) = stmt;
4748 RDG_MEM_WRITE_STMT (rdg, i) = false;
4749 RDG_MEM_READS_STMT (rdg, i) = false;
4750 if (gimple_code (stmt) == GIMPLE_PHI)
4753 get_references_in_stmt (stmt, &references);
4754 for (j = 0; VEC_iterate (data_ref_loc, references, j, ref); j++)
4756 RDG_MEM_WRITE_STMT (rdg, i) = true;
4758 RDG_MEM_READS_STMT (rdg, i) = true;
4760 VEC_free (data_ref_loc, heap, references);
4764 /* Initialize STMTS with all the statements of LOOP. When
4765 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4766 which we discover statements is important as
4767 generate_loops_for_partition is using the same traversal for
4768 identifying statements. */
4771 stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
4774 basic_block *bbs = get_loop_body_in_dom_order (loop);
4776 for (i = 0; i < loop->num_nodes; i++)
4778 basic_block bb = bbs[i];
4779 gimple_stmt_iterator bsi;
4782 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4783 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
4785 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4787 stmt = gsi_stmt (bsi);
4788 if (gimple_code (stmt) != GIMPLE_LABEL)
4789 VEC_safe_push (gimple, heap, *stmts, stmt);
4796 /* Returns true when all the dependences are computable. */
4799 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
4804 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4805 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4811 /* Computes a hash function for element ELT. */
4814 hash_stmt_vertex_info (const void *elt)
4816 const struct rdg_vertex_info *const rvi =
4817 (const struct rdg_vertex_info *) elt;
4818 gimple stmt = rvi->stmt;
4820 return htab_hash_pointer (stmt);
4823 /* Compares database elements E1 and E2. */
4826 eq_stmt_vertex_info (const void *e1, const void *e2)
4828 const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
4829 const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
4831 return elt1->stmt == elt2->stmt;
4834 /* Free the element E. */
4837 hash_stmt_vertex_del (void *e)
4842 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4843 statement of the loop nest, and one edge per data dependence or
4844 scalar dependence. */
4847 build_empty_rdg (int n_stmts)
4849 int nb_data_refs = 10;
4850 struct graph *rdg = new_graph (n_stmts);
4852 rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
4853 eq_stmt_vertex_info, hash_stmt_vertex_del);
4857 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4858 statement of the loop nest, and one edge per data dependence or
4859 scalar dependence. */
4862 build_rdg (struct loop *loop)
4864 int nb_data_refs = 10;
4865 struct graph *rdg = NULL;
4866 VEC (ddr_p, heap) *dependence_relations;
4867 VEC (data_reference_p, heap) *datarefs;
4868 VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs);
4870 dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
4871 datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
4872 compute_data_dependences_for_loop (loop,
4875 &dependence_relations);
4877 if (!known_dependences_p (dependence_relations))
4879 free_dependence_relations (dependence_relations);
4880 free_data_refs (datarefs);
4881 VEC_free (gimple, heap, stmts);
4886 stmts_from_loop (loop, &stmts);
4887 rdg = build_empty_rdg (VEC_length (gimple, stmts));
4889 rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
4890 eq_stmt_vertex_info, hash_stmt_vertex_del);
4891 create_rdg_vertices (rdg, stmts);
4892 create_rdg_edges (rdg, dependence_relations);
4894 VEC_free (gimple, heap, stmts);
4898 /* Free the reduced dependence graph RDG. */
4901 free_rdg (struct graph *rdg)
4905 for (i = 0; i < rdg->n_vertices; i++)
4906 free (rdg->vertices[i].data);
4908 htab_delete (rdg->indices);
4912 /* Initialize STMTS with all the statements of LOOP that contain a
4916 stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
4919 basic_block *bbs = get_loop_body_in_dom_order (loop);
4921 for (i = 0; i < loop->num_nodes; i++)
4923 basic_block bb = bbs[i];
4924 gimple_stmt_iterator bsi;
4926 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4927 if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi), SSA_OP_VDEF))
4928 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
4934 /* For a data reference REF, return the declaration of its base
4935 address or NULL_TREE if the base is not determined. */
4938 ref_base_address (gimple stmt, data_ref_loc *ref)
4940 tree base = NULL_TREE;
4942 struct data_reference *dr = XCNEW (struct data_reference);
4944 DR_STMT (dr) = stmt;
4945 DR_REF (dr) = *ref->pos;
4946 dr_analyze_innermost (dr);
4947 base_address = DR_BASE_ADDRESS (dr);
4952 switch (TREE_CODE (base_address))
4955 base = TREE_OPERAND (base_address, 0);
4959 base = base_address;
4968 /* Determines whether the statement from vertex V of the RDG has a
4969 definition used outside the loop that contains this statement. */
4972 rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
4974 gimple stmt = RDG_STMT (rdg, v);
4975 struct loop *loop = loop_containing_stmt (stmt);
4976 use_operand_p imm_use_p;
4977 imm_use_iterator iterator;
4979 def_operand_p def_p;
4984 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
4986 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
4988 if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
4996 /* Determines whether statements S1 and S2 access to similar memory
4997 locations. Two memory accesses are considered similar when they
4998 have the same base address declaration, i.e. when their
4999 ref_base_address is the same. */
5002 have_similar_memory_accesses (gimple s1, gimple s2)
5006 VEC (data_ref_loc, heap) *refs1, *refs2;
5007 data_ref_loc *ref1, *ref2;
5009 get_references_in_stmt (s1, &refs1);
5010 get_references_in_stmt (s2, &refs2);
5012 for (i = 0; VEC_iterate (data_ref_loc, refs1, i, ref1); i++)
5014 tree base1 = ref_base_address (s1, ref1);
5017 for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++)
5018 if (base1 == ref_base_address (s2, ref2))
5026 VEC_free (data_ref_loc, heap, refs1);
5027 VEC_free (data_ref_loc, heap, refs2);
5031 /* Helper function for the hashtab. */
5034 have_similar_memory_accesses_1 (const void *s1, const void *s2)
5036 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1),
5037 CONST_CAST_GIMPLE ((const_gimple) s2));
5040 /* Helper function for the hashtab. */
5043 ref_base_address_1 (const void *s)
5045 gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s);
5047 VEC (data_ref_loc, heap) *refs;
5051 get_references_in_stmt (stmt, &refs);
5053 for (i = 0; VEC_iterate (data_ref_loc, refs, i, ref); i++)
5056 res = htab_hash_pointer (ref_base_address (stmt, ref));
5060 VEC_free (data_ref_loc, heap, refs);
5064 /* Try to remove duplicated write data references from STMTS. */
5067 remove_similar_memory_refs (VEC (gimple, heap) **stmts)
5071 htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1,
5072 have_similar_memory_accesses_1, NULL);
5074 for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); )
5078 slot = htab_find_slot (seen, stmt, INSERT);
5081 VEC_ordered_remove (gimple, *stmts, i);
5084 *slot = (void *) stmt;
5092 /* Returns the index of PARAMETER in the parameters vector of the
5093 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5096 access_matrix_get_index_for_parameter (tree parameter,
5097 struct access_matrix *access_matrix)
5100 VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
5101 tree lambda_parameter;
5103 for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++)
5104 if (lambda_parameter == parameter)
5105 return i + AM_NB_INDUCTION_VARS (access_matrix);