1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass walks a given loop structure searching for array
22 references. The information about the array accesses is recorded
23 in DATA_REFERENCE structures.
25 The basic test for determining the dependences is:
26 given two access functions chrec1 and chrec2 to a same array, and
27 x and y two vectors from the iteration domain, the same element of
28 the array is accessed twice at iterations x and y if and only if:
29 | chrec1 (x) == chrec2 (y).
31 The goals of this analysis are:
33 - to determine the independence: the relation between two
34 independent accesses is qualified with the chrec_known (this
35 information allows a loop parallelization),
37 - when two data references access the same data, to qualify the
38 dependence relation with classic dependence representations:
42 - loop carried level dependence
43 - polyhedron dependence
44 or with the chains of recurrences based representation,
46 - to define a knowledge base for storing the data dependence
49 - to define an interface to access this data.
54 - subscript: given two array accesses a subscript is the tuple
55 composed of the access functions for a given dimension. Example:
56 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
57 (f1, g1), (f2, g2), (f3, g3).
59 - Diophantine equation: an equation whose coefficients and
60 solutions are integer constants, for example the equation
62 has an integer solution x = 1 and y = -1.
66 - "Advanced Compilation for High Performance Computing" by Randy
67 Allen and Ken Kennedy.
68 http://citeseer.ist.psu.edu/goff91practical.html
70 - "Loop Transformations for Restructuring Compilers - The Foundations"
78 #include "coretypes.h"
83 /* These RTL headers are needed for basic-block.h. */
85 #include "basic-block.h"
86 #include "diagnostic.h"
87 #include "tree-flow.h"
88 #include "tree-dump.h"
91 #include "tree-chrec.h"
92 #include "tree-data-ref.h"
93 #include "tree-scalar-evolution.h"
94 #include "tree-pass.h"
95 #include "langhooks.h"
97 static struct datadep_stats
99 int num_dependence_tests
;
100 int num_dependence_dependent
;
101 int num_dependence_independent
;
102 int num_dependence_undetermined
;
104 int num_subscript_tests
;
105 int num_subscript_undetermined
;
106 int num_same_subscript_function
;
109 int num_ziv_independent
;
110 int num_ziv_dependent
;
111 int num_ziv_unimplemented
;
114 int num_siv_independent
;
115 int num_siv_dependent
;
116 int num_siv_unimplemented
;
119 int num_miv_independent
;
120 int num_miv_dependent
;
121 int num_miv_unimplemented
;
124 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
125 struct data_reference
*,
126 struct data_reference
*,
128 /* Returns true iff A divides B. */
131 tree_fold_divides_p (const_tree a
, const_tree b
)
133 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
134 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
135 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
, 0));
138 /* Returns true iff A divides B. */
141 int_divides_p (int a
, int b
)
143 return ((b
% a
) == 0);
148 /* Dump into FILE all the data references from DATAREFS. */
151 dump_data_references (FILE *file
, VEC (data_reference_p
, heap
) *datarefs
)
154 struct data_reference
*dr
;
156 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
157 dump_data_reference (file
, dr
);
160 /* Dump into FILE all the dependence relations from DDRS. */
163 dump_data_dependence_relations (FILE *file
,
164 VEC (ddr_p
, heap
) *ddrs
)
167 struct data_dependence_relation
*ddr
;
169 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
170 dump_data_dependence_relation (file
, ddr
);
173 /* Dump function for a DATA_REFERENCE structure. */
176 dump_data_reference (FILE *outf
,
177 struct data_reference
*dr
)
181 fprintf (outf
, "(Data Ref: \n stmt: ");
182 print_generic_stmt (outf
, DR_STMT (dr
), 0);
183 fprintf (outf
, " ref: ");
184 print_generic_stmt (outf
, DR_REF (dr
), 0);
185 fprintf (outf
, " base_object: ");
186 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
188 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
190 fprintf (outf
, " Access function %d: ", i
);
191 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
193 fprintf (outf
, ")\n");
196 /* Dumps the affine function described by FN to the file OUTF. */
199 dump_affine_function (FILE *outf
, affine_fn fn
)
204 print_generic_expr (outf
, VEC_index (tree
, fn
, 0), TDF_SLIM
);
205 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
207 fprintf (outf
, " + ");
208 print_generic_expr (outf
, coef
, TDF_SLIM
);
209 fprintf (outf
, " * x_%u", i
);
213 /* Dumps the conflict function CF to the file OUTF. */
216 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
220 if (cf
->n
== NO_DEPENDENCE
)
221 fprintf (outf
, "no dependence\n");
222 else if (cf
->n
== NOT_KNOWN
)
223 fprintf (outf
, "not known\n");
226 for (i
= 0; i
< cf
->n
; i
++)
229 dump_affine_function (outf
, cf
->fns
[i
]);
230 fprintf (outf
, "]\n");
235 /* Dump function for a SUBSCRIPT structure. */
238 dump_subscript (FILE *outf
, struct subscript
*subscript
)
240 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
242 fprintf (outf
, "\n (subscript \n");
243 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
244 dump_conflict_function (outf
, cf
);
245 if (CF_NONTRIVIAL_P (cf
))
247 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
248 fprintf (outf
, " last_conflict: ");
249 print_generic_stmt (outf
, last_iteration
, 0);
252 cf
= SUB_CONFLICTS_IN_B (subscript
);
253 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
254 dump_conflict_function (outf
, cf
);
255 if (CF_NONTRIVIAL_P (cf
))
257 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
258 fprintf (outf
, " last_conflict: ");
259 print_generic_stmt (outf
, last_iteration
, 0);
262 fprintf (outf
, " (Subscript distance: ");
263 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
264 fprintf (outf
, " )\n");
265 fprintf (outf
, " )\n");
268 /* Print the classic direction vector DIRV to OUTF. */
271 print_direction_vector (FILE *outf
,
277 for (eq
= 0; eq
< length
; eq
++)
279 enum data_dependence_direction dir
= dirv
[eq
];
284 fprintf (outf
, " +");
287 fprintf (outf
, " -");
290 fprintf (outf
, " =");
292 case dir_positive_or_equal
:
293 fprintf (outf
, " +=");
295 case dir_positive_or_negative
:
296 fprintf (outf
, " +-");
298 case dir_negative_or_equal
:
299 fprintf (outf
, " -=");
302 fprintf (outf
, " *");
305 fprintf (outf
, "indep");
309 fprintf (outf
, "\n");
312 /* Print a vector of direction vectors. */
315 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
321 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
322 print_direction_vector (outf
, v
, length
);
325 /* Print a vector of distance vectors. */
328 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
334 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
335 print_lambda_vector (outf
, v
, length
);
341 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
343 dump_data_dependence_relation (stderr
, ddr
);
346 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
349 dump_data_dependence_relation (FILE *outf
,
350 struct data_dependence_relation
*ddr
)
352 struct data_reference
*dra
, *drb
;
356 fprintf (outf
, "(Data Dep: \n");
357 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
358 fprintf (outf
, " (don't know)\n");
360 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
361 fprintf (outf
, " (no dependence)\n");
363 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
368 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
370 fprintf (outf
, " access_fn_A: ");
371 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
372 fprintf (outf
, " access_fn_B: ");
373 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
374 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
377 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
378 fprintf (outf
, " loop nest: (");
379 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
380 fprintf (outf
, "%d ", loopi
->num
);
381 fprintf (outf
, ")\n");
383 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
385 fprintf (outf
, " distance_vector: ");
386 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
390 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
392 fprintf (outf
, " direction_vector: ");
393 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
398 fprintf (outf
, ")\n");
401 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
404 dump_data_dependence_direction (FILE *file
,
405 enum data_dependence_direction dir
)
421 case dir_positive_or_negative
:
422 fprintf (file
, "+-");
425 case dir_positive_or_equal
:
426 fprintf (file
, "+=");
429 case dir_negative_or_equal
:
430 fprintf (file
, "-=");
442 /* Dumps the distance and direction vectors in FILE. DDRS contains
443 the dependence relations, and VECT_SIZE is the size of the
444 dependence vectors, or in other words the number of loops in the
448 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
451 struct data_dependence_relation
*ddr
;
454 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
455 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
457 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
459 fprintf (file
, "DISTANCE_V (");
460 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
461 fprintf (file
, ")\n");
464 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
466 fprintf (file
, "DIRECTION_V (");
467 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
468 fprintf (file
, ")\n");
472 fprintf (file
, "\n\n");
475 /* Dumps the data dependence relations DDRS in FILE. */
478 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
481 struct data_dependence_relation
*ddr
;
483 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
484 dump_data_dependence_relation (file
, ddr
);
486 fprintf (file
, "\n\n");
489 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
490 will be ssizetype. */
493 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
495 tree type
= TREE_TYPE (exp
), otype
;
502 otype
= TREE_TYPE (exp
);
503 code
= TREE_CODE (exp
);
508 *var
= build_int_cst (type
, 0);
509 *off
= fold_convert (ssizetype
, exp
);
512 case POINTER_PLUS_EXPR
:
517 split_constant_offset (TREE_OPERAND (exp
, 0), &var0
, &off0
);
518 split_constant_offset (TREE_OPERAND (exp
, 1), &var1
, &off1
);
519 *var
= fold_convert (type
, fold_build2 (TREE_CODE (exp
), otype
,
521 *off
= size_binop (code
, off0
, off1
);
525 off1
= TREE_OPERAND (exp
, 1);
526 if (TREE_CODE (off1
) != INTEGER_CST
)
529 split_constant_offset (TREE_OPERAND (exp
, 0), &var0
, &off0
);
530 *var
= fold_convert (type
, fold_build2 (MULT_EXPR
, otype
,
532 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, off1
));
537 tree op
, base
, poffset
;
538 HOST_WIDE_INT pbitsize
, pbitpos
;
539 enum machine_mode pmode
;
540 int punsignedp
, pvolatilep
;
542 op
= TREE_OPERAND (exp
, 0);
543 if (!handled_component_p (op
))
546 base
= get_inner_reference (op
, &pbitsize
, &pbitpos
, &poffset
,
547 &pmode
, &punsignedp
, &pvolatilep
, false);
549 if (pbitpos
% BITS_PER_UNIT
!= 0)
551 base
= build_fold_addr_expr (base
);
552 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
556 split_constant_offset (poffset
, &poffset
, &off1
);
557 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
558 if (POINTER_TYPE_P (TREE_TYPE (base
)))
559 base
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (base
),
560 base
, fold_convert (sizetype
, poffset
));
562 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
563 fold_convert (TREE_TYPE (base
), poffset
));
566 var0
= fold_convert (type
, base
);
568 /* If variable length types are involved, punt, otherwise casts
569 might be converted into ARRAY_REFs in gimplify_conversion.
570 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
571 possibly no longer appears in current GIMPLE, might resurface.
572 This perhaps could run
573 if (TREE_CODE (var0) == NOP_EXPR
574 || TREE_CODE (var0) == CONVERT_EXPR)
576 gimplify_conversion (&var0);
577 // Attempt to fill in any within var0 found ARRAY_REF's
578 // element size from corresponding op embedded ARRAY_REF,
579 // if unsuccessful, just punt.
581 while (POINTER_TYPE_P (type
))
582 type
= TREE_TYPE (type
);
583 if (int_size_in_bytes (type
) < 0)
593 tree def_stmt
= SSA_NAME_DEF_STMT (exp
);
594 if (TREE_CODE (def_stmt
) == GIMPLE_MODIFY_STMT
)
596 tree def_stmt_rhs
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
598 if (!TREE_SIDE_EFFECTS (def_stmt_rhs
)
599 && EXPR_P (def_stmt_rhs
)
600 && !REFERENCE_CLASS_P (def_stmt_rhs
)
601 && !get_call_expr_in (def_stmt_rhs
))
603 split_constant_offset (def_stmt_rhs
, &var0
, &off0
);
604 var0
= fold_convert (type
, var0
);
617 *off
= ssize_int (0);
620 /* Returns the address ADDR of an object in a canonical shape (without nop
621 casts, and with type of pointer to the object). */
624 canonicalize_base_object_address (tree addr
)
630 /* The base address may be obtained by casting from integer, in that case
632 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
635 if (TREE_CODE (addr
) != ADDR_EXPR
)
638 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
641 /* Analyzes the behavior of the memory reference DR in the innermost loop that
645 dr_analyze_innermost (struct data_reference
*dr
)
647 tree stmt
= DR_STMT (dr
);
648 struct loop
*loop
= loop_containing_stmt (stmt
);
649 tree ref
= DR_REF (dr
);
650 HOST_WIDE_INT pbitsize
, pbitpos
;
652 enum machine_mode pmode
;
653 int punsignedp
, pvolatilep
;
654 affine_iv base_iv
, offset_iv
;
655 tree init
, dinit
, step
;
657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
658 fprintf (dump_file
, "analyze_innermost: ");
660 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
661 &pmode
, &punsignedp
, &pvolatilep
, false);
662 gcc_assert (base
!= NULL_TREE
);
664 if (pbitpos
% BITS_PER_UNIT
!= 0)
666 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
667 fprintf (dump_file
, "failed: bit offset alignment.\n");
671 base
= build_fold_addr_expr (base
);
672 if (!simple_iv (loop
, stmt
, base
, &base_iv
, false))
674 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
675 fprintf (dump_file
, "failed: evolution of base is not affine.\n");
680 offset_iv
.base
= ssize_int (0);
681 offset_iv
.step
= ssize_int (0);
683 else if (!simple_iv (loop
, stmt
, poffset
, &offset_iv
, false))
685 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
686 fprintf (dump_file
, "failed: evolution of offset is not affine.\n");
690 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
691 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
692 init
= size_binop (PLUS_EXPR
, init
, dinit
);
693 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
694 init
= size_binop (PLUS_EXPR
, init
, dinit
);
696 step
= size_binop (PLUS_EXPR
,
697 fold_convert (ssizetype
, base_iv
.step
),
698 fold_convert (ssizetype
, offset_iv
.step
));
700 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
702 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
706 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
708 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
709 fprintf (dump_file
, "success.\n");
712 /* Determines the base object and the list of indices of memory reference
713 DR, analyzed in loop nest NEST. */
716 dr_analyze_indices (struct data_reference
*dr
, struct loop
*nest
)
718 tree stmt
= DR_STMT (dr
);
719 struct loop
*loop
= loop_containing_stmt (stmt
);
720 VEC (tree
, heap
) *access_fns
= NULL
;
721 tree ref
= unshare_expr (DR_REF (dr
)), aref
= ref
, op
;
722 tree base
, off
, access_fn
;
724 while (handled_component_p (aref
))
726 if (TREE_CODE (aref
) == ARRAY_REF
)
728 op
= TREE_OPERAND (aref
, 1);
729 access_fn
= analyze_scalar_evolution (loop
, op
);
730 access_fn
= resolve_mixers (nest
, access_fn
);
731 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
733 TREE_OPERAND (aref
, 1) = build_int_cst (TREE_TYPE (op
), 0);
736 aref
= TREE_OPERAND (aref
, 0);
739 if (INDIRECT_REF_P (aref
))
741 op
= TREE_OPERAND (aref
, 0);
742 access_fn
= analyze_scalar_evolution (loop
, op
);
743 access_fn
= resolve_mixers (nest
, access_fn
);
744 base
= initial_condition (access_fn
);
745 split_constant_offset (base
, &base
, &off
);
746 access_fn
= chrec_replace_initial_condition (access_fn
,
747 fold_convert (TREE_TYPE (base
), off
));
749 TREE_OPERAND (aref
, 0) = base
;
750 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
753 DR_BASE_OBJECT (dr
) = ref
;
754 DR_ACCESS_FNS (dr
) = access_fns
;
757 /* Extracts the alias analysis information from the memory reference DR. */
760 dr_analyze_alias (struct data_reference
*dr
)
762 tree stmt
= DR_STMT (dr
);
763 tree ref
= DR_REF (dr
);
764 tree base
= get_base_address (ref
), addr
, smt
= NULL_TREE
;
771 else if (INDIRECT_REF_P (base
))
773 addr
= TREE_OPERAND (base
, 0);
774 if (TREE_CODE (addr
) == SSA_NAME
)
776 smt
= symbol_mem_tag (SSA_NAME_VAR (addr
));
777 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
781 DR_SYMBOL_TAG (dr
) = smt
;
782 if (smt
&& var_can_have_subvars (smt
))
783 DR_SUBVARS (dr
) = get_subvars_for_var (smt
);
785 vops
= BITMAP_ALLOC (NULL
);
786 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, it
, SSA_OP_VIRTUAL_USES
)
788 bitmap_set_bit (vops
, DECL_UID (SSA_NAME_VAR (op
)));
794 /* Returns true if the address of DR is invariant. */
797 dr_address_invariant_p (struct data_reference
*dr
)
802 for (i
= 0; VEC_iterate (tree
, DR_ACCESS_FNS (dr
), i
, idx
); i
++)
803 if (tree_contains_chrecs (idx
, NULL
))
809 /* Frees data reference DR. */
812 free_data_ref (data_reference_p dr
)
814 BITMAP_FREE (DR_VOPS (dr
));
815 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
819 /* Analyzes memory reference MEMREF accessed in STMT. The reference
820 is read if IS_READ is true, write otherwise. Returns the
821 data_reference description of MEMREF. NEST is the outermost loop of the
822 loop nest in that the reference should be analyzed. */
824 struct data_reference
*
825 create_data_ref (struct loop
*nest
, tree memref
, tree stmt
, bool is_read
)
827 struct data_reference
*dr
;
829 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
831 fprintf (dump_file
, "Creating dr for ");
832 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
833 fprintf (dump_file
, "\n");
836 dr
= XCNEW (struct data_reference
);
838 DR_REF (dr
) = memref
;
839 DR_IS_READ (dr
) = is_read
;
841 dr_analyze_innermost (dr
);
842 dr_analyze_indices (dr
, nest
);
843 dr_analyze_alias (dr
);
845 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
847 fprintf (dump_file
, "\tbase_address: ");
848 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
849 fprintf (dump_file
, "\n\toffset from base address: ");
850 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
851 fprintf (dump_file
, "\n\tconstant offset from base address: ");
852 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
853 fprintf (dump_file
, "\n\tstep: ");
854 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
855 fprintf (dump_file
, "\n\taligned to: ");
856 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
857 fprintf (dump_file
, "\n\tbase_object: ");
858 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
859 fprintf (dump_file
, "\n\tsymbol tag: ");
860 print_generic_expr (dump_file
, DR_SYMBOL_TAG (dr
), TDF_SLIM
);
861 fprintf (dump_file
, "\n");
867 /* Returns true if FNA == FNB. */
870 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
872 unsigned i
, n
= VEC_length (tree
, fna
);
874 if (n
!= VEC_length (tree
, fnb
))
877 for (i
= 0; i
< n
; i
++)
878 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
879 VEC_index (tree
, fnb
, i
), 0))
885 /* If all the functions in CF are the same, returns one of them,
886 otherwise returns NULL. */
889 common_affine_function (conflict_function
*cf
)
894 if (!CF_NONTRIVIAL_P (cf
))
899 for (i
= 1; i
< cf
->n
; i
++)
900 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
906 /* Returns the base of the affine function FN. */
909 affine_function_base (affine_fn fn
)
911 return VEC_index (tree
, fn
, 0);
914 /* Returns true if FN is a constant. */
917 affine_function_constant_p (affine_fn fn
)
922 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
923 if (!integer_zerop (coef
))
929 /* Returns true if FN is the zero constant function. */
932 affine_function_zero_p (affine_fn fn
)
934 return (integer_zerop (affine_function_base (fn
))
935 && affine_function_constant_p (fn
));
938 /* Returns a signed integer type with the largest precision from TA
942 signed_type_for_types (tree ta
, tree tb
)
944 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
945 return signed_type_for (ta
);
947 return signed_type_for (tb
);
950 /* Applies operation OP on affine functions FNA and FNB, and returns the
954 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
960 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
962 n
= VEC_length (tree
, fna
);
963 m
= VEC_length (tree
, fnb
);
967 n
= VEC_length (tree
, fnb
);
968 m
= VEC_length (tree
, fna
);
971 ret
= VEC_alloc (tree
, heap
, m
);
972 for (i
= 0; i
< n
; i
++)
974 tree type
= signed_type_for_types (TREE_TYPE (VEC_index (tree
, fna
, i
)),
975 TREE_TYPE (VEC_index (tree
, fnb
, i
)));
977 VEC_quick_push (tree
, ret
,
978 fold_build2 (op
, type
,
979 VEC_index (tree
, fna
, i
),
980 VEC_index (tree
, fnb
, i
)));
983 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
984 VEC_quick_push (tree
, ret
,
985 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
986 coef
, integer_zero_node
));
987 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
988 VEC_quick_push (tree
, ret
,
989 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
990 integer_zero_node
, coef
));
995 /* Returns the sum of affine functions FNA and FNB. */
998 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1000 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1003 /* Returns the difference of affine functions FNA and FNB. */
1006 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1008 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1011 /* Frees affine function FN. */
1014 affine_fn_free (affine_fn fn
)
1016 VEC_free (tree
, heap
, fn
);
1019 /* Determine for each subscript in the data dependence relation DDR
1023 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1025 conflict_function
*cf_a
, *cf_b
;
1026 affine_fn fn_a
, fn_b
, diff
;
1028 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1032 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1034 struct subscript
*subscript
;
1036 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1037 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1038 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1040 fn_a
= common_affine_function (cf_a
);
1041 fn_b
= common_affine_function (cf_b
);
1044 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1047 diff
= affine_fn_minus (fn_a
, fn_b
);
1049 if (affine_function_constant_p (diff
))
1050 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1052 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1054 affine_fn_free (diff
);
1059 /* Returns the conflict function for "unknown". */
1061 static conflict_function
*
1062 conflict_fn_not_known (void)
1064 conflict_function
*fn
= XCNEW (conflict_function
);
1070 /* Returns the conflict function for "independent". */
1072 static conflict_function
*
1073 conflict_fn_no_dependence (void)
1075 conflict_function
*fn
= XCNEW (conflict_function
);
1076 fn
->n
= NO_DEPENDENCE
;
1081 /* Returns true if the address of OBJ is invariant in LOOP. */
1084 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1086 while (handled_component_p (obj
))
1088 if (TREE_CODE (obj
) == ARRAY_REF
)
1090 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1091 need to check the stride and the lower bound of the reference. */
1092 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1094 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1098 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1100 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1104 obj
= TREE_OPERAND (obj
, 0);
1107 if (!INDIRECT_REF_P (obj
))
1110 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1114 /* Returns true if A and B are accesses to different objects, or to different
1115 fields of the same object. */
1118 disjoint_objects_p (tree a
, tree b
)
1120 tree base_a
, base_b
;
1121 VEC (tree
, heap
) *comp_a
= NULL
, *comp_b
= NULL
;
1124 base_a
= get_base_address (a
);
1125 base_b
= get_base_address (b
);
1129 && base_a
!= base_b
)
1132 if (!operand_equal_p (base_a
, base_b
, 0))
1135 /* Compare the component references of A and B. We must start from the inner
1136 ones, so record them to the vector first. */
1137 while (handled_component_p (a
))
1139 VEC_safe_push (tree
, heap
, comp_a
, a
);
1140 a
= TREE_OPERAND (a
, 0);
1142 while (handled_component_p (b
))
1144 VEC_safe_push (tree
, heap
, comp_b
, b
);
1145 b
= TREE_OPERAND (b
, 0);
1151 if (VEC_length (tree
, comp_a
) == 0
1152 || VEC_length (tree
, comp_b
) == 0)
1155 a
= VEC_pop (tree
, comp_a
);
1156 b
= VEC_pop (tree
, comp_b
);
1158 /* Real and imaginary part of a variable do not alias. */
1159 if ((TREE_CODE (a
) == REALPART_EXPR
1160 && TREE_CODE (b
) == IMAGPART_EXPR
)
1161 || (TREE_CODE (a
) == IMAGPART_EXPR
1162 && TREE_CODE (b
) == REALPART_EXPR
))
1168 if (TREE_CODE (a
) != TREE_CODE (b
))
1171 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1172 DR_BASE_OBJECT are always zero. */
1173 if (TREE_CODE (a
) == ARRAY_REF
)
1175 else if (TREE_CODE (a
) == COMPONENT_REF
)
1177 if (operand_equal_p (TREE_OPERAND (a
, 1), TREE_OPERAND (b
, 1), 0))
1180 /* Different fields of unions may overlap. */
1181 base_a
= TREE_OPERAND (a
, 0);
1182 if (TREE_CODE (TREE_TYPE (base_a
)) == UNION_TYPE
)
1185 /* Different fields of structures cannot. */
1193 VEC_free (tree
, heap
, comp_a
);
1194 VEC_free (tree
, heap
, comp_b
);
1199 /* Returns false if we can prove that data references A and B do not alias,
1203 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
)
1205 const_tree addr_a
= DR_BASE_ADDRESS (a
);
1206 const_tree addr_b
= DR_BASE_ADDRESS (b
);
1207 const_tree type_a
, type_b
;
1208 const_tree decl_a
= NULL_TREE
, decl_b
= NULL_TREE
;
1210 /* If the sets of virtual operands are disjoint, the memory references do not
1212 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
1215 /* If the accessed objects are disjoint, the memory references do not
1217 if (disjoint_objects_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
)))
1220 if (!addr_a
|| !addr_b
)
1223 /* If the references are based on different static objects, they cannot alias
1224 (PTA should be able to disambiguate such accesses, but often it fails to,
1225 since currently we cannot distinguish between pointer and offset in pointer
1227 if (TREE_CODE (addr_a
) == ADDR_EXPR
1228 && TREE_CODE (addr_b
) == ADDR_EXPR
)
1229 return TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0);
1231 /* An instruction writing through a restricted pointer is "independent" of any
1232 instruction reading or writing through a different restricted pointer,
1233 in the same block/scope. */
1235 type_a
= TREE_TYPE (addr_a
);
1236 type_b
= TREE_TYPE (addr_b
);
1237 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
1239 if (TREE_CODE (addr_a
) == SSA_NAME
)
1240 decl_a
= SSA_NAME_VAR (addr_a
);
1241 if (TREE_CODE (addr_b
) == SSA_NAME
)
1242 decl_b
= SSA_NAME_VAR (addr_b
);
1244 if (TYPE_RESTRICT (type_a
) && TYPE_RESTRICT (type_b
)
1245 && (!DR_IS_READ (a
) || !DR_IS_READ (b
))
1246 && decl_a
&& DECL_P (decl_a
)
1247 && decl_b
&& DECL_P (decl_b
)
1249 && TREE_CODE (DECL_CONTEXT (decl_a
)) == FUNCTION_DECL
1250 && DECL_CONTEXT (decl_a
) == DECL_CONTEXT (decl_b
))
1256 /* Initialize a data dependence relation between data accesses A and
1257 B. NB_LOOPS is the number of loops surrounding the references: the
1258 size of the classic distance/direction vectors. */
1260 static struct data_dependence_relation
*
1261 initialize_data_dependence_relation (struct data_reference
*a
,
1262 struct data_reference
*b
,
1263 VEC (loop_p
, heap
) *loop_nest
)
1265 struct data_dependence_relation
*res
;
1268 res
= XNEW (struct data_dependence_relation
);
1271 DDR_LOOP_NEST (res
) = NULL
;
1272 DDR_REVERSED_P (res
) = false;
1273 DDR_SUBSCRIPTS (res
) = NULL
;
1274 DDR_DIR_VECTS (res
) = NULL
;
1275 DDR_DIST_VECTS (res
) = NULL
;
1277 if (a
== NULL
|| b
== NULL
)
1279 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1283 /* If the data references do not alias, then they are independent. */
1284 if (!dr_may_alias_p (a
, b
))
1286 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1290 /* If the references do not access the same object, we do not know
1291 whether they alias or not. */
1292 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1294 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1298 /* If the base of the object is not invariant in the loop nest, we cannot
1299 analyze it. TODO -- in fact, it would suffice to record that there may
1300 be arbitrary dependences in the loops where the base object varies. */
1301 if (!object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1302 DR_BASE_OBJECT (a
)))
1304 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1308 gcc_assert (DR_NUM_DIMENSIONS (a
) == DR_NUM_DIMENSIONS (b
));
1310 DDR_AFFINE_P (res
) = true;
1311 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1312 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1313 DDR_LOOP_NEST (res
) = loop_nest
;
1314 DDR_INNER_LOOP (res
) = 0;
1316 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1318 struct subscript
*subscript
;
1320 subscript
= XNEW (struct subscript
);
1321 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1322 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1323 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1324 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1325 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1331 /* Frees memory used by the conflict function F. */
1334 free_conflict_function (conflict_function
*f
)
1338 if (CF_NONTRIVIAL_P (f
))
1340 for (i
= 0; i
< f
->n
; i
++)
1341 affine_fn_free (f
->fns
[i
]);
1346 /* Frees memory used by SUBSCRIPTS. */
1349 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1354 for (i
= 0; VEC_iterate (subscript_p
, subscripts
, i
, s
); i
++)
1356 free_conflict_function (s
->conflicting_iterations_in_a
);
1357 free_conflict_function (s
->conflicting_iterations_in_b
);
1359 VEC_free (subscript_p
, heap
, subscripts
);
1362 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1366 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1371 fprintf (dump_file
, "(dependence classified: ");
1372 print_generic_expr (dump_file
, chrec
, 0);
1373 fprintf (dump_file
, ")\n");
1376 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1377 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1378 DDR_SUBSCRIPTS (ddr
) = NULL
;
1381 /* The dependence relation DDR cannot be represented by a distance
1385 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1387 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1388 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1390 DDR_AFFINE_P (ddr
) = false;
1395 /* This section contains the classic Banerjee tests. */
1397 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1398 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1401 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1403 return (evolution_function_is_constant_p (chrec_a
)
1404 && evolution_function_is_constant_p (chrec_b
));
1407 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1408 variable, i.e., if the SIV (Single Index Variable) test is true. */
1411 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1413 if ((evolution_function_is_constant_p (chrec_a
)
1414 && evolution_function_is_univariate_p (chrec_b
))
1415 || (evolution_function_is_constant_p (chrec_b
)
1416 && evolution_function_is_univariate_p (chrec_a
)))
1419 if (evolution_function_is_univariate_p (chrec_a
)
1420 && evolution_function_is_univariate_p (chrec_b
))
1422 switch (TREE_CODE (chrec_a
))
1424 case POLYNOMIAL_CHREC
:
1425 switch (TREE_CODE (chrec_b
))
1427 case POLYNOMIAL_CHREC
:
1428 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1443 /* Creates a conflict function with N dimensions. The affine functions
1444 in each dimension follow. */
1446 static conflict_function
*
1447 conflict_fn (unsigned n
, ...)
1450 conflict_function
*ret
= XCNEW (conflict_function
);
1453 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1457 for (i
= 0; i
< n
; i
++)
1458 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1464 /* Returns constant affine function with value CST. */
1467 affine_fn_cst (tree cst
)
1469 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1470 VEC_quick_push (tree
, fn
, cst
);
1474 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1477 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1479 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1482 gcc_assert (dim
> 0);
1483 VEC_quick_push (tree
, fn
, cst
);
1484 for (i
= 1; i
< dim
; i
++)
1485 VEC_quick_push (tree
, fn
, integer_zero_node
);
1486 VEC_quick_push (tree
, fn
, coef
);
1490 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1491 *OVERLAPS_B are initialized to the functions that describe the
1492 relation between the elements accessed twice by CHREC_A and
1493 CHREC_B. For k >= 0, the following property is verified:
1495 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1498 analyze_ziv_subscript (tree chrec_a
,
1500 conflict_function
**overlaps_a
,
1501 conflict_function
**overlaps_b
,
1502 tree
*last_conflicts
)
1504 tree type
, difference
;
1505 dependence_stats
.num_ziv
++;
1507 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1508 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1510 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1511 chrec_a
= chrec_convert (type
, chrec_a
, NULL_TREE
);
1512 chrec_b
= chrec_convert (type
, chrec_b
, NULL_TREE
);
1513 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1515 switch (TREE_CODE (difference
))
1518 if (integer_zerop (difference
))
1520 /* The difference is equal to zero: the accessed index
1521 overlaps for each iteration in the loop. */
1522 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1523 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1524 *last_conflicts
= chrec_dont_know
;
1525 dependence_stats
.num_ziv_dependent
++;
1529 /* The accesses do not overlap. */
1530 *overlaps_a
= conflict_fn_no_dependence ();
1531 *overlaps_b
= conflict_fn_no_dependence ();
1532 *last_conflicts
= integer_zero_node
;
1533 dependence_stats
.num_ziv_independent
++;
1538 /* We're not sure whether the indexes overlap. For the moment,
1539 conservatively answer "don't know". */
1540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1541 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1543 *overlaps_a
= conflict_fn_not_known ();
1544 *overlaps_b
= conflict_fn_not_known ();
1545 *last_conflicts
= chrec_dont_know
;
1546 dependence_stats
.num_ziv_unimplemented
++;
1550 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1551 fprintf (dump_file
, ")\n");
1554 /* Sets NIT to the estimated number of executions of the statements in
1555 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1556 large as the number of iterations. If we have no reliable estimate,
1557 the function returns false, otherwise returns true. */
1560 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
1563 estimate_numbers_of_iterations_loop (loop
);
1566 if (!loop
->any_upper_bound
)
1569 *nit
= loop
->nb_iterations_upper_bound
;
1573 if (!loop
->any_estimate
)
1576 *nit
= loop
->nb_iterations_estimate
;
1582 /* Similar to estimated_loop_iterations, but returns the estimate only
1583 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1584 on the number of iterations of LOOP could not be derived, returns -1. */
1587 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
1590 HOST_WIDE_INT hwi_nit
;
1592 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1595 if (!double_int_fits_in_shwi_p (nit
))
1597 hwi_nit
= double_int_to_shwi (nit
);
1599 return hwi_nit
< 0 ? -1 : hwi_nit
;
1602 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1603 and only if it fits to the int type. If this is not the case, or the
1604 estimate on the number of iterations of LOOP could not be derived, returns
1608 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
1613 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1614 return chrec_dont_know
;
1616 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
1617 if (!double_int_fits_to_tree_p (type
, nit
))
1618 return chrec_dont_know
;
1620 return double_int_to_tree (type
, nit
);
1623 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1624 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1625 *OVERLAPS_B are initialized to the functions that describe the
1626 relation between the elements accessed twice by CHREC_A and
1627 CHREC_B. For k >= 0, the following property is verified:
1629 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1632 analyze_siv_subscript_cst_affine (tree chrec_a
,
1634 conflict_function
**overlaps_a
,
1635 conflict_function
**overlaps_b
,
1636 tree
*last_conflicts
)
1638 bool value0
, value1
, value2
;
1639 tree type
, difference
, tmp
;
1641 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1642 chrec_a
= chrec_convert (type
, chrec_a
, NULL_TREE
);
1643 chrec_b
= chrec_convert (type
, chrec_b
, NULL_TREE
);
1644 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1646 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1648 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1649 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1651 dependence_stats
.num_siv_unimplemented
++;
1652 *overlaps_a
= conflict_fn_not_known ();
1653 *overlaps_b
= conflict_fn_not_known ();
1654 *last_conflicts
= chrec_dont_know
;
1659 if (value0
== false)
1661 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1664 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1666 *overlaps_a
= conflict_fn_not_known ();
1667 *overlaps_b
= conflict_fn_not_known ();
1668 *last_conflicts
= chrec_dont_know
;
1669 dependence_stats
.num_siv_unimplemented
++;
1678 chrec_b = {10, +, 1}
1681 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1683 HOST_WIDE_INT numiter
;
1684 struct loop
*loop
= get_chrec_loop (chrec_b
);
1686 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1687 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1688 fold_build1 (ABS_EXPR
, type
, difference
),
1689 CHREC_RIGHT (chrec_b
));
1690 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1691 *last_conflicts
= integer_one_node
;
1694 /* Perform weak-zero siv test to see if overlap is
1695 outside the loop bounds. */
1696 numiter
= estimated_loop_iterations_int (loop
, false);
1699 && compare_tree_int (tmp
, numiter
) > 0)
1701 free_conflict_function (*overlaps_a
);
1702 free_conflict_function (*overlaps_b
);
1703 *overlaps_a
= conflict_fn_no_dependence ();
1704 *overlaps_b
= conflict_fn_no_dependence ();
1705 *last_conflicts
= integer_zero_node
;
1706 dependence_stats
.num_siv_independent
++;
1709 dependence_stats
.num_siv_dependent
++;
1713 /* When the step does not divide the difference, there are
1717 *overlaps_a
= conflict_fn_no_dependence ();
1718 *overlaps_b
= conflict_fn_no_dependence ();
1719 *last_conflicts
= integer_zero_node
;
1720 dependence_stats
.num_siv_independent
++;
1729 chrec_b = {10, +, -1}
1731 In this case, chrec_a will not overlap with chrec_b. */
1732 *overlaps_a
= conflict_fn_no_dependence ();
1733 *overlaps_b
= conflict_fn_no_dependence ();
1734 *last_conflicts
= integer_zero_node
;
1735 dependence_stats
.num_siv_independent
++;
1742 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1745 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1747 *overlaps_a
= conflict_fn_not_known ();
1748 *overlaps_b
= conflict_fn_not_known ();
1749 *last_conflicts
= chrec_dont_know
;
1750 dependence_stats
.num_siv_unimplemented
++;
1755 if (value2
== false)
1759 chrec_b = {10, +, -1}
1761 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1763 HOST_WIDE_INT numiter
;
1764 struct loop
*loop
= get_chrec_loop (chrec_b
);
1766 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1767 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1768 CHREC_RIGHT (chrec_b
));
1769 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1770 *last_conflicts
= integer_one_node
;
1772 /* Perform weak-zero siv test to see if overlap is
1773 outside the loop bounds. */
1774 numiter
= estimated_loop_iterations_int (loop
, false);
1777 && compare_tree_int (tmp
, numiter
) > 0)
1779 free_conflict_function (*overlaps_a
);
1780 free_conflict_function (*overlaps_b
);
1781 *overlaps_a
= conflict_fn_no_dependence ();
1782 *overlaps_b
= conflict_fn_no_dependence ();
1783 *last_conflicts
= integer_zero_node
;
1784 dependence_stats
.num_siv_independent
++;
1787 dependence_stats
.num_siv_dependent
++;
1791 /* When the step does not divide the difference, there
1795 *overlaps_a
= conflict_fn_no_dependence ();
1796 *overlaps_b
= conflict_fn_no_dependence ();
1797 *last_conflicts
= integer_zero_node
;
1798 dependence_stats
.num_siv_independent
++;
1808 In this case, chrec_a will not overlap with chrec_b. */
1809 *overlaps_a
= conflict_fn_no_dependence ();
1810 *overlaps_b
= conflict_fn_no_dependence ();
1811 *last_conflicts
= integer_zero_node
;
1812 dependence_stats
.num_siv_independent
++;
1820 /* Helper recursive function for initializing the matrix A. Returns
1821 the initial value of CHREC. */
1823 static HOST_WIDE_INT
1824 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1830 type
= TREE_TYPE (chrec
);
1831 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1832 return tree_low_cst (chrec
, TYPE_UNSIGNED (type
)
1833 && !(TREE_CODE (type
) == INTEGER_TYPE
1834 && TYPE_IS_SIZETYPE (type
)));
1836 type
= TREE_TYPE (CHREC_RIGHT (chrec
));
1837 A
[index
][0] = mult
* tree_low_cst (CHREC_RIGHT (chrec
),
1838 TYPE_UNSIGNED (type
)
1839 && !(TREE_CODE (type
) == INTEGER_TYPE
1840 && TYPE_IS_SIZETYPE (type
)));
1841 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1844 #define FLOOR_DIV(x,y) ((x) / (y))
1846 /* Solves the special case of the Diophantine equation:
1847 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1849 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1850 number of iterations that loops X and Y run. The overlaps will be
1851 constructed as evolutions in dimension DIM. */
1854 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1855 affine_fn
*overlaps_a
,
1856 affine_fn
*overlaps_b
,
1857 tree
*last_conflicts
, int dim
)
1859 if (((step_a
> 0 && step_b
> 0)
1860 || (step_a
< 0 && step_b
< 0)))
1862 int step_overlaps_a
, step_overlaps_b
;
1863 int gcd_steps_a_b
, last_conflict
, tau2
;
1865 gcd_steps_a_b
= gcd (step_a
, step_b
);
1866 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1867 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1871 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1872 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1873 last_conflict
= tau2
;
1874 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1877 *last_conflicts
= chrec_dont_know
;
1879 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
1880 build_int_cst (NULL_TREE
,
1882 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
1883 build_int_cst (NULL_TREE
,
1889 *overlaps_a
= affine_fn_cst (integer_zero_node
);
1890 *overlaps_b
= affine_fn_cst (integer_zero_node
);
1891 *last_conflicts
= integer_zero_node
;
1895 /* Solves the special case of a Diophantine equation where CHREC_A is
1896 an affine bivariate function, and CHREC_B is an affine univariate
1897 function. For example,
1899 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1901 has the following overlapping functions:
1903 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1904 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1905 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1907 FORNOW: This is a specialized implementation for a case occurring in
1908 a common benchmark. Implement the general algorithm. */
1911 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1912 conflict_function
**overlaps_a
,
1913 conflict_function
**overlaps_b
,
1914 tree
*last_conflicts
)
1916 bool xz_p
, yz_p
, xyz_p
;
1917 int step_x
, step_y
, step_z
;
1918 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
1919 affine_fn overlaps_a_xz
, overlaps_b_xz
;
1920 affine_fn overlaps_a_yz
, overlaps_b_yz
;
1921 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
1922 affine_fn ova1
, ova2
, ovb
;
1923 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
1925 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
1926 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
1927 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
1930 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a
)),
1932 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), false);
1933 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), false);
1935 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
1937 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1938 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
1940 *overlaps_a
= conflict_fn_not_known ();
1941 *overlaps_b
= conflict_fn_not_known ();
1942 *last_conflicts
= chrec_dont_know
;
1946 niter
= MIN (niter_x
, niter_z
);
1947 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
1950 &last_conflicts_xz
, 1);
1951 niter
= MIN (niter_y
, niter_z
);
1952 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
1955 &last_conflicts_yz
, 2);
1956 niter
= MIN (niter_x
, niter_z
);
1957 niter
= MIN (niter_y
, niter
);
1958 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
1961 &last_conflicts_xyz
, 3);
1963 xz_p
= !integer_zerop (last_conflicts_xz
);
1964 yz_p
= !integer_zerop (last_conflicts_yz
);
1965 xyz_p
= !integer_zerop (last_conflicts_xyz
);
1967 if (xz_p
|| yz_p
|| xyz_p
)
1969 ova1
= affine_fn_cst (integer_zero_node
);
1970 ova2
= affine_fn_cst (integer_zero_node
);
1971 ovb
= affine_fn_cst (integer_zero_node
);
1974 affine_fn t0
= ova1
;
1977 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
1978 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
1979 affine_fn_free (t0
);
1980 affine_fn_free (t2
);
1981 *last_conflicts
= last_conflicts_xz
;
1985 affine_fn t0
= ova2
;
1988 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
1989 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
1990 affine_fn_free (t0
);
1991 affine_fn_free (t2
);
1992 *last_conflicts
= last_conflicts_yz
;
1996 affine_fn t0
= ova1
;
1997 affine_fn t2
= ova2
;
2000 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2001 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2002 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2003 affine_fn_free (t0
);
2004 affine_fn_free (t2
);
2005 affine_fn_free (t4
);
2006 *last_conflicts
= last_conflicts_xyz
;
2008 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2009 *overlaps_b
= conflict_fn (1, ovb
);
2013 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2014 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2015 *last_conflicts
= integer_zero_node
;
2018 affine_fn_free (overlaps_a_xz
);
2019 affine_fn_free (overlaps_b_xz
);
2020 affine_fn_free (overlaps_a_yz
);
2021 affine_fn_free (overlaps_b_yz
);
2022 affine_fn_free (overlaps_a_xyz
);
2023 affine_fn_free (overlaps_b_xyz
);
2026 /* Determines the overlapping elements due to accesses CHREC_A and
2027 CHREC_B, that are affine functions. This function cannot handle
2028 symbolic evolution functions, ie. when initial conditions are
2029 parameters, because it uses lambda matrices of integers. */
2032 analyze_subscript_affine_affine (tree chrec_a
,
2034 conflict_function
**overlaps_a
,
2035 conflict_function
**overlaps_b
,
2036 tree
*last_conflicts
)
2038 unsigned nb_vars_a
, nb_vars_b
, dim
;
2039 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2040 lambda_matrix A
, U
, S
;
2042 if (eq_evolutions_p (chrec_a
, chrec_b
))
2044 /* The accessed index overlaps for each iteration in the
2046 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2047 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2048 *last_conflicts
= chrec_dont_know
;
2051 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2052 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2054 /* For determining the initial intersection, we have to solve a
2055 Diophantine equation. This is the most time consuming part.
2057 For answering to the question: "Is there a dependence?" we have
2058 to prove that there exists a solution to the Diophantine
2059 equation, and that the solution is in the iteration domain,
2060 i.e. the solution is positive or zero, and that the solution
2061 happens before the upper bound loop.nb_iterations. Otherwise
2062 there is no dependence. This function outputs a description of
2063 the iterations that hold the intersections. */
2065 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2066 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2068 dim
= nb_vars_a
+ nb_vars_b
;
2069 U
= lambda_matrix_new (dim
, dim
);
2070 A
= lambda_matrix_new (dim
, 1);
2071 S
= lambda_matrix_new (dim
, 1);
2073 init_a
= initialize_matrix_A (A
, chrec_a
, 0, 1);
2074 init_b
= initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1);
2075 gamma
= init_b
- init_a
;
2077 /* Don't do all the hard work of solving the Diophantine equation
2078 when we already know the solution: for example,
2081 | gamma = 3 - 3 = 0.
2082 Then the first overlap occurs during the first iterations:
2083 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2087 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2089 HOST_WIDE_INT step_a
, step_b
;
2090 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2093 niter_a
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
),
2095 niter_b
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
),
2097 niter
= MIN (niter_a
, niter_b
);
2098 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2099 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2101 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2104 *overlaps_a
= conflict_fn (1, ova
);
2105 *overlaps_b
= conflict_fn (1, ovb
);
2108 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2109 compute_overlap_steps_for_affine_1_2
2110 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2112 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2113 compute_overlap_steps_for_affine_1_2
2114 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2119 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2120 *overlaps_a
= conflict_fn_not_known ();
2121 *overlaps_b
= conflict_fn_not_known ();
2122 *last_conflicts
= chrec_dont_know
;
2124 goto end_analyze_subs_aa
;
2128 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2133 lambda_matrix_row_negate (U
, dim
, 0);
2135 gcd_alpha_beta
= S
[0][0];
2137 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2138 but that is a quite strange case. Instead of ICEing, answer
2140 if (gcd_alpha_beta
== 0)
2142 *overlaps_a
= conflict_fn_not_known ();
2143 *overlaps_b
= conflict_fn_not_known ();
2144 *last_conflicts
= chrec_dont_know
;
2145 goto end_analyze_subs_aa
;
2148 /* The classic "gcd-test". */
2149 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2151 /* The "gcd-test" has determined that there is no integer
2152 solution, i.e. there is no dependence. */
2153 *overlaps_a
= conflict_fn_no_dependence ();
2154 *overlaps_b
= conflict_fn_no_dependence ();
2155 *last_conflicts
= integer_zero_node
;
2158 /* Both access functions are univariate. This includes SIV and MIV cases. */
2159 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2161 /* Both functions should have the same evolution sign. */
2162 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2163 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2165 /* The solutions are given by:
2167 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2170 For a given integer t. Using the following variables,
2172 | i0 = u11 * gamma / gcd_alpha_beta
2173 | j0 = u12 * gamma / gcd_alpha_beta
2180 | y0 = j0 + j1 * t. */
2181 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2183 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2184 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2188 if ((i1
== 0 && i0
< 0)
2189 || (j1
== 0 && j0
< 0))
2191 /* There is no solution.
2192 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2193 falls in here, but for the moment we don't look at the
2194 upper bound of the iteration domain. */
2195 *overlaps_a
= conflict_fn_no_dependence ();
2196 *overlaps_b
= conflict_fn_no_dependence ();
2197 *last_conflicts
= integer_zero_node
;
2198 goto end_analyze_subs_aa
;
2201 if (i1
> 0 && j1
> 0)
2203 HOST_WIDE_INT niter_a
= estimated_loop_iterations_int
2204 (get_chrec_loop (chrec_a
), false);
2205 HOST_WIDE_INT niter_b
= estimated_loop_iterations_int
2206 (get_chrec_loop (chrec_b
), false);
2207 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2209 /* (X0, Y0) is a solution of the Diophantine equation:
2210 "chrec_a (X0) = chrec_b (Y0)". */
2211 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2213 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2214 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2216 /* (X1, Y1) is the smallest positive solution of the eq
2217 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2218 first conflict occurs. */
2219 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2220 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2221 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2225 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2226 FLOOR_DIV (niter
- j0
, j1
));
2227 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2229 /* If the overlap occurs outside of the bounds of the
2230 loop, there is no dependence. */
2231 if (x1
> niter
|| y1
> niter
)
2233 *overlaps_a
= conflict_fn_no_dependence ();
2234 *overlaps_b
= conflict_fn_no_dependence ();
2235 *last_conflicts
= integer_zero_node
;
2236 goto end_analyze_subs_aa
;
2239 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2242 *last_conflicts
= chrec_dont_know
;
2246 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2248 build_int_cst (NULL_TREE
, i1
)));
2251 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2253 build_int_cst (NULL_TREE
, j1
)));
2257 /* FIXME: For the moment, the upper bound of the
2258 iteration domain for i and j is not checked. */
2259 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2260 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2261 *overlaps_a
= conflict_fn_not_known ();
2262 *overlaps_b
= conflict_fn_not_known ();
2263 *last_conflicts
= chrec_dont_know
;
2268 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2269 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2270 *overlaps_a
= conflict_fn_not_known ();
2271 *overlaps_b
= conflict_fn_not_known ();
2272 *last_conflicts
= chrec_dont_know
;
2277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2278 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2279 *overlaps_a
= conflict_fn_not_known ();
2280 *overlaps_b
= conflict_fn_not_known ();
2281 *last_conflicts
= chrec_dont_know
;
2284 end_analyze_subs_aa
:
2285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2287 fprintf (dump_file
, " (overlaps_a = ");
2288 dump_conflict_function (dump_file
, *overlaps_a
);
2289 fprintf (dump_file
, ")\n (overlaps_b = ");
2290 dump_conflict_function (dump_file
, *overlaps_b
);
2291 fprintf (dump_file
, ")\n");
2292 fprintf (dump_file
, ")\n");
2296 /* Returns true when analyze_subscript_affine_affine can be used for
2297 determining the dependence relation between chrec_a and chrec_b,
2298 that contain symbols. This function modifies chrec_a and chrec_b
2299 such that the analysis result is the same, and such that they don't
2300 contain symbols, and then can safely be passed to the analyzer.
2302 Example: The analysis of the following tuples of evolutions produce
2303 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2306 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2307 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2311 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2313 tree diff
, type
, left_a
, left_b
, right_b
;
2315 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2316 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2317 /* FIXME: For the moment not handled. Might be refined later. */
2320 type
= chrec_type (*chrec_a
);
2321 left_a
= CHREC_LEFT (*chrec_a
);
2322 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL_TREE
);
2323 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2325 if (!evolution_function_is_constant_p (diff
))
2328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2329 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2331 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2332 diff
, CHREC_RIGHT (*chrec_a
));
2333 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL_TREE
);
2334 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2335 build_int_cst (type
, 0),
2340 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2341 *OVERLAPS_B are initialized to the functions that describe the
2342 relation between the elements accessed twice by CHREC_A and
2343 CHREC_B. For k >= 0, the following property is verified:
2345 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2348 analyze_siv_subscript (tree chrec_a
,
2350 conflict_function
**overlaps_a
,
2351 conflict_function
**overlaps_b
,
2352 tree
*last_conflicts
)
2354 dependence_stats
.num_siv
++;
2356 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2357 fprintf (dump_file
, "(analyze_siv_subscript \n");
2359 if (evolution_function_is_constant_p (chrec_a
)
2360 && evolution_function_is_affine_p (chrec_b
))
2361 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2362 overlaps_a
, overlaps_b
, last_conflicts
);
2364 else if (evolution_function_is_affine_p (chrec_a
)
2365 && evolution_function_is_constant_p (chrec_b
))
2366 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2367 overlaps_b
, overlaps_a
, last_conflicts
);
2369 else if (evolution_function_is_affine_p (chrec_a
)
2370 && evolution_function_is_affine_p (chrec_b
))
2372 if (!chrec_contains_symbols (chrec_a
)
2373 && !chrec_contains_symbols (chrec_b
))
2375 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2376 overlaps_a
, overlaps_b
,
2379 if (CF_NOT_KNOWN_P (*overlaps_a
)
2380 || CF_NOT_KNOWN_P (*overlaps_b
))
2381 dependence_stats
.num_siv_unimplemented
++;
2382 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2383 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2384 dependence_stats
.num_siv_independent
++;
2386 dependence_stats
.num_siv_dependent
++;
2388 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2391 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2392 overlaps_a
, overlaps_b
,
2395 if (CF_NOT_KNOWN_P (*overlaps_a
)
2396 || CF_NOT_KNOWN_P (*overlaps_b
))
2397 dependence_stats
.num_siv_unimplemented
++;
2398 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2399 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2400 dependence_stats
.num_siv_independent
++;
2402 dependence_stats
.num_siv_dependent
++;
2405 goto siv_subscript_dontknow
;
2410 siv_subscript_dontknow
:;
2411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2412 fprintf (dump_file
, "siv test failed: unimplemented.\n");
2413 *overlaps_a
= conflict_fn_not_known ();
2414 *overlaps_b
= conflict_fn_not_known ();
2415 *last_conflicts
= chrec_dont_know
;
2416 dependence_stats
.num_siv_unimplemented
++;
2419 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2420 fprintf (dump_file
, ")\n");
2423 /* Returns false if we can prove that the greatest common divisor of the steps
2424 of CHREC does not divide CST, false otherwise. */
2427 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2429 HOST_WIDE_INT cd
= 0, val
;
2432 if (!host_integerp (cst
, 0))
2434 val
= tree_low_cst (cst
, 0);
2436 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2438 step
= CHREC_RIGHT (chrec
);
2439 if (!host_integerp (step
, 0))
2441 cd
= gcd (cd
, tree_low_cst (step
, 0));
2442 chrec
= CHREC_LEFT (chrec
);
2445 return val
% cd
== 0;
2448 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2449 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2450 functions that describe the relation between the elements accessed
2451 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2454 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2457 analyze_miv_subscript (tree chrec_a
,
2459 conflict_function
**overlaps_a
,
2460 conflict_function
**overlaps_b
,
2461 tree
*last_conflicts
,
2462 struct loop
*loop_nest
)
2464 /* FIXME: This is a MIV subscript, not yet handled.
2465 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2468 In the SIV test we had to solve a Diophantine equation with two
2469 variables. In the MIV case we have to solve a Diophantine
2470 equation with 2*n variables (if the subscript uses n IVs).
2472 tree type
, difference
;
2474 dependence_stats
.num_miv
++;
2475 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2476 fprintf (dump_file
, "(analyze_miv_subscript \n");
2478 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2479 chrec_a
= chrec_convert (type
, chrec_a
, NULL_TREE
);
2480 chrec_b
= chrec_convert (type
, chrec_b
, NULL_TREE
);
2481 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2483 if (eq_evolutions_p (chrec_a
, chrec_b
))
2485 /* Access functions are the same: all the elements are accessed
2486 in the same order. */
2487 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2488 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2489 *last_conflicts
= estimated_loop_iterations_tree
2490 (get_chrec_loop (chrec_a
), true);
2491 dependence_stats
.num_miv_dependent
++;
2494 else if (evolution_function_is_constant_p (difference
)
2495 /* For the moment, the following is verified:
2496 evolution_function_is_affine_multivariate_p (chrec_a,
2498 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2500 /* testsuite/.../ssa-chrec-33.c
2501 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2503 The difference is 1, and all the evolution steps are multiples
2504 of 2, consequently there are no overlapping elements. */
2505 *overlaps_a
= conflict_fn_no_dependence ();
2506 *overlaps_b
= conflict_fn_no_dependence ();
2507 *last_conflicts
= integer_zero_node
;
2508 dependence_stats
.num_miv_independent
++;
2511 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2512 && !chrec_contains_symbols (chrec_a
)
2513 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2514 && !chrec_contains_symbols (chrec_b
))
2516 /* testsuite/.../ssa-chrec-35.c
2517 {0, +, 1}_2 vs. {0, +, 1}_3
2518 the overlapping elements are respectively located at iterations:
2519 {0, +, 1}_x and {0, +, 1}_x,
2520 in other words, we have the equality:
2521 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2524 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2525 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2527 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2528 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2530 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2531 overlaps_a
, overlaps_b
, last_conflicts
);
2533 if (CF_NOT_KNOWN_P (*overlaps_a
)
2534 || CF_NOT_KNOWN_P (*overlaps_b
))
2535 dependence_stats
.num_miv_unimplemented
++;
2536 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2537 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2538 dependence_stats
.num_miv_independent
++;
2540 dependence_stats
.num_miv_dependent
++;
2545 /* When the analysis is too difficult, answer "don't know". */
2546 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2547 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2549 *overlaps_a
= conflict_fn_not_known ();
2550 *overlaps_b
= conflict_fn_not_known ();
2551 *last_conflicts
= chrec_dont_know
;
2552 dependence_stats
.num_miv_unimplemented
++;
2555 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2556 fprintf (dump_file
, ")\n");
2559 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2560 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2561 OVERLAP_ITERATIONS_B are initialized with two functions that
2562 describe the iterations that contain conflicting elements.
2564 Remark: For an integer k >= 0, the following equality is true:
2566 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2570 analyze_overlapping_iterations (tree chrec_a
,
2572 conflict_function
**overlap_iterations_a
,
2573 conflict_function
**overlap_iterations_b
,
2574 tree
*last_conflicts
, struct loop
*loop_nest
)
2576 unsigned int lnn
= loop_nest
->num
;
2578 dependence_stats
.num_subscript_tests
++;
2580 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2582 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2583 fprintf (dump_file
, " (chrec_a = ");
2584 print_generic_expr (dump_file
, chrec_a
, 0);
2585 fprintf (dump_file
, ")\n (chrec_b = ");
2586 print_generic_expr (dump_file
, chrec_b
, 0);
2587 fprintf (dump_file
, ")\n");
2590 if (chrec_a
== NULL_TREE
2591 || chrec_b
== NULL_TREE
2592 || chrec_contains_undetermined (chrec_a
)
2593 || chrec_contains_undetermined (chrec_b
))
2595 dependence_stats
.num_subscript_undetermined
++;
2597 *overlap_iterations_a
= conflict_fn_not_known ();
2598 *overlap_iterations_b
= conflict_fn_not_known ();
2601 /* If they are the same chrec, and are affine, they overlap
2602 on every iteration. */
2603 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2604 && evolution_function_is_affine_multivariate_p (chrec_a
, lnn
))
2606 dependence_stats
.num_same_subscript_function
++;
2607 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2608 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2609 *last_conflicts
= chrec_dont_know
;
2612 /* If they aren't the same, and aren't affine, we can't do anything
2614 else if ((chrec_contains_symbols (chrec_a
)
2615 || chrec_contains_symbols (chrec_b
))
2616 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2617 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2619 dependence_stats
.num_subscript_undetermined
++;
2620 *overlap_iterations_a
= conflict_fn_not_known ();
2621 *overlap_iterations_b
= conflict_fn_not_known ();
2624 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2625 analyze_ziv_subscript (chrec_a
, chrec_b
,
2626 overlap_iterations_a
, overlap_iterations_b
,
2629 else if (siv_subscript_p (chrec_a
, chrec_b
))
2630 analyze_siv_subscript (chrec_a
, chrec_b
,
2631 overlap_iterations_a
, overlap_iterations_b
,
2635 analyze_miv_subscript (chrec_a
, chrec_b
,
2636 overlap_iterations_a
, overlap_iterations_b
,
2637 last_conflicts
, loop_nest
);
2639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2641 fprintf (dump_file
, " (overlap_iterations_a = ");
2642 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2643 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2644 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2645 fprintf (dump_file
, ")\n");
2646 fprintf (dump_file
, ")\n");
2650 /* Helper function for uniquely inserting distance vectors. */
2653 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2658 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
2659 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2662 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2665 /* Helper function for uniquely inserting direction vectors. */
2668 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2673 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
2674 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2677 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2680 /* Add a distance of 1 on all the loops outer than INDEX. If we
2681 haven't yet determined a distance for this outer loop, push a new
2682 distance vector composed of the previous distance, and a distance
2683 of 1 for this outer loop. Example:
2691 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2692 save (0, 1), then we have to save (1, 0). */
2695 add_outer_distances (struct data_dependence_relation
*ddr
,
2696 lambda_vector dist_v
, int index
)
2698 /* For each outer loop where init_v is not set, the accesses are
2699 in dependence of distance 1 in the loop. */
2700 while (--index
>= 0)
2702 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2703 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2705 save_dist_v (ddr
, save_v
);
2709 /* Return false when fail to represent the data dependence as a
2710 distance vector. INIT_B is set to true when a component has been
2711 added to the distance vector DIST_V. INDEX_CARRY is then set to
2712 the index in DIST_V that carries the dependence. */
2715 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2716 struct data_reference
*ddr_a
,
2717 struct data_reference
*ddr_b
,
2718 lambda_vector dist_v
, bool *init_b
,
2722 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2724 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2726 tree access_fn_a
, access_fn_b
;
2727 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2729 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2731 non_affine_dependence_relation (ddr
);
2735 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2736 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2738 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2739 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2742 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2743 DDR_LOOP_NEST (ddr
));
2744 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2745 DDR_LOOP_NEST (ddr
));
2747 /* The dependence is carried by the outermost loop. Example:
2754 In this case, the dependence is carried by loop_1. */
2755 index
= index_a
< index_b
? index_a
: index_b
;
2756 *index_carry
= MIN (index
, *index_carry
);
2758 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2760 non_affine_dependence_relation (ddr
);
2764 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2766 /* This is the subscript coupling test. If we have already
2767 recorded a distance for this loop (a distance coming from
2768 another subscript), it should be the same. For example,
2769 in the following code, there is no dependence:
2776 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2778 finalize_ddr_dependent (ddr
, chrec_known
);
2782 dist_v
[index
] = dist
;
2786 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2788 /* This can be for example an affine vs. constant dependence
2789 (T[i] vs. T[3]) that is not an affine dependence and is
2790 not representable as a distance vector. */
2791 non_affine_dependence_relation (ddr
);
2799 /* Return true when the DDR contains two data references that have the
2800 same access functions. */
2803 same_access_functions (const struct data_dependence_relation
*ddr
)
2807 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2808 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr
), i
),
2809 DR_ACCESS_FN (DDR_B (ddr
), i
)))
2815 /* Return true when the DDR contains only constant access functions. */
2818 constant_access_functions (const struct data_dependence_relation
*ddr
)
2822 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2823 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2824 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2830 /* Helper function for the case where DDR_A and DDR_B are the same
2831 multivariate access function with a constant step. For an example
2835 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2838 tree c_1
= CHREC_LEFT (c_2
);
2839 tree c_0
= CHREC_LEFT (c_1
);
2840 lambda_vector dist_v
;
2843 /* Polynomials with more than 2 variables are not handled yet. When
2844 the evolution steps are parameters, it is not possible to
2845 represent the dependence using classical distance vectors. */
2846 if (TREE_CODE (c_0
) != INTEGER_CST
2847 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
2848 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
2850 DDR_AFFINE_P (ddr
) = false;
2854 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2855 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2857 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2858 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2859 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2860 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2873 save_dist_v (ddr
, dist_v
);
2875 add_outer_distances (ddr
, dist_v
, x_1
);
2878 /* Helper function for the case where DDR_A and DDR_B are the same
2879 access functions. */
2882 add_other_self_distances (struct data_dependence_relation
*ddr
)
2884 lambda_vector dist_v
;
2886 int index_carry
= DDR_NB_LOOPS (ddr
);
2888 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2890 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
2892 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
2894 if (!evolution_function_is_univariate_p (access_fun
))
2896 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
2898 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2902 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
2904 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
2905 add_multivariate_self_dist (ddr
, access_fun
);
2907 /* The evolution step is not constant: it varies in
2908 the outer loop, so this cannot be represented by a
2909 distance vector. For example in pr34635.c the
2910 evolution is {0, +, {0, +, 4}_1}_2. */
2911 DDR_AFFINE_P (ddr
) = false;
2916 index_carry
= MIN (index_carry
,
2917 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
2918 DDR_LOOP_NEST (ddr
)));
2922 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2923 add_outer_distances (ddr
, dist_v
, index_carry
);
2927 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
2929 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2931 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
2932 save_dist_v (ddr
, dist_v
);
2935 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2936 is the case for example when access functions are the same and
2937 equal to a constant, as in:
2944 in which case the distance vectors are (0) and (1). */
2947 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
2951 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2953 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
2954 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
2955 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
2957 for (j
= 0; j
< ca
->n
; j
++)
2958 if (affine_function_zero_p (ca
->fns
[j
]))
2960 insert_innermost_unit_dist_vector (ddr
);
2964 for (j
= 0; j
< cb
->n
; j
++)
2965 if (affine_function_zero_p (cb
->fns
[j
]))
2967 insert_innermost_unit_dist_vector (ddr
);
2973 /* Compute the classic per loop distance vector. DDR is the data
2974 dependence relation to build a vector from. Return false when fail
2975 to represent the data dependence as a distance vector. */
2978 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
2979 struct loop
*loop_nest
)
2981 bool init_b
= false;
2982 int index_carry
= DDR_NB_LOOPS (ddr
);
2983 lambda_vector dist_v
;
2985 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
2988 if (same_access_functions (ddr
))
2990 /* Save the 0 vector. */
2991 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2992 save_dist_v (ddr
, dist_v
);
2994 if (constant_access_functions (ddr
))
2995 add_distance_for_zero_overlaps (ddr
);
2997 if (DDR_NB_LOOPS (ddr
) > 1)
2998 add_other_self_distances (ddr
);
3003 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3004 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3005 dist_v
, &init_b
, &index_carry
))
3008 /* Save the distance vector if we initialized one. */
3011 /* Verify a basic constraint: classic distance vectors should
3012 always be lexicographically positive.
3014 Data references are collected in the order of execution of
3015 the program, thus for the following loop
3017 | for (i = 1; i < 100; i++)
3018 | for (j = 1; j < 100; j++)
3020 | t = T[j+1][i-1]; // A
3021 | T[j][i] = t + 2; // B
3024 references are collected following the direction of the wind:
3025 A then B. The data dependence tests are performed also
3026 following this order, such that we're looking at the distance
3027 separating the elements accessed by A from the elements later
3028 accessed by B. But in this example, the distance returned by
3029 test_dep (A, B) is lexicographically negative (-1, 1), that
3030 means that the access A occurs later than B with respect to
3031 the outer loop, ie. we're actually looking upwind. In this
3032 case we solve test_dep (B, A) looking downwind to the
3033 lexicographically positive solution, that returns the
3034 distance vector (1, -1). */
3035 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3037 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3038 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3041 compute_subscript_distance (ddr
);
3042 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3043 save_v
, &init_b
, &index_carry
))
3045 save_dist_v (ddr
, save_v
);
3046 DDR_REVERSED_P (ddr
) = true;
3048 /* In this case there is a dependence forward for all the
3051 | for (k = 1; k < 100; k++)
3052 | for (i = 1; i < 100; i++)
3053 | for (j = 1; j < 100; j++)
3055 | t = T[j+1][i-1]; // A
3056 | T[j][i] = t + 2; // B
3064 if (DDR_NB_LOOPS (ddr
) > 1)
3066 add_outer_distances (ddr
, save_v
, index_carry
);
3067 add_outer_distances (ddr
, dist_v
, index_carry
);
3072 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3073 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3075 if (DDR_NB_LOOPS (ddr
) > 1)
3077 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3079 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3080 DDR_A (ddr
), loop_nest
))
3082 compute_subscript_distance (ddr
);
3083 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3084 opposite_v
, &init_b
,
3088 save_dist_v (ddr
, save_v
);
3089 add_outer_distances (ddr
, dist_v
, index_carry
);
3090 add_outer_distances (ddr
, opposite_v
, index_carry
);
3093 save_dist_v (ddr
, save_v
);
3098 /* There is a distance of 1 on all the outer loops: Example:
3099 there is a dependence of distance 1 on loop_1 for the array A.
3105 add_outer_distances (ddr
, dist_v
,
3106 lambda_vector_first_nz (dist_v
,
3107 DDR_NB_LOOPS (ddr
), 0));
3110 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3114 fprintf (dump_file
, "(build_classic_dist_vector\n");
3115 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3117 fprintf (dump_file
, " dist_vector = (");
3118 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3119 DDR_NB_LOOPS (ddr
));
3120 fprintf (dump_file
, " )\n");
3122 fprintf (dump_file
, ")\n");
3128 /* Return the direction for a given distance.
3129 FIXME: Computing dir this way is suboptimal, since dir can catch
3130 cases that dist is unable to represent. */
3132 static inline enum data_dependence_direction
3133 dir_from_dist (int dist
)
3136 return dir_positive
;
3138 return dir_negative
;
3143 /* Compute the classic per loop direction vector. DDR is the data
3144 dependence relation to build a vector from. */
3147 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3150 lambda_vector dist_v
;
3152 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3154 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3156 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3157 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3159 save_dir_v (ddr
, dir_v
);
3163 /* Helper function. Returns true when there is a dependence between
3164 data references DRA and DRB. */
3167 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3168 struct data_reference
*dra
,
3169 struct data_reference
*drb
,
3170 struct loop
*loop_nest
)
3173 tree last_conflicts
;
3174 struct subscript
*subscript
;
3176 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3179 conflict_function
*overlaps_a
, *overlaps_b
;
3181 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3182 DR_ACCESS_FN (drb
, i
),
3183 &overlaps_a
, &overlaps_b
,
3184 &last_conflicts
, loop_nest
);
3186 if (CF_NOT_KNOWN_P (overlaps_a
)
3187 || CF_NOT_KNOWN_P (overlaps_b
))
3189 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3190 dependence_stats
.num_dependence_undetermined
++;
3191 free_conflict_function (overlaps_a
);
3192 free_conflict_function (overlaps_b
);
3196 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3197 || CF_NO_DEPENDENCE_P (overlaps_b
))
3199 finalize_ddr_dependent (ddr
, chrec_known
);
3200 dependence_stats
.num_dependence_independent
++;
3201 free_conflict_function (overlaps_a
);
3202 free_conflict_function (overlaps_b
);
3208 if (SUB_CONFLICTS_IN_A (subscript
))
3209 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3210 if (SUB_CONFLICTS_IN_B (subscript
))
3211 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3213 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3214 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3215 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3222 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3225 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3226 struct loop
*loop_nest
)
3229 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3230 fprintf (dump_file
, "(subscript_dependence_tester \n");
3232 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3233 dependence_stats
.num_dependence_dependent
++;
3235 compute_subscript_distance (ddr
);
3236 if (build_classic_dist_vector (ddr
, loop_nest
))
3237 build_classic_dir_vector (ddr
);
3239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3240 fprintf (dump_file
, ")\n");
3243 /* Returns true when all the access functions of A are affine or
3244 constant with respect to LOOP_NEST. */
3247 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3248 const struct loop
*loop_nest
)
3251 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3254 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
3255 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3256 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3262 /* Initializes an equation for an OMEGA problem using the information
3263 contained in the ACCESS_FUN. Returns true when the operation
3266 PB is the omega constraint system.
3267 EQ is the number of the equation to be initialized.
3268 OFFSET is used for shifting the variables names in the constraints:
3269 a constrain is composed of 2 * the number of variables surrounding
3270 dependence accesses. OFFSET is set either to 0 for the first n variables,
3271 then it is set to n.
3272 ACCESS_FUN is expected to be an affine chrec. */
3275 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3276 unsigned int offset
, tree access_fun
,
3277 struct data_dependence_relation
*ddr
)
3279 switch (TREE_CODE (access_fun
))
3281 case POLYNOMIAL_CHREC
:
3283 tree left
= CHREC_LEFT (access_fun
);
3284 tree right
= CHREC_RIGHT (access_fun
);
3285 int var
= CHREC_VARIABLE (access_fun
);
3288 if (TREE_CODE (right
) != INTEGER_CST
)
3291 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3292 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3294 /* Compute the innermost loop index. */
3295 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3298 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3299 += int_cst_value (right
);
3301 switch (TREE_CODE (left
))
3303 case POLYNOMIAL_CHREC
:
3304 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3307 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3316 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3324 /* As explained in the comments preceding init_omega_for_ddr, we have
3325 to set up a system for each loop level, setting outer loops
3326 variation to zero, and current loop variation to positive or zero.
3327 Save each lexico positive distance vector. */
3330 omega_extract_distance_vectors (omega_pb pb
,
3331 struct data_dependence_relation
*ddr
)
3335 struct loop
*loopi
, *loopj
;
3336 enum omega_result res
;
3338 /* Set a new problem for each loop in the nest. The basis is the
3339 problem that we have initialized until now. On top of this we
3340 add new constraints. */
3341 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3342 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3345 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3346 DDR_NB_LOOPS (ddr
));
3348 omega_copy_problem (copy
, pb
);
3350 /* For all the outer loops "loop_j", add "dj = 0". */
3352 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3354 eq
= omega_add_zero_eq (copy
, omega_black
);
3355 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3358 /* For "loop_i", add "0 <= di". */
3359 geq
= omega_add_zero_geq (copy
, omega_black
);
3360 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3362 /* Reduce the constraint system, and test that the current
3363 problem is feasible. */
3364 res
= omega_simplify_problem (copy
);
3365 if (res
== omega_false
3366 || res
== omega_unknown
3367 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3370 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3371 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3373 dist
= copy
->subs
[eq
].coef
[0];
3379 /* Reinitialize problem... */
3380 omega_copy_problem (copy
, pb
);
3382 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3384 eq
= omega_add_zero_eq (copy
, omega_black
);
3385 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3388 /* ..., but this time "di = 1". */
3389 eq
= omega_add_zero_eq (copy
, omega_black
);
3390 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3391 copy
->eqs
[eq
].coef
[0] = -1;
3393 res
= omega_simplify_problem (copy
);
3394 if (res
== omega_false
3395 || res
== omega_unknown
3396 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3399 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3400 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3402 dist
= copy
->subs
[eq
].coef
[0];
3408 /* Save the lexicographically positive distance vector. */
3411 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3412 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3416 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3417 if (copy
->subs
[eq
].key
> 0)
3419 dist
= copy
->subs
[eq
].coef
[0];
3420 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3423 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3424 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3426 save_dist_v (ddr
, dist_v
);
3427 save_dir_v (ddr
, dir_v
);
3431 omega_free_problem (copy
);
3435 /* This is called for each subscript of a tuple of data references:
3436 insert an equality for representing the conflicts. */
3439 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3440 struct data_dependence_relation
*ddr
,
3441 omega_pb pb
, bool *maybe_dependent
)
3444 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3445 TREE_TYPE (access_fun_b
));
3446 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL_TREE
);
3447 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL_TREE
);
3448 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3450 /* When the fun_a - fun_b is not constant, the dependence is not
3451 captured by the classic distance vector representation. */
3452 if (TREE_CODE (difference
) != INTEGER_CST
)
3456 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3458 /* There is no dependence. */
3459 *maybe_dependent
= false;
3463 fun_b
= chrec_fold_multiply (type
, fun_b
, integer_minus_one_node
);
3465 eq
= omega_add_zero_eq (pb
, omega_black
);
3466 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3467 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3468 /* There is probably a dependence, but the system of
3469 constraints cannot be built: answer "don't know". */
3473 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3474 && !int_divides_p (lambda_vector_gcd
3475 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3476 2 * DDR_NB_LOOPS (ddr
)),
3477 pb
->eqs
[eq
].coef
[0]))
3479 /* There is no dependence. */
3480 *maybe_dependent
= false;
3487 /* Helper function, same as init_omega_for_ddr but specialized for
3488 data references A and B. */
3491 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3492 struct data_dependence_relation
*ddr
,
3493 omega_pb pb
, bool *maybe_dependent
)
3498 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3500 /* Insert an equality per subscript. */
3501 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3503 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3504 ddr
, pb
, maybe_dependent
))
3506 else if (*maybe_dependent
== false)
3508 /* There is no dependence. */
3509 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3514 /* Insert inequalities: constraints corresponding to the iteration
3515 domain, i.e. the loops surrounding the references "loop_x" and
3516 the distance variables "dx". The layout of the OMEGA
3517 representation is as follows:
3518 - coef[0] is the constant
3519 - coef[1..nb_loops] are the protected variables that will not be
3520 removed by the solver: the "dx"
3521 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3523 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3524 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3526 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3529 ineq
= omega_add_zero_geq (pb
, omega_black
);
3530 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3532 /* 0 <= loop_x + dx */
3533 ineq
= omega_add_zero_geq (pb
, omega_black
);
3534 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3535 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3539 /* loop_x <= nb_iters */
3540 ineq
= omega_add_zero_geq (pb
, omega_black
);
3541 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3542 pb
->geqs
[ineq
].coef
[0] = nbi
;
3544 /* loop_x + dx <= nb_iters */
3545 ineq
= omega_add_zero_geq (pb
, omega_black
);
3546 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3547 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3548 pb
->geqs
[ineq
].coef
[0] = nbi
;
3550 /* A step "dx" bigger than nb_iters is not feasible, so
3551 add "0 <= nb_iters + dx", */
3552 ineq
= omega_add_zero_geq (pb
, omega_black
);
3553 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3554 pb
->geqs
[ineq
].coef
[0] = nbi
;
3555 /* and "dx <= nb_iters". */
3556 ineq
= omega_add_zero_geq (pb
, omega_black
);
3557 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3558 pb
->geqs
[ineq
].coef
[0] = nbi
;
3562 omega_extract_distance_vectors (pb
, ddr
);
3567 /* Sets up the Omega dependence problem for the data dependence
3568 relation DDR. Returns false when the constraint system cannot be
3569 built, ie. when the test answers "don't know". Returns true
3570 otherwise, and when independence has been proved (using one of the
3571 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3572 set MAYBE_DEPENDENT to true.
3574 Example: for setting up the dependence system corresponding to the
3575 conflicting accesses
3580 | ... A[2*j, 2*(i + j)]
3584 the following constraints come from the iteration domain:
3591 where di, dj are the distance variables. The constraints
3592 representing the conflicting elements are:
3595 i + 1 = 2 * (i + di + j + dj)
3597 For asking that the resulting distance vector (di, dj) be
3598 lexicographically positive, we insert the constraint "di >= 0". If
3599 "di = 0" in the solution, we fix that component to zero, and we
3600 look at the inner loops: we set a new problem where all the outer
3601 loop distances are zero, and fix this inner component to be
3602 positive. When one of the components is positive, we save that
3603 distance, and set a new problem where the distance on this loop is
3604 zero, searching for other distances in the inner loops. Here is
3605 the classic example that illustrates that we have to set for each
3606 inner loop a new problem:
3614 we have to save two distances (1, 0) and (0, 1).
3616 Given two array references, refA and refB, we have to set the
3617 dependence problem twice, refA vs. refB and refB vs. refA, and we
3618 cannot do a single test, as refB might occur before refA in the
3619 inner loops, and the contrary when considering outer loops: ex.
3624 | T[{1,+,1}_2][{1,+,1}_1] // refA
3625 | T[{2,+,1}_2][{0,+,1}_1] // refB
3630 refB touches the elements in T before refA, and thus for the same
3631 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3632 but for successive loop_0 iterations, we have (1, -1, 1)
3634 The Omega solver expects the distance variables ("di" in the
3635 previous example) to come first in the constraint system (as
3636 variables to be protected, or "safe" variables), the constraint
3637 system is built using the following layout:
3639 "cst | distance vars | index vars".
3643 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3644 bool *maybe_dependent
)
3649 *maybe_dependent
= true;
3651 if (same_access_functions (ddr
))
3654 lambda_vector dir_v
;
3656 /* Save the 0 vector. */
3657 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3658 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3659 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3660 dir_v
[j
] = dir_equal
;
3661 save_dir_v (ddr
, dir_v
);
3663 /* Save the dependences carried by outer loops. */
3664 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3665 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3667 omega_free_problem (pb
);
3671 /* Omega expects the protected variables (those that have to be kept
3672 after elimination) to appear first in the constraint system.
3673 These variables are the distance variables. In the following
3674 initialization we declare NB_LOOPS safe variables, and the total
3675 number of variables for the constraint system is 2*NB_LOOPS. */
3676 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3677 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3679 omega_free_problem (pb
);
3681 /* Stop computation if not decidable, or no dependence. */
3682 if (res
== false || *maybe_dependent
== false)
3685 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3686 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3688 omega_free_problem (pb
);
3693 /* Return true when DDR contains the same information as that stored
3694 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3697 ddr_consistent_p (FILE *file
,
3698 struct data_dependence_relation
*ddr
,
3699 VEC (lambda_vector
, heap
) *dist_vects
,
3700 VEC (lambda_vector
, heap
) *dir_vects
)
3704 /* If dump_file is set, output there. */
3705 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3708 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3710 lambda_vector b_dist_v
;
3711 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3712 VEC_length (lambda_vector
, dist_vects
),
3713 DDR_NUM_DIST_VECTS (ddr
));
3715 fprintf (file
, "Banerjee dist vectors:\n");
3716 for (i
= 0; VEC_iterate (lambda_vector
, dist_vects
, i
, b_dist_v
); i
++)
3717 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3719 fprintf (file
, "Omega dist vectors:\n");
3720 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3721 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3723 fprintf (file
, "data dependence relation:\n");
3724 dump_data_dependence_relation (file
, ddr
);
3726 fprintf (file
, ")\n");
3730 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3732 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3733 VEC_length (lambda_vector
, dir_vects
),
3734 DDR_NUM_DIR_VECTS (ddr
));
3738 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3740 lambda_vector a_dist_v
;
3741 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3743 /* Distance vectors are not ordered in the same way in the DDR
3744 and in the DIST_VECTS: search for a matching vector. */
3745 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, a_dist_v
); j
++)
3746 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3749 if (j
== VEC_length (lambda_vector
, dist_vects
))
3751 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3752 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3753 fprintf (file
, "not found in Omega dist vectors:\n");
3754 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3755 fprintf (file
, "data dependence relation:\n");
3756 dump_data_dependence_relation (file
, ddr
);
3757 fprintf (file
, ")\n");
3761 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3763 lambda_vector a_dir_v
;
3764 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3766 /* Direction vectors are not ordered in the same way in the DDR
3767 and in the DIR_VECTS: search for a matching vector. */
3768 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, a_dir_v
); j
++)
3769 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3772 if (j
== VEC_length (lambda_vector
, dist_vects
))
3774 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3775 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3776 fprintf (file
, "not found in Omega dir vectors:\n");
3777 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3778 fprintf (file
, "data dependence relation:\n");
3779 dump_data_dependence_relation (file
, ddr
);
3780 fprintf (file
, ")\n");
3787 /* This computes the affine dependence relation between A and B with
3788 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3789 independence between two accesses, while CHREC_DONT_KNOW is used
3790 for representing the unknown relation.
3792 Note that it is possible to stop the computation of the dependence
3793 relation the first time we detect a CHREC_KNOWN element for a given
3797 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3798 struct loop
*loop_nest
)
3800 struct data_reference
*dra
= DDR_A (ddr
);
3801 struct data_reference
*drb
= DDR_B (ddr
);
3803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3805 fprintf (dump_file
, "(compute_affine_dependence\n");
3806 fprintf (dump_file
, " (stmt_a = \n");
3807 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
3808 fprintf (dump_file
, ")\n (stmt_b = \n");
3809 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
3810 fprintf (dump_file
, ")\n");
3813 /* Analyze only when the dependence relation is not yet known. */
3814 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3816 dependence_stats
.num_dependence_tests
++;
3818 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3819 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3821 if (flag_check_data_deps
)
3823 /* Compute the dependences using the first algorithm. */
3824 subscript_dependence_tester (ddr
, loop_nest
);
3826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3828 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3829 dump_data_dependence_relation (dump_file
, ddr
);
3832 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3834 bool maybe_dependent
;
3835 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3837 /* Save the result of the first DD analyzer. */
3838 dist_vects
= DDR_DIST_VECTS (ddr
);
3839 dir_vects
= DDR_DIR_VECTS (ddr
);
3841 /* Reset the information. */
3842 DDR_DIST_VECTS (ddr
) = NULL
;
3843 DDR_DIR_VECTS (ddr
) = NULL
;
3845 /* Compute the same information using Omega. */
3846 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3847 goto csys_dont_know
;
3849 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3851 fprintf (dump_file
, "Omega Analyzer\n");
3852 dump_data_dependence_relation (dump_file
, ddr
);
3855 /* Check that we get the same information. */
3856 if (maybe_dependent
)
3857 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3862 subscript_dependence_tester (ddr
, loop_nest
);
3865 /* As a last case, if the dependence cannot be determined, or if
3866 the dependence is considered too difficult to determine, answer
3871 dependence_stats
.num_dependence_undetermined
++;
3873 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3875 fprintf (dump_file
, "Data ref a:\n");
3876 dump_data_reference (dump_file
, dra
);
3877 fprintf (dump_file
, "Data ref b:\n");
3878 dump_data_reference (dump_file
, drb
);
3879 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3881 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3886 fprintf (dump_file
, ")\n");
3889 /* This computes the dependence relation for the same data
3890 reference into DDR. */
3893 compute_self_dependence (struct data_dependence_relation
*ddr
)
3896 struct subscript
*subscript
;
3898 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3901 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3904 if (SUB_CONFLICTS_IN_A (subscript
))
3905 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3906 if (SUB_CONFLICTS_IN_B (subscript
))
3907 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3909 /* The accessed index overlaps for each iteration. */
3910 SUB_CONFLICTS_IN_A (subscript
)
3911 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3912 SUB_CONFLICTS_IN_B (subscript
)
3913 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3914 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3917 /* The distance vector is the zero vector. */
3918 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3919 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3922 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3923 the data references in DATAREFS, in the LOOP_NEST. When
3924 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3928 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
3929 VEC (ddr_p
, heap
) **dependence_relations
,
3930 VEC (loop_p
, heap
) *loop_nest
,
3931 bool compute_self_and_rr
)
3933 struct data_dependence_relation
*ddr
;
3934 struct data_reference
*a
, *b
;
3937 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
3938 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
3939 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
3941 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
3942 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3943 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
3946 if (compute_self_and_rr
)
3947 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
3949 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
3950 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3951 compute_self_dependence (ddr
);
3955 /* Stores the locations of memory references in STMT to REFERENCES. Returns
3956 true if STMT clobbers memory, false otherwise. */
3959 get_references_in_stmt (tree stmt
, VEC (data_ref_loc
, heap
) **references
)
3961 bool clobbers_memory
= false;
3963 tree
*op0
, *op1
, call
;
3967 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3968 Calls have side-effects, except those to const or pure
3970 call
= get_call_expr_in (stmt
);
3972 && !(call_expr_flags (call
) & (ECF_CONST
| ECF_PURE
)))
3973 || (TREE_CODE (stmt
) == ASM_EXPR
3974 && ASM_VOLATILE_P (stmt
)))
3975 clobbers_memory
= true;
3977 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
3978 return clobbers_memory
;
3980 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3982 op0
= &GIMPLE_STMT_OPERAND (stmt
, 0);
3983 op1
= &GIMPLE_STMT_OPERAND (stmt
, 1);
3986 || (REFERENCE_CLASS_P (*op1
) && get_base_address (*op1
)))
3988 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
3990 ref
->is_read
= true;
3994 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
3996 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
3998 ref
->is_read
= false;
4004 unsigned i
, n
= call_expr_nargs (call
);
4006 for (i
= 0; i
< n
; i
++)
4008 op0
= &CALL_EXPR_ARG (call
, i
);
4011 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4013 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4015 ref
->is_read
= true;
4020 return clobbers_memory
;
4023 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4024 reference, returns false, otherwise returns true. NEST is the outermost
4025 loop of the loop nest in that the references should be analyzed. */
4028 find_data_references_in_stmt (struct loop
*nest
, tree stmt
,
4029 VEC (data_reference_p
, heap
) **datarefs
)
4032 VEC (data_ref_loc
, heap
) *references
;
4035 data_reference_p dr
;
4037 if (get_references_in_stmt (stmt
, &references
))
4039 VEC_free (data_ref_loc
, heap
, references
);
4043 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
4045 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4046 gcc_assert (dr
!= NULL
);
4048 /* FIXME -- data dependence analysis does not work correctly for objects with
4049 invariant addresses. Let us fail here until the problem is fixed. */
4050 if (dr_address_invariant_p (dr
))
4053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4054 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
4059 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4061 VEC_free (data_ref_loc
, heap
, references
);
4065 /* Search the data references in LOOP, and record the information into
4066 DATAREFS. Returns chrec_dont_know when failing to analyze a
4067 difficult case, returns NULL_TREE otherwise.
4069 TODO: This function should be made smarter so that it can handle address
4070 arithmetic as if they were array accesses, etc. */
4073 find_data_references_in_loop (struct loop
*loop
,
4074 VEC (data_reference_p
, heap
) **datarefs
)
4076 basic_block bb
, *bbs
;
4078 block_stmt_iterator bsi
;
4080 bbs
= get_loop_body_in_dom_order (loop
);
4082 for (i
= 0; i
< loop
->num_nodes
; i
++)
4086 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4088 tree stmt
= bsi_stmt (bsi
);
4090 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4092 struct data_reference
*res
;
4093 res
= XCNEW (struct data_reference
);
4094 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4097 return chrec_dont_know
;
4106 /* Recursive helper function. */
4109 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4111 /* Inner loops of the nest should not contain siblings. Example:
4112 when there are two consecutive loops,
4123 the dependence relation cannot be captured by the distance
4128 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4130 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4134 /* Return false when the LOOP is not well nested. Otherwise return
4135 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4136 contain the loops from the outermost to the innermost, as they will
4137 appear in the classic distance vector. */
4140 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4142 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4144 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4148 /* Given a loop nest LOOP, the following vectors are returned:
4149 DATAREFS is initialized to all the array elements contained in this loop,
4150 DEPENDENCE_RELATIONS contains the relations between the data references.
4151 Compute read-read and self relations if
4152 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4155 compute_data_dependences_for_loop (struct loop
*loop
,
4156 bool compute_self_and_read_read_dependences
,
4157 VEC (data_reference_p
, heap
) **datarefs
,
4158 VEC (ddr_p
, heap
) **dependence_relations
)
4160 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4162 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4164 /* If the loop nest is not well formed, or one of the data references
4165 is not computable, give up without spending time to compute other
4168 || !find_loop_nest (loop
, &vloops
)
4169 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4171 struct data_dependence_relation
*ddr
;
4173 /* Insert a single relation into dependence_relations:
4175 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4176 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4179 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4180 compute_self_and_read_read_dependences
);
4182 if (dump_file
&& (dump_flags
& TDF_STATS
))
4184 fprintf (dump_file
, "Dependence tester statistics:\n");
4186 fprintf (dump_file
, "Number of dependence tests: %d\n",
4187 dependence_stats
.num_dependence_tests
);
4188 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4189 dependence_stats
.num_dependence_dependent
);
4190 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4191 dependence_stats
.num_dependence_independent
);
4192 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4193 dependence_stats
.num_dependence_undetermined
);
4195 fprintf (dump_file
, "Number of subscript tests: %d\n",
4196 dependence_stats
.num_subscript_tests
);
4197 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4198 dependence_stats
.num_subscript_undetermined
);
4199 fprintf (dump_file
, "Number of same subscript function: %d\n",
4200 dependence_stats
.num_same_subscript_function
);
4202 fprintf (dump_file
, "Number of ziv tests: %d\n",
4203 dependence_stats
.num_ziv
);
4204 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4205 dependence_stats
.num_ziv_dependent
);
4206 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4207 dependence_stats
.num_ziv_independent
);
4208 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4209 dependence_stats
.num_ziv_unimplemented
);
4211 fprintf (dump_file
, "Number of siv tests: %d\n",
4212 dependence_stats
.num_siv
);
4213 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4214 dependence_stats
.num_siv_dependent
);
4215 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4216 dependence_stats
.num_siv_independent
);
4217 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4218 dependence_stats
.num_siv_unimplemented
);
4220 fprintf (dump_file
, "Number of miv tests: %d\n",
4221 dependence_stats
.num_miv
);
4222 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4223 dependence_stats
.num_miv_dependent
);
4224 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4225 dependence_stats
.num_miv_independent
);
4226 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4227 dependence_stats
.num_miv_unimplemented
);
4231 /* Entry point (for testing only). Analyze all the data references
4232 and the dependence relations in LOOP.
4234 The data references are computed first.
4236 A relation on these nodes is represented by a complete graph. Some
4237 of the relations could be of no interest, thus the relations can be
4240 In the following function we compute all the relations. This is
4241 just a first implementation that is here for:
4242 - for showing how to ask for the dependence relations,
4243 - for the debugging the whole dependence graph,
4244 - for the dejagnu testcases and maintenance.
4246 It is possible to ask only for a part of the graph, avoiding to
4247 compute the whole dependence graph. The computed dependences are
4248 stored in a knowledge base (KB) such that later queries don't
4249 recompute the same information. The implementation of this KB is
4250 transparent to the optimizer, and thus the KB can be changed with a
4251 more efficient implementation, or the KB could be disabled. */
4253 analyze_all_data_dependences (struct loop
*loop
)
4256 int nb_data_refs
= 10;
4257 VEC (data_reference_p
, heap
) *datarefs
=
4258 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4259 VEC (ddr_p
, heap
) *dependence_relations
=
4260 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4262 /* Compute DDs on the whole function. */
4263 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4264 &dependence_relations
);
4268 dump_data_dependence_relations (dump_file
, dependence_relations
);
4269 fprintf (dump_file
, "\n\n");
4271 if (dump_flags
& TDF_DETAILS
)
4272 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4274 if (dump_flags
& TDF_STATS
)
4276 unsigned nb_top_relations
= 0;
4277 unsigned nb_bot_relations
= 0;
4278 unsigned nb_basename_differ
= 0;
4279 unsigned nb_chrec_relations
= 0;
4280 struct data_dependence_relation
*ddr
;
4282 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4284 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4287 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4289 struct data_reference
*a
= DDR_A (ddr
);
4290 struct data_reference
*b
= DDR_B (ddr
);
4292 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
4293 nb_basename_differ
++;
4299 nb_chrec_relations
++;
4302 gather_stats_on_scev_database ();
4306 free_dependence_relations (dependence_relations
);
4307 free_data_refs (datarefs
);
4310 /* Computes all the data dependences and check that the results of
4311 several analyzers are the same. */
4314 tree_check_data_deps (void)
4317 struct loop
*loop_nest
;
4319 FOR_EACH_LOOP (li
, loop_nest
, 0)
4320 analyze_all_data_dependences (loop_nest
);
4323 /* Free the memory used by a data dependence relation DDR. */
4326 free_dependence_relation (struct data_dependence_relation
*ddr
)
4331 if (DDR_SUBSCRIPTS (ddr
))
4332 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4333 if (DDR_DIST_VECTS (ddr
))
4334 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4335 if (DDR_DIR_VECTS (ddr
))
4336 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4341 /* Free the memory used by the data dependence relations from
4342 DEPENDENCE_RELATIONS. */
4345 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4348 struct data_dependence_relation
*ddr
;
4349 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4351 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4355 if (loop_nest
== NULL
)
4356 loop_nest
= DDR_LOOP_NEST (ddr
);
4358 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4359 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4360 free_dependence_relation (ddr
);
4364 VEC_free (loop_p
, heap
, loop_nest
);
4365 VEC_free (ddr_p
, heap
, dependence_relations
);
4368 /* Free the memory used by the data references from DATAREFS. */
4371 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4374 struct data_reference
*dr
;
4376 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4378 VEC_free (data_reference_p
, heap
, datarefs
);
4383 /* Returns the index of STMT in RDG. */
4386 find_vertex_for_stmt (const struct graph
*rdg
, const_tree stmt
)
4390 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4391 if (RDGV_STMT (&(rdg
->vertices
[i
])) == stmt
)
4398 /* Creates an edge in RDG for each distance vector from DDR. */
4401 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4404 data_reference_p dra
;
4405 data_reference_p drb
;
4406 struct graph_edge
*e
;
4408 if (DDR_REVERSED_P (ddr
))
4419 va
= find_vertex_for_stmt (rdg
, DR_STMT (dra
));
4420 vb
= find_vertex_for_stmt (rdg
, DR_STMT (drb
));
4422 e
= add_edge (rdg
, va
, vb
);
4423 e
->data
= XNEW (struct rdg_edge
);
4425 /* Determines the type of the data dependence. */
4426 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4427 RDGE_TYPE (e
) = input_dd
;
4428 else if (!DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4429 RDGE_TYPE (e
) = output_dd
;
4430 else if (!DR_IS_READ (dra
) && DR_IS_READ (drb
))
4431 RDGE_TYPE (e
) = flow_dd
;
4432 else if (DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4433 RDGE_TYPE (e
) = anti_dd
;
4436 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4437 the index of DEF in RDG. */
4440 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4442 use_operand_p imm_use_p
;
4443 imm_use_iterator iterator
;
4445 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4447 int use
= find_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4448 struct graph_edge
*e
= add_edge (rdg
, idef
, use
);
4450 e
->data
= XNEW (struct rdg_edge
);
4451 RDGE_TYPE (e
) = flow_dd
;
4455 /* Creates the edges of the reduced dependence graph RDG. */
4458 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4461 struct data_dependence_relation
*ddr
;
4462 def_operand_p def_p
;
4465 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
4466 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4467 create_rdg_edge_for_ddr (rdg
, ddr
);
4469 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4470 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDGV_STMT (&(rdg
->vertices
[i
])),
4471 iter
, SSA_OP_ALL_DEFS
)
4472 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4475 /* Build the vertices of the reduced dependence graph RDG. */
4478 create_rdg_vertices (struct graph
*rdg
, VEC (tree
, heap
) *stmts
)
4483 for (i
= 0; VEC_iterate (tree
, stmts
, i
, s
); i
++)
4485 struct vertex
*v
= &(rdg
->vertices
[i
]);
4487 v
->data
= XNEW (struct rdg_vertex
);
4492 /* Initialize STMTS with all the statements and PHI nodes of LOOP. */
4495 stmts_from_loop (struct loop
*loop
, VEC (tree
, heap
) **stmts
)
4498 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4500 for (i
= 0; i
< loop
->num_nodes
; i
++)
4503 basic_block bb
= bbs
[i
];
4504 block_stmt_iterator bsi
;
4506 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
4507 VEC_safe_push (tree
, heap
, *stmts
, phi
);
4509 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4510 VEC_safe_push (tree
, heap
, *stmts
, bsi_stmt (bsi
));
4516 /* Returns true when all the dependences are computable. */
4519 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
4524 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4525 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4531 /* Build a Reduced Dependence Graph with one vertex per statement of the
4532 loop nest and one edge per data dependence or scalar dependence. */
4535 build_rdg (struct loop
*loop
)
4537 int nb_data_refs
= 10;
4538 struct graph
*rdg
= NULL
;
4539 VEC (ddr_p
, heap
) *dependence_relations
;
4540 VEC (data_reference_p
, heap
) *datarefs
;
4541 VEC (tree
, heap
) *stmts
= VEC_alloc (tree
, heap
, 10);
4543 dependence_relations
= VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
) ;
4544 datarefs
= VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4545 compute_data_dependences_for_loop (loop
,
4548 &dependence_relations
);
4550 if (!known_dependences_p (dependence_relations
))
4553 stmts_from_loop (loop
, &stmts
);
4554 rdg
= new_graph (VEC_length (tree
, stmts
));
4555 create_rdg_vertices (rdg
, stmts
);
4556 create_rdg_edges (rdg
, dependence_relations
);
4559 free_dependence_relations (dependence_relations
);
4560 free_data_refs (datarefs
);
4561 VEC_free (tree
, heap
, stmts
);