1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
84 /* These RTL headers are needed for basic-block.h. */
86 #include "basic-block.h"
87 #include "diagnostic.h"
88 #include "tree-flow.h"
89 #include "tree-dump.h"
92 #include "tree-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 to STDERR all the dependence relations from DDRS. */
163 debug_data_dependence_relations (VEC (ddr_p
, heap
) *ddrs
)
165 dump_data_dependence_relations (stderr
, ddrs
);
168 /* Dump into FILE all the dependence relations from DDRS. */
171 dump_data_dependence_relations (FILE *file
,
172 VEC (ddr_p
, heap
) *ddrs
)
175 struct data_dependence_relation
*ddr
;
177 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
178 dump_data_dependence_relation (file
, ddr
);
181 /* Dump function for a DATA_REFERENCE structure. */
184 dump_data_reference (FILE *outf
,
185 struct data_reference
*dr
)
189 fprintf (outf
, "(Data Ref: \n stmt: ");
190 print_gimple_stmt (outf
, DR_STMT (dr
), 0, 0);
191 fprintf (outf
, " ref: ");
192 print_generic_stmt (outf
, DR_REF (dr
), 0);
193 fprintf (outf
, " base_object: ");
194 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
196 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
198 fprintf (outf
, " Access function %d: ", i
);
199 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
201 fprintf (outf
, ")\n");
204 /* Dumps the affine function described by FN to the file OUTF. */
207 dump_affine_function (FILE *outf
, affine_fn fn
)
212 print_generic_expr (outf
, VEC_index (tree
, fn
, 0), TDF_SLIM
);
213 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
215 fprintf (outf
, " + ");
216 print_generic_expr (outf
, coef
, TDF_SLIM
);
217 fprintf (outf
, " * x_%u", i
);
221 /* Dumps the conflict function CF to the file OUTF. */
224 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
228 if (cf
->n
== NO_DEPENDENCE
)
229 fprintf (outf
, "no dependence\n");
230 else if (cf
->n
== NOT_KNOWN
)
231 fprintf (outf
, "not known\n");
234 for (i
= 0; i
< cf
->n
; i
++)
237 dump_affine_function (outf
, cf
->fns
[i
]);
238 fprintf (outf
, "]\n");
243 /* Dump function for a SUBSCRIPT structure. */
246 dump_subscript (FILE *outf
, struct subscript
*subscript
)
248 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
250 fprintf (outf
, "\n (subscript \n");
251 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
252 dump_conflict_function (outf
, cf
);
253 if (CF_NONTRIVIAL_P (cf
))
255 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
256 fprintf (outf
, " last_conflict: ");
257 print_generic_stmt (outf
, last_iteration
, 0);
260 cf
= SUB_CONFLICTS_IN_B (subscript
);
261 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
262 dump_conflict_function (outf
, cf
);
263 if (CF_NONTRIVIAL_P (cf
))
265 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
266 fprintf (outf
, " last_conflict: ");
267 print_generic_stmt (outf
, last_iteration
, 0);
270 fprintf (outf
, " (Subscript distance: ");
271 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
272 fprintf (outf
, " )\n");
273 fprintf (outf
, " )\n");
276 /* Print the classic direction vector DIRV to OUTF. */
279 print_direction_vector (FILE *outf
,
285 for (eq
= 0; eq
< length
; eq
++)
287 enum data_dependence_direction dir
= dirv
[eq
];
292 fprintf (outf
, " +");
295 fprintf (outf
, " -");
298 fprintf (outf
, " =");
300 case dir_positive_or_equal
:
301 fprintf (outf
, " +=");
303 case dir_positive_or_negative
:
304 fprintf (outf
, " +-");
306 case dir_negative_or_equal
:
307 fprintf (outf
, " -=");
310 fprintf (outf
, " *");
313 fprintf (outf
, "indep");
317 fprintf (outf
, "\n");
320 /* Print a vector of direction vectors. */
323 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
329 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
330 print_direction_vector (outf
, v
, length
);
333 /* Print a vector of distance vectors. */
336 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
342 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
343 print_lambda_vector (outf
, v
, length
);
349 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
351 dump_data_dependence_relation (stderr
, ddr
);
354 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
357 dump_data_dependence_relation (FILE *outf
,
358 struct data_dependence_relation
*ddr
)
360 struct data_reference
*dra
, *drb
;
362 fprintf (outf
, "(Data Dep: \n");
364 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
366 fprintf (outf
, " (don't know)\n)\n");
372 dump_data_reference (outf
, dra
);
373 dump_data_reference (outf
, drb
);
375 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
376 fprintf (outf
, " (no dependence)\n");
378 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
383 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
385 fprintf (outf
, " access_fn_A: ");
386 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
387 fprintf (outf
, " access_fn_B: ");
388 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
389 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
392 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
393 fprintf (outf
, " loop nest: (");
394 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
395 fprintf (outf
, "%d ", loopi
->num
);
396 fprintf (outf
, ")\n");
398 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
400 fprintf (outf
, " distance_vector: ");
401 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
405 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
407 fprintf (outf
, " direction_vector: ");
408 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
413 fprintf (outf
, ")\n");
416 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
419 dump_data_dependence_direction (FILE *file
,
420 enum data_dependence_direction dir
)
436 case dir_positive_or_negative
:
437 fprintf (file
, "+-");
440 case dir_positive_or_equal
:
441 fprintf (file
, "+=");
444 case dir_negative_or_equal
:
445 fprintf (file
, "-=");
457 /* Dumps the distance and direction vectors in FILE. DDRS contains
458 the dependence relations, and VECT_SIZE is the size of the
459 dependence vectors, or in other words the number of loops in the
463 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
466 struct data_dependence_relation
*ddr
;
469 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
470 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
472 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
474 fprintf (file
, "DISTANCE_V (");
475 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
476 fprintf (file
, ")\n");
479 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
481 fprintf (file
, "DIRECTION_V (");
482 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
483 fprintf (file
, ")\n");
487 fprintf (file
, "\n\n");
490 /* Dumps the data dependence relations DDRS in FILE. */
493 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
496 struct data_dependence_relation
*ddr
;
498 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
499 dump_data_dependence_relation (file
, ddr
);
501 fprintf (file
, "\n\n");
504 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
505 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
506 constant of type ssizetype, and returns true. If we cannot do this
507 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
511 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
512 tree
*var
, tree
*off
)
516 enum tree_code ocode
= code
;
524 *var
= build_int_cst (type
, 0);
525 *off
= fold_convert (ssizetype
, op0
);
528 case POINTER_PLUS_EXPR
:
533 split_constant_offset (op0
, &var0
, &off0
);
534 split_constant_offset (op1
, &var1
, &off1
);
535 *var
= fold_build2 (code
, type
, var0
, var1
);
536 *off
= size_binop (ocode
, off0
, off1
);
540 if (TREE_CODE (op1
) != INTEGER_CST
)
543 split_constant_offset (op0
, &var0
, &off0
);
544 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
545 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
551 HOST_WIDE_INT pbitsize
, pbitpos
;
552 enum machine_mode pmode
;
553 int punsignedp
, pvolatilep
;
555 op0
= TREE_OPERAND (op0
, 0);
556 if (!handled_component_p (op0
))
559 base
= get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
,
560 &pmode
, &punsignedp
, &pvolatilep
, false);
562 if (pbitpos
% BITS_PER_UNIT
!= 0)
564 base
= build_fold_addr_expr (base
);
565 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
569 split_constant_offset (poffset
, &poffset
, &off1
);
570 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
571 if (POINTER_TYPE_P (TREE_TYPE (base
)))
572 base
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (base
),
573 base
, fold_convert (sizetype
, poffset
));
575 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
576 fold_convert (TREE_TYPE (base
), poffset
));
579 var0
= fold_convert (type
, base
);
581 /* If variable length types are involved, punt, otherwise casts
582 might be converted into ARRAY_REFs in gimplify_conversion.
583 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
584 possibly no longer appears in current GIMPLE, might resurface.
585 This perhaps could run
586 if (CONVERT_EXPR_P (var0))
588 gimplify_conversion (&var0);
589 // Attempt to fill in any within var0 found ARRAY_REF's
590 // element size from corresponding op embedded ARRAY_REF,
591 // if unsuccessful, just punt.
593 while (POINTER_TYPE_P (type
))
594 type
= TREE_TYPE (type
);
595 if (int_size_in_bytes (type
) < 0)
605 gimple def_stmt
= SSA_NAME_DEF_STMT (op0
);
606 enum tree_code subcode
;
608 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
611 var0
= gimple_assign_rhs1 (def_stmt
);
612 subcode
= gimple_assign_rhs_code (def_stmt
);
613 var1
= gimple_assign_rhs2 (def_stmt
);
615 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
623 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
624 will be ssizetype. */
627 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
629 tree type
= TREE_TYPE (exp
), otype
, op0
, op1
, e
, o
;
633 *off
= ssize_int (0);
636 if (automatically_generated_chrec_p (exp
))
639 otype
= TREE_TYPE (exp
);
640 code
= TREE_CODE (exp
);
641 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
642 if (split_constant_offset_1 (otype
, op0
, code
, op1
, &e
, &o
))
644 *var
= fold_convert (type
, e
);
649 /* Returns the address ADDR of an object in a canonical shape (without nop
650 casts, and with type of pointer to the object). */
653 canonicalize_base_object_address (tree addr
)
659 /* The base address may be obtained by casting from integer, in that case
661 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
664 if (TREE_CODE (addr
) != ADDR_EXPR
)
667 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
670 /* Analyzes the behavior of the memory reference DR in the innermost loop that
671 contains it. Returns true if analysis succeed or false otherwise. */
674 dr_analyze_innermost (struct data_reference
*dr
)
676 gimple stmt
= DR_STMT (dr
);
677 struct loop
*loop
= loop_containing_stmt (stmt
);
678 tree ref
= DR_REF (dr
);
679 HOST_WIDE_INT pbitsize
, pbitpos
;
681 enum machine_mode pmode
;
682 int punsignedp
, pvolatilep
;
683 affine_iv base_iv
, offset_iv
;
684 tree init
, dinit
, step
;
686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
687 fprintf (dump_file
, "analyze_innermost: ");
689 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
690 &pmode
, &punsignedp
, &pvolatilep
, false);
691 gcc_assert (base
!= NULL_TREE
);
693 if (pbitpos
% BITS_PER_UNIT
!= 0)
695 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
696 fprintf (dump_file
, "failed: bit offset alignment.\n");
700 base
= build_fold_addr_expr (base
);
701 if (!simple_iv (loop
, loop_containing_stmt (stmt
), base
, &base_iv
, false))
703 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
704 fprintf (dump_file
, "failed: evolution of base is not affine.\n");
709 offset_iv
.base
= ssize_int (0);
710 offset_iv
.step
= ssize_int (0);
712 else if (!simple_iv (loop
, loop_containing_stmt (stmt
),
713 poffset
, &offset_iv
, false))
715 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
716 fprintf (dump_file
, "failed: evolution of offset is not affine.\n");
720 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
721 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
722 init
= size_binop (PLUS_EXPR
, init
, dinit
);
723 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
724 init
= size_binop (PLUS_EXPR
, init
, dinit
);
726 step
= size_binop (PLUS_EXPR
,
727 fold_convert (ssizetype
, base_iv
.step
),
728 fold_convert (ssizetype
, offset_iv
.step
));
730 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
732 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
736 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
738 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
739 fprintf (dump_file
, "success.\n");
744 /* Determines the base object and the list of indices of memory reference
745 DR, analyzed in loop nest NEST. */
748 dr_analyze_indices (struct data_reference
*dr
, struct loop
*nest
)
750 gimple stmt
= DR_STMT (dr
);
751 struct loop
*loop
= loop_containing_stmt (stmt
);
752 VEC (tree
, heap
) *access_fns
= NULL
;
753 tree ref
= unshare_expr (DR_REF (dr
)), aref
= ref
, op
;
754 tree base
, off
, access_fn
;
755 basic_block before_loop
= block_before_loop (nest
);
757 while (handled_component_p (aref
))
759 if (TREE_CODE (aref
) == ARRAY_REF
)
761 op
= TREE_OPERAND (aref
, 1);
762 access_fn
= analyze_scalar_evolution (loop
, op
);
763 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
764 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
766 TREE_OPERAND (aref
, 1) = build_int_cst (TREE_TYPE (op
), 0);
769 aref
= TREE_OPERAND (aref
, 0);
772 if (INDIRECT_REF_P (aref
))
774 op
= TREE_OPERAND (aref
, 0);
775 access_fn
= analyze_scalar_evolution (loop
, op
);
776 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
777 base
= initial_condition (access_fn
);
778 split_constant_offset (base
, &base
, &off
);
779 access_fn
= chrec_replace_initial_condition (access_fn
,
780 fold_convert (TREE_TYPE (base
), off
));
782 TREE_OPERAND (aref
, 0) = base
;
783 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
786 DR_BASE_OBJECT (dr
) = ref
;
787 DR_ACCESS_FNS (dr
) = access_fns
;
790 /* Extracts the alias analysis information from the memory reference DR. */
793 dr_analyze_alias (struct data_reference
*dr
)
795 tree ref
= DR_REF (dr
);
796 tree base
= get_base_address (ref
), addr
;
798 if (INDIRECT_REF_P (base
))
800 addr
= TREE_OPERAND (base
, 0);
801 if (TREE_CODE (addr
) == SSA_NAME
)
802 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
806 /* Returns true if the address of DR is invariant. */
809 dr_address_invariant_p (struct data_reference
*dr
)
814 for (i
= 0; VEC_iterate (tree
, DR_ACCESS_FNS (dr
), i
, idx
); i
++)
815 if (tree_contains_chrecs (idx
, NULL
))
821 /* Frees data reference DR. */
824 free_data_ref (data_reference_p dr
)
826 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
830 /* Analyzes memory reference MEMREF accessed in STMT. The reference
831 is read if IS_READ is true, write otherwise. Returns the
832 data_reference description of MEMREF. NEST is the outermost loop of the
833 loop nest in that the reference should be analyzed. */
835 struct data_reference
*
836 create_data_ref (struct loop
*nest
, tree memref
, gimple stmt
, bool is_read
)
838 struct data_reference
*dr
;
840 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
842 fprintf (dump_file
, "Creating dr for ");
843 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
844 fprintf (dump_file
, "\n");
847 dr
= XCNEW (struct data_reference
);
849 DR_REF (dr
) = memref
;
850 DR_IS_READ (dr
) = is_read
;
852 dr_analyze_innermost (dr
);
853 dr_analyze_indices (dr
, nest
);
854 dr_analyze_alias (dr
);
856 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
858 fprintf (dump_file
, "\tbase_address: ");
859 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
860 fprintf (dump_file
, "\n\toffset from base address: ");
861 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
862 fprintf (dump_file
, "\n\tconstant offset from base address: ");
863 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
864 fprintf (dump_file
, "\n\tstep: ");
865 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
866 fprintf (dump_file
, "\n\taligned to: ");
867 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
868 fprintf (dump_file
, "\n\tbase_object: ");
869 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
870 fprintf (dump_file
, "\n");
876 /* Returns true if FNA == FNB. */
879 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
881 unsigned i
, n
= VEC_length (tree
, fna
);
883 if (n
!= VEC_length (tree
, fnb
))
886 for (i
= 0; i
< n
; i
++)
887 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
888 VEC_index (tree
, fnb
, i
), 0))
894 /* If all the functions in CF are the same, returns one of them,
895 otherwise returns NULL. */
898 common_affine_function (conflict_function
*cf
)
903 if (!CF_NONTRIVIAL_P (cf
))
908 for (i
= 1; i
< cf
->n
; i
++)
909 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
915 /* Returns the base of the affine function FN. */
918 affine_function_base (affine_fn fn
)
920 return VEC_index (tree
, fn
, 0);
923 /* Returns true if FN is a constant. */
926 affine_function_constant_p (affine_fn fn
)
931 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
932 if (!integer_zerop (coef
))
938 /* Returns true if FN is the zero constant function. */
941 affine_function_zero_p (affine_fn fn
)
943 return (integer_zerop (affine_function_base (fn
))
944 && affine_function_constant_p (fn
));
947 /* Returns a signed integer type with the largest precision from TA
951 signed_type_for_types (tree ta
, tree tb
)
953 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
954 return signed_type_for (ta
);
956 return signed_type_for (tb
);
959 /* Applies operation OP on affine functions FNA and FNB, and returns the
963 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
969 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
971 n
= VEC_length (tree
, fna
);
972 m
= VEC_length (tree
, fnb
);
976 n
= VEC_length (tree
, fnb
);
977 m
= VEC_length (tree
, fna
);
980 ret
= VEC_alloc (tree
, heap
, m
);
981 for (i
= 0; i
< n
; i
++)
983 tree type
= signed_type_for_types (TREE_TYPE (VEC_index (tree
, fna
, i
)),
984 TREE_TYPE (VEC_index (tree
, fnb
, i
)));
986 VEC_quick_push (tree
, ret
,
987 fold_build2 (op
, type
,
988 VEC_index (tree
, fna
, i
),
989 VEC_index (tree
, fnb
, i
)));
992 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
993 VEC_quick_push (tree
, ret
,
994 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
995 coef
, integer_zero_node
));
996 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
997 VEC_quick_push (tree
, ret
,
998 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
999 integer_zero_node
, coef
));
1004 /* Returns the sum of affine functions FNA and FNB. */
1007 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1009 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1012 /* Returns the difference of affine functions FNA and FNB. */
1015 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1017 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1020 /* Frees affine function FN. */
1023 affine_fn_free (affine_fn fn
)
1025 VEC_free (tree
, heap
, fn
);
1028 /* Determine for each subscript in the data dependence relation DDR
1032 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1034 conflict_function
*cf_a
, *cf_b
;
1035 affine_fn fn_a
, fn_b
, diff
;
1037 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1041 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1043 struct subscript
*subscript
;
1045 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1046 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1047 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1049 fn_a
= common_affine_function (cf_a
);
1050 fn_b
= common_affine_function (cf_b
);
1053 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1056 diff
= affine_fn_minus (fn_a
, fn_b
);
1058 if (affine_function_constant_p (diff
))
1059 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1061 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1063 affine_fn_free (diff
);
1068 /* Returns the conflict function for "unknown". */
1070 static conflict_function
*
1071 conflict_fn_not_known (void)
1073 conflict_function
*fn
= XCNEW (conflict_function
);
1079 /* Returns the conflict function for "independent". */
1081 static conflict_function
*
1082 conflict_fn_no_dependence (void)
1084 conflict_function
*fn
= XCNEW (conflict_function
);
1085 fn
->n
= NO_DEPENDENCE
;
1090 /* Returns true if the address of OBJ is invariant in LOOP. */
1093 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1095 while (handled_component_p (obj
))
1097 if (TREE_CODE (obj
) == ARRAY_REF
)
1099 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1100 need to check the stride and the lower bound of the reference. */
1101 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1103 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1107 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1109 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1113 obj
= TREE_OPERAND (obj
, 0);
1116 if (!INDIRECT_REF_P (obj
))
1119 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1123 /* Returns true if A and B are accesses to different objects, or to different
1124 fields of the same object. */
1127 disjoint_objects_p (tree a
, tree b
)
1129 tree base_a
, base_b
;
1130 VEC (tree
, heap
) *comp_a
= NULL
, *comp_b
= NULL
;
1133 base_a
= get_base_address (a
);
1134 base_b
= get_base_address (b
);
1138 && base_a
!= base_b
)
1141 if (!operand_equal_p (base_a
, base_b
, 0))
1144 /* Compare the component references of A and B. We must start from the inner
1145 ones, so record them to the vector first. */
1146 while (handled_component_p (a
))
1148 VEC_safe_push (tree
, heap
, comp_a
, a
);
1149 a
= TREE_OPERAND (a
, 0);
1151 while (handled_component_p (b
))
1153 VEC_safe_push (tree
, heap
, comp_b
, b
);
1154 b
= TREE_OPERAND (b
, 0);
1160 if (VEC_length (tree
, comp_a
) == 0
1161 || VEC_length (tree
, comp_b
) == 0)
1164 a
= VEC_pop (tree
, comp_a
);
1165 b
= VEC_pop (tree
, comp_b
);
1167 /* Real and imaginary part of a variable do not alias. */
1168 if ((TREE_CODE (a
) == REALPART_EXPR
1169 && TREE_CODE (b
) == IMAGPART_EXPR
)
1170 || (TREE_CODE (a
) == IMAGPART_EXPR
1171 && TREE_CODE (b
) == REALPART_EXPR
))
1177 if (TREE_CODE (a
) != TREE_CODE (b
))
1180 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1181 DR_BASE_OBJECT are always zero. */
1182 if (TREE_CODE (a
) == ARRAY_REF
)
1184 else if (TREE_CODE (a
) == COMPONENT_REF
)
1186 if (operand_equal_p (TREE_OPERAND (a
, 1), TREE_OPERAND (b
, 1), 0))
1189 /* Different fields of unions may overlap. */
1190 base_a
= TREE_OPERAND (a
, 0);
1191 if (TREE_CODE (TREE_TYPE (base_a
)) == UNION_TYPE
)
1194 /* Different fields of structures cannot. */
1202 VEC_free (tree
, heap
, comp_a
);
1203 VEC_free (tree
, heap
, comp_b
);
1208 /* Returns false if we can prove that data references A and B do not alias,
1212 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
)
1214 const_tree addr_a
= DR_BASE_ADDRESS (a
);
1215 const_tree addr_b
= DR_BASE_ADDRESS (b
);
1216 const_tree type_a
, type_b
;
1217 const_tree decl_a
= NULL_TREE
, decl_b
= NULL_TREE
;
1219 /* If the accessed objects are disjoint, the memory references do not
1221 if (disjoint_objects_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
)))
1224 /* Query the alias oracle. */
1225 if (!refs_may_alias_p (DR_REF (a
), DR_REF (b
)))
1228 if (!addr_a
|| !addr_b
)
1231 /* If the references are based on different static objects, they cannot
1232 alias (PTA should be able to disambiguate such accesses, but often
1234 if (TREE_CODE (addr_a
) == ADDR_EXPR
1235 && TREE_CODE (addr_b
) == ADDR_EXPR
)
1236 return TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0);
1238 /* An instruction writing through a restricted pointer is "independent" of any
1239 instruction reading or writing through a different restricted pointer,
1240 in the same block/scope. */
1242 type_a
= TREE_TYPE (addr_a
);
1243 type_b
= TREE_TYPE (addr_b
);
1244 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
1246 if (TREE_CODE (addr_a
) == SSA_NAME
)
1247 decl_a
= SSA_NAME_VAR (addr_a
);
1248 if (TREE_CODE (addr_b
) == SSA_NAME
)
1249 decl_b
= SSA_NAME_VAR (addr_b
);
1251 if (TYPE_RESTRICT (type_a
) && TYPE_RESTRICT (type_b
)
1252 && (!DR_IS_READ (a
) || !DR_IS_READ (b
))
1253 && decl_a
&& DECL_P (decl_a
)
1254 && decl_b
&& DECL_P (decl_b
)
1256 && TREE_CODE (DECL_CONTEXT (decl_a
)) == FUNCTION_DECL
1257 && DECL_CONTEXT (decl_a
) == DECL_CONTEXT (decl_b
))
1263 static void compute_self_dependence (struct data_dependence_relation
*);
1265 /* Initialize a data dependence relation between data accesses A and
1266 B. NB_LOOPS is the number of loops surrounding the references: the
1267 size of the classic distance/direction vectors. */
1269 static struct data_dependence_relation
*
1270 initialize_data_dependence_relation (struct data_reference
*a
,
1271 struct data_reference
*b
,
1272 VEC (loop_p
, heap
) *loop_nest
)
1274 struct data_dependence_relation
*res
;
1277 res
= XNEW (struct data_dependence_relation
);
1280 DDR_LOOP_NEST (res
) = NULL
;
1281 DDR_REVERSED_P (res
) = false;
1282 DDR_SUBSCRIPTS (res
) = NULL
;
1283 DDR_DIR_VECTS (res
) = NULL
;
1284 DDR_DIST_VECTS (res
) = NULL
;
1286 if (a
== NULL
|| b
== NULL
)
1288 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1292 /* If the data references do not alias, then they are independent. */
1293 if (!dr_may_alias_p (a
, b
))
1295 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1299 /* When the references are exactly the same, don't spend time doing
1300 the data dependence tests, just initialize the ddr and return. */
1301 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1303 DDR_AFFINE_P (res
) = true;
1304 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1305 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1306 DDR_LOOP_NEST (res
) = loop_nest
;
1307 DDR_INNER_LOOP (res
) = 0;
1308 DDR_SELF_REFERENCE (res
) = true;
1309 compute_self_dependence (res
);
1313 /* If the references do not access the same object, we do not know
1314 whether they alias or not. */
1315 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1317 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1321 /* If the base of the object is not invariant in the loop nest, we cannot
1322 analyze it. TODO -- in fact, it would suffice to record that there may
1323 be arbitrary dependences in the loops where the base object varies. */
1324 if (!object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1325 DR_BASE_OBJECT (a
)))
1327 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1331 gcc_assert (DR_NUM_DIMENSIONS (a
) == DR_NUM_DIMENSIONS (b
));
1333 DDR_AFFINE_P (res
) = true;
1334 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1335 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1336 DDR_LOOP_NEST (res
) = loop_nest
;
1337 DDR_INNER_LOOP (res
) = 0;
1338 DDR_SELF_REFERENCE (res
) = false;
1340 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1342 struct subscript
*subscript
;
1344 subscript
= XNEW (struct subscript
);
1345 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1346 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1347 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1348 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1349 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1355 /* Frees memory used by the conflict function F. */
1358 free_conflict_function (conflict_function
*f
)
1362 if (CF_NONTRIVIAL_P (f
))
1364 for (i
= 0; i
< f
->n
; i
++)
1365 affine_fn_free (f
->fns
[i
]);
1370 /* Frees memory used by SUBSCRIPTS. */
1373 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1378 for (i
= 0; VEC_iterate (subscript_p
, subscripts
, i
, s
); i
++)
1380 free_conflict_function (s
->conflicting_iterations_in_a
);
1381 free_conflict_function (s
->conflicting_iterations_in_b
);
1384 VEC_free (subscript_p
, heap
, subscripts
);
1387 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1391 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1394 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1396 fprintf (dump_file
, "(dependence classified: ");
1397 print_generic_expr (dump_file
, chrec
, 0);
1398 fprintf (dump_file
, ")\n");
1401 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1402 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1403 DDR_SUBSCRIPTS (ddr
) = NULL
;
1406 /* The dependence relation DDR cannot be represented by a distance
1410 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1412 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1413 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1415 DDR_AFFINE_P (ddr
) = false;
1420 /* This section contains the classic Banerjee tests. */
1422 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1423 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1426 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1428 return (evolution_function_is_constant_p (chrec_a
)
1429 && evolution_function_is_constant_p (chrec_b
));
1432 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1433 variable, i.e., if the SIV (Single Index Variable) test is true. */
1436 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1438 if ((evolution_function_is_constant_p (chrec_a
)
1439 && evolution_function_is_univariate_p (chrec_b
))
1440 || (evolution_function_is_constant_p (chrec_b
)
1441 && evolution_function_is_univariate_p (chrec_a
)))
1444 if (evolution_function_is_univariate_p (chrec_a
)
1445 && evolution_function_is_univariate_p (chrec_b
))
1447 switch (TREE_CODE (chrec_a
))
1449 case POLYNOMIAL_CHREC
:
1450 switch (TREE_CODE (chrec_b
))
1452 case POLYNOMIAL_CHREC
:
1453 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1468 /* Creates a conflict function with N dimensions. The affine functions
1469 in each dimension follow. */
1471 static conflict_function
*
1472 conflict_fn (unsigned n
, ...)
1475 conflict_function
*ret
= XCNEW (conflict_function
);
1478 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1482 for (i
= 0; i
< n
; i
++)
1483 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1489 /* Returns constant affine function with value CST. */
1492 affine_fn_cst (tree cst
)
1494 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1495 VEC_quick_push (tree
, fn
, cst
);
1499 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1502 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1504 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1507 gcc_assert (dim
> 0);
1508 VEC_quick_push (tree
, fn
, cst
);
1509 for (i
= 1; i
< dim
; i
++)
1510 VEC_quick_push (tree
, fn
, integer_zero_node
);
1511 VEC_quick_push (tree
, fn
, coef
);
1515 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1516 *OVERLAPS_B are initialized to the functions that describe the
1517 relation between the elements accessed twice by CHREC_A and
1518 CHREC_B. For k >= 0, the following property is verified:
1520 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1523 analyze_ziv_subscript (tree chrec_a
,
1525 conflict_function
**overlaps_a
,
1526 conflict_function
**overlaps_b
,
1527 tree
*last_conflicts
)
1529 tree type
, difference
;
1530 dependence_stats
.num_ziv
++;
1532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1533 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1535 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1536 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1537 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1538 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1540 switch (TREE_CODE (difference
))
1543 if (integer_zerop (difference
))
1545 /* The difference is equal to zero: the accessed index
1546 overlaps for each iteration in the loop. */
1547 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1548 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1549 *last_conflicts
= chrec_dont_know
;
1550 dependence_stats
.num_ziv_dependent
++;
1554 /* The accesses do not overlap. */
1555 *overlaps_a
= conflict_fn_no_dependence ();
1556 *overlaps_b
= conflict_fn_no_dependence ();
1557 *last_conflicts
= integer_zero_node
;
1558 dependence_stats
.num_ziv_independent
++;
1563 /* We're not sure whether the indexes overlap. For the moment,
1564 conservatively answer "don't know". */
1565 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1566 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1568 *overlaps_a
= conflict_fn_not_known ();
1569 *overlaps_b
= conflict_fn_not_known ();
1570 *last_conflicts
= chrec_dont_know
;
1571 dependence_stats
.num_ziv_unimplemented
++;
1575 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1576 fprintf (dump_file
, ")\n");
1579 /* Sets NIT to the estimated number of executions of the statements in
1580 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1581 large as the number of iterations. If we have no reliable estimate,
1582 the function returns false, otherwise returns true. */
1585 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
1588 estimate_numbers_of_iterations_loop (loop
);
1591 if (!loop
->any_upper_bound
)
1594 *nit
= loop
->nb_iterations_upper_bound
;
1598 if (!loop
->any_estimate
)
1601 *nit
= loop
->nb_iterations_estimate
;
1607 /* Similar to estimated_loop_iterations, but returns the estimate only
1608 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1609 on the number of iterations of LOOP could not be derived, returns -1. */
1612 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
1615 HOST_WIDE_INT hwi_nit
;
1617 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1620 if (!double_int_fits_in_shwi_p (nit
))
1622 hwi_nit
= double_int_to_shwi (nit
);
1624 return hwi_nit
< 0 ? -1 : hwi_nit
;
1627 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1628 and only if it fits to the int type. If this is not the case, or the
1629 estimate on the number of iterations of LOOP could not be derived, returns
1633 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
1638 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1639 return chrec_dont_know
;
1641 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
1642 if (!double_int_fits_to_tree_p (type
, nit
))
1643 return chrec_dont_know
;
1645 return double_int_to_tree (type
, nit
);
1648 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1649 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1650 *OVERLAPS_B are initialized to the functions that describe the
1651 relation between the elements accessed twice by CHREC_A and
1652 CHREC_B. For k >= 0, the following property is verified:
1654 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1657 analyze_siv_subscript_cst_affine (tree chrec_a
,
1659 conflict_function
**overlaps_a
,
1660 conflict_function
**overlaps_b
,
1661 tree
*last_conflicts
)
1663 bool value0
, value1
, value2
;
1664 tree type
, difference
, tmp
;
1666 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1667 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1668 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1669 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1671 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1673 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1674 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1676 dependence_stats
.num_siv_unimplemented
++;
1677 *overlaps_a
= conflict_fn_not_known ();
1678 *overlaps_b
= conflict_fn_not_known ();
1679 *last_conflicts
= chrec_dont_know
;
1684 if (value0
== false)
1686 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1688 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1689 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1691 *overlaps_a
= conflict_fn_not_known ();
1692 *overlaps_b
= conflict_fn_not_known ();
1693 *last_conflicts
= chrec_dont_know
;
1694 dependence_stats
.num_siv_unimplemented
++;
1703 chrec_b = {10, +, 1}
1706 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1708 HOST_WIDE_INT numiter
;
1709 struct loop
*loop
= get_chrec_loop (chrec_b
);
1711 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1712 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1713 fold_build1 (ABS_EXPR
, type
, difference
),
1714 CHREC_RIGHT (chrec_b
));
1715 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1716 *last_conflicts
= integer_one_node
;
1719 /* Perform weak-zero siv test to see if overlap is
1720 outside the loop bounds. */
1721 numiter
= estimated_loop_iterations_int (loop
, false);
1724 && compare_tree_int (tmp
, numiter
) > 0)
1726 free_conflict_function (*overlaps_a
);
1727 free_conflict_function (*overlaps_b
);
1728 *overlaps_a
= conflict_fn_no_dependence ();
1729 *overlaps_b
= conflict_fn_no_dependence ();
1730 *last_conflicts
= integer_zero_node
;
1731 dependence_stats
.num_siv_independent
++;
1734 dependence_stats
.num_siv_dependent
++;
1738 /* When the step does not divide the difference, there are
1742 *overlaps_a
= conflict_fn_no_dependence ();
1743 *overlaps_b
= conflict_fn_no_dependence ();
1744 *last_conflicts
= integer_zero_node
;
1745 dependence_stats
.num_siv_independent
++;
1754 chrec_b = {10, +, -1}
1756 In this case, chrec_a will not overlap with chrec_b. */
1757 *overlaps_a
= conflict_fn_no_dependence ();
1758 *overlaps_b
= conflict_fn_no_dependence ();
1759 *last_conflicts
= integer_zero_node
;
1760 dependence_stats
.num_siv_independent
++;
1767 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1770 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1772 *overlaps_a
= conflict_fn_not_known ();
1773 *overlaps_b
= conflict_fn_not_known ();
1774 *last_conflicts
= chrec_dont_know
;
1775 dependence_stats
.num_siv_unimplemented
++;
1780 if (value2
== false)
1784 chrec_b = {10, +, -1}
1786 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1788 HOST_WIDE_INT numiter
;
1789 struct loop
*loop
= get_chrec_loop (chrec_b
);
1791 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1792 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1793 CHREC_RIGHT (chrec_b
));
1794 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1795 *last_conflicts
= integer_one_node
;
1797 /* Perform weak-zero siv test to see if overlap is
1798 outside the loop bounds. */
1799 numiter
= estimated_loop_iterations_int (loop
, false);
1802 && compare_tree_int (tmp
, numiter
) > 0)
1804 free_conflict_function (*overlaps_a
);
1805 free_conflict_function (*overlaps_b
);
1806 *overlaps_a
= conflict_fn_no_dependence ();
1807 *overlaps_b
= conflict_fn_no_dependence ();
1808 *last_conflicts
= integer_zero_node
;
1809 dependence_stats
.num_siv_independent
++;
1812 dependence_stats
.num_siv_dependent
++;
1816 /* When the step does not divide the difference, there
1820 *overlaps_a
= conflict_fn_no_dependence ();
1821 *overlaps_b
= conflict_fn_no_dependence ();
1822 *last_conflicts
= integer_zero_node
;
1823 dependence_stats
.num_siv_independent
++;
1833 In this case, chrec_a will not overlap with chrec_b. */
1834 *overlaps_a
= conflict_fn_no_dependence ();
1835 *overlaps_b
= conflict_fn_no_dependence ();
1836 *last_conflicts
= integer_zero_node
;
1837 dependence_stats
.num_siv_independent
++;
1845 /* Helper recursive function for initializing the matrix A. Returns
1846 the initial value of CHREC. */
1849 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1853 switch (TREE_CODE (chrec
))
1855 case POLYNOMIAL_CHREC
:
1856 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
1858 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1859 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1865 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1866 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
1868 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
1873 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1874 return chrec_convert (chrec_type (chrec
), op
, NULL
);
1879 /* Handle ~X as -1 - X. */
1880 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1881 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
1882 build_int_cst (TREE_TYPE (chrec
), -1), op
);
1894 #define FLOOR_DIV(x,y) ((x) / (y))
1896 /* Solves the special case of the Diophantine equation:
1897 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1899 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1900 number of iterations that loops X and Y run. The overlaps will be
1901 constructed as evolutions in dimension DIM. */
1904 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1905 affine_fn
*overlaps_a
,
1906 affine_fn
*overlaps_b
,
1907 tree
*last_conflicts
, int dim
)
1909 if (((step_a
> 0 && step_b
> 0)
1910 || (step_a
< 0 && step_b
< 0)))
1912 int step_overlaps_a
, step_overlaps_b
;
1913 int gcd_steps_a_b
, last_conflict
, tau2
;
1915 gcd_steps_a_b
= gcd (step_a
, step_b
);
1916 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1917 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1921 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1922 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1923 last_conflict
= tau2
;
1924 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1927 *last_conflicts
= chrec_dont_know
;
1929 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
1930 build_int_cst (NULL_TREE
,
1932 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
1933 build_int_cst (NULL_TREE
,
1939 *overlaps_a
= affine_fn_cst (integer_zero_node
);
1940 *overlaps_b
= affine_fn_cst (integer_zero_node
);
1941 *last_conflicts
= integer_zero_node
;
1945 /* Solves the special case of a Diophantine equation where CHREC_A is
1946 an affine bivariate function, and CHREC_B is an affine univariate
1947 function. For example,
1949 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1951 has the following overlapping functions:
1953 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1954 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1955 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1957 FORNOW: This is a specialized implementation for a case occurring in
1958 a common benchmark. Implement the general algorithm. */
1961 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1962 conflict_function
**overlaps_a
,
1963 conflict_function
**overlaps_b
,
1964 tree
*last_conflicts
)
1966 bool xz_p
, yz_p
, xyz_p
;
1967 int step_x
, step_y
, step_z
;
1968 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
1969 affine_fn overlaps_a_xz
, overlaps_b_xz
;
1970 affine_fn overlaps_a_yz
, overlaps_b_yz
;
1971 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
1972 affine_fn ova1
, ova2
, ovb
;
1973 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
1975 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
1976 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
1977 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
1980 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a
)),
1982 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), false);
1983 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), false);
1985 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
1987 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1988 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
1990 *overlaps_a
= conflict_fn_not_known ();
1991 *overlaps_b
= conflict_fn_not_known ();
1992 *last_conflicts
= chrec_dont_know
;
1996 niter
= MIN (niter_x
, niter_z
);
1997 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2000 &last_conflicts_xz
, 1);
2001 niter
= MIN (niter_y
, niter_z
);
2002 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2005 &last_conflicts_yz
, 2);
2006 niter
= MIN (niter_x
, niter_z
);
2007 niter
= MIN (niter_y
, niter
);
2008 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2011 &last_conflicts_xyz
, 3);
2013 xz_p
= !integer_zerop (last_conflicts_xz
);
2014 yz_p
= !integer_zerop (last_conflicts_yz
);
2015 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2017 if (xz_p
|| yz_p
|| xyz_p
)
2019 ova1
= affine_fn_cst (integer_zero_node
);
2020 ova2
= affine_fn_cst (integer_zero_node
);
2021 ovb
= affine_fn_cst (integer_zero_node
);
2024 affine_fn t0
= ova1
;
2027 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2028 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2029 affine_fn_free (t0
);
2030 affine_fn_free (t2
);
2031 *last_conflicts
= last_conflicts_xz
;
2035 affine_fn t0
= ova2
;
2038 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2039 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2040 affine_fn_free (t0
);
2041 affine_fn_free (t2
);
2042 *last_conflicts
= last_conflicts_yz
;
2046 affine_fn t0
= ova1
;
2047 affine_fn t2
= ova2
;
2050 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2051 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2052 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2053 affine_fn_free (t0
);
2054 affine_fn_free (t2
);
2055 affine_fn_free (t4
);
2056 *last_conflicts
= last_conflicts_xyz
;
2058 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2059 *overlaps_b
= conflict_fn (1, ovb
);
2063 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2064 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2065 *last_conflicts
= integer_zero_node
;
2068 affine_fn_free (overlaps_a_xz
);
2069 affine_fn_free (overlaps_b_xz
);
2070 affine_fn_free (overlaps_a_yz
);
2071 affine_fn_free (overlaps_b_yz
);
2072 affine_fn_free (overlaps_a_xyz
);
2073 affine_fn_free (overlaps_b_xyz
);
2076 /* Determines the overlapping elements due to accesses CHREC_A and
2077 CHREC_B, that are affine functions. This function cannot handle
2078 symbolic evolution functions, ie. when initial conditions are
2079 parameters, because it uses lambda matrices of integers. */
2082 analyze_subscript_affine_affine (tree chrec_a
,
2084 conflict_function
**overlaps_a
,
2085 conflict_function
**overlaps_b
,
2086 tree
*last_conflicts
)
2088 unsigned nb_vars_a
, nb_vars_b
, dim
;
2089 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2090 lambda_matrix A
, U
, S
;
2092 if (eq_evolutions_p (chrec_a
, chrec_b
))
2094 /* The accessed index overlaps for each iteration in the
2096 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2097 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2098 *last_conflicts
= chrec_dont_know
;
2101 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2102 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2104 /* For determining the initial intersection, we have to solve a
2105 Diophantine equation. This is the most time consuming part.
2107 For answering to the question: "Is there a dependence?" we have
2108 to prove that there exists a solution to the Diophantine
2109 equation, and that the solution is in the iteration domain,
2110 i.e. the solution is positive or zero, and that the solution
2111 happens before the upper bound loop.nb_iterations. Otherwise
2112 there is no dependence. This function outputs a description of
2113 the iterations that hold the intersections. */
2115 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2116 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2118 dim
= nb_vars_a
+ nb_vars_b
;
2119 U
= lambda_matrix_new (dim
, dim
);
2120 A
= lambda_matrix_new (dim
, 1);
2121 S
= lambda_matrix_new (dim
, 1);
2123 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2124 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2125 gamma
= init_b
- init_a
;
2127 /* Don't do all the hard work of solving the Diophantine equation
2128 when we already know the solution: for example,
2131 | gamma = 3 - 3 = 0.
2132 Then the first overlap occurs during the first iterations:
2133 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2137 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2139 HOST_WIDE_INT step_a
, step_b
;
2140 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2143 niter_a
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
),
2145 niter_b
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
),
2147 niter
= MIN (niter_a
, niter_b
);
2148 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2149 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2151 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2154 *overlaps_a
= conflict_fn (1, ova
);
2155 *overlaps_b
= conflict_fn (1, ovb
);
2158 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2159 compute_overlap_steps_for_affine_1_2
2160 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2162 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2163 compute_overlap_steps_for_affine_1_2
2164 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2168 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2169 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2170 *overlaps_a
= conflict_fn_not_known ();
2171 *overlaps_b
= conflict_fn_not_known ();
2172 *last_conflicts
= chrec_dont_know
;
2174 goto end_analyze_subs_aa
;
2178 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2183 lambda_matrix_row_negate (U
, dim
, 0);
2185 gcd_alpha_beta
= S
[0][0];
2187 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2188 but that is a quite strange case. Instead of ICEing, answer
2190 if (gcd_alpha_beta
== 0)
2192 *overlaps_a
= conflict_fn_not_known ();
2193 *overlaps_b
= conflict_fn_not_known ();
2194 *last_conflicts
= chrec_dont_know
;
2195 goto end_analyze_subs_aa
;
2198 /* The classic "gcd-test". */
2199 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2201 /* The "gcd-test" has determined that there is no integer
2202 solution, i.e. there is no dependence. */
2203 *overlaps_a
= conflict_fn_no_dependence ();
2204 *overlaps_b
= conflict_fn_no_dependence ();
2205 *last_conflicts
= integer_zero_node
;
2208 /* Both access functions are univariate. This includes SIV and MIV cases. */
2209 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2211 /* Both functions should have the same evolution sign. */
2212 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2213 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2215 /* The solutions are given by:
2217 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2220 For a given integer t. Using the following variables,
2222 | i0 = u11 * gamma / gcd_alpha_beta
2223 | j0 = u12 * gamma / gcd_alpha_beta
2230 | y0 = j0 + j1 * t. */
2231 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2233 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2234 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2238 if ((i1
== 0 && i0
< 0)
2239 || (j1
== 0 && j0
< 0))
2241 /* There is no solution.
2242 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2243 falls in here, but for the moment we don't look at the
2244 upper bound of the iteration domain. */
2245 *overlaps_a
= conflict_fn_no_dependence ();
2246 *overlaps_b
= conflict_fn_no_dependence ();
2247 *last_conflicts
= integer_zero_node
;
2248 goto end_analyze_subs_aa
;
2251 if (i1
> 0 && j1
> 0)
2253 HOST_WIDE_INT niter_a
= estimated_loop_iterations_int
2254 (get_chrec_loop (chrec_a
), false);
2255 HOST_WIDE_INT niter_b
= estimated_loop_iterations_int
2256 (get_chrec_loop (chrec_b
), false);
2257 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2259 /* (X0, Y0) is a solution of the Diophantine equation:
2260 "chrec_a (X0) = chrec_b (Y0)". */
2261 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2263 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2264 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2266 /* (X1, Y1) is the smallest positive solution of the eq
2267 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2268 first conflict occurs. */
2269 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2270 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2271 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2275 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2276 FLOOR_DIV (niter
- j0
, j1
));
2277 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2279 /* If the overlap occurs outside of the bounds of the
2280 loop, there is no dependence. */
2281 if (x1
>= niter
|| y1
>= niter
)
2283 *overlaps_a
= conflict_fn_no_dependence ();
2284 *overlaps_b
= conflict_fn_no_dependence ();
2285 *last_conflicts
= integer_zero_node
;
2286 goto end_analyze_subs_aa
;
2289 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2292 *last_conflicts
= chrec_dont_know
;
2296 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2298 build_int_cst (NULL_TREE
, i1
)));
2301 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2303 build_int_cst (NULL_TREE
, j1
)));
2307 /* FIXME: For the moment, the upper bound of the
2308 iteration domain for i and j is not checked. */
2309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2310 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2311 *overlaps_a
= conflict_fn_not_known ();
2312 *overlaps_b
= conflict_fn_not_known ();
2313 *last_conflicts
= chrec_dont_know
;
2318 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2319 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2320 *overlaps_a
= conflict_fn_not_known ();
2321 *overlaps_b
= conflict_fn_not_known ();
2322 *last_conflicts
= chrec_dont_know
;
2327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2328 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2329 *overlaps_a
= conflict_fn_not_known ();
2330 *overlaps_b
= conflict_fn_not_known ();
2331 *last_conflicts
= chrec_dont_know
;
2334 end_analyze_subs_aa
:
2335 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2337 fprintf (dump_file
, " (overlaps_a = ");
2338 dump_conflict_function (dump_file
, *overlaps_a
);
2339 fprintf (dump_file
, ")\n (overlaps_b = ");
2340 dump_conflict_function (dump_file
, *overlaps_b
);
2341 fprintf (dump_file
, ")\n");
2342 fprintf (dump_file
, ")\n");
2346 /* Returns true when analyze_subscript_affine_affine can be used for
2347 determining the dependence relation between chrec_a and chrec_b,
2348 that contain symbols. This function modifies chrec_a and chrec_b
2349 such that the analysis result is the same, and such that they don't
2350 contain symbols, and then can safely be passed to the analyzer.
2352 Example: The analysis of the following tuples of evolutions produce
2353 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2356 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2357 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2361 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2363 tree diff
, type
, left_a
, left_b
, right_b
;
2365 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2366 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2367 /* FIXME: For the moment not handled. Might be refined later. */
2370 type
= chrec_type (*chrec_a
);
2371 left_a
= CHREC_LEFT (*chrec_a
);
2372 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2373 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2375 if (!evolution_function_is_constant_p (diff
))
2378 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2379 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2381 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2382 diff
, CHREC_RIGHT (*chrec_a
));
2383 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2384 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2385 build_int_cst (type
, 0),
2390 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2391 *OVERLAPS_B are initialized to the functions that describe the
2392 relation between the elements accessed twice by CHREC_A and
2393 CHREC_B. For k >= 0, the following property is verified:
2395 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2398 analyze_siv_subscript (tree chrec_a
,
2400 conflict_function
**overlaps_a
,
2401 conflict_function
**overlaps_b
,
2402 tree
*last_conflicts
,
2405 dependence_stats
.num_siv
++;
2407 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2408 fprintf (dump_file
, "(analyze_siv_subscript \n");
2410 if (evolution_function_is_constant_p (chrec_a
)
2411 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2412 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2413 overlaps_a
, overlaps_b
, last_conflicts
);
2415 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2416 && evolution_function_is_constant_p (chrec_b
))
2417 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2418 overlaps_b
, overlaps_a
, last_conflicts
);
2420 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2421 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2423 if (!chrec_contains_symbols (chrec_a
)
2424 && !chrec_contains_symbols (chrec_b
))
2426 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2427 overlaps_a
, overlaps_b
,
2430 if (CF_NOT_KNOWN_P (*overlaps_a
)
2431 || CF_NOT_KNOWN_P (*overlaps_b
))
2432 dependence_stats
.num_siv_unimplemented
++;
2433 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2434 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2435 dependence_stats
.num_siv_independent
++;
2437 dependence_stats
.num_siv_dependent
++;
2439 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2442 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2443 overlaps_a
, overlaps_b
,
2446 if (CF_NOT_KNOWN_P (*overlaps_a
)
2447 || CF_NOT_KNOWN_P (*overlaps_b
))
2448 dependence_stats
.num_siv_unimplemented
++;
2449 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2450 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2451 dependence_stats
.num_siv_independent
++;
2453 dependence_stats
.num_siv_dependent
++;
2456 goto siv_subscript_dontknow
;
2461 siv_subscript_dontknow
:;
2462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2463 fprintf (dump_file
, "siv test failed: unimplemented.\n");
2464 *overlaps_a
= conflict_fn_not_known ();
2465 *overlaps_b
= conflict_fn_not_known ();
2466 *last_conflicts
= chrec_dont_know
;
2467 dependence_stats
.num_siv_unimplemented
++;
2470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2471 fprintf (dump_file
, ")\n");
2474 /* Returns false if we can prove that the greatest common divisor of the steps
2475 of CHREC does not divide CST, false otherwise. */
2478 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2480 HOST_WIDE_INT cd
= 0, val
;
2483 if (!host_integerp (cst
, 0))
2485 val
= tree_low_cst (cst
, 0);
2487 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2489 step
= CHREC_RIGHT (chrec
);
2490 if (!host_integerp (step
, 0))
2492 cd
= gcd (cd
, tree_low_cst (step
, 0));
2493 chrec
= CHREC_LEFT (chrec
);
2496 return val
% cd
== 0;
2499 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2500 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2501 functions that describe the relation between the elements accessed
2502 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2505 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2508 analyze_miv_subscript (tree chrec_a
,
2510 conflict_function
**overlaps_a
,
2511 conflict_function
**overlaps_b
,
2512 tree
*last_conflicts
,
2513 struct loop
*loop_nest
)
2515 /* FIXME: This is a MIV subscript, not yet handled.
2516 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2519 In the SIV test we had to solve a Diophantine equation with two
2520 variables. In the MIV case we have to solve a Diophantine
2521 equation with 2*n variables (if the subscript uses n IVs).
2523 tree type
, difference
;
2525 dependence_stats
.num_miv
++;
2526 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2527 fprintf (dump_file
, "(analyze_miv_subscript \n");
2529 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2530 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2531 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2532 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2534 if (eq_evolutions_p (chrec_a
, chrec_b
))
2536 /* Access functions are the same: all the elements are accessed
2537 in the same order. */
2538 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2539 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2540 *last_conflicts
= estimated_loop_iterations_tree
2541 (get_chrec_loop (chrec_a
), true);
2542 dependence_stats
.num_miv_dependent
++;
2545 else if (evolution_function_is_constant_p (difference
)
2546 /* For the moment, the following is verified:
2547 evolution_function_is_affine_multivariate_p (chrec_a,
2549 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2551 /* testsuite/.../ssa-chrec-33.c
2552 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2554 The difference is 1, and all the evolution steps are multiples
2555 of 2, consequently there are no overlapping elements. */
2556 *overlaps_a
= conflict_fn_no_dependence ();
2557 *overlaps_b
= conflict_fn_no_dependence ();
2558 *last_conflicts
= integer_zero_node
;
2559 dependence_stats
.num_miv_independent
++;
2562 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2563 && !chrec_contains_symbols (chrec_a
)
2564 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2565 && !chrec_contains_symbols (chrec_b
))
2567 /* testsuite/.../ssa-chrec-35.c
2568 {0, +, 1}_2 vs. {0, +, 1}_3
2569 the overlapping elements are respectively located at iterations:
2570 {0, +, 1}_x and {0, +, 1}_x,
2571 in other words, we have the equality:
2572 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2575 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2576 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2578 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2579 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2581 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2582 overlaps_a
, overlaps_b
, last_conflicts
);
2584 if (CF_NOT_KNOWN_P (*overlaps_a
)
2585 || CF_NOT_KNOWN_P (*overlaps_b
))
2586 dependence_stats
.num_miv_unimplemented
++;
2587 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2588 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2589 dependence_stats
.num_miv_independent
++;
2591 dependence_stats
.num_miv_dependent
++;
2596 /* When the analysis is too difficult, answer "don't know". */
2597 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2598 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2600 *overlaps_a
= conflict_fn_not_known ();
2601 *overlaps_b
= conflict_fn_not_known ();
2602 *last_conflicts
= chrec_dont_know
;
2603 dependence_stats
.num_miv_unimplemented
++;
2606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2607 fprintf (dump_file
, ")\n");
2610 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2611 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2612 OVERLAP_ITERATIONS_B are initialized with two functions that
2613 describe the iterations that contain conflicting elements.
2615 Remark: For an integer k >= 0, the following equality is true:
2617 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2621 analyze_overlapping_iterations (tree chrec_a
,
2623 conflict_function
**overlap_iterations_a
,
2624 conflict_function
**overlap_iterations_b
,
2625 tree
*last_conflicts
, struct loop
*loop_nest
)
2627 unsigned int lnn
= loop_nest
->num
;
2629 dependence_stats
.num_subscript_tests
++;
2631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2633 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2634 fprintf (dump_file
, " (chrec_a = ");
2635 print_generic_expr (dump_file
, chrec_a
, 0);
2636 fprintf (dump_file
, ")\n (chrec_b = ");
2637 print_generic_expr (dump_file
, chrec_b
, 0);
2638 fprintf (dump_file
, ")\n");
2641 if (chrec_a
== NULL_TREE
2642 || chrec_b
== NULL_TREE
2643 || chrec_contains_undetermined (chrec_a
)
2644 || chrec_contains_undetermined (chrec_b
))
2646 dependence_stats
.num_subscript_undetermined
++;
2648 *overlap_iterations_a
= conflict_fn_not_known ();
2649 *overlap_iterations_b
= conflict_fn_not_known ();
2652 /* If they are the same chrec, and are affine, they overlap
2653 on every iteration. */
2654 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2655 && evolution_function_is_affine_multivariate_p (chrec_a
, lnn
))
2657 dependence_stats
.num_same_subscript_function
++;
2658 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2659 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2660 *last_conflicts
= chrec_dont_know
;
2663 /* If they aren't the same, and aren't affine, we can't do anything
2665 else if ((chrec_contains_symbols (chrec_a
)
2666 || chrec_contains_symbols (chrec_b
))
2667 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2668 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2670 dependence_stats
.num_subscript_undetermined
++;
2671 *overlap_iterations_a
= conflict_fn_not_known ();
2672 *overlap_iterations_b
= conflict_fn_not_known ();
2675 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2676 analyze_ziv_subscript (chrec_a
, chrec_b
,
2677 overlap_iterations_a
, overlap_iterations_b
,
2680 else if (siv_subscript_p (chrec_a
, chrec_b
))
2681 analyze_siv_subscript (chrec_a
, chrec_b
,
2682 overlap_iterations_a
, overlap_iterations_b
,
2683 last_conflicts
, lnn
);
2686 analyze_miv_subscript (chrec_a
, chrec_b
,
2687 overlap_iterations_a
, overlap_iterations_b
,
2688 last_conflicts
, loop_nest
);
2690 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2692 fprintf (dump_file
, " (overlap_iterations_a = ");
2693 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2694 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2695 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2696 fprintf (dump_file
, ")\n");
2697 fprintf (dump_file
, ")\n");
2701 /* Helper function for uniquely inserting distance vectors. */
2704 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2709 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
2710 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2713 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2716 /* Helper function for uniquely inserting direction vectors. */
2719 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2724 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
2725 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2728 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2731 /* Add a distance of 1 on all the loops outer than INDEX. If we
2732 haven't yet determined a distance for this outer loop, push a new
2733 distance vector composed of the previous distance, and a distance
2734 of 1 for this outer loop. Example:
2742 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2743 save (0, 1), then we have to save (1, 0). */
2746 add_outer_distances (struct data_dependence_relation
*ddr
,
2747 lambda_vector dist_v
, int index
)
2749 /* For each outer loop where init_v is not set, the accesses are
2750 in dependence of distance 1 in the loop. */
2751 while (--index
>= 0)
2753 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2754 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2756 save_dist_v (ddr
, save_v
);
2760 /* Return false when fail to represent the data dependence as a
2761 distance vector. INIT_B is set to true when a component has been
2762 added to the distance vector DIST_V. INDEX_CARRY is then set to
2763 the index in DIST_V that carries the dependence. */
2766 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2767 struct data_reference
*ddr_a
,
2768 struct data_reference
*ddr_b
,
2769 lambda_vector dist_v
, bool *init_b
,
2773 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2775 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2777 tree access_fn_a
, access_fn_b
;
2778 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2780 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2782 non_affine_dependence_relation (ddr
);
2786 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2787 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2789 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2790 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2793 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2794 DDR_LOOP_NEST (ddr
));
2795 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2796 DDR_LOOP_NEST (ddr
));
2798 /* The dependence is carried by the outermost loop. Example:
2805 In this case, the dependence is carried by loop_1. */
2806 index
= index_a
< index_b
? index_a
: index_b
;
2807 *index_carry
= MIN (index
, *index_carry
);
2809 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2811 non_affine_dependence_relation (ddr
);
2815 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2817 /* This is the subscript coupling test. If we have already
2818 recorded a distance for this loop (a distance coming from
2819 another subscript), it should be the same. For example,
2820 in the following code, there is no dependence:
2827 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2829 finalize_ddr_dependent (ddr
, chrec_known
);
2833 dist_v
[index
] = dist
;
2837 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2839 /* This can be for example an affine vs. constant dependence
2840 (T[i] vs. T[3]) that is not an affine dependence and is
2841 not representable as a distance vector. */
2842 non_affine_dependence_relation (ddr
);
2850 /* Return true when the DDR contains only constant access functions. */
2853 constant_access_functions (const struct data_dependence_relation
*ddr
)
2857 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2858 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2859 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2865 /* Helper function for the case where DDR_A and DDR_B are the same
2866 multivariate access function with a constant step. For an example
2870 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2873 tree c_1
= CHREC_LEFT (c_2
);
2874 tree c_0
= CHREC_LEFT (c_1
);
2875 lambda_vector dist_v
;
2878 /* Polynomials with more than 2 variables are not handled yet. When
2879 the evolution steps are parameters, it is not possible to
2880 represent the dependence using classical distance vectors. */
2881 if (TREE_CODE (c_0
) != INTEGER_CST
2882 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
2883 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
2885 DDR_AFFINE_P (ddr
) = false;
2889 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2890 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2892 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2893 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2894 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2895 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2908 save_dist_v (ddr
, dist_v
);
2910 add_outer_distances (ddr
, dist_v
, x_1
);
2913 /* Helper function for the case where DDR_A and DDR_B are the same
2914 access functions. */
2917 add_other_self_distances (struct data_dependence_relation
*ddr
)
2919 lambda_vector dist_v
;
2921 int index_carry
= DDR_NB_LOOPS (ddr
);
2923 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2925 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
2927 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
2929 if (!evolution_function_is_univariate_p (access_fun
))
2931 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
2933 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2937 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
2939 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
2940 add_multivariate_self_dist (ddr
, access_fun
);
2942 /* The evolution step is not constant: it varies in
2943 the outer loop, so this cannot be represented by a
2944 distance vector. For example in pr34635.c the
2945 evolution is {0, +, {0, +, 4}_1}_2. */
2946 DDR_AFFINE_P (ddr
) = false;
2951 index_carry
= MIN (index_carry
,
2952 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
2953 DDR_LOOP_NEST (ddr
)));
2957 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2958 add_outer_distances (ddr
, dist_v
, index_carry
);
2962 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
2964 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2966 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
2967 save_dist_v (ddr
, dist_v
);
2970 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2971 is the case for example when access functions are the same and
2972 equal to a constant, as in:
2979 in which case the distance vectors are (0) and (1). */
2982 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
2986 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2988 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
2989 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
2990 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
2992 for (j
= 0; j
< ca
->n
; j
++)
2993 if (affine_function_zero_p (ca
->fns
[j
]))
2995 insert_innermost_unit_dist_vector (ddr
);
2999 for (j
= 0; j
< cb
->n
; j
++)
3000 if (affine_function_zero_p (cb
->fns
[j
]))
3002 insert_innermost_unit_dist_vector (ddr
);
3008 /* Compute the classic per loop distance vector. DDR is the data
3009 dependence relation to build a vector from. Return false when fail
3010 to represent the data dependence as a distance vector. */
3013 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3014 struct loop
*loop_nest
)
3016 bool init_b
= false;
3017 int index_carry
= DDR_NB_LOOPS (ddr
);
3018 lambda_vector dist_v
;
3020 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3023 if (same_access_functions (ddr
))
3025 /* Save the 0 vector. */
3026 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3027 save_dist_v (ddr
, dist_v
);
3029 if (constant_access_functions (ddr
))
3030 add_distance_for_zero_overlaps (ddr
);
3032 if (DDR_NB_LOOPS (ddr
) > 1)
3033 add_other_self_distances (ddr
);
3038 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3039 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3040 dist_v
, &init_b
, &index_carry
))
3043 /* Save the distance vector if we initialized one. */
3046 /* Verify a basic constraint: classic distance vectors should
3047 always be lexicographically positive.
3049 Data references are collected in the order of execution of
3050 the program, thus for the following loop
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
3059 references are collected following the direction of the wind:
3060 A then B. The data dependence tests are performed also
3061 following this order, such that we're looking at the distance
3062 separating the elements accessed by A from the elements later
3063 accessed by B. But in this example, the distance returned by
3064 test_dep (A, B) is lexicographically negative (-1, 1), that
3065 means that the access A occurs later than B with respect to
3066 the outer loop, ie. we're actually looking upwind. In this
3067 case we solve test_dep (B, A) looking downwind to the
3068 lexicographically positive solution, that returns the
3069 distance vector (1, -1). */
3070 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3072 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3073 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3076 compute_subscript_distance (ddr
);
3077 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3078 save_v
, &init_b
, &index_carry
))
3080 save_dist_v (ddr
, save_v
);
3081 DDR_REVERSED_P (ddr
) = true;
3083 /* In this case there is a dependence forward for all the
3086 | for (k = 1; k < 100; k++)
3087 | for (i = 1; i < 100; i++)
3088 | for (j = 1; j < 100; j++)
3090 | t = T[j+1][i-1]; // A
3091 | T[j][i] = t + 2; // B
3099 if (DDR_NB_LOOPS (ddr
) > 1)
3101 add_outer_distances (ddr
, save_v
, index_carry
);
3102 add_outer_distances (ddr
, dist_v
, index_carry
);
3107 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3108 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3110 if (DDR_NB_LOOPS (ddr
) > 1)
3112 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3114 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3115 DDR_A (ddr
), loop_nest
))
3117 compute_subscript_distance (ddr
);
3118 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3119 opposite_v
, &init_b
,
3123 save_dist_v (ddr
, save_v
);
3124 add_outer_distances (ddr
, dist_v
, index_carry
);
3125 add_outer_distances (ddr
, opposite_v
, index_carry
);
3128 save_dist_v (ddr
, save_v
);
3133 /* There is a distance of 1 on all the outer loops: Example:
3134 there is a dependence of distance 1 on loop_1 for the array A.
3140 add_outer_distances (ddr
, dist_v
,
3141 lambda_vector_first_nz (dist_v
,
3142 DDR_NB_LOOPS (ddr
), 0));
3145 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3149 fprintf (dump_file
, "(build_classic_dist_vector\n");
3150 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3152 fprintf (dump_file
, " dist_vector = (");
3153 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3154 DDR_NB_LOOPS (ddr
));
3155 fprintf (dump_file
, " )\n");
3157 fprintf (dump_file
, ")\n");
3163 /* Return the direction for a given distance.
3164 FIXME: Computing dir this way is suboptimal, since dir can catch
3165 cases that dist is unable to represent. */
3167 static inline enum data_dependence_direction
3168 dir_from_dist (int dist
)
3171 return dir_positive
;
3173 return dir_negative
;
3178 /* Compute the classic per loop direction vector. DDR is the data
3179 dependence relation to build a vector from. */
3182 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3185 lambda_vector dist_v
;
3187 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3189 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3191 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3192 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3194 save_dir_v (ddr
, dir_v
);
3198 /* Helper function. Returns true when there is a dependence between
3199 data references DRA and DRB. */
3202 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3203 struct data_reference
*dra
,
3204 struct data_reference
*drb
,
3205 struct loop
*loop_nest
)
3208 tree last_conflicts
;
3209 struct subscript
*subscript
;
3211 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3214 conflict_function
*overlaps_a
, *overlaps_b
;
3216 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3217 DR_ACCESS_FN (drb
, i
),
3218 &overlaps_a
, &overlaps_b
,
3219 &last_conflicts
, loop_nest
);
3221 if (CF_NOT_KNOWN_P (overlaps_a
)
3222 || CF_NOT_KNOWN_P (overlaps_b
))
3224 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3225 dependence_stats
.num_dependence_undetermined
++;
3226 free_conflict_function (overlaps_a
);
3227 free_conflict_function (overlaps_b
);
3231 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3232 || CF_NO_DEPENDENCE_P (overlaps_b
))
3234 finalize_ddr_dependent (ddr
, chrec_known
);
3235 dependence_stats
.num_dependence_independent
++;
3236 free_conflict_function (overlaps_a
);
3237 free_conflict_function (overlaps_b
);
3243 if (SUB_CONFLICTS_IN_A (subscript
))
3244 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3245 if (SUB_CONFLICTS_IN_B (subscript
))
3246 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3248 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3249 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3250 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3257 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3260 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3261 struct loop
*loop_nest
)
3264 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3265 fprintf (dump_file
, "(subscript_dependence_tester \n");
3267 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3268 dependence_stats
.num_dependence_dependent
++;
3270 compute_subscript_distance (ddr
);
3271 if (build_classic_dist_vector (ddr
, loop_nest
))
3272 build_classic_dir_vector (ddr
);
3274 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3275 fprintf (dump_file
, ")\n");
3278 /* Returns true when all the access functions of A are affine or
3279 constant with respect to LOOP_NEST. */
3282 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3283 const struct loop
*loop_nest
)
3286 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3289 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
3290 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3291 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3297 /* Return true if we can create an affine data-ref for OP in STMT. */
3300 stmt_simple_memref_p (struct loop
*loop
, gimple stmt
, tree op
)
3302 data_reference_p dr
;
3305 dr
= create_data_ref (loop
, op
, stmt
, true);
3306 if (!access_functions_are_affine_or_constant_p (dr
, loop
))
3313 /* Initializes an equation for an OMEGA problem using the information
3314 contained in the ACCESS_FUN. Returns true when the operation
3317 PB is the omega constraint system.
3318 EQ is the number of the equation to be initialized.
3319 OFFSET is used for shifting the variables names in the constraints:
3320 a constrain is composed of 2 * the number of variables surrounding
3321 dependence accesses. OFFSET is set either to 0 for the first n variables,
3322 then it is set to n.
3323 ACCESS_FUN is expected to be an affine chrec. */
3326 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3327 unsigned int offset
, tree access_fun
,
3328 struct data_dependence_relation
*ddr
)
3330 switch (TREE_CODE (access_fun
))
3332 case POLYNOMIAL_CHREC
:
3334 tree left
= CHREC_LEFT (access_fun
);
3335 tree right
= CHREC_RIGHT (access_fun
);
3336 int var
= CHREC_VARIABLE (access_fun
);
3339 if (TREE_CODE (right
) != INTEGER_CST
)
3342 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3343 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3345 /* Compute the innermost loop index. */
3346 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3349 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3350 += int_cst_value (right
);
3352 switch (TREE_CODE (left
))
3354 case POLYNOMIAL_CHREC
:
3355 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3358 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3367 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3375 /* As explained in the comments preceding init_omega_for_ddr, we have
3376 to set up a system for each loop level, setting outer loops
3377 variation to zero, and current loop variation to positive or zero.
3378 Save each lexico positive distance vector. */
3381 omega_extract_distance_vectors (omega_pb pb
,
3382 struct data_dependence_relation
*ddr
)
3386 struct loop
*loopi
, *loopj
;
3387 enum omega_result res
;
3389 /* Set a new problem for each loop in the nest. The basis is the
3390 problem that we have initialized until now. On top of this we
3391 add new constraints. */
3392 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3393 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3396 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3397 DDR_NB_LOOPS (ddr
));
3399 omega_copy_problem (copy
, pb
);
3401 /* For all the outer loops "loop_j", add "dj = 0". */
3403 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3405 eq
= omega_add_zero_eq (copy
, omega_black
);
3406 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3409 /* For "loop_i", add "0 <= di". */
3410 geq
= omega_add_zero_geq (copy
, omega_black
);
3411 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3413 /* Reduce the constraint system, and test that the current
3414 problem is feasible. */
3415 res
= omega_simplify_problem (copy
);
3416 if (res
== omega_false
3417 || res
== omega_unknown
3418 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3421 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3422 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3424 dist
= copy
->subs
[eq
].coef
[0];
3430 /* Reinitialize problem... */
3431 omega_copy_problem (copy
, pb
);
3433 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3435 eq
= omega_add_zero_eq (copy
, omega_black
);
3436 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3439 /* ..., but this time "di = 1". */
3440 eq
= omega_add_zero_eq (copy
, omega_black
);
3441 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3442 copy
->eqs
[eq
].coef
[0] = -1;
3444 res
= omega_simplify_problem (copy
);
3445 if (res
== omega_false
3446 || res
== omega_unknown
3447 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3450 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3451 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3453 dist
= copy
->subs
[eq
].coef
[0];
3459 /* Save the lexicographically positive distance vector. */
3462 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3463 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3467 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3468 if (copy
->subs
[eq
].key
> 0)
3470 dist
= copy
->subs
[eq
].coef
[0];
3471 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3474 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3475 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3477 save_dist_v (ddr
, dist_v
);
3478 save_dir_v (ddr
, dir_v
);
3482 omega_free_problem (copy
);
3486 /* This is called for each subscript of a tuple of data references:
3487 insert an equality for representing the conflicts. */
3490 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3491 struct data_dependence_relation
*ddr
,
3492 omega_pb pb
, bool *maybe_dependent
)
3495 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3496 TREE_TYPE (access_fun_b
));
3497 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3498 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3499 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3501 /* When the fun_a - fun_b is not constant, the dependence is not
3502 captured by the classic distance vector representation. */
3503 if (TREE_CODE (difference
) != INTEGER_CST
)
3507 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3509 /* There is no dependence. */
3510 *maybe_dependent
= false;
3514 fun_b
= chrec_fold_multiply (type
, fun_b
, integer_minus_one_node
);
3516 eq
= omega_add_zero_eq (pb
, omega_black
);
3517 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3518 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3519 /* There is probably a dependence, but the system of
3520 constraints cannot be built: answer "don't know". */
3524 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3525 && !int_divides_p (lambda_vector_gcd
3526 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3527 2 * DDR_NB_LOOPS (ddr
)),
3528 pb
->eqs
[eq
].coef
[0]))
3530 /* There is no dependence. */
3531 *maybe_dependent
= false;
3538 /* Helper function, same as init_omega_for_ddr but specialized for
3539 data references A and B. */
3542 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3543 struct data_dependence_relation
*ddr
,
3544 omega_pb pb
, bool *maybe_dependent
)
3549 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3551 /* Insert an equality per subscript. */
3552 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3554 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3555 ddr
, pb
, maybe_dependent
))
3557 else if (*maybe_dependent
== false)
3559 /* There is no dependence. */
3560 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3565 /* Insert inequalities: constraints corresponding to the iteration
3566 domain, i.e. the loops surrounding the references "loop_x" and
3567 the distance variables "dx". The layout of the OMEGA
3568 representation is as follows:
3569 - coef[0] is the constant
3570 - coef[1..nb_loops] are the protected variables that will not be
3571 removed by the solver: the "dx"
3572 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3574 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3575 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3577 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3580 ineq
= omega_add_zero_geq (pb
, omega_black
);
3581 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3583 /* 0 <= loop_x + dx */
3584 ineq
= omega_add_zero_geq (pb
, omega_black
);
3585 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3586 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3590 /* loop_x <= nb_iters */
3591 ineq
= omega_add_zero_geq (pb
, omega_black
);
3592 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3593 pb
->geqs
[ineq
].coef
[0] = nbi
;
3595 /* loop_x + dx <= nb_iters */
3596 ineq
= omega_add_zero_geq (pb
, omega_black
);
3597 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3598 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3599 pb
->geqs
[ineq
].coef
[0] = nbi
;
3601 /* A step "dx" bigger than nb_iters is not feasible, so
3602 add "0 <= nb_iters + dx", */
3603 ineq
= omega_add_zero_geq (pb
, omega_black
);
3604 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3605 pb
->geqs
[ineq
].coef
[0] = nbi
;
3606 /* and "dx <= nb_iters". */
3607 ineq
= omega_add_zero_geq (pb
, omega_black
);
3608 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3609 pb
->geqs
[ineq
].coef
[0] = nbi
;
3613 omega_extract_distance_vectors (pb
, ddr
);
3618 /* Sets up the Omega dependence problem for the data dependence
3619 relation DDR. Returns false when the constraint system cannot be
3620 built, ie. when the test answers "don't know". Returns true
3621 otherwise, and when independence has been proved (using one of the
3622 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3623 set MAYBE_DEPENDENT to true.
3625 Example: for setting up the dependence system corresponding to the
3626 conflicting accesses
3631 | ... A[2*j, 2*(i + j)]
3635 the following constraints come from the iteration domain:
3642 where di, dj are the distance variables. The constraints
3643 representing the conflicting elements are:
3646 i + 1 = 2 * (i + di + j + dj)
3648 For asking that the resulting distance vector (di, dj) be
3649 lexicographically positive, we insert the constraint "di >= 0". If
3650 "di = 0" in the solution, we fix that component to zero, and we
3651 look at the inner loops: we set a new problem where all the outer
3652 loop distances are zero, and fix this inner component to be
3653 positive. When one of the components is positive, we save that
3654 distance, and set a new problem where the distance on this loop is
3655 zero, searching for other distances in the inner loops. Here is
3656 the classic example that illustrates that we have to set for each
3657 inner loop a new problem:
3665 we have to save two distances (1, 0) and (0, 1).
3667 Given two array references, refA and refB, we have to set the
3668 dependence problem twice, refA vs. refB and refB vs. refA, and we
3669 cannot do a single test, as refB might occur before refA in the
3670 inner loops, and the contrary when considering outer loops: ex.
3675 | T[{1,+,1}_2][{1,+,1}_1] // refA
3676 | T[{2,+,1}_2][{0,+,1}_1] // refB
3681 refB touches the elements in T before refA, and thus for the same
3682 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3683 but for successive loop_0 iterations, we have (1, -1, 1)
3685 The Omega solver expects the distance variables ("di" in the
3686 previous example) to come first in the constraint system (as
3687 variables to be protected, or "safe" variables), the constraint
3688 system is built using the following layout:
3690 "cst | distance vars | index vars".
3694 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3695 bool *maybe_dependent
)
3700 *maybe_dependent
= true;
3702 if (same_access_functions (ddr
))
3705 lambda_vector dir_v
;
3707 /* Save the 0 vector. */
3708 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3709 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3710 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3711 dir_v
[j
] = dir_equal
;
3712 save_dir_v (ddr
, dir_v
);
3714 /* Save the dependences carried by outer loops. */
3715 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3716 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3718 omega_free_problem (pb
);
3722 /* Omega expects the protected variables (those that have to be kept
3723 after elimination) to appear first in the constraint system.
3724 These variables are the distance variables. In the following
3725 initialization we declare NB_LOOPS safe variables, and the total
3726 number of variables for the constraint system is 2*NB_LOOPS. */
3727 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3728 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3730 omega_free_problem (pb
);
3732 /* Stop computation if not decidable, or no dependence. */
3733 if (res
== false || *maybe_dependent
== false)
3736 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3737 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3739 omega_free_problem (pb
);
3744 /* Return true when DDR contains the same information as that stored
3745 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3748 ddr_consistent_p (FILE *file
,
3749 struct data_dependence_relation
*ddr
,
3750 VEC (lambda_vector
, heap
) *dist_vects
,
3751 VEC (lambda_vector
, heap
) *dir_vects
)
3755 /* If dump_file is set, output there. */
3756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3759 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3761 lambda_vector b_dist_v
;
3762 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3763 VEC_length (lambda_vector
, dist_vects
),
3764 DDR_NUM_DIST_VECTS (ddr
));
3766 fprintf (file
, "Banerjee dist vectors:\n");
3767 for (i
= 0; VEC_iterate (lambda_vector
, dist_vects
, i
, b_dist_v
); i
++)
3768 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3770 fprintf (file
, "Omega dist vectors:\n");
3771 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3772 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3774 fprintf (file
, "data dependence relation:\n");
3775 dump_data_dependence_relation (file
, ddr
);
3777 fprintf (file
, ")\n");
3781 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3783 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3784 VEC_length (lambda_vector
, dir_vects
),
3785 DDR_NUM_DIR_VECTS (ddr
));
3789 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3791 lambda_vector a_dist_v
;
3792 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3794 /* Distance vectors are not ordered in the same way in the DDR
3795 and in the DIST_VECTS: search for a matching vector. */
3796 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, a_dist_v
); j
++)
3797 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3800 if (j
== VEC_length (lambda_vector
, dist_vects
))
3802 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3803 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3804 fprintf (file
, "not found in Omega dist vectors:\n");
3805 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3806 fprintf (file
, "data dependence relation:\n");
3807 dump_data_dependence_relation (file
, ddr
);
3808 fprintf (file
, ")\n");
3812 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3814 lambda_vector a_dir_v
;
3815 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3817 /* Direction vectors are not ordered in the same way in the DDR
3818 and in the DIR_VECTS: search for a matching vector. */
3819 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, a_dir_v
); j
++)
3820 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3823 if (j
== VEC_length (lambda_vector
, dist_vects
))
3825 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3826 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3827 fprintf (file
, "not found in Omega dir vectors:\n");
3828 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3829 fprintf (file
, "data dependence relation:\n");
3830 dump_data_dependence_relation (file
, ddr
);
3831 fprintf (file
, ")\n");
3838 /* This computes the affine dependence relation between A and B with
3839 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3840 independence between two accesses, while CHREC_DONT_KNOW is used
3841 for representing the unknown relation.
3843 Note that it is possible to stop the computation of the dependence
3844 relation the first time we detect a CHREC_KNOWN element for a given
3848 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3849 struct loop
*loop_nest
)
3851 struct data_reference
*dra
= DDR_A (ddr
);
3852 struct data_reference
*drb
= DDR_B (ddr
);
3854 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3856 fprintf (dump_file
, "(compute_affine_dependence\n");
3857 fprintf (dump_file
, " (stmt_a = \n");
3858 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, 0);
3859 fprintf (dump_file
, ")\n (stmt_b = \n");
3860 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, 0);
3861 fprintf (dump_file
, ")\n");
3864 /* Analyze only when the dependence relation is not yet known. */
3865 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
3866 && !DDR_SELF_REFERENCE (ddr
))
3868 dependence_stats
.num_dependence_tests
++;
3870 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3871 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3873 if (flag_check_data_deps
)
3875 /* Compute the dependences using the first algorithm. */
3876 subscript_dependence_tester (ddr
, loop_nest
);
3878 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3880 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3881 dump_data_dependence_relation (dump_file
, ddr
);
3884 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3886 bool maybe_dependent
;
3887 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3889 /* Save the result of the first DD analyzer. */
3890 dist_vects
= DDR_DIST_VECTS (ddr
);
3891 dir_vects
= DDR_DIR_VECTS (ddr
);
3893 /* Reset the information. */
3894 DDR_DIST_VECTS (ddr
) = NULL
;
3895 DDR_DIR_VECTS (ddr
) = NULL
;
3897 /* Compute the same information using Omega. */
3898 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3899 goto csys_dont_know
;
3901 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3903 fprintf (dump_file
, "Omega Analyzer\n");
3904 dump_data_dependence_relation (dump_file
, ddr
);
3907 /* Check that we get the same information. */
3908 if (maybe_dependent
)
3909 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3914 subscript_dependence_tester (ddr
, loop_nest
);
3917 /* As a last case, if the dependence cannot be determined, or if
3918 the dependence is considered too difficult to determine, answer
3923 dependence_stats
.num_dependence_undetermined
++;
3925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3927 fprintf (dump_file
, "Data ref a:\n");
3928 dump_data_reference (dump_file
, dra
);
3929 fprintf (dump_file
, "Data ref b:\n");
3930 dump_data_reference (dump_file
, drb
);
3931 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3933 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3937 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3938 fprintf (dump_file
, ")\n");
3941 /* This computes the dependence relation for the same data
3942 reference into DDR. */
3945 compute_self_dependence (struct data_dependence_relation
*ddr
)
3948 struct subscript
*subscript
;
3950 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3953 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3956 if (SUB_CONFLICTS_IN_A (subscript
))
3957 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3958 if (SUB_CONFLICTS_IN_B (subscript
))
3959 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3961 /* The accessed index overlaps for each iteration. */
3962 SUB_CONFLICTS_IN_A (subscript
)
3963 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3964 SUB_CONFLICTS_IN_B (subscript
)
3965 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3966 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3969 /* The distance vector is the zero vector. */
3970 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3971 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3974 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3975 the data references in DATAREFS, in the LOOP_NEST. When
3976 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3980 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
3981 VEC (ddr_p
, heap
) **dependence_relations
,
3982 VEC (loop_p
, heap
) *loop_nest
,
3983 bool compute_self_and_rr
)
3985 struct data_dependence_relation
*ddr
;
3986 struct data_reference
*a
, *b
;
3989 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
3990 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
3991 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
3993 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
3994 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3995 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
3998 if (compute_self_and_rr
)
3999 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4001 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4002 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4003 compute_self_dependence (ddr
);
4007 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4008 true if STMT clobbers memory, false otherwise. */
4011 get_references_in_stmt (gimple stmt
, VEC (data_ref_loc
, heap
) **references
)
4013 bool clobbers_memory
= false;
4016 enum gimple_code stmt_code
= gimple_code (stmt
);
4020 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4021 Calls have side-effects, except those to const or pure
4023 if ((stmt_code
== GIMPLE_CALL
4024 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4025 || (stmt_code
== GIMPLE_ASM
4026 && gimple_asm_volatile_p (stmt
)))
4027 clobbers_memory
= true;
4029 if (!gimple_vuse (stmt
))
4030 return clobbers_memory
;
4032 if (stmt_code
== GIMPLE_ASSIGN
)
4035 op0
= gimple_assign_lhs_ptr (stmt
);
4036 op1
= gimple_assign_rhs1_ptr (stmt
);
4039 || (REFERENCE_CLASS_P (*op1
)
4040 && (base
= get_base_address (*op1
))
4041 && TREE_CODE (base
) != SSA_NAME
))
4043 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4045 ref
->is_read
= true;
4049 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4051 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4053 ref
->is_read
= false;
4056 else if (stmt_code
== GIMPLE_CALL
)
4058 unsigned i
, n
= gimple_call_num_args (stmt
);
4060 for (i
= 0; i
< n
; i
++)
4062 op0
= gimple_call_arg_ptr (stmt
, i
);
4065 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4067 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4069 ref
->is_read
= true;
4074 return clobbers_memory
;
4077 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4078 reference, returns false, otherwise returns true. NEST is the outermost
4079 loop of the loop nest in which the references should be analyzed. */
4082 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4083 VEC (data_reference_p
, heap
) **datarefs
)
4086 VEC (data_ref_loc
, heap
) *references
;
4089 data_reference_p dr
;
4091 if (get_references_in_stmt (stmt
, &references
))
4093 VEC_free (data_ref_loc
, heap
, references
);
4097 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
4099 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4100 gcc_assert (dr
!= NULL
);
4102 /* FIXME -- data dependence analysis does not work correctly for objects with
4103 invariant addresses. Let us fail here until the problem is fixed. */
4104 if (dr_address_invariant_p (dr
))
4107 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4108 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
4113 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4115 VEC_free (data_ref_loc
, heap
, references
);
4119 /* Search the data references in LOOP, and record the information into
4120 DATAREFS. Returns chrec_dont_know when failing to analyze a
4121 difficult case, returns NULL_TREE otherwise.
4123 TODO: This function should be made smarter so that it can handle address
4124 arithmetic as if they were array accesses, etc. */
4127 find_data_references_in_loop (struct loop
*loop
,
4128 VEC (data_reference_p
, heap
) **datarefs
)
4130 basic_block bb
, *bbs
;
4132 gimple_stmt_iterator bsi
;
4134 bbs
= get_loop_body_in_dom_order (loop
);
4136 for (i
= 0; i
< loop
->num_nodes
; i
++)
4140 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4142 gimple stmt
= gsi_stmt (bsi
);
4144 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4146 struct data_reference
*res
;
4147 res
= XCNEW (struct data_reference
);
4148 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4151 return chrec_dont_know
;
4160 /* Recursive helper function. */
4163 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4165 /* Inner loops of the nest should not contain siblings. Example:
4166 when there are two consecutive loops,
4177 the dependence relation cannot be captured by the distance
4182 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4184 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4188 /* Return false when the LOOP is not well nested. Otherwise return
4189 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4190 contain the loops from the outermost to the innermost, as they will
4191 appear in the classic distance vector. */
4194 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4196 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4198 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4202 /* Returns true when the data dependences have been computed, false otherwise.
4203 Given a loop nest LOOP, the following vectors are returned:
4204 DATAREFS is initialized to all the array elements contained in this loop,
4205 DEPENDENCE_RELATIONS contains the relations between the data references.
4206 Compute read-read and self relations if
4207 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4210 compute_data_dependences_for_loop (struct loop
*loop
,
4211 bool compute_self_and_read_read_dependences
,
4212 VEC (data_reference_p
, heap
) **datarefs
,
4213 VEC (ddr_p
, heap
) **dependence_relations
)
4216 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4218 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4220 /* If the loop nest is not well formed, or one of the data references
4221 is not computable, give up without spending time to compute other
4224 || !find_loop_nest (loop
, &vloops
)
4225 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4227 struct data_dependence_relation
*ddr
;
4229 /* Insert a single relation into dependence_relations:
4231 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4232 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4236 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4237 compute_self_and_read_read_dependences
);
4239 if (dump_file
&& (dump_flags
& TDF_STATS
))
4241 fprintf (dump_file
, "Dependence tester statistics:\n");
4243 fprintf (dump_file
, "Number of dependence tests: %d\n",
4244 dependence_stats
.num_dependence_tests
);
4245 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4246 dependence_stats
.num_dependence_dependent
);
4247 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4248 dependence_stats
.num_dependence_independent
);
4249 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4250 dependence_stats
.num_dependence_undetermined
);
4252 fprintf (dump_file
, "Number of subscript tests: %d\n",
4253 dependence_stats
.num_subscript_tests
);
4254 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4255 dependence_stats
.num_subscript_undetermined
);
4256 fprintf (dump_file
, "Number of same subscript function: %d\n",
4257 dependence_stats
.num_same_subscript_function
);
4259 fprintf (dump_file
, "Number of ziv tests: %d\n",
4260 dependence_stats
.num_ziv
);
4261 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4262 dependence_stats
.num_ziv_dependent
);
4263 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4264 dependence_stats
.num_ziv_independent
);
4265 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4266 dependence_stats
.num_ziv_unimplemented
);
4268 fprintf (dump_file
, "Number of siv tests: %d\n",
4269 dependence_stats
.num_siv
);
4270 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4271 dependence_stats
.num_siv_dependent
);
4272 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4273 dependence_stats
.num_siv_independent
);
4274 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4275 dependence_stats
.num_siv_unimplemented
);
4277 fprintf (dump_file
, "Number of miv tests: %d\n",
4278 dependence_stats
.num_miv
);
4279 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4280 dependence_stats
.num_miv_dependent
);
4281 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4282 dependence_stats
.num_miv_independent
);
4283 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4284 dependence_stats
.num_miv_unimplemented
);
4290 /* Entry point (for testing only). Analyze all the data references
4291 and the dependence relations in LOOP.
4293 The data references are computed first.
4295 A relation on these nodes is represented by a complete graph. Some
4296 of the relations could be of no interest, thus the relations can be
4299 In the following function we compute all the relations. This is
4300 just a first implementation that is here for:
4301 - for showing how to ask for the dependence relations,
4302 - for the debugging the whole dependence graph,
4303 - for the dejagnu testcases and maintenance.
4305 It is possible to ask only for a part of the graph, avoiding to
4306 compute the whole dependence graph. The computed dependences are
4307 stored in a knowledge base (KB) such that later queries don't
4308 recompute the same information. The implementation of this KB is
4309 transparent to the optimizer, and thus the KB can be changed with a
4310 more efficient implementation, or the KB could be disabled. */
4312 analyze_all_data_dependences (struct loop
*loop
)
4315 int nb_data_refs
= 10;
4316 VEC (data_reference_p
, heap
) *datarefs
=
4317 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4318 VEC (ddr_p
, heap
) *dependence_relations
=
4319 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4321 /* Compute DDs on the whole function. */
4322 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4323 &dependence_relations
);
4327 dump_data_dependence_relations (dump_file
, dependence_relations
);
4328 fprintf (dump_file
, "\n\n");
4330 if (dump_flags
& TDF_DETAILS
)
4331 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4333 if (dump_flags
& TDF_STATS
)
4335 unsigned nb_top_relations
= 0;
4336 unsigned nb_bot_relations
= 0;
4337 unsigned nb_chrec_relations
= 0;
4338 struct data_dependence_relation
*ddr
;
4340 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4342 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4345 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4349 nb_chrec_relations
++;
4352 gather_stats_on_scev_database ();
4356 free_dependence_relations (dependence_relations
);
4357 free_data_refs (datarefs
);
4360 /* Computes all the data dependences and check that the results of
4361 several analyzers are the same. */
4364 tree_check_data_deps (void)
4367 struct loop
*loop_nest
;
4369 FOR_EACH_LOOP (li
, loop_nest
, 0)
4370 analyze_all_data_dependences (loop_nest
);
4373 /* Free the memory used by a data dependence relation DDR. */
4376 free_dependence_relation (struct data_dependence_relation
*ddr
)
4381 if (DDR_SUBSCRIPTS (ddr
))
4382 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4383 if (DDR_DIST_VECTS (ddr
))
4384 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4385 if (DDR_DIR_VECTS (ddr
))
4386 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4391 /* Free the memory used by the data dependence relations from
4392 DEPENDENCE_RELATIONS. */
4395 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4398 struct data_dependence_relation
*ddr
;
4399 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4401 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4405 if (loop_nest
== NULL
)
4406 loop_nest
= DDR_LOOP_NEST (ddr
);
4408 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4409 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4410 free_dependence_relation (ddr
);
4414 VEC_free (loop_p
, heap
, loop_nest
);
4415 VEC_free (ddr_p
, heap
, dependence_relations
);
4418 /* Free the memory used by the data references from DATAREFS. */
4421 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4424 struct data_reference
*dr
;
4426 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4428 VEC_free (data_reference_p
, heap
, datarefs
);
4433 /* Dump vertex I in RDG to FILE. */
4436 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4438 struct vertex
*v
= &(rdg
->vertices
[i
]);
4439 struct graph_edge
*e
;
4441 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4442 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4443 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4446 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4447 fprintf (file
, " %d", e
->src
);
4449 fprintf (file
, ") (out:");
4452 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4453 fprintf (file
, " %d", e
->dest
);
4455 fprintf (file
, ") \n");
4456 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4457 fprintf (file
, ")\n");
4460 /* Call dump_rdg_vertex on stderr. */
4463 debug_rdg_vertex (struct graph
*rdg
, int i
)
4465 dump_rdg_vertex (stderr
, rdg
, i
);
4468 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4469 dumped vertices to that bitmap. */
4471 void dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4475 fprintf (file
, "(%d\n", c
);
4477 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4478 if (rdg
->vertices
[i
].component
== c
)
4481 bitmap_set_bit (dumped
, i
);
4483 dump_rdg_vertex (file
, rdg
, i
);
4486 fprintf (file
, ")\n");
4489 /* Call dump_rdg_vertex on stderr. */
4492 debug_rdg_component (struct graph
*rdg
, int c
)
4494 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4497 /* Dump the reduced dependence graph RDG to FILE. */
4500 dump_rdg (FILE *file
, struct graph
*rdg
)
4503 bitmap dumped
= BITMAP_ALLOC (NULL
);
4505 fprintf (file
, "(rdg\n");
4507 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4508 if (!bitmap_bit_p (dumped
, i
))
4509 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4511 fprintf (file
, ")\n");
4512 BITMAP_FREE (dumped
);
4515 /* Call dump_rdg on stderr. */
4518 debug_rdg (struct graph
*rdg
)
4520 dump_rdg (stderr
, rdg
);
4524 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
4528 fprintf (file
, "digraph RDG {\n");
4530 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4532 struct vertex
*v
= &(rdg
->vertices
[i
]);
4533 struct graph_edge
*e
;
4535 /* Highlight reads from memory. */
4536 if (RDG_MEM_READS_STMT (rdg
, i
))
4537 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
4539 /* Highlight stores to memory. */
4540 if (RDG_MEM_WRITE_STMT (rdg
, i
))
4541 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
4544 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4545 switch (RDGE_TYPE (e
))
4548 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
4552 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
4556 /* These are the most common dependences: don't print these. */
4557 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
4561 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
4569 fprintf (file
, "}\n\n");
4572 /* Display SCOP using dotty. */
4575 dot_rdg (struct graph
*rdg
)
4577 FILE *file
= fopen ("/tmp/rdg.dot", "w");
4578 gcc_assert (file
!= NULL
);
4580 dot_rdg_1 (file
, rdg
);
4583 system ("dotty /tmp/rdg.dot");
4587 /* This structure is used for recording the mapping statement index in
4590 struct rdg_vertex_info
GTY(())
4596 /* Returns the index of STMT in RDG. */
4599 rdg_vertex_for_stmt (struct graph
*rdg
, gimple stmt
)
4601 struct rdg_vertex_info rvi
, *slot
;
4604 slot
= (struct rdg_vertex_info
*) htab_find (rdg
->indices
, &rvi
);
4612 /* Creates an edge in RDG for each distance vector from DDR. The
4613 order that we keep track of in the RDG is the order in which
4614 statements have to be executed. */
4617 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4619 struct graph_edge
*e
;
4621 data_reference_p dra
= DDR_A (ddr
);
4622 data_reference_p drb
= DDR_B (ddr
);
4623 unsigned level
= ddr_dependence_level (ddr
);
4625 /* For non scalar dependences, when the dependence is REVERSED,
4626 statement B has to be executed before statement A. */
4628 && !DDR_REVERSED_P (ddr
))
4630 data_reference_p tmp
= dra
;
4635 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4636 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4638 if (va
< 0 || vb
< 0)
4641 e
= add_edge (rdg
, va
, vb
);
4642 e
->data
= XNEW (struct rdg_edge
);
4644 RDGE_LEVEL (e
) = level
;
4645 RDGE_RELATION (e
) = ddr
;
4647 /* Determines the type of the data dependence. */
4648 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4649 RDGE_TYPE (e
) = input_dd
;
4650 else if (!DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4651 RDGE_TYPE (e
) = output_dd
;
4652 else if (!DR_IS_READ (dra
) && DR_IS_READ (drb
))
4653 RDGE_TYPE (e
) = flow_dd
;
4654 else if (DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4655 RDGE_TYPE (e
) = anti_dd
;
4658 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4659 the index of DEF in RDG. */
4662 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4664 use_operand_p imm_use_p
;
4665 imm_use_iterator iterator
;
4667 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4669 struct graph_edge
*e
;
4670 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4675 e
= add_edge (rdg
, idef
, use
);
4676 e
->data
= XNEW (struct rdg_edge
);
4677 RDGE_TYPE (e
) = flow_dd
;
4678 RDGE_RELATION (e
) = NULL
;
4682 /* Creates the edges of the reduced dependence graph RDG. */
4685 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4688 struct data_dependence_relation
*ddr
;
4689 def_operand_p def_p
;
4692 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
4693 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4694 create_rdg_edge_for_ddr (rdg
, ddr
);
4696 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4697 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4699 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4702 /* Build the vertices of the reduced dependence graph RDG. */
4705 create_rdg_vertices (struct graph
*rdg
, VEC (gimple
, heap
) *stmts
)
4710 for (i
= 0; VEC_iterate (gimple
, stmts
, i
, stmt
); i
++)
4712 VEC (data_ref_loc
, heap
) *references
;
4714 struct vertex
*v
= &(rdg
->vertices
[i
]);
4715 struct rdg_vertex_info
*rvi
= XNEW (struct rdg_vertex_info
);
4716 struct rdg_vertex_info
**slot
;
4720 slot
= (struct rdg_vertex_info
**) htab_find_slot (rdg
->indices
, rvi
, INSERT
);
4727 v
->data
= XNEW (struct rdg_vertex
);
4728 RDG_STMT (rdg
, i
) = stmt
;
4730 RDG_MEM_WRITE_STMT (rdg
, i
) = false;
4731 RDG_MEM_READS_STMT (rdg
, i
) = false;
4732 if (gimple_code (stmt
) == GIMPLE_PHI
)
4735 get_references_in_stmt (stmt
, &references
);
4736 for (j
= 0; VEC_iterate (data_ref_loc
, references
, j
, ref
); j
++)
4738 RDG_MEM_WRITE_STMT (rdg
, i
) = true;
4740 RDG_MEM_READS_STMT (rdg
, i
) = true;
4742 VEC_free (data_ref_loc
, heap
, references
);
4746 /* Initialize STMTS with all the statements of LOOP. When
4747 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4748 which we discover statements is important as
4749 generate_loops_for_partition is using the same traversal for
4750 identifying statements. */
4753 stmts_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4756 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4758 for (i
= 0; i
< loop
->num_nodes
; i
++)
4760 basic_block bb
= bbs
[i
];
4761 gimple_stmt_iterator bsi
;
4764 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4765 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4767 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4769 stmt
= gsi_stmt (bsi
);
4770 if (gimple_code (stmt
) != GIMPLE_LABEL
)
4771 VEC_safe_push (gimple
, heap
, *stmts
, stmt
);
4778 /* Returns true when all the dependences are computable. */
4781 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
4786 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4787 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4793 /* Computes a hash function for element ELT. */
4796 hash_stmt_vertex_info (const void *elt
)
4798 const struct rdg_vertex_info
*const rvi
=
4799 (const struct rdg_vertex_info
*) elt
;
4800 gimple stmt
= rvi
->stmt
;
4802 return htab_hash_pointer (stmt
);
4805 /* Compares database elements E1 and E2. */
4808 eq_stmt_vertex_info (const void *e1
, const void *e2
)
4810 const struct rdg_vertex_info
*elt1
= (const struct rdg_vertex_info
*) e1
;
4811 const struct rdg_vertex_info
*elt2
= (const struct rdg_vertex_info
*) e2
;
4813 return elt1
->stmt
== elt2
->stmt
;
4816 /* Free the element E. */
4819 hash_stmt_vertex_del (void *e
)
4824 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4825 statement of the loop nest, and one edge per data dependence or
4826 scalar dependence. */
4829 build_empty_rdg (int n_stmts
)
4831 int nb_data_refs
= 10;
4832 struct graph
*rdg
= new_graph (n_stmts
);
4834 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4835 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4839 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4840 statement of the loop nest, and one edge per data dependence or
4841 scalar dependence. */
4844 build_rdg (struct loop
*loop
)
4846 int nb_data_refs
= 10;
4847 struct graph
*rdg
= NULL
;
4848 VEC (ddr_p
, heap
) *dependence_relations
;
4849 VEC (data_reference_p
, heap
) *datarefs
;
4850 VEC (gimple
, heap
) *stmts
= VEC_alloc (gimple
, heap
, nb_data_refs
);
4852 dependence_relations
= VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
) ;
4853 datarefs
= VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4854 compute_data_dependences_for_loop (loop
,
4857 &dependence_relations
);
4859 if (!known_dependences_p (dependence_relations
))
4861 free_dependence_relations (dependence_relations
);
4862 free_data_refs (datarefs
);
4863 VEC_free (gimple
, heap
, stmts
);
4868 stmts_from_loop (loop
, &stmts
);
4869 rdg
= build_empty_rdg (VEC_length (gimple
, stmts
));
4871 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4872 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4873 create_rdg_vertices (rdg
, stmts
);
4874 create_rdg_edges (rdg
, dependence_relations
);
4876 VEC_free (gimple
, heap
, stmts
);
4880 /* Free the reduced dependence graph RDG. */
4883 free_rdg (struct graph
*rdg
)
4887 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4888 free (rdg
->vertices
[i
].data
);
4890 htab_delete (rdg
->indices
);
4894 /* Initialize STMTS with all the statements of LOOP that contain a
4898 stores_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4901 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4903 for (i
= 0; i
< loop
->num_nodes
; i
++)
4905 basic_block bb
= bbs
[i
];
4906 gimple_stmt_iterator bsi
;
4908 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4909 if (gimple_vdef (gsi_stmt (bsi
)))
4910 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4916 /* For a data reference REF, return the declaration of its base
4917 address or NULL_TREE if the base is not determined. */
4920 ref_base_address (gimple stmt
, data_ref_loc
*ref
)
4922 tree base
= NULL_TREE
;
4924 struct data_reference
*dr
= XCNEW (struct data_reference
);
4926 DR_STMT (dr
) = stmt
;
4927 DR_REF (dr
) = *ref
->pos
;
4928 dr_analyze_innermost (dr
);
4929 base_address
= DR_BASE_ADDRESS (dr
);
4934 switch (TREE_CODE (base_address
))
4937 base
= TREE_OPERAND (base_address
, 0);
4941 base
= base_address
;
4950 /* Determines whether the statement from vertex V of the RDG has a
4951 definition used outside the loop that contains this statement. */
4954 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
4956 gimple stmt
= RDG_STMT (rdg
, v
);
4957 struct loop
*loop
= loop_containing_stmt (stmt
);
4958 use_operand_p imm_use_p
;
4959 imm_use_iterator iterator
;
4961 def_operand_p def_p
;
4966 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
4968 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
4970 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)
4978 /* Determines whether statements S1 and S2 access to similar memory
4979 locations. Two memory accesses are considered similar when they
4980 have the same base address declaration, i.e. when their
4981 ref_base_address is the same. */
4984 have_similar_memory_accesses (gimple s1
, gimple s2
)
4988 VEC (data_ref_loc
, heap
) *refs1
, *refs2
;
4989 data_ref_loc
*ref1
, *ref2
;
4991 get_references_in_stmt (s1
, &refs1
);
4992 get_references_in_stmt (s2
, &refs2
);
4994 for (i
= 0; VEC_iterate (data_ref_loc
, refs1
, i
, ref1
); i
++)
4996 tree base1
= ref_base_address (s1
, ref1
);
4999 for (j
= 0; VEC_iterate (data_ref_loc
, refs2
, j
, ref2
); j
++)
5000 if (base1
== ref_base_address (s2
, ref2
))
5008 VEC_free (data_ref_loc
, heap
, refs1
);
5009 VEC_free (data_ref_loc
, heap
, refs2
);
5013 /* Helper function for the hashtab. */
5016 have_similar_memory_accesses_1 (const void *s1
, const void *s2
)
5018 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple
) s1
),
5019 CONST_CAST_GIMPLE ((const_gimple
) s2
));
5022 /* Helper function for the hashtab. */
5025 ref_base_address_1 (const void *s
)
5027 gimple stmt
= CONST_CAST_GIMPLE ((const_gimple
) s
);
5029 VEC (data_ref_loc
, heap
) *refs
;
5033 get_references_in_stmt (stmt
, &refs
);
5035 for (i
= 0; VEC_iterate (data_ref_loc
, refs
, i
, ref
); i
++)
5038 res
= htab_hash_pointer (ref_base_address (stmt
, ref
));
5042 VEC_free (data_ref_loc
, heap
, refs
);
5046 /* Try to remove duplicated write data references from STMTS. */
5049 remove_similar_memory_refs (VEC (gimple
, heap
) **stmts
)
5053 htab_t seen
= htab_create (VEC_length (gimple
, *stmts
), ref_base_address_1
,
5054 have_similar_memory_accesses_1
, NULL
);
5056 for (i
= 0; VEC_iterate (gimple
, *stmts
, i
, stmt
); )
5060 slot
= htab_find_slot (seen
, stmt
, INSERT
);
5063 VEC_ordered_remove (gimple
, *stmts
, i
);
5066 *slot
= (void *) stmt
;
5074 /* Returns the index of PARAMETER in the parameters vector of the
5075 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5078 access_matrix_get_index_for_parameter (tree parameter
,
5079 struct access_matrix
*access_matrix
)
5082 VEC (tree
,heap
) *lambda_parameters
= AM_PARAMETERS (access_matrix
);
5083 tree lambda_parameter
;
5085 for (i
= 0; VEC_iterate (tree
, lambda_parameters
, i
, lambda_parameter
); i
++)
5086 if (lambda_parameter
== parameter
)
5087 return i
+ AM_NB_INDUCTION_VARS (access_matrix
);