1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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"
84 /* These RTL headers are needed for basic-block.h. */
86 #include "basic-block.h"
87 #include "diagnostic.h"
88 #include "tree-flow.h"
89 #include "tree-dump.h"
92 #include "tree-chrec.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
*);
128 /* Returns true iff A divides B. */
131 tree_fold_divides_p (tree a
, tree b
)
133 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
134 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
135 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
, 0));
138 /* Returns true iff A divides B. */
141 int_divides_p (int a
, int b
)
143 return ((b
% a
) == 0);
148 /* Dump into FILE all the data references from DATAREFS. */
151 dump_data_references (FILE *file
, VEC (data_reference_p
, heap
) *datarefs
)
154 struct data_reference
*dr
;
156 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
157 dump_data_reference (file
, dr
);
160 /* Dump into FILE all the dependence relations from DDRS. */
163 dump_data_dependence_relations (FILE *file
,
164 VEC (ddr_p
, heap
) *ddrs
)
167 struct data_dependence_relation
*ddr
;
169 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
170 dump_data_dependence_relation (file
, ddr
);
173 /* Dump function for a DATA_REFERENCE structure. */
176 dump_data_reference (FILE *outf
,
177 struct data_reference
*dr
)
181 fprintf (outf
, "(Data Ref: \n stmt: ");
182 print_generic_stmt (outf
, DR_STMT (dr
), 0);
183 fprintf (outf
, " ref: ");
184 print_generic_stmt (outf
, DR_REF (dr
), 0);
185 fprintf (outf
, " base_object: ");
186 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
188 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
190 fprintf (outf
, " Access function %d: ", i
);
191 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
193 fprintf (outf
, ")\n");
196 /* Dumps the affine function described by FN to the file OUTF. */
199 dump_affine_function (FILE *outf
, affine_fn fn
)
204 print_generic_expr (outf
, VEC_index (tree
, fn
, 0), TDF_SLIM
);
205 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
207 fprintf (outf
, " + ");
208 print_generic_expr (outf
, coef
, TDF_SLIM
);
209 fprintf (outf
, " * x_%u", i
);
213 /* Dumps the conflict function CF to the file OUTF. */
216 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
220 if (cf
->n
== NO_DEPENDENCE
)
221 fprintf (outf
, "no dependence\n");
222 else if (cf
->n
== NOT_KNOWN
)
223 fprintf (outf
, "not known\n");
226 for (i
= 0; i
< cf
->n
; i
++)
229 dump_affine_function (outf
, cf
->fns
[i
]);
230 fprintf (outf
, "]\n");
235 /* Dump function for a SUBSCRIPT structure. */
238 dump_subscript (FILE *outf
, struct subscript
*subscript
)
240 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
242 fprintf (outf
, "\n (subscript \n");
243 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
244 dump_conflict_function (outf
, cf
);
245 if (CF_NONTRIVIAL_P (cf
))
247 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
248 fprintf (outf
, " last_conflict: ");
249 print_generic_stmt (outf
, last_iteration
, 0);
252 cf
= SUB_CONFLICTS_IN_B (subscript
);
253 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
254 dump_conflict_function (outf
, cf
);
255 if (CF_NONTRIVIAL_P (cf
))
257 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
258 fprintf (outf
, " last_conflict: ");
259 print_generic_stmt (outf
, last_iteration
, 0);
262 fprintf (outf
, " (Subscript distance: ");
263 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
264 fprintf (outf
, " )\n");
265 fprintf (outf
, " )\n");
268 /* Print the classic direction vector DIRV to OUTF. */
271 print_direction_vector (FILE *outf
,
277 for (eq
= 0; eq
< length
; eq
++)
279 enum data_dependence_direction dir
= dirv
[eq
];
284 fprintf (outf
, " +");
287 fprintf (outf
, " -");
290 fprintf (outf
, " =");
292 case dir_positive_or_equal
:
293 fprintf (outf
, " +=");
295 case dir_positive_or_negative
:
296 fprintf (outf
, " +-");
298 case dir_negative_or_equal
:
299 fprintf (outf
, " -=");
302 fprintf (outf
, " *");
305 fprintf (outf
, "indep");
309 fprintf (outf
, "\n");
312 /* Print a vector of direction vectors. */
315 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
321 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
322 print_direction_vector (outf
, v
, length
);
325 /* Print a vector of distance vectors. */
328 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
334 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
335 print_lambda_vector (outf
, v
, length
);
341 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
343 dump_data_dependence_relation (stderr
, ddr
);
346 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
349 dump_data_dependence_relation (FILE *outf
,
350 struct data_dependence_relation
*ddr
)
352 struct data_reference
*dra
, *drb
;
356 fprintf (outf
, "(Data Dep: \n");
357 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
358 fprintf (outf
, " (don't know)\n");
360 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
361 fprintf (outf
, " (no dependence)\n");
363 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
368 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
370 fprintf (outf
, " access_fn_A: ");
371 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
372 fprintf (outf
, " access_fn_B: ");
373 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
374 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
377 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
378 fprintf (outf
, " loop nest: (");
379 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
380 fprintf (outf
, "%d ", loopi
->num
);
381 fprintf (outf
, ")\n");
383 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
385 fprintf (outf
, " distance_vector: ");
386 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
390 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
392 fprintf (outf
, " direction_vector: ");
393 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
398 fprintf (outf
, ")\n");
401 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
404 dump_data_dependence_direction (FILE *file
,
405 enum data_dependence_direction dir
)
421 case dir_positive_or_negative
:
422 fprintf (file
, "+-");
425 case dir_positive_or_equal
:
426 fprintf (file
, "+=");
429 case dir_negative_or_equal
:
430 fprintf (file
, "-=");
442 /* Dumps the distance and direction vectors in FILE. DDRS contains
443 the dependence relations, and VECT_SIZE is the size of the
444 dependence vectors, or in other words the number of loops in the
448 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
451 struct data_dependence_relation
*ddr
;
454 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
455 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
457 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
459 fprintf (file
, "DISTANCE_V (");
460 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
461 fprintf (file
, ")\n");
464 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
466 fprintf (file
, "DIRECTION_V (");
467 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
468 fprintf (file
, ")\n");
472 fprintf (file
, "\n\n");
475 /* Dumps the data dependence relations DDRS in FILE. */
478 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
481 struct data_dependence_relation
*ddr
;
483 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
484 dump_data_dependence_relation (file
, ddr
);
486 fprintf (file
, "\n\n");
489 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
490 will be ssizetype. */
493 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
495 tree type
= TREE_TYPE (exp
), otype
;
502 otype
= TREE_TYPE (exp
);
503 code
= TREE_CODE (exp
);
508 *var
= build_int_cst (type
, 0);
509 *off
= fold_convert (ssizetype
, exp
);
512 case POINTER_PLUS_EXPR
:
517 split_constant_offset (TREE_OPERAND (exp
, 0), &var0
, &off0
);
518 split_constant_offset (TREE_OPERAND (exp
, 1), &var1
, &off1
);
519 *var
= fold_convert (type
, fold_build2 (TREE_CODE (exp
), otype
,
521 *off
= size_binop (code
, off0
, off1
);
525 off1
= TREE_OPERAND (exp
, 1);
526 if (TREE_CODE (off1
) != INTEGER_CST
)
529 split_constant_offset (TREE_OPERAND (exp
, 0), &var0
, &off0
);
530 *var
= fold_convert (type
, fold_build2 (MULT_EXPR
, otype
,
532 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, off1
));
537 tree op
, base
, poffset
;
538 HOST_WIDE_INT pbitsize
, pbitpos
;
539 enum machine_mode pmode
;
540 int punsignedp
, pvolatilep
;
542 op
= TREE_OPERAND (exp
, 0);
543 if (!handled_component_p (op
))
546 base
= get_inner_reference (op
, &pbitsize
, &pbitpos
, &poffset
,
547 &pmode
, &punsignedp
, &pvolatilep
, false);
549 if (pbitpos
% BITS_PER_UNIT
!= 0)
551 base
= build_fold_addr_expr (base
);
552 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
556 split_constant_offset (poffset
, &poffset
, &off1
);
557 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
558 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
),
560 fold_convert (TREE_TYPE (base
), poffset
));
563 *var
= fold_convert (type
, base
);
572 *off
= ssize_int (0);
575 /* Returns the address ADDR of an object in a canonical shape (without nop
576 casts, and with type of pointer to the object). */
579 canonicalize_base_object_address (tree addr
)
585 /* The base address may be obtained by casting from integer, in that case
587 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
590 if (TREE_CODE (addr
) != ADDR_EXPR
)
593 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
596 /* Analyzes the behavior of the memory reference DR in the innermost loop that
600 dr_analyze_innermost (struct data_reference
*dr
)
602 tree stmt
= DR_STMT (dr
);
603 struct loop
*loop
= loop_containing_stmt (stmt
);
604 tree ref
= DR_REF (dr
);
605 HOST_WIDE_INT pbitsize
, pbitpos
;
607 enum machine_mode pmode
;
608 int punsignedp
, pvolatilep
;
609 affine_iv base_iv
, offset_iv
;
610 tree init
, dinit
, step
;
612 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
613 fprintf (dump_file
, "analyze_innermost: ");
615 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
616 &pmode
, &punsignedp
, &pvolatilep
, false);
617 gcc_assert (base
!= NULL_TREE
);
619 if (pbitpos
% BITS_PER_UNIT
!= 0)
621 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
622 fprintf (dump_file
, "failed: bit offset alignment.\n");
626 base
= build_fold_addr_expr (base
);
627 if (!simple_iv (loop
, stmt
, base
, &base_iv
, false))
629 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
630 fprintf (dump_file
, "failed: evolution of base is not affine.\n");
635 offset_iv
.base
= ssize_int (0);
636 offset_iv
.step
= ssize_int (0);
638 else if (!simple_iv (loop
, stmt
, poffset
, &offset_iv
, false))
640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
641 fprintf (dump_file
, "failed: evolution of offset is not affine.\n");
645 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
646 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
647 init
= size_binop (PLUS_EXPR
, init
, dinit
);
648 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
649 init
= size_binop (PLUS_EXPR
, init
, dinit
);
651 step
= size_binop (PLUS_EXPR
,
652 fold_convert (ssizetype
, base_iv
.step
),
653 fold_convert (ssizetype
, offset_iv
.step
));
655 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
657 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
661 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
664 fprintf (dump_file
, "success.\n");
667 /* Determines the base object and the list of indices of memory reference
668 DR, analyzed in loop nest NEST. */
671 dr_analyze_indices (struct data_reference
*dr
, struct loop
*nest
)
673 tree stmt
= DR_STMT (dr
);
674 struct loop
*loop
= loop_containing_stmt (stmt
);
675 VEC (tree
, heap
) *access_fns
= NULL
;
676 tree ref
= unshare_expr (DR_REF (dr
)), aref
= ref
, op
;
677 tree base
, off
, access_fn
;
679 while (handled_component_p (aref
))
681 if (TREE_CODE (aref
) == ARRAY_REF
)
683 op
= TREE_OPERAND (aref
, 1);
684 access_fn
= analyze_scalar_evolution (loop
, op
);
685 access_fn
= resolve_mixers (nest
, access_fn
);
686 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
688 TREE_OPERAND (aref
, 1) = build_int_cst (TREE_TYPE (op
), 0);
691 aref
= TREE_OPERAND (aref
, 0);
694 if (INDIRECT_REF_P (aref
))
696 op
= TREE_OPERAND (aref
, 0);
697 access_fn
= analyze_scalar_evolution (loop
, op
);
698 access_fn
= resolve_mixers (nest
, access_fn
);
699 base
= initial_condition (access_fn
);
700 split_constant_offset (base
, &base
, &off
);
701 access_fn
= chrec_replace_initial_condition (access_fn
,
702 fold_convert (TREE_TYPE (base
), off
));
704 TREE_OPERAND (aref
, 0) = base
;
705 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
708 DR_BASE_OBJECT (dr
) = ref
;
709 DR_ACCESS_FNS (dr
) = access_fns
;
712 /* Extracts the alias analysis information from the memory reference DR. */
715 dr_analyze_alias (struct data_reference
*dr
)
717 tree stmt
= DR_STMT (dr
);
718 tree ref
= DR_REF (dr
);
719 tree base
= get_base_address (ref
), addr
, smt
= NULL_TREE
;
726 else if (INDIRECT_REF_P (base
))
728 addr
= TREE_OPERAND (base
, 0);
729 if (TREE_CODE (addr
) == SSA_NAME
)
731 smt
= symbol_mem_tag (SSA_NAME_VAR (addr
));
732 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
736 DR_SYMBOL_TAG (dr
) = smt
;
737 if (smt
&& var_can_have_subvars (smt
))
738 DR_SUBVARS (dr
) = get_subvars_for_var (smt
);
740 vops
= BITMAP_ALLOC (NULL
);
741 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, it
, SSA_OP_VIRTUAL_USES
)
743 bitmap_set_bit (vops
, DECL_UID (SSA_NAME_VAR (op
)));
749 /* Returns true if the address of DR is invariant. */
752 dr_address_invariant_p (struct data_reference
*dr
)
757 for (i
= 0; VEC_iterate (tree
, DR_ACCESS_FNS (dr
), i
, idx
); i
++)
758 if (tree_contains_chrecs (idx
, NULL
))
764 /* Frees data reference DR. */
767 free_data_ref (data_reference_p dr
)
769 BITMAP_FREE (DR_VOPS (dr
));
770 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
774 /* Analyzes memory reference MEMREF accessed in STMT. The reference
775 is read if IS_READ is true, write otherwise. Returns the
776 data_reference description of MEMREF. NEST is the outermost loop of the
777 loop nest in that the reference should be analyzed. */
779 struct data_reference
*
780 create_data_ref (struct loop
*nest
, tree memref
, tree stmt
, bool is_read
)
782 struct data_reference
*dr
;
784 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
786 fprintf (dump_file
, "Creating dr for ");
787 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
788 fprintf (dump_file
, "\n");
791 dr
= XCNEW (struct data_reference
);
793 DR_REF (dr
) = memref
;
794 DR_IS_READ (dr
) = is_read
;
796 dr_analyze_innermost (dr
);
797 dr_analyze_indices (dr
, nest
);
798 dr_analyze_alias (dr
);
800 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
802 fprintf (dump_file
, "\tbase_address: ");
803 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
804 fprintf (dump_file
, "\n\toffset from base address: ");
805 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
806 fprintf (dump_file
, "\n\tconstant offset from base address: ");
807 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
808 fprintf (dump_file
, "\n\tstep: ");
809 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
810 fprintf (dump_file
, "\n\taligned to: ");
811 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
812 fprintf (dump_file
, "\n\tbase_object: ");
813 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
814 fprintf (dump_file
, "\n\tsymbol tag: ");
815 print_generic_expr (dump_file
, DR_SYMBOL_TAG (dr
), TDF_SLIM
);
816 fprintf (dump_file
, "\n");
822 /* Returns true if FNA == FNB. */
825 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
827 unsigned i
, n
= VEC_length (tree
, fna
);
829 if (n
!= VEC_length (tree
, fnb
))
832 for (i
= 0; i
< n
; i
++)
833 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
834 VEC_index (tree
, fnb
, i
), 0))
840 /* If all the functions in CF are the same, returns one of them,
841 otherwise returns NULL. */
844 common_affine_function (conflict_function
*cf
)
849 if (!CF_NONTRIVIAL_P (cf
))
854 for (i
= 1; i
< cf
->n
; i
++)
855 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
861 /* Returns the base of the affine function FN. */
864 affine_function_base (affine_fn fn
)
866 return VEC_index (tree
, fn
, 0);
869 /* Returns true if FN is a constant. */
872 affine_function_constant_p (affine_fn fn
)
877 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
878 if (!integer_zerop (coef
))
884 /* Returns true if FN is the zero constant function. */
887 affine_function_zero_p (affine_fn fn
)
889 return (integer_zerop (affine_function_base (fn
))
890 && affine_function_constant_p (fn
));
893 /* Applies operation OP on affine functions FNA and FNB, and returns the
897 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
903 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
905 n
= VEC_length (tree
, fna
);
906 m
= VEC_length (tree
, fnb
);
910 n
= VEC_length (tree
, fnb
);
911 m
= VEC_length (tree
, fna
);
914 ret
= VEC_alloc (tree
, heap
, m
);
915 for (i
= 0; i
< n
; i
++)
916 VEC_quick_push (tree
, ret
,
917 fold_build2 (op
, integer_type_node
,
918 VEC_index (tree
, fna
, i
),
919 VEC_index (tree
, fnb
, i
)));
921 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
922 VEC_quick_push (tree
, ret
,
923 fold_build2 (op
, integer_type_node
,
924 coef
, integer_zero_node
));
925 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
926 VEC_quick_push (tree
, ret
,
927 fold_build2 (op
, integer_type_node
,
928 integer_zero_node
, coef
));
933 /* Returns the sum of affine functions FNA and FNB. */
936 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
938 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
941 /* Returns the difference of affine functions FNA and FNB. */
944 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
946 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
949 /* Frees affine function FN. */
952 affine_fn_free (affine_fn fn
)
954 VEC_free (tree
, heap
, fn
);
957 /* Determine for each subscript in the data dependence relation DDR
961 compute_subscript_distance (struct data_dependence_relation
*ddr
)
963 conflict_function
*cf_a
, *cf_b
;
964 affine_fn fn_a
, fn_b
, diff
;
966 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
970 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
972 struct subscript
*subscript
;
974 subscript
= DDR_SUBSCRIPT (ddr
, i
);
975 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
976 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
978 fn_a
= common_affine_function (cf_a
);
979 fn_b
= common_affine_function (cf_b
);
982 SUB_DISTANCE (subscript
) = chrec_dont_know
;
985 diff
= affine_fn_minus (fn_a
, fn_b
);
987 if (affine_function_constant_p (diff
))
988 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
990 SUB_DISTANCE (subscript
) = chrec_dont_know
;
992 affine_fn_free (diff
);
997 /* Returns the conflict function for "unknown". */
999 static conflict_function
*
1000 conflict_fn_not_known (void)
1002 conflict_function
*fn
= XCNEW (conflict_function
);
1008 /* Returns the conflict function for "independent". */
1010 static conflict_function
*
1011 conflict_fn_no_dependence (void)
1013 conflict_function
*fn
= XCNEW (conflict_function
);
1014 fn
->n
= NO_DEPENDENCE
;
1019 /* Returns true if the address of OBJ is invariant in LOOP. */
1022 object_address_invariant_in_loop_p (struct loop
*loop
, tree obj
)
1024 while (handled_component_p (obj
))
1026 if (TREE_CODE (obj
) == ARRAY_REF
)
1028 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1029 need to check the stride and the lower bound of the reference. */
1030 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1032 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1036 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1038 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1042 obj
= TREE_OPERAND (obj
, 0);
1045 if (!INDIRECT_REF_P (obj
))
1048 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1052 /* Returns true if A and B are accesses to different objects, or to different
1053 fields of the same object. */
1056 disjoint_objects_p (tree a
, tree b
)
1058 tree base_a
, base_b
;
1059 VEC (tree
, heap
) *comp_a
= NULL
, *comp_b
= NULL
;
1062 base_a
= get_base_address (a
);
1063 base_b
= get_base_address (b
);
1067 && base_a
!= base_b
)
1070 if (!operand_equal_p (base_a
, base_b
, 0))
1073 /* Compare the component references of A and B. We must start from the inner
1074 ones, so record them to the vector first. */
1075 while (handled_component_p (a
))
1077 VEC_safe_push (tree
, heap
, comp_a
, a
);
1078 a
= TREE_OPERAND (a
, 0);
1080 while (handled_component_p (b
))
1082 VEC_safe_push (tree
, heap
, comp_b
, b
);
1083 b
= TREE_OPERAND (b
, 0);
1089 if (VEC_length (tree
, comp_a
) == 0
1090 || VEC_length (tree
, comp_b
) == 0)
1093 a
= VEC_pop (tree
, comp_a
);
1094 b
= VEC_pop (tree
, comp_b
);
1096 /* Real and imaginary part of a variable do not alias. */
1097 if ((TREE_CODE (a
) == REALPART_EXPR
1098 && TREE_CODE (b
) == IMAGPART_EXPR
)
1099 || (TREE_CODE (a
) == IMAGPART_EXPR
1100 && TREE_CODE (b
) == REALPART_EXPR
))
1106 if (TREE_CODE (a
) != TREE_CODE (b
))
1109 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1110 DR_BASE_OBJECT are always zero. */
1111 if (TREE_CODE (a
) == ARRAY_REF
)
1113 else if (TREE_CODE (a
) == COMPONENT_REF
)
1115 if (operand_equal_p (TREE_OPERAND (a
, 1), TREE_OPERAND (b
, 1), 0))
1118 /* Different fields of unions may overlap. */
1119 base_a
= TREE_OPERAND (a
, 0);
1120 if (TREE_CODE (TREE_TYPE (base_a
)) == UNION_TYPE
)
1123 /* Different fields of structures cannot. */
1131 VEC_free (tree
, heap
, comp_a
);
1132 VEC_free (tree
, heap
, comp_b
);
1137 /* Returns false if we can prove that data references A and B do not alias,
1141 dr_may_alias_p (struct data_reference
*a
, struct data_reference
*b
)
1143 tree addr_a
= DR_BASE_ADDRESS (a
);
1144 tree addr_b
= DR_BASE_ADDRESS (b
);
1145 tree type_a
, type_b
;
1146 tree decl_a
= NULL_TREE
, decl_b
= NULL_TREE
;
1148 /* If the sets of virtual operands are disjoint, the memory references do not
1150 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
1153 /* If the accessed objects are disjoint, the memory references do not
1155 if (disjoint_objects_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
)))
1158 if (!addr_a
|| !addr_b
)
1161 /* If the references are based on different static objects, they cannot alias
1162 (PTA should be able to disambiguate such accesses, but often it fails to,
1163 since currently we cannot distinguish between pointer and offset in pointer
1165 if (TREE_CODE (addr_a
) == ADDR_EXPR
1166 && TREE_CODE (addr_b
) == ADDR_EXPR
)
1167 return TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0);
1169 /* An instruction writing through a restricted pointer is "independent" of any
1170 instruction reading or writing through a different restricted pointer,
1171 in the same block/scope. */
1173 type_a
= TREE_TYPE (addr_a
);
1174 type_b
= TREE_TYPE (addr_b
);
1175 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
1177 if (TREE_CODE (addr_a
) == SSA_NAME
)
1178 decl_a
= SSA_NAME_VAR (addr_a
);
1179 if (TREE_CODE (addr_b
) == SSA_NAME
)
1180 decl_b
= SSA_NAME_VAR (addr_b
);
1182 if (TYPE_RESTRICT (type_a
) && TYPE_RESTRICT (type_b
)
1183 && (!DR_IS_READ (a
) || !DR_IS_READ (b
))
1184 && decl_a
&& DECL_P (decl_a
)
1185 && decl_b
&& DECL_P (decl_b
)
1187 && TREE_CODE (DECL_CONTEXT (decl_a
)) == FUNCTION_DECL
1188 && DECL_CONTEXT (decl_a
) == DECL_CONTEXT (decl_b
))
1194 /* Initialize a data dependence relation between data accesses A and
1195 B. NB_LOOPS is the number of loops surrounding the references: the
1196 size of the classic distance/direction vectors. */
1198 static struct data_dependence_relation
*
1199 initialize_data_dependence_relation (struct data_reference
*a
,
1200 struct data_reference
*b
,
1201 VEC (loop_p
, heap
) *loop_nest
)
1203 struct data_dependence_relation
*res
;
1206 res
= XNEW (struct data_dependence_relation
);
1209 DDR_LOOP_NEST (res
) = NULL
;
1211 if (a
== NULL
|| b
== NULL
)
1213 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1217 /* If the data references do not alias, then they are independent. */
1218 if (!dr_may_alias_p (a
, b
))
1220 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1224 /* If the references do not access the same object, we do not know
1225 whether they alias or not. */
1226 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1228 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1232 /* If the base of the object is not invariant in the loop nest, we cannot
1233 analyze it. TODO -- in fact, it would suffice to record that there may
1234 be arbitrary dependences in the loops where the base object varies. */
1235 if (!object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1236 DR_BASE_OBJECT (a
)))
1238 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1242 gcc_assert (DR_NUM_DIMENSIONS (a
) == DR_NUM_DIMENSIONS (b
));
1244 DDR_AFFINE_P (res
) = true;
1245 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1246 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1247 DDR_LOOP_NEST (res
) = loop_nest
;
1248 DDR_INNER_LOOP (res
) = 0;
1249 DDR_DIR_VECTS (res
) = NULL
;
1250 DDR_DIST_VECTS (res
) = NULL
;
1252 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1254 struct subscript
*subscript
;
1256 subscript
= XNEW (struct subscript
);
1257 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1258 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1259 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1260 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1261 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1267 /* Frees memory used by the conflict function F. */
1270 free_conflict_function (conflict_function
*f
)
1274 if (CF_NONTRIVIAL_P (f
))
1276 for (i
= 0; i
< f
->n
; i
++)
1277 affine_fn_free (f
->fns
[i
]);
1282 /* Frees memory used by SUBSCRIPTS. */
1285 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1290 for (i
= 0; VEC_iterate (subscript_p
, subscripts
, i
, s
); i
++)
1292 free_conflict_function (s
->conflicting_iterations_in_a
);
1293 free_conflict_function (s
->conflicting_iterations_in_b
);
1295 VEC_free (subscript_p
, heap
, subscripts
);
1298 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1302 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1305 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1307 fprintf (dump_file
, "(dependence classified: ");
1308 print_generic_expr (dump_file
, chrec
, 0);
1309 fprintf (dump_file
, ")\n");
1312 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1313 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1316 /* The dependence relation DDR cannot be represented by a distance
1320 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1323 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1325 DDR_AFFINE_P (ddr
) = false;
1330 /* This section contains the classic Banerjee tests. */
1332 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1333 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1336 ziv_subscript_p (tree chrec_a
,
1339 return (evolution_function_is_constant_p (chrec_a
)
1340 && evolution_function_is_constant_p (chrec_b
));
1343 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1344 variable, i.e., if the SIV (Single Index Variable) test is true. */
1347 siv_subscript_p (tree chrec_a
,
1350 if ((evolution_function_is_constant_p (chrec_a
)
1351 && evolution_function_is_univariate_p (chrec_b
))
1352 || (evolution_function_is_constant_p (chrec_b
)
1353 && evolution_function_is_univariate_p (chrec_a
)))
1356 if (evolution_function_is_univariate_p (chrec_a
)
1357 && evolution_function_is_univariate_p (chrec_b
))
1359 switch (TREE_CODE (chrec_a
))
1361 case POLYNOMIAL_CHREC
:
1362 switch (TREE_CODE (chrec_b
))
1364 case POLYNOMIAL_CHREC
:
1365 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1380 /* Creates a conflict function with N dimensions. The affine functions
1381 in each dimension follow. */
1383 static conflict_function
*
1384 conflict_fn (unsigned n
, ...)
1387 conflict_function
*ret
= XCNEW (conflict_function
);
1390 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1394 for (i
= 0; i
< n
; i
++)
1395 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1401 /* Returns constant affine function with value CST. */
1404 affine_fn_cst (tree cst
)
1406 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1407 VEC_quick_push (tree
, fn
, cst
);
1411 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1414 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1416 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1419 gcc_assert (dim
> 0);
1420 VEC_quick_push (tree
, fn
, cst
);
1421 for (i
= 1; i
< dim
; i
++)
1422 VEC_quick_push (tree
, fn
, integer_zero_node
);
1423 VEC_quick_push (tree
, fn
, coef
);
1427 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1428 *OVERLAPS_B are initialized to the functions that describe the
1429 relation between the elements accessed twice by CHREC_A and
1430 CHREC_B. For k >= 0, the following property is verified:
1432 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1435 analyze_ziv_subscript (tree chrec_a
,
1437 conflict_function
**overlaps_a
,
1438 conflict_function
**overlaps_b
,
1439 tree
*last_conflicts
)
1442 dependence_stats
.num_ziv
++;
1444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1445 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1447 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
1448 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
1449 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
1451 switch (TREE_CODE (difference
))
1454 if (integer_zerop (difference
))
1456 /* The difference is equal to zero: the accessed index
1457 overlaps for each iteration in the loop. */
1458 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1459 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1460 *last_conflicts
= chrec_dont_know
;
1461 dependence_stats
.num_ziv_dependent
++;
1465 /* The accesses do not overlap. */
1466 *overlaps_a
= conflict_fn_no_dependence ();
1467 *overlaps_b
= conflict_fn_no_dependence ();
1468 *last_conflicts
= integer_zero_node
;
1469 dependence_stats
.num_ziv_independent
++;
1474 /* We're not sure whether the indexes overlap. For the moment,
1475 conservatively answer "don't know". */
1476 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1477 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1479 *overlaps_a
= conflict_fn_not_known ();
1480 *overlaps_b
= conflict_fn_not_known ();
1481 *last_conflicts
= chrec_dont_know
;
1482 dependence_stats
.num_ziv_unimplemented
++;
1486 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1487 fprintf (dump_file
, ")\n");
1490 /* Sets NIT to the estimated number of executions of the statements in
1491 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1492 large as the number of iterations. If we have no reliable estimate,
1493 the function returns false, otherwise returns true. */
1496 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
1499 estimate_numbers_of_iterations_loop (loop
);
1502 if (!loop
->any_upper_bound
)
1505 *nit
= loop
->nb_iterations_upper_bound
;
1509 if (!loop
->any_estimate
)
1512 *nit
= loop
->nb_iterations_estimate
;
1518 /* Similar to estimated_loop_iterations, but returns the estimate only
1519 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1520 on the number of iterations of LOOP could not be derived, returns -1. */
1523 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
1526 HOST_WIDE_INT hwi_nit
;
1528 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1531 if (!double_int_fits_in_shwi_p (nit
))
1533 hwi_nit
= double_int_to_shwi (nit
);
1535 return hwi_nit
< 0 ? -1 : hwi_nit
;
1538 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1539 and only if it fits to the int type. If this is not the case, or the
1540 estimate on the number of iterations of LOOP could not be derived, returns
1544 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
1549 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1550 return chrec_dont_know
;
1552 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
1553 if (!double_int_fits_to_tree_p (type
, nit
))
1554 return chrec_dont_know
;
1556 return double_int_to_tree (type
, nit
);
1559 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1560 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1561 *OVERLAPS_B are initialized to the functions that describe the
1562 relation between the elements accessed twice by CHREC_A and
1563 CHREC_B. For k >= 0, the following property is verified:
1565 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1568 analyze_siv_subscript_cst_affine (tree chrec_a
,
1570 conflict_function
**overlaps_a
,
1571 conflict_function
**overlaps_b
,
1572 tree
*last_conflicts
)
1574 bool value0
, value1
, value2
;
1575 tree difference
, tmp
;
1577 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
1578 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
1579 difference
= chrec_fold_minus
1580 (integer_type_node
, initial_condition (chrec_b
), chrec_a
);
1582 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1585 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1587 dependence_stats
.num_siv_unimplemented
++;
1588 *overlaps_a
= conflict_fn_not_known ();
1589 *overlaps_b
= conflict_fn_not_known ();
1590 *last_conflicts
= chrec_dont_know
;
1595 if (value0
== false)
1597 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1599 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1600 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1602 *overlaps_a
= conflict_fn_not_known ();
1603 *overlaps_b
= conflict_fn_not_known ();
1604 *last_conflicts
= chrec_dont_know
;
1605 dependence_stats
.num_siv_unimplemented
++;
1614 chrec_b = {10, +, 1}
1617 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1619 HOST_WIDE_INT numiter
;
1620 struct loop
*loop
= get_chrec_loop (chrec_b
);
1622 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1623 tmp
= fold_build2 (EXACT_DIV_EXPR
, integer_type_node
,
1624 fold_build1 (ABS_EXPR
,
1627 CHREC_RIGHT (chrec_b
));
1628 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1629 *last_conflicts
= integer_one_node
;
1632 /* Perform weak-zero siv test to see if overlap is
1633 outside the loop bounds. */
1634 numiter
= estimated_loop_iterations_int (loop
, true);
1637 && compare_tree_int (tmp
, numiter
) > 0)
1639 free_conflict_function (*overlaps_a
);
1640 free_conflict_function (*overlaps_b
);
1641 *overlaps_a
= conflict_fn_no_dependence ();
1642 *overlaps_b
= conflict_fn_no_dependence ();
1643 *last_conflicts
= integer_zero_node
;
1644 dependence_stats
.num_siv_independent
++;
1647 dependence_stats
.num_siv_dependent
++;
1651 /* When the step does not divide the difference, there are
1655 *overlaps_a
= conflict_fn_no_dependence ();
1656 *overlaps_b
= conflict_fn_no_dependence ();
1657 *last_conflicts
= integer_zero_node
;
1658 dependence_stats
.num_siv_independent
++;
1667 chrec_b = {10, +, -1}
1669 In this case, chrec_a will not overlap with chrec_b. */
1670 *overlaps_a
= conflict_fn_no_dependence ();
1671 *overlaps_b
= conflict_fn_no_dependence ();
1672 *last_conflicts
= integer_zero_node
;
1673 dependence_stats
.num_siv_independent
++;
1680 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1683 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1685 *overlaps_a
= conflict_fn_not_known ();
1686 *overlaps_b
= conflict_fn_not_known ();
1687 *last_conflicts
= chrec_dont_know
;
1688 dependence_stats
.num_siv_unimplemented
++;
1693 if (value2
== false)
1697 chrec_b = {10, +, -1}
1699 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1701 HOST_WIDE_INT numiter
;
1702 struct loop
*loop
= get_chrec_loop (chrec_b
);
1704 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1705 tmp
= fold_build2 (EXACT_DIV_EXPR
,
1706 integer_type_node
, difference
,
1707 CHREC_RIGHT (chrec_b
));
1708 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1709 *last_conflicts
= integer_one_node
;
1711 /* Perform weak-zero siv test to see if overlap is
1712 outside the loop bounds. */
1713 numiter
= estimated_loop_iterations_int (loop
, true);
1716 && compare_tree_int (tmp
, numiter
) > 0)
1718 free_conflict_function (*overlaps_a
);
1719 free_conflict_function (*overlaps_b
);
1720 *overlaps_a
= conflict_fn_no_dependence ();
1721 *overlaps_b
= conflict_fn_no_dependence ();
1722 *last_conflicts
= integer_zero_node
;
1723 dependence_stats
.num_siv_independent
++;
1726 dependence_stats
.num_siv_dependent
++;
1730 /* When the step does not divide the difference, there
1734 *overlaps_a
= conflict_fn_no_dependence ();
1735 *overlaps_b
= conflict_fn_no_dependence ();
1736 *last_conflicts
= integer_zero_node
;
1737 dependence_stats
.num_siv_independent
++;
1747 In this case, chrec_a will not overlap with chrec_b. */
1748 *overlaps_a
= conflict_fn_no_dependence ();
1749 *overlaps_b
= conflict_fn_no_dependence ();
1750 *last_conflicts
= integer_zero_node
;
1751 dependence_stats
.num_siv_independent
++;
1759 /* Helper recursive function for initializing the matrix A. Returns
1760 the initial value of CHREC. */
1763 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1767 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1768 return int_cst_value (chrec
);
1770 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1771 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1774 #define FLOOR_DIV(x,y) ((x) / (y))
1776 /* Solves the special case of the Diophantine equation:
1777 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1779 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1780 number of iterations that loops X and Y run. The overlaps will be
1781 constructed as evolutions in dimension DIM. */
1784 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1785 affine_fn
*overlaps_a
,
1786 affine_fn
*overlaps_b
,
1787 tree
*last_conflicts
, int dim
)
1789 if (((step_a
> 0 && step_b
> 0)
1790 || (step_a
< 0 && step_b
< 0)))
1792 int step_overlaps_a
, step_overlaps_b
;
1793 int gcd_steps_a_b
, last_conflict
, tau2
;
1795 gcd_steps_a_b
= gcd (step_a
, step_b
);
1796 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1797 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1799 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1800 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1801 last_conflict
= tau2
;
1803 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
1804 build_int_cst (NULL_TREE
,
1806 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
1807 build_int_cst (NULL_TREE
,
1809 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1814 *overlaps_a
= affine_fn_cst (integer_zero_node
);
1815 *overlaps_b
= affine_fn_cst (integer_zero_node
);
1816 *last_conflicts
= integer_zero_node
;
1820 /* Solves the special case of a Diophantine equation where CHREC_A is
1821 an affine bivariate function, and CHREC_B is an affine univariate
1822 function. For example,
1824 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1826 has the following overlapping functions:
1828 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1829 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1830 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1832 FORNOW: This is a specialized implementation for a case occurring in
1833 a common benchmark. Implement the general algorithm. */
1836 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1837 conflict_function
**overlaps_a
,
1838 conflict_function
**overlaps_b
,
1839 tree
*last_conflicts
)
1841 bool xz_p
, yz_p
, xyz_p
;
1842 int step_x
, step_y
, step_z
;
1843 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
1844 affine_fn overlaps_a_xz
, overlaps_b_xz
;
1845 affine_fn overlaps_a_yz
, overlaps_b_yz
;
1846 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
1847 affine_fn ova1
, ova2
, ovb
;
1848 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
1850 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
1851 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
1852 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
1854 niter_x
= estimated_loop_iterations_int
1855 (get_chrec_loop (CHREC_LEFT (chrec_a
)), true);
1856 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), true);
1857 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), true);
1859 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
1861 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1862 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
1864 *overlaps_a
= conflict_fn_not_known ();
1865 *overlaps_b
= conflict_fn_not_known ();
1866 *last_conflicts
= chrec_dont_know
;
1870 niter
= MIN (niter_x
, niter_z
);
1871 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
1874 &last_conflicts_xz
, 1);
1875 niter
= MIN (niter_y
, niter_z
);
1876 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
1879 &last_conflicts_yz
, 2);
1880 niter
= MIN (niter_x
, niter_z
);
1881 niter
= MIN (niter_y
, niter
);
1882 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
1885 &last_conflicts_xyz
, 3);
1887 xz_p
= !integer_zerop (last_conflicts_xz
);
1888 yz_p
= !integer_zerop (last_conflicts_yz
);
1889 xyz_p
= !integer_zerop (last_conflicts_xyz
);
1891 if (xz_p
|| yz_p
|| xyz_p
)
1893 ova1
= affine_fn_cst (integer_zero_node
);
1894 ova2
= affine_fn_cst (integer_zero_node
);
1895 ovb
= affine_fn_cst (integer_zero_node
);
1898 affine_fn t0
= ova1
;
1901 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
1902 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
1903 affine_fn_free (t0
);
1904 affine_fn_free (t2
);
1905 *last_conflicts
= last_conflicts_xz
;
1909 affine_fn t0
= ova2
;
1912 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
1913 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
1914 affine_fn_free (t0
);
1915 affine_fn_free (t2
);
1916 *last_conflicts
= last_conflicts_yz
;
1920 affine_fn t0
= ova1
;
1921 affine_fn t2
= ova2
;
1924 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
1925 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
1926 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
1927 affine_fn_free (t0
);
1928 affine_fn_free (t2
);
1929 affine_fn_free (t4
);
1930 *last_conflicts
= last_conflicts_xyz
;
1932 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
1933 *overlaps_b
= conflict_fn (1, ovb
);
1937 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1938 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1939 *last_conflicts
= integer_zero_node
;
1942 affine_fn_free (overlaps_a_xz
);
1943 affine_fn_free (overlaps_b_xz
);
1944 affine_fn_free (overlaps_a_yz
);
1945 affine_fn_free (overlaps_b_yz
);
1946 affine_fn_free (overlaps_a_xyz
);
1947 affine_fn_free (overlaps_b_xyz
);
1950 /* Determines the overlapping elements due to accesses CHREC_A and
1951 CHREC_B, that are affine functions. This function cannot handle
1952 symbolic evolution functions, ie. when initial conditions are
1953 parameters, because it uses lambda matrices of integers. */
1956 analyze_subscript_affine_affine (tree chrec_a
,
1958 conflict_function
**overlaps_a
,
1959 conflict_function
**overlaps_b
,
1960 tree
*last_conflicts
)
1962 unsigned nb_vars_a
, nb_vars_b
, dim
;
1963 int init_a
, init_b
, gamma
, gcd_alpha_beta
;
1965 lambda_matrix A
, U
, S
;
1967 if (eq_evolutions_p (chrec_a
, chrec_b
))
1969 /* The accessed index overlaps for each iteration in the
1971 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1972 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1973 *last_conflicts
= chrec_dont_know
;
1976 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1977 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
1979 /* For determining the initial intersection, we have to solve a
1980 Diophantine equation. This is the most time consuming part.
1982 For answering to the question: "Is there a dependence?" we have
1983 to prove that there exists a solution to the Diophantine
1984 equation, and that the solution is in the iteration domain,
1985 i.e. the solution is positive or zero, and that the solution
1986 happens before the upper bound loop.nb_iterations. Otherwise
1987 there is no dependence. This function outputs a description of
1988 the iterations that hold the intersections. */
1990 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
1991 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
1993 dim
= nb_vars_a
+ nb_vars_b
;
1994 U
= lambda_matrix_new (dim
, dim
);
1995 A
= lambda_matrix_new (dim
, 1);
1996 S
= lambda_matrix_new (dim
, 1);
1998 init_a
= initialize_matrix_A (A
, chrec_a
, 0, 1);
1999 init_b
= initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1);
2000 gamma
= init_b
- init_a
;
2002 /* Don't do all the hard work of solving the Diophantine equation
2003 when we already know the solution: for example,
2006 | gamma = 3 - 3 = 0.
2007 Then the first overlap occurs during the first iterations:
2008 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2012 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2015 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2018 niter_a
= estimated_loop_iterations_int
2019 (get_chrec_loop (chrec_a
), true);
2020 niter_b
= estimated_loop_iterations_int
2021 (get_chrec_loop (chrec_b
), true);
2022 if (niter_a
< 0 || niter_b
< 0)
2024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2025 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
2026 *overlaps_a
= conflict_fn_not_known ();
2027 *overlaps_b
= conflict_fn_not_known ();
2028 *last_conflicts
= chrec_dont_know
;
2029 goto end_analyze_subs_aa
;
2032 niter
= MIN (niter_a
, niter_b
);
2034 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2035 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2037 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2040 *overlaps_a
= conflict_fn (1, ova
);
2041 *overlaps_b
= conflict_fn (1, ovb
);
2044 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2045 compute_overlap_steps_for_affine_1_2
2046 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2048 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2049 compute_overlap_steps_for_affine_1_2
2050 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2054 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2055 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2056 *overlaps_a
= conflict_fn_not_known ();
2057 *overlaps_b
= conflict_fn_not_known ();
2058 *last_conflicts
= chrec_dont_know
;
2060 goto end_analyze_subs_aa
;
2064 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2069 lambda_matrix_row_negate (U
, dim
, 0);
2071 gcd_alpha_beta
= S
[0][0];
2073 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2074 but that is a quite strange case. Instead of ICEing, answer
2076 if (gcd_alpha_beta
== 0)
2078 *overlaps_a
= conflict_fn_not_known ();
2079 *overlaps_b
= conflict_fn_not_known ();
2080 *last_conflicts
= chrec_dont_know
;
2081 goto end_analyze_subs_aa
;
2084 /* The classic "gcd-test". */
2085 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2087 /* The "gcd-test" has determined that there is no integer
2088 solution, i.e. there is no dependence. */
2089 *overlaps_a
= conflict_fn_no_dependence ();
2090 *overlaps_b
= conflict_fn_no_dependence ();
2091 *last_conflicts
= integer_zero_node
;
2094 /* Both access functions are univariate. This includes SIV and MIV cases. */
2095 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2097 /* Both functions should have the same evolution sign. */
2098 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2099 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2101 /* The solutions are given by:
2103 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2106 For a given integer t. Using the following variables,
2108 | i0 = u11 * gamma / gcd_alpha_beta
2109 | j0 = u12 * gamma / gcd_alpha_beta
2116 | y0 = j0 + j1 * t. */
2120 /* X0 and Y0 are the first iterations for which there is a
2121 dependence. X0, Y0 are two solutions of the Diophantine
2122 equation: chrec_a (X0) = chrec_b (Y0). */
2124 int niter
, niter_a
, niter_b
;
2126 niter_a
= estimated_loop_iterations_int
2127 (get_chrec_loop (chrec_a
), true);
2128 niter_b
= estimated_loop_iterations_int
2129 (get_chrec_loop (chrec_b
), true);
2131 if (niter_a
< 0 || niter_b
< 0)
2133 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2134 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
2135 *overlaps_a
= conflict_fn_not_known ();
2136 *overlaps_b
= conflict_fn_not_known ();
2137 *last_conflicts
= chrec_dont_know
;
2138 goto end_analyze_subs_aa
;
2141 niter
= MIN (niter_a
, niter_b
);
2143 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2144 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2148 if ((i1
== 0 && i0
< 0)
2149 || (j1
== 0 && j0
< 0))
2151 /* There is no solution.
2152 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2153 falls in here, but for the moment we don't look at the
2154 upper bound of the iteration domain. */
2155 *overlaps_a
= conflict_fn_no_dependence ();
2156 *overlaps_b
= conflict_fn_no_dependence ();
2157 *last_conflicts
= integer_zero_node
;
2164 tau1
= CEIL (-i0
, i1
);
2165 tau2
= FLOOR_DIV (niter
- i0
, i1
);
2169 int last_conflict
, min_multiple
;
2170 tau1
= MAX (tau1
, CEIL (-j0
, j1
));
2171 tau2
= MIN (tau2
, FLOOR_DIV (niter
- j0
, j1
));
2173 x0
= i1
* tau1
+ i0
;
2174 y0
= j1
* tau1
+ j0
;
2176 /* At this point (x0, y0) is one of the
2177 solutions to the Diophantine equation. The
2178 next step has to compute the smallest
2179 positive solution: the first conflicts. */
2180 min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2181 x0
-= i1
* min_multiple
;
2182 y0
-= j1
* min_multiple
;
2184 tau1
= (x0
- i0
)/i1
;
2185 last_conflict
= tau2
- tau1
;
2187 /* If the overlap occurs outside of the bounds of the
2188 loop, there is no dependence. */
2189 if (x0
> niter
|| y0
> niter
)
2191 *overlaps_a
= conflict_fn_no_dependence ();
2192 *overlaps_b
= conflict_fn_no_dependence ();
2193 *last_conflicts
= integer_zero_node
;
2199 affine_fn_univar (build_int_cst (NULL_TREE
, x0
),
2201 build_int_cst (NULL_TREE
, i1
)));
2204 affine_fn_univar (build_int_cst (NULL_TREE
, y0
),
2206 build_int_cst (NULL_TREE
, j1
)));
2207 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2212 /* FIXME: For the moment, the upper bound of the
2213 iteration domain for j is not checked. */
2214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2215 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2216 *overlaps_a
= conflict_fn_not_known ();
2217 *overlaps_b
= conflict_fn_not_known ();
2218 *last_conflicts
= chrec_dont_know
;
2224 /* FIXME: For the moment, the upper bound of the
2225 iteration domain for i is not checked. */
2226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2227 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2228 *overlaps_a
= conflict_fn_not_known ();
2229 *overlaps_b
= conflict_fn_not_known ();
2230 *last_conflicts
= chrec_dont_know
;
2236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2237 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2238 *overlaps_a
= conflict_fn_not_known ();
2239 *overlaps_b
= conflict_fn_not_known ();
2240 *last_conflicts
= chrec_dont_know
;
2246 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2247 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2248 *overlaps_a
= conflict_fn_not_known ();
2249 *overlaps_b
= conflict_fn_not_known ();
2250 *last_conflicts
= chrec_dont_know
;
2253 end_analyze_subs_aa
:
2254 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2256 fprintf (dump_file
, " (overlaps_a = ");
2257 dump_conflict_function (dump_file
, *overlaps_a
);
2258 fprintf (dump_file
, ")\n (overlaps_b = ");
2259 dump_conflict_function (dump_file
, *overlaps_b
);
2260 fprintf (dump_file
, ")\n");
2261 fprintf (dump_file
, ")\n");
2265 /* Returns true when analyze_subscript_affine_affine can be used for
2266 determining the dependence relation between chrec_a and chrec_b,
2267 that contain symbols. This function modifies chrec_a and chrec_b
2268 such that the analysis result is the same, and such that they don't
2269 contain symbols, and then can safely be passed to the analyzer.
2271 Example: The analysis of the following tuples of evolutions produce
2272 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2275 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2276 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2280 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2282 tree diff
, type
, left_a
, left_b
, right_b
;
2284 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2285 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2286 /* FIXME: For the moment not handled. Might be refined later. */
2289 type
= chrec_type (*chrec_a
);
2290 left_a
= CHREC_LEFT (*chrec_a
);
2291 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL_TREE
);
2292 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2294 if (!evolution_function_is_constant_p (diff
))
2297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2298 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2300 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2301 diff
, CHREC_RIGHT (*chrec_a
));
2302 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL_TREE
);
2303 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2304 build_int_cst (type
, 0),
2309 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2310 *OVERLAPS_B are initialized to the functions that describe the
2311 relation between the elements accessed twice by CHREC_A and
2312 CHREC_B. For k >= 0, the following property is verified:
2314 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2317 analyze_siv_subscript (tree chrec_a
,
2319 conflict_function
**overlaps_a
,
2320 conflict_function
**overlaps_b
,
2321 tree
*last_conflicts
)
2323 dependence_stats
.num_siv
++;
2325 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2326 fprintf (dump_file
, "(analyze_siv_subscript \n");
2328 if (evolution_function_is_constant_p (chrec_a
)
2329 && evolution_function_is_affine_p (chrec_b
))
2330 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2331 overlaps_a
, overlaps_b
, last_conflicts
);
2333 else if (evolution_function_is_affine_p (chrec_a
)
2334 && evolution_function_is_constant_p (chrec_b
))
2335 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2336 overlaps_b
, overlaps_a
, last_conflicts
);
2338 else if (evolution_function_is_affine_p (chrec_a
)
2339 && evolution_function_is_affine_p (chrec_b
))
2341 if (!chrec_contains_symbols (chrec_a
)
2342 && !chrec_contains_symbols (chrec_b
))
2344 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2345 overlaps_a
, overlaps_b
,
2348 if (CF_NOT_KNOWN_P (*overlaps_a
)
2349 || CF_NOT_KNOWN_P (*overlaps_b
))
2350 dependence_stats
.num_siv_unimplemented
++;
2351 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2352 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2353 dependence_stats
.num_siv_independent
++;
2355 dependence_stats
.num_siv_dependent
++;
2357 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2360 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2361 overlaps_a
, overlaps_b
,
2363 /* FIXME: The number of iterations is a symbolic expression.
2364 Compute it properly. */
2365 *last_conflicts
= chrec_dont_know
;
2367 if (CF_NOT_KNOWN_P (*overlaps_a
)
2368 || CF_NOT_KNOWN_P (*overlaps_b
))
2369 dependence_stats
.num_siv_unimplemented
++;
2370 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2371 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2372 dependence_stats
.num_siv_independent
++;
2374 dependence_stats
.num_siv_dependent
++;
2377 goto siv_subscript_dontknow
;
2382 siv_subscript_dontknow
:;
2383 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2384 fprintf (dump_file
, "siv test failed: unimplemented.\n");
2385 *overlaps_a
= conflict_fn_not_known ();
2386 *overlaps_b
= conflict_fn_not_known ();
2387 *last_conflicts
= chrec_dont_know
;
2388 dependence_stats
.num_siv_unimplemented
++;
2391 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2392 fprintf (dump_file
, ")\n");
2395 /* Returns false if we can prove that the greatest common divisor of the steps
2396 of CHREC does not divide CST, false otherwise. */
2399 gcd_of_steps_may_divide_p (tree chrec
, tree cst
)
2401 HOST_WIDE_INT cd
= 0, val
;
2404 if (!host_integerp (cst
, 0))
2406 val
= tree_low_cst (cst
, 0);
2408 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2410 step
= CHREC_RIGHT (chrec
);
2411 if (!host_integerp (step
, 0))
2413 cd
= gcd (cd
, tree_low_cst (step
, 0));
2414 chrec
= CHREC_LEFT (chrec
);
2417 return val
% cd
== 0;
2420 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
2421 *OVERLAPS_B are initialized to the functions that describe the
2422 relation between the elements accessed twice by CHREC_A and
2423 CHREC_B. For k >= 0, the following property is verified:
2425 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2428 analyze_miv_subscript (tree chrec_a
,
2430 conflict_function
**overlaps_a
,
2431 conflict_function
**overlaps_b
,
2432 tree
*last_conflicts
)
2434 /* FIXME: This is a MIV subscript, not yet handled.
2435 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2438 In the SIV test we had to solve a Diophantine equation with two
2439 variables. In the MIV case we have to solve a Diophantine
2440 equation with 2*n variables (if the subscript uses n IVs).
2443 dependence_stats
.num_miv
++;
2444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2445 fprintf (dump_file
, "(analyze_miv_subscript \n");
2447 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
2448 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
2449 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
2451 if (eq_evolutions_p (chrec_a
, chrec_b
))
2453 /* Access functions are the same: all the elements are accessed
2454 in the same order. */
2455 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2456 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2457 *last_conflicts
= estimated_loop_iterations_tree
2458 (get_chrec_loop (chrec_a
), true);
2459 dependence_stats
.num_miv_dependent
++;
2462 else if (evolution_function_is_constant_p (difference
)
2463 /* For the moment, the following is verified:
2464 evolution_function_is_affine_multivariate_p (chrec_a, 0) */
2465 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2467 /* testsuite/.../ssa-chrec-33.c
2468 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2470 The difference is 1, and all the evolution steps are multiples
2471 of 2, consequently there are no overlapping elements. */
2472 *overlaps_a
= conflict_fn_no_dependence ();
2473 *overlaps_b
= conflict_fn_no_dependence ();
2474 *last_conflicts
= integer_zero_node
;
2475 dependence_stats
.num_miv_independent
++;
2478 else if (evolution_function_is_affine_multivariate_p (chrec_a
, 0)
2479 && !chrec_contains_symbols (chrec_a
)
2480 && evolution_function_is_affine_multivariate_p (chrec_b
, 0)
2481 && !chrec_contains_symbols (chrec_b
))
2483 /* testsuite/.../ssa-chrec-35.c
2484 {0, +, 1}_2 vs. {0, +, 1}_3
2485 the overlapping elements are respectively located at iterations:
2486 {0, +, 1}_x and {0, +, 1}_x,
2487 in other words, we have the equality:
2488 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2491 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2492 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2494 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2495 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2497 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2498 overlaps_a
, overlaps_b
, last_conflicts
);
2500 if (CF_NOT_KNOWN_P (*overlaps_a
)
2501 || CF_NOT_KNOWN_P (*overlaps_b
))
2502 dependence_stats
.num_miv_unimplemented
++;
2503 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2504 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2505 dependence_stats
.num_miv_independent
++;
2507 dependence_stats
.num_miv_dependent
++;
2512 /* When the analysis is too difficult, answer "don't know". */
2513 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2514 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2516 *overlaps_a
= conflict_fn_not_known ();
2517 *overlaps_b
= conflict_fn_not_known ();
2518 *last_conflicts
= chrec_dont_know
;
2519 dependence_stats
.num_miv_unimplemented
++;
2522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2523 fprintf (dump_file
, ")\n");
2526 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
2527 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2528 two functions that describe the iterations that contain conflicting
2531 Remark: For an integer k >= 0, the following equality is true:
2533 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2537 analyze_overlapping_iterations (tree chrec_a
,
2539 conflict_function
**overlap_iterations_a
,
2540 conflict_function
**overlap_iterations_b
,
2541 tree
*last_conflicts
)
2543 dependence_stats
.num_subscript_tests
++;
2545 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2547 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2548 fprintf (dump_file
, " (chrec_a = ");
2549 print_generic_expr (dump_file
, chrec_a
, 0);
2550 fprintf (dump_file
, ")\n (chrec_b = ");
2551 print_generic_expr (dump_file
, chrec_b
, 0);
2552 fprintf (dump_file
, ")\n");
2555 if (chrec_a
== NULL_TREE
2556 || chrec_b
== NULL_TREE
2557 || chrec_contains_undetermined (chrec_a
)
2558 || chrec_contains_undetermined (chrec_b
))
2560 dependence_stats
.num_subscript_undetermined
++;
2562 *overlap_iterations_a
= conflict_fn_not_known ();
2563 *overlap_iterations_b
= conflict_fn_not_known ();
2566 /* If they are the same chrec, and are affine, they overlap
2567 on every iteration. */
2568 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2569 && evolution_function_is_affine_multivariate_p (chrec_a
, 0))
2571 dependence_stats
.num_same_subscript_function
++;
2572 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2573 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2574 *last_conflicts
= chrec_dont_know
;
2577 /* If they aren't the same, and aren't affine, we can't do anything
2579 else if ((chrec_contains_symbols (chrec_a
)
2580 || chrec_contains_symbols (chrec_b
))
2581 && (!evolution_function_is_affine_multivariate_p (chrec_a
, 0)
2582 || !evolution_function_is_affine_multivariate_p (chrec_b
, 0)))
2584 dependence_stats
.num_subscript_undetermined
++;
2585 *overlap_iterations_a
= conflict_fn_not_known ();
2586 *overlap_iterations_b
= conflict_fn_not_known ();
2589 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2590 analyze_ziv_subscript (chrec_a
, chrec_b
,
2591 overlap_iterations_a
, overlap_iterations_b
,
2594 else if (siv_subscript_p (chrec_a
, chrec_b
))
2595 analyze_siv_subscript (chrec_a
, chrec_b
,
2596 overlap_iterations_a
, overlap_iterations_b
,
2600 analyze_miv_subscript (chrec_a
, chrec_b
,
2601 overlap_iterations_a
, overlap_iterations_b
,
2604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2606 fprintf (dump_file
, " (overlap_iterations_a = ");
2607 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2608 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2609 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2610 fprintf (dump_file
, ")\n");
2611 fprintf (dump_file
, ")\n");
2615 /* Helper function for uniquely inserting distance vectors. */
2618 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2623 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
2624 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2627 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2630 /* Helper function for uniquely inserting direction vectors. */
2633 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2638 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
2639 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2642 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2645 /* Add a distance of 1 on all the loops outer than INDEX. If we
2646 haven't yet determined a distance for this outer loop, push a new
2647 distance vector composed of the previous distance, and a distance
2648 of 1 for this outer loop. Example:
2656 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2657 save (0, 1), then we have to save (1, 0). */
2660 add_outer_distances (struct data_dependence_relation
*ddr
,
2661 lambda_vector dist_v
, int index
)
2663 /* For each outer loop where init_v is not set, the accesses are
2664 in dependence of distance 1 in the loop. */
2665 while (--index
>= 0)
2667 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2668 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2670 save_dist_v (ddr
, save_v
);
2674 /* Return false when fail to represent the data dependence as a
2675 distance vector. INIT_B is set to true when a component has been
2676 added to the distance vector DIST_V. INDEX_CARRY is then set to
2677 the index in DIST_V that carries the dependence. */
2680 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2681 struct data_reference
*ddr_a
,
2682 struct data_reference
*ddr_b
,
2683 lambda_vector dist_v
, bool *init_b
,
2687 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2689 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2691 tree access_fn_a
, access_fn_b
;
2692 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2694 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2696 non_affine_dependence_relation (ddr
);
2700 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2701 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2703 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2704 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2707 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2708 DDR_LOOP_NEST (ddr
));
2709 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2710 DDR_LOOP_NEST (ddr
));
2712 /* The dependence is carried by the outermost loop. Example:
2719 In this case, the dependence is carried by loop_1. */
2720 index
= index_a
< index_b
? index_a
: index_b
;
2721 *index_carry
= MIN (index
, *index_carry
);
2723 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2725 non_affine_dependence_relation (ddr
);
2729 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2731 /* This is the subscript coupling test. If we have already
2732 recorded a distance for this loop (a distance coming from
2733 another subscript), it should be the same. For example,
2734 in the following code, there is no dependence:
2741 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2743 finalize_ddr_dependent (ddr
, chrec_known
);
2747 dist_v
[index
] = dist
;
2751 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2753 /* This can be for example an affine vs. constant dependence
2754 (T[i] vs. T[3]) that is not an affine dependence and is
2755 not representable as a distance vector. */
2756 non_affine_dependence_relation (ddr
);
2764 /* Return true when the DDR contains two data references that have the
2765 same access functions. */
2768 same_access_functions (struct data_dependence_relation
*ddr
)
2772 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2773 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr
), i
),
2774 DR_ACCESS_FN (DDR_B (ddr
), i
)))
2780 /* Return true when the DDR contains only constant access functions. */
2783 constant_access_functions (struct data_dependence_relation
*ddr
)
2787 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2788 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2789 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2796 /* Helper function for the case where DDR_A and DDR_B are the same
2797 multivariate access function. */
2800 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2803 tree c_1
= CHREC_LEFT (c_2
);
2804 tree c_0
= CHREC_LEFT (c_1
);
2805 lambda_vector dist_v
;
2808 /* Polynomials with more than 2 variables are not handled yet. */
2809 if (TREE_CODE (c_0
) != INTEGER_CST
)
2811 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2815 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2816 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2818 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2819 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2820 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2821 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2834 save_dist_v (ddr
, dist_v
);
2836 add_outer_distances (ddr
, dist_v
, x_1
);
2839 /* Helper function for the case where DDR_A and DDR_B are the same
2840 access functions. */
2843 add_other_self_distances (struct data_dependence_relation
*ddr
)
2845 lambda_vector dist_v
;
2847 int index_carry
= DDR_NB_LOOPS (ddr
);
2849 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2851 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
2853 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
2855 if (!evolution_function_is_univariate_p (access_fun
))
2857 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
2859 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2863 add_multivariate_self_dist (ddr
, DR_ACCESS_FN (DDR_A (ddr
), 0));
2867 index_carry
= MIN (index_carry
,
2868 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
2869 DDR_LOOP_NEST (ddr
)));
2873 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2874 add_outer_distances (ddr
, dist_v
, index_carry
);
2878 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
2880 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2882 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
2883 save_dist_v (ddr
, dist_v
);
2886 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2887 is the case for example when access functions are the same and
2888 equal to a constant, as in:
2895 in which case the distance vectors are (0) and (1). */
2898 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
2902 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2904 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
2905 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
2906 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
2908 for (j
= 0; j
< ca
->n
; j
++)
2909 if (affine_function_zero_p (ca
->fns
[j
]))
2911 insert_innermost_unit_dist_vector (ddr
);
2915 for (j
= 0; j
< cb
->n
; j
++)
2916 if (affine_function_zero_p (cb
->fns
[j
]))
2918 insert_innermost_unit_dist_vector (ddr
);
2924 /* Compute the classic per loop distance vector. DDR is the data
2925 dependence relation to build a vector from. Return false when fail
2926 to represent the data dependence as a distance vector. */
2929 build_classic_dist_vector (struct data_dependence_relation
*ddr
)
2931 bool init_b
= false;
2932 int index_carry
= DDR_NB_LOOPS (ddr
);
2933 lambda_vector dist_v
;
2935 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
2938 if (same_access_functions (ddr
))
2940 /* Save the 0 vector. */
2941 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2942 save_dist_v (ddr
, dist_v
);
2944 if (constant_access_functions (ddr
))
2945 add_distance_for_zero_overlaps (ddr
);
2947 if (DDR_NB_LOOPS (ddr
) > 1)
2948 add_other_self_distances (ddr
);
2953 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2954 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
2955 dist_v
, &init_b
, &index_carry
))
2958 /* Save the distance vector if we initialized one. */
2961 /* Verify a basic constraint: classic distance vectors should
2962 always be lexicographically positive.
2964 Data references are collected in the order of execution of
2965 the program, thus for the following loop
2967 | for (i = 1; i < 100; i++)
2968 | for (j = 1; j < 100; j++)
2970 | t = T[j+1][i-1]; // A
2971 | T[j][i] = t + 2; // B
2974 references are collected following the direction of the wind:
2975 A then B. The data dependence tests are performed also
2976 following this order, such that we're looking at the distance
2977 separating the elements accessed by A from the elements later
2978 accessed by B. But in this example, the distance returned by
2979 test_dep (A, B) is lexicographically negative (-1, 1), that
2980 means that the access A occurs later than B with respect to
2981 the outer loop, ie. we're actually looking upwind. In this
2982 case we solve test_dep (B, A) looking downwind to the
2983 lexicographically positive solution, that returns the
2984 distance vector (1, -1). */
2985 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
2987 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2988 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
));
2989 compute_subscript_distance (ddr
);
2990 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
2991 save_v
, &init_b
, &index_carry
);
2992 save_dist_v (ddr
, save_v
);
2994 /* In this case there is a dependence forward for all the
2997 | for (k = 1; k < 100; k++)
2998 | for (i = 1; i < 100; i++)
2999 | for (j = 1; j < 100; j++)
3001 | t = T[j+1][i-1]; // A
3002 | T[j][i] = t + 2; // B
3010 if (DDR_NB_LOOPS (ddr
) > 1)
3012 add_outer_distances (ddr
, save_v
, index_carry
);
3013 add_outer_distances (ddr
, dist_v
, index_carry
);
3018 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3019 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3020 save_dist_v (ddr
, save_v
);
3022 if (DDR_NB_LOOPS (ddr
) > 1)
3024 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3026 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
));
3027 compute_subscript_distance (ddr
);
3028 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3029 opposite_v
, &init_b
, &index_carry
);
3031 add_outer_distances (ddr
, dist_v
, index_carry
);
3032 add_outer_distances (ddr
, opposite_v
, index_carry
);
3038 /* There is a distance of 1 on all the outer loops: Example:
3039 there is a dependence of distance 1 on loop_1 for the array A.
3045 add_outer_distances (ddr
, dist_v
,
3046 lambda_vector_first_nz (dist_v
,
3047 DDR_NB_LOOPS (ddr
), 0));
3050 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3054 fprintf (dump_file
, "(build_classic_dist_vector\n");
3055 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3057 fprintf (dump_file
, " dist_vector = (");
3058 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3059 DDR_NB_LOOPS (ddr
));
3060 fprintf (dump_file
, " )\n");
3062 fprintf (dump_file
, ")\n");
3068 /* Return the direction for a given distance.
3069 FIXME: Computing dir this way is suboptimal, since dir can catch
3070 cases that dist is unable to represent. */
3072 static inline enum data_dependence_direction
3073 dir_from_dist (int dist
)
3076 return dir_positive
;
3078 return dir_negative
;
3083 /* Compute the classic per loop direction vector. DDR is the data
3084 dependence relation to build a vector from. */
3087 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3090 lambda_vector dist_v
;
3092 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3094 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3096 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3097 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3099 save_dir_v (ddr
, dir_v
);
3103 /* Helper function. Returns true when there is a dependence between
3104 data references DRA and DRB. */
3107 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3108 struct data_reference
*dra
,
3109 struct data_reference
*drb
)
3112 tree last_conflicts
;
3113 struct subscript
*subscript
;
3115 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3118 conflict_function
*overlaps_a
, *overlaps_b
;
3120 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3121 DR_ACCESS_FN (drb
, i
),
3122 &overlaps_a
, &overlaps_b
,
3125 if (CF_NOT_KNOWN_P (overlaps_a
)
3126 || CF_NOT_KNOWN_P (overlaps_b
))
3128 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3129 dependence_stats
.num_dependence_undetermined
++;
3130 free_conflict_function (overlaps_a
);
3131 free_conflict_function (overlaps_b
);
3135 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3136 || CF_NO_DEPENDENCE_P (overlaps_b
))
3138 finalize_ddr_dependent (ddr
, chrec_known
);
3139 dependence_stats
.num_dependence_independent
++;
3140 free_conflict_function (overlaps_a
);
3141 free_conflict_function (overlaps_b
);
3147 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3148 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3149 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3156 /* Computes the conflicting iterations, and initialize DDR. */
3159 subscript_dependence_tester (struct data_dependence_relation
*ddr
)
3162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3163 fprintf (dump_file
, "(subscript_dependence_tester \n");
3165 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
)))
3166 dependence_stats
.num_dependence_dependent
++;
3168 compute_subscript_distance (ddr
);
3169 if (build_classic_dist_vector (ddr
))
3170 build_classic_dir_vector (ddr
);
3172 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3173 fprintf (dump_file
, ")\n");
3176 /* Returns true when all the access functions of A are affine or
3180 access_functions_are_affine_or_constant_p (struct data_reference
*a
)
3183 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3186 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
3187 if (!evolution_function_is_constant_p (t
)
3188 && !evolution_function_is_affine_multivariate_p (t
, 0))
3194 /* Initializes an equation for an OMEGA problem using the information
3195 contained in the ACCESS_FUN. Returns true when the operation
3198 PB is the omega constraint system.
3199 EQ is the number of the equation to be initialized.
3200 OFFSET is used for shifting the variables names in the constraints:
3201 a constrain is composed of 2 * the number of variables surrounding
3202 dependence accesses. OFFSET is set either to 0 for the first n variables,
3203 then it is set to n.
3204 ACCESS_FUN is expected to be an affine chrec. */
3207 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3208 unsigned int offset
, tree access_fun
,
3209 struct data_dependence_relation
*ddr
)
3211 switch (TREE_CODE (access_fun
))
3213 case POLYNOMIAL_CHREC
:
3215 tree left
= CHREC_LEFT (access_fun
);
3216 tree right
= CHREC_RIGHT (access_fun
);
3217 int var
= CHREC_VARIABLE (access_fun
);
3220 if (TREE_CODE (right
) != INTEGER_CST
)
3223 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3224 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3226 /* Compute the innermost loop index. */
3227 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3230 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3231 += int_cst_value (right
);
3233 switch (TREE_CODE (left
))
3235 case POLYNOMIAL_CHREC
:
3236 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3239 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3248 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3256 /* As explained in the comments preceding init_omega_for_ddr, we have
3257 to set up a system for each loop level, setting outer loops
3258 variation to zero, and current loop variation to positive or zero.
3259 Save each lexico positive distance vector. */
3262 omega_extract_distance_vectors (omega_pb pb
,
3263 struct data_dependence_relation
*ddr
)
3267 struct loop
*loopi
, *loopj
;
3268 enum omega_result res
;
3270 /* Set a new problem for each loop in the nest. The basis is the
3271 problem that we have initialized until now. On top of this we
3272 add new constraints. */
3273 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3274 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3277 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3278 DDR_NB_LOOPS (ddr
));
3280 omega_copy_problem (copy
, pb
);
3282 /* For all the outer loops "loop_j", add "dj = 0". */
3284 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3286 eq
= omega_add_zero_eq (copy
, omega_black
);
3287 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3290 /* For "loop_i", add "0 <= di". */
3291 geq
= omega_add_zero_geq (copy
, omega_black
);
3292 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3294 /* Reduce the constraint system, and test that the current
3295 problem is feasible. */
3296 res
= omega_simplify_problem (copy
);
3297 if (res
== omega_false
3298 || res
== omega_unknown
3299 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3302 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3303 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3305 dist
= copy
->subs
[eq
].coef
[0];
3311 /* Reinitialize problem... */
3312 omega_copy_problem (copy
, pb
);
3314 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3316 eq
= omega_add_zero_eq (copy
, omega_black
);
3317 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3320 /* ..., but this time "di = 1". */
3321 eq
= omega_add_zero_eq (copy
, omega_black
);
3322 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3323 copy
->eqs
[eq
].coef
[0] = -1;
3325 res
= omega_simplify_problem (copy
);
3326 if (res
== omega_false
3327 || res
== omega_unknown
3328 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3331 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3332 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3334 dist
= copy
->subs
[eq
].coef
[0];
3340 /* Save the lexicographically positive distance vector. */
3343 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3344 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3348 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3349 if (copy
->subs
[eq
].key
> 0)
3351 dist
= copy
->subs
[eq
].coef
[0];
3352 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3355 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3356 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3358 save_dist_v (ddr
, dist_v
);
3359 save_dir_v (ddr
, dir_v
);
3363 omega_free_problem (copy
);
3367 /* This is called for each subscript of a tuple of data references:
3368 insert an equality for representing the conflicts. */
3371 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3372 struct data_dependence_relation
*ddr
,
3373 omega_pb pb
, bool *maybe_dependent
)
3376 tree fun_a
= chrec_convert (integer_type_node
, access_fun_a
, NULL_TREE
);
3377 tree fun_b
= chrec_convert (integer_type_node
, access_fun_b
, NULL_TREE
);
3378 tree difference
= chrec_fold_minus (integer_type_node
, fun_a
, fun_b
);
3380 /* When the fun_a - fun_b is not constant, the dependence is not
3381 captured by the classic distance vector representation. */
3382 if (TREE_CODE (difference
) != INTEGER_CST
)
3386 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3388 /* There is no dependence. */
3389 *maybe_dependent
= false;
3393 fun_b
= chrec_fold_multiply (integer_type_node
, fun_b
,
3394 integer_minus_one_node
);
3396 eq
= omega_add_zero_eq (pb
, omega_black
);
3397 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3398 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3399 /* There is probably a dependence, but the system of
3400 constraints cannot be built: answer "don't know". */
3404 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3405 && !int_divides_p (lambda_vector_gcd
3406 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3407 2 * DDR_NB_LOOPS (ddr
)),
3408 pb
->eqs
[eq
].coef
[0]))
3410 /* There is no dependence. */
3411 *maybe_dependent
= false;
3418 /* Helper function, same as init_omega_for_ddr but specialized for
3419 data references A and B. */
3422 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3423 struct data_dependence_relation
*ddr
,
3424 omega_pb pb
, bool *maybe_dependent
)
3429 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3431 /* Insert an equality per subscript. */
3432 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3434 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3435 ddr
, pb
, maybe_dependent
))
3437 else if (*maybe_dependent
== false)
3439 /* There is no dependence. */
3440 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3445 /* Insert inequalities: constraints corresponding to the iteration
3446 domain, i.e. the loops surrounding the references "loop_x" and
3447 the distance variables "dx". The layout of the OMEGA
3448 representation is as follows:
3449 - coef[0] is the constant
3450 - coef[1..nb_loops] are the protected variables that will not be
3451 removed by the solver: the "dx"
3452 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3454 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3455 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3457 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, true);
3460 ineq
= omega_add_zero_geq (pb
, omega_black
);
3461 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3463 /* 0 <= loop_x + dx */
3464 ineq
= omega_add_zero_geq (pb
, omega_black
);
3465 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3466 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3470 /* loop_x <= nb_iters */
3471 ineq
= omega_add_zero_geq (pb
, omega_black
);
3472 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3473 pb
->geqs
[ineq
].coef
[0] = nbi
;
3475 /* loop_x + dx <= nb_iters */
3476 ineq
= omega_add_zero_geq (pb
, omega_black
);
3477 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3478 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3479 pb
->geqs
[ineq
].coef
[0] = nbi
;
3481 /* A step "dx" bigger than nb_iters is not feasible, so
3482 add "0 <= nb_iters + dx", */
3483 ineq
= omega_add_zero_geq (pb
, omega_black
);
3484 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3485 pb
->geqs
[ineq
].coef
[0] = nbi
;
3486 /* and "dx <= nb_iters". */
3487 ineq
= omega_add_zero_geq (pb
, omega_black
);
3488 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3489 pb
->geqs
[ineq
].coef
[0] = nbi
;
3493 omega_extract_distance_vectors (pb
, ddr
);
3498 /* Sets up the Omega dependence problem for the data dependence
3499 relation DDR. Returns false when the constraint system cannot be
3500 built, ie. when the test answers "don't know". Returns true
3501 otherwise, and when independence has been proved (using one of the
3502 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3503 set MAYBE_DEPENDENT to true.
3505 Example: for setting up the dependence system corresponding to the
3506 conflicting accesses
3511 | ... A[2*j, 2*(i + j)]
3515 the following constraints come from the iteration domain:
3522 where di, dj are the distance variables. The constraints
3523 representing the conflicting elements are:
3526 i + 1 = 2 * (i + di + j + dj)
3528 For asking that the resulting distance vector (di, dj) be
3529 lexicographically positive, we insert the constraint "di >= 0". If
3530 "di = 0" in the solution, we fix that component to zero, and we
3531 look at the inner loops: we set a new problem where all the outer
3532 loop distances are zero, and fix this inner component to be
3533 positive. When one of the components is positive, we save that
3534 distance, and set a new problem where the distance on this loop is
3535 zero, searching for other distances in the inner loops. Here is
3536 the classic example that illustrates that we have to set for each
3537 inner loop a new problem:
3545 we have to save two distances (1, 0) and (0, 1).
3547 Given two array references, refA and refB, we have to set the
3548 dependence problem twice, refA vs. refB and refB vs. refA, and we
3549 cannot do a single test, as refB might occur before refA in the
3550 inner loops, and the contrary when considering outer loops: ex.
3555 | T[{1,+,1}_2][{1,+,1}_1] // refA
3556 | T[{2,+,1}_2][{0,+,1}_1] // refB
3561 refB touches the elements in T before refA, and thus for the same
3562 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3563 but for successive loop_0 iterations, we have (1, -1, 1)
3565 The Omega solver expects the distance variables ("di" in the
3566 previous example) to come first in the constraint system (as
3567 variables to be protected, or "safe" variables), the constraint
3568 system is built using the following layout:
3570 "cst | distance vars | index vars".
3574 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3575 bool *maybe_dependent
)
3580 *maybe_dependent
= true;
3582 if (same_access_functions (ddr
))
3585 lambda_vector dir_v
;
3587 /* Save the 0 vector. */
3588 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3589 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3590 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3591 dir_v
[j
] = dir_equal
;
3592 save_dir_v (ddr
, dir_v
);
3594 /* Save the dependences carried by outer loops. */
3595 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3596 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3598 omega_free_problem (pb
);
3602 /* Omega expects the protected variables (those that have to be kept
3603 after elimination) to appear first in the constraint system.
3604 These variables are the distance variables. In the following
3605 initialization we declare NB_LOOPS safe variables, and the total
3606 number of variables for the constraint system is 2*NB_LOOPS. */
3607 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3608 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3610 omega_free_problem (pb
);
3612 /* Stop computation if not decidable, or no dependence. */
3613 if (res
== false || *maybe_dependent
== false)
3616 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3617 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3619 omega_free_problem (pb
);
3624 /* Return true when DDR contains the same information as that stored
3625 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3628 ddr_consistent_p (FILE *file
,
3629 struct data_dependence_relation
*ddr
,
3630 VEC (lambda_vector
, heap
) *dist_vects
,
3631 VEC (lambda_vector
, heap
) *dir_vects
)
3635 /* If dump_file is set, output there. */
3636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3639 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3641 lambda_vector b_dist_v
;
3642 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3643 VEC_length (lambda_vector
, dist_vects
),
3644 DDR_NUM_DIST_VECTS (ddr
));
3646 fprintf (file
, "Banerjee dist vectors:\n");
3647 for (i
= 0; VEC_iterate (lambda_vector
, dist_vects
, i
, b_dist_v
); i
++)
3648 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3650 fprintf (file
, "Omega dist vectors:\n");
3651 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3652 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3654 fprintf (file
, "data dependence relation:\n");
3655 dump_data_dependence_relation (file
, ddr
);
3657 fprintf (file
, ")\n");
3661 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3663 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3664 VEC_length (lambda_vector
, dir_vects
),
3665 DDR_NUM_DIR_VECTS (ddr
));
3669 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3671 lambda_vector a_dist_v
;
3672 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3674 /* Distance vectors are not ordered in the same way in the DDR
3675 and in the DIST_VECTS: search for a matching vector. */
3676 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, a_dist_v
); j
++)
3677 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3680 if (j
== VEC_length (lambda_vector
, dist_vects
))
3682 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3683 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3684 fprintf (file
, "not found in Omega dist vectors:\n");
3685 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3686 fprintf (file
, "data dependence relation:\n");
3687 dump_data_dependence_relation (file
, ddr
);
3688 fprintf (file
, ")\n");
3692 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3694 lambda_vector a_dir_v
;
3695 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3697 /* Direction vectors are not ordered in the same way in the DDR
3698 and in the DIR_VECTS: search for a matching vector. */
3699 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, a_dir_v
); j
++)
3700 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3703 if (j
== VEC_length (lambda_vector
, dist_vects
))
3705 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3706 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3707 fprintf (file
, "not found in Omega dir vectors:\n");
3708 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3709 fprintf (file
, "data dependence relation:\n");
3710 dump_data_dependence_relation (file
, ddr
);
3711 fprintf (file
, ")\n");
3718 /* This computes the affine dependence relation between A and B.
3719 CHREC_KNOWN is used for representing the independence between two
3720 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3723 Note that it is possible to stop the computation of the dependence
3724 relation the first time we detect a CHREC_KNOWN element for a given
3728 compute_affine_dependence (struct data_dependence_relation
*ddr
)
3730 struct data_reference
*dra
= DDR_A (ddr
);
3731 struct data_reference
*drb
= DDR_B (ddr
);
3733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3735 fprintf (dump_file
, "(compute_affine_dependence\n");
3736 fprintf (dump_file
, " (stmt_a = \n");
3737 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
3738 fprintf (dump_file
, ")\n (stmt_b = \n");
3739 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
3740 fprintf (dump_file
, ")\n");
3743 /* Analyze only when the dependence relation is not yet known. */
3744 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3746 dependence_stats
.num_dependence_tests
++;
3748 if (access_functions_are_affine_or_constant_p (dra
)
3749 && access_functions_are_affine_or_constant_p (drb
))
3751 if (flag_check_data_deps
)
3753 /* Compute the dependences using the first algorithm. */
3754 subscript_dependence_tester (ddr
);
3756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3758 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3759 dump_data_dependence_relation (dump_file
, ddr
);
3762 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3764 bool maybe_dependent
;
3765 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3767 /* Save the result of the first DD analyzer. */
3768 dist_vects
= DDR_DIST_VECTS (ddr
);
3769 dir_vects
= DDR_DIR_VECTS (ddr
);
3771 /* Reset the information. */
3772 DDR_DIST_VECTS (ddr
) = NULL
;
3773 DDR_DIR_VECTS (ddr
) = NULL
;
3775 /* Compute the same information using Omega. */
3776 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3777 goto csys_dont_know
;
3779 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3781 fprintf (dump_file
, "Omega Analyzer\n");
3782 dump_data_dependence_relation (dump_file
, ddr
);
3785 /* Check that we get the same information. */
3786 if (maybe_dependent
)
3787 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3792 subscript_dependence_tester (ddr
);
3795 /* As a last case, if the dependence cannot be determined, or if
3796 the dependence is considered too difficult to determine, answer
3801 dependence_stats
.num_dependence_undetermined
++;
3803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3805 fprintf (dump_file
, "Data ref a:\n");
3806 dump_data_reference (dump_file
, dra
);
3807 fprintf (dump_file
, "Data ref b:\n");
3808 dump_data_reference (dump_file
, drb
);
3809 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3811 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3815 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3816 fprintf (dump_file
, ")\n");
3819 /* This computes the dependence relation for the same data
3820 reference into DDR. */
3823 compute_self_dependence (struct data_dependence_relation
*ddr
)
3826 struct subscript
*subscript
;
3828 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3831 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3834 /* The accessed index overlaps for each iteration. */
3835 SUB_CONFLICTS_IN_A (subscript
)
3836 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3837 SUB_CONFLICTS_IN_B (subscript
)
3838 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3839 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3842 /* The distance vector is the zero vector. */
3843 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3844 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3847 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3848 the data references in DATAREFS, in the LOOP_NEST. When
3849 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3853 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
3854 VEC (ddr_p
, heap
) **dependence_relations
,
3855 VEC (loop_p
, heap
) *loop_nest
,
3856 bool compute_self_and_rr
)
3858 struct data_dependence_relation
*ddr
;
3859 struct data_reference
*a
, *b
;
3862 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
3863 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
3864 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
3866 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
3867 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3868 compute_affine_dependence (ddr
);
3871 if (compute_self_and_rr
)
3872 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
3874 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
3875 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3876 compute_self_dependence (ddr
);
3880 /* Stores the locations of memory references in STMT to REFERENCES. Returns
3881 true if STMT clobbers memory, false otherwise. */
3884 get_references_in_stmt (tree stmt
, VEC (data_ref_loc
, heap
) **references
)
3886 bool clobbers_memory
= false;
3888 tree
*op0
, *op1
, call
;
3892 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3893 Calls have side-effects, except those to const or pure
3895 call
= get_call_expr_in (stmt
);
3897 && !(call_expr_flags (call
) & (ECF_CONST
| ECF_PURE
)))
3898 || (TREE_CODE (stmt
) == ASM_EXPR
3899 && ASM_VOLATILE_P (stmt
)))
3900 clobbers_memory
= true;
3902 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
3903 return clobbers_memory
;
3905 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3907 op0
= &GIMPLE_STMT_OPERAND (stmt
, 0);
3908 op1
= &GIMPLE_STMT_OPERAND (stmt
, 1);
3911 || REFERENCE_CLASS_P (*op1
))
3913 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
3915 ref
->is_read
= true;
3919 || REFERENCE_CLASS_P (*op0
))
3921 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
3923 ref
->is_read
= false;
3929 unsigned i
, n
= call_expr_nargs (call
);
3931 for (i
= 0; i
< n
; i
++)
3933 op0
= &CALL_EXPR_ARG (call
, i
);
3936 || REFERENCE_CLASS_P (*op0
))
3938 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
3940 ref
->is_read
= true;
3945 return clobbers_memory
;
3948 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
3949 reference, returns false, otherwise returns true. NEST is the outermost
3950 loop of the loop nest in that the references should be analyzed. */
3953 find_data_references_in_stmt (struct loop
*nest
, tree stmt
,
3954 VEC (data_reference_p
, heap
) **datarefs
)
3957 VEC (data_ref_loc
, heap
) *references
;
3960 data_reference_p dr
;
3962 if (get_references_in_stmt (stmt
, &references
))
3964 VEC_free (data_ref_loc
, heap
, references
);
3968 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
3970 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
3971 gcc_assert (dr
!= NULL
);
3973 /* FIXME -- data dependence analysis does not work correctly for objects with
3974 invariant addresses. Let us fail here until the problem is fixed. */
3975 if (dr_address_invariant_p (dr
))
3978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3979 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
3984 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
3986 VEC_free (data_ref_loc
, heap
, references
);
3990 /* Search the data references in LOOP, and record the information into
3991 DATAREFS. Returns chrec_dont_know when failing to analyze a
3992 difficult case, returns NULL_TREE otherwise.
3994 TODO: This function should be made smarter so that it can handle address
3995 arithmetic as if they were array accesses, etc. */
3998 find_data_references_in_loop (struct loop
*loop
,
3999 VEC (data_reference_p
, heap
) **datarefs
)
4001 basic_block bb
, *bbs
;
4003 block_stmt_iterator bsi
;
4005 bbs
= get_loop_body_in_dom_order (loop
);
4007 for (i
= 0; i
< loop
->num_nodes
; i
++)
4011 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4013 tree stmt
= bsi_stmt (bsi
);
4015 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4017 struct data_reference
*res
;
4018 res
= XCNEW (struct data_reference
);
4019 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4022 return chrec_dont_know
;
4031 /* Recursive helper function. */
4034 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4036 /* Inner loops of the nest should not contain siblings. Example:
4037 when there are two consecutive loops,
4048 the dependence relation cannot be captured by the distance
4053 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4055 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4059 /* Return false when the LOOP is not well nested. Otherwise return
4060 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4061 contain the loops from the outermost to the innermost, as they will
4062 appear in the classic distance vector. */
4065 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4067 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4069 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4073 /* Given a loop nest LOOP, the following vectors are returned:
4074 DATAREFS is initialized to all the array elements contained in this loop,
4075 DEPENDENCE_RELATIONS contains the relations between the data references.
4076 Compute read-read and self relations if
4077 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4080 compute_data_dependences_for_loop (struct loop
*loop
,
4081 bool compute_self_and_read_read_dependences
,
4082 VEC (data_reference_p
, heap
) **datarefs
,
4083 VEC (ddr_p
, heap
) **dependence_relations
)
4085 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4087 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4089 /* If the loop nest is not well formed, or one of the data references
4090 is not computable, give up without spending time to compute other
4093 || !find_loop_nest (loop
, &vloops
)
4094 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4096 struct data_dependence_relation
*ddr
;
4098 /* Insert a single relation into dependence_relations:
4100 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4101 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4104 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4105 compute_self_and_read_read_dependences
);
4107 if (dump_file
&& (dump_flags
& TDF_STATS
))
4109 fprintf (dump_file
, "Dependence tester statistics:\n");
4111 fprintf (dump_file
, "Number of dependence tests: %d\n",
4112 dependence_stats
.num_dependence_tests
);
4113 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4114 dependence_stats
.num_dependence_dependent
);
4115 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4116 dependence_stats
.num_dependence_independent
);
4117 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4118 dependence_stats
.num_dependence_undetermined
);
4120 fprintf (dump_file
, "Number of subscript tests: %d\n",
4121 dependence_stats
.num_subscript_tests
);
4122 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4123 dependence_stats
.num_subscript_undetermined
);
4124 fprintf (dump_file
, "Number of same subscript function: %d\n",
4125 dependence_stats
.num_same_subscript_function
);
4127 fprintf (dump_file
, "Number of ziv tests: %d\n",
4128 dependence_stats
.num_ziv
);
4129 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4130 dependence_stats
.num_ziv_dependent
);
4131 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4132 dependence_stats
.num_ziv_independent
);
4133 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4134 dependence_stats
.num_ziv_unimplemented
);
4136 fprintf (dump_file
, "Number of siv tests: %d\n",
4137 dependence_stats
.num_siv
);
4138 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4139 dependence_stats
.num_siv_dependent
);
4140 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4141 dependence_stats
.num_siv_independent
);
4142 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4143 dependence_stats
.num_siv_unimplemented
);
4145 fprintf (dump_file
, "Number of miv tests: %d\n",
4146 dependence_stats
.num_miv
);
4147 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4148 dependence_stats
.num_miv_dependent
);
4149 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4150 dependence_stats
.num_miv_independent
);
4151 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4152 dependence_stats
.num_miv_unimplemented
);
4156 /* Entry point (for testing only). Analyze all the data references
4157 and the dependence relations in LOOP.
4159 The data references are computed first.
4161 A relation on these nodes is represented by a complete graph. Some
4162 of the relations could be of no interest, thus the relations can be
4165 In the following function we compute all the relations. This is
4166 just a first implementation that is here for:
4167 - for showing how to ask for the dependence relations,
4168 - for the debugging the whole dependence graph,
4169 - for the dejagnu testcases and maintenance.
4171 It is possible to ask only for a part of the graph, avoiding to
4172 compute the whole dependence graph. The computed dependences are
4173 stored in a knowledge base (KB) such that later queries don't
4174 recompute the same information. The implementation of this KB is
4175 transparent to the optimizer, and thus the KB can be changed with a
4176 more efficient implementation, or the KB could be disabled. */
4178 analyze_all_data_dependences (struct loop
*loop
)
4181 int nb_data_refs
= 10;
4182 VEC (data_reference_p
, heap
) *datarefs
=
4183 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4184 VEC (ddr_p
, heap
) *dependence_relations
=
4185 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4187 /* Compute DDs on the whole function. */
4188 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4189 &dependence_relations
);
4193 dump_data_dependence_relations (dump_file
, dependence_relations
);
4194 fprintf (dump_file
, "\n\n");
4196 if (dump_flags
& TDF_DETAILS
)
4197 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4199 if (dump_flags
& TDF_STATS
)
4201 unsigned nb_top_relations
= 0;
4202 unsigned nb_bot_relations
= 0;
4203 unsigned nb_basename_differ
= 0;
4204 unsigned nb_chrec_relations
= 0;
4205 struct data_dependence_relation
*ddr
;
4207 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4209 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4212 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4214 struct data_reference
*a
= DDR_A (ddr
);
4215 struct data_reference
*b
= DDR_B (ddr
);
4217 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
4218 nb_basename_differ
++;
4224 nb_chrec_relations
++;
4227 gather_stats_on_scev_database ();
4231 free_dependence_relations (dependence_relations
);
4232 free_data_refs (datarefs
);
4235 /* Computes all the data dependences and check that the results of
4236 several analyzers are the same. */
4239 tree_check_data_deps (void)
4242 struct loop
*loop_nest
;
4244 FOR_EACH_LOOP (li
, loop_nest
, 0)
4245 analyze_all_data_dependences (loop_nest
);
4248 /* Free the memory used by a data dependence relation DDR. */
4251 free_dependence_relation (struct data_dependence_relation
*ddr
)
4256 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
4257 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4262 /* Free the memory used by the data dependence relations from
4263 DEPENDENCE_RELATIONS. */
4266 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4269 struct data_dependence_relation
*ddr
;
4270 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4272 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4276 if (loop_nest
== NULL
)
4277 loop_nest
= DDR_LOOP_NEST (ddr
);
4279 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4280 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4281 free_dependence_relation (ddr
);
4285 VEC_free (loop_p
, heap
, loop_nest
);
4286 VEC_free (ddr_p
, heap
, dependence_relations
);
4289 /* Free the memory used by the data references from DATAREFS. */
4292 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4295 struct data_reference
*dr
;
4297 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4299 VEC_free (data_reference_p
, heap
, datarefs
);