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
*,
129 /* Returns true iff A divides B. */
132 tree_fold_divides_p (tree a
, tree b
)
134 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
135 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
136 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
, 0));
139 /* Returns true iff A divides B. */
142 int_divides_p (int a
, int b
)
144 return ((b
% a
) == 0);
149 /* Dump into FILE all the data references from DATAREFS. */
152 dump_data_references (FILE *file
, VEC (data_reference_p
, heap
) *datarefs
)
155 struct data_reference
*dr
;
157 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
158 dump_data_reference (file
, dr
);
161 /* Dump into FILE all the dependence relations from DDRS. */
164 dump_data_dependence_relations (FILE *file
,
165 VEC (ddr_p
, heap
) *ddrs
)
168 struct data_dependence_relation
*ddr
;
170 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
171 dump_data_dependence_relation (file
, ddr
);
174 /* Dump function for a DATA_REFERENCE structure. */
177 dump_data_reference (FILE *outf
,
178 struct data_reference
*dr
)
182 fprintf (outf
, "(Data Ref: \n stmt: ");
183 print_generic_stmt (outf
, DR_STMT (dr
), 0);
184 fprintf (outf
, " ref: ");
185 print_generic_stmt (outf
, DR_REF (dr
), 0);
186 fprintf (outf
, " base_object: ");
187 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
189 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
191 fprintf (outf
, " Access function %d: ", i
);
192 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
194 fprintf (outf
, ")\n");
197 /* Dumps the affine function described by FN to the file OUTF. */
200 dump_affine_function (FILE *outf
, affine_fn fn
)
205 print_generic_expr (outf
, VEC_index (tree
, fn
, 0), TDF_SLIM
);
206 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
208 fprintf (outf
, " + ");
209 print_generic_expr (outf
, coef
, TDF_SLIM
);
210 fprintf (outf
, " * x_%u", i
);
214 /* Dumps the conflict function CF to the file OUTF. */
217 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
221 if (cf
->n
== NO_DEPENDENCE
)
222 fprintf (outf
, "no dependence\n");
223 else if (cf
->n
== NOT_KNOWN
)
224 fprintf (outf
, "not known\n");
227 for (i
= 0; i
< cf
->n
; i
++)
230 dump_affine_function (outf
, cf
->fns
[i
]);
231 fprintf (outf
, "]\n");
236 /* Dump function for a SUBSCRIPT structure. */
239 dump_subscript (FILE *outf
, struct subscript
*subscript
)
241 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
243 fprintf (outf
, "\n (subscript \n");
244 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
245 dump_conflict_function (outf
, cf
);
246 if (CF_NONTRIVIAL_P (cf
))
248 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
249 fprintf (outf
, " last_conflict: ");
250 print_generic_stmt (outf
, last_iteration
, 0);
253 cf
= SUB_CONFLICTS_IN_B (subscript
);
254 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
255 dump_conflict_function (outf
, cf
);
256 if (CF_NONTRIVIAL_P (cf
))
258 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
259 fprintf (outf
, " last_conflict: ");
260 print_generic_stmt (outf
, last_iteration
, 0);
263 fprintf (outf
, " (Subscript distance: ");
264 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
265 fprintf (outf
, " )\n");
266 fprintf (outf
, " )\n");
269 /* Print the classic direction vector DIRV to OUTF. */
272 print_direction_vector (FILE *outf
,
278 for (eq
= 0; eq
< length
; eq
++)
280 enum data_dependence_direction dir
= dirv
[eq
];
285 fprintf (outf
, " +");
288 fprintf (outf
, " -");
291 fprintf (outf
, " =");
293 case dir_positive_or_equal
:
294 fprintf (outf
, " +=");
296 case dir_positive_or_negative
:
297 fprintf (outf
, " +-");
299 case dir_negative_or_equal
:
300 fprintf (outf
, " -=");
303 fprintf (outf
, " *");
306 fprintf (outf
, "indep");
310 fprintf (outf
, "\n");
313 /* Print a vector of direction vectors. */
316 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
322 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
323 print_direction_vector (outf
, v
, length
);
326 /* Print a vector of distance vectors. */
329 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
335 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
336 print_lambda_vector (outf
, v
, length
);
342 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
344 dump_data_dependence_relation (stderr
, ddr
);
347 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
350 dump_data_dependence_relation (FILE *outf
,
351 struct data_dependence_relation
*ddr
)
353 struct data_reference
*dra
, *drb
;
357 fprintf (outf
, "(Data Dep: \n");
358 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
359 fprintf (outf
, " (don't know)\n");
361 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
362 fprintf (outf
, " (no dependence)\n");
364 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
369 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
371 fprintf (outf
, " access_fn_A: ");
372 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
373 fprintf (outf
, " access_fn_B: ");
374 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
375 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
378 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
379 fprintf (outf
, " loop nest: (");
380 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
381 fprintf (outf
, "%d ", loopi
->num
);
382 fprintf (outf
, ")\n");
384 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
386 fprintf (outf
, " distance_vector: ");
387 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
391 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
393 fprintf (outf
, " direction_vector: ");
394 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
399 fprintf (outf
, ")\n");
402 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
405 dump_data_dependence_direction (FILE *file
,
406 enum data_dependence_direction dir
)
422 case dir_positive_or_negative
:
423 fprintf (file
, "+-");
426 case dir_positive_or_equal
:
427 fprintf (file
, "+=");
430 case dir_negative_or_equal
:
431 fprintf (file
, "-=");
443 /* Dumps the distance and direction vectors in FILE. DDRS contains
444 the dependence relations, and VECT_SIZE is the size of the
445 dependence vectors, or in other words the number of loops in the
449 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
452 struct data_dependence_relation
*ddr
;
455 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
456 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
458 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
460 fprintf (file
, "DISTANCE_V (");
461 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
462 fprintf (file
, ")\n");
465 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
467 fprintf (file
, "DIRECTION_V (");
468 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
469 fprintf (file
, ")\n");
473 fprintf (file
, "\n\n");
476 /* Dumps the data dependence relations DDRS in FILE. */
479 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
482 struct data_dependence_relation
*ddr
;
484 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
485 dump_data_dependence_relation (file
, ddr
);
487 fprintf (file
, "\n\n");
490 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
491 will be ssizetype. */
494 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
496 tree type
= TREE_TYPE (exp
), otype
;
503 otype
= TREE_TYPE (exp
);
504 code
= TREE_CODE (exp
);
509 *var
= build_int_cst (type
, 0);
510 *off
= fold_convert (ssizetype
, exp
);
513 case POINTER_PLUS_EXPR
:
518 split_constant_offset (TREE_OPERAND (exp
, 0), &var0
, &off0
);
519 split_constant_offset (TREE_OPERAND (exp
, 1), &var1
, &off1
);
520 *var
= fold_convert (type
, fold_build2 (TREE_CODE (exp
), otype
,
522 *off
= size_binop (code
, off0
, off1
);
526 off1
= TREE_OPERAND (exp
, 1);
527 if (TREE_CODE (off1
) != INTEGER_CST
)
530 split_constant_offset (TREE_OPERAND (exp
, 0), &var0
, &off0
);
531 *var
= fold_convert (type
, fold_build2 (MULT_EXPR
, otype
,
533 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, off1
));
538 tree op
, base
, poffset
;
539 HOST_WIDE_INT pbitsize
, pbitpos
;
540 enum machine_mode pmode
;
541 int punsignedp
, pvolatilep
;
543 op
= TREE_OPERAND (exp
, 0);
544 if (!handled_component_p (op
))
547 base
= get_inner_reference (op
, &pbitsize
, &pbitpos
, &poffset
,
548 &pmode
, &punsignedp
, &pvolatilep
, false);
550 if (pbitpos
% BITS_PER_UNIT
!= 0)
552 base
= build_fold_addr_expr (base
);
553 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
557 split_constant_offset (poffset
, &poffset
, &off1
);
558 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
559 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
),
561 fold_convert (TREE_TYPE (base
), poffset
));
564 *var
= fold_convert (type
, base
);
573 *off
= ssize_int (0);
576 /* Returns the address ADDR of an object in a canonical shape (without nop
577 casts, and with type of pointer to the object). */
580 canonicalize_base_object_address (tree addr
)
586 /* The base address may be obtained by casting from integer, in that case
588 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
591 if (TREE_CODE (addr
) != ADDR_EXPR
)
594 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
597 /* Analyzes the behavior of the memory reference DR in the innermost loop that
601 dr_analyze_innermost (struct data_reference
*dr
)
603 tree stmt
= DR_STMT (dr
);
604 struct loop
*loop
= loop_containing_stmt (stmt
);
605 tree ref
= DR_REF (dr
);
606 HOST_WIDE_INT pbitsize
, pbitpos
;
608 enum machine_mode pmode
;
609 int punsignedp
, pvolatilep
;
610 affine_iv base_iv
, offset_iv
;
611 tree init
, dinit
, step
;
613 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
614 fprintf (dump_file
, "analyze_innermost: ");
616 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
617 &pmode
, &punsignedp
, &pvolatilep
, false);
618 gcc_assert (base
!= NULL_TREE
);
620 if (pbitpos
% BITS_PER_UNIT
!= 0)
622 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
623 fprintf (dump_file
, "failed: bit offset alignment.\n");
627 base
= build_fold_addr_expr (base
);
628 if (!simple_iv (loop
, stmt
, base
, &base_iv
, false))
630 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
631 fprintf (dump_file
, "failed: evolution of base is not affine.\n");
636 offset_iv
.base
= ssize_int (0);
637 offset_iv
.step
= ssize_int (0);
639 else if (!simple_iv (loop
, stmt
, poffset
, &offset_iv
, false))
641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
642 fprintf (dump_file
, "failed: evolution of offset is not affine.\n");
646 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
647 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
648 init
= size_binop (PLUS_EXPR
, init
, dinit
);
649 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
650 init
= size_binop (PLUS_EXPR
, init
, dinit
);
652 step
= size_binop (PLUS_EXPR
,
653 fold_convert (ssizetype
, base_iv
.step
),
654 fold_convert (ssizetype
, offset_iv
.step
));
656 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
658 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
662 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
664 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
665 fprintf (dump_file
, "success.\n");
668 /* Determines the base object and the list of indices of memory reference
669 DR, analyzed in loop nest NEST. */
672 dr_analyze_indices (struct data_reference
*dr
, struct loop
*nest
)
674 tree stmt
= DR_STMT (dr
);
675 struct loop
*loop
= loop_containing_stmt (stmt
);
676 VEC (tree
, heap
) *access_fns
= NULL
;
677 tree ref
= unshare_expr (DR_REF (dr
)), aref
= ref
, op
;
678 tree base
, off
, access_fn
;
680 while (handled_component_p (aref
))
682 if (TREE_CODE (aref
) == ARRAY_REF
)
684 op
= TREE_OPERAND (aref
, 1);
685 access_fn
= analyze_scalar_evolution (loop
, op
);
686 access_fn
= resolve_mixers (nest
, access_fn
);
687 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
689 TREE_OPERAND (aref
, 1) = build_int_cst (TREE_TYPE (op
), 0);
692 aref
= TREE_OPERAND (aref
, 0);
695 if (INDIRECT_REF_P (aref
))
697 op
= TREE_OPERAND (aref
, 0);
698 access_fn
= analyze_scalar_evolution (loop
, op
);
699 access_fn
= resolve_mixers (nest
, access_fn
);
700 base
= initial_condition (access_fn
);
701 split_constant_offset (base
, &base
, &off
);
702 access_fn
= chrec_replace_initial_condition (access_fn
,
703 fold_convert (TREE_TYPE (base
), off
));
705 TREE_OPERAND (aref
, 0) = base
;
706 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
709 DR_BASE_OBJECT (dr
) = ref
;
710 DR_ACCESS_FNS (dr
) = access_fns
;
713 /* Extracts the alias analysis information from the memory reference DR. */
716 dr_analyze_alias (struct data_reference
*dr
)
718 tree stmt
= DR_STMT (dr
);
719 tree ref
= DR_REF (dr
);
720 tree base
= get_base_address (ref
), addr
, smt
= NULL_TREE
;
727 else if (INDIRECT_REF_P (base
))
729 addr
= TREE_OPERAND (base
, 0);
730 if (TREE_CODE (addr
) == SSA_NAME
)
732 smt
= symbol_mem_tag (SSA_NAME_VAR (addr
));
733 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
737 DR_SYMBOL_TAG (dr
) = smt
;
738 if (smt
&& var_can_have_subvars (smt
))
739 DR_SUBVARS (dr
) = get_subvars_for_var (smt
);
741 vops
= BITMAP_ALLOC (NULL
);
742 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, it
, SSA_OP_VIRTUAL_USES
)
744 bitmap_set_bit (vops
, DECL_UID (SSA_NAME_VAR (op
)));
750 /* Returns true if the address of DR is invariant. */
753 dr_address_invariant_p (struct data_reference
*dr
)
758 for (i
= 0; VEC_iterate (tree
, DR_ACCESS_FNS (dr
), i
, idx
); i
++)
759 if (tree_contains_chrecs (idx
, NULL
))
765 /* Frees data reference DR. */
768 free_data_ref (data_reference_p dr
)
770 BITMAP_FREE (DR_VOPS (dr
));
771 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
775 /* Analyzes memory reference MEMREF accessed in STMT. The reference
776 is read if IS_READ is true, write otherwise. Returns the
777 data_reference description of MEMREF. NEST is the outermost loop of the
778 loop nest in that the reference should be analyzed. */
780 struct data_reference
*
781 create_data_ref (struct loop
*nest
, tree memref
, tree stmt
, bool is_read
)
783 struct data_reference
*dr
;
785 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
787 fprintf (dump_file
, "Creating dr for ");
788 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
789 fprintf (dump_file
, "\n");
792 dr
= XCNEW (struct data_reference
);
794 DR_REF (dr
) = memref
;
795 DR_IS_READ (dr
) = is_read
;
797 dr_analyze_innermost (dr
);
798 dr_analyze_indices (dr
, nest
);
799 dr_analyze_alias (dr
);
801 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
803 fprintf (dump_file
, "\tbase_address: ");
804 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
805 fprintf (dump_file
, "\n\toffset from base address: ");
806 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
807 fprintf (dump_file
, "\n\tconstant offset from base address: ");
808 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
809 fprintf (dump_file
, "\n\tstep: ");
810 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
811 fprintf (dump_file
, "\n\taligned to: ");
812 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
813 fprintf (dump_file
, "\n\tbase_object: ");
814 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
815 fprintf (dump_file
, "\n\tsymbol tag: ");
816 print_generic_expr (dump_file
, DR_SYMBOL_TAG (dr
), TDF_SLIM
);
817 fprintf (dump_file
, "\n");
823 /* Returns true if FNA == FNB. */
826 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
828 unsigned i
, n
= VEC_length (tree
, fna
);
830 if (n
!= VEC_length (tree
, fnb
))
833 for (i
= 0; i
< n
; i
++)
834 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
835 VEC_index (tree
, fnb
, i
), 0))
841 /* If all the functions in CF are the same, returns one of them,
842 otherwise returns NULL. */
845 common_affine_function (conflict_function
*cf
)
850 if (!CF_NONTRIVIAL_P (cf
))
855 for (i
= 1; i
< cf
->n
; i
++)
856 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
862 /* Returns the base of the affine function FN. */
865 affine_function_base (affine_fn fn
)
867 return VEC_index (tree
, fn
, 0);
870 /* Returns true if FN is a constant. */
873 affine_function_constant_p (affine_fn fn
)
878 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
879 if (!integer_zerop (coef
))
885 /* Returns true if FN is the zero constant function. */
888 affine_function_zero_p (affine_fn fn
)
890 return (integer_zerop (affine_function_base (fn
))
891 && affine_function_constant_p (fn
));
894 /* Applies operation OP on affine functions FNA and FNB, and returns the
898 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
904 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
906 n
= VEC_length (tree
, fna
);
907 m
= VEC_length (tree
, fnb
);
911 n
= VEC_length (tree
, fnb
);
912 m
= VEC_length (tree
, fna
);
915 ret
= VEC_alloc (tree
, heap
, m
);
916 for (i
= 0; i
< n
; i
++)
917 VEC_quick_push (tree
, ret
,
918 fold_build2 (op
, integer_type_node
,
919 VEC_index (tree
, fna
, i
),
920 VEC_index (tree
, fnb
, i
)));
922 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
923 VEC_quick_push (tree
, ret
,
924 fold_build2 (op
, integer_type_node
,
925 coef
, integer_zero_node
));
926 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
927 VEC_quick_push (tree
, ret
,
928 fold_build2 (op
, integer_type_node
,
929 integer_zero_node
, coef
));
934 /* Returns the sum of affine functions FNA and FNB. */
937 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
939 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
942 /* Returns the difference of affine functions FNA and FNB. */
945 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
947 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
950 /* Frees affine function FN. */
953 affine_fn_free (affine_fn fn
)
955 VEC_free (tree
, heap
, fn
);
958 /* Determine for each subscript in the data dependence relation DDR
962 compute_subscript_distance (struct data_dependence_relation
*ddr
)
964 conflict_function
*cf_a
, *cf_b
;
965 affine_fn fn_a
, fn_b
, diff
;
967 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
971 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
973 struct subscript
*subscript
;
975 subscript
= DDR_SUBSCRIPT (ddr
, i
);
976 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
977 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
979 fn_a
= common_affine_function (cf_a
);
980 fn_b
= common_affine_function (cf_b
);
983 SUB_DISTANCE (subscript
) = chrec_dont_know
;
986 diff
= affine_fn_minus (fn_a
, fn_b
);
988 if (affine_function_constant_p (diff
))
989 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
991 SUB_DISTANCE (subscript
) = chrec_dont_know
;
993 affine_fn_free (diff
);
998 /* Returns the conflict function for "unknown". */
1000 static conflict_function
*
1001 conflict_fn_not_known (void)
1003 conflict_function
*fn
= XCNEW (conflict_function
);
1009 /* Returns the conflict function for "independent". */
1011 static conflict_function
*
1012 conflict_fn_no_dependence (void)
1014 conflict_function
*fn
= XCNEW (conflict_function
);
1015 fn
->n
= NO_DEPENDENCE
;
1020 /* Returns true if the address of OBJ is invariant in LOOP. */
1023 object_address_invariant_in_loop_p (struct loop
*loop
, tree obj
)
1025 while (handled_component_p (obj
))
1027 if (TREE_CODE (obj
) == ARRAY_REF
)
1029 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1030 need to check the stride and the lower bound of the reference. */
1031 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1033 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1037 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1039 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1043 obj
= TREE_OPERAND (obj
, 0);
1046 if (!INDIRECT_REF_P (obj
))
1049 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1053 /* Returns true if A and B are accesses to different objects, or to different
1054 fields of the same object. */
1057 disjoint_objects_p (tree a
, tree b
)
1059 tree base_a
, base_b
;
1060 VEC (tree
, heap
) *comp_a
= NULL
, *comp_b
= NULL
;
1063 base_a
= get_base_address (a
);
1064 base_b
= get_base_address (b
);
1068 && base_a
!= base_b
)
1071 if (!operand_equal_p (base_a
, base_b
, 0))
1074 /* Compare the component references of A and B. We must start from the inner
1075 ones, so record them to the vector first. */
1076 while (handled_component_p (a
))
1078 VEC_safe_push (tree
, heap
, comp_a
, a
);
1079 a
= TREE_OPERAND (a
, 0);
1081 while (handled_component_p (b
))
1083 VEC_safe_push (tree
, heap
, comp_b
, b
);
1084 b
= TREE_OPERAND (b
, 0);
1090 if (VEC_length (tree
, comp_a
) == 0
1091 || VEC_length (tree
, comp_b
) == 0)
1094 a
= VEC_pop (tree
, comp_a
);
1095 b
= VEC_pop (tree
, comp_b
);
1097 /* Real and imaginary part of a variable do not alias. */
1098 if ((TREE_CODE (a
) == REALPART_EXPR
1099 && TREE_CODE (b
) == IMAGPART_EXPR
)
1100 || (TREE_CODE (a
) == IMAGPART_EXPR
1101 && TREE_CODE (b
) == REALPART_EXPR
))
1107 if (TREE_CODE (a
) != TREE_CODE (b
))
1110 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1111 DR_BASE_OBJECT are always zero. */
1112 if (TREE_CODE (a
) == ARRAY_REF
)
1114 else if (TREE_CODE (a
) == COMPONENT_REF
)
1116 if (operand_equal_p (TREE_OPERAND (a
, 1), TREE_OPERAND (b
, 1), 0))
1119 /* Different fields of unions may overlap. */
1120 base_a
= TREE_OPERAND (a
, 0);
1121 if (TREE_CODE (TREE_TYPE (base_a
)) == UNION_TYPE
)
1124 /* Different fields of structures cannot. */
1132 VEC_free (tree
, heap
, comp_a
);
1133 VEC_free (tree
, heap
, comp_b
);
1138 /* Returns false if we can prove that data references A and B do not alias,
1142 dr_may_alias_p (struct data_reference
*a
, struct data_reference
*b
)
1144 tree addr_a
= DR_BASE_ADDRESS (a
);
1145 tree addr_b
= DR_BASE_ADDRESS (b
);
1146 tree type_a
, type_b
;
1147 tree decl_a
= NULL_TREE
, decl_b
= NULL_TREE
;
1149 /* If the sets of virtual operands are disjoint, the memory references do not
1151 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
1154 /* If the accessed objects are disjoint, the memory references do not
1156 if (disjoint_objects_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
)))
1159 if (!addr_a
|| !addr_b
)
1162 /* If the references are based on different static objects, they cannot alias
1163 (PTA should be able to disambiguate such accesses, but often it fails to,
1164 since currently we cannot distinguish between pointer and offset in pointer
1166 if (TREE_CODE (addr_a
) == ADDR_EXPR
1167 && TREE_CODE (addr_b
) == ADDR_EXPR
)
1168 return TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0);
1170 /* An instruction writing through a restricted pointer is "independent" of any
1171 instruction reading or writing through a different restricted pointer,
1172 in the same block/scope. */
1174 type_a
= TREE_TYPE (addr_a
);
1175 type_b
= TREE_TYPE (addr_b
);
1176 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
1178 if (TREE_CODE (addr_a
) == SSA_NAME
)
1179 decl_a
= SSA_NAME_VAR (addr_a
);
1180 if (TREE_CODE (addr_b
) == SSA_NAME
)
1181 decl_b
= SSA_NAME_VAR (addr_b
);
1183 if (TYPE_RESTRICT (type_a
) && TYPE_RESTRICT (type_b
)
1184 && (!DR_IS_READ (a
) || !DR_IS_READ (b
))
1185 && decl_a
&& DECL_P (decl_a
)
1186 && decl_b
&& DECL_P (decl_b
)
1188 && TREE_CODE (DECL_CONTEXT (decl_a
)) == FUNCTION_DECL
1189 && DECL_CONTEXT (decl_a
) == DECL_CONTEXT (decl_b
))
1195 /* Initialize a data dependence relation between data accesses A and
1196 B. NB_LOOPS is the number of loops surrounding the references: the
1197 size of the classic distance/direction vectors. */
1199 static struct data_dependence_relation
*
1200 initialize_data_dependence_relation (struct data_reference
*a
,
1201 struct data_reference
*b
,
1202 VEC (loop_p
, heap
) *loop_nest
)
1204 struct data_dependence_relation
*res
;
1207 res
= XNEW (struct data_dependence_relation
);
1210 DDR_LOOP_NEST (res
) = NULL
;
1211 DDR_REVERSED_P (res
) = false;
1213 if (a
== NULL
|| b
== NULL
)
1215 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1219 /* If the data references do not alias, then they are independent. */
1220 if (!dr_may_alias_p (a
, b
))
1222 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1226 /* If the references do not access the same object, we do not know
1227 whether they alias or not. */
1228 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1230 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1234 /* If the base of the object is not invariant in the loop nest, we cannot
1235 analyze it. TODO -- in fact, it would suffice to record that there may
1236 be arbitrary dependences in the loops where the base object varies. */
1237 if (!object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1238 DR_BASE_OBJECT (a
)))
1240 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1244 gcc_assert (DR_NUM_DIMENSIONS (a
) == DR_NUM_DIMENSIONS (b
));
1246 DDR_AFFINE_P (res
) = true;
1247 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1248 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1249 DDR_LOOP_NEST (res
) = loop_nest
;
1250 DDR_INNER_LOOP (res
) = 0;
1251 DDR_DIR_VECTS (res
) = NULL
;
1252 DDR_DIST_VECTS (res
) = NULL
;
1254 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1256 struct subscript
*subscript
;
1258 subscript
= XNEW (struct subscript
);
1259 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1260 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1261 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1262 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1263 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1269 /* Frees memory used by the conflict function F. */
1272 free_conflict_function (conflict_function
*f
)
1276 if (CF_NONTRIVIAL_P (f
))
1278 for (i
= 0; i
< f
->n
; i
++)
1279 affine_fn_free (f
->fns
[i
]);
1284 /* Frees memory used by SUBSCRIPTS. */
1287 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1292 for (i
= 0; VEC_iterate (subscript_p
, subscripts
, i
, s
); i
++)
1294 free_conflict_function (s
->conflicting_iterations_in_a
);
1295 free_conflict_function (s
->conflicting_iterations_in_b
);
1297 VEC_free (subscript_p
, heap
, subscripts
);
1300 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1304 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1309 fprintf (dump_file
, "(dependence classified: ");
1310 print_generic_expr (dump_file
, chrec
, 0);
1311 fprintf (dump_file
, ")\n");
1314 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1315 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1318 /* The dependence relation DDR cannot be represented by a distance
1322 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1324 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1325 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1327 DDR_AFFINE_P (ddr
) = false;
1332 /* This section contains the classic Banerjee tests. */
1334 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1335 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1338 ziv_subscript_p (tree chrec_a
,
1341 return (evolution_function_is_constant_p (chrec_a
)
1342 && evolution_function_is_constant_p (chrec_b
));
1345 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1346 variable, i.e., if the SIV (Single Index Variable) test is true. */
1349 siv_subscript_p (tree chrec_a
,
1352 if ((evolution_function_is_constant_p (chrec_a
)
1353 && evolution_function_is_univariate_p (chrec_b
))
1354 || (evolution_function_is_constant_p (chrec_b
)
1355 && evolution_function_is_univariate_p (chrec_a
)))
1358 if (evolution_function_is_univariate_p (chrec_a
)
1359 && evolution_function_is_univariate_p (chrec_b
))
1361 switch (TREE_CODE (chrec_a
))
1363 case POLYNOMIAL_CHREC
:
1364 switch (TREE_CODE (chrec_b
))
1366 case POLYNOMIAL_CHREC
:
1367 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1382 /* Creates a conflict function with N dimensions. The affine functions
1383 in each dimension follow. */
1385 static conflict_function
*
1386 conflict_fn (unsigned n
, ...)
1389 conflict_function
*ret
= XCNEW (conflict_function
);
1392 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1396 for (i
= 0; i
< n
; i
++)
1397 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1403 /* Returns constant affine function with value CST. */
1406 affine_fn_cst (tree cst
)
1408 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1409 VEC_quick_push (tree
, fn
, cst
);
1413 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1416 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1418 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1421 gcc_assert (dim
> 0);
1422 VEC_quick_push (tree
, fn
, cst
);
1423 for (i
= 1; i
< dim
; i
++)
1424 VEC_quick_push (tree
, fn
, integer_zero_node
);
1425 VEC_quick_push (tree
, fn
, coef
);
1429 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1430 *OVERLAPS_B are initialized to the functions that describe the
1431 relation between the elements accessed twice by CHREC_A and
1432 CHREC_B. For k >= 0, the following property is verified:
1434 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1437 analyze_ziv_subscript (tree chrec_a
,
1439 conflict_function
**overlaps_a
,
1440 conflict_function
**overlaps_b
,
1441 tree
*last_conflicts
)
1444 dependence_stats
.num_ziv
++;
1446 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1447 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1449 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
1450 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
1451 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
1453 switch (TREE_CODE (difference
))
1456 if (integer_zerop (difference
))
1458 /* The difference is equal to zero: the accessed index
1459 overlaps for each iteration in the loop. */
1460 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1461 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1462 *last_conflicts
= chrec_dont_know
;
1463 dependence_stats
.num_ziv_dependent
++;
1467 /* The accesses do not overlap. */
1468 *overlaps_a
= conflict_fn_no_dependence ();
1469 *overlaps_b
= conflict_fn_no_dependence ();
1470 *last_conflicts
= integer_zero_node
;
1471 dependence_stats
.num_ziv_independent
++;
1476 /* We're not sure whether the indexes overlap. For the moment,
1477 conservatively answer "don't know". */
1478 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1479 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1481 *overlaps_a
= conflict_fn_not_known ();
1482 *overlaps_b
= conflict_fn_not_known ();
1483 *last_conflicts
= chrec_dont_know
;
1484 dependence_stats
.num_ziv_unimplemented
++;
1488 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1489 fprintf (dump_file
, ")\n");
1492 /* Sets NIT to the estimated number of executions of the statements in
1493 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1494 large as the number of iterations. If we have no reliable estimate,
1495 the function returns false, otherwise returns true. */
1498 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
1501 estimate_numbers_of_iterations_loop (loop
);
1504 if (!loop
->any_upper_bound
)
1507 *nit
= loop
->nb_iterations_upper_bound
;
1511 if (!loop
->any_estimate
)
1514 *nit
= loop
->nb_iterations_estimate
;
1520 /* Similar to estimated_loop_iterations, but returns the estimate only
1521 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1522 on the number of iterations of LOOP could not be derived, returns -1. */
1525 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
1528 HOST_WIDE_INT hwi_nit
;
1530 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1533 if (!double_int_fits_in_shwi_p (nit
))
1535 hwi_nit
= double_int_to_shwi (nit
);
1537 return hwi_nit
< 0 ? -1 : hwi_nit
;
1540 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1541 and only if it fits to the int type. If this is not the case, or the
1542 estimate on the number of iterations of LOOP could not be derived, returns
1546 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
1551 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1552 return chrec_dont_know
;
1554 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
1555 if (!double_int_fits_to_tree_p (type
, nit
))
1556 return chrec_dont_know
;
1558 return double_int_to_tree (type
, nit
);
1561 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1562 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1563 *OVERLAPS_B are initialized to the functions that describe the
1564 relation between the elements accessed twice by CHREC_A and
1565 CHREC_B. For k >= 0, the following property is verified:
1567 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1570 analyze_siv_subscript_cst_affine (tree chrec_a
,
1572 conflict_function
**overlaps_a
,
1573 conflict_function
**overlaps_b
,
1574 tree
*last_conflicts
)
1576 bool value0
, value1
, value2
;
1577 tree difference
, tmp
;
1579 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
1580 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
1581 difference
= chrec_fold_minus
1582 (integer_type_node
, initial_condition (chrec_b
), chrec_a
);
1584 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1586 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1587 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1589 dependence_stats
.num_siv_unimplemented
++;
1590 *overlaps_a
= conflict_fn_not_known ();
1591 *overlaps_b
= conflict_fn_not_known ();
1592 *last_conflicts
= chrec_dont_know
;
1597 if (value0
== false)
1599 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1601 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1602 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1604 *overlaps_a
= conflict_fn_not_known ();
1605 *overlaps_b
= conflict_fn_not_known ();
1606 *last_conflicts
= chrec_dont_know
;
1607 dependence_stats
.num_siv_unimplemented
++;
1616 chrec_b = {10, +, 1}
1619 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1621 HOST_WIDE_INT numiter
;
1622 struct loop
*loop
= get_chrec_loop (chrec_b
);
1624 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1625 tmp
= fold_build2 (EXACT_DIV_EXPR
, integer_type_node
,
1626 fold_build1 (ABS_EXPR
,
1629 CHREC_RIGHT (chrec_b
));
1630 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1631 *last_conflicts
= integer_one_node
;
1634 /* Perform weak-zero siv test to see if overlap is
1635 outside the loop bounds. */
1636 numiter
= estimated_loop_iterations_int (loop
, false);
1639 && compare_tree_int (tmp
, numiter
) > 0)
1641 free_conflict_function (*overlaps_a
);
1642 free_conflict_function (*overlaps_b
);
1643 *overlaps_a
= conflict_fn_no_dependence ();
1644 *overlaps_b
= conflict_fn_no_dependence ();
1645 *last_conflicts
= integer_zero_node
;
1646 dependence_stats
.num_siv_independent
++;
1649 dependence_stats
.num_siv_dependent
++;
1653 /* When the step does not divide the difference, there are
1657 *overlaps_a
= conflict_fn_no_dependence ();
1658 *overlaps_b
= conflict_fn_no_dependence ();
1659 *last_conflicts
= integer_zero_node
;
1660 dependence_stats
.num_siv_independent
++;
1669 chrec_b = {10, +, -1}
1671 In this case, chrec_a will not overlap with chrec_b. */
1672 *overlaps_a
= conflict_fn_no_dependence ();
1673 *overlaps_b
= conflict_fn_no_dependence ();
1674 *last_conflicts
= integer_zero_node
;
1675 dependence_stats
.num_siv_independent
++;
1682 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1684 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1685 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1687 *overlaps_a
= conflict_fn_not_known ();
1688 *overlaps_b
= conflict_fn_not_known ();
1689 *last_conflicts
= chrec_dont_know
;
1690 dependence_stats
.num_siv_unimplemented
++;
1695 if (value2
== false)
1699 chrec_b = {10, +, -1}
1701 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1703 HOST_WIDE_INT numiter
;
1704 struct loop
*loop
= get_chrec_loop (chrec_b
);
1706 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1707 tmp
= fold_build2 (EXACT_DIV_EXPR
,
1708 integer_type_node
, difference
,
1709 CHREC_RIGHT (chrec_b
));
1710 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1711 *last_conflicts
= integer_one_node
;
1713 /* Perform weak-zero siv test to see if overlap is
1714 outside the loop bounds. */
1715 numiter
= estimated_loop_iterations_int (loop
, false);
1718 && compare_tree_int (tmp
, numiter
) > 0)
1720 free_conflict_function (*overlaps_a
);
1721 free_conflict_function (*overlaps_b
);
1722 *overlaps_a
= conflict_fn_no_dependence ();
1723 *overlaps_b
= conflict_fn_no_dependence ();
1724 *last_conflicts
= integer_zero_node
;
1725 dependence_stats
.num_siv_independent
++;
1728 dependence_stats
.num_siv_dependent
++;
1732 /* When the step does not divide the difference, there
1736 *overlaps_a
= conflict_fn_no_dependence ();
1737 *overlaps_b
= conflict_fn_no_dependence ();
1738 *last_conflicts
= integer_zero_node
;
1739 dependence_stats
.num_siv_independent
++;
1749 In this case, chrec_a will not overlap with chrec_b. */
1750 *overlaps_a
= conflict_fn_no_dependence ();
1751 *overlaps_b
= conflict_fn_no_dependence ();
1752 *last_conflicts
= integer_zero_node
;
1753 dependence_stats
.num_siv_independent
++;
1761 /* Helper recursive function for initializing the matrix A. Returns
1762 the initial value of CHREC. */
1765 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1769 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1770 return int_cst_value (chrec
);
1772 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1773 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1776 #define FLOOR_DIV(x,y) ((x) / (y))
1778 /* Solves the special case of the Diophantine equation:
1779 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1781 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1782 number of iterations that loops X and Y run. The overlaps will be
1783 constructed as evolutions in dimension DIM. */
1786 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1787 affine_fn
*overlaps_a
,
1788 affine_fn
*overlaps_b
,
1789 tree
*last_conflicts
, int dim
)
1791 if (((step_a
> 0 && step_b
> 0)
1792 || (step_a
< 0 && step_b
< 0)))
1794 int step_overlaps_a
, step_overlaps_b
;
1795 int gcd_steps_a_b
, last_conflict
, tau2
;
1797 gcd_steps_a_b
= gcd (step_a
, step_b
);
1798 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1799 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1801 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1802 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1803 last_conflict
= tau2
;
1805 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
1806 build_int_cst (NULL_TREE
,
1808 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
1809 build_int_cst (NULL_TREE
,
1811 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1816 *overlaps_a
= affine_fn_cst (integer_zero_node
);
1817 *overlaps_b
= affine_fn_cst (integer_zero_node
);
1818 *last_conflicts
= integer_zero_node
;
1822 /* Solves the special case of a Diophantine equation where CHREC_A is
1823 an affine bivariate function, and CHREC_B is an affine univariate
1824 function. For example,
1826 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1828 has the following overlapping functions:
1830 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1831 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1832 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1834 FORNOW: This is a specialized implementation for a case occurring in
1835 a common benchmark. Implement the general algorithm. */
1838 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1839 conflict_function
**overlaps_a
,
1840 conflict_function
**overlaps_b
,
1841 tree
*last_conflicts
)
1843 bool xz_p
, yz_p
, xyz_p
;
1844 int step_x
, step_y
, step_z
;
1845 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
1846 affine_fn overlaps_a_xz
, overlaps_b_xz
;
1847 affine_fn overlaps_a_yz
, overlaps_b_yz
;
1848 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
1849 affine_fn ova1
, ova2
, ovb
;
1850 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
1852 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
1853 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
1854 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
1857 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a
)),
1859 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), false);
1860 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), false);
1862 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
1864 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1865 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
1867 *overlaps_a
= conflict_fn_not_known ();
1868 *overlaps_b
= conflict_fn_not_known ();
1869 *last_conflicts
= chrec_dont_know
;
1873 niter
= MIN (niter_x
, niter_z
);
1874 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
1877 &last_conflicts_xz
, 1);
1878 niter
= MIN (niter_y
, niter_z
);
1879 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
1882 &last_conflicts_yz
, 2);
1883 niter
= MIN (niter_x
, niter_z
);
1884 niter
= MIN (niter_y
, niter
);
1885 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
1888 &last_conflicts_xyz
, 3);
1890 xz_p
= !integer_zerop (last_conflicts_xz
);
1891 yz_p
= !integer_zerop (last_conflicts_yz
);
1892 xyz_p
= !integer_zerop (last_conflicts_xyz
);
1894 if (xz_p
|| yz_p
|| xyz_p
)
1896 ova1
= affine_fn_cst (integer_zero_node
);
1897 ova2
= affine_fn_cst (integer_zero_node
);
1898 ovb
= affine_fn_cst (integer_zero_node
);
1901 affine_fn t0
= ova1
;
1904 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
1905 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
1906 affine_fn_free (t0
);
1907 affine_fn_free (t2
);
1908 *last_conflicts
= last_conflicts_xz
;
1912 affine_fn t0
= ova2
;
1915 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
1916 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
1917 affine_fn_free (t0
);
1918 affine_fn_free (t2
);
1919 *last_conflicts
= last_conflicts_yz
;
1923 affine_fn t0
= ova1
;
1924 affine_fn t2
= ova2
;
1927 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
1928 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
1929 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
1930 affine_fn_free (t0
);
1931 affine_fn_free (t2
);
1932 affine_fn_free (t4
);
1933 *last_conflicts
= last_conflicts_xyz
;
1935 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
1936 *overlaps_b
= conflict_fn (1, ovb
);
1940 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1941 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1942 *last_conflicts
= integer_zero_node
;
1945 affine_fn_free (overlaps_a_xz
);
1946 affine_fn_free (overlaps_b_xz
);
1947 affine_fn_free (overlaps_a_yz
);
1948 affine_fn_free (overlaps_b_yz
);
1949 affine_fn_free (overlaps_a_xyz
);
1950 affine_fn_free (overlaps_b_xyz
);
1953 /* Determines the overlapping elements due to accesses CHREC_A and
1954 CHREC_B, that are affine functions. This function cannot handle
1955 symbolic evolution functions, ie. when initial conditions are
1956 parameters, because it uses lambda matrices of integers. */
1959 analyze_subscript_affine_affine (tree chrec_a
,
1961 conflict_function
**overlaps_a
,
1962 conflict_function
**overlaps_b
,
1963 tree
*last_conflicts
)
1965 unsigned nb_vars_a
, nb_vars_b
, dim
;
1966 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
1967 HOST_WIDE_INT tau1
, tau2
;
1968 lambda_matrix A
, U
, S
;
1970 if (eq_evolutions_p (chrec_a
, chrec_b
))
1972 /* The accessed index overlaps for each iteration in the
1974 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1975 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1976 *last_conflicts
= chrec_dont_know
;
1979 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1980 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
1982 /* For determining the initial intersection, we have to solve a
1983 Diophantine equation. This is the most time consuming part.
1985 For answering to the question: "Is there a dependence?" we have
1986 to prove that there exists a solution to the Diophantine
1987 equation, and that the solution is in the iteration domain,
1988 i.e. the solution is positive or zero, and that the solution
1989 happens before the upper bound loop.nb_iterations. Otherwise
1990 there is no dependence. This function outputs a description of
1991 the iterations that hold the intersections. */
1993 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
1994 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
1996 dim
= nb_vars_a
+ nb_vars_b
;
1997 U
= lambda_matrix_new (dim
, dim
);
1998 A
= lambda_matrix_new (dim
, 1);
1999 S
= lambda_matrix_new (dim
, 1);
2001 init_a
= initialize_matrix_A (A
, chrec_a
, 0, 1);
2002 init_b
= initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1);
2003 gamma
= init_b
- init_a
;
2005 /* Don't do all the hard work of solving the Diophantine equation
2006 when we already know the solution: for example,
2009 | gamma = 3 - 3 = 0.
2010 Then the first overlap occurs during the first iterations:
2011 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2015 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2017 HOST_WIDE_INT step_a
, step_b
;
2018 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2021 niter_a
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
),
2023 niter_b
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
),
2025 if (niter_a
< 0 || niter_b
< 0)
2027 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2028 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
2029 *overlaps_a
= conflict_fn_not_known ();
2030 *overlaps_b
= conflict_fn_not_known ();
2031 *last_conflicts
= chrec_dont_know
;
2032 goto end_analyze_subs_aa
;
2035 niter
= MIN (niter_a
, niter_b
);
2037 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2038 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2040 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2043 *overlaps_a
= conflict_fn (1, ova
);
2044 *overlaps_b
= conflict_fn (1, ovb
);
2047 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2048 compute_overlap_steps_for_affine_1_2
2049 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2051 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2052 compute_overlap_steps_for_affine_1_2
2053 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2057 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2058 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2059 *overlaps_a
= conflict_fn_not_known ();
2060 *overlaps_b
= conflict_fn_not_known ();
2061 *last_conflicts
= chrec_dont_know
;
2063 goto end_analyze_subs_aa
;
2067 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2072 lambda_matrix_row_negate (U
, dim
, 0);
2074 gcd_alpha_beta
= S
[0][0];
2076 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2077 but that is a quite strange case. Instead of ICEing, answer
2079 if (gcd_alpha_beta
== 0)
2081 *overlaps_a
= conflict_fn_not_known ();
2082 *overlaps_b
= conflict_fn_not_known ();
2083 *last_conflicts
= chrec_dont_know
;
2084 goto end_analyze_subs_aa
;
2087 /* The classic "gcd-test". */
2088 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2090 /* The "gcd-test" has determined that there is no integer
2091 solution, i.e. there is no dependence. */
2092 *overlaps_a
= conflict_fn_no_dependence ();
2093 *overlaps_b
= conflict_fn_no_dependence ();
2094 *last_conflicts
= integer_zero_node
;
2097 /* Both access functions are univariate. This includes SIV and MIV cases. */
2098 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2100 /* Both functions should have the same evolution sign. */
2101 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2102 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2104 /* The solutions are given by:
2106 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2109 For a given integer t. Using the following variables,
2111 | i0 = u11 * gamma / gcd_alpha_beta
2112 | j0 = u12 * gamma / gcd_alpha_beta
2119 | y0 = j0 + j1 * t. */
2121 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2123 /* X0 and Y0 are the first iterations for which there is a
2124 dependence. X0, Y0 are two solutions of the Diophantine
2125 equation: chrec_a (X0) = chrec_b (Y0). */
2126 HOST_WIDE_INT x0
, y0
;
2127 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2129 niter_a
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
),
2131 niter_b
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
),
2134 if (niter_a
< 0 || niter_b
< 0)
2136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2137 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
2138 *overlaps_a
= conflict_fn_not_known ();
2139 *overlaps_b
= conflict_fn_not_known ();
2140 *last_conflicts
= chrec_dont_know
;
2141 goto end_analyze_subs_aa
;
2144 niter
= MIN (niter_a
, niter_b
);
2146 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2147 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2151 if ((i1
== 0 && i0
< 0)
2152 || (j1
== 0 && j0
< 0))
2154 /* There is no solution.
2155 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2156 falls in here, but for the moment we don't look at the
2157 upper bound of the iteration domain. */
2158 *overlaps_a
= conflict_fn_no_dependence ();
2159 *overlaps_b
= conflict_fn_no_dependence ();
2160 *last_conflicts
= integer_zero_node
;
2167 tau1
= CEIL (-i0
, i1
);
2168 tau2
= FLOOR_DIV (niter
- i0
, i1
);
2172 int last_conflict
, min_multiple
;
2173 tau1
= MAX (tau1
, CEIL (-j0
, j1
));
2174 tau2
= MIN (tau2
, FLOOR_DIV (niter
- j0
, j1
));
2176 x0
= i1
* tau1
+ i0
;
2177 y0
= j1
* tau1
+ j0
;
2179 /* At this point (x0, y0) is one of the
2180 solutions to the Diophantine equation. The
2181 next step has to compute the smallest
2182 positive solution: the first conflicts. */
2183 min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2184 x0
-= i1
* min_multiple
;
2185 y0
-= j1
* min_multiple
;
2187 tau1
= (x0
- i0
)/i1
;
2188 last_conflict
= tau2
- tau1
;
2190 /* If the overlap occurs outside of the bounds of the
2191 loop, there is no dependence. */
2192 if (x0
> niter
|| y0
> niter
)
2194 *overlaps_a
= conflict_fn_no_dependence ();
2195 *overlaps_b
= conflict_fn_no_dependence ();
2196 *last_conflicts
= integer_zero_node
;
2202 affine_fn_univar (build_int_cst (NULL_TREE
, x0
),
2204 build_int_cst (NULL_TREE
, i1
)));
2207 affine_fn_univar (build_int_cst (NULL_TREE
, y0
),
2209 build_int_cst (NULL_TREE
, j1
)));
2210 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2215 /* FIXME: For the moment, the upper bound of the
2216 iteration domain for j is not checked. */
2217 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2218 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2219 *overlaps_a
= conflict_fn_not_known ();
2220 *overlaps_b
= conflict_fn_not_known ();
2221 *last_conflicts
= chrec_dont_know
;
2227 /* FIXME: For the moment, the upper bound of the
2228 iteration domain for i is not checked. */
2229 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2230 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2231 *overlaps_a
= conflict_fn_not_known ();
2232 *overlaps_b
= conflict_fn_not_known ();
2233 *last_conflicts
= chrec_dont_know
;
2239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2240 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2241 *overlaps_a
= conflict_fn_not_known ();
2242 *overlaps_b
= conflict_fn_not_known ();
2243 *last_conflicts
= chrec_dont_know
;
2249 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2250 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2251 *overlaps_a
= conflict_fn_not_known ();
2252 *overlaps_b
= conflict_fn_not_known ();
2253 *last_conflicts
= chrec_dont_know
;
2256 end_analyze_subs_aa
:
2257 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2259 fprintf (dump_file
, " (overlaps_a = ");
2260 dump_conflict_function (dump_file
, *overlaps_a
);
2261 fprintf (dump_file
, ")\n (overlaps_b = ");
2262 dump_conflict_function (dump_file
, *overlaps_b
);
2263 fprintf (dump_file
, ")\n");
2264 fprintf (dump_file
, ")\n");
2268 /* Returns true when analyze_subscript_affine_affine can be used for
2269 determining the dependence relation between chrec_a and chrec_b,
2270 that contain symbols. This function modifies chrec_a and chrec_b
2271 such that the analysis result is the same, and such that they don't
2272 contain symbols, and then can safely be passed to the analyzer.
2274 Example: The analysis of the following tuples of evolutions produce
2275 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2278 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2279 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2283 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2285 tree diff
, type
, left_a
, left_b
, right_b
;
2287 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2288 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2289 /* FIXME: For the moment not handled. Might be refined later. */
2292 type
= chrec_type (*chrec_a
);
2293 left_a
= CHREC_LEFT (*chrec_a
);
2294 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL_TREE
);
2295 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2297 if (!evolution_function_is_constant_p (diff
))
2300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2301 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2303 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2304 diff
, CHREC_RIGHT (*chrec_a
));
2305 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL_TREE
);
2306 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2307 build_int_cst (type
, 0),
2312 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2313 *OVERLAPS_B are initialized to the functions that describe the
2314 relation between the elements accessed twice by CHREC_A and
2315 CHREC_B. For k >= 0, the following property is verified:
2317 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2320 analyze_siv_subscript (tree chrec_a
,
2322 conflict_function
**overlaps_a
,
2323 conflict_function
**overlaps_b
,
2324 tree
*last_conflicts
)
2326 dependence_stats
.num_siv
++;
2328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2329 fprintf (dump_file
, "(analyze_siv_subscript \n");
2331 if (evolution_function_is_constant_p (chrec_a
)
2332 && evolution_function_is_affine_p (chrec_b
))
2333 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2334 overlaps_a
, overlaps_b
, last_conflicts
);
2336 else if (evolution_function_is_affine_p (chrec_a
)
2337 && evolution_function_is_constant_p (chrec_b
))
2338 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2339 overlaps_b
, overlaps_a
, last_conflicts
);
2341 else if (evolution_function_is_affine_p (chrec_a
)
2342 && evolution_function_is_affine_p (chrec_b
))
2344 if (!chrec_contains_symbols (chrec_a
)
2345 && !chrec_contains_symbols (chrec_b
))
2347 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2348 overlaps_a
, overlaps_b
,
2351 if (CF_NOT_KNOWN_P (*overlaps_a
)
2352 || CF_NOT_KNOWN_P (*overlaps_b
))
2353 dependence_stats
.num_siv_unimplemented
++;
2354 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2355 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2356 dependence_stats
.num_siv_independent
++;
2358 dependence_stats
.num_siv_dependent
++;
2360 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2363 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2364 overlaps_a
, overlaps_b
,
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 with respect to
2421 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2422 functions that describe the relation between the elements accessed
2423 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2426 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2429 analyze_miv_subscript (tree chrec_a
,
2431 conflict_function
**overlaps_a
,
2432 conflict_function
**overlaps_b
,
2433 tree
*last_conflicts
,
2434 struct loop
*loop_nest
)
2436 /* FIXME: This is a MIV subscript, not yet handled.
2437 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2440 In the SIV test we had to solve a Diophantine equation with two
2441 variables. In the MIV case we have to solve a Diophantine
2442 equation with 2*n variables (if the subscript uses n IVs).
2445 dependence_stats
.num_miv
++;
2446 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2447 fprintf (dump_file
, "(analyze_miv_subscript \n");
2449 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
2450 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
2451 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
2453 if (eq_evolutions_p (chrec_a
, chrec_b
))
2455 /* Access functions are the same: all the elements are accessed
2456 in the same order. */
2457 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2458 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2459 *last_conflicts
= estimated_loop_iterations_tree
2460 (get_chrec_loop (chrec_a
), true);
2461 dependence_stats
.num_miv_dependent
++;
2464 else if (evolution_function_is_constant_p (difference
)
2465 /* For the moment, the following is verified:
2466 evolution_function_is_affine_multivariate_p (chrec_a,
2468 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2470 /* testsuite/.../ssa-chrec-33.c
2471 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2473 The difference is 1, and all the evolution steps are multiples
2474 of 2, consequently there are no overlapping elements. */
2475 *overlaps_a
= conflict_fn_no_dependence ();
2476 *overlaps_b
= conflict_fn_no_dependence ();
2477 *last_conflicts
= integer_zero_node
;
2478 dependence_stats
.num_miv_independent
++;
2481 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2482 && !chrec_contains_symbols (chrec_a
)
2483 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2484 && !chrec_contains_symbols (chrec_b
))
2486 /* testsuite/.../ssa-chrec-35.c
2487 {0, +, 1}_2 vs. {0, +, 1}_3
2488 the overlapping elements are respectively located at iterations:
2489 {0, +, 1}_x and {0, +, 1}_x,
2490 in other words, we have the equality:
2491 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2494 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2495 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2497 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2498 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2500 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2501 overlaps_a
, overlaps_b
, last_conflicts
);
2503 if (CF_NOT_KNOWN_P (*overlaps_a
)
2504 || CF_NOT_KNOWN_P (*overlaps_b
))
2505 dependence_stats
.num_miv_unimplemented
++;
2506 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2507 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2508 dependence_stats
.num_miv_independent
++;
2510 dependence_stats
.num_miv_dependent
++;
2515 /* When the analysis is too difficult, answer "don't know". */
2516 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2517 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2519 *overlaps_a
= conflict_fn_not_known ();
2520 *overlaps_b
= conflict_fn_not_known ();
2521 *last_conflicts
= chrec_dont_know
;
2522 dependence_stats
.num_miv_unimplemented
++;
2525 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2526 fprintf (dump_file
, ")\n");
2529 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2530 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2531 OVERLAP_ITERATIONS_B are initialized with two functions that
2532 describe the iterations that contain conflicting elements.
2534 Remark: For an integer k >= 0, the following equality is true:
2536 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2540 analyze_overlapping_iterations (tree chrec_a
,
2542 conflict_function
**overlap_iterations_a
,
2543 conflict_function
**overlap_iterations_b
,
2544 tree
*last_conflicts
, struct loop
*loop_nest
)
2546 unsigned int lnn
= loop_nest
->num
;
2548 dependence_stats
.num_subscript_tests
++;
2550 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2552 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2553 fprintf (dump_file
, " (chrec_a = ");
2554 print_generic_expr (dump_file
, chrec_a
, 0);
2555 fprintf (dump_file
, ")\n (chrec_b = ");
2556 print_generic_expr (dump_file
, chrec_b
, 0);
2557 fprintf (dump_file
, ")\n");
2560 if (chrec_a
== NULL_TREE
2561 || chrec_b
== NULL_TREE
2562 || chrec_contains_undetermined (chrec_a
)
2563 || chrec_contains_undetermined (chrec_b
))
2565 dependence_stats
.num_subscript_undetermined
++;
2567 *overlap_iterations_a
= conflict_fn_not_known ();
2568 *overlap_iterations_b
= conflict_fn_not_known ();
2571 /* If they are the same chrec, and are affine, they overlap
2572 on every iteration. */
2573 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2574 && evolution_function_is_affine_multivariate_p (chrec_a
, lnn
))
2576 dependence_stats
.num_same_subscript_function
++;
2577 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2578 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2579 *last_conflicts
= chrec_dont_know
;
2582 /* If they aren't the same, and aren't affine, we can't do anything
2584 else if ((chrec_contains_symbols (chrec_a
)
2585 || chrec_contains_symbols (chrec_b
))
2586 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2587 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2589 dependence_stats
.num_subscript_undetermined
++;
2590 *overlap_iterations_a
= conflict_fn_not_known ();
2591 *overlap_iterations_b
= conflict_fn_not_known ();
2594 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2595 analyze_ziv_subscript (chrec_a
, chrec_b
,
2596 overlap_iterations_a
, overlap_iterations_b
,
2599 else if (siv_subscript_p (chrec_a
, chrec_b
))
2600 analyze_siv_subscript (chrec_a
, chrec_b
,
2601 overlap_iterations_a
, overlap_iterations_b
,
2605 analyze_miv_subscript (chrec_a
, chrec_b
,
2606 overlap_iterations_a
, overlap_iterations_b
,
2607 last_conflicts
, loop_nest
);
2609 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2611 fprintf (dump_file
, " (overlap_iterations_a = ");
2612 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2613 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2614 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2615 fprintf (dump_file
, ")\n");
2616 fprintf (dump_file
, ")\n");
2620 /* Helper function for uniquely inserting distance vectors. */
2623 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2628 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
2629 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2632 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2635 /* Helper function for uniquely inserting direction vectors. */
2638 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2643 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
2644 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2647 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2650 /* Add a distance of 1 on all the loops outer than INDEX. If we
2651 haven't yet determined a distance for this outer loop, push a new
2652 distance vector composed of the previous distance, and a distance
2653 of 1 for this outer loop. Example:
2661 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2662 save (0, 1), then we have to save (1, 0). */
2665 add_outer_distances (struct data_dependence_relation
*ddr
,
2666 lambda_vector dist_v
, int index
)
2668 /* For each outer loop where init_v is not set, the accesses are
2669 in dependence of distance 1 in the loop. */
2670 while (--index
>= 0)
2672 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2673 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2675 save_dist_v (ddr
, save_v
);
2679 /* Return false when fail to represent the data dependence as a
2680 distance vector. INIT_B is set to true when a component has been
2681 added to the distance vector DIST_V. INDEX_CARRY is then set to
2682 the index in DIST_V that carries the dependence. */
2685 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2686 struct data_reference
*ddr_a
,
2687 struct data_reference
*ddr_b
,
2688 lambda_vector dist_v
, bool *init_b
,
2692 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2694 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2696 tree access_fn_a
, access_fn_b
;
2697 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2699 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2701 non_affine_dependence_relation (ddr
);
2705 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2706 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2708 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2709 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2712 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2713 DDR_LOOP_NEST (ddr
));
2714 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2715 DDR_LOOP_NEST (ddr
));
2717 /* The dependence is carried by the outermost loop. Example:
2724 In this case, the dependence is carried by loop_1. */
2725 index
= index_a
< index_b
? index_a
: index_b
;
2726 *index_carry
= MIN (index
, *index_carry
);
2728 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2730 non_affine_dependence_relation (ddr
);
2734 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2736 /* This is the subscript coupling test. If we have already
2737 recorded a distance for this loop (a distance coming from
2738 another subscript), it should be the same. For example,
2739 in the following code, there is no dependence:
2746 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2748 finalize_ddr_dependent (ddr
, chrec_known
);
2752 dist_v
[index
] = dist
;
2756 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2758 /* This can be for example an affine vs. constant dependence
2759 (T[i] vs. T[3]) that is not an affine dependence and is
2760 not representable as a distance vector. */
2761 non_affine_dependence_relation (ddr
);
2769 /* Return true when the DDR contains two data references that have the
2770 same access functions. */
2773 same_access_functions (struct data_dependence_relation
*ddr
)
2777 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2778 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr
), i
),
2779 DR_ACCESS_FN (DDR_B (ddr
), i
)))
2785 /* Return true when the DDR contains only constant access functions. */
2788 constant_access_functions (struct data_dependence_relation
*ddr
)
2792 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2793 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2794 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2801 /* Helper function for the case where DDR_A and DDR_B are the same
2802 multivariate access function. */
2805 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2808 tree c_1
= CHREC_LEFT (c_2
);
2809 tree c_0
= CHREC_LEFT (c_1
);
2810 lambda_vector dist_v
;
2813 /* Polynomials with more than 2 variables are not handled yet. */
2814 if (TREE_CODE (c_0
) != INTEGER_CST
)
2816 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2820 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2821 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2823 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2824 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2825 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2826 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2839 save_dist_v (ddr
, dist_v
);
2841 add_outer_distances (ddr
, dist_v
, x_1
);
2844 /* Helper function for the case where DDR_A and DDR_B are the same
2845 access functions. */
2848 add_other_self_distances (struct data_dependence_relation
*ddr
)
2850 lambda_vector dist_v
;
2852 int index_carry
= DDR_NB_LOOPS (ddr
);
2854 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2856 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
2858 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
2860 if (!evolution_function_is_univariate_p (access_fun
))
2862 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
2864 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2868 add_multivariate_self_dist (ddr
, DR_ACCESS_FN (DDR_A (ddr
), 0));
2872 index_carry
= MIN (index_carry
,
2873 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
2874 DDR_LOOP_NEST (ddr
)));
2878 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2879 add_outer_distances (ddr
, dist_v
, index_carry
);
2883 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
2885 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2887 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
2888 save_dist_v (ddr
, dist_v
);
2891 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2892 is the case for example when access functions are the same and
2893 equal to a constant, as in:
2900 in which case the distance vectors are (0) and (1). */
2903 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
2907 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2909 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
2910 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
2911 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
2913 for (j
= 0; j
< ca
->n
; j
++)
2914 if (affine_function_zero_p (ca
->fns
[j
]))
2916 insert_innermost_unit_dist_vector (ddr
);
2920 for (j
= 0; j
< cb
->n
; j
++)
2921 if (affine_function_zero_p (cb
->fns
[j
]))
2923 insert_innermost_unit_dist_vector (ddr
);
2929 /* Compute the classic per loop distance vector. DDR is the data
2930 dependence relation to build a vector from. Return false when fail
2931 to represent the data dependence as a distance vector. */
2934 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
2935 struct loop
*loop_nest
)
2937 bool init_b
= false;
2938 int index_carry
= DDR_NB_LOOPS (ddr
);
2939 lambda_vector dist_v
;
2941 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
2944 if (same_access_functions (ddr
))
2946 /* Save the 0 vector. */
2947 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2948 save_dist_v (ddr
, dist_v
);
2950 if (constant_access_functions (ddr
))
2951 add_distance_for_zero_overlaps (ddr
);
2953 if (DDR_NB_LOOPS (ddr
) > 1)
2954 add_other_self_distances (ddr
);
2959 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2960 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
2961 dist_v
, &init_b
, &index_carry
))
2964 /* Save the distance vector if we initialized one. */
2967 /* Verify a basic constraint: classic distance vectors should
2968 always be lexicographically positive.
2970 Data references are collected in the order of execution of
2971 the program, thus for the following loop
2973 | for (i = 1; i < 100; i++)
2974 | for (j = 1; j < 100; j++)
2976 | t = T[j+1][i-1]; // A
2977 | T[j][i] = t + 2; // B
2980 references are collected following the direction of the wind:
2981 A then B. The data dependence tests are performed also
2982 following this order, such that we're looking at the distance
2983 separating the elements accessed by A from the elements later
2984 accessed by B. But in this example, the distance returned by
2985 test_dep (A, B) is lexicographically negative (-1, 1), that
2986 means that the access A occurs later than B with respect to
2987 the outer loop, ie. we're actually looking upwind. In this
2988 case we solve test_dep (B, A) looking downwind to the
2989 lexicographically positive solution, that returns the
2990 distance vector (1, -1). */
2991 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
2993 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2994 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
2996 compute_subscript_distance (ddr
);
2997 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
2998 save_v
, &init_b
, &index_carry
);
2999 save_dist_v (ddr
, save_v
);
3000 DDR_REVERSED_P (ddr
) = true;
3002 /* In this case there is a dependence forward for all the
3005 | for (k = 1; k < 100; k++)
3006 | for (i = 1; i < 100; i++)
3007 | for (j = 1; j < 100; j++)
3009 | t = T[j+1][i-1]; // A
3010 | T[j][i] = t + 2; // B
3018 if (DDR_NB_LOOPS (ddr
) > 1)
3020 add_outer_distances (ddr
, save_v
, index_carry
);
3021 add_outer_distances (ddr
, dist_v
, index_carry
);
3026 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3027 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3028 save_dist_v (ddr
, save_v
);
3030 if (DDR_NB_LOOPS (ddr
) > 1)
3032 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3034 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3036 compute_subscript_distance (ddr
);
3037 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3038 opposite_v
, &init_b
, &index_carry
);
3040 add_outer_distances (ddr
, dist_v
, index_carry
);
3041 add_outer_distances (ddr
, opposite_v
, index_carry
);
3047 /* There is a distance of 1 on all the outer loops: Example:
3048 there is a dependence of distance 1 on loop_1 for the array A.
3054 add_outer_distances (ddr
, dist_v
,
3055 lambda_vector_first_nz (dist_v
,
3056 DDR_NB_LOOPS (ddr
), 0));
3059 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3063 fprintf (dump_file
, "(build_classic_dist_vector\n");
3064 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3066 fprintf (dump_file
, " dist_vector = (");
3067 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3068 DDR_NB_LOOPS (ddr
));
3069 fprintf (dump_file
, " )\n");
3071 fprintf (dump_file
, ")\n");
3077 /* Return the direction for a given distance.
3078 FIXME: Computing dir this way is suboptimal, since dir can catch
3079 cases that dist is unable to represent. */
3081 static inline enum data_dependence_direction
3082 dir_from_dist (int dist
)
3085 return dir_positive
;
3087 return dir_negative
;
3092 /* Compute the classic per loop direction vector. DDR is the data
3093 dependence relation to build a vector from. */
3096 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3099 lambda_vector dist_v
;
3101 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3103 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3105 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3106 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3108 save_dir_v (ddr
, dir_v
);
3112 /* Helper function. Returns true when there is a dependence between
3113 data references DRA and DRB. */
3116 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3117 struct data_reference
*dra
,
3118 struct data_reference
*drb
,
3119 struct loop
*loop_nest
)
3122 tree last_conflicts
;
3123 struct subscript
*subscript
;
3125 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3128 conflict_function
*overlaps_a
, *overlaps_b
;
3130 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3131 DR_ACCESS_FN (drb
, i
),
3132 &overlaps_a
, &overlaps_b
,
3133 &last_conflicts
, loop_nest
);
3135 if (CF_NOT_KNOWN_P (overlaps_a
)
3136 || CF_NOT_KNOWN_P (overlaps_b
))
3138 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3139 dependence_stats
.num_dependence_undetermined
++;
3140 free_conflict_function (overlaps_a
);
3141 free_conflict_function (overlaps_b
);
3145 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3146 || CF_NO_DEPENDENCE_P (overlaps_b
))
3148 finalize_ddr_dependent (ddr
, chrec_known
);
3149 dependence_stats
.num_dependence_independent
++;
3150 free_conflict_function (overlaps_a
);
3151 free_conflict_function (overlaps_b
);
3157 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3158 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3159 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3166 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3169 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3170 struct loop
*loop_nest
)
3173 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3174 fprintf (dump_file
, "(subscript_dependence_tester \n");
3176 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3177 dependence_stats
.num_dependence_dependent
++;
3179 compute_subscript_distance (ddr
);
3180 if (build_classic_dist_vector (ddr
, loop_nest
))
3181 build_classic_dir_vector (ddr
);
3183 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3184 fprintf (dump_file
, ")\n");
3187 /* Returns true when all the access functions of A are affine or
3188 constant with respect to LOOP_NEST. */
3191 access_functions_are_affine_or_constant_p (struct data_reference
*a
,
3192 struct loop
*loop_nest
)
3195 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3198 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
3199 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3200 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3206 /* Initializes an equation for an OMEGA problem using the information
3207 contained in the ACCESS_FUN. Returns true when the operation
3210 PB is the omega constraint system.
3211 EQ is the number of the equation to be initialized.
3212 OFFSET is used for shifting the variables names in the constraints:
3213 a constrain is composed of 2 * the number of variables surrounding
3214 dependence accesses. OFFSET is set either to 0 for the first n variables,
3215 then it is set to n.
3216 ACCESS_FUN is expected to be an affine chrec. */
3219 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3220 unsigned int offset
, tree access_fun
,
3221 struct data_dependence_relation
*ddr
)
3223 switch (TREE_CODE (access_fun
))
3225 case POLYNOMIAL_CHREC
:
3227 tree left
= CHREC_LEFT (access_fun
);
3228 tree right
= CHREC_RIGHT (access_fun
);
3229 int var
= CHREC_VARIABLE (access_fun
);
3232 if (TREE_CODE (right
) != INTEGER_CST
)
3235 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3236 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3238 /* Compute the innermost loop index. */
3239 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3242 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3243 += int_cst_value (right
);
3245 switch (TREE_CODE (left
))
3247 case POLYNOMIAL_CHREC
:
3248 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3251 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3260 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3268 /* As explained in the comments preceding init_omega_for_ddr, we have
3269 to set up a system for each loop level, setting outer loops
3270 variation to zero, and current loop variation to positive or zero.
3271 Save each lexico positive distance vector. */
3274 omega_extract_distance_vectors (omega_pb pb
,
3275 struct data_dependence_relation
*ddr
)
3279 struct loop
*loopi
, *loopj
;
3280 enum omega_result res
;
3282 /* Set a new problem for each loop in the nest. The basis is the
3283 problem that we have initialized until now. On top of this we
3284 add new constraints. */
3285 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3286 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3289 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3290 DDR_NB_LOOPS (ddr
));
3292 omega_copy_problem (copy
, pb
);
3294 /* For all the outer loops "loop_j", add "dj = 0". */
3296 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3298 eq
= omega_add_zero_eq (copy
, omega_black
);
3299 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3302 /* For "loop_i", add "0 <= di". */
3303 geq
= omega_add_zero_geq (copy
, omega_black
);
3304 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3306 /* Reduce the constraint system, and test that the current
3307 problem is feasible. */
3308 res
= omega_simplify_problem (copy
);
3309 if (res
== omega_false
3310 || res
== omega_unknown
3311 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3314 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3315 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3317 dist
= copy
->subs
[eq
].coef
[0];
3323 /* Reinitialize problem... */
3324 omega_copy_problem (copy
, pb
);
3326 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3328 eq
= omega_add_zero_eq (copy
, omega_black
);
3329 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3332 /* ..., but this time "di = 1". */
3333 eq
= omega_add_zero_eq (copy
, omega_black
);
3334 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3335 copy
->eqs
[eq
].coef
[0] = -1;
3337 res
= omega_simplify_problem (copy
);
3338 if (res
== omega_false
3339 || res
== omega_unknown
3340 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3343 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3344 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3346 dist
= copy
->subs
[eq
].coef
[0];
3352 /* Save the lexicographically positive distance vector. */
3355 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3356 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3360 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3361 if (copy
->subs
[eq
].key
> 0)
3363 dist
= copy
->subs
[eq
].coef
[0];
3364 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3367 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3368 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3370 save_dist_v (ddr
, dist_v
);
3371 save_dir_v (ddr
, dir_v
);
3375 omega_free_problem (copy
);
3379 /* This is called for each subscript of a tuple of data references:
3380 insert an equality for representing the conflicts. */
3383 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3384 struct data_dependence_relation
*ddr
,
3385 omega_pb pb
, bool *maybe_dependent
)
3388 tree fun_a
= chrec_convert (integer_type_node
, access_fun_a
, NULL_TREE
);
3389 tree fun_b
= chrec_convert (integer_type_node
, access_fun_b
, NULL_TREE
);
3390 tree difference
= chrec_fold_minus (integer_type_node
, fun_a
, fun_b
);
3392 /* When the fun_a - fun_b is not constant, the dependence is not
3393 captured by the classic distance vector representation. */
3394 if (TREE_CODE (difference
) != INTEGER_CST
)
3398 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3400 /* There is no dependence. */
3401 *maybe_dependent
= false;
3405 fun_b
= chrec_fold_multiply (integer_type_node
, fun_b
,
3406 integer_minus_one_node
);
3408 eq
= omega_add_zero_eq (pb
, omega_black
);
3409 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3410 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3411 /* There is probably a dependence, but the system of
3412 constraints cannot be built: answer "don't know". */
3416 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3417 && !int_divides_p (lambda_vector_gcd
3418 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3419 2 * DDR_NB_LOOPS (ddr
)),
3420 pb
->eqs
[eq
].coef
[0]))
3422 /* There is no dependence. */
3423 *maybe_dependent
= false;
3430 /* Helper function, same as init_omega_for_ddr but specialized for
3431 data references A and B. */
3434 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3435 struct data_dependence_relation
*ddr
,
3436 omega_pb pb
, bool *maybe_dependent
)
3441 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3443 /* Insert an equality per subscript. */
3444 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3446 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3447 ddr
, pb
, maybe_dependent
))
3449 else if (*maybe_dependent
== false)
3451 /* There is no dependence. */
3452 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3457 /* Insert inequalities: constraints corresponding to the iteration
3458 domain, i.e. the loops surrounding the references "loop_x" and
3459 the distance variables "dx". The layout of the OMEGA
3460 representation is as follows:
3461 - coef[0] is the constant
3462 - coef[1..nb_loops] are the protected variables that will not be
3463 removed by the solver: the "dx"
3464 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3466 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3467 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3469 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3472 ineq
= omega_add_zero_geq (pb
, omega_black
);
3473 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3475 /* 0 <= loop_x + dx */
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;
3482 /* loop_x <= nb_iters */
3483 ineq
= omega_add_zero_geq (pb
, omega_black
);
3484 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3485 pb
->geqs
[ineq
].coef
[0] = nbi
;
3487 /* loop_x + dx <= nb_iters */
3488 ineq
= omega_add_zero_geq (pb
, omega_black
);
3489 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3490 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3491 pb
->geqs
[ineq
].coef
[0] = nbi
;
3493 /* A step "dx" bigger than nb_iters is not feasible, so
3494 add "0 <= nb_iters + dx", */
3495 ineq
= omega_add_zero_geq (pb
, omega_black
);
3496 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3497 pb
->geqs
[ineq
].coef
[0] = nbi
;
3498 /* and "dx <= nb_iters". */
3499 ineq
= omega_add_zero_geq (pb
, omega_black
);
3500 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3501 pb
->geqs
[ineq
].coef
[0] = nbi
;
3505 omega_extract_distance_vectors (pb
, ddr
);
3510 /* Sets up the Omega dependence problem for the data dependence
3511 relation DDR. Returns false when the constraint system cannot be
3512 built, ie. when the test answers "don't know". Returns true
3513 otherwise, and when independence has been proved (using one of the
3514 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3515 set MAYBE_DEPENDENT to true.
3517 Example: for setting up the dependence system corresponding to the
3518 conflicting accesses
3523 | ... A[2*j, 2*(i + j)]
3527 the following constraints come from the iteration domain:
3534 where di, dj are the distance variables. The constraints
3535 representing the conflicting elements are:
3538 i + 1 = 2 * (i + di + j + dj)
3540 For asking that the resulting distance vector (di, dj) be
3541 lexicographically positive, we insert the constraint "di >= 0". If
3542 "di = 0" in the solution, we fix that component to zero, and we
3543 look at the inner loops: we set a new problem where all the outer
3544 loop distances are zero, and fix this inner component to be
3545 positive. When one of the components is positive, we save that
3546 distance, and set a new problem where the distance on this loop is
3547 zero, searching for other distances in the inner loops. Here is
3548 the classic example that illustrates that we have to set for each
3549 inner loop a new problem:
3557 we have to save two distances (1, 0) and (0, 1).
3559 Given two array references, refA and refB, we have to set the
3560 dependence problem twice, refA vs. refB and refB vs. refA, and we
3561 cannot do a single test, as refB might occur before refA in the
3562 inner loops, and the contrary when considering outer loops: ex.
3567 | T[{1,+,1}_2][{1,+,1}_1] // refA
3568 | T[{2,+,1}_2][{0,+,1}_1] // refB
3573 refB touches the elements in T before refA, and thus for the same
3574 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3575 but for successive loop_0 iterations, we have (1, -1, 1)
3577 The Omega solver expects the distance variables ("di" in the
3578 previous example) to come first in the constraint system (as
3579 variables to be protected, or "safe" variables), the constraint
3580 system is built using the following layout:
3582 "cst | distance vars | index vars".
3586 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3587 bool *maybe_dependent
)
3592 *maybe_dependent
= true;
3594 if (same_access_functions (ddr
))
3597 lambda_vector dir_v
;
3599 /* Save the 0 vector. */
3600 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3601 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3602 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3603 dir_v
[j
] = dir_equal
;
3604 save_dir_v (ddr
, dir_v
);
3606 /* Save the dependences carried by outer 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
);
3614 /* Omega expects the protected variables (those that have to be kept
3615 after elimination) to appear first in the constraint system.
3616 These variables are the distance variables. In the following
3617 initialization we declare NB_LOOPS safe variables, and the total
3618 number of variables for the constraint system is 2*NB_LOOPS. */
3619 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3620 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3622 omega_free_problem (pb
);
3624 /* Stop computation if not decidable, or no dependence. */
3625 if (res
== false || *maybe_dependent
== false)
3628 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3629 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3631 omega_free_problem (pb
);
3636 /* Return true when DDR contains the same information as that stored
3637 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3640 ddr_consistent_p (FILE *file
,
3641 struct data_dependence_relation
*ddr
,
3642 VEC (lambda_vector
, heap
) *dist_vects
,
3643 VEC (lambda_vector
, heap
) *dir_vects
)
3647 /* If dump_file is set, output there. */
3648 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3651 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3653 lambda_vector b_dist_v
;
3654 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3655 VEC_length (lambda_vector
, dist_vects
),
3656 DDR_NUM_DIST_VECTS (ddr
));
3658 fprintf (file
, "Banerjee dist vectors:\n");
3659 for (i
= 0; VEC_iterate (lambda_vector
, dist_vects
, i
, b_dist_v
); i
++)
3660 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3662 fprintf (file
, "Omega dist vectors:\n");
3663 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3664 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3666 fprintf (file
, "data dependence relation:\n");
3667 dump_data_dependence_relation (file
, ddr
);
3669 fprintf (file
, ")\n");
3673 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3675 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3676 VEC_length (lambda_vector
, dir_vects
),
3677 DDR_NUM_DIR_VECTS (ddr
));
3681 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3683 lambda_vector a_dist_v
;
3684 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3686 /* Distance vectors are not ordered in the same way in the DDR
3687 and in the DIST_VECTS: search for a matching vector. */
3688 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, a_dist_v
); j
++)
3689 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3692 if (j
== VEC_length (lambda_vector
, dist_vects
))
3694 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3695 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3696 fprintf (file
, "not found in Omega dist vectors:\n");
3697 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3698 fprintf (file
, "data dependence relation:\n");
3699 dump_data_dependence_relation (file
, ddr
);
3700 fprintf (file
, ")\n");
3704 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3706 lambda_vector a_dir_v
;
3707 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3709 /* Direction vectors are not ordered in the same way in the DDR
3710 and in the DIR_VECTS: search for a matching vector. */
3711 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, a_dir_v
); j
++)
3712 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3715 if (j
== VEC_length (lambda_vector
, dist_vects
))
3717 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3718 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3719 fprintf (file
, "not found in Omega dir vectors:\n");
3720 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3721 fprintf (file
, "data dependence relation:\n");
3722 dump_data_dependence_relation (file
, ddr
);
3723 fprintf (file
, ")\n");
3730 /* This computes the affine dependence relation between A and B with
3731 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3732 independence between two accesses, while CHREC_DONT_KNOW is used
3733 for representing the unknown relation.
3735 Note that it is possible to stop the computation of the dependence
3736 relation the first time we detect a CHREC_KNOWN element for a given
3740 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3741 struct loop
*loop_nest
)
3743 struct data_reference
*dra
= DDR_A (ddr
);
3744 struct data_reference
*drb
= DDR_B (ddr
);
3746 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3748 fprintf (dump_file
, "(compute_affine_dependence\n");
3749 fprintf (dump_file
, " (stmt_a = \n");
3750 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
3751 fprintf (dump_file
, ")\n (stmt_b = \n");
3752 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
3753 fprintf (dump_file
, ")\n");
3756 /* Analyze only when the dependence relation is not yet known. */
3757 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3759 dependence_stats
.num_dependence_tests
++;
3761 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3762 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3764 if (flag_check_data_deps
)
3766 /* Compute the dependences using the first algorithm. */
3767 subscript_dependence_tester (ddr
, loop_nest
);
3769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3771 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3772 dump_data_dependence_relation (dump_file
, ddr
);
3775 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3777 bool maybe_dependent
;
3778 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3780 /* Save the result of the first DD analyzer. */
3781 dist_vects
= DDR_DIST_VECTS (ddr
);
3782 dir_vects
= DDR_DIR_VECTS (ddr
);
3784 /* Reset the information. */
3785 DDR_DIST_VECTS (ddr
) = NULL
;
3786 DDR_DIR_VECTS (ddr
) = NULL
;
3788 /* Compute the same information using Omega. */
3789 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3790 goto csys_dont_know
;
3792 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3794 fprintf (dump_file
, "Omega Analyzer\n");
3795 dump_data_dependence_relation (dump_file
, ddr
);
3798 /* Check that we get the same information. */
3799 if (maybe_dependent
)
3800 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3805 subscript_dependence_tester (ddr
, loop_nest
);
3808 /* As a last case, if the dependence cannot be determined, or if
3809 the dependence is considered too difficult to determine, answer
3814 dependence_stats
.num_dependence_undetermined
++;
3816 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3818 fprintf (dump_file
, "Data ref a:\n");
3819 dump_data_reference (dump_file
, dra
);
3820 fprintf (dump_file
, "Data ref b:\n");
3821 dump_data_reference (dump_file
, drb
);
3822 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3824 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3828 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3829 fprintf (dump_file
, ")\n");
3832 /* This computes the dependence relation for the same data
3833 reference into DDR. */
3836 compute_self_dependence (struct data_dependence_relation
*ddr
)
3839 struct subscript
*subscript
;
3841 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3844 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3847 /* The accessed index overlaps for each iteration. */
3848 SUB_CONFLICTS_IN_A (subscript
)
3849 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3850 SUB_CONFLICTS_IN_B (subscript
)
3851 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3852 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3855 /* The distance vector is the zero vector. */
3856 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3857 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3860 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3861 the data references in DATAREFS, in the LOOP_NEST. When
3862 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3866 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
3867 VEC (ddr_p
, heap
) **dependence_relations
,
3868 VEC (loop_p
, heap
) *loop_nest
,
3869 bool compute_self_and_rr
)
3871 struct data_dependence_relation
*ddr
;
3872 struct data_reference
*a
, *b
;
3875 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
3876 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
3877 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
3879 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
3880 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3881 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
3884 if (compute_self_and_rr
)
3885 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
3887 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
3888 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3889 compute_self_dependence (ddr
);
3893 /* Stores the locations of memory references in STMT to REFERENCES. Returns
3894 true if STMT clobbers memory, false otherwise. */
3897 get_references_in_stmt (tree stmt
, VEC (data_ref_loc
, heap
) **references
)
3899 bool clobbers_memory
= false;
3901 tree
*op0
, *op1
, call
;
3905 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3906 Calls have side-effects, except those to const or pure
3908 call
= get_call_expr_in (stmt
);
3910 && !(call_expr_flags (call
) & (ECF_CONST
| ECF_PURE
)))
3911 || (TREE_CODE (stmt
) == ASM_EXPR
3912 && ASM_VOLATILE_P (stmt
)))
3913 clobbers_memory
= true;
3915 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
3916 return clobbers_memory
;
3918 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3920 op0
= &GIMPLE_STMT_OPERAND (stmt
, 0);
3921 op1
= &GIMPLE_STMT_OPERAND (stmt
, 1);
3924 || REFERENCE_CLASS_P (*op1
))
3926 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
3928 ref
->is_read
= true;
3932 || REFERENCE_CLASS_P (*op0
))
3934 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
3936 ref
->is_read
= false;
3942 unsigned i
, n
= call_expr_nargs (call
);
3944 for (i
= 0; i
< n
; i
++)
3946 op0
= &CALL_EXPR_ARG (call
, i
);
3949 || REFERENCE_CLASS_P (*op0
))
3951 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
3953 ref
->is_read
= true;
3958 return clobbers_memory
;
3961 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
3962 reference, returns false, otherwise returns true. NEST is the outermost
3963 loop of the loop nest in that the references should be analyzed. */
3966 find_data_references_in_stmt (struct loop
*nest
, tree stmt
,
3967 VEC (data_reference_p
, heap
) **datarefs
)
3970 VEC (data_ref_loc
, heap
) *references
;
3973 data_reference_p dr
;
3975 if (get_references_in_stmt (stmt
, &references
))
3977 VEC_free (data_ref_loc
, heap
, references
);
3981 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
3983 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
3984 gcc_assert (dr
!= NULL
);
3986 /* FIXME -- data dependence analysis does not work correctly for objects with
3987 invariant addresses. Let us fail here until the problem is fixed. */
3988 if (dr_address_invariant_p (dr
))
3991 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3992 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
3997 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
3999 VEC_free (data_ref_loc
, heap
, references
);
4003 /* Search the data references in LOOP, and record the information into
4004 DATAREFS. Returns chrec_dont_know when failing to analyze a
4005 difficult case, returns NULL_TREE otherwise.
4007 TODO: This function should be made smarter so that it can handle address
4008 arithmetic as if they were array accesses, etc. */
4011 find_data_references_in_loop (struct loop
*loop
,
4012 VEC (data_reference_p
, heap
) **datarefs
)
4014 basic_block bb
, *bbs
;
4016 block_stmt_iterator bsi
;
4018 bbs
= get_loop_body_in_dom_order (loop
);
4020 for (i
= 0; i
< loop
->num_nodes
; i
++)
4024 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4026 tree stmt
= bsi_stmt (bsi
);
4028 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4030 struct data_reference
*res
;
4031 res
= XCNEW (struct data_reference
);
4032 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4035 return chrec_dont_know
;
4044 /* Recursive helper function. */
4047 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4049 /* Inner loops of the nest should not contain siblings. Example:
4050 when there are two consecutive loops,
4061 the dependence relation cannot be captured by the distance
4066 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4068 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4072 /* Return false when the LOOP is not well nested. Otherwise return
4073 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4074 contain the loops from the outermost to the innermost, as they will
4075 appear in the classic distance vector. */
4078 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4080 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4082 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4086 /* Given a loop nest LOOP, the following vectors are returned:
4087 DATAREFS is initialized to all the array elements contained in this loop,
4088 DEPENDENCE_RELATIONS contains the relations between the data references.
4089 Compute read-read and self relations if
4090 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4093 compute_data_dependences_for_loop (struct loop
*loop
,
4094 bool compute_self_and_read_read_dependences
,
4095 VEC (data_reference_p
, heap
) **datarefs
,
4096 VEC (ddr_p
, heap
) **dependence_relations
)
4098 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4100 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4102 /* If the loop nest is not well formed, or one of the data references
4103 is not computable, give up without spending time to compute other
4106 || !find_loop_nest (loop
, &vloops
)
4107 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4109 struct data_dependence_relation
*ddr
;
4111 /* Insert a single relation into dependence_relations:
4113 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4114 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4117 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4118 compute_self_and_read_read_dependences
);
4120 if (dump_file
&& (dump_flags
& TDF_STATS
))
4122 fprintf (dump_file
, "Dependence tester statistics:\n");
4124 fprintf (dump_file
, "Number of dependence tests: %d\n",
4125 dependence_stats
.num_dependence_tests
);
4126 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4127 dependence_stats
.num_dependence_dependent
);
4128 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4129 dependence_stats
.num_dependence_independent
);
4130 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4131 dependence_stats
.num_dependence_undetermined
);
4133 fprintf (dump_file
, "Number of subscript tests: %d\n",
4134 dependence_stats
.num_subscript_tests
);
4135 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4136 dependence_stats
.num_subscript_undetermined
);
4137 fprintf (dump_file
, "Number of same subscript function: %d\n",
4138 dependence_stats
.num_same_subscript_function
);
4140 fprintf (dump_file
, "Number of ziv tests: %d\n",
4141 dependence_stats
.num_ziv
);
4142 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4143 dependence_stats
.num_ziv_dependent
);
4144 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4145 dependence_stats
.num_ziv_independent
);
4146 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4147 dependence_stats
.num_ziv_unimplemented
);
4149 fprintf (dump_file
, "Number of siv tests: %d\n",
4150 dependence_stats
.num_siv
);
4151 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4152 dependence_stats
.num_siv_dependent
);
4153 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4154 dependence_stats
.num_siv_independent
);
4155 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4156 dependence_stats
.num_siv_unimplemented
);
4158 fprintf (dump_file
, "Number of miv tests: %d\n",
4159 dependence_stats
.num_miv
);
4160 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4161 dependence_stats
.num_miv_dependent
);
4162 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4163 dependence_stats
.num_miv_independent
);
4164 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4165 dependence_stats
.num_miv_unimplemented
);
4169 /* Entry point (for testing only). Analyze all the data references
4170 and the dependence relations in LOOP.
4172 The data references are computed first.
4174 A relation on these nodes is represented by a complete graph. Some
4175 of the relations could be of no interest, thus the relations can be
4178 In the following function we compute all the relations. This is
4179 just a first implementation that is here for:
4180 - for showing how to ask for the dependence relations,
4181 - for the debugging the whole dependence graph,
4182 - for the dejagnu testcases and maintenance.
4184 It is possible to ask only for a part of the graph, avoiding to
4185 compute the whole dependence graph. The computed dependences are
4186 stored in a knowledge base (KB) such that later queries don't
4187 recompute the same information. The implementation of this KB is
4188 transparent to the optimizer, and thus the KB can be changed with a
4189 more efficient implementation, or the KB could be disabled. */
4191 analyze_all_data_dependences (struct loop
*loop
)
4194 int nb_data_refs
= 10;
4195 VEC (data_reference_p
, heap
) *datarefs
=
4196 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4197 VEC (ddr_p
, heap
) *dependence_relations
=
4198 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4200 /* Compute DDs on the whole function. */
4201 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4202 &dependence_relations
);
4206 dump_data_dependence_relations (dump_file
, dependence_relations
);
4207 fprintf (dump_file
, "\n\n");
4209 if (dump_flags
& TDF_DETAILS
)
4210 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4212 if (dump_flags
& TDF_STATS
)
4214 unsigned nb_top_relations
= 0;
4215 unsigned nb_bot_relations
= 0;
4216 unsigned nb_basename_differ
= 0;
4217 unsigned nb_chrec_relations
= 0;
4218 struct data_dependence_relation
*ddr
;
4220 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4222 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4225 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4227 struct data_reference
*a
= DDR_A (ddr
);
4228 struct data_reference
*b
= DDR_B (ddr
);
4230 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
4231 nb_basename_differ
++;
4237 nb_chrec_relations
++;
4240 gather_stats_on_scev_database ();
4244 free_dependence_relations (dependence_relations
);
4245 free_data_refs (datarefs
);
4248 /* Computes all the data dependences and check that the results of
4249 several analyzers are the same. */
4252 tree_check_data_deps (void)
4255 struct loop
*loop_nest
;
4257 FOR_EACH_LOOP (li
, loop_nest
, 0)
4258 analyze_all_data_dependences (loop_nest
);
4261 /* Free the memory used by a data dependence relation DDR. */
4264 free_dependence_relation (struct data_dependence_relation
*ddr
)
4269 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
4270 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4275 /* Free the memory used by the data dependence relations from
4276 DEPENDENCE_RELATIONS. */
4279 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4282 struct data_dependence_relation
*ddr
;
4283 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4285 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4289 if (loop_nest
== NULL
)
4290 loop_nest
= DDR_LOOP_NEST (ddr
);
4292 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4293 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4294 free_dependence_relation (ddr
);
4298 VEC_free (loop_p
, heap
, loop_nest
);
4299 VEC_free (ddr_p
, heap
, dependence_relations
);
4302 /* Free the memory used by the data references from DATAREFS. */
4305 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4308 struct data_reference
*dr
;
4310 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4312 VEC_free (data_reference_p
, heap
, datarefs
);