1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
85 /* These RTL headers are needed for basic-block.h. */
87 #include "basic-block.h"
88 #include "diagnostic.h"
89 #include "tree-flow.h"
90 #include "tree-dump.h"
93 #include "tree-data-ref.h"
94 #include "tree-scalar-evolution.h"
95 #include "tree-pass.h"
96 #include "langhooks.h"
98 static struct datadep_stats
100 int num_dependence_tests
;
101 int num_dependence_dependent
;
102 int num_dependence_independent
;
103 int num_dependence_undetermined
;
105 int num_subscript_tests
;
106 int num_subscript_undetermined
;
107 int num_same_subscript_function
;
110 int num_ziv_independent
;
111 int num_ziv_dependent
;
112 int num_ziv_unimplemented
;
115 int num_siv_independent
;
116 int num_siv_dependent
;
117 int num_siv_unimplemented
;
120 int num_miv_independent
;
121 int num_miv_dependent
;
122 int num_miv_unimplemented
;
125 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
126 struct data_reference
*,
127 struct data_reference
*,
129 /* Returns true iff A divides B. */
132 tree_fold_divides_p (const_tree a
, const_tree b
)
134 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
135 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
136 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
, 0));
139 /* Returns true iff A divides B. */
142 int_divides_p (int a
, int b
)
144 return ((b
% a
) == 0);
149 /* Dump into FILE all the data references from DATAREFS. */
152 dump_data_references (FILE *file
, VEC (data_reference_p
, heap
) *datarefs
)
155 struct data_reference
*dr
;
157 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
158 dump_data_reference (file
, dr
);
161 /* Dump into STDERR all the data references from DATAREFS. */
164 debug_data_references (VEC (data_reference_p
, heap
) *datarefs
)
166 dump_data_references (stderr
, datarefs
);
169 /* Dump to STDERR all the dependence relations from DDRS. */
172 debug_data_dependence_relations (VEC (ddr_p
, heap
) *ddrs
)
174 dump_data_dependence_relations (stderr
, ddrs
);
177 /* Dump into FILE all the dependence relations from DDRS. */
180 dump_data_dependence_relations (FILE *file
,
181 VEC (ddr_p
, heap
) *ddrs
)
184 struct data_dependence_relation
*ddr
;
186 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
187 dump_data_dependence_relation (file
, ddr
);
190 /* Print to STDERR the data_reference DR. */
193 debug_data_reference (struct data_reference
*dr
)
195 dump_data_reference (stderr
, dr
);
198 /* Dump function for a DATA_REFERENCE structure. */
201 dump_data_reference (FILE *outf
,
202 struct data_reference
*dr
)
206 fprintf (outf
, "#(Data Ref: \n# stmt: ");
207 print_gimple_stmt (outf
, DR_STMT (dr
), 0, 0);
208 fprintf (outf
, "# ref: ");
209 print_generic_stmt (outf
, DR_REF (dr
), 0);
210 fprintf (outf
, "# base_object: ");
211 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
213 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
215 fprintf (outf
, "# Access function %d: ", i
);
216 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
218 fprintf (outf
, "#)\n");
221 /* Dumps the affine function described by FN to the file OUTF. */
224 dump_affine_function (FILE *outf
, affine_fn fn
)
229 print_generic_expr (outf
, VEC_index (tree
, fn
, 0), TDF_SLIM
);
230 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
232 fprintf (outf
, " + ");
233 print_generic_expr (outf
, coef
, TDF_SLIM
);
234 fprintf (outf
, " * x_%u", i
);
238 /* Dumps the conflict function CF to the file OUTF. */
241 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
245 if (cf
->n
== NO_DEPENDENCE
)
246 fprintf (outf
, "no dependence\n");
247 else if (cf
->n
== NOT_KNOWN
)
248 fprintf (outf
, "not known\n");
251 for (i
= 0; i
< cf
->n
; i
++)
254 dump_affine_function (outf
, cf
->fns
[i
]);
255 fprintf (outf
, "]\n");
260 /* Dump function for a SUBSCRIPT structure. */
263 dump_subscript (FILE *outf
, struct subscript
*subscript
)
265 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
267 fprintf (outf
, "\n (subscript \n");
268 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
269 dump_conflict_function (outf
, cf
);
270 if (CF_NONTRIVIAL_P (cf
))
272 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
273 fprintf (outf
, " last_conflict: ");
274 print_generic_stmt (outf
, last_iteration
, 0);
277 cf
= SUB_CONFLICTS_IN_B (subscript
);
278 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
279 dump_conflict_function (outf
, cf
);
280 if (CF_NONTRIVIAL_P (cf
))
282 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
283 fprintf (outf
, " last_conflict: ");
284 print_generic_stmt (outf
, last_iteration
, 0);
287 fprintf (outf
, " (Subscript distance: ");
288 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
289 fprintf (outf
, " )\n");
290 fprintf (outf
, " )\n");
293 /* Print the classic direction vector DIRV to OUTF. */
296 print_direction_vector (FILE *outf
,
302 for (eq
= 0; eq
< length
; eq
++)
304 enum data_dependence_direction dir
= ((enum data_dependence_direction
)
310 fprintf (outf
, " +");
313 fprintf (outf
, " -");
316 fprintf (outf
, " =");
318 case dir_positive_or_equal
:
319 fprintf (outf
, " +=");
321 case dir_positive_or_negative
:
322 fprintf (outf
, " +-");
324 case dir_negative_or_equal
:
325 fprintf (outf
, " -=");
328 fprintf (outf
, " *");
331 fprintf (outf
, "indep");
335 fprintf (outf
, "\n");
338 /* Print a vector of direction vectors. */
341 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
347 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
348 print_direction_vector (outf
, v
, length
);
351 /* Print a vector of distance vectors. */
354 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
360 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
361 print_lambda_vector (outf
, v
, length
);
367 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
369 dump_data_dependence_relation (stderr
, ddr
);
372 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
375 dump_data_dependence_relation (FILE *outf
,
376 struct data_dependence_relation
*ddr
)
378 struct data_reference
*dra
, *drb
;
380 fprintf (outf
, "(Data Dep: \n");
382 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
389 dump_data_reference (outf
, dra
);
391 fprintf (outf
, " (nil)\n");
393 dump_data_reference (outf
, drb
);
395 fprintf (outf
, " (nil)\n");
397 fprintf (outf
, " (don't know)\n)\n");
403 dump_data_reference (outf
, dra
);
404 dump_data_reference (outf
, drb
);
406 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
407 fprintf (outf
, " (no dependence)\n");
409 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
414 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
416 fprintf (outf
, " access_fn_A: ");
417 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
418 fprintf (outf
, " access_fn_B: ");
419 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
420 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
423 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
424 fprintf (outf
, " loop nest: (");
425 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
426 fprintf (outf
, "%d ", loopi
->num
);
427 fprintf (outf
, ")\n");
429 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
431 fprintf (outf
, " distance_vector: ");
432 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
436 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
438 fprintf (outf
, " direction_vector: ");
439 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
444 fprintf (outf
, ")\n");
447 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
450 dump_data_dependence_direction (FILE *file
,
451 enum data_dependence_direction dir
)
467 case dir_positive_or_negative
:
468 fprintf (file
, "+-");
471 case dir_positive_or_equal
:
472 fprintf (file
, "+=");
475 case dir_negative_or_equal
:
476 fprintf (file
, "-=");
488 /* Dumps the distance and direction vectors in FILE. DDRS contains
489 the dependence relations, and VECT_SIZE is the size of the
490 dependence vectors, or in other words the number of loops in the
494 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
497 struct data_dependence_relation
*ddr
;
500 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
501 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
503 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
505 fprintf (file
, "DISTANCE_V (");
506 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
507 fprintf (file
, ")\n");
510 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
512 fprintf (file
, "DIRECTION_V (");
513 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
514 fprintf (file
, ")\n");
518 fprintf (file
, "\n\n");
521 /* Dumps the data dependence relations DDRS in FILE. */
524 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
527 struct data_dependence_relation
*ddr
;
529 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
530 dump_data_dependence_relation (file
, ddr
);
532 fprintf (file
, "\n\n");
535 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
536 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
537 constant of type ssizetype, and returns true. If we cannot do this
538 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
542 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
543 tree
*var
, tree
*off
)
547 enum tree_code ocode
= code
;
555 *var
= build_int_cst (type
, 0);
556 *off
= fold_convert (ssizetype
, op0
);
559 case POINTER_PLUS_EXPR
:
564 split_constant_offset (op0
, &var0
, &off0
);
565 split_constant_offset (op1
, &var1
, &off1
);
566 *var
= fold_build2 (code
, type
, var0
, var1
);
567 *off
= size_binop (ocode
, off0
, off1
);
571 if (TREE_CODE (op1
) != INTEGER_CST
)
574 split_constant_offset (op0
, &var0
, &off0
);
575 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
576 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
582 HOST_WIDE_INT pbitsize
, pbitpos
;
583 enum machine_mode pmode
;
584 int punsignedp
, pvolatilep
;
586 op0
= TREE_OPERAND (op0
, 0);
587 if (!handled_component_p (op0
))
590 base
= get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
,
591 &pmode
, &punsignedp
, &pvolatilep
, false);
593 if (pbitpos
% BITS_PER_UNIT
!= 0)
595 base
= build_fold_addr_expr (base
);
596 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
600 split_constant_offset (poffset
, &poffset
, &off1
);
601 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
602 if (POINTER_TYPE_P (TREE_TYPE (base
)))
603 base
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (base
),
604 base
, fold_convert (sizetype
, poffset
));
606 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
607 fold_convert (TREE_TYPE (base
), poffset
));
610 var0
= fold_convert (type
, base
);
612 /* If variable length types are involved, punt, otherwise casts
613 might be converted into ARRAY_REFs in gimplify_conversion.
614 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
615 possibly no longer appears in current GIMPLE, might resurface.
616 This perhaps could run
617 if (CONVERT_EXPR_P (var0))
619 gimplify_conversion (&var0);
620 // Attempt to fill in any within var0 found ARRAY_REF's
621 // element size from corresponding op embedded ARRAY_REF,
622 // if unsuccessful, just punt.
624 while (POINTER_TYPE_P (type
))
625 type
= TREE_TYPE (type
);
626 if (int_size_in_bytes (type
) < 0)
636 gimple def_stmt
= SSA_NAME_DEF_STMT (op0
);
637 enum tree_code subcode
;
639 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
642 var0
= gimple_assign_rhs1 (def_stmt
);
643 subcode
= gimple_assign_rhs_code (def_stmt
);
644 var1
= gimple_assign_rhs2 (def_stmt
);
646 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
650 /* We must not introduce undefined overflow, and we must not change the value.
651 Hence we're okay if the inner type doesn't overflow to start with
652 (pointer or signed), the outer type also is an integer or pointer
653 and the outer precision is at least as large as the inner. */
654 tree itype
= TREE_TYPE (op0
);
655 if ((POINTER_TYPE_P (itype
)
656 || (INTEGRAL_TYPE_P (itype
) && TYPE_OVERFLOW_UNDEFINED (itype
)))
657 && TYPE_PRECISION (type
) >= TYPE_PRECISION (itype
)
658 && (POINTER_TYPE_P (type
) || INTEGRAL_TYPE_P (type
)))
660 split_constant_offset (op0
, &var0
, off
);
661 *var
= fold_convert (type
, var0
);
672 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
673 will be ssizetype. */
676 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
678 tree type
= TREE_TYPE (exp
), otype
, op0
, op1
, e
, o
;
682 *off
= ssize_int (0);
685 if (automatically_generated_chrec_p (exp
))
688 otype
= TREE_TYPE (exp
);
689 code
= TREE_CODE (exp
);
690 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
691 if (split_constant_offset_1 (otype
, op0
, code
, op1
, &e
, &o
))
693 *var
= fold_convert (type
, e
);
698 /* Returns the address ADDR of an object in a canonical shape (without nop
699 casts, and with type of pointer to the object). */
702 canonicalize_base_object_address (tree addr
)
708 /* The base address may be obtained by casting from integer, in that case
710 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
713 if (TREE_CODE (addr
) != ADDR_EXPR
)
716 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
719 /* Analyzes the behavior of the memory reference DR in the innermost loop or
720 basic block that contains it. Returns true if analysis succeed or false
724 dr_analyze_innermost (struct data_reference
*dr
)
726 gimple stmt
= DR_STMT (dr
);
727 struct loop
*loop
= loop_containing_stmt (stmt
);
728 tree ref
= DR_REF (dr
);
729 HOST_WIDE_INT pbitsize
, pbitpos
;
731 enum machine_mode pmode
;
732 int punsignedp
, pvolatilep
;
733 affine_iv base_iv
, offset_iv
;
734 tree init
, dinit
, step
;
735 bool in_loop
= (loop
&& loop
->num
);
737 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
738 fprintf (dump_file
, "analyze_innermost: ");
740 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
741 &pmode
, &punsignedp
, &pvolatilep
, false);
742 gcc_assert (base
!= NULL_TREE
);
744 if (pbitpos
% BITS_PER_UNIT
!= 0)
746 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
747 fprintf (dump_file
, "failed: bit offset alignment.\n");
751 base
= build_fold_addr_expr (base
);
754 if (!simple_iv (loop
, loop_containing_stmt (stmt
), base
, &base_iv
,
757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
758 fprintf (dump_file
, "failed: evolution of base is not affine.\n");
765 base_iv
.step
= ssize_int (0);
766 base_iv
.no_overflow
= true;
771 offset_iv
.base
= ssize_int (0);
772 offset_iv
.step
= ssize_int (0);
778 offset_iv
.base
= poffset
;
779 offset_iv
.step
= ssize_int (0);
781 else if (!simple_iv (loop
, loop_containing_stmt (stmt
),
782 poffset
, &offset_iv
, false))
784 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
785 fprintf (dump_file
, "failed: evolution of offset is not"
791 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
792 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
793 init
= size_binop (PLUS_EXPR
, init
, dinit
);
794 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
795 init
= size_binop (PLUS_EXPR
, init
, dinit
);
797 step
= size_binop (PLUS_EXPR
,
798 fold_convert (ssizetype
, base_iv
.step
),
799 fold_convert (ssizetype
, offset_iv
.step
));
801 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
803 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
807 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
809 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
810 fprintf (dump_file
, "success.\n");
815 /* Determines the base object and the list of indices of memory reference
816 DR, analyzed in loop nest NEST. */
819 dr_analyze_indices (struct data_reference
*dr
, struct loop
*nest
)
821 gimple stmt
= DR_STMT (dr
);
822 struct loop
*loop
= loop_containing_stmt (stmt
);
823 VEC (tree
, heap
) *access_fns
= NULL
;
824 tree ref
= unshare_expr (DR_REF (dr
)), aref
= ref
, op
;
825 tree base
, off
, access_fn
= NULL_TREE
;
826 basic_block before_loop
= NULL
;
829 before_loop
= block_before_loop (nest
);
831 while (handled_component_p (aref
))
833 if (TREE_CODE (aref
) == ARRAY_REF
)
835 op
= TREE_OPERAND (aref
, 1);
838 access_fn
= analyze_scalar_evolution (loop
, op
);
839 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
840 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
843 TREE_OPERAND (aref
, 1) = build_int_cst (TREE_TYPE (op
), 0);
846 aref
= TREE_OPERAND (aref
, 0);
849 if (nest
&& INDIRECT_REF_P (aref
))
851 op
= TREE_OPERAND (aref
, 0);
852 access_fn
= analyze_scalar_evolution (loop
, op
);
853 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
854 base
= initial_condition (access_fn
);
855 split_constant_offset (base
, &base
, &off
);
856 access_fn
= chrec_replace_initial_condition (access_fn
,
857 fold_convert (TREE_TYPE (base
), off
));
859 TREE_OPERAND (aref
, 0) = base
;
860 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
863 DR_BASE_OBJECT (dr
) = ref
;
864 DR_ACCESS_FNS (dr
) = access_fns
;
867 /* Extracts the alias analysis information from the memory reference DR. */
870 dr_analyze_alias (struct data_reference
*dr
)
872 tree ref
= DR_REF (dr
);
873 tree base
= get_base_address (ref
), addr
;
875 if (INDIRECT_REF_P (base
))
877 addr
= TREE_OPERAND (base
, 0);
878 if (TREE_CODE (addr
) == SSA_NAME
)
879 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
883 /* Returns true if the address of DR is invariant. */
886 dr_address_invariant_p (struct data_reference
*dr
)
891 for (i
= 0; VEC_iterate (tree
, DR_ACCESS_FNS (dr
), i
, idx
); i
++)
892 if (tree_contains_chrecs (idx
, NULL
))
898 /* Frees data reference DR. */
901 free_data_ref (data_reference_p dr
)
903 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
907 /* Analyzes memory reference MEMREF accessed in STMT. The reference
908 is read if IS_READ is true, write otherwise. Returns the
909 data_reference description of MEMREF. NEST is the outermost loop of the
910 loop nest in that the reference should be analyzed. */
912 struct data_reference
*
913 create_data_ref (struct loop
*nest
, tree memref
, gimple stmt
, bool is_read
)
915 struct data_reference
*dr
;
917 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
919 fprintf (dump_file
, "Creating dr for ");
920 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
921 fprintf (dump_file
, "\n");
924 dr
= XCNEW (struct data_reference
);
926 DR_REF (dr
) = memref
;
927 DR_IS_READ (dr
) = is_read
;
929 dr_analyze_innermost (dr
);
930 dr_analyze_indices (dr
, nest
);
931 dr_analyze_alias (dr
);
933 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
935 fprintf (dump_file
, "\tbase_address: ");
936 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
937 fprintf (dump_file
, "\n\toffset from base address: ");
938 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
939 fprintf (dump_file
, "\n\tconstant offset from base address: ");
940 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
941 fprintf (dump_file
, "\n\tstep: ");
942 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
943 fprintf (dump_file
, "\n\taligned to: ");
944 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
945 fprintf (dump_file
, "\n\tbase_object: ");
946 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
947 fprintf (dump_file
, "\n");
953 /* Returns true if FNA == FNB. */
956 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
958 unsigned i
, n
= VEC_length (tree
, fna
);
960 if (n
!= VEC_length (tree
, fnb
))
963 for (i
= 0; i
< n
; i
++)
964 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
965 VEC_index (tree
, fnb
, i
), 0))
971 /* If all the functions in CF are the same, returns one of them,
972 otherwise returns NULL. */
975 common_affine_function (conflict_function
*cf
)
980 if (!CF_NONTRIVIAL_P (cf
))
985 for (i
= 1; i
< cf
->n
; i
++)
986 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
992 /* Returns the base of the affine function FN. */
995 affine_function_base (affine_fn fn
)
997 return VEC_index (tree
, fn
, 0);
1000 /* Returns true if FN is a constant. */
1003 affine_function_constant_p (affine_fn fn
)
1008 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
1009 if (!integer_zerop (coef
))
1015 /* Returns true if FN is the zero constant function. */
1018 affine_function_zero_p (affine_fn fn
)
1020 return (integer_zerop (affine_function_base (fn
))
1021 && affine_function_constant_p (fn
));
1024 /* Returns a signed integer type with the largest precision from TA
1028 signed_type_for_types (tree ta
, tree tb
)
1030 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
1031 return signed_type_for (ta
);
1033 return signed_type_for (tb
);
1036 /* Applies operation OP on affine functions FNA and FNB, and returns the
1040 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
1046 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
1048 n
= VEC_length (tree
, fna
);
1049 m
= VEC_length (tree
, fnb
);
1053 n
= VEC_length (tree
, fnb
);
1054 m
= VEC_length (tree
, fna
);
1057 ret
= VEC_alloc (tree
, heap
, m
);
1058 for (i
= 0; i
< n
; i
++)
1060 tree type
= signed_type_for_types (TREE_TYPE (VEC_index (tree
, fna
, i
)),
1061 TREE_TYPE (VEC_index (tree
, fnb
, i
)));
1063 VEC_quick_push (tree
, ret
,
1064 fold_build2 (op
, type
,
1065 VEC_index (tree
, fna
, i
),
1066 VEC_index (tree
, fnb
, i
)));
1069 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
1070 VEC_quick_push (tree
, ret
,
1071 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1072 coef
, integer_zero_node
));
1073 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
1074 VEC_quick_push (tree
, ret
,
1075 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1076 integer_zero_node
, coef
));
1081 /* Returns the sum of affine functions FNA and FNB. */
1084 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1086 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1089 /* Returns the difference of affine functions FNA and FNB. */
1092 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1094 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1097 /* Frees affine function FN. */
1100 affine_fn_free (affine_fn fn
)
1102 VEC_free (tree
, heap
, fn
);
1105 /* Determine for each subscript in the data dependence relation DDR
1109 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1111 conflict_function
*cf_a
, *cf_b
;
1112 affine_fn fn_a
, fn_b
, diff
;
1114 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1118 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1120 struct subscript
*subscript
;
1122 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1123 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1124 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1126 fn_a
= common_affine_function (cf_a
);
1127 fn_b
= common_affine_function (cf_b
);
1130 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1133 diff
= affine_fn_minus (fn_a
, fn_b
);
1135 if (affine_function_constant_p (diff
))
1136 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1138 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1140 affine_fn_free (diff
);
1145 /* Returns the conflict function for "unknown". */
1147 static conflict_function
*
1148 conflict_fn_not_known (void)
1150 conflict_function
*fn
= XCNEW (conflict_function
);
1156 /* Returns the conflict function for "independent". */
1158 static conflict_function
*
1159 conflict_fn_no_dependence (void)
1161 conflict_function
*fn
= XCNEW (conflict_function
);
1162 fn
->n
= NO_DEPENDENCE
;
1167 /* Returns true if the address of OBJ is invariant in LOOP. */
1170 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1172 while (handled_component_p (obj
))
1174 if (TREE_CODE (obj
) == ARRAY_REF
)
1176 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1177 need to check the stride and the lower bound of the reference. */
1178 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1180 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1184 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1186 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1190 obj
= TREE_OPERAND (obj
, 0);
1193 if (!INDIRECT_REF_P (obj
))
1196 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1200 /* Returns true if A and B are accesses to different objects, or to different
1201 fields of the same object. */
1204 disjoint_objects_p (tree a
, tree b
)
1206 tree base_a
, base_b
;
1207 VEC (tree
, heap
) *comp_a
= NULL
, *comp_b
= NULL
;
1210 base_a
= get_base_address (a
);
1211 base_b
= get_base_address (b
);
1215 && base_a
!= base_b
)
1218 if (!operand_equal_p (base_a
, base_b
, 0))
1221 /* Compare the component references of A and B. We must start from the inner
1222 ones, so record them to the vector first. */
1223 while (handled_component_p (a
))
1225 VEC_safe_push (tree
, heap
, comp_a
, a
);
1226 a
= TREE_OPERAND (a
, 0);
1228 while (handled_component_p (b
))
1230 VEC_safe_push (tree
, heap
, comp_b
, b
);
1231 b
= TREE_OPERAND (b
, 0);
1237 if (VEC_length (tree
, comp_a
) == 0
1238 || VEC_length (tree
, comp_b
) == 0)
1241 a
= VEC_pop (tree
, comp_a
);
1242 b
= VEC_pop (tree
, comp_b
);
1244 /* Real and imaginary part of a variable do not alias. */
1245 if ((TREE_CODE (a
) == REALPART_EXPR
1246 && TREE_CODE (b
) == IMAGPART_EXPR
)
1247 || (TREE_CODE (a
) == IMAGPART_EXPR
1248 && TREE_CODE (b
) == REALPART_EXPR
))
1254 if (TREE_CODE (a
) != TREE_CODE (b
))
1257 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1258 DR_BASE_OBJECT are always zero. */
1259 if (TREE_CODE (a
) == ARRAY_REF
)
1261 else if (TREE_CODE (a
) == COMPONENT_REF
)
1263 if (operand_equal_p (TREE_OPERAND (a
, 1), TREE_OPERAND (b
, 1), 0))
1266 /* Different fields of unions may overlap. */
1267 base_a
= TREE_OPERAND (a
, 0);
1268 if (TREE_CODE (TREE_TYPE (base_a
)) == UNION_TYPE
)
1271 /* Different fields of structures cannot. */
1279 VEC_free (tree
, heap
, comp_a
);
1280 VEC_free (tree
, heap
, comp_b
);
1285 /* Returns false if we can prove that data references A and B do not alias,
1289 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
)
1291 const_tree addr_a
= DR_BASE_ADDRESS (a
);
1292 const_tree addr_b
= DR_BASE_ADDRESS (b
);
1293 const_tree type_a
, type_b
;
1294 const_tree decl_a
= NULL_TREE
, decl_b
= NULL_TREE
;
1296 /* If the accessed objects are disjoint, the memory references do not
1298 if (disjoint_objects_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
)))
1301 /* Query the alias oracle. */
1302 if (!DR_IS_READ (a
) && !DR_IS_READ (b
))
1304 if (!refs_output_dependent_p (DR_REF (a
), DR_REF (b
)))
1307 else if (DR_IS_READ (a
) && !DR_IS_READ (b
))
1309 if (!refs_anti_dependent_p (DR_REF (a
), DR_REF (b
)))
1312 else if (!refs_may_alias_p (DR_REF (a
), DR_REF (b
)))
1315 if (!addr_a
|| !addr_b
)
1318 /* If the references are based on different static objects, they cannot
1319 alias (PTA should be able to disambiguate such accesses, but often
1321 if (TREE_CODE (addr_a
) == ADDR_EXPR
1322 && TREE_CODE (addr_b
) == ADDR_EXPR
)
1323 return TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0);
1325 /* An instruction writing through a restricted pointer is "independent" of any
1326 instruction reading or writing through a different restricted pointer,
1327 in the same block/scope. */
1329 type_a
= TREE_TYPE (addr_a
);
1330 type_b
= TREE_TYPE (addr_b
);
1331 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
1333 if (TREE_CODE (addr_a
) == SSA_NAME
)
1334 decl_a
= SSA_NAME_VAR (addr_a
);
1335 if (TREE_CODE (addr_b
) == SSA_NAME
)
1336 decl_b
= SSA_NAME_VAR (addr_b
);
1338 if (TYPE_RESTRICT (type_a
) && TYPE_RESTRICT (type_b
)
1339 && (!DR_IS_READ (a
) || !DR_IS_READ (b
))
1340 && decl_a
&& DECL_P (decl_a
)
1341 && decl_b
&& DECL_P (decl_b
)
1343 && TREE_CODE (DECL_CONTEXT (decl_a
)) == FUNCTION_DECL
1344 && DECL_CONTEXT (decl_a
) == DECL_CONTEXT (decl_b
))
1350 static void compute_self_dependence (struct data_dependence_relation
*);
1352 /* Initialize a data dependence relation between data accesses A and
1353 B. NB_LOOPS is the number of loops surrounding the references: the
1354 size of the classic distance/direction vectors. */
1356 static struct data_dependence_relation
*
1357 initialize_data_dependence_relation (struct data_reference
*a
,
1358 struct data_reference
*b
,
1359 VEC (loop_p
, heap
) *loop_nest
)
1361 struct data_dependence_relation
*res
;
1364 res
= XNEW (struct data_dependence_relation
);
1367 DDR_LOOP_NEST (res
) = NULL
;
1368 DDR_REVERSED_P (res
) = false;
1369 DDR_SUBSCRIPTS (res
) = NULL
;
1370 DDR_DIR_VECTS (res
) = NULL
;
1371 DDR_DIST_VECTS (res
) = NULL
;
1373 if (a
== NULL
|| b
== NULL
)
1375 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1379 /* If the data references do not alias, then they are independent. */
1380 if (!dr_may_alias_p (a
, b
))
1382 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1386 /* When the references are exactly the same, don't spend time doing
1387 the data dependence tests, just initialize the ddr and return. */
1388 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1390 DDR_AFFINE_P (res
) = true;
1391 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1392 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1393 DDR_LOOP_NEST (res
) = loop_nest
;
1394 DDR_INNER_LOOP (res
) = 0;
1395 DDR_SELF_REFERENCE (res
) = true;
1396 compute_self_dependence (res
);
1400 /* If the references do not access the same object, we do not know
1401 whether they alias or not. */
1402 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1404 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1408 /* If the base of the object is not invariant in the loop nest, we cannot
1409 analyze it. TODO -- in fact, it would suffice to record that there may
1410 be arbitrary dependences in the loops where the base object varies. */
1412 && !object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1413 DR_BASE_OBJECT (a
)))
1415 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1419 gcc_assert (DR_NUM_DIMENSIONS (a
) == DR_NUM_DIMENSIONS (b
));
1421 DDR_AFFINE_P (res
) = true;
1422 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1423 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1424 DDR_LOOP_NEST (res
) = loop_nest
;
1425 DDR_INNER_LOOP (res
) = 0;
1426 DDR_SELF_REFERENCE (res
) = false;
1428 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1430 struct subscript
*subscript
;
1432 subscript
= XNEW (struct subscript
);
1433 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1434 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1435 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1436 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1437 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1443 /* Frees memory used by the conflict function F. */
1446 free_conflict_function (conflict_function
*f
)
1450 if (CF_NONTRIVIAL_P (f
))
1452 for (i
= 0; i
< f
->n
; i
++)
1453 affine_fn_free (f
->fns
[i
]);
1458 /* Frees memory used by SUBSCRIPTS. */
1461 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1466 for (i
= 0; VEC_iterate (subscript_p
, subscripts
, i
, s
); i
++)
1468 free_conflict_function (s
->conflicting_iterations_in_a
);
1469 free_conflict_function (s
->conflicting_iterations_in_b
);
1472 VEC_free (subscript_p
, heap
, subscripts
);
1475 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1479 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1482 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1484 fprintf (dump_file
, "(dependence classified: ");
1485 print_generic_expr (dump_file
, chrec
, 0);
1486 fprintf (dump_file
, ")\n");
1489 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1490 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1491 DDR_SUBSCRIPTS (ddr
) = NULL
;
1494 /* The dependence relation DDR cannot be represented by a distance
1498 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1500 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1501 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1503 DDR_AFFINE_P (ddr
) = false;
1508 /* This section contains the classic Banerjee tests. */
1510 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1511 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1514 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1516 return (evolution_function_is_constant_p (chrec_a
)
1517 && evolution_function_is_constant_p (chrec_b
));
1520 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1521 variable, i.e., if the SIV (Single Index Variable) test is true. */
1524 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1526 if ((evolution_function_is_constant_p (chrec_a
)
1527 && evolution_function_is_univariate_p (chrec_b
))
1528 || (evolution_function_is_constant_p (chrec_b
)
1529 && evolution_function_is_univariate_p (chrec_a
)))
1532 if (evolution_function_is_univariate_p (chrec_a
)
1533 && evolution_function_is_univariate_p (chrec_b
))
1535 switch (TREE_CODE (chrec_a
))
1537 case POLYNOMIAL_CHREC
:
1538 switch (TREE_CODE (chrec_b
))
1540 case POLYNOMIAL_CHREC
:
1541 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1556 /* Creates a conflict function with N dimensions. The affine functions
1557 in each dimension follow. */
1559 static conflict_function
*
1560 conflict_fn (unsigned n
, ...)
1563 conflict_function
*ret
= XCNEW (conflict_function
);
1566 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1570 for (i
= 0; i
< n
; i
++)
1571 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1577 /* Returns constant affine function with value CST. */
1580 affine_fn_cst (tree cst
)
1582 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1583 VEC_quick_push (tree
, fn
, cst
);
1587 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1590 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1592 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1595 gcc_assert (dim
> 0);
1596 VEC_quick_push (tree
, fn
, cst
);
1597 for (i
= 1; i
< dim
; i
++)
1598 VEC_quick_push (tree
, fn
, integer_zero_node
);
1599 VEC_quick_push (tree
, fn
, coef
);
1603 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1604 *OVERLAPS_B are initialized to the functions that describe the
1605 relation between the elements accessed twice by CHREC_A and
1606 CHREC_B. For k >= 0, the following property is verified:
1608 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1611 analyze_ziv_subscript (tree chrec_a
,
1613 conflict_function
**overlaps_a
,
1614 conflict_function
**overlaps_b
,
1615 tree
*last_conflicts
)
1617 tree type
, difference
;
1618 dependence_stats
.num_ziv
++;
1620 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1621 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1623 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1624 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1625 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1626 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1628 switch (TREE_CODE (difference
))
1631 if (integer_zerop (difference
))
1633 /* The difference is equal to zero: the accessed index
1634 overlaps for each iteration in the loop. */
1635 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1636 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1637 *last_conflicts
= chrec_dont_know
;
1638 dependence_stats
.num_ziv_dependent
++;
1642 /* The accesses do not overlap. */
1643 *overlaps_a
= conflict_fn_no_dependence ();
1644 *overlaps_b
= conflict_fn_no_dependence ();
1645 *last_conflicts
= integer_zero_node
;
1646 dependence_stats
.num_ziv_independent
++;
1651 /* We're not sure whether the indexes overlap. For the moment,
1652 conservatively answer "don't know". */
1653 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1654 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1656 *overlaps_a
= conflict_fn_not_known ();
1657 *overlaps_b
= conflict_fn_not_known ();
1658 *last_conflicts
= chrec_dont_know
;
1659 dependence_stats
.num_ziv_unimplemented
++;
1663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1664 fprintf (dump_file
, ")\n");
1667 /* Sets NIT to the estimated number of executions of the statements in
1668 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1669 large as the number of iterations. If we have no reliable estimate,
1670 the function returns false, otherwise returns true. */
1673 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
1676 estimate_numbers_of_iterations_loop (loop
);
1679 if (!loop
->any_upper_bound
)
1682 *nit
= loop
->nb_iterations_upper_bound
;
1686 if (!loop
->any_estimate
)
1689 *nit
= loop
->nb_iterations_estimate
;
1695 /* Similar to estimated_loop_iterations, but returns the estimate only
1696 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1697 on the number of iterations of LOOP could not be derived, returns -1. */
1700 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
1703 HOST_WIDE_INT hwi_nit
;
1705 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1708 if (!double_int_fits_in_shwi_p (nit
))
1710 hwi_nit
= double_int_to_shwi (nit
);
1712 return hwi_nit
< 0 ? -1 : hwi_nit
;
1715 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1716 and only if it fits to the int type. If this is not the case, or the
1717 estimate on the number of iterations of LOOP could not be derived, returns
1721 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
1726 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1727 return chrec_dont_know
;
1729 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
1730 if (!double_int_fits_to_tree_p (type
, nit
))
1731 return chrec_dont_know
;
1733 return double_int_to_tree (type
, nit
);
1736 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1737 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1738 *OVERLAPS_B are initialized to the functions that describe the
1739 relation between the elements accessed twice by CHREC_A and
1740 CHREC_B. For k >= 0, the following property is verified:
1742 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1745 analyze_siv_subscript_cst_affine (tree chrec_a
,
1747 conflict_function
**overlaps_a
,
1748 conflict_function
**overlaps_b
,
1749 tree
*last_conflicts
)
1751 bool value0
, value1
, value2
;
1752 tree type
, difference
, tmp
;
1754 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1755 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1756 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1757 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1759 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1762 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1764 dependence_stats
.num_siv_unimplemented
++;
1765 *overlaps_a
= conflict_fn_not_known ();
1766 *overlaps_b
= conflict_fn_not_known ();
1767 *last_conflicts
= chrec_dont_know
;
1772 if (value0
== false)
1774 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1776 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1777 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1779 *overlaps_a
= conflict_fn_not_known ();
1780 *overlaps_b
= conflict_fn_not_known ();
1781 *last_conflicts
= chrec_dont_know
;
1782 dependence_stats
.num_siv_unimplemented
++;
1791 chrec_b = {10, +, 1}
1794 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1796 HOST_WIDE_INT numiter
;
1797 struct loop
*loop
= get_chrec_loop (chrec_b
);
1799 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1800 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1801 fold_build1 (ABS_EXPR
, type
, difference
),
1802 CHREC_RIGHT (chrec_b
));
1803 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1804 *last_conflicts
= integer_one_node
;
1807 /* Perform weak-zero siv test to see if overlap is
1808 outside the loop bounds. */
1809 numiter
= estimated_loop_iterations_int (loop
, false);
1812 && compare_tree_int (tmp
, numiter
) > 0)
1814 free_conflict_function (*overlaps_a
);
1815 free_conflict_function (*overlaps_b
);
1816 *overlaps_a
= conflict_fn_no_dependence ();
1817 *overlaps_b
= conflict_fn_no_dependence ();
1818 *last_conflicts
= integer_zero_node
;
1819 dependence_stats
.num_siv_independent
++;
1822 dependence_stats
.num_siv_dependent
++;
1826 /* When the step does not divide the difference, there are
1830 *overlaps_a
= conflict_fn_no_dependence ();
1831 *overlaps_b
= conflict_fn_no_dependence ();
1832 *last_conflicts
= integer_zero_node
;
1833 dependence_stats
.num_siv_independent
++;
1842 chrec_b = {10, +, -1}
1844 In this case, chrec_a will not overlap with chrec_b. */
1845 *overlaps_a
= conflict_fn_no_dependence ();
1846 *overlaps_b
= conflict_fn_no_dependence ();
1847 *last_conflicts
= integer_zero_node
;
1848 dependence_stats
.num_siv_independent
++;
1855 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1857 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1858 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1860 *overlaps_a
= conflict_fn_not_known ();
1861 *overlaps_b
= conflict_fn_not_known ();
1862 *last_conflicts
= chrec_dont_know
;
1863 dependence_stats
.num_siv_unimplemented
++;
1868 if (value2
== false)
1872 chrec_b = {10, +, -1}
1874 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1876 HOST_WIDE_INT numiter
;
1877 struct loop
*loop
= get_chrec_loop (chrec_b
);
1879 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1880 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1881 CHREC_RIGHT (chrec_b
));
1882 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1883 *last_conflicts
= integer_one_node
;
1885 /* Perform weak-zero siv test to see if overlap is
1886 outside the loop bounds. */
1887 numiter
= estimated_loop_iterations_int (loop
, false);
1890 && compare_tree_int (tmp
, numiter
) > 0)
1892 free_conflict_function (*overlaps_a
);
1893 free_conflict_function (*overlaps_b
);
1894 *overlaps_a
= conflict_fn_no_dependence ();
1895 *overlaps_b
= conflict_fn_no_dependence ();
1896 *last_conflicts
= integer_zero_node
;
1897 dependence_stats
.num_siv_independent
++;
1900 dependence_stats
.num_siv_dependent
++;
1904 /* When the step does not divide the difference, there
1908 *overlaps_a
= conflict_fn_no_dependence ();
1909 *overlaps_b
= conflict_fn_no_dependence ();
1910 *last_conflicts
= integer_zero_node
;
1911 dependence_stats
.num_siv_independent
++;
1921 In this case, chrec_a will not overlap with chrec_b. */
1922 *overlaps_a
= conflict_fn_no_dependence ();
1923 *overlaps_b
= conflict_fn_no_dependence ();
1924 *last_conflicts
= integer_zero_node
;
1925 dependence_stats
.num_siv_independent
++;
1933 /* Helper recursive function for initializing the matrix A. Returns
1934 the initial value of CHREC. */
1937 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1941 switch (TREE_CODE (chrec
))
1943 case POLYNOMIAL_CHREC
:
1944 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
1946 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1947 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1953 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1954 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
1956 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
1961 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1962 return chrec_convert (chrec_type (chrec
), op
, NULL
);
1967 /* Handle ~X as -1 - X. */
1968 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1969 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
1970 build_int_cst (TREE_TYPE (chrec
), -1), op
);
1982 #define FLOOR_DIV(x,y) ((x) / (y))
1984 /* Solves the special case of the Diophantine equation:
1985 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1987 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1988 number of iterations that loops X and Y run. The overlaps will be
1989 constructed as evolutions in dimension DIM. */
1992 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1993 affine_fn
*overlaps_a
,
1994 affine_fn
*overlaps_b
,
1995 tree
*last_conflicts
, int dim
)
1997 if (((step_a
> 0 && step_b
> 0)
1998 || (step_a
< 0 && step_b
< 0)))
2000 int step_overlaps_a
, step_overlaps_b
;
2001 int gcd_steps_a_b
, last_conflict
, tau2
;
2003 gcd_steps_a_b
= gcd (step_a
, step_b
);
2004 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2005 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2009 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2010 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2011 last_conflict
= tau2
;
2012 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2015 *last_conflicts
= chrec_dont_know
;
2017 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
2018 build_int_cst (NULL_TREE
,
2020 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
2021 build_int_cst (NULL_TREE
,
2027 *overlaps_a
= affine_fn_cst (integer_zero_node
);
2028 *overlaps_b
= affine_fn_cst (integer_zero_node
);
2029 *last_conflicts
= integer_zero_node
;
2033 /* Solves the special case of a Diophantine equation where CHREC_A is
2034 an affine bivariate function, and CHREC_B is an affine univariate
2035 function. For example,
2037 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2039 has the following overlapping functions:
2041 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2042 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2043 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2045 FORNOW: This is a specialized implementation for a case occurring in
2046 a common benchmark. Implement the general algorithm. */
2049 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2050 conflict_function
**overlaps_a
,
2051 conflict_function
**overlaps_b
,
2052 tree
*last_conflicts
)
2054 bool xz_p
, yz_p
, xyz_p
;
2055 int step_x
, step_y
, step_z
;
2056 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
2057 affine_fn overlaps_a_xz
, overlaps_b_xz
;
2058 affine_fn overlaps_a_yz
, overlaps_b_yz
;
2059 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
2060 affine_fn ova1
, ova2
, ovb
;
2061 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
2063 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2064 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2065 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2068 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a
)),
2070 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), false);
2071 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), false);
2073 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2076 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2078 *overlaps_a
= conflict_fn_not_known ();
2079 *overlaps_b
= conflict_fn_not_known ();
2080 *last_conflicts
= chrec_dont_know
;
2084 niter
= MIN (niter_x
, niter_z
);
2085 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2088 &last_conflicts_xz
, 1);
2089 niter
= MIN (niter_y
, niter_z
);
2090 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2093 &last_conflicts_yz
, 2);
2094 niter
= MIN (niter_x
, niter_z
);
2095 niter
= MIN (niter_y
, niter
);
2096 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2099 &last_conflicts_xyz
, 3);
2101 xz_p
= !integer_zerop (last_conflicts_xz
);
2102 yz_p
= !integer_zerop (last_conflicts_yz
);
2103 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2105 if (xz_p
|| yz_p
|| xyz_p
)
2107 ova1
= affine_fn_cst (integer_zero_node
);
2108 ova2
= affine_fn_cst (integer_zero_node
);
2109 ovb
= affine_fn_cst (integer_zero_node
);
2112 affine_fn t0
= ova1
;
2115 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2116 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2117 affine_fn_free (t0
);
2118 affine_fn_free (t2
);
2119 *last_conflicts
= last_conflicts_xz
;
2123 affine_fn t0
= ova2
;
2126 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2127 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2128 affine_fn_free (t0
);
2129 affine_fn_free (t2
);
2130 *last_conflicts
= last_conflicts_yz
;
2134 affine_fn t0
= ova1
;
2135 affine_fn t2
= ova2
;
2138 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2139 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2140 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2141 affine_fn_free (t0
);
2142 affine_fn_free (t2
);
2143 affine_fn_free (t4
);
2144 *last_conflicts
= last_conflicts_xyz
;
2146 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2147 *overlaps_b
= conflict_fn (1, ovb
);
2151 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2152 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2153 *last_conflicts
= integer_zero_node
;
2156 affine_fn_free (overlaps_a_xz
);
2157 affine_fn_free (overlaps_b_xz
);
2158 affine_fn_free (overlaps_a_yz
);
2159 affine_fn_free (overlaps_b_yz
);
2160 affine_fn_free (overlaps_a_xyz
);
2161 affine_fn_free (overlaps_b_xyz
);
2164 /* Determines the overlapping elements due to accesses CHREC_A and
2165 CHREC_B, that are affine functions. This function cannot handle
2166 symbolic evolution functions, ie. when initial conditions are
2167 parameters, because it uses lambda matrices of integers. */
2170 analyze_subscript_affine_affine (tree chrec_a
,
2172 conflict_function
**overlaps_a
,
2173 conflict_function
**overlaps_b
,
2174 tree
*last_conflicts
)
2176 unsigned nb_vars_a
, nb_vars_b
, dim
;
2177 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2178 lambda_matrix A
, U
, S
;
2180 if (eq_evolutions_p (chrec_a
, chrec_b
))
2182 /* The accessed index overlaps for each iteration in the
2184 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2185 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2186 *last_conflicts
= chrec_dont_know
;
2189 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2190 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2192 /* For determining the initial intersection, we have to solve a
2193 Diophantine equation. This is the most time consuming part.
2195 For answering to the question: "Is there a dependence?" we have
2196 to prove that there exists a solution to the Diophantine
2197 equation, and that the solution is in the iteration domain,
2198 i.e. the solution is positive or zero, and that the solution
2199 happens before the upper bound loop.nb_iterations. Otherwise
2200 there is no dependence. This function outputs a description of
2201 the iterations that hold the intersections. */
2203 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2204 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2206 dim
= nb_vars_a
+ nb_vars_b
;
2207 U
= lambda_matrix_new (dim
, dim
);
2208 A
= lambda_matrix_new (dim
, 1);
2209 S
= lambda_matrix_new (dim
, 1);
2211 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2212 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2213 gamma
= init_b
- init_a
;
2215 /* Don't do all the hard work of solving the Diophantine equation
2216 when we already know the solution: for example,
2219 | gamma = 3 - 3 = 0.
2220 Then the first overlap occurs during the first iterations:
2221 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2225 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2227 HOST_WIDE_INT step_a
, step_b
;
2228 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2231 niter_a
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
),
2233 niter_b
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
),
2235 niter
= MIN (niter_a
, niter_b
);
2236 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2237 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2239 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2242 *overlaps_a
= conflict_fn (1, ova
);
2243 *overlaps_b
= conflict_fn (1, ovb
);
2246 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2247 compute_overlap_steps_for_affine_1_2
2248 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2250 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2251 compute_overlap_steps_for_affine_1_2
2252 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2256 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2257 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2258 *overlaps_a
= conflict_fn_not_known ();
2259 *overlaps_b
= conflict_fn_not_known ();
2260 *last_conflicts
= chrec_dont_know
;
2262 goto end_analyze_subs_aa
;
2266 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2271 lambda_matrix_row_negate (U
, dim
, 0);
2273 gcd_alpha_beta
= S
[0][0];
2275 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2276 but that is a quite strange case. Instead of ICEing, answer
2278 if (gcd_alpha_beta
== 0)
2280 *overlaps_a
= conflict_fn_not_known ();
2281 *overlaps_b
= conflict_fn_not_known ();
2282 *last_conflicts
= chrec_dont_know
;
2283 goto end_analyze_subs_aa
;
2286 /* The classic "gcd-test". */
2287 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2289 /* The "gcd-test" has determined that there is no integer
2290 solution, i.e. there is no dependence. */
2291 *overlaps_a
= conflict_fn_no_dependence ();
2292 *overlaps_b
= conflict_fn_no_dependence ();
2293 *last_conflicts
= integer_zero_node
;
2296 /* Both access functions are univariate. This includes SIV and MIV cases. */
2297 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2299 /* Both functions should have the same evolution sign. */
2300 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2301 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2303 /* The solutions are given by:
2305 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2308 For a given integer t. Using the following variables,
2310 | i0 = u11 * gamma / gcd_alpha_beta
2311 | j0 = u12 * gamma / gcd_alpha_beta
2318 | y0 = j0 + j1 * t. */
2319 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2321 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2322 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2326 if ((i1
== 0 && i0
< 0)
2327 || (j1
== 0 && j0
< 0))
2329 /* There is no solution.
2330 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2331 falls in here, but for the moment we don't look at the
2332 upper bound of the iteration domain. */
2333 *overlaps_a
= conflict_fn_no_dependence ();
2334 *overlaps_b
= conflict_fn_no_dependence ();
2335 *last_conflicts
= integer_zero_node
;
2336 goto end_analyze_subs_aa
;
2339 if (i1
> 0 && j1
> 0)
2341 HOST_WIDE_INT niter_a
= estimated_loop_iterations_int
2342 (get_chrec_loop (chrec_a
), false);
2343 HOST_WIDE_INT niter_b
= estimated_loop_iterations_int
2344 (get_chrec_loop (chrec_b
), false);
2345 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2347 /* (X0, Y0) is a solution of the Diophantine equation:
2348 "chrec_a (X0) = chrec_b (Y0)". */
2349 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2351 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2352 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2354 /* (X1, Y1) is the smallest positive solution of the eq
2355 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2356 first conflict occurs. */
2357 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2358 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2359 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2363 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2364 FLOOR_DIV (niter
- j0
, j1
));
2365 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2367 /* If the overlap occurs outside of the bounds of the
2368 loop, there is no dependence. */
2369 if (x1
>= niter
|| y1
>= niter
)
2371 *overlaps_a
= conflict_fn_no_dependence ();
2372 *overlaps_b
= conflict_fn_no_dependence ();
2373 *last_conflicts
= integer_zero_node
;
2374 goto end_analyze_subs_aa
;
2377 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2380 *last_conflicts
= chrec_dont_know
;
2384 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2386 build_int_cst (NULL_TREE
, i1
)));
2389 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2391 build_int_cst (NULL_TREE
, j1
)));
2395 /* FIXME: For the moment, the upper bound of the
2396 iteration domain for i and j is not checked. */
2397 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2398 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2399 *overlaps_a
= conflict_fn_not_known ();
2400 *overlaps_b
= conflict_fn_not_known ();
2401 *last_conflicts
= chrec_dont_know
;
2406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2407 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2408 *overlaps_a
= conflict_fn_not_known ();
2409 *overlaps_b
= conflict_fn_not_known ();
2410 *last_conflicts
= chrec_dont_know
;
2415 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2416 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2417 *overlaps_a
= conflict_fn_not_known ();
2418 *overlaps_b
= conflict_fn_not_known ();
2419 *last_conflicts
= chrec_dont_know
;
2422 end_analyze_subs_aa
:
2423 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2425 fprintf (dump_file
, " (overlaps_a = ");
2426 dump_conflict_function (dump_file
, *overlaps_a
);
2427 fprintf (dump_file
, ")\n (overlaps_b = ");
2428 dump_conflict_function (dump_file
, *overlaps_b
);
2429 fprintf (dump_file
, ")\n");
2430 fprintf (dump_file
, ")\n");
2434 /* Returns true when analyze_subscript_affine_affine can be used for
2435 determining the dependence relation between chrec_a and chrec_b,
2436 that contain symbols. This function modifies chrec_a and chrec_b
2437 such that the analysis result is the same, and such that they don't
2438 contain symbols, and then can safely be passed to the analyzer.
2440 Example: The analysis of the following tuples of evolutions produce
2441 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2444 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2445 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2449 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2451 tree diff
, type
, left_a
, left_b
, right_b
;
2453 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2454 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2455 /* FIXME: For the moment not handled. Might be refined later. */
2458 type
= chrec_type (*chrec_a
);
2459 left_a
= CHREC_LEFT (*chrec_a
);
2460 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2461 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2463 if (!evolution_function_is_constant_p (diff
))
2466 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2467 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2469 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2470 diff
, CHREC_RIGHT (*chrec_a
));
2471 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2472 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2473 build_int_cst (type
, 0),
2478 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2479 *OVERLAPS_B are initialized to the functions that describe the
2480 relation between the elements accessed twice by CHREC_A and
2481 CHREC_B. For k >= 0, the following property is verified:
2483 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2486 analyze_siv_subscript (tree chrec_a
,
2488 conflict_function
**overlaps_a
,
2489 conflict_function
**overlaps_b
,
2490 tree
*last_conflicts
,
2493 dependence_stats
.num_siv
++;
2495 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2496 fprintf (dump_file
, "(analyze_siv_subscript \n");
2498 if (evolution_function_is_constant_p (chrec_a
)
2499 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2500 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2501 overlaps_a
, overlaps_b
, last_conflicts
);
2503 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2504 && evolution_function_is_constant_p (chrec_b
))
2505 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2506 overlaps_b
, overlaps_a
, last_conflicts
);
2508 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2509 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2511 if (!chrec_contains_symbols (chrec_a
)
2512 && !chrec_contains_symbols (chrec_b
))
2514 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2515 overlaps_a
, overlaps_b
,
2518 if (CF_NOT_KNOWN_P (*overlaps_a
)
2519 || CF_NOT_KNOWN_P (*overlaps_b
))
2520 dependence_stats
.num_siv_unimplemented
++;
2521 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2522 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2523 dependence_stats
.num_siv_independent
++;
2525 dependence_stats
.num_siv_dependent
++;
2527 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2530 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2531 overlaps_a
, overlaps_b
,
2534 if (CF_NOT_KNOWN_P (*overlaps_a
)
2535 || CF_NOT_KNOWN_P (*overlaps_b
))
2536 dependence_stats
.num_siv_unimplemented
++;
2537 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2538 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2539 dependence_stats
.num_siv_independent
++;
2541 dependence_stats
.num_siv_dependent
++;
2544 goto siv_subscript_dontknow
;
2549 siv_subscript_dontknow
:;
2550 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2551 fprintf (dump_file
, "siv test failed: unimplemented.\n");
2552 *overlaps_a
= conflict_fn_not_known ();
2553 *overlaps_b
= conflict_fn_not_known ();
2554 *last_conflicts
= chrec_dont_know
;
2555 dependence_stats
.num_siv_unimplemented
++;
2558 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2559 fprintf (dump_file
, ")\n");
2562 /* Returns false if we can prove that the greatest common divisor of the steps
2563 of CHREC does not divide CST, false otherwise. */
2566 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2568 HOST_WIDE_INT cd
= 0, val
;
2571 if (!host_integerp (cst
, 0))
2573 val
= tree_low_cst (cst
, 0);
2575 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2577 step
= CHREC_RIGHT (chrec
);
2578 if (!host_integerp (step
, 0))
2580 cd
= gcd (cd
, tree_low_cst (step
, 0));
2581 chrec
= CHREC_LEFT (chrec
);
2584 return val
% cd
== 0;
2587 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2588 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2589 functions that describe the relation between the elements accessed
2590 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2593 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2596 analyze_miv_subscript (tree chrec_a
,
2598 conflict_function
**overlaps_a
,
2599 conflict_function
**overlaps_b
,
2600 tree
*last_conflicts
,
2601 struct loop
*loop_nest
)
2603 /* FIXME: This is a MIV subscript, not yet handled.
2604 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2607 In the SIV test we had to solve a Diophantine equation with two
2608 variables. In the MIV case we have to solve a Diophantine
2609 equation with 2*n variables (if the subscript uses n IVs).
2611 tree type
, difference
;
2613 dependence_stats
.num_miv
++;
2614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2615 fprintf (dump_file
, "(analyze_miv_subscript \n");
2617 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2618 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2619 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2620 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2622 if (eq_evolutions_p (chrec_a
, chrec_b
))
2624 /* Access functions are the same: all the elements are accessed
2625 in the same order. */
2626 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2627 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2628 *last_conflicts
= estimated_loop_iterations_tree
2629 (get_chrec_loop (chrec_a
), true);
2630 dependence_stats
.num_miv_dependent
++;
2633 else if (evolution_function_is_constant_p (difference
)
2634 /* For the moment, the following is verified:
2635 evolution_function_is_affine_multivariate_p (chrec_a,
2637 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2639 /* testsuite/.../ssa-chrec-33.c
2640 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2642 The difference is 1, and all the evolution steps are multiples
2643 of 2, consequently there are no overlapping elements. */
2644 *overlaps_a
= conflict_fn_no_dependence ();
2645 *overlaps_b
= conflict_fn_no_dependence ();
2646 *last_conflicts
= integer_zero_node
;
2647 dependence_stats
.num_miv_independent
++;
2650 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2651 && !chrec_contains_symbols (chrec_a
)
2652 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2653 && !chrec_contains_symbols (chrec_b
))
2655 /* testsuite/.../ssa-chrec-35.c
2656 {0, +, 1}_2 vs. {0, +, 1}_3
2657 the overlapping elements are respectively located at iterations:
2658 {0, +, 1}_x and {0, +, 1}_x,
2659 in other words, we have the equality:
2660 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2663 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2664 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2666 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2667 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2669 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2670 overlaps_a
, overlaps_b
, last_conflicts
);
2672 if (CF_NOT_KNOWN_P (*overlaps_a
)
2673 || CF_NOT_KNOWN_P (*overlaps_b
))
2674 dependence_stats
.num_miv_unimplemented
++;
2675 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2676 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2677 dependence_stats
.num_miv_independent
++;
2679 dependence_stats
.num_miv_dependent
++;
2684 /* When the analysis is too difficult, answer "don't know". */
2685 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2686 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2688 *overlaps_a
= conflict_fn_not_known ();
2689 *overlaps_b
= conflict_fn_not_known ();
2690 *last_conflicts
= chrec_dont_know
;
2691 dependence_stats
.num_miv_unimplemented
++;
2694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2695 fprintf (dump_file
, ")\n");
2698 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2699 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2700 OVERLAP_ITERATIONS_B are initialized with two functions that
2701 describe the iterations that contain conflicting elements.
2703 Remark: For an integer k >= 0, the following equality is true:
2705 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2709 analyze_overlapping_iterations (tree chrec_a
,
2711 conflict_function
**overlap_iterations_a
,
2712 conflict_function
**overlap_iterations_b
,
2713 tree
*last_conflicts
, struct loop
*loop_nest
)
2715 unsigned int lnn
= loop_nest
->num
;
2717 dependence_stats
.num_subscript_tests
++;
2719 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2721 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2722 fprintf (dump_file
, " (chrec_a = ");
2723 print_generic_expr (dump_file
, chrec_a
, 0);
2724 fprintf (dump_file
, ")\n (chrec_b = ");
2725 print_generic_expr (dump_file
, chrec_b
, 0);
2726 fprintf (dump_file
, ")\n");
2729 if (chrec_a
== NULL_TREE
2730 || chrec_b
== NULL_TREE
2731 || chrec_contains_undetermined (chrec_a
)
2732 || chrec_contains_undetermined (chrec_b
))
2734 dependence_stats
.num_subscript_undetermined
++;
2736 *overlap_iterations_a
= conflict_fn_not_known ();
2737 *overlap_iterations_b
= conflict_fn_not_known ();
2740 /* If they are the same chrec, and are affine, they overlap
2741 on every iteration. */
2742 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2743 && evolution_function_is_affine_multivariate_p (chrec_a
, lnn
))
2745 dependence_stats
.num_same_subscript_function
++;
2746 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2747 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2748 *last_conflicts
= chrec_dont_know
;
2751 /* If they aren't the same, and aren't affine, we can't do anything
2753 else if ((chrec_contains_symbols (chrec_a
)
2754 || chrec_contains_symbols (chrec_b
))
2755 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2756 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2758 dependence_stats
.num_subscript_undetermined
++;
2759 *overlap_iterations_a
= conflict_fn_not_known ();
2760 *overlap_iterations_b
= conflict_fn_not_known ();
2763 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2764 analyze_ziv_subscript (chrec_a
, chrec_b
,
2765 overlap_iterations_a
, overlap_iterations_b
,
2768 else if (siv_subscript_p (chrec_a
, chrec_b
))
2769 analyze_siv_subscript (chrec_a
, chrec_b
,
2770 overlap_iterations_a
, overlap_iterations_b
,
2771 last_conflicts
, lnn
);
2774 analyze_miv_subscript (chrec_a
, chrec_b
,
2775 overlap_iterations_a
, overlap_iterations_b
,
2776 last_conflicts
, loop_nest
);
2778 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2780 fprintf (dump_file
, " (overlap_iterations_a = ");
2781 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2782 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2783 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2784 fprintf (dump_file
, ")\n");
2785 fprintf (dump_file
, ")\n");
2789 /* Helper function for uniquely inserting distance vectors. */
2792 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2797 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
2798 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2801 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2804 /* Helper function for uniquely inserting direction vectors. */
2807 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2812 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
2813 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2816 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2819 /* Add a distance of 1 on all the loops outer than INDEX. If we
2820 haven't yet determined a distance for this outer loop, push a new
2821 distance vector composed of the previous distance, and a distance
2822 of 1 for this outer loop. Example:
2830 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2831 save (0, 1), then we have to save (1, 0). */
2834 add_outer_distances (struct data_dependence_relation
*ddr
,
2835 lambda_vector dist_v
, int index
)
2837 /* For each outer loop where init_v is not set, the accesses are
2838 in dependence of distance 1 in the loop. */
2839 while (--index
>= 0)
2841 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2842 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2844 save_dist_v (ddr
, save_v
);
2848 /* Return false when fail to represent the data dependence as a
2849 distance vector. INIT_B is set to true when a component has been
2850 added to the distance vector DIST_V. INDEX_CARRY is then set to
2851 the index in DIST_V that carries the dependence. */
2854 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2855 struct data_reference
*ddr_a
,
2856 struct data_reference
*ddr_b
,
2857 lambda_vector dist_v
, bool *init_b
,
2861 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2863 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2865 tree access_fn_a
, access_fn_b
;
2866 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2868 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2870 non_affine_dependence_relation (ddr
);
2874 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2875 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2877 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2878 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2881 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2882 DDR_LOOP_NEST (ddr
));
2883 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2884 DDR_LOOP_NEST (ddr
));
2886 /* The dependence is carried by the outermost loop. Example:
2893 In this case, the dependence is carried by loop_1. */
2894 index
= index_a
< index_b
? index_a
: index_b
;
2895 *index_carry
= MIN (index
, *index_carry
);
2897 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2899 non_affine_dependence_relation (ddr
);
2903 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2905 /* This is the subscript coupling test. If we have already
2906 recorded a distance for this loop (a distance coming from
2907 another subscript), it should be the same. For example,
2908 in the following code, there is no dependence:
2915 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2917 finalize_ddr_dependent (ddr
, chrec_known
);
2921 dist_v
[index
] = dist
;
2925 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2927 /* This can be for example an affine vs. constant dependence
2928 (T[i] vs. T[3]) that is not an affine dependence and is
2929 not representable as a distance vector. */
2930 non_affine_dependence_relation (ddr
);
2938 /* Return true when the DDR contains only constant access functions. */
2941 constant_access_functions (const struct data_dependence_relation
*ddr
)
2945 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2946 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2947 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2953 /* Helper function for the case where DDR_A and DDR_B are the same
2954 multivariate access function with a constant step. For an example
2958 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2961 tree c_1
= CHREC_LEFT (c_2
);
2962 tree c_0
= CHREC_LEFT (c_1
);
2963 lambda_vector dist_v
;
2966 /* Polynomials with more than 2 variables are not handled yet. When
2967 the evolution steps are parameters, it is not possible to
2968 represent the dependence using classical distance vectors. */
2969 if (TREE_CODE (c_0
) != INTEGER_CST
2970 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
2971 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
2973 DDR_AFFINE_P (ddr
) = false;
2977 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2978 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2980 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2981 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2982 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2983 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2996 save_dist_v (ddr
, dist_v
);
2998 add_outer_distances (ddr
, dist_v
, x_1
);
3001 /* Helper function for the case where DDR_A and DDR_B are the same
3002 access functions. */
3005 add_other_self_distances (struct data_dependence_relation
*ddr
)
3007 lambda_vector dist_v
;
3009 int index_carry
= DDR_NB_LOOPS (ddr
);
3011 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3013 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3015 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3017 if (!evolution_function_is_univariate_p (access_fun
))
3019 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3021 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3025 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
3027 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
3028 add_multivariate_self_dist (ddr
, access_fun
);
3030 /* The evolution step is not constant: it varies in
3031 the outer loop, so this cannot be represented by a
3032 distance vector. For example in pr34635.c the
3033 evolution is {0, +, {0, +, 4}_1}_2. */
3034 DDR_AFFINE_P (ddr
) = false;
3039 index_carry
= MIN (index_carry
,
3040 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3041 DDR_LOOP_NEST (ddr
)));
3045 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3046 add_outer_distances (ddr
, dist_v
, index_carry
);
3050 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
3052 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3054 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
3055 save_dist_v (ddr
, dist_v
);
3058 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3059 is the case for example when access functions are the same and
3060 equal to a constant, as in:
3067 in which case the distance vectors are (0) and (1). */
3070 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
3074 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3076 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
3077 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
3078 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
3080 for (j
= 0; j
< ca
->n
; j
++)
3081 if (affine_function_zero_p (ca
->fns
[j
]))
3083 insert_innermost_unit_dist_vector (ddr
);
3087 for (j
= 0; j
< cb
->n
; j
++)
3088 if (affine_function_zero_p (cb
->fns
[j
]))
3090 insert_innermost_unit_dist_vector (ddr
);
3096 /* Compute the classic per loop distance vector. DDR is the data
3097 dependence relation to build a vector from. Return false when fail
3098 to represent the data dependence as a distance vector. */
3101 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3102 struct loop
*loop_nest
)
3104 bool init_b
= false;
3105 int index_carry
= DDR_NB_LOOPS (ddr
);
3106 lambda_vector dist_v
;
3108 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3111 if (same_access_functions (ddr
))
3113 /* Save the 0 vector. */
3114 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3115 save_dist_v (ddr
, dist_v
);
3117 if (constant_access_functions (ddr
))
3118 add_distance_for_zero_overlaps (ddr
);
3120 if (DDR_NB_LOOPS (ddr
) > 1)
3121 add_other_self_distances (ddr
);
3126 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3127 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3128 dist_v
, &init_b
, &index_carry
))
3131 /* Save the distance vector if we initialized one. */
3134 /* Verify a basic constraint: classic distance vectors should
3135 always be lexicographically positive.
3137 Data references are collected in the order of execution of
3138 the program, thus for the following loop
3140 | for (i = 1; i < 100; i++)
3141 | for (j = 1; j < 100; j++)
3143 | t = T[j+1][i-1]; // A
3144 | T[j][i] = t + 2; // B
3147 references are collected following the direction of the wind:
3148 A then B. The data dependence tests are performed also
3149 following this order, such that we're looking at the distance
3150 separating the elements accessed by A from the elements later
3151 accessed by B. But in this example, the distance returned by
3152 test_dep (A, B) is lexicographically negative (-1, 1), that
3153 means that the access A occurs later than B with respect to
3154 the outer loop, ie. we're actually looking upwind. In this
3155 case we solve test_dep (B, A) looking downwind to the
3156 lexicographically positive solution, that returns the
3157 distance vector (1, -1). */
3158 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3160 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3161 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3164 compute_subscript_distance (ddr
);
3165 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3166 save_v
, &init_b
, &index_carry
))
3168 save_dist_v (ddr
, save_v
);
3169 DDR_REVERSED_P (ddr
) = true;
3171 /* In this case there is a dependence forward for all the
3174 | for (k = 1; k < 100; k++)
3175 | for (i = 1; i < 100; i++)
3176 | for (j = 1; j < 100; j++)
3178 | t = T[j+1][i-1]; // A
3179 | T[j][i] = t + 2; // B
3187 if (DDR_NB_LOOPS (ddr
) > 1)
3189 add_outer_distances (ddr
, save_v
, index_carry
);
3190 add_outer_distances (ddr
, dist_v
, index_carry
);
3195 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3196 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3198 if (DDR_NB_LOOPS (ddr
) > 1)
3200 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3202 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3203 DDR_A (ddr
), loop_nest
))
3205 compute_subscript_distance (ddr
);
3206 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3207 opposite_v
, &init_b
,
3211 save_dist_v (ddr
, save_v
);
3212 add_outer_distances (ddr
, dist_v
, index_carry
);
3213 add_outer_distances (ddr
, opposite_v
, index_carry
);
3216 save_dist_v (ddr
, save_v
);
3221 /* There is a distance of 1 on all the outer loops: Example:
3222 there is a dependence of distance 1 on loop_1 for the array A.
3228 add_outer_distances (ddr
, dist_v
,
3229 lambda_vector_first_nz (dist_v
,
3230 DDR_NB_LOOPS (ddr
), 0));
3233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3237 fprintf (dump_file
, "(build_classic_dist_vector\n");
3238 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3240 fprintf (dump_file
, " dist_vector = (");
3241 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3242 DDR_NB_LOOPS (ddr
));
3243 fprintf (dump_file
, " )\n");
3245 fprintf (dump_file
, ")\n");
3251 /* Return the direction for a given distance.
3252 FIXME: Computing dir this way is suboptimal, since dir can catch
3253 cases that dist is unable to represent. */
3255 static inline enum data_dependence_direction
3256 dir_from_dist (int dist
)
3259 return dir_positive
;
3261 return dir_negative
;
3266 /* Compute the classic per loop direction vector. DDR is the data
3267 dependence relation to build a vector from. */
3270 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3273 lambda_vector dist_v
;
3275 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3277 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3279 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3280 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3282 save_dir_v (ddr
, dir_v
);
3286 /* Helper function. Returns true when there is a dependence between
3287 data references DRA and DRB. */
3290 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3291 struct data_reference
*dra
,
3292 struct data_reference
*drb
,
3293 struct loop
*loop_nest
)
3296 tree last_conflicts
;
3297 struct subscript
*subscript
;
3299 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3302 conflict_function
*overlaps_a
, *overlaps_b
;
3304 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3305 DR_ACCESS_FN (drb
, i
),
3306 &overlaps_a
, &overlaps_b
,
3307 &last_conflicts
, loop_nest
);
3309 if (CF_NOT_KNOWN_P (overlaps_a
)
3310 || CF_NOT_KNOWN_P (overlaps_b
))
3312 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3313 dependence_stats
.num_dependence_undetermined
++;
3314 free_conflict_function (overlaps_a
);
3315 free_conflict_function (overlaps_b
);
3319 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3320 || CF_NO_DEPENDENCE_P (overlaps_b
))
3322 finalize_ddr_dependent (ddr
, chrec_known
);
3323 dependence_stats
.num_dependence_independent
++;
3324 free_conflict_function (overlaps_a
);
3325 free_conflict_function (overlaps_b
);
3331 if (SUB_CONFLICTS_IN_A (subscript
))
3332 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3333 if (SUB_CONFLICTS_IN_B (subscript
))
3334 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3336 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3337 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3338 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3345 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3348 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3349 struct loop
*loop_nest
)
3352 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3353 fprintf (dump_file
, "(subscript_dependence_tester \n");
3355 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3356 dependence_stats
.num_dependence_dependent
++;
3358 compute_subscript_distance (ddr
);
3359 if (build_classic_dist_vector (ddr
, loop_nest
))
3360 build_classic_dir_vector (ddr
);
3362 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3363 fprintf (dump_file
, ")\n");
3366 /* Returns true when all the access functions of A are affine or
3367 constant with respect to LOOP_NEST. */
3370 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3371 const struct loop
*loop_nest
)
3374 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3377 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
3378 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3379 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3385 /* Initializes an equation for an OMEGA problem using the information
3386 contained in the ACCESS_FUN. Returns true when the operation
3389 PB is the omega constraint system.
3390 EQ is the number of the equation to be initialized.
3391 OFFSET is used for shifting the variables names in the constraints:
3392 a constrain is composed of 2 * the number of variables surrounding
3393 dependence accesses. OFFSET is set either to 0 for the first n variables,
3394 then it is set to n.
3395 ACCESS_FUN is expected to be an affine chrec. */
3398 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3399 unsigned int offset
, tree access_fun
,
3400 struct data_dependence_relation
*ddr
)
3402 switch (TREE_CODE (access_fun
))
3404 case POLYNOMIAL_CHREC
:
3406 tree left
= CHREC_LEFT (access_fun
);
3407 tree right
= CHREC_RIGHT (access_fun
);
3408 int var
= CHREC_VARIABLE (access_fun
);
3411 if (TREE_CODE (right
) != INTEGER_CST
)
3414 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3415 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3417 /* Compute the innermost loop index. */
3418 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3421 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3422 += int_cst_value (right
);
3424 switch (TREE_CODE (left
))
3426 case POLYNOMIAL_CHREC
:
3427 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3430 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3439 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3447 /* As explained in the comments preceding init_omega_for_ddr, we have
3448 to set up a system for each loop level, setting outer loops
3449 variation to zero, and current loop variation to positive or zero.
3450 Save each lexico positive distance vector. */
3453 omega_extract_distance_vectors (omega_pb pb
,
3454 struct data_dependence_relation
*ddr
)
3458 struct loop
*loopi
, *loopj
;
3459 enum omega_result res
;
3461 /* Set a new problem for each loop in the nest. The basis is the
3462 problem that we have initialized until now. On top of this we
3463 add new constraints. */
3464 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3465 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3468 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3469 DDR_NB_LOOPS (ddr
));
3471 omega_copy_problem (copy
, pb
);
3473 /* For all the outer loops "loop_j", add "dj = 0". */
3475 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3477 eq
= omega_add_zero_eq (copy
, omega_black
);
3478 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3481 /* For "loop_i", add "0 <= di". */
3482 geq
= omega_add_zero_geq (copy
, omega_black
);
3483 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3485 /* Reduce the constraint system, and test that the current
3486 problem is feasible. */
3487 res
= omega_simplify_problem (copy
);
3488 if (res
== omega_false
3489 || res
== omega_unknown
3490 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3493 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3494 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3496 dist
= copy
->subs
[eq
].coef
[0];
3502 /* Reinitialize problem... */
3503 omega_copy_problem (copy
, pb
);
3505 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3507 eq
= omega_add_zero_eq (copy
, omega_black
);
3508 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3511 /* ..., but this time "di = 1". */
3512 eq
= omega_add_zero_eq (copy
, omega_black
);
3513 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3514 copy
->eqs
[eq
].coef
[0] = -1;
3516 res
= omega_simplify_problem (copy
);
3517 if (res
== omega_false
3518 || res
== omega_unknown
3519 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3522 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3523 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3525 dist
= copy
->subs
[eq
].coef
[0];
3531 /* Save the lexicographically positive distance vector. */
3534 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3535 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3539 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3540 if (copy
->subs
[eq
].key
> 0)
3542 dist
= copy
->subs
[eq
].coef
[0];
3543 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3546 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3547 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3549 save_dist_v (ddr
, dist_v
);
3550 save_dir_v (ddr
, dir_v
);
3554 omega_free_problem (copy
);
3558 /* This is called for each subscript of a tuple of data references:
3559 insert an equality for representing the conflicts. */
3562 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3563 struct data_dependence_relation
*ddr
,
3564 omega_pb pb
, bool *maybe_dependent
)
3567 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3568 TREE_TYPE (access_fun_b
));
3569 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3570 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3571 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3573 /* When the fun_a - fun_b is not constant, the dependence is not
3574 captured by the classic distance vector representation. */
3575 if (TREE_CODE (difference
) != INTEGER_CST
)
3579 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3581 /* There is no dependence. */
3582 *maybe_dependent
= false;
3586 fun_b
= chrec_fold_multiply (type
, fun_b
, integer_minus_one_node
);
3588 eq
= omega_add_zero_eq (pb
, omega_black
);
3589 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3590 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3591 /* There is probably a dependence, but the system of
3592 constraints cannot be built: answer "don't know". */
3596 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3597 && !int_divides_p (lambda_vector_gcd
3598 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3599 2 * DDR_NB_LOOPS (ddr
)),
3600 pb
->eqs
[eq
].coef
[0]))
3602 /* There is no dependence. */
3603 *maybe_dependent
= false;
3610 /* Helper function, same as init_omega_for_ddr but specialized for
3611 data references A and B. */
3614 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3615 struct data_dependence_relation
*ddr
,
3616 omega_pb pb
, bool *maybe_dependent
)
3621 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3623 /* Insert an equality per subscript. */
3624 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3626 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3627 ddr
, pb
, maybe_dependent
))
3629 else if (*maybe_dependent
== false)
3631 /* There is no dependence. */
3632 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3637 /* Insert inequalities: constraints corresponding to the iteration
3638 domain, i.e. the loops surrounding the references "loop_x" and
3639 the distance variables "dx". The layout of the OMEGA
3640 representation is as follows:
3641 - coef[0] is the constant
3642 - coef[1..nb_loops] are the protected variables that will not be
3643 removed by the solver: the "dx"
3644 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3646 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3647 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3649 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3652 ineq
= omega_add_zero_geq (pb
, omega_black
);
3653 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3655 /* 0 <= loop_x + dx */
3656 ineq
= omega_add_zero_geq (pb
, omega_black
);
3657 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3658 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3662 /* loop_x <= nb_iters */
3663 ineq
= omega_add_zero_geq (pb
, omega_black
);
3664 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3665 pb
->geqs
[ineq
].coef
[0] = nbi
;
3667 /* loop_x + dx <= nb_iters */
3668 ineq
= omega_add_zero_geq (pb
, omega_black
);
3669 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3670 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3671 pb
->geqs
[ineq
].coef
[0] = nbi
;
3673 /* A step "dx" bigger than nb_iters is not feasible, so
3674 add "0 <= nb_iters + dx", */
3675 ineq
= omega_add_zero_geq (pb
, omega_black
);
3676 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3677 pb
->geqs
[ineq
].coef
[0] = nbi
;
3678 /* and "dx <= nb_iters". */
3679 ineq
= omega_add_zero_geq (pb
, omega_black
);
3680 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3681 pb
->geqs
[ineq
].coef
[0] = nbi
;
3685 omega_extract_distance_vectors (pb
, ddr
);
3690 /* Sets up the Omega dependence problem for the data dependence
3691 relation DDR. Returns false when the constraint system cannot be
3692 built, ie. when the test answers "don't know". Returns true
3693 otherwise, and when independence has been proved (using one of the
3694 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3695 set MAYBE_DEPENDENT to true.
3697 Example: for setting up the dependence system corresponding to the
3698 conflicting accesses
3703 | ... A[2*j, 2*(i + j)]
3707 the following constraints come from the iteration domain:
3714 where di, dj are the distance variables. The constraints
3715 representing the conflicting elements are:
3718 i + 1 = 2 * (i + di + j + dj)
3720 For asking that the resulting distance vector (di, dj) be
3721 lexicographically positive, we insert the constraint "di >= 0". If
3722 "di = 0" in the solution, we fix that component to zero, and we
3723 look at the inner loops: we set a new problem where all the outer
3724 loop distances are zero, and fix this inner component to be
3725 positive. When one of the components is positive, we save that
3726 distance, and set a new problem where the distance on this loop is
3727 zero, searching for other distances in the inner loops. Here is
3728 the classic example that illustrates that we have to set for each
3729 inner loop a new problem:
3737 we have to save two distances (1, 0) and (0, 1).
3739 Given two array references, refA and refB, we have to set the
3740 dependence problem twice, refA vs. refB and refB vs. refA, and we
3741 cannot do a single test, as refB might occur before refA in the
3742 inner loops, and the contrary when considering outer loops: ex.
3747 | T[{1,+,1}_2][{1,+,1}_1] // refA
3748 | T[{2,+,1}_2][{0,+,1}_1] // refB
3753 refB touches the elements in T before refA, and thus for the same
3754 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3755 but for successive loop_0 iterations, we have (1, -1, 1)
3757 The Omega solver expects the distance variables ("di" in the
3758 previous example) to come first in the constraint system (as
3759 variables to be protected, or "safe" variables), the constraint
3760 system is built using the following layout:
3762 "cst | distance vars | index vars".
3766 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3767 bool *maybe_dependent
)
3772 *maybe_dependent
= true;
3774 if (same_access_functions (ddr
))
3777 lambda_vector dir_v
;
3779 /* Save the 0 vector. */
3780 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3781 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3782 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3783 dir_v
[j
] = dir_equal
;
3784 save_dir_v (ddr
, dir_v
);
3786 /* Save the dependences carried by outer loops. */
3787 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3788 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3790 omega_free_problem (pb
);
3794 /* Omega expects the protected variables (those that have to be kept
3795 after elimination) to appear first in the constraint system.
3796 These variables are the distance variables. In the following
3797 initialization we declare NB_LOOPS safe variables, and the total
3798 number of variables for the constraint system is 2*NB_LOOPS. */
3799 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3800 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3802 omega_free_problem (pb
);
3804 /* Stop computation if not decidable, or no dependence. */
3805 if (res
== false || *maybe_dependent
== false)
3808 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3809 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3811 omega_free_problem (pb
);
3816 /* Return true when DDR contains the same information as that stored
3817 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3820 ddr_consistent_p (FILE *file
,
3821 struct data_dependence_relation
*ddr
,
3822 VEC (lambda_vector
, heap
) *dist_vects
,
3823 VEC (lambda_vector
, heap
) *dir_vects
)
3827 /* If dump_file is set, output there. */
3828 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3831 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3833 lambda_vector b_dist_v
;
3834 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3835 VEC_length (lambda_vector
, dist_vects
),
3836 DDR_NUM_DIST_VECTS (ddr
));
3838 fprintf (file
, "Banerjee dist vectors:\n");
3839 for (i
= 0; VEC_iterate (lambda_vector
, dist_vects
, i
, b_dist_v
); i
++)
3840 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3842 fprintf (file
, "Omega dist vectors:\n");
3843 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3844 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3846 fprintf (file
, "data dependence relation:\n");
3847 dump_data_dependence_relation (file
, ddr
);
3849 fprintf (file
, ")\n");
3853 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3855 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3856 VEC_length (lambda_vector
, dir_vects
),
3857 DDR_NUM_DIR_VECTS (ddr
));
3861 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3863 lambda_vector a_dist_v
;
3864 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3866 /* Distance vectors are not ordered in the same way in the DDR
3867 and in the DIST_VECTS: search for a matching vector. */
3868 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, a_dist_v
); j
++)
3869 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3872 if (j
== VEC_length (lambda_vector
, dist_vects
))
3874 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3875 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3876 fprintf (file
, "not found in Omega dist vectors:\n");
3877 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3878 fprintf (file
, "data dependence relation:\n");
3879 dump_data_dependence_relation (file
, ddr
);
3880 fprintf (file
, ")\n");
3884 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3886 lambda_vector a_dir_v
;
3887 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3889 /* Direction vectors are not ordered in the same way in the DDR
3890 and in the DIR_VECTS: search for a matching vector. */
3891 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, a_dir_v
); j
++)
3892 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3895 if (j
== VEC_length (lambda_vector
, dist_vects
))
3897 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3898 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3899 fprintf (file
, "not found in Omega dir vectors:\n");
3900 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3901 fprintf (file
, "data dependence relation:\n");
3902 dump_data_dependence_relation (file
, ddr
);
3903 fprintf (file
, ")\n");
3910 /* This computes the affine dependence relation between A and B with
3911 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3912 independence between two accesses, while CHREC_DONT_KNOW is used
3913 for representing the unknown relation.
3915 Note that it is possible to stop the computation of the dependence
3916 relation the first time we detect a CHREC_KNOWN element for a given
3920 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3921 struct loop
*loop_nest
)
3923 struct data_reference
*dra
= DDR_A (ddr
);
3924 struct data_reference
*drb
= DDR_B (ddr
);
3926 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3928 fprintf (dump_file
, "(compute_affine_dependence\n");
3929 fprintf (dump_file
, " (stmt_a = \n");
3930 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, 0);
3931 fprintf (dump_file
, ")\n (stmt_b = \n");
3932 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, 0);
3933 fprintf (dump_file
, ")\n");
3936 /* Analyze only when the dependence relation is not yet known. */
3937 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
3938 && !DDR_SELF_REFERENCE (ddr
))
3940 dependence_stats
.num_dependence_tests
++;
3942 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3943 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3945 if (flag_check_data_deps
)
3947 /* Compute the dependences using the first algorithm. */
3948 subscript_dependence_tester (ddr
, loop_nest
);
3950 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3952 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3953 dump_data_dependence_relation (dump_file
, ddr
);
3956 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3958 bool maybe_dependent
;
3959 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3961 /* Save the result of the first DD analyzer. */
3962 dist_vects
= DDR_DIST_VECTS (ddr
);
3963 dir_vects
= DDR_DIR_VECTS (ddr
);
3965 /* Reset the information. */
3966 DDR_DIST_VECTS (ddr
) = NULL
;
3967 DDR_DIR_VECTS (ddr
) = NULL
;
3969 /* Compute the same information using Omega. */
3970 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3971 goto csys_dont_know
;
3973 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3975 fprintf (dump_file
, "Omega Analyzer\n");
3976 dump_data_dependence_relation (dump_file
, ddr
);
3979 /* Check that we get the same information. */
3980 if (maybe_dependent
)
3981 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3986 subscript_dependence_tester (ddr
, loop_nest
);
3989 /* As a last case, if the dependence cannot be determined, or if
3990 the dependence is considered too difficult to determine, answer
3995 dependence_stats
.num_dependence_undetermined
++;
3997 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3999 fprintf (dump_file
, "Data ref a:\n");
4000 dump_data_reference (dump_file
, dra
);
4001 fprintf (dump_file
, "Data ref b:\n");
4002 dump_data_reference (dump_file
, drb
);
4003 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
4005 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4009 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4010 fprintf (dump_file
, ")\n");
4013 /* This computes the dependence relation for the same data
4014 reference into DDR. */
4017 compute_self_dependence (struct data_dependence_relation
*ddr
)
4020 struct subscript
*subscript
;
4022 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
4025 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
4028 if (SUB_CONFLICTS_IN_A (subscript
))
4029 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
4030 if (SUB_CONFLICTS_IN_B (subscript
))
4031 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
4033 /* The accessed index overlaps for each iteration. */
4034 SUB_CONFLICTS_IN_A (subscript
)
4035 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
4036 SUB_CONFLICTS_IN_B (subscript
)
4037 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
4038 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
4041 /* The distance vector is the zero vector. */
4042 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4043 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4046 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4047 the data references in DATAREFS, in the LOOP_NEST. When
4048 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4052 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
4053 VEC (ddr_p
, heap
) **dependence_relations
,
4054 VEC (loop_p
, heap
) *loop_nest
,
4055 bool compute_self_and_rr
)
4057 struct data_dependence_relation
*ddr
;
4058 struct data_reference
*a
, *b
;
4061 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4062 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
4063 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
4065 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4066 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4068 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
4071 if (compute_self_and_rr
)
4072 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4074 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4075 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4076 compute_self_dependence (ddr
);
4080 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4081 true if STMT clobbers memory, false otherwise. */
4084 get_references_in_stmt (gimple stmt
, VEC (data_ref_loc
, heap
) **references
)
4086 bool clobbers_memory
= false;
4089 enum gimple_code stmt_code
= gimple_code (stmt
);
4093 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4094 Calls have side-effects, except those to const or pure
4096 if ((stmt_code
== GIMPLE_CALL
4097 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4098 || (stmt_code
== GIMPLE_ASM
4099 && gimple_asm_volatile_p (stmt
)))
4100 clobbers_memory
= true;
4102 if (!gimple_vuse (stmt
))
4103 return clobbers_memory
;
4105 if (stmt_code
== GIMPLE_ASSIGN
)
4108 op0
= gimple_assign_lhs_ptr (stmt
);
4109 op1
= gimple_assign_rhs1_ptr (stmt
);
4112 || (REFERENCE_CLASS_P (*op1
)
4113 && (base
= get_base_address (*op1
))
4114 && TREE_CODE (base
) != SSA_NAME
))
4116 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4118 ref
->is_read
= true;
4122 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4124 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4126 ref
->is_read
= false;
4129 else if (stmt_code
== GIMPLE_CALL
)
4131 unsigned i
, n
= gimple_call_num_args (stmt
);
4133 for (i
= 0; i
< n
; i
++)
4135 op0
= gimple_call_arg_ptr (stmt
, i
);
4138 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4140 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4142 ref
->is_read
= true;
4147 return clobbers_memory
;
4150 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4151 reference, returns false, otherwise returns true. NEST is the outermost
4152 loop of the loop nest in which the references should be analyzed. */
4155 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4156 VEC (data_reference_p
, heap
) **datarefs
)
4159 VEC (data_ref_loc
, heap
) *references
;
4162 data_reference_p dr
;
4164 if (get_references_in_stmt (stmt
, &references
))
4166 VEC_free (data_ref_loc
, heap
, references
);
4170 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
4172 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4173 gcc_assert (dr
!= NULL
);
4175 /* FIXME -- data dependence analysis does not work correctly for objects
4176 with invariant addresses in loop nests. Let us fail here until the
4177 problem is fixed. */
4178 if (dr_address_invariant_p (dr
) && nest
)
4181 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4182 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
4187 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4189 VEC_free (data_ref_loc
, heap
, references
);
4193 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4194 reference, returns false, otherwise returns true. NEST is the outermost
4195 loop of the loop nest in which the references should be analyzed. */
4198 graphite_find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4199 VEC (data_reference_p
, heap
) **datarefs
)
4202 VEC (data_ref_loc
, heap
) *references
;
4205 data_reference_p dr
;
4207 if (get_references_in_stmt (stmt
, &references
))
4209 VEC_free (data_ref_loc
, heap
, references
);
4213 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
4215 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4216 gcc_assert (dr
!= NULL
);
4217 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4220 VEC_free (data_ref_loc
, heap
, references
);
4224 /* Search the data references in LOOP, and record the information into
4225 DATAREFS. Returns chrec_dont_know when failing to analyze a
4226 difficult case, returns NULL_TREE otherwise. */
4229 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4230 VEC (data_reference_p
, heap
) **datarefs
)
4232 gimple_stmt_iterator bsi
;
4234 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4236 gimple stmt
= gsi_stmt (bsi
);
4238 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4240 struct data_reference
*res
;
4241 res
= XCNEW (struct data_reference
);
4242 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4244 return chrec_dont_know
;
4251 /* Search the data references in LOOP, and record the information into
4252 DATAREFS. Returns chrec_dont_know when failing to analyze a
4253 difficult case, returns NULL_TREE otherwise.
4255 TODO: This function should be made smarter so that it can handle address
4256 arithmetic as if they were array accesses, etc. */
4259 find_data_references_in_loop (struct loop
*loop
,
4260 VEC (data_reference_p
, heap
) **datarefs
)
4262 basic_block bb
, *bbs
;
4265 bbs
= get_loop_body_in_dom_order (loop
);
4267 for (i
= 0; i
< loop
->num_nodes
; i
++)
4271 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4274 return chrec_dont_know
;
4282 /* Recursive helper function. */
4285 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4287 /* Inner loops of the nest should not contain siblings. Example:
4288 when there are two consecutive loops,
4299 the dependence relation cannot be captured by the distance
4304 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4306 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4310 /* Return false when the LOOP is not well nested. Otherwise return
4311 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4312 contain the loops from the outermost to the innermost, as they will
4313 appear in the classic distance vector. */
4316 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4318 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4320 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4324 /* Returns true when the data dependences have been computed, false otherwise.
4325 Given a loop nest LOOP, the following vectors are returned:
4326 DATAREFS is initialized to all the array elements contained in this loop,
4327 DEPENDENCE_RELATIONS contains the relations between the data references.
4328 Compute read-read and self relations if
4329 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4332 compute_data_dependences_for_loop (struct loop
*loop
,
4333 bool compute_self_and_read_read_dependences
,
4334 VEC (data_reference_p
, heap
) **datarefs
,
4335 VEC (ddr_p
, heap
) **dependence_relations
)
4338 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4340 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4342 /* If the loop nest is not well formed, or one of the data references
4343 is not computable, give up without spending time to compute other
4346 || !find_loop_nest (loop
, &vloops
)
4347 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4349 struct data_dependence_relation
*ddr
;
4351 /* Insert a single relation into dependence_relations:
4353 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4354 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4358 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4359 compute_self_and_read_read_dependences
);
4361 if (dump_file
&& (dump_flags
& TDF_STATS
))
4363 fprintf (dump_file
, "Dependence tester statistics:\n");
4365 fprintf (dump_file
, "Number of dependence tests: %d\n",
4366 dependence_stats
.num_dependence_tests
);
4367 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4368 dependence_stats
.num_dependence_dependent
);
4369 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4370 dependence_stats
.num_dependence_independent
);
4371 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4372 dependence_stats
.num_dependence_undetermined
);
4374 fprintf (dump_file
, "Number of subscript tests: %d\n",
4375 dependence_stats
.num_subscript_tests
);
4376 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4377 dependence_stats
.num_subscript_undetermined
);
4378 fprintf (dump_file
, "Number of same subscript function: %d\n",
4379 dependence_stats
.num_same_subscript_function
);
4381 fprintf (dump_file
, "Number of ziv tests: %d\n",
4382 dependence_stats
.num_ziv
);
4383 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4384 dependence_stats
.num_ziv_dependent
);
4385 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4386 dependence_stats
.num_ziv_independent
);
4387 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4388 dependence_stats
.num_ziv_unimplemented
);
4390 fprintf (dump_file
, "Number of siv tests: %d\n",
4391 dependence_stats
.num_siv
);
4392 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4393 dependence_stats
.num_siv_dependent
);
4394 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4395 dependence_stats
.num_siv_independent
);
4396 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4397 dependence_stats
.num_siv_unimplemented
);
4399 fprintf (dump_file
, "Number of miv tests: %d\n",
4400 dependence_stats
.num_miv
);
4401 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4402 dependence_stats
.num_miv_dependent
);
4403 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4404 dependence_stats
.num_miv_independent
);
4405 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4406 dependence_stats
.num_miv_unimplemented
);
4412 /* Returns true when the data dependences for the basic block BB have been
4413 computed, false otherwise.
4414 DATAREFS is initialized to all the array elements contained in this basic
4415 block, DEPENDENCE_RELATIONS contains the relations between the data
4416 references. Compute read-read and self relations if
4417 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4419 compute_data_dependences_for_bb (basic_block bb
,
4420 bool compute_self_and_read_read_dependences
,
4421 VEC (data_reference_p
, heap
) **datarefs
,
4422 VEC (ddr_p
, heap
) **dependence_relations
)
4424 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4427 compute_all_dependences (*datarefs
, dependence_relations
, NULL
,
4428 compute_self_and_read_read_dependences
);
4432 /* Entry point (for testing only). Analyze all the data references
4433 and the dependence relations in LOOP.
4435 The data references are computed first.
4437 A relation on these nodes is represented by a complete graph. Some
4438 of the relations could be of no interest, thus the relations can be
4441 In the following function we compute all the relations. This is
4442 just a first implementation that is here for:
4443 - for showing how to ask for the dependence relations,
4444 - for the debugging the whole dependence graph,
4445 - for the dejagnu testcases and maintenance.
4447 It is possible to ask only for a part of the graph, avoiding to
4448 compute the whole dependence graph. The computed dependences are
4449 stored in a knowledge base (KB) such that later queries don't
4450 recompute the same information. The implementation of this KB is
4451 transparent to the optimizer, and thus the KB can be changed with a
4452 more efficient implementation, or the KB could be disabled. */
4454 analyze_all_data_dependences (struct loop
*loop
)
4457 int nb_data_refs
= 10;
4458 VEC (data_reference_p
, heap
) *datarefs
=
4459 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4460 VEC (ddr_p
, heap
) *dependence_relations
=
4461 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4463 /* Compute DDs on the whole function. */
4464 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4465 &dependence_relations
);
4469 dump_data_dependence_relations (dump_file
, dependence_relations
);
4470 fprintf (dump_file
, "\n\n");
4472 if (dump_flags
& TDF_DETAILS
)
4473 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4475 if (dump_flags
& TDF_STATS
)
4477 unsigned nb_top_relations
= 0;
4478 unsigned nb_bot_relations
= 0;
4479 unsigned nb_chrec_relations
= 0;
4480 struct data_dependence_relation
*ddr
;
4482 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4484 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4487 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4491 nb_chrec_relations
++;
4494 gather_stats_on_scev_database ();
4498 free_dependence_relations (dependence_relations
);
4499 free_data_refs (datarefs
);
4502 /* Computes all the data dependences and check that the results of
4503 several analyzers are the same. */
4506 tree_check_data_deps (void)
4509 struct loop
*loop_nest
;
4511 FOR_EACH_LOOP (li
, loop_nest
, 0)
4512 analyze_all_data_dependences (loop_nest
);
4515 /* Free the memory used by a data dependence relation DDR. */
4518 free_dependence_relation (struct data_dependence_relation
*ddr
)
4523 if (DDR_SUBSCRIPTS (ddr
))
4524 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4525 if (DDR_DIST_VECTS (ddr
))
4526 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4527 if (DDR_DIR_VECTS (ddr
))
4528 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4533 /* Free the memory used by the data dependence relations from
4534 DEPENDENCE_RELATIONS. */
4537 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4540 struct data_dependence_relation
*ddr
;
4541 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4543 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4547 if (loop_nest
== NULL
)
4548 loop_nest
= DDR_LOOP_NEST (ddr
);
4550 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4551 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4552 free_dependence_relation (ddr
);
4556 VEC_free (loop_p
, heap
, loop_nest
);
4557 VEC_free (ddr_p
, heap
, dependence_relations
);
4560 /* Free the memory used by the data references from DATAREFS. */
4563 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4566 struct data_reference
*dr
;
4568 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4570 VEC_free (data_reference_p
, heap
, datarefs
);
4575 /* Dump vertex I in RDG to FILE. */
4578 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4580 struct vertex
*v
= &(rdg
->vertices
[i
]);
4581 struct graph_edge
*e
;
4583 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4584 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4585 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4588 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4589 fprintf (file
, " %d", e
->src
);
4591 fprintf (file
, ") (out:");
4594 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4595 fprintf (file
, " %d", e
->dest
);
4597 fprintf (file
, ") \n");
4598 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4599 fprintf (file
, ")\n");
4602 /* Call dump_rdg_vertex on stderr. */
4605 debug_rdg_vertex (struct graph
*rdg
, int i
)
4607 dump_rdg_vertex (stderr
, rdg
, i
);
4610 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4611 dumped vertices to that bitmap. */
4613 void dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4617 fprintf (file
, "(%d\n", c
);
4619 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4620 if (rdg
->vertices
[i
].component
== c
)
4623 bitmap_set_bit (dumped
, i
);
4625 dump_rdg_vertex (file
, rdg
, i
);
4628 fprintf (file
, ")\n");
4631 /* Call dump_rdg_vertex on stderr. */
4634 debug_rdg_component (struct graph
*rdg
, int c
)
4636 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4639 /* Dump the reduced dependence graph RDG to FILE. */
4642 dump_rdg (FILE *file
, struct graph
*rdg
)
4645 bitmap dumped
= BITMAP_ALLOC (NULL
);
4647 fprintf (file
, "(rdg\n");
4649 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4650 if (!bitmap_bit_p (dumped
, i
))
4651 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4653 fprintf (file
, ")\n");
4654 BITMAP_FREE (dumped
);
4657 /* Call dump_rdg on stderr. */
4660 debug_rdg (struct graph
*rdg
)
4662 dump_rdg (stderr
, rdg
);
4665 /* This structure is used for recording the mapping statement index in
4668 struct GTY(()) rdg_vertex_info
4674 /* Returns the index of STMT in RDG. */
4677 rdg_vertex_for_stmt (struct graph
*rdg
, gimple stmt
)
4679 struct rdg_vertex_info rvi
, *slot
;
4682 slot
= (struct rdg_vertex_info
*) htab_find (rdg
->indices
, &rvi
);
4690 /* Creates an edge in RDG for each distance vector from DDR. The
4691 order that we keep track of in the RDG is the order in which
4692 statements have to be executed. */
4695 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4697 struct graph_edge
*e
;
4699 data_reference_p dra
= DDR_A (ddr
);
4700 data_reference_p drb
= DDR_B (ddr
);
4701 unsigned level
= ddr_dependence_level (ddr
);
4703 /* For non scalar dependences, when the dependence is REVERSED,
4704 statement B has to be executed before statement A. */
4706 && !DDR_REVERSED_P (ddr
))
4708 data_reference_p tmp
= dra
;
4713 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4714 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4716 if (va
< 0 || vb
< 0)
4719 e
= add_edge (rdg
, va
, vb
);
4720 e
->data
= XNEW (struct rdg_edge
);
4722 RDGE_LEVEL (e
) = level
;
4723 RDGE_RELATION (e
) = ddr
;
4725 /* Determines the type of the data dependence. */
4726 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4727 RDGE_TYPE (e
) = input_dd
;
4728 else if (!DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4729 RDGE_TYPE (e
) = output_dd
;
4730 else if (!DR_IS_READ (dra
) && DR_IS_READ (drb
))
4731 RDGE_TYPE (e
) = flow_dd
;
4732 else if (DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4733 RDGE_TYPE (e
) = anti_dd
;
4736 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4737 the index of DEF in RDG. */
4740 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4742 use_operand_p imm_use_p
;
4743 imm_use_iterator iterator
;
4745 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4747 struct graph_edge
*e
;
4748 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4753 e
= add_edge (rdg
, idef
, use
);
4754 e
->data
= XNEW (struct rdg_edge
);
4755 RDGE_TYPE (e
) = flow_dd
;
4756 RDGE_RELATION (e
) = NULL
;
4760 /* Creates the edges of the reduced dependence graph RDG. */
4763 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4766 struct data_dependence_relation
*ddr
;
4767 def_operand_p def_p
;
4770 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
4771 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4772 create_rdg_edge_for_ddr (rdg
, ddr
);
4774 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4775 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4777 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4780 /* Build the vertices of the reduced dependence graph RDG. */
4783 create_rdg_vertices (struct graph
*rdg
, VEC (gimple
, heap
) *stmts
)
4788 for (i
= 0; VEC_iterate (gimple
, stmts
, i
, stmt
); i
++)
4790 VEC (data_ref_loc
, heap
) *references
;
4792 struct vertex
*v
= &(rdg
->vertices
[i
]);
4793 struct rdg_vertex_info
*rvi
= XNEW (struct rdg_vertex_info
);
4794 struct rdg_vertex_info
**slot
;
4798 slot
= (struct rdg_vertex_info
**) htab_find_slot (rdg
->indices
, rvi
, INSERT
);
4805 v
->data
= XNEW (struct rdg_vertex
);
4806 RDG_STMT (rdg
, i
) = stmt
;
4808 RDG_MEM_WRITE_STMT (rdg
, i
) = false;
4809 RDG_MEM_READS_STMT (rdg
, i
) = false;
4810 if (gimple_code (stmt
) == GIMPLE_PHI
)
4813 get_references_in_stmt (stmt
, &references
);
4814 for (j
= 0; VEC_iterate (data_ref_loc
, references
, j
, ref
); j
++)
4816 RDG_MEM_WRITE_STMT (rdg
, i
) = true;
4818 RDG_MEM_READS_STMT (rdg
, i
) = true;
4820 VEC_free (data_ref_loc
, heap
, references
);
4824 /* Initialize STMTS with all the statements of LOOP. When
4825 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4826 which we discover statements is important as
4827 generate_loops_for_partition is using the same traversal for
4828 identifying statements. */
4831 stmts_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4834 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4836 for (i
= 0; i
< loop
->num_nodes
; i
++)
4838 basic_block bb
= bbs
[i
];
4839 gimple_stmt_iterator bsi
;
4842 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4843 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4845 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4847 stmt
= gsi_stmt (bsi
);
4848 if (gimple_code (stmt
) != GIMPLE_LABEL
)
4849 VEC_safe_push (gimple
, heap
, *stmts
, stmt
);
4856 /* Returns true when all the dependences are computable. */
4859 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
4864 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4865 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4871 /* Computes a hash function for element ELT. */
4874 hash_stmt_vertex_info (const void *elt
)
4876 const struct rdg_vertex_info
*const rvi
=
4877 (const struct rdg_vertex_info
*) elt
;
4878 gimple stmt
= rvi
->stmt
;
4880 return htab_hash_pointer (stmt
);
4883 /* Compares database elements E1 and E2. */
4886 eq_stmt_vertex_info (const void *e1
, const void *e2
)
4888 const struct rdg_vertex_info
*elt1
= (const struct rdg_vertex_info
*) e1
;
4889 const struct rdg_vertex_info
*elt2
= (const struct rdg_vertex_info
*) e2
;
4891 return elt1
->stmt
== elt2
->stmt
;
4894 /* Free the element E. */
4897 hash_stmt_vertex_del (void *e
)
4902 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4903 statement of the loop nest, and one edge per data dependence or
4904 scalar dependence. */
4907 build_empty_rdg (int n_stmts
)
4909 int nb_data_refs
= 10;
4910 struct graph
*rdg
= new_graph (n_stmts
);
4912 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4913 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4917 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4918 statement of the loop nest, and one edge per data dependence or
4919 scalar dependence. */
4922 build_rdg (struct loop
*loop
)
4924 int nb_data_refs
= 10;
4925 struct graph
*rdg
= NULL
;
4926 VEC (ddr_p
, heap
) *dependence_relations
;
4927 VEC (data_reference_p
, heap
) *datarefs
;
4928 VEC (gimple
, heap
) *stmts
= VEC_alloc (gimple
, heap
, nb_data_refs
);
4930 dependence_relations
= VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
) ;
4931 datarefs
= VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4932 compute_data_dependences_for_loop (loop
,
4935 &dependence_relations
);
4937 if (!known_dependences_p (dependence_relations
))
4939 free_dependence_relations (dependence_relations
);
4940 free_data_refs (datarefs
);
4941 VEC_free (gimple
, heap
, stmts
);
4946 stmts_from_loop (loop
, &stmts
);
4947 rdg
= build_empty_rdg (VEC_length (gimple
, stmts
));
4949 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4950 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4951 create_rdg_vertices (rdg
, stmts
);
4952 create_rdg_edges (rdg
, dependence_relations
);
4954 VEC_free (gimple
, heap
, stmts
);
4958 /* Free the reduced dependence graph RDG. */
4961 free_rdg (struct graph
*rdg
)
4965 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4966 free (rdg
->vertices
[i
].data
);
4968 htab_delete (rdg
->indices
);
4972 /* Initialize STMTS with all the statements of LOOP that contain a
4976 stores_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4979 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4981 for (i
= 0; i
< loop
->num_nodes
; i
++)
4983 basic_block bb
= bbs
[i
];
4984 gimple_stmt_iterator bsi
;
4986 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4987 if (gimple_vdef (gsi_stmt (bsi
)))
4988 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4994 /* For a data reference REF, return the declaration of its base
4995 address or NULL_TREE if the base is not determined. */
4998 ref_base_address (gimple stmt
, data_ref_loc
*ref
)
5000 tree base
= NULL_TREE
;
5002 struct data_reference
*dr
= XCNEW (struct data_reference
);
5004 DR_STMT (dr
) = stmt
;
5005 DR_REF (dr
) = *ref
->pos
;
5006 dr_analyze_innermost (dr
);
5007 base_address
= DR_BASE_ADDRESS (dr
);
5012 switch (TREE_CODE (base_address
))
5015 base
= TREE_OPERAND (base_address
, 0);
5019 base
= base_address
;
5028 /* Determines whether the statement from vertex V of the RDG has a
5029 definition used outside the loop that contains this statement. */
5032 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
5034 gimple stmt
= RDG_STMT (rdg
, v
);
5035 struct loop
*loop
= loop_containing_stmt (stmt
);
5036 use_operand_p imm_use_p
;
5037 imm_use_iterator iterator
;
5039 def_operand_p def_p
;
5044 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
5046 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
5048 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)
5056 /* Determines whether statements S1 and S2 access to similar memory
5057 locations. Two memory accesses are considered similar when they
5058 have the same base address declaration, i.e. when their
5059 ref_base_address is the same. */
5062 have_similar_memory_accesses (gimple s1
, gimple s2
)
5066 VEC (data_ref_loc
, heap
) *refs1
, *refs2
;
5067 data_ref_loc
*ref1
, *ref2
;
5069 get_references_in_stmt (s1
, &refs1
);
5070 get_references_in_stmt (s2
, &refs2
);
5072 for (i
= 0; VEC_iterate (data_ref_loc
, refs1
, i
, ref1
); i
++)
5074 tree base1
= ref_base_address (s1
, ref1
);
5077 for (j
= 0; VEC_iterate (data_ref_loc
, refs2
, j
, ref2
); j
++)
5078 if (base1
== ref_base_address (s2
, ref2
))
5086 VEC_free (data_ref_loc
, heap
, refs1
);
5087 VEC_free (data_ref_loc
, heap
, refs2
);
5091 /* Helper function for the hashtab. */
5094 have_similar_memory_accesses_1 (const void *s1
, const void *s2
)
5096 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple
) s1
),
5097 CONST_CAST_GIMPLE ((const_gimple
) s2
));
5100 /* Helper function for the hashtab. */
5103 ref_base_address_1 (const void *s
)
5105 gimple stmt
= CONST_CAST_GIMPLE ((const_gimple
) s
);
5107 VEC (data_ref_loc
, heap
) *refs
;
5111 get_references_in_stmt (stmt
, &refs
);
5113 for (i
= 0; VEC_iterate (data_ref_loc
, refs
, i
, ref
); i
++)
5116 res
= htab_hash_pointer (ref_base_address (stmt
, ref
));
5120 VEC_free (data_ref_loc
, heap
, refs
);
5124 /* Try to remove duplicated write data references from STMTS. */
5127 remove_similar_memory_refs (VEC (gimple
, heap
) **stmts
)
5131 htab_t seen
= htab_create (VEC_length (gimple
, *stmts
), ref_base_address_1
,
5132 have_similar_memory_accesses_1
, NULL
);
5134 for (i
= 0; VEC_iterate (gimple
, *stmts
, i
, stmt
); )
5138 slot
= htab_find_slot (seen
, stmt
, INSERT
);
5141 VEC_ordered_remove (gimple
, *stmts
, i
);
5144 *slot
= (void *) stmt
;
5152 /* Returns the index of PARAMETER in the parameters vector of the
5153 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5156 access_matrix_get_index_for_parameter (tree parameter
,
5157 struct access_matrix
*access_matrix
)
5160 VEC (tree
,heap
) *lambda_parameters
= AM_PARAMETERS (access_matrix
);
5161 tree lambda_parameter
;
5163 for (i
= 0; VEC_iterate (tree
, lambda_parameters
, i
, lambda_parameter
); i
++)
5164 if (lambda_parameter
== parameter
)
5165 return i
+ AM_NB_INDUCTION_VARS (access_matrix
);