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 (TREE_CODE (var0) == NOP_EXPR
585 || TREE_CODE (var0) == CONVERT_EXPR)
587 gimplify_conversion (&var0);
588 // Attempt to fill in any within var0 found ARRAY_REF's
589 // element size from corresponding op embedded ARRAY_REF,
590 // if unsuccessful, just punt.
592 while (POINTER_TYPE_P (type))
593 type = TREE_TYPE (type);
594 if (int_size_in_bytes (type) < 0)
604 gimple def_stmt = SSA_NAME_DEF_STMT (op0);
605 enum tree_code subcode;
607 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
610 var0 = gimple_assign_rhs1 (def_stmt);
611 subcode = gimple_assign_rhs_code (def_stmt);
612 var1 = gimple_assign_rhs2 (def_stmt);
614 return split_constant_offset_1 (type, var0, subcode, var1, var, off);
622 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
623 will be ssizetype. */
626 split_constant_offset (tree exp, tree *var, tree *off)
628 tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
632 *off = ssize_int (0);
635 if (automatically_generated_chrec_p (exp))
638 otype = TREE_TYPE (exp);
639 code = TREE_CODE (exp);
640 extract_ops_from_tree (exp, &code, &op0, &op1);
641 if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
643 *var = fold_convert (type, e);
648 /* Returns the address ADDR of an object in a canonical shape (without nop
649 casts, and with type of pointer to the object). */
652 canonicalize_base_object_address (tree addr)
658 /* The base address may be obtained by casting from integer, in that case
660 if (!POINTER_TYPE_P (TREE_TYPE (addr)))
663 if (TREE_CODE (addr) != ADDR_EXPR)
666 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
669 /* Analyzes the behavior of the memory reference DR in the innermost loop that
673 dr_analyze_innermost (struct data_reference *dr)
675 gimple stmt = DR_STMT (dr);
676 struct loop *loop = loop_containing_stmt (stmt);
677 tree ref = DR_REF (dr);
678 HOST_WIDE_INT pbitsize, pbitpos;
680 enum machine_mode pmode;
681 int punsignedp, pvolatilep;
682 affine_iv base_iv, offset_iv;
683 tree init, dinit, step;
685 if (dump_file && (dump_flags & TDF_DETAILS))
686 fprintf (dump_file, "analyze_innermost: ");
688 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
689 &pmode, &punsignedp, &pvolatilep, false);
690 gcc_assert (base != NULL_TREE);
692 if (pbitpos % BITS_PER_UNIT != 0)
694 if (dump_file && (dump_flags & TDF_DETAILS))
695 fprintf (dump_file, "failed: bit offset alignment.\n");
699 base = build_fold_addr_expr (base);
700 if (!simple_iv (loop, stmt, base, &base_iv, false))
702 if (dump_file && (dump_flags & TDF_DETAILS))
703 fprintf (dump_file, "failed: evolution of base is not affine.\n");
708 offset_iv.base = ssize_int (0);
709 offset_iv.step = ssize_int (0);
711 else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
713 if (dump_file && (dump_flags & TDF_DETAILS))
714 fprintf (dump_file, "failed: evolution of offset is not affine.\n");
718 init = ssize_int (pbitpos / BITS_PER_UNIT);
719 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
720 init = size_binop (PLUS_EXPR, init, dinit);
721 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
722 init = size_binop (PLUS_EXPR, init, dinit);
724 step = size_binop (PLUS_EXPR,
725 fold_convert (ssizetype, base_iv.step),
726 fold_convert (ssizetype, offset_iv.step));
728 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
730 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
734 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
736 if (dump_file && (dump_flags & TDF_DETAILS))
737 fprintf (dump_file, "success.\n");
740 /* Determines the base object and the list of indices of memory reference
741 DR, analyzed in loop nest NEST. */
744 dr_analyze_indices (struct data_reference *dr, struct loop *nest)
746 gimple stmt = DR_STMT (dr);
747 struct loop *loop = loop_containing_stmt (stmt);
748 VEC (tree, heap) *access_fns = NULL;
749 tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
750 tree base, off, access_fn;
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 (nest, 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 (nest, 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 /* Initializes an equation for an OMEGA problem using the information
3308 contained in the ACCESS_FUN. Returns true when the operation
3311 PB is the omega constraint system.
3312 EQ is the number of the equation to be initialized.
3313 OFFSET is used for shifting the variables names in the constraints:
3314 a constrain is composed of 2 * the number of variables surrounding
3315 dependence accesses. OFFSET is set either to 0 for the first n variables,
3316 then it is set to n.
3317 ACCESS_FUN is expected to be an affine chrec. */
3320 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3321 unsigned int offset, tree access_fun,
3322 struct data_dependence_relation *ddr)
3324 switch (TREE_CODE (access_fun))
3326 case POLYNOMIAL_CHREC:
3328 tree left = CHREC_LEFT (access_fun);
3329 tree right = CHREC_RIGHT (access_fun);
3330 int var = CHREC_VARIABLE (access_fun);
3333 if (TREE_CODE (right) != INTEGER_CST)
3336 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3337 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3339 /* Compute the innermost loop index. */
3340 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3343 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3344 += int_cst_value (right);
3346 switch (TREE_CODE (left))
3348 case POLYNOMIAL_CHREC:
3349 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3352 pb->eqs[eq].coef[0] += int_cst_value (left);
3361 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3369 /* As explained in the comments preceding init_omega_for_ddr, we have
3370 to set up a system for each loop level, setting outer loops
3371 variation to zero, and current loop variation to positive or zero.
3372 Save each lexico positive distance vector. */
3375 omega_extract_distance_vectors (omega_pb pb,
3376 struct data_dependence_relation *ddr)
3380 struct loop *loopi, *loopj;
3381 enum omega_result res;
3383 /* Set a new problem for each loop in the nest. The basis is the
3384 problem that we have initialized until now. On top of this we
3385 add new constraints. */
3386 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3387 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3390 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3391 DDR_NB_LOOPS (ddr));
3393 omega_copy_problem (copy, pb);
3395 /* For all the outer loops "loop_j", add "dj = 0". */
3397 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3399 eq = omega_add_zero_eq (copy, omega_black);
3400 copy->eqs[eq].coef[j + 1] = 1;
3403 /* For "loop_i", add "0 <= di". */
3404 geq = omega_add_zero_geq (copy, omega_black);
3405 copy->geqs[geq].coef[i + 1] = 1;
3407 /* Reduce the constraint system, and test that the current
3408 problem is feasible. */
3409 res = omega_simplify_problem (copy);
3410 if (res == omega_false
3411 || res == omega_unknown
3412 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3415 for (eq = 0; eq < copy->num_subs; eq++)
3416 if (copy->subs[eq].key == (int) i + 1)
3418 dist = copy->subs[eq].coef[0];
3424 /* Reinitialize problem... */
3425 omega_copy_problem (copy, pb);
3427 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3429 eq = omega_add_zero_eq (copy, omega_black);
3430 copy->eqs[eq].coef[j + 1] = 1;
3433 /* ..., but this time "di = 1". */
3434 eq = omega_add_zero_eq (copy, omega_black);
3435 copy->eqs[eq].coef[i + 1] = 1;
3436 copy->eqs[eq].coef[0] = -1;
3438 res = omega_simplify_problem (copy);
3439 if (res == omega_false
3440 || res == omega_unknown
3441 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3444 for (eq = 0; eq < copy->num_subs; eq++)
3445 if (copy->subs[eq].key == (int) i + 1)
3447 dist = copy->subs[eq].coef[0];
3453 /* Save the lexicographically positive distance vector. */
3456 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3457 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3461 for (eq = 0; eq < copy->num_subs; eq++)
3462 if (copy->subs[eq].key > 0)
3464 dist = copy->subs[eq].coef[0];
3465 dist_v[copy->subs[eq].key - 1] = dist;
3468 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3469 dir_v[j] = dir_from_dist (dist_v[j]);
3471 save_dist_v (ddr, dist_v);
3472 save_dir_v (ddr, dir_v);
3476 omega_free_problem (copy);
3480 /* This is called for each subscript of a tuple of data references:
3481 insert an equality for representing the conflicts. */
3484 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3485 struct data_dependence_relation *ddr,
3486 omega_pb pb, bool *maybe_dependent)
3489 tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3490 TREE_TYPE (access_fun_b));
3491 tree fun_a = chrec_convert (type, access_fun_a, NULL);
3492 tree fun_b = chrec_convert (type, access_fun_b, NULL);
3493 tree difference = chrec_fold_minus (type, fun_a, fun_b);
3495 /* When the fun_a - fun_b is not constant, the dependence is not
3496 captured by the classic distance vector representation. */
3497 if (TREE_CODE (difference) != INTEGER_CST)
3501 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3503 /* There is no dependence. */
3504 *maybe_dependent = false;
3508 fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
3510 eq = omega_add_zero_eq (pb, omega_black);
3511 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3512 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3513 /* There is probably a dependence, but the system of
3514 constraints cannot be built: answer "don't know". */
3518 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3519 && !int_divides_p (lambda_vector_gcd
3520 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3521 2 * DDR_NB_LOOPS (ddr)),
3522 pb->eqs[eq].coef[0]))
3524 /* There is no dependence. */
3525 *maybe_dependent = false;
3532 /* Helper function, same as init_omega_for_ddr but specialized for
3533 data references A and B. */
3536 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3537 struct data_dependence_relation *ddr,
3538 omega_pb pb, bool *maybe_dependent)
3543 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3545 /* Insert an equality per subscript. */
3546 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3548 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3549 ddr, pb, maybe_dependent))
3551 else if (*maybe_dependent == false)
3553 /* There is no dependence. */
3554 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3559 /* Insert inequalities: constraints corresponding to the iteration
3560 domain, i.e. the loops surrounding the references "loop_x" and
3561 the distance variables "dx". The layout of the OMEGA
3562 representation is as follows:
3563 - coef[0] is the constant
3564 - coef[1..nb_loops] are the protected variables that will not be
3565 removed by the solver: the "dx"
3566 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3568 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3569 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3571 HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
3574 ineq = omega_add_zero_geq (pb, omega_black);
3575 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3577 /* 0 <= loop_x + dx */
3578 ineq = omega_add_zero_geq (pb, omega_black);
3579 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3580 pb->geqs[ineq].coef[i + 1] = 1;
3584 /* loop_x <= nb_iters */
3585 ineq = omega_add_zero_geq (pb, omega_black);
3586 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3587 pb->geqs[ineq].coef[0] = nbi;
3589 /* loop_x + dx <= nb_iters */
3590 ineq = omega_add_zero_geq (pb, omega_black);
3591 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3592 pb->geqs[ineq].coef[i + 1] = -1;
3593 pb->geqs[ineq].coef[0] = nbi;
3595 /* A step "dx" bigger than nb_iters is not feasible, so
3596 add "0 <= nb_iters + dx", */
3597 ineq = omega_add_zero_geq (pb, omega_black);
3598 pb->geqs[ineq].coef[i + 1] = 1;
3599 pb->geqs[ineq].coef[0] = nbi;
3600 /* and "dx <= nb_iters". */
3601 ineq = omega_add_zero_geq (pb, omega_black);
3602 pb->geqs[ineq].coef[i + 1] = -1;
3603 pb->geqs[ineq].coef[0] = nbi;
3607 omega_extract_distance_vectors (pb, ddr);
3612 /* Sets up the Omega dependence problem for the data dependence
3613 relation DDR. Returns false when the constraint system cannot be
3614 built, ie. when the test answers "don't know". Returns true
3615 otherwise, and when independence has been proved (using one of the
3616 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3617 set MAYBE_DEPENDENT to true.
3619 Example: for setting up the dependence system corresponding to the
3620 conflicting accesses
3625 | ... A[2*j, 2*(i + j)]
3629 the following constraints come from the iteration domain:
3636 where di, dj are the distance variables. The constraints
3637 representing the conflicting elements are:
3640 i + 1 = 2 * (i + di + j + dj)
3642 For asking that the resulting distance vector (di, dj) be
3643 lexicographically positive, we insert the constraint "di >= 0". If
3644 "di = 0" in the solution, we fix that component to zero, and we
3645 look at the inner loops: we set a new problem where all the outer
3646 loop distances are zero, and fix this inner component to be
3647 positive. When one of the components is positive, we save that
3648 distance, and set a new problem where the distance on this loop is
3649 zero, searching for other distances in the inner loops. Here is
3650 the classic example that illustrates that we have to set for each
3651 inner loop a new problem:
3659 we have to save two distances (1, 0) and (0, 1).
3661 Given two array references, refA and refB, we have to set the
3662 dependence problem twice, refA vs. refB and refB vs. refA, and we
3663 cannot do a single test, as refB might occur before refA in the
3664 inner loops, and the contrary when considering outer loops: ex.
3669 | T[{1,+,1}_2][{1,+,1}_1] // refA
3670 | T[{2,+,1}_2][{0,+,1}_1] // refB
3675 refB touches the elements in T before refA, and thus for the same
3676 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3677 but for successive loop_0 iterations, we have (1, -1, 1)
3679 The Omega solver expects the distance variables ("di" in the
3680 previous example) to come first in the constraint system (as
3681 variables to be protected, or "safe" variables), the constraint
3682 system is built using the following layout:
3684 "cst | distance vars | index vars".
3688 init_omega_for_ddr (struct data_dependence_relation *ddr,
3689 bool *maybe_dependent)
3694 *maybe_dependent = true;
3696 if (same_access_functions (ddr))
3699 lambda_vector dir_v;
3701 /* Save the 0 vector. */
3702 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3703 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3704 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3705 dir_v[j] = dir_equal;
3706 save_dir_v (ddr, dir_v);
3708 /* Save the dependences carried by outer loops. */
3709 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3710 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3712 omega_free_problem (pb);
3716 /* Omega expects the protected variables (those that have to be kept
3717 after elimination) to appear first in the constraint system.
3718 These variables are the distance variables. In the following
3719 initialization we declare NB_LOOPS safe variables, and the total
3720 number of variables for the constraint system is 2*NB_LOOPS. */
3721 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3722 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3724 omega_free_problem (pb);
3726 /* Stop computation if not decidable, or no dependence. */
3727 if (res == false || *maybe_dependent == false)
3730 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3731 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3733 omega_free_problem (pb);
3738 /* Return true when DDR contains the same information as that stored
3739 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3742 ddr_consistent_p (FILE *file,
3743 struct data_dependence_relation *ddr,
3744 VEC (lambda_vector, heap) *dist_vects,
3745 VEC (lambda_vector, heap) *dir_vects)
3749 /* If dump_file is set, output there. */
3750 if (dump_file && (dump_flags & TDF_DETAILS))
3753 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3755 lambda_vector b_dist_v;
3756 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3757 VEC_length (lambda_vector, dist_vects),
3758 DDR_NUM_DIST_VECTS (ddr));
3760 fprintf (file, "Banerjee dist vectors:\n");
3761 for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
3762 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3764 fprintf (file, "Omega dist vectors:\n");
3765 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3766 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3768 fprintf (file, "data dependence relation:\n");
3769 dump_data_dependence_relation (file, ddr);
3771 fprintf (file, ")\n");
3775 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3777 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3778 VEC_length (lambda_vector, dir_vects),
3779 DDR_NUM_DIR_VECTS (ddr));
3783 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3785 lambda_vector a_dist_v;
3786 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3788 /* Distance vectors are not ordered in the same way in the DDR
3789 and in the DIST_VECTS: search for a matching vector. */
3790 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
3791 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3794 if (j == VEC_length (lambda_vector, dist_vects))
3796 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3797 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3798 fprintf (file, "not found in Omega dist vectors:\n");
3799 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3800 fprintf (file, "data dependence relation:\n");
3801 dump_data_dependence_relation (file, ddr);
3802 fprintf (file, ")\n");
3806 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3808 lambda_vector a_dir_v;
3809 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3811 /* Direction vectors are not ordered in the same way in the DDR
3812 and in the DIR_VECTS: search for a matching vector. */
3813 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
3814 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3817 if (j == VEC_length (lambda_vector, dist_vects))
3819 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3820 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3821 fprintf (file, "not found in Omega dir vectors:\n");
3822 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3823 fprintf (file, "data dependence relation:\n");
3824 dump_data_dependence_relation (file, ddr);
3825 fprintf (file, ")\n");
3832 /* This computes the affine dependence relation between A and B with
3833 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3834 independence between two accesses, while CHREC_DONT_KNOW is used
3835 for representing the unknown relation.
3837 Note that it is possible to stop the computation of the dependence
3838 relation the first time we detect a CHREC_KNOWN element for a given
3842 compute_affine_dependence (struct data_dependence_relation *ddr,
3843 struct loop *loop_nest)
3845 struct data_reference *dra = DDR_A (ddr);
3846 struct data_reference *drb = DDR_B (ddr);
3848 if (dump_file && (dump_flags & TDF_DETAILS))
3850 fprintf (dump_file, "(compute_affine_dependence\n");
3851 fprintf (dump_file, " (stmt_a = \n");
3852 print_gimple_stmt (dump_file, DR_STMT (dra), 0, 0);
3853 fprintf (dump_file, ")\n (stmt_b = \n");
3854 print_gimple_stmt (dump_file, DR_STMT (drb), 0, 0);
3855 fprintf (dump_file, ")\n");
3858 /* Analyze only when the dependence relation is not yet known. */
3859 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
3860 && !DDR_SELF_REFERENCE (ddr))
3862 dependence_stats.num_dependence_tests++;
3864 if (access_functions_are_affine_or_constant_p (dra, loop_nest)
3865 && access_functions_are_affine_or_constant_p (drb, loop_nest))
3867 if (flag_check_data_deps)
3869 /* Compute the dependences using the first algorithm. */
3870 subscript_dependence_tester (ddr, loop_nest);
3872 if (dump_file && (dump_flags & TDF_DETAILS))
3874 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3875 dump_data_dependence_relation (dump_file, ddr);
3878 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3880 bool maybe_dependent;
3881 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3883 /* Save the result of the first DD analyzer. */
3884 dist_vects = DDR_DIST_VECTS (ddr);
3885 dir_vects = DDR_DIR_VECTS (ddr);
3887 /* Reset the information. */
3888 DDR_DIST_VECTS (ddr) = NULL;
3889 DDR_DIR_VECTS (ddr) = NULL;
3891 /* Compute the same information using Omega. */
3892 if (!init_omega_for_ddr (ddr, &maybe_dependent))
3893 goto csys_dont_know;
3895 if (dump_file && (dump_flags & TDF_DETAILS))
3897 fprintf (dump_file, "Omega Analyzer\n");
3898 dump_data_dependence_relation (dump_file, ddr);
3901 /* Check that we get the same information. */
3902 if (maybe_dependent)
3903 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3908 subscript_dependence_tester (ddr, loop_nest);
3911 /* As a last case, if the dependence cannot be determined, or if
3912 the dependence is considered too difficult to determine, answer
3917 dependence_stats.num_dependence_undetermined++;
3919 if (dump_file && (dump_flags & TDF_DETAILS))
3921 fprintf (dump_file, "Data ref a:\n");
3922 dump_data_reference (dump_file, dra);
3923 fprintf (dump_file, "Data ref b:\n");
3924 dump_data_reference (dump_file, drb);
3925 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3927 finalize_ddr_dependent (ddr, chrec_dont_know);
3931 if (dump_file && (dump_flags & TDF_DETAILS))
3932 fprintf (dump_file, ")\n");
3935 /* This computes the dependence relation for the same data
3936 reference into DDR. */
3939 compute_self_dependence (struct data_dependence_relation *ddr)
3942 struct subscript *subscript;
3944 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3947 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3950 if (SUB_CONFLICTS_IN_A (subscript))
3951 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3952 if (SUB_CONFLICTS_IN_B (subscript))
3953 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3955 /* The accessed index overlaps for each iteration. */
3956 SUB_CONFLICTS_IN_A (subscript)
3957 = conflict_fn (1, affine_fn_cst (integer_zero_node));
3958 SUB_CONFLICTS_IN_B (subscript)
3959 = conflict_fn (1, affine_fn_cst (integer_zero_node));
3960 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3963 /* The distance vector is the zero vector. */
3964 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3965 save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3968 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3969 the data references in DATAREFS, in the LOOP_NEST. When
3970 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3974 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3975 VEC (ddr_p, heap) **dependence_relations,
3976 VEC (loop_p, heap) *loop_nest,
3977 bool compute_self_and_rr)
3979 struct data_dependence_relation *ddr;
3980 struct data_reference *a, *b;
3983 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3984 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
3985 if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
3987 ddr = initialize_data_dependence_relation (a, b, loop_nest);
3988 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3989 compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
3992 if (compute_self_and_rr)
3993 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3995 ddr = initialize_data_dependence_relation (a, a, loop_nest);
3996 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3997 compute_self_dependence (ddr);
4001 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4002 true if STMT clobbers memory, false otherwise. */
4005 get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
4007 bool clobbers_memory = false;
4010 enum gimple_code stmt_code = gimple_code (stmt);
4014 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4015 Calls have side-effects, except those to const or pure
4017 if ((stmt_code == GIMPLE_CALL
4018 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
4019 || (stmt_code == GIMPLE_ASM
4020 && gimple_asm_volatile_p (stmt)))
4021 clobbers_memory = true;
4023 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
4024 return clobbers_memory;
4026 if (stmt_code == GIMPLE_ASSIGN)
4029 op0 = gimple_assign_lhs_ptr (stmt);
4030 op1 = gimple_assign_rhs1_ptr (stmt);
4033 || (REFERENCE_CLASS_P (*op1)
4034 && (base = get_base_address (*op1))
4035 && TREE_CODE (base) != SSA_NAME))
4037 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4039 ref->is_read = true;
4043 || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4045 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4047 ref->is_read = false;
4050 else if (stmt_code == GIMPLE_CALL)
4052 unsigned i, n = gimple_call_num_args (stmt);
4054 for (i = 0; i < n; i++)
4056 op0 = gimple_call_arg_ptr (stmt, i);
4059 || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4061 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4063 ref->is_read = true;
4068 return clobbers_memory;
4071 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4072 reference, returns false, otherwise returns true. NEST is the outermost
4073 loop of the loop nest in that the references should be analyzed. */
4076 find_data_references_in_stmt (struct loop *nest, gimple stmt,
4077 VEC (data_reference_p, heap) **datarefs)
4080 VEC (data_ref_loc, heap) *references;
4083 data_reference_p dr;
4085 if (get_references_in_stmt (stmt, &references))
4087 VEC_free (data_ref_loc, heap, references);
4091 for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4093 dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
4094 gcc_assert (dr != NULL);
4096 /* FIXME -- data dependence analysis does not work correctly for objects with
4097 invariant addresses. Let us fail here until the problem is fixed. */
4098 if (dr_address_invariant_p (dr))
4101 if (dump_file && (dump_flags & TDF_DETAILS))
4102 fprintf (dump_file, "\tFAILED as dr address is invariant\n");
4107 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4109 VEC_free (data_ref_loc, heap, references);
4113 /* Search the data references in LOOP, and record the information into
4114 DATAREFS. Returns chrec_dont_know when failing to analyze a
4115 difficult case, returns NULL_TREE otherwise.
4117 TODO: This function should be made smarter so that it can handle address
4118 arithmetic as if they were array accesses, etc. */
4121 find_data_references_in_loop (struct loop *loop,
4122 VEC (data_reference_p, heap) **datarefs)
4124 basic_block bb, *bbs;
4126 gimple_stmt_iterator bsi;
4128 bbs = get_loop_body_in_dom_order (loop);
4130 for (i = 0; i < loop->num_nodes; i++)
4134 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4136 gimple stmt = gsi_stmt (bsi);
4138 if (!find_data_references_in_stmt (loop, stmt, datarefs))
4140 struct data_reference *res;
4141 res = XCNEW (struct data_reference);
4142 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4145 return chrec_dont_know;
4154 /* Recursive helper function. */
4157 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4159 /* Inner loops of the nest should not contain siblings. Example:
4160 when there are two consecutive loops,
4171 the dependence relation cannot be captured by the distance
4176 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4178 return find_loop_nest_1 (loop->inner, loop_nest);
4182 /* Return false when the LOOP is not well nested. Otherwise return
4183 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4184 contain the loops from the outermost to the innermost, as they will
4185 appear in the classic distance vector. */
4188 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4190 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4192 return find_loop_nest_1 (loop->inner, loop_nest);
4196 /* Returns true when the data dependences have been computed, false otherwise.
4197 Given a loop nest LOOP, the following vectors are returned:
4198 DATAREFS is initialized to all the array elements contained in this loop,
4199 DEPENDENCE_RELATIONS contains the relations between the data references.
4200 Compute read-read and self relations if
4201 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4204 compute_data_dependences_for_loop (struct loop *loop,
4205 bool compute_self_and_read_read_dependences,
4206 VEC (data_reference_p, heap) **datarefs,
4207 VEC (ddr_p, heap) **dependence_relations)
4210 VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4212 memset (&dependence_stats, 0, sizeof (dependence_stats));
4214 /* If the loop nest is not well formed, or one of the data references
4215 is not computable, give up without spending time to compute other
4218 || !find_loop_nest (loop, &vloops)
4219 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4221 struct data_dependence_relation *ddr;
4223 /* Insert a single relation into dependence_relations:
4225 ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4226 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4230 compute_all_dependences (*datarefs, dependence_relations, vloops,
4231 compute_self_and_read_read_dependences);
4233 if (dump_file && (dump_flags & TDF_STATS))
4235 fprintf (dump_file, "Dependence tester statistics:\n");
4237 fprintf (dump_file, "Number of dependence tests: %d\n",
4238 dependence_stats.num_dependence_tests);
4239 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4240 dependence_stats.num_dependence_dependent);
4241 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4242 dependence_stats.num_dependence_independent);
4243 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4244 dependence_stats.num_dependence_undetermined);
4246 fprintf (dump_file, "Number of subscript tests: %d\n",
4247 dependence_stats.num_subscript_tests);
4248 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4249 dependence_stats.num_subscript_undetermined);
4250 fprintf (dump_file, "Number of same subscript function: %d\n",
4251 dependence_stats.num_same_subscript_function);
4253 fprintf (dump_file, "Number of ziv tests: %d\n",
4254 dependence_stats.num_ziv);
4255 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4256 dependence_stats.num_ziv_dependent);
4257 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4258 dependence_stats.num_ziv_independent);
4259 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4260 dependence_stats.num_ziv_unimplemented);
4262 fprintf (dump_file, "Number of siv tests: %d\n",
4263 dependence_stats.num_siv);
4264 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4265 dependence_stats.num_siv_dependent);
4266 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4267 dependence_stats.num_siv_independent);
4268 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4269 dependence_stats.num_siv_unimplemented);
4271 fprintf (dump_file, "Number of miv tests: %d\n",
4272 dependence_stats.num_miv);
4273 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4274 dependence_stats.num_miv_dependent);
4275 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4276 dependence_stats.num_miv_independent);
4277 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4278 dependence_stats.num_miv_unimplemented);
4284 /* Entry point (for testing only). Analyze all the data references
4285 and the dependence relations in LOOP.
4287 The data references are computed first.
4289 A relation on these nodes is represented by a complete graph. Some
4290 of the relations could be of no interest, thus the relations can be
4293 In the following function we compute all the relations. This is
4294 just a first implementation that is here for:
4295 - for showing how to ask for the dependence relations,
4296 - for the debugging the whole dependence graph,
4297 - for the dejagnu testcases and maintenance.
4299 It is possible to ask only for a part of the graph, avoiding to
4300 compute the whole dependence graph. The computed dependences are
4301 stored in a knowledge base (KB) such that later queries don't
4302 recompute the same information. The implementation of this KB is
4303 transparent to the optimizer, and thus the KB can be changed with a
4304 more efficient implementation, or the KB could be disabled. */
4306 analyze_all_data_dependences (struct loop *loop)
4309 int nb_data_refs = 10;
4310 VEC (data_reference_p, heap) *datarefs =
4311 VEC_alloc (data_reference_p, heap, nb_data_refs);
4312 VEC (ddr_p, heap) *dependence_relations =
4313 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4315 /* Compute DDs on the whole function. */
4316 compute_data_dependences_for_loop (loop, false, &datarefs,
4317 &dependence_relations);
4321 dump_data_dependence_relations (dump_file, dependence_relations);
4322 fprintf (dump_file, "\n\n");
4324 if (dump_flags & TDF_DETAILS)
4325 dump_dist_dir_vectors (dump_file, dependence_relations);
4327 if (dump_flags & TDF_STATS)
4329 unsigned nb_top_relations = 0;
4330 unsigned nb_bot_relations = 0;
4331 unsigned nb_basename_differ = 0;
4332 unsigned nb_chrec_relations = 0;
4333 struct data_dependence_relation *ddr;
4335 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4337 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4340 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4342 struct data_reference *a = DDR_A (ddr);
4343 struct data_reference *b = DDR_B (ddr);
4345 if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
4346 nb_basename_differ++;
4352 nb_chrec_relations++;
4355 gather_stats_on_scev_database ();
4359 free_dependence_relations (dependence_relations);
4360 free_data_refs (datarefs);
4363 /* Computes all the data dependences and check that the results of
4364 several analyzers are the same. */
4367 tree_check_data_deps (void)
4370 struct loop *loop_nest;
4372 FOR_EACH_LOOP (li, loop_nest, 0)
4373 analyze_all_data_dependences (loop_nest);
4376 /* Free the memory used by a data dependence relation DDR. */
4379 free_dependence_relation (struct data_dependence_relation *ddr)
4384 if (DDR_SUBSCRIPTS (ddr))
4385 free_subscripts (DDR_SUBSCRIPTS (ddr));
4386 if (DDR_DIST_VECTS (ddr))
4387 VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
4388 if (DDR_DIR_VECTS (ddr))
4389 VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
4394 /* Free the memory used by the data dependence relations from
4395 DEPENDENCE_RELATIONS. */
4398 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4401 struct data_dependence_relation *ddr;
4402 VEC (loop_p, heap) *loop_nest = NULL;
4404 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4408 if (loop_nest == NULL)
4409 loop_nest = DDR_LOOP_NEST (ddr);
4411 gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4412 || DDR_LOOP_NEST (ddr) == loop_nest);
4413 free_dependence_relation (ddr);
4417 VEC_free (loop_p, heap, loop_nest);
4418 VEC_free (ddr_p, heap, dependence_relations);
4421 /* Free the memory used by the data references from DATAREFS. */
4424 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4427 struct data_reference *dr;
4429 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4431 VEC_free (data_reference_p, heap, datarefs);
4436 /* Dump vertex I in RDG to FILE. */
4439 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
4441 struct vertex *v = &(rdg->vertices[i]);
4442 struct graph_edge *e;
4444 fprintf (file, "(vertex %d: (%s%s) (in:", i,
4445 RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
4446 RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
4449 for (e = v->pred; e; e = e->pred_next)
4450 fprintf (file, " %d", e->src);
4452 fprintf (file, ") (out:");
4455 for (e = v->succ; e; e = e->succ_next)
4456 fprintf (file, " %d", e->dest);
4458 fprintf (file, ") \n");
4459 print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
4460 fprintf (file, ")\n");
4463 /* Call dump_rdg_vertex on stderr. */
4466 debug_rdg_vertex (struct graph *rdg, int i)
4468 dump_rdg_vertex (stderr, rdg, i);
4471 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4472 dumped vertices to that bitmap. */
4474 void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
4478 fprintf (file, "(%d\n", c);
4480 for (i = 0; i < rdg->n_vertices; i++)
4481 if (rdg->vertices[i].component == c)
4484 bitmap_set_bit (dumped, i);
4486 dump_rdg_vertex (file, rdg, i);
4489 fprintf (file, ")\n");
4492 /* Call dump_rdg_vertex on stderr. */
4495 debug_rdg_component (struct graph *rdg, int c)
4497 dump_rdg_component (stderr, rdg, c, NULL);
4500 /* Dump the reduced dependence graph RDG to FILE. */
4503 dump_rdg (FILE *file, struct graph *rdg)
4506 bitmap dumped = BITMAP_ALLOC (NULL);
4508 fprintf (file, "(rdg\n");
4510 for (i = 0; i < rdg->n_vertices; i++)
4511 if (!bitmap_bit_p (dumped, i))
4512 dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
4514 fprintf (file, ")\n");
4515 BITMAP_FREE (dumped);
4518 /* Call dump_rdg on stderr. */
4521 debug_rdg (struct graph *rdg)
4523 dump_rdg (stderr, rdg);
4527 dot_rdg_1 (FILE *file, struct graph *rdg)
4531 fprintf (file, "digraph RDG {\n");
4533 for (i = 0; i < rdg->n_vertices; i++)
4535 struct vertex *v = &(rdg->vertices[i]);
4536 struct graph_edge *e;
4538 /* Highlight reads from memory. */
4539 if (RDG_MEM_READS_STMT (rdg, i))
4540 fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
4542 /* Highlight stores to memory. */
4543 if (RDG_MEM_WRITE_STMT (rdg, i))
4544 fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
4547 for (e = v->succ; e; e = e->succ_next)
4548 switch (RDGE_TYPE (e))
4551 fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
4555 fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
4559 /* These are the most common dependences: don't print these. */
4560 fprintf (file, "%d -> %d \n", i, e->dest);
4564 fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
4572 fprintf (file, "}\n\n");
4575 /* Display SCOP using dotty. */
4578 dot_rdg (struct graph *rdg)
4580 FILE *file = fopen ("/tmp/rdg.dot", "w");
4581 gcc_assert (file != NULL);
4583 dot_rdg_1 (file, rdg);
4586 system ("dotty /tmp/rdg.dot");
4590 /* This structure is used for recording the mapping statement index in
4593 struct rdg_vertex_info GTY(())
4599 /* Returns the index of STMT in RDG. */
4602 rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
4604 struct rdg_vertex_info rvi, *slot;
4607 slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
4615 /* Creates an edge in RDG for each distance vector from DDR. The
4616 order that we keep track of in the RDG is the order in which
4617 statements have to be executed. */
4620 create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
4622 struct graph_edge *e;
4624 data_reference_p dra = DDR_A (ddr);
4625 data_reference_p drb = DDR_B (ddr);
4626 unsigned level = ddr_dependence_level (ddr);
4628 /* For non scalar dependences, when the dependence is REVERSED,
4629 statement B has to be executed before statement A. */
4631 && !DDR_REVERSED_P (ddr))
4633 data_reference_p tmp = dra;
4638 va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
4639 vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
4641 if (va < 0 || vb < 0)
4644 e = add_edge (rdg, va, vb);
4645 e->data = XNEW (struct rdg_edge);
4647 RDGE_LEVEL (e) = level;
4649 /* Determines the type of the data dependence. */
4650 if (DR_IS_READ (dra) && DR_IS_READ (drb))
4651 RDGE_TYPE (e) = input_dd;
4652 else if (!DR_IS_READ (dra) && !DR_IS_READ (drb))
4653 RDGE_TYPE (e) = output_dd;
4654 else if (!DR_IS_READ (dra) && DR_IS_READ (drb))
4655 RDGE_TYPE (e) = flow_dd;
4656 else if (DR_IS_READ (dra) && !DR_IS_READ (drb))
4657 RDGE_TYPE (e) = anti_dd;
4660 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4661 the index of DEF in RDG. */
4664 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
4666 use_operand_p imm_use_p;
4667 imm_use_iterator iterator;
4669 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
4671 struct graph_edge *e;
4672 int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
4677 e = add_edge (rdg, idef, use);
4678 e->data = XNEW (struct rdg_edge);
4679 RDGE_TYPE (e) = flow_dd;
4683 /* Creates the edges of the reduced dependence graph RDG. */
4686 create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
4689 struct data_dependence_relation *ddr;
4690 def_operand_p def_p;
4693 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
4694 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4695 create_rdg_edge_for_ddr (rdg, ddr);
4697 for (i = 0; i < rdg->n_vertices; i++)
4698 FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
4700 create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
4703 /* Build the vertices of the reduced dependence graph RDG. */
4706 create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
4711 for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++)
4713 VEC (data_ref_loc, heap) *references;
4715 struct vertex *v = &(rdg->vertices[i]);
4716 struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
4717 struct rdg_vertex_info **slot;
4721 slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
4728 v->data = XNEW (struct rdg_vertex);
4729 RDG_STMT (rdg, i) = stmt;
4731 RDG_MEM_WRITE_STMT (rdg, i) = false;
4732 RDG_MEM_READS_STMT (rdg, i) = false;
4733 if (gimple_code (stmt) == GIMPLE_PHI)
4736 get_references_in_stmt (stmt, &references);
4737 for (j = 0; VEC_iterate (data_ref_loc, references, j, ref); j++)
4739 RDG_MEM_WRITE_STMT (rdg, i) = true;
4741 RDG_MEM_READS_STMT (rdg, i) = true;
4743 VEC_free (data_ref_loc, heap, references);
4747 /* Initialize STMTS with all the statements of LOOP. When
4748 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4749 which we discover statements is important as
4750 generate_loops_for_partition is using the same traversal for
4751 identifying statements. */
4754 stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
4757 basic_block *bbs = get_loop_body_in_dom_order (loop);
4759 for (i = 0; i < loop->num_nodes; i++)
4761 basic_block bb = bbs[i];
4762 gimple_stmt_iterator bsi;
4765 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4766 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
4768 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4770 stmt = gsi_stmt (bsi);
4771 if (gimple_code (stmt) != GIMPLE_LABEL)
4772 VEC_safe_push (gimple, heap, *stmts, stmt);
4779 /* Returns true when all the dependences are computable. */
4782 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
4787 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4788 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4794 /* Computes a hash function for element ELT. */
4797 hash_stmt_vertex_info (const void *elt)
4799 const struct rdg_vertex_info *const rvi =
4800 (const struct rdg_vertex_info *) elt;
4801 gimple stmt = rvi->stmt;
4803 return htab_hash_pointer (stmt);
4806 /* Compares database elements E1 and E2. */
4809 eq_stmt_vertex_info (const void *e1, const void *e2)
4811 const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
4812 const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
4814 return elt1->stmt == elt2->stmt;
4817 /* Free the element E. */
4820 hash_stmt_vertex_del (void *e)
4825 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4826 statement of the loop nest, and one edge per data dependence or
4827 scalar dependence. */
4830 build_rdg (struct loop *loop)
4832 int nb_data_refs = 10;
4833 struct graph *rdg = NULL;
4834 VEC (ddr_p, heap) *dependence_relations;
4835 VEC (data_reference_p, heap) *datarefs;
4836 VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs);
4838 dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
4839 datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
4840 compute_data_dependences_for_loop (loop,
4843 &dependence_relations);
4845 if (!known_dependences_p (dependence_relations))
4848 stmts_from_loop (loop, &stmts);
4849 rdg = new_graph (VEC_length (gimple, stmts));
4851 rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
4852 eq_stmt_vertex_info, hash_stmt_vertex_del);
4853 create_rdg_vertices (rdg, stmts);
4854 create_rdg_edges (rdg, dependence_relations);
4857 free_dependence_relations (dependence_relations);
4858 free_data_refs (datarefs);
4859 VEC_free (gimple, heap, stmts);
4864 /* Free the reduced dependence graph RDG. */
4867 free_rdg (struct graph *rdg)
4871 for (i = 0; i < rdg->n_vertices; i++)
4872 free (rdg->vertices[i].data);
4874 htab_delete (rdg->indices);
4878 /* Initialize STMTS with all the statements of LOOP that contain a
4882 stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
4885 basic_block *bbs = get_loop_body_in_dom_order (loop);
4887 for (i = 0; i < loop->num_nodes; i++)
4889 basic_block bb = bbs[i];
4890 gimple_stmt_iterator bsi;
4892 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4893 if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi), SSA_OP_VDEF))
4894 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
4900 /* For a data reference REF, return the declaration of its base
4901 address or NULL_TREE if the base is not determined. */
4904 ref_base_address (gimple stmt, data_ref_loc *ref)
4906 tree base = NULL_TREE;
4908 struct data_reference *dr = XCNEW (struct data_reference);
4910 DR_STMT (dr) = stmt;
4911 DR_REF (dr) = *ref->pos;
4912 dr_analyze_innermost (dr);
4913 base_address = DR_BASE_ADDRESS (dr);
4918 switch (TREE_CODE (base_address))
4921 base = TREE_OPERAND (base_address, 0);
4925 base = base_address;
4934 /* Determines whether the statement from vertex V of the RDG has a
4935 definition used outside the loop that contains this statement. */
4938 rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
4940 gimple stmt = RDG_STMT (rdg, v);
4941 struct loop *loop = loop_containing_stmt (stmt);
4942 use_operand_p imm_use_p;
4943 imm_use_iterator iterator;
4945 def_operand_p def_p;
4950 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
4952 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
4954 if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
4962 /* Determines whether statements S1 and S2 access to similar memory
4963 locations. Two memory accesses are considered similar when they
4964 have the same base address declaration, i.e. when their
4965 ref_base_address is the same. */
4968 have_similar_memory_accesses (gimple s1, gimple s2)
4972 VEC (data_ref_loc, heap) *refs1, *refs2;
4973 data_ref_loc *ref1, *ref2;
4975 get_references_in_stmt (s1, &refs1);
4976 get_references_in_stmt (s2, &refs2);
4978 for (i = 0; VEC_iterate (data_ref_loc, refs1, i, ref1); i++)
4980 tree base1 = ref_base_address (s1, ref1);
4983 for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++)
4984 if (base1 == ref_base_address (s2, ref2))
4992 VEC_free (data_ref_loc, heap, refs1);
4993 VEC_free (data_ref_loc, heap, refs2);
4997 /* Helper function for the hashtab. */
5000 have_similar_memory_accesses_1 (const void *s1, const void *s2)
5002 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1),
5003 CONST_CAST_GIMPLE ((const_gimple) s2));
5006 /* Helper function for the hashtab. */
5009 ref_base_address_1 (const void *s)
5011 gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s);
5013 VEC (data_ref_loc, heap) *refs;
5017 get_references_in_stmt (stmt, &refs);
5019 for (i = 0; VEC_iterate (data_ref_loc, refs, i, ref); i++)
5022 res = htab_hash_pointer (ref_base_address (stmt, ref));
5026 VEC_free (data_ref_loc, heap, refs);
5030 /* Try to remove duplicated write data references from STMTS. */
5033 remove_similar_memory_refs (VEC (gimple, heap) **stmts)
5037 htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1,
5038 have_similar_memory_accesses_1, NULL);
5040 for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); )
5044 slot = htab_find_slot (seen, stmt, INSERT);
5047 VEC_ordered_remove (gimple, *stmts, i);
5050 *slot = (void *) stmt;
5058 /* Returns the index of PARAMETER in the parameters vector of the
5059 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5062 access_matrix_get_index_for_parameter (tree parameter,
5063 struct access_matrix *access_matrix)
5066 VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
5067 tree lambda_parameter;
5069 for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++)
5070 if (lambda_parameter == parameter)
5071 return i + AM_NB_INDUCTION_VARS (access_matrix);