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 gimple stmt
= DR_STMT (dr
);
796 tree ref
= DR_REF (dr
);
797 tree base
= get_base_address (ref
), addr
, smt
= NULL_TREE
;
804 else if (INDIRECT_REF_P (base
))
806 addr
= TREE_OPERAND (base
, 0);
807 if (TREE_CODE (addr
) == SSA_NAME
)
809 smt
= symbol_mem_tag (SSA_NAME_VAR (addr
));
810 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
814 DR_SYMBOL_TAG (dr
) = smt
;
816 vops
= BITMAP_ALLOC (NULL
);
817 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, it
, SSA_OP_VIRTUAL_USES
)
819 bitmap_set_bit (vops
, DECL_UID (SSA_NAME_VAR (op
)));
825 /* Returns true if the address of DR is invariant. */
828 dr_address_invariant_p (struct data_reference
*dr
)
833 for (i
= 0; VEC_iterate (tree
, DR_ACCESS_FNS (dr
), i
, idx
); i
++)
834 if (tree_contains_chrecs (idx
, NULL
))
840 /* Frees data reference DR. */
843 free_data_ref (data_reference_p dr
)
845 BITMAP_FREE (DR_VOPS (dr
));
846 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
850 /* Analyzes memory reference MEMREF accessed in STMT. The reference
851 is read if IS_READ is true, write otherwise. Returns the
852 data_reference description of MEMREF. NEST is the outermost loop of the
853 loop nest in that the reference should be analyzed. */
855 struct data_reference
*
856 create_data_ref (struct loop
*nest
, tree memref
, gimple stmt
, bool is_read
)
858 struct data_reference
*dr
;
860 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
862 fprintf (dump_file
, "Creating dr for ");
863 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
864 fprintf (dump_file
, "\n");
867 dr
= XCNEW (struct data_reference
);
869 DR_REF (dr
) = memref
;
870 DR_IS_READ (dr
) = is_read
;
872 dr_analyze_innermost (dr
);
873 dr_analyze_indices (dr
, nest
);
874 dr_analyze_alias (dr
);
876 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
878 fprintf (dump_file
, "\tbase_address: ");
879 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
880 fprintf (dump_file
, "\n\toffset from base address: ");
881 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
882 fprintf (dump_file
, "\n\tconstant offset from base address: ");
883 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
884 fprintf (dump_file
, "\n\tstep: ");
885 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
886 fprintf (dump_file
, "\n\taligned to: ");
887 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
888 fprintf (dump_file
, "\n\tbase_object: ");
889 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
890 fprintf (dump_file
, "\n\tsymbol tag: ");
891 print_generic_expr (dump_file
, DR_SYMBOL_TAG (dr
), TDF_SLIM
);
892 fprintf (dump_file
, "\n");
898 /* Returns true if FNA == FNB. */
901 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
903 unsigned i
, n
= VEC_length (tree
, fna
);
905 if (n
!= VEC_length (tree
, fnb
))
908 for (i
= 0; i
< n
; i
++)
909 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
910 VEC_index (tree
, fnb
, i
), 0))
916 /* If all the functions in CF are the same, returns one of them,
917 otherwise returns NULL. */
920 common_affine_function (conflict_function
*cf
)
925 if (!CF_NONTRIVIAL_P (cf
))
930 for (i
= 1; i
< cf
->n
; i
++)
931 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
937 /* Returns the base of the affine function FN. */
940 affine_function_base (affine_fn fn
)
942 return VEC_index (tree
, fn
, 0);
945 /* Returns true if FN is a constant. */
948 affine_function_constant_p (affine_fn fn
)
953 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
954 if (!integer_zerop (coef
))
960 /* Returns true if FN is the zero constant function. */
963 affine_function_zero_p (affine_fn fn
)
965 return (integer_zerop (affine_function_base (fn
))
966 && affine_function_constant_p (fn
));
969 /* Returns a signed integer type with the largest precision from TA
973 signed_type_for_types (tree ta
, tree tb
)
975 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
976 return signed_type_for (ta
);
978 return signed_type_for (tb
);
981 /* Applies operation OP on affine functions FNA and FNB, and returns the
985 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
991 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
993 n
= VEC_length (tree
, fna
);
994 m
= VEC_length (tree
, fnb
);
998 n
= VEC_length (tree
, fnb
);
999 m
= VEC_length (tree
, fna
);
1002 ret
= VEC_alloc (tree
, heap
, m
);
1003 for (i
= 0; i
< n
; i
++)
1005 tree type
= signed_type_for_types (TREE_TYPE (VEC_index (tree
, fna
, i
)),
1006 TREE_TYPE (VEC_index (tree
, fnb
, i
)));
1008 VEC_quick_push (tree
, ret
,
1009 fold_build2 (op
, type
,
1010 VEC_index (tree
, fna
, i
),
1011 VEC_index (tree
, fnb
, i
)));
1014 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
1015 VEC_quick_push (tree
, ret
,
1016 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1017 coef
, integer_zero_node
));
1018 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
1019 VEC_quick_push (tree
, ret
,
1020 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1021 integer_zero_node
, coef
));
1026 /* Returns the sum of affine functions FNA and FNB. */
1029 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1031 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1034 /* Returns the difference of affine functions FNA and FNB. */
1037 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1039 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1042 /* Frees affine function FN. */
1045 affine_fn_free (affine_fn fn
)
1047 VEC_free (tree
, heap
, fn
);
1050 /* Determine for each subscript in the data dependence relation DDR
1054 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1056 conflict_function
*cf_a
, *cf_b
;
1057 affine_fn fn_a
, fn_b
, diff
;
1059 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1063 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1065 struct subscript
*subscript
;
1067 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1068 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1069 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1071 fn_a
= common_affine_function (cf_a
);
1072 fn_b
= common_affine_function (cf_b
);
1075 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1078 diff
= affine_fn_minus (fn_a
, fn_b
);
1080 if (affine_function_constant_p (diff
))
1081 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1083 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1085 affine_fn_free (diff
);
1090 /* Returns the conflict function for "unknown". */
1092 static conflict_function
*
1093 conflict_fn_not_known (void)
1095 conflict_function
*fn
= XCNEW (conflict_function
);
1101 /* Returns the conflict function for "independent". */
1103 static conflict_function
*
1104 conflict_fn_no_dependence (void)
1106 conflict_function
*fn
= XCNEW (conflict_function
);
1107 fn
->n
= NO_DEPENDENCE
;
1112 /* Returns true if the address of OBJ is invariant in LOOP. */
1115 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1117 while (handled_component_p (obj
))
1119 if (TREE_CODE (obj
) == ARRAY_REF
)
1121 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1122 need to check the stride and the lower bound of the reference. */
1123 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1125 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1129 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1131 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1135 obj
= TREE_OPERAND (obj
, 0);
1138 if (!INDIRECT_REF_P (obj
))
1141 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1145 /* Returns true if A and B are accesses to different objects, or to different
1146 fields of the same object. */
1149 disjoint_objects_p (tree a
, tree b
)
1151 tree base_a
, base_b
;
1152 VEC (tree
, heap
) *comp_a
= NULL
, *comp_b
= NULL
;
1155 base_a
= get_base_address (a
);
1156 base_b
= get_base_address (b
);
1160 && base_a
!= base_b
)
1163 if (!operand_equal_p (base_a
, base_b
, 0))
1166 /* Compare the component references of A and B. We must start from the inner
1167 ones, so record them to the vector first. */
1168 while (handled_component_p (a
))
1170 VEC_safe_push (tree
, heap
, comp_a
, a
);
1171 a
= TREE_OPERAND (a
, 0);
1173 while (handled_component_p (b
))
1175 VEC_safe_push (tree
, heap
, comp_b
, b
);
1176 b
= TREE_OPERAND (b
, 0);
1182 if (VEC_length (tree
, comp_a
) == 0
1183 || VEC_length (tree
, comp_b
) == 0)
1186 a
= VEC_pop (tree
, comp_a
);
1187 b
= VEC_pop (tree
, comp_b
);
1189 /* Real and imaginary part of a variable do not alias. */
1190 if ((TREE_CODE (a
) == REALPART_EXPR
1191 && TREE_CODE (b
) == IMAGPART_EXPR
)
1192 || (TREE_CODE (a
) == IMAGPART_EXPR
1193 && TREE_CODE (b
) == REALPART_EXPR
))
1199 if (TREE_CODE (a
) != TREE_CODE (b
))
1202 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1203 DR_BASE_OBJECT are always zero. */
1204 if (TREE_CODE (a
) == ARRAY_REF
)
1206 else if (TREE_CODE (a
) == COMPONENT_REF
)
1208 if (operand_equal_p (TREE_OPERAND (a
, 1), TREE_OPERAND (b
, 1), 0))
1211 /* Different fields of unions may overlap. */
1212 base_a
= TREE_OPERAND (a
, 0);
1213 if (TREE_CODE (TREE_TYPE (base_a
)) == UNION_TYPE
)
1216 /* Different fields of structures cannot. */
1224 VEC_free (tree
, heap
, comp_a
);
1225 VEC_free (tree
, heap
, comp_b
);
1230 /* Returns false if we can prove that data references A and B do not alias,
1234 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
)
1236 const_tree addr_a
= DR_BASE_ADDRESS (a
);
1237 const_tree addr_b
= DR_BASE_ADDRESS (b
);
1238 const_tree type_a
, type_b
;
1239 const_tree decl_a
= NULL_TREE
, decl_b
= NULL_TREE
;
1241 /* If the sets of virtual operands are disjoint, the memory references do not
1243 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
1246 /* If the accessed objects are disjoint, the memory references do not
1248 if (disjoint_objects_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
)))
1251 if (!addr_a
|| !addr_b
)
1254 /* If the references are based on different static objects, they cannot alias
1255 (PTA should be able to disambiguate such accesses, but often it fails to,
1256 since currently we cannot distinguish between pointer and offset in pointer
1258 if (TREE_CODE (addr_a
) == ADDR_EXPR
1259 && TREE_CODE (addr_b
) == ADDR_EXPR
)
1260 return TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0);
1262 /* An instruction writing through a restricted pointer is "independent" of any
1263 instruction reading or writing through a different restricted pointer,
1264 in the same block/scope. */
1266 type_a
= TREE_TYPE (addr_a
);
1267 type_b
= TREE_TYPE (addr_b
);
1268 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
1270 if (TREE_CODE (addr_a
) == SSA_NAME
)
1271 decl_a
= SSA_NAME_VAR (addr_a
);
1272 if (TREE_CODE (addr_b
) == SSA_NAME
)
1273 decl_b
= SSA_NAME_VAR (addr_b
);
1275 if (TYPE_RESTRICT (type_a
) && TYPE_RESTRICT (type_b
)
1276 && (!DR_IS_READ (a
) || !DR_IS_READ (b
))
1277 && decl_a
&& DECL_P (decl_a
)
1278 && decl_b
&& DECL_P (decl_b
)
1280 && TREE_CODE (DECL_CONTEXT (decl_a
)) == FUNCTION_DECL
1281 && DECL_CONTEXT (decl_a
) == DECL_CONTEXT (decl_b
))
1287 static void compute_self_dependence (struct data_dependence_relation
*);
1289 /* Initialize a data dependence relation between data accesses A and
1290 B. NB_LOOPS is the number of loops surrounding the references: the
1291 size of the classic distance/direction vectors. */
1293 static struct data_dependence_relation
*
1294 initialize_data_dependence_relation (struct data_reference
*a
,
1295 struct data_reference
*b
,
1296 VEC (loop_p
, heap
) *loop_nest
)
1298 struct data_dependence_relation
*res
;
1301 res
= XNEW (struct data_dependence_relation
);
1304 DDR_LOOP_NEST (res
) = NULL
;
1305 DDR_REVERSED_P (res
) = false;
1306 DDR_SUBSCRIPTS (res
) = NULL
;
1307 DDR_DIR_VECTS (res
) = NULL
;
1308 DDR_DIST_VECTS (res
) = NULL
;
1310 if (a
== NULL
|| b
== NULL
)
1312 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1316 /* If the data references do not alias, then they are independent. */
1317 if (!dr_may_alias_p (a
, b
))
1319 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1323 /* When the references are exactly the same, don't spend time doing
1324 the data dependence tests, just initialize the ddr and return. */
1325 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1327 DDR_AFFINE_P (res
) = true;
1328 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1329 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1330 DDR_LOOP_NEST (res
) = loop_nest
;
1331 DDR_INNER_LOOP (res
) = 0;
1332 DDR_SELF_REFERENCE (res
) = true;
1333 compute_self_dependence (res
);
1337 /* If the references do not access the same object, we do not know
1338 whether they alias or not. */
1339 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1341 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1345 /* If the base of the object is not invariant in the loop nest, we cannot
1346 analyze it. TODO -- in fact, it would suffice to record that there may
1347 be arbitrary dependences in the loops where the base object varies. */
1348 if (!object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1349 DR_BASE_OBJECT (a
)))
1351 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1355 gcc_assert (DR_NUM_DIMENSIONS (a
) == DR_NUM_DIMENSIONS (b
));
1357 DDR_AFFINE_P (res
) = true;
1358 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1359 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1360 DDR_LOOP_NEST (res
) = loop_nest
;
1361 DDR_INNER_LOOP (res
) = 0;
1362 DDR_SELF_REFERENCE (res
) = false;
1364 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1366 struct subscript
*subscript
;
1368 subscript
= XNEW (struct subscript
);
1369 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1370 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1371 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1372 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1373 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1379 /* Frees memory used by the conflict function F. */
1382 free_conflict_function (conflict_function
*f
)
1386 if (CF_NONTRIVIAL_P (f
))
1388 for (i
= 0; i
< f
->n
; i
++)
1389 affine_fn_free (f
->fns
[i
]);
1394 /* Frees memory used by SUBSCRIPTS. */
1397 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1402 for (i
= 0; VEC_iterate (subscript_p
, subscripts
, i
, s
); i
++)
1404 free_conflict_function (s
->conflicting_iterations_in_a
);
1405 free_conflict_function (s
->conflicting_iterations_in_b
);
1408 VEC_free (subscript_p
, heap
, subscripts
);
1411 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1415 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1418 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1420 fprintf (dump_file
, "(dependence classified: ");
1421 print_generic_expr (dump_file
, chrec
, 0);
1422 fprintf (dump_file
, ")\n");
1425 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1426 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1427 DDR_SUBSCRIPTS (ddr
) = NULL
;
1430 /* The dependence relation DDR cannot be represented by a distance
1434 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1436 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1437 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1439 DDR_AFFINE_P (ddr
) = false;
1444 /* This section contains the classic Banerjee tests. */
1446 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1447 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1450 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1452 return (evolution_function_is_constant_p (chrec_a
)
1453 && evolution_function_is_constant_p (chrec_b
));
1456 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1457 variable, i.e., if the SIV (Single Index Variable) test is true. */
1460 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1462 if ((evolution_function_is_constant_p (chrec_a
)
1463 && evolution_function_is_univariate_p (chrec_b
))
1464 || (evolution_function_is_constant_p (chrec_b
)
1465 && evolution_function_is_univariate_p (chrec_a
)))
1468 if (evolution_function_is_univariate_p (chrec_a
)
1469 && evolution_function_is_univariate_p (chrec_b
))
1471 switch (TREE_CODE (chrec_a
))
1473 case POLYNOMIAL_CHREC
:
1474 switch (TREE_CODE (chrec_b
))
1476 case POLYNOMIAL_CHREC
:
1477 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1492 /* Creates a conflict function with N dimensions. The affine functions
1493 in each dimension follow. */
1495 static conflict_function
*
1496 conflict_fn (unsigned n
, ...)
1499 conflict_function
*ret
= XCNEW (conflict_function
);
1502 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1506 for (i
= 0; i
< n
; i
++)
1507 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1513 /* Returns constant affine function with value CST. */
1516 affine_fn_cst (tree cst
)
1518 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1519 VEC_quick_push (tree
, fn
, cst
);
1523 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1526 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1528 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1531 gcc_assert (dim
> 0);
1532 VEC_quick_push (tree
, fn
, cst
);
1533 for (i
= 1; i
< dim
; i
++)
1534 VEC_quick_push (tree
, fn
, integer_zero_node
);
1535 VEC_quick_push (tree
, fn
, coef
);
1539 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1540 *OVERLAPS_B are initialized to the functions that describe the
1541 relation between the elements accessed twice by CHREC_A and
1542 CHREC_B. For k >= 0, the following property is verified:
1544 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1547 analyze_ziv_subscript (tree chrec_a
,
1549 conflict_function
**overlaps_a
,
1550 conflict_function
**overlaps_b
,
1551 tree
*last_conflicts
)
1553 tree type
, difference
;
1554 dependence_stats
.num_ziv
++;
1556 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1557 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1559 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1560 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1561 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1562 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1564 switch (TREE_CODE (difference
))
1567 if (integer_zerop (difference
))
1569 /* The difference is equal to zero: the accessed index
1570 overlaps for each iteration in the loop. */
1571 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1572 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1573 *last_conflicts
= chrec_dont_know
;
1574 dependence_stats
.num_ziv_dependent
++;
1578 /* The accesses do not overlap. */
1579 *overlaps_a
= conflict_fn_no_dependence ();
1580 *overlaps_b
= conflict_fn_no_dependence ();
1581 *last_conflicts
= integer_zero_node
;
1582 dependence_stats
.num_ziv_independent
++;
1587 /* We're not sure whether the indexes overlap. For the moment,
1588 conservatively answer "don't know". */
1589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1590 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1592 *overlaps_a
= conflict_fn_not_known ();
1593 *overlaps_b
= conflict_fn_not_known ();
1594 *last_conflicts
= chrec_dont_know
;
1595 dependence_stats
.num_ziv_unimplemented
++;
1599 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1600 fprintf (dump_file
, ")\n");
1603 /* Sets NIT to the estimated number of executions of the statements in
1604 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1605 large as the number of iterations. If we have no reliable estimate,
1606 the function returns false, otherwise returns true. */
1609 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
1612 estimate_numbers_of_iterations_loop (loop
);
1615 if (!loop
->any_upper_bound
)
1618 *nit
= loop
->nb_iterations_upper_bound
;
1622 if (!loop
->any_estimate
)
1625 *nit
= loop
->nb_iterations_estimate
;
1631 /* Similar to estimated_loop_iterations, but returns the estimate only
1632 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1633 on the number of iterations of LOOP could not be derived, returns -1. */
1636 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
1639 HOST_WIDE_INT hwi_nit
;
1641 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1644 if (!double_int_fits_in_shwi_p (nit
))
1646 hwi_nit
= double_int_to_shwi (nit
);
1648 return hwi_nit
< 0 ? -1 : hwi_nit
;
1651 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1652 and only if it fits to the int type. If this is not the case, or the
1653 estimate on the number of iterations of LOOP could not be derived, returns
1657 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
1662 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1663 return chrec_dont_know
;
1665 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
1666 if (!double_int_fits_to_tree_p (type
, nit
))
1667 return chrec_dont_know
;
1669 return double_int_to_tree (type
, nit
);
1672 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1673 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1674 *OVERLAPS_B are initialized to the functions that describe the
1675 relation between the elements accessed twice by CHREC_A and
1676 CHREC_B. For k >= 0, the following property is verified:
1678 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1681 analyze_siv_subscript_cst_affine (tree chrec_a
,
1683 conflict_function
**overlaps_a
,
1684 conflict_function
**overlaps_b
,
1685 tree
*last_conflicts
)
1687 bool value0
, value1
, value2
;
1688 tree type
, difference
, tmp
;
1690 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1691 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1692 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1693 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1695 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1697 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1698 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1700 dependence_stats
.num_siv_unimplemented
++;
1701 *overlaps_a
= conflict_fn_not_known ();
1702 *overlaps_b
= conflict_fn_not_known ();
1703 *last_conflicts
= chrec_dont_know
;
1708 if (value0
== false)
1710 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1712 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1713 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1715 *overlaps_a
= conflict_fn_not_known ();
1716 *overlaps_b
= conflict_fn_not_known ();
1717 *last_conflicts
= chrec_dont_know
;
1718 dependence_stats
.num_siv_unimplemented
++;
1727 chrec_b = {10, +, 1}
1730 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1732 HOST_WIDE_INT numiter
;
1733 struct loop
*loop
= get_chrec_loop (chrec_b
);
1735 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1736 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1737 fold_build1 (ABS_EXPR
, type
, difference
),
1738 CHREC_RIGHT (chrec_b
));
1739 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1740 *last_conflicts
= integer_one_node
;
1743 /* Perform weak-zero siv test to see if overlap is
1744 outside the loop bounds. */
1745 numiter
= estimated_loop_iterations_int (loop
, false);
1748 && compare_tree_int (tmp
, numiter
) > 0)
1750 free_conflict_function (*overlaps_a
);
1751 free_conflict_function (*overlaps_b
);
1752 *overlaps_a
= conflict_fn_no_dependence ();
1753 *overlaps_b
= conflict_fn_no_dependence ();
1754 *last_conflicts
= integer_zero_node
;
1755 dependence_stats
.num_siv_independent
++;
1758 dependence_stats
.num_siv_dependent
++;
1762 /* When the step does not divide the difference, there are
1766 *overlaps_a
= conflict_fn_no_dependence ();
1767 *overlaps_b
= conflict_fn_no_dependence ();
1768 *last_conflicts
= integer_zero_node
;
1769 dependence_stats
.num_siv_independent
++;
1778 chrec_b = {10, +, -1}
1780 In this case, chrec_a will not overlap with chrec_b. */
1781 *overlaps_a
= conflict_fn_no_dependence ();
1782 *overlaps_b
= conflict_fn_no_dependence ();
1783 *last_conflicts
= integer_zero_node
;
1784 dependence_stats
.num_siv_independent
++;
1791 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1794 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1796 *overlaps_a
= conflict_fn_not_known ();
1797 *overlaps_b
= conflict_fn_not_known ();
1798 *last_conflicts
= chrec_dont_know
;
1799 dependence_stats
.num_siv_unimplemented
++;
1804 if (value2
== false)
1808 chrec_b = {10, +, -1}
1810 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1812 HOST_WIDE_INT numiter
;
1813 struct loop
*loop
= get_chrec_loop (chrec_b
);
1815 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1816 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1817 CHREC_RIGHT (chrec_b
));
1818 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1819 *last_conflicts
= integer_one_node
;
1821 /* Perform weak-zero siv test to see if overlap is
1822 outside the loop bounds. */
1823 numiter
= estimated_loop_iterations_int (loop
, false);
1826 && compare_tree_int (tmp
, numiter
) > 0)
1828 free_conflict_function (*overlaps_a
);
1829 free_conflict_function (*overlaps_b
);
1830 *overlaps_a
= conflict_fn_no_dependence ();
1831 *overlaps_b
= conflict_fn_no_dependence ();
1832 *last_conflicts
= integer_zero_node
;
1833 dependence_stats
.num_siv_independent
++;
1836 dependence_stats
.num_siv_dependent
++;
1840 /* When the step does not divide the difference, there
1844 *overlaps_a
= conflict_fn_no_dependence ();
1845 *overlaps_b
= conflict_fn_no_dependence ();
1846 *last_conflicts
= integer_zero_node
;
1847 dependence_stats
.num_siv_independent
++;
1857 In this case, chrec_a will not overlap with chrec_b. */
1858 *overlaps_a
= conflict_fn_no_dependence ();
1859 *overlaps_b
= conflict_fn_no_dependence ();
1860 *last_conflicts
= integer_zero_node
;
1861 dependence_stats
.num_siv_independent
++;
1869 /* Helper recursive function for initializing the matrix A. Returns
1870 the initial value of CHREC. */
1873 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1877 switch (TREE_CODE (chrec
))
1879 case POLYNOMIAL_CHREC
:
1880 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
1882 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1883 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1889 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1890 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
1892 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
1897 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1898 return chrec_convert (chrec_type (chrec
), op
, NULL
);
1903 /* Handle ~X as -1 - X. */
1904 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1905 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
1906 build_int_cst (TREE_TYPE (chrec
), -1), op
);
1918 #define FLOOR_DIV(x,y) ((x) / (y))
1920 /* Solves the special case of the Diophantine equation:
1921 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1923 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1924 number of iterations that loops X and Y run. The overlaps will be
1925 constructed as evolutions in dimension DIM. */
1928 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1929 affine_fn
*overlaps_a
,
1930 affine_fn
*overlaps_b
,
1931 tree
*last_conflicts
, int dim
)
1933 if (((step_a
> 0 && step_b
> 0)
1934 || (step_a
< 0 && step_b
< 0)))
1936 int step_overlaps_a
, step_overlaps_b
;
1937 int gcd_steps_a_b
, last_conflict
, tau2
;
1939 gcd_steps_a_b
= gcd (step_a
, step_b
);
1940 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1941 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1945 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1946 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1947 last_conflict
= tau2
;
1948 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1951 *last_conflicts
= chrec_dont_know
;
1953 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
1954 build_int_cst (NULL_TREE
,
1956 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
1957 build_int_cst (NULL_TREE
,
1963 *overlaps_a
= affine_fn_cst (integer_zero_node
);
1964 *overlaps_b
= affine_fn_cst (integer_zero_node
);
1965 *last_conflicts
= integer_zero_node
;
1969 /* Solves the special case of a Diophantine equation where CHREC_A is
1970 an affine bivariate function, and CHREC_B is an affine univariate
1971 function. For example,
1973 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1975 has the following overlapping functions:
1977 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1978 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1979 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1981 FORNOW: This is a specialized implementation for a case occurring in
1982 a common benchmark. Implement the general algorithm. */
1985 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1986 conflict_function
**overlaps_a
,
1987 conflict_function
**overlaps_b
,
1988 tree
*last_conflicts
)
1990 bool xz_p
, yz_p
, xyz_p
;
1991 int step_x
, step_y
, step_z
;
1992 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
1993 affine_fn overlaps_a_xz
, overlaps_b_xz
;
1994 affine_fn overlaps_a_yz
, overlaps_b_yz
;
1995 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
1996 affine_fn ova1
, ova2
, ovb
;
1997 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
1999 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2000 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2001 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2004 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a
)),
2006 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), false);
2007 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), false);
2009 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2012 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2014 *overlaps_a
= conflict_fn_not_known ();
2015 *overlaps_b
= conflict_fn_not_known ();
2016 *last_conflicts
= chrec_dont_know
;
2020 niter
= MIN (niter_x
, niter_z
);
2021 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2024 &last_conflicts_xz
, 1);
2025 niter
= MIN (niter_y
, niter_z
);
2026 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2029 &last_conflicts_yz
, 2);
2030 niter
= MIN (niter_x
, niter_z
);
2031 niter
= MIN (niter_y
, niter
);
2032 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2035 &last_conflicts_xyz
, 3);
2037 xz_p
= !integer_zerop (last_conflicts_xz
);
2038 yz_p
= !integer_zerop (last_conflicts_yz
);
2039 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2041 if (xz_p
|| yz_p
|| xyz_p
)
2043 ova1
= affine_fn_cst (integer_zero_node
);
2044 ova2
= affine_fn_cst (integer_zero_node
);
2045 ovb
= affine_fn_cst (integer_zero_node
);
2048 affine_fn t0
= ova1
;
2051 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2052 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2053 affine_fn_free (t0
);
2054 affine_fn_free (t2
);
2055 *last_conflicts
= last_conflicts_xz
;
2059 affine_fn t0
= ova2
;
2062 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2063 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2064 affine_fn_free (t0
);
2065 affine_fn_free (t2
);
2066 *last_conflicts
= last_conflicts_yz
;
2070 affine_fn t0
= ova1
;
2071 affine_fn t2
= ova2
;
2074 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2075 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2076 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2077 affine_fn_free (t0
);
2078 affine_fn_free (t2
);
2079 affine_fn_free (t4
);
2080 *last_conflicts
= last_conflicts_xyz
;
2082 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2083 *overlaps_b
= conflict_fn (1, ovb
);
2087 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2088 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2089 *last_conflicts
= integer_zero_node
;
2092 affine_fn_free (overlaps_a_xz
);
2093 affine_fn_free (overlaps_b_xz
);
2094 affine_fn_free (overlaps_a_yz
);
2095 affine_fn_free (overlaps_b_yz
);
2096 affine_fn_free (overlaps_a_xyz
);
2097 affine_fn_free (overlaps_b_xyz
);
2100 /* Determines the overlapping elements due to accesses CHREC_A and
2101 CHREC_B, that are affine functions. This function cannot handle
2102 symbolic evolution functions, ie. when initial conditions are
2103 parameters, because it uses lambda matrices of integers. */
2106 analyze_subscript_affine_affine (tree chrec_a
,
2108 conflict_function
**overlaps_a
,
2109 conflict_function
**overlaps_b
,
2110 tree
*last_conflicts
)
2112 unsigned nb_vars_a
, nb_vars_b
, dim
;
2113 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2114 lambda_matrix A
, U
, S
;
2116 if (eq_evolutions_p (chrec_a
, chrec_b
))
2118 /* The accessed index overlaps for each iteration in the
2120 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2121 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2122 *last_conflicts
= chrec_dont_know
;
2125 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2126 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2128 /* For determining the initial intersection, we have to solve a
2129 Diophantine equation. This is the most time consuming part.
2131 For answering to the question: "Is there a dependence?" we have
2132 to prove that there exists a solution to the Diophantine
2133 equation, and that the solution is in the iteration domain,
2134 i.e. the solution is positive or zero, and that the solution
2135 happens before the upper bound loop.nb_iterations. Otherwise
2136 there is no dependence. This function outputs a description of
2137 the iterations that hold the intersections. */
2139 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2140 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2142 dim
= nb_vars_a
+ nb_vars_b
;
2143 U
= lambda_matrix_new (dim
, dim
);
2144 A
= lambda_matrix_new (dim
, 1);
2145 S
= lambda_matrix_new (dim
, 1);
2147 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2148 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2149 gamma
= init_b
- init_a
;
2151 /* Don't do all the hard work of solving the Diophantine equation
2152 when we already know the solution: for example,
2155 | gamma = 3 - 3 = 0.
2156 Then the first overlap occurs during the first iterations:
2157 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2161 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2163 HOST_WIDE_INT step_a
, step_b
;
2164 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2167 niter_a
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
),
2169 niter_b
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
),
2171 niter
= MIN (niter_a
, niter_b
);
2172 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2173 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2175 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2178 *overlaps_a
= conflict_fn (1, ova
);
2179 *overlaps_b
= conflict_fn (1, ovb
);
2182 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2183 compute_overlap_steps_for_affine_1_2
2184 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2186 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2187 compute_overlap_steps_for_affine_1_2
2188 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2192 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2193 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2194 *overlaps_a
= conflict_fn_not_known ();
2195 *overlaps_b
= conflict_fn_not_known ();
2196 *last_conflicts
= chrec_dont_know
;
2198 goto end_analyze_subs_aa
;
2202 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2207 lambda_matrix_row_negate (U
, dim
, 0);
2209 gcd_alpha_beta
= S
[0][0];
2211 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2212 but that is a quite strange case. Instead of ICEing, answer
2214 if (gcd_alpha_beta
== 0)
2216 *overlaps_a
= conflict_fn_not_known ();
2217 *overlaps_b
= conflict_fn_not_known ();
2218 *last_conflicts
= chrec_dont_know
;
2219 goto end_analyze_subs_aa
;
2222 /* The classic "gcd-test". */
2223 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2225 /* The "gcd-test" has determined that there is no integer
2226 solution, i.e. there is no dependence. */
2227 *overlaps_a
= conflict_fn_no_dependence ();
2228 *overlaps_b
= conflict_fn_no_dependence ();
2229 *last_conflicts
= integer_zero_node
;
2232 /* Both access functions are univariate. This includes SIV and MIV cases. */
2233 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2235 /* Both functions should have the same evolution sign. */
2236 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2237 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2239 /* The solutions are given by:
2241 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2244 For a given integer t. Using the following variables,
2246 | i0 = u11 * gamma / gcd_alpha_beta
2247 | j0 = u12 * gamma / gcd_alpha_beta
2254 | y0 = j0 + j1 * t. */
2255 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2257 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2258 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2262 if ((i1
== 0 && i0
< 0)
2263 || (j1
== 0 && j0
< 0))
2265 /* There is no solution.
2266 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2267 falls in here, but for the moment we don't look at the
2268 upper bound of the iteration domain. */
2269 *overlaps_a
= conflict_fn_no_dependence ();
2270 *overlaps_b
= conflict_fn_no_dependence ();
2271 *last_conflicts
= integer_zero_node
;
2272 goto end_analyze_subs_aa
;
2275 if (i1
> 0 && j1
> 0)
2277 HOST_WIDE_INT niter_a
= estimated_loop_iterations_int
2278 (get_chrec_loop (chrec_a
), false);
2279 HOST_WIDE_INT niter_b
= estimated_loop_iterations_int
2280 (get_chrec_loop (chrec_b
), false);
2281 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2283 /* (X0, Y0) is a solution of the Diophantine equation:
2284 "chrec_a (X0) = chrec_b (Y0)". */
2285 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2287 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2288 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2290 /* (X1, Y1) is the smallest positive solution of the eq
2291 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2292 first conflict occurs. */
2293 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2294 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2295 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2299 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2300 FLOOR_DIV (niter
- j0
, j1
));
2301 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2303 /* If the overlap occurs outside of the bounds of the
2304 loop, there is no dependence. */
2305 if (x1
>= niter
|| y1
>= niter
)
2307 *overlaps_a
= conflict_fn_no_dependence ();
2308 *overlaps_b
= conflict_fn_no_dependence ();
2309 *last_conflicts
= integer_zero_node
;
2310 goto end_analyze_subs_aa
;
2313 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2316 *last_conflicts
= chrec_dont_know
;
2320 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2322 build_int_cst (NULL_TREE
, i1
)));
2325 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2327 build_int_cst (NULL_TREE
, j1
)));
2331 /* FIXME: For the moment, the upper bound of the
2332 iteration domain for i and j is not checked. */
2333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2334 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2335 *overlaps_a
= conflict_fn_not_known ();
2336 *overlaps_b
= conflict_fn_not_known ();
2337 *last_conflicts
= chrec_dont_know
;
2342 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2343 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2344 *overlaps_a
= conflict_fn_not_known ();
2345 *overlaps_b
= conflict_fn_not_known ();
2346 *last_conflicts
= chrec_dont_know
;
2351 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2352 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2353 *overlaps_a
= conflict_fn_not_known ();
2354 *overlaps_b
= conflict_fn_not_known ();
2355 *last_conflicts
= chrec_dont_know
;
2358 end_analyze_subs_aa
:
2359 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2361 fprintf (dump_file
, " (overlaps_a = ");
2362 dump_conflict_function (dump_file
, *overlaps_a
);
2363 fprintf (dump_file
, ")\n (overlaps_b = ");
2364 dump_conflict_function (dump_file
, *overlaps_b
);
2365 fprintf (dump_file
, ")\n");
2366 fprintf (dump_file
, ")\n");
2370 /* Returns true when analyze_subscript_affine_affine can be used for
2371 determining the dependence relation between chrec_a and chrec_b,
2372 that contain symbols. This function modifies chrec_a and chrec_b
2373 such that the analysis result is the same, and such that they don't
2374 contain symbols, and then can safely be passed to the analyzer.
2376 Example: The analysis of the following tuples of evolutions produce
2377 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2380 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2381 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2385 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2387 tree diff
, type
, left_a
, left_b
, right_b
;
2389 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2390 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2391 /* FIXME: For the moment not handled. Might be refined later. */
2394 type
= chrec_type (*chrec_a
);
2395 left_a
= CHREC_LEFT (*chrec_a
);
2396 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2397 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2399 if (!evolution_function_is_constant_p (diff
))
2402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2403 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2405 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2406 diff
, CHREC_RIGHT (*chrec_a
));
2407 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2408 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2409 build_int_cst (type
, 0),
2414 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2415 *OVERLAPS_B are initialized to the functions that describe the
2416 relation between the elements accessed twice by CHREC_A and
2417 CHREC_B. For k >= 0, the following property is verified:
2419 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2422 analyze_siv_subscript (tree chrec_a
,
2424 conflict_function
**overlaps_a
,
2425 conflict_function
**overlaps_b
,
2426 tree
*last_conflicts
,
2429 dependence_stats
.num_siv
++;
2431 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2432 fprintf (dump_file
, "(analyze_siv_subscript \n");
2434 if (evolution_function_is_constant_p (chrec_a
)
2435 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2436 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2437 overlaps_a
, overlaps_b
, last_conflicts
);
2439 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2440 && evolution_function_is_constant_p (chrec_b
))
2441 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2442 overlaps_b
, overlaps_a
, last_conflicts
);
2444 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2445 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2447 if (!chrec_contains_symbols (chrec_a
)
2448 && !chrec_contains_symbols (chrec_b
))
2450 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2451 overlaps_a
, overlaps_b
,
2454 if (CF_NOT_KNOWN_P (*overlaps_a
)
2455 || CF_NOT_KNOWN_P (*overlaps_b
))
2456 dependence_stats
.num_siv_unimplemented
++;
2457 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2458 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2459 dependence_stats
.num_siv_independent
++;
2461 dependence_stats
.num_siv_dependent
++;
2463 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2466 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2467 overlaps_a
, overlaps_b
,
2470 if (CF_NOT_KNOWN_P (*overlaps_a
)
2471 || CF_NOT_KNOWN_P (*overlaps_b
))
2472 dependence_stats
.num_siv_unimplemented
++;
2473 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2474 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2475 dependence_stats
.num_siv_independent
++;
2477 dependence_stats
.num_siv_dependent
++;
2480 goto siv_subscript_dontknow
;
2485 siv_subscript_dontknow
:;
2486 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2487 fprintf (dump_file
, "siv test failed: unimplemented.\n");
2488 *overlaps_a
= conflict_fn_not_known ();
2489 *overlaps_b
= conflict_fn_not_known ();
2490 *last_conflicts
= chrec_dont_know
;
2491 dependence_stats
.num_siv_unimplemented
++;
2494 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2495 fprintf (dump_file
, ")\n");
2498 /* Returns false if we can prove that the greatest common divisor of the steps
2499 of CHREC does not divide CST, false otherwise. */
2502 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2504 HOST_WIDE_INT cd
= 0, val
;
2507 if (!host_integerp (cst
, 0))
2509 val
= tree_low_cst (cst
, 0);
2511 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2513 step
= CHREC_RIGHT (chrec
);
2514 if (!host_integerp (step
, 0))
2516 cd
= gcd (cd
, tree_low_cst (step
, 0));
2517 chrec
= CHREC_LEFT (chrec
);
2520 return val
% cd
== 0;
2523 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2524 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2525 functions that describe the relation between the elements accessed
2526 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2529 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2532 analyze_miv_subscript (tree chrec_a
,
2534 conflict_function
**overlaps_a
,
2535 conflict_function
**overlaps_b
,
2536 tree
*last_conflicts
,
2537 struct loop
*loop_nest
)
2539 /* FIXME: This is a MIV subscript, not yet handled.
2540 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2543 In the SIV test we had to solve a Diophantine equation with two
2544 variables. In the MIV case we have to solve a Diophantine
2545 equation with 2*n variables (if the subscript uses n IVs).
2547 tree type
, difference
;
2549 dependence_stats
.num_miv
++;
2550 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2551 fprintf (dump_file
, "(analyze_miv_subscript \n");
2553 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2554 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2555 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2556 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2558 if (eq_evolutions_p (chrec_a
, chrec_b
))
2560 /* Access functions are the same: all the elements are accessed
2561 in the same order. */
2562 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2563 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2564 *last_conflicts
= estimated_loop_iterations_tree
2565 (get_chrec_loop (chrec_a
), true);
2566 dependence_stats
.num_miv_dependent
++;
2569 else if (evolution_function_is_constant_p (difference
)
2570 /* For the moment, the following is verified:
2571 evolution_function_is_affine_multivariate_p (chrec_a,
2573 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2575 /* testsuite/.../ssa-chrec-33.c
2576 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2578 The difference is 1, and all the evolution steps are multiples
2579 of 2, consequently there are no overlapping elements. */
2580 *overlaps_a
= conflict_fn_no_dependence ();
2581 *overlaps_b
= conflict_fn_no_dependence ();
2582 *last_conflicts
= integer_zero_node
;
2583 dependence_stats
.num_miv_independent
++;
2586 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2587 && !chrec_contains_symbols (chrec_a
)
2588 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2589 && !chrec_contains_symbols (chrec_b
))
2591 /* testsuite/.../ssa-chrec-35.c
2592 {0, +, 1}_2 vs. {0, +, 1}_3
2593 the overlapping elements are respectively located at iterations:
2594 {0, +, 1}_x and {0, +, 1}_x,
2595 in other words, we have the equality:
2596 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2599 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2600 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2602 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2603 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2605 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2606 overlaps_a
, overlaps_b
, last_conflicts
);
2608 if (CF_NOT_KNOWN_P (*overlaps_a
)
2609 || CF_NOT_KNOWN_P (*overlaps_b
))
2610 dependence_stats
.num_miv_unimplemented
++;
2611 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2612 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2613 dependence_stats
.num_miv_independent
++;
2615 dependence_stats
.num_miv_dependent
++;
2620 /* When the analysis is too difficult, answer "don't know". */
2621 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2622 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2624 *overlaps_a
= conflict_fn_not_known ();
2625 *overlaps_b
= conflict_fn_not_known ();
2626 *last_conflicts
= chrec_dont_know
;
2627 dependence_stats
.num_miv_unimplemented
++;
2630 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2631 fprintf (dump_file
, ")\n");
2634 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2635 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2636 OVERLAP_ITERATIONS_B are initialized with two functions that
2637 describe the iterations that contain conflicting elements.
2639 Remark: For an integer k >= 0, the following equality is true:
2641 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2645 analyze_overlapping_iterations (tree chrec_a
,
2647 conflict_function
**overlap_iterations_a
,
2648 conflict_function
**overlap_iterations_b
,
2649 tree
*last_conflicts
, struct loop
*loop_nest
)
2651 unsigned int lnn
= loop_nest
->num
;
2653 dependence_stats
.num_subscript_tests
++;
2655 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2657 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2658 fprintf (dump_file
, " (chrec_a = ");
2659 print_generic_expr (dump_file
, chrec_a
, 0);
2660 fprintf (dump_file
, ")\n (chrec_b = ");
2661 print_generic_expr (dump_file
, chrec_b
, 0);
2662 fprintf (dump_file
, ")\n");
2665 if (chrec_a
== NULL_TREE
2666 || chrec_b
== NULL_TREE
2667 || chrec_contains_undetermined (chrec_a
)
2668 || chrec_contains_undetermined (chrec_b
))
2670 dependence_stats
.num_subscript_undetermined
++;
2672 *overlap_iterations_a
= conflict_fn_not_known ();
2673 *overlap_iterations_b
= conflict_fn_not_known ();
2676 /* If they are the same chrec, and are affine, they overlap
2677 on every iteration. */
2678 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2679 && evolution_function_is_affine_multivariate_p (chrec_a
, lnn
))
2681 dependence_stats
.num_same_subscript_function
++;
2682 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2683 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2684 *last_conflicts
= chrec_dont_know
;
2687 /* If they aren't the same, and aren't affine, we can't do anything
2689 else if ((chrec_contains_symbols (chrec_a
)
2690 || chrec_contains_symbols (chrec_b
))
2691 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2692 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2694 dependence_stats
.num_subscript_undetermined
++;
2695 *overlap_iterations_a
= conflict_fn_not_known ();
2696 *overlap_iterations_b
= conflict_fn_not_known ();
2699 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2700 analyze_ziv_subscript (chrec_a
, chrec_b
,
2701 overlap_iterations_a
, overlap_iterations_b
,
2704 else if (siv_subscript_p (chrec_a
, chrec_b
))
2705 analyze_siv_subscript (chrec_a
, chrec_b
,
2706 overlap_iterations_a
, overlap_iterations_b
,
2707 last_conflicts
, lnn
);
2710 analyze_miv_subscript (chrec_a
, chrec_b
,
2711 overlap_iterations_a
, overlap_iterations_b
,
2712 last_conflicts
, loop_nest
);
2714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2716 fprintf (dump_file
, " (overlap_iterations_a = ");
2717 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2718 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2719 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2720 fprintf (dump_file
, ")\n");
2721 fprintf (dump_file
, ")\n");
2725 /* Helper function for uniquely inserting distance vectors. */
2728 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2733 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
2734 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2737 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2740 /* Helper function for uniquely inserting direction vectors. */
2743 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2748 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
2749 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2752 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2755 /* Add a distance of 1 on all the loops outer than INDEX. If we
2756 haven't yet determined a distance for this outer loop, push a new
2757 distance vector composed of the previous distance, and a distance
2758 of 1 for this outer loop. Example:
2766 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2767 save (0, 1), then we have to save (1, 0). */
2770 add_outer_distances (struct data_dependence_relation
*ddr
,
2771 lambda_vector dist_v
, int index
)
2773 /* For each outer loop where init_v is not set, the accesses are
2774 in dependence of distance 1 in the loop. */
2775 while (--index
>= 0)
2777 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2778 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2780 save_dist_v (ddr
, save_v
);
2784 /* Return false when fail to represent the data dependence as a
2785 distance vector. INIT_B is set to true when a component has been
2786 added to the distance vector DIST_V. INDEX_CARRY is then set to
2787 the index in DIST_V that carries the dependence. */
2790 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2791 struct data_reference
*ddr_a
,
2792 struct data_reference
*ddr_b
,
2793 lambda_vector dist_v
, bool *init_b
,
2797 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2799 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2801 tree access_fn_a
, access_fn_b
;
2802 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2804 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2806 non_affine_dependence_relation (ddr
);
2810 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2811 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2813 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2814 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2817 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2818 DDR_LOOP_NEST (ddr
));
2819 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2820 DDR_LOOP_NEST (ddr
));
2822 /* The dependence is carried by the outermost loop. Example:
2829 In this case, the dependence is carried by loop_1. */
2830 index
= index_a
< index_b
? index_a
: index_b
;
2831 *index_carry
= MIN (index
, *index_carry
);
2833 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2835 non_affine_dependence_relation (ddr
);
2839 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2841 /* This is the subscript coupling test. If we have already
2842 recorded a distance for this loop (a distance coming from
2843 another subscript), it should be the same. For example,
2844 in the following code, there is no dependence:
2851 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2853 finalize_ddr_dependent (ddr
, chrec_known
);
2857 dist_v
[index
] = dist
;
2861 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2863 /* This can be for example an affine vs. constant dependence
2864 (T[i] vs. T[3]) that is not an affine dependence and is
2865 not representable as a distance vector. */
2866 non_affine_dependence_relation (ddr
);
2874 /* Return true when the DDR contains only constant access functions. */
2877 constant_access_functions (const struct data_dependence_relation
*ddr
)
2881 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2882 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2883 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2889 /* Helper function for the case where DDR_A and DDR_B are the same
2890 multivariate access function with a constant step. For an example
2894 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2897 tree c_1
= CHREC_LEFT (c_2
);
2898 tree c_0
= CHREC_LEFT (c_1
);
2899 lambda_vector dist_v
;
2902 /* Polynomials with more than 2 variables are not handled yet. When
2903 the evolution steps are parameters, it is not possible to
2904 represent the dependence using classical distance vectors. */
2905 if (TREE_CODE (c_0
) != INTEGER_CST
2906 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
2907 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
2909 DDR_AFFINE_P (ddr
) = false;
2913 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2914 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2916 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2917 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2918 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2919 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2932 save_dist_v (ddr
, dist_v
);
2934 add_outer_distances (ddr
, dist_v
, x_1
);
2937 /* Helper function for the case where DDR_A and DDR_B are the same
2938 access functions. */
2941 add_other_self_distances (struct data_dependence_relation
*ddr
)
2943 lambda_vector dist_v
;
2945 int index_carry
= DDR_NB_LOOPS (ddr
);
2947 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2949 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
2951 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
2953 if (!evolution_function_is_univariate_p (access_fun
))
2955 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
2957 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2961 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
2963 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
2964 add_multivariate_self_dist (ddr
, access_fun
);
2966 /* The evolution step is not constant: it varies in
2967 the outer loop, so this cannot be represented by a
2968 distance vector. For example in pr34635.c the
2969 evolution is {0, +, {0, +, 4}_1}_2. */
2970 DDR_AFFINE_P (ddr
) = false;
2975 index_carry
= MIN (index_carry
,
2976 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
2977 DDR_LOOP_NEST (ddr
)));
2981 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2982 add_outer_distances (ddr
, dist_v
, index_carry
);
2986 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
2988 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2990 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
2991 save_dist_v (ddr
, dist_v
);
2994 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2995 is the case for example when access functions are the same and
2996 equal to a constant, as in:
3003 in which case the distance vectors are (0) and (1). */
3006 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
3010 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3012 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
3013 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
3014 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
3016 for (j
= 0; j
< ca
->n
; j
++)
3017 if (affine_function_zero_p (ca
->fns
[j
]))
3019 insert_innermost_unit_dist_vector (ddr
);
3023 for (j
= 0; j
< cb
->n
; j
++)
3024 if (affine_function_zero_p (cb
->fns
[j
]))
3026 insert_innermost_unit_dist_vector (ddr
);
3032 /* Compute the classic per loop distance vector. DDR is the data
3033 dependence relation to build a vector from. Return false when fail
3034 to represent the data dependence as a distance vector. */
3037 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3038 struct loop
*loop_nest
)
3040 bool init_b
= false;
3041 int index_carry
= DDR_NB_LOOPS (ddr
);
3042 lambda_vector dist_v
;
3044 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3047 if (same_access_functions (ddr
))
3049 /* Save the 0 vector. */
3050 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3051 save_dist_v (ddr
, dist_v
);
3053 if (constant_access_functions (ddr
))
3054 add_distance_for_zero_overlaps (ddr
);
3056 if (DDR_NB_LOOPS (ddr
) > 1)
3057 add_other_self_distances (ddr
);
3062 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3063 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3064 dist_v
, &init_b
, &index_carry
))
3067 /* Save the distance vector if we initialized one. */
3070 /* Verify a basic constraint: classic distance vectors should
3071 always be lexicographically positive.
3073 Data references are collected in the order of execution of
3074 the program, thus for the following loop
3076 | for (i = 1; i < 100; i++)
3077 | for (j = 1; j < 100; j++)
3079 | t = T[j+1][i-1]; // A
3080 | T[j][i] = t + 2; // B
3083 references are collected following the direction of the wind:
3084 A then B. The data dependence tests are performed also
3085 following this order, such that we're looking at the distance
3086 separating the elements accessed by A from the elements later
3087 accessed by B. But in this example, the distance returned by
3088 test_dep (A, B) is lexicographically negative (-1, 1), that
3089 means that the access A occurs later than B with respect to
3090 the outer loop, ie. we're actually looking upwind. In this
3091 case we solve test_dep (B, A) looking downwind to the
3092 lexicographically positive solution, that returns the
3093 distance vector (1, -1). */
3094 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3096 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3097 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3100 compute_subscript_distance (ddr
);
3101 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3102 save_v
, &init_b
, &index_carry
))
3104 save_dist_v (ddr
, save_v
);
3105 DDR_REVERSED_P (ddr
) = true;
3107 /* In this case there is a dependence forward for all the
3110 | for (k = 1; k < 100; k++)
3111 | for (i = 1; i < 100; i++)
3112 | for (j = 1; j < 100; j++)
3114 | t = T[j+1][i-1]; // A
3115 | T[j][i] = t + 2; // B
3123 if (DDR_NB_LOOPS (ddr
) > 1)
3125 add_outer_distances (ddr
, save_v
, index_carry
);
3126 add_outer_distances (ddr
, dist_v
, index_carry
);
3131 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3132 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3134 if (DDR_NB_LOOPS (ddr
) > 1)
3136 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3138 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3139 DDR_A (ddr
), loop_nest
))
3141 compute_subscript_distance (ddr
);
3142 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3143 opposite_v
, &init_b
,
3147 save_dist_v (ddr
, save_v
);
3148 add_outer_distances (ddr
, dist_v
, index_carry
);
3149 add_outer_distances (ddr
, opposite_v
, index_carry
);
3152 save_dist_v (ddr
, save_v
);
3157 /* There is a distance of 1 on all the outer loops: Example:
3158 there is a dependence of distance 1 on loop_1 for the array A.
3164 add_outer_distances (ddr
, dist_v
,
3165 lambda_vector_first_nz (dist_v
,
3166 DDR_NB_LOOPS (ddr
), 0));
3169 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3173 fprintf (dump_file
, "(build_classic_dist_vector\n");
3174 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3176 fprintf (dump_file
, " dist_vector = (");
3177 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3178 DDR_NB_LOOPS (ddr
));
3179 fprintf (dump_file
, " )\n");
3181 fprintf (dump_file
, ")\n");
3187 /* Return the direction for a given distance.
3188 FIXME: Computing dir this way is suboptimal, since dir can catch
3189 cases that dist is unable to represent. */
3191 static inline enum data_dependence_direction
3192 dir_from_dist (int dist
)
3195 return dir_positive
;
3197 return dir_negative
;
3202 /* Compute the classic per loop direction vector. DDR is the data
3203 dependence relation to build a vector from. */
3206 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3209 lambda_vector dist_v
;
3211 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3213 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3215 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3216 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3218 save_dir_v (ddr
, dir_v
);
3222 /* Helper function. Returns true when there is a dependence between
3223 data references DRA and DRB. */
3226 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3227 struct data_reference
*dra
,
3228 struct data_reference
*drb
,
3229 struct loop
*loop_nest
)
3232 tree last_conflicts
;
3233 struct subscript
*subscript
;
3235 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3238 conflict_function
*overlaps_a
, *overlaps_b
;
3240 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3241 DR_ACCESS_FN (drb
, i
),
3242 &overlaps_a
, &overlaps_b
,
3243 &last_conflicts
, loop_nest
);
3245 if (CF_NOT_KNOWN_P (overlaps_a
)
3246 || CF_NOT_KNOWN_P (overlaps_b
))
3248 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3249 dependence_stats
.num_dependence_undetermined
++;
3250 free_conflict_function (overlaps_a
);
3251 free_conflict_function (overlaps_b
);
3255 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3256 || CF_NO_DEPENDENCE_P (overlaps_b
))
3258 finalize_ddr_dependent (ddr
, chrec_known
);
3259 dependence_stats
.num_dependence_independent
++;
3260 free_conflict_function (overlaps_a
);
3261 free_conflict_function (overlaps_b
);
3267 if (SUB_CONFLICTS_IN_A (subscript
))
3268 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3269 if (SUB_CONFLICTS_IN_B (subscript
))
3270 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3272 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3273 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3274 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3281 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3284 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3285 struct loop
*loop_nest
)
3288 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3289 fprintf (dump_file
, "(subscript_dependence_tester \n");
3291 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3292 dependence_stats
.num_dependence_dependent
++;
3294 compute_subscript_distance (ddr
);
3295 if (build_classic_dist_vector (ddr
, loop_nest
))
3296 build_classic_dir_vector (ddr
);
3298 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3299 fprintf (dump_file
, ")\n");
3302 /* Returns true when all the access functions of A are affine or
3303 constant with respect to LOOP_NEST. */
3306 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3307 const struct loop
*loop_nest
)
3310 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3313 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
3314 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3315 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3321 /* Return true if we can create an affine data-ref for OP in STMT. */
3324 stmt_simple_memref_p (struct loop
*loop
, gimple stmt
, tree op
)
3326 data_reference_p dr
;
3329 dr
= create_data_ref (loop
, op
, stmt
, true);
3330 if (!access_functions_are_affine_or_constant_p (dr
, loop
))
3337 /* Initializes an equation for an OMEGA problem using the information
3338 contained in the ACCESS_FUN. Returns true when the operation
3341 PB is the omega constraint system.
3342 EQ is the number of the equation to be initialized.
3343 OFFSET is used for shifting the variables names in the constraints:
3344 a constrain is composed of 2 * the number of variables surrounding
3345 dependence accesses. OFFSET is set either to 0 for the first n variables,
3346 then it is set to n.
3347 ACCESS_FUN is expected to be an affine chrec. */
3350 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3351 unsigned int offset
, tree access_fun
,
3352 struct data_dependence_relation
*ddr
)
3354 switch (TREE_CODE (access_fun
))
3356 case POLYNOMIAL_CHREC
:
3358 tree left
= CHREC_LEFT (access_fun
);
3359 tree right
= CHREC_RIGHT (access_fun
);
3360 int var
= CHREC_VARIABLE (access_fun
);
3363 if (TREE_CODE (right
) != INTEGER_CST
)
3366 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3367 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3369 /* Compute the innermost loop index. */
3370 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3373 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3374 += int_cst_value (right
);
3376 switch (TREE_CODE (left
))
3378 case POLYNOMIAL_CHREC
:
3379 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3382 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3391 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3399 /* As explained in the comments preceding init_omega_for_ddr, we have
3400 to set up a system for each loop level, setting outer loops
3401 variation to zero, and current loop variation to positive or zero.
3402 Save each lexico positive distance vector. */
3405 omega_extract_distance_vectors (omega_pb pb
,
3406 struct data_dependence_relation
*ddr
)
3410 struct loop
*loopi
, *loopj
;
3411 enum omega_result res
;
3413 /* Set a new problem for each loop in the nest. The basis is the
3414 problem that we have initialized until now. On top of this we
3415 add new constraints. */
3416 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3417 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3420 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3421 DDR_NB_LOOPS (ddr
));
3423 omega_copy_problem (copy
, pb
);
3425 /* For all the outer loops "loop_j", add "dj = 0". */
3427 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3429 eq
= omega_add_zero_eq (copy
, omega_black
);
3430 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3433 /* For "loop_i", add "0 <= di". */
3434 geq
= omega_add_zero_geq (copy
, omega_black
);
3435 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3437 /* Reduce the constraint system, and test that the current
3438 problem is feasible. */
3439 res
= omega_simplify_problem (copy
);
3440 if (res
== omega_false
3441 || res
== omega_unknown
3442 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3445 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3446 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3448 dist
= copy
->subs
[eq
].coef
[0];
3454 /* Reinitialize problem... */
3455 omega_copy_problem (copy
, pb
);
3457 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3459 eq
= omega_add_zero_eq (copy
, omega_black
);
3460 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3463 /* ..., but this time "di = 1". */
3464 eq
= omega_add_zero_eq (copy
, omega_black
);
3465 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3466 copy
->eqs
[eq
].coef
[0] = -1;
3468 res
= omega_simplify_problem (copy
);
3469 if (res
== omega_false
3470 || res
== omega_unknown
3471 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3474 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3475 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3477 dist
= copy
->subs
[eq
].coef
[0];
3483 /* Save the lexicographically positive distance vector. */
3486 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3487 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3491 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3492 if (copy
->subs
[eq
].key
> 0)
3494 dist
= copy
->subs
[eq
].coef
[0];
3495 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3498 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3499 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3501 save_dist_v (ddr
, dist_v
);
3502 save_dir_v (ddr
, dir_v
);
3506 omega_free_problem (copy
);
3510 /* This is called for each subscript of a tuple of data references:
3511 insert an equality for representing the conflicts. */
3514 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3515 struct data_dependence_relation
*ddr
,
3516 omega_pb pb
, bool *maybe_dependent
)
3519 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3520 TREE_TYPE (access_fun_b
));
3521 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3522 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3523 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3525 /* When the fun_a - fun_b is not constant, the dependence is not
3526 captured by the classic distance vector representation. */
3527 if (TREE_CODE (difference
) != INTEGER_CST
)
3531 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3533 /* There is no dependence. */
3534 *maybe_dependent
= false;
3538 fun_b
= chrec_fold_multiply (type
, fun_b
, integer_minus_one_node
);
3540 eq
= omega_add_zero_eq (pb
, omega_black
);
3541 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3542 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3543 /* There is probably a dependence, but the system of
3544 constraints cannot be built: answer "don't know". */
3548 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3549 && !int_divides_p (lambda_vector_gcd
3550 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3551 2 * DDR_NB_LOOPS (ddr
)),
3552 pb
->eqs
[eq
].coef
[0]))
3554 /* There is no dependence. */
3555 *maybe_dependent
= false;
3562 /* Helper function, same as init_omega_for_ddr but specialized for
3563 data references A and B. */
3566 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3567 struct data_dependence_relation
*ddr
,
3568 omega_pb pb
, bool *maybe_dependent
)
3573 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3575 /* Insert an equality per subscript. */
3576 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3578 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3579 ddr
, pb
, maybe_dependent
))
3581 else if (*maybe_dependent
== false)
3583 /* There is no dependence. */
3584 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3589 /* Insert inequalities: constraints corresponding to the iteration
3590 domain, i.e. the loops surrounding the references "loop_x" and
3591 the distance variables "dx". The layout of the OMEGA
3592 representation is as follows:
3593 - coef[0] is the constant
3594 - coef[1..nb_loops] are the protected variables that will not be
3595 removed by the solver: the "dx"
3596 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3598 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3599 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3601 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3604 ineq
= omega_add_zero_geq (pb
, omega_black
);
3605 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3607 /* 0 <= loop_x + dx */
3608 ineq
= omega_add_zero_geq (pb
, omega_black
);
3609 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3610 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3614 /* loop_x <= nb_iters */
3615 ineq
= omega_add_zero_geq (pb
, omega_black
);
3616 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3617 pb
->geqs
[ineq
].coef
[0] = nbi
;
3619 /* loop_x + dx <= nb_iters */
3620 ineq
= omega_add_zero_geq (pb
, omega_black
);
3621 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3622 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3623 pb
->geqs
[ineq
].coef
[0] = nbi
;
3625 /* A step "dx" bigger than nb_iters is not feasible, so
3626 add "0 <= nb_iters + dx", */
3627 ineq
= omega_add_zero_geq (pb
, omega_black
);
3628 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3629 pb
->geqs
[ineq
].coef
[0] = nbi
;
3630 /* and "dx <= nb_iters". */
3631 ineq
= omega_add_zero_geq (pb
, omega_black
);
3632 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3633 pb
->geqs
[ineq
].coef
[0] = nbi
;
3637 omega_extract_distance_vectors (pb
, ddr
);
3642 /* Sets up the Omega dependence problem for the data dependence
3643 relation DDR. Returns false when the constraint system cannot be
3644 built, ie. when the test answers "don't know". Returns true
3645 otherwise, and when independence has been proved (using one of the
3646 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3647 set MAYBE_DEPENDENT to true.
3649 Example: for setting up the dependence system corresponding to the
3650 conflicting accesses
3655 | ... A[2*j, 2*(i + j)]
3659 the following constraints come from the iteration domain:
3666 where di, dj are the distance variables. The constraints
3667 representing the conflicting elements are:
3670 i + 1 = 2 * (i + di + j + dj)
3672 For asking that the resulting distance vector (di, dj) be
3673 lexicographically positive, we insert the constraint "di >= 0". If
3674 "di = 0" in the solution, we fix that component to zero, and we
3675 look at the inner loops: we set a new problem where all the outer
3676 loop distances are zero, and fix this inner component to be
3677 positive. When one of the components is positive, we save that
3678 distance, and set a new problem where the distance on this loop is
3679 zero, searching for other distances in the inner loops. Here is
3680 the classic example that illustrates that we have to set for each
3681 inner loop a new problem:
3689 we have to save two distances (1, 0) and (0, 1).
3691 Given two array references, refA and refB, we have to set the
3692 dependence problem twice, refA vs. refB and refB vs. refA, and we
3693 cannot do a single test, as refB might occur before refA in the
3694 inner loops, and the contrary when considering outer loops: ex.
3699 | T[{1,+,1}_2][{1,+,1}_1] // refA
3700 | T[{2,+,1}_2][{0,+,1}_1] // refB
3705 refB touches the elements in T before refA, and thus for the same
3706 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3707 but for successive loop_0 iterations, we have (1, -1, 1)
3709 The Omega solver expects the distance variables ("di" in the
3710 previous example) to come first in the constraint system (as
3711 variables to be protected, or "safe" variables), the constraint
3712 system is built using the following layout:
3714 "cst | distance vars | index vars".
3718 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3719 bool *maybe_dependent
)
3724 *maybe_dependent
= true;
3726 if (same_access_functions (ddr
))
3729 lambda_vector dir_v
;
3731 /* Save the 0 vector. */
3732 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3733 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3734 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3735 dir_v
[j
] = dir_equal
;
3736 save_dir_v (ddr
, dir_v
);
3738 /* Save the dependences carried by outer loops. */
3739 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3740 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3742 omega_free_problem (pb
);
3746 /* Omega expects the protected variables (those that have to be kept
3747 after elimination) to appear first in the constraint system.
3748 These variables are the distance variables. In the following
3749 initialization we declare NB_LOOPS safe variables, and the total
3750 number of variables for the constraint system is 2*NB_LOOPS. */
3751 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3752 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3754 omega_free_problem (pb
);
3756 /* Stop computation if not decidable, or no dependence. */
3757 if (res
== false || *maybe_dependent
== false)
3760 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3761 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3763 omega_free_problem (pb
);
3768 /* Return true when DDR contains the same information as that stored
3769 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3772 ddr_consistent_p (FILE *file
,
3773 struct data_dependence_relation
*ddr
,
3774 VEC (lambda_vector
, heap
) *dist_vects
,
3775 VEC (lambda_vector
, heap
) *dir_vects
)
3779 /* If dump_file is set, output there. */
3780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3783 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3785 lambda_vector b_dist_v
;
3786 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3787 VEC_length (lambda_vector
, dist_vects
),
3788 DDR_NUM_DIST_VECTS (ddr
));
3790 fprintf (file
, "Banerjee dist vectors:\n");
3791 for (i
= 0; VEC_iterate (lambda_vector
, dist_vects
, i
, b_dist_v
); i
++)
3792 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3794 fprintf (file
, "Omega dist vectors:\n");
3795 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3796 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3798 fprintf (file
, "data dependence relation:\n");
3799 dump_data_dependence_relation (file
, ddr
);
3801 fprintf (file
, ")\n");
3805 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3807 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3808 VEC_length (lambda_vector
, dir_vects
),
3809 DDR_NUM_DIR_VECTS (ddr
));
3813 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3815 lambda_vector a_dist_v
;
3816 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3818 /* Distance vectors are not ordered in the same way in the DDR
3819 and in the DIST_VECTS: search for a matching vector. */
3820 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, a_dist_v
); j
++)
3821 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3824 if (j
== VEC_length (lambda_vector
, dist_vects
))
3826 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3827 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3828 fprintf (file
, "not found in Omega dist vectors:\n");
3829 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3830 fprintf (file
, "data dependence relation:\n");
3831 dump_data_dependence_relation (file
, ddr
);
3832 fprintf (file
, ")\n");
3836 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3838 lambda_vector a_dir_v
;
3839 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3841 /* Direction vectors are not ordered in the same way in the DDR
3842 and in the DIR_VECTS: search for a matching vector. */
3843 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, a_dir_v
); j
++)
3844 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3847 if (j
== VEC_length (lambda_vector
, dist_vects
))
3849 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3850 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3851 fprintf (file
, "not found in Omega dir vectors:\n");
3852 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3853 fprintf (file
, "data dependence relation:\n");
3854 dump_data_dependence_relation (file
, ddr
);
3855 fprintf (file
, ")\n");
3862 /* This computes the affine dependence relation between A and B with
3863 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3864 independence between two accesses, while CHREC_DONT_KNOW is used
3865 for representing the unknown relation.
3867 Note that it is possible to stop the computation of the dependence
3868 relation the first time we detect a CHREC_KNOWN element for a given
3872 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3873 struct loop
*loop_nest
)
3875 struct data_reference
*dra
= DDR_A (ddr
);
3876 struct data_reference
*drb
= DDR_B (ddr
);
3878 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3880 fprintf (dump_file
, "(compute_affine_dependence\n");
3881 fprintf (dump_file
, " (stmt_a = \n");
3882 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, 0);
3883 fprintf (dump_file
, ")\n (stmt_b = \n");
3884 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, 0);
3885 fprintf (dump_file
, ")\n");
3888 /* Analyze only when the dependence relation is not yet known. */
3889 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
3890 && !DDR_SELF_REFERENCE (ddr
))
3892 dependence_stats
.num_dependence_tests
++;
3894 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3895 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3897 if (flag_check_data_deps
)
3899 /* Compute the dependences using the first algorithm. */
3900 subscript_dependence_tester (ddr
, loop_nest
);
3902 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3904 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3905 dump_data_dependence_relation (dump_file
, ddr
);
3908 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3910 bool maybe_dependent
;
3911 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3913 /* Save the result of the first DD analyzer. */
3914 dist_vects
= DDR_DIST_VECTS (ddr
);
3915 dir_vects
= DDR_DIR_VECTS (ddr
);
3917 /* Reset the information. */
3918 DDR_DIST_VECTS (ddr
) = NULL
;
3919 DDR_DIR_VECTS (ddr
) = NULL
;
3921 /* Compute the same information using Omega. */
3922 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3923 goto csys_dont_know
;
3925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3927 fprintf (dump_file
, "Omega Analyzer\n");
3928 dump_data_dependence_relation (dump_file
, ddr
);
3931 /* Check that we get the same information. */
3932 if (maybe_dependent
)
3933 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3938 subscript_dependence_tester (ddr
, loop_nest
);
3941 /* As a last case, if the dependence cannot be determined, or if
3942 the dependence is considered too difficult to determine, answer
3947 dependence_stats
.num_dependence_undetermined
++;
3949 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3951 fprintf (dump_file
, "Data ref a:\n");
3952 dump_data_reference (dump_file
, dra
);
3953 fprintf (dump_file
, "Data ref b:\n");
3954 dump_data_reference (dump_file
, drb
);
3955 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3957 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3961 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3962 fprintf (dump_file
, ")\n");
3965 /* This computes the dependence relation for the same data
3966 reference into DDR. */
3969 compute_self_dependence (struct data_dependence_relation
*ddr
)
3972 struct subscript
*subscript
;
3974 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3977 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3980 if (SUB_CONFLICTS_IN_A (subscript
))
3981 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3982 if (SUB_CONFLICTS_IN_B (subscript
))
3983 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3985 /* The accessed index overlaps for each iteration. */
3986 SUB_CONFLICTS_IN_A (subscript
)
3987 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3988 SUB_CONFLICTS_IN_B (subscript
)
3989 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3990 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3993 /* The distance vector is the zero vector. */
3994 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3995 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3998 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3999 the data references in DATAREFS, in the LOOP_NEST. When
4000 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4004 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
4005 VEC (ddr_p
, heap
) **dependence_relations
,
4006 VEC (loop_p
, heap
) *loop_nest
,
4007 bool compute_self_and_rr
)
4009 struct data_dependence_relation
*ddr
;
4010 struct data_reference
*a
, *b
;
4013 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4014 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
4015 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
4017 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4018 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4019 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
4022 if (compute_self_and_rr
)
4023 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4025 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4026 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4027 compute_self_dependence (ddr
);
4031 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4032 true if STMT clobbers memory, false otherwise. */
4035 get_references_in_stmt (gimple stmt
, VEC (data_ref_loc
, heap
) **references
)
4037 bool clobbers_memory
= false;
4040 enum gimple_code stmt_code
= gimple_code (stmt
);
4044 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4045 Calls have side-effects, except those to const or pure
4047 if ((stmt_code
== GIMPLE_CALL
4048 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4049 || (stmt_code
== GIMPLE_ASM
4050 && gimple_asm_volatile_p (stmt
)))
4051 clobbers_memory
= true;
4053 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
4054 return clobbers_memory
;
4056 if (stmt_code
== GIMPLE_ASSIGN
)
4059 op0
= gimple_assign_lhs_ptr (stmt
);
4060 op1
= gimple_assign_rhs1_ptr (stmt
);
4063 || (REFERENCE_CLASS_P (*op1
)
4064 && (base
= get_base_address (*op1
))
4065 && TREE_CODE (base
) != SSA_NAME
))
4067 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4069 ref
->is_read
= true;
4073 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4075 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4077 ref
->is_read
= false;
4080 else if (stmt_code
== GIMPLE_CALL
)
4082 unsigned i
, n
= gimple_call_num_args (stmt
);
4084 for (i
= 0; i
< n
; i
++)
4086 op0
= gimple_call_arg_ptr (stmt
, i
);
4089 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4091 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4093 ref
->is_read
= true;
4098 return clobbers_memory
;
4101 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4102 reference, returns false, otherwise returns true. NEST is the outermost
4103 loop of the loop nest in which the references should be analyzed. */
4106 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4107 VEC (data_reference_p
, heap
) **datarefs
)
4110 VEC (data_ref_loc
, heap
) *references
;
4113 data_reference_p dr
;
4115 if (get_references_in_stmt (stmt
, &references
))
4117 VEC_free (data_ref_loc
, heap
, references
);
4121 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
4123 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4124 gcc_assert (dr
!= NULL
);
4126 /* FIXME -- data dependence analysis does not work correctly for objects with
4127 invariant addresses. Let us fail here until the problem is fixed. */
4128 if (dr_address_invariant_p (dr
))
4131 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4132 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
4137 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4139 VEC_free (data_ref_loc
, heap
, references
);
4143 /* Search the data references in LOOP, and record the information into
4144 DATAREFS. Returns chrec_dont_know when failing to analyze a
4145 difficult case, returns NULL_TREE otherwise.
4147 TODO: This function should be made smarter so that it can handle address
4148 arithmetic as if they were array accesses, etc. */
4151 find_data_references_in_loop (struct loop
*loop
,
4152 VEC (data_reference_p
, heap
) **datarefs
)
4154 basic_block bb
, *bbs
;
4156 gimple_stmt_iterator bsi
;
4158 bbs
= get_loop_body_in_dom_order (loop
);
4160 for (i
= 0; i
< loop
->num_nodes
; i
++)
4164 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4166 gimple stmt
= gsi_stmt (bsi
);
4168 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4170 struct data_reference
*res
;
4171 res
= XCNEW (struct data_reference
);
4172 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4175 return chrec_dont_know
;
4184 /* Recursive helper function. */
4187 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4189 /* Inner loops of the nest should not contain siblings. Example:
4190 when there are two consecutive loops,
4201 the dependence relation cannot be captured by the distance
4206 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4208 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4212 /* Return false when the LOOP is not well nested. Otherwise return
4213 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4214 contain the loops from the outermost to the innermost, as they will
4215 appear in the classic distance vector. */
4218 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4220 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4222 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4226 /* Returns true when the data dependences have been computed, false otherwise.
4227 Given a loop nest LOOP, the following vectors are returned:
4228 DATAREFS is initialized to all the array elements contained in this loop,
4229 DEPENDENCE_RELATIONS contains the relations between the data references.
4230 Compute read-read and self relations if
4231 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4234 compute_data_dependences_for_loop (struct loop
*loop
,
4235 bool compute_self_and_read_read_dependences
,
4236 VEC (data_reference_p
, heap
) **datarefs
,
4237 VEC (ddr_p
, heap
) **dependence_relations
)
4240 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4242 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4244 /* If the loop nest is not well formed, or one of the data references
4245 is not computable, give up without spending time to compute other
4248 || !find_loop_nest (loop
, &vloops
)
4249 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4251 struct data_dependence_relation
*ddr
;
4253 /* Insert a single relation into dependence_relations:
4255 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4256 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4260 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4261 compute_self_and_read_read_dependences
);
4263 if (dump_file
&& (dump_flags
& TDF_STATS
))
4265 fprintf (dump_file
, "Dependence tester statistics:\n");
4267 fprintf (dump_file
, "Number of dependence tests: %d\n",
4268 dependence_stats
.num_dependence_tests
);
4269 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4270 dependence_stats
.num_dependence_dependent
);
4271 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4272 dependence_stats
.num_dependence_independent
);
4273 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4274 dependence_stats
.num_dependence_undetermined
);
4276 fprintf (dump_file
, "Number of subscript tests: %d\n",
4277 dependence_stats
.num_subscript_tests
);
4278 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4279 dependence_stats
.num_subscript_undetermined
);
4280 fprintf (dump_file
, "Number of same subscript function: %d\n",
4281 dependence_stats
.num_same_subscript_function
);
4283 fprintf (dump_file
, "Number of ziv tests: %d\n",
4284 dependence_stats
.num_ziv
);
4285 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4286 dependence_stats
.num_ziv_dependent
);
4287 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4288 dependence_stats
.num_ziv_independent
);
4289 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4290 dependence_stats
.num_ziv_unimplemented
);
4292 fprintf (dump_file
, "Number of siv tests: %d\n",
4293 dependence_stats
.num_siv
);
4294 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4295 dependence_stats
.num_siv_dependent
);
4296 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4297 dependence_stats
.num_siv_independent
);
4298 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4299 dependence_stats
.num_siv_unimplemented
);
4301 fprintf (dump_file
, "Number of miv tests: %d\n",
4302 dependence_stats
.num_miv
);
4303 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4304 dependence_stats
.num_miv_dependent
);
4305 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4306 dependence_stats
.num_miv_independent
);
4307 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4308 dependence_stats
.num_miv_unimplemented
);
4314 /* Entry point (for testing only). Analyze all the data references
4315 and the dependence relations in LOOP.
4317 The data references are computed first.
4319 A relation on these nodes is represented by a complete graph. Some
4320 of the relations could be of no interest, thus the relations can be
4323 In the following function we compute all the relations. This is
4324 just a first implementation that is here for:
4325 - for showing how to ask for the dependence relations,
4326 - for the debugging the whole dependence graph,
4327 - for the dejagnu testcases and maintenance.
4329 It is possible to ask only for a part of the graph, avoiding to
4330 compute the whole dependence graph. The computed dependences are
4331 stored in a knowledge base (KB) such that later queries don't
4332 recompute the same information. The implementation of this KB is
4333 transparent to the optimizer, and thus the KB can be changed with a
4334 more efficient implementation, or the KB could be disabled. */
4336 analyze_all_data_dependences (struct loop
*loop
)
4339 int nb_data_refs
= 10;
4340 VEC (data_reference_p
, heap
) *datarefs
=
4341 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4342 VEC (ddr_p
, heap
) *dependence_relations
=
4343 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4345 /* Compute DDs on the whole function. */
4346 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4347 &dependence_relations
);
4351 dump_data_dependence_relations (dump_file
, dependence_relations
);
4352 fprintf (dump_file
, "\n\n");
4354 if (dump_flags
& TDF_DETAILS
)
4355 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4357 if (dump_flags
& TDF_STATS
)
4359 unsigned nb_top_relations
= 0;
4360 unsigned nb_bot_relations
= 0;
4361 unsigned nb_basename_differ
= 0;
4362 unsigned nb_chrec_relations
= 0;
4363 struct data_dependence_relation
*ddr
;
4365 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4367 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4370 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4372 struct data_reference
*a
= DDR_A (ddr
);
4373 struct data_reference
*b
= DDR_B (ddr
);
4375 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
4376 nb_basename_differ
++;
4382 nb_chrec_relations
++;
4385 gather_stats_on_scev_database ();
4389 free_dependence_relations (dependence_relations
);
4390 free_data_refs (datarefs
);
4393 /* Computes all the data dependences and check that the results of
4394 several analyzers are the same. */
4397 tree_check_data_deps (void)
4400 struct loop
*loop_nest
;
4402 FOR_EACH_LOOP (li
, loop_nest
, 0)
4403 analyze_all_data_dependences (loop_nest
);
4406 /* Free the memory used by a data dependence relation DDR. */
4409 free_dependence_relation (struct data_dependence_relation
*ddr
)
4414 if (DDR_SUBSCRIPTS (ddr
))
4415 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4416 if (DDR_DIST_VECTS (ddr
))
4417 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4418 if (DDR_DIR_VECTS (ddr
))
4419 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4424 /* Free the memory used by the data dependence relations from
4425 DEPENDENCE_RELATIONS. */
4428 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4431 struct data_dependence_relation
*ddr
;
4432 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4434 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4438 if (loop_nest
== NULL
)
4439 loop_nest
= DDR_LOOP_NEST (ddr
);
4441 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4442 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4443 free_dependence_relation (ddr
);
4447 VEC_free (loop_p
, heap
, loop_nest
);
4448 VEC_free (ddr_p
, heap
, dependence_relations
);
4451 /* Free the memory used by the data references from DATAREFS. */
4454 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4457 struct data_reference
*dr
;
4459 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4461 VEC_free (data_reference_p
, heap
, datarefs
);
4466 /* Dump vertex I in RDG to FILE. */
4469 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4471 struct vertex
*v
= &(rdg
->vertices
[i
]);
4472 struct graph_edge
*e
;
4474 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4475 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4476 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4479 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4480 fprintf (file
, " %d", e
->src
);
4482 fprintf (file
, ") (out:");
4485 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4486 fprintf (file
, " %d", e
->dest
);
4488 fprintf (file
, ") \n");
4489 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4490 fprintf (file
, ")\n");
4493 /* Call dump_rdg_vertex on stderr. */
4496 debug_rdg_vertex (struct graph
*rdg
, int i
)
4498 dump_rdg_vertex (stderr
, rdg
, i
);
4501 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4502 dumped vertices to that bitmap. */
4504 void dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4508 fprintf (file
, "(%d\n", c
);
4510 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4511 if (rdg
->vertices
[i
].component
== c
)
4514 bitmap_set_bit (dumped
, i
);
4516 dump_rdg_vertex (file
, rdg
, i
);
4519 fprintf (file
, ")\n");
4522 /* Call dump_rdg_vertex on stderr. */
4525 debug_rdg_component (struct graph
*rdg
, int c
)
4527 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4530 /* Dump the reduced dependence graph RDG to FILE. */
4533 dump_rdg (FILE *file
, struct graph
*rdg
)
4536 bitmap dumped
= BITMAP_ALLOC (NULL
);
4538 fprintf (file
, "(rdg\n");
4540 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4541 if (!bitmap_bit_p (dumped
, i
))
4542 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4544 fprintf (file
, ")\n");
4545 BITMAP_FREE (dumped
);
4548 /* Call dump_rdg on stderr. */
4551 debug_rdg (struct graph
*rdg
)
4553 dump_rdg (stderr
, rdg
);
4557 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
4561 fprintf (file
, "digraph RDG {\n");
4563 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4565 struct vertex
*v
= &(rdg
->vertices
[i
]);
4566 struct graph_edge
*e
;
4568 /* Highlight reads from memory. */
4569 if (RDG_MEM_READS_STMT (rdg
, i
))
4570 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
4572 /* Highlight stores to memory. */
4573 if (RDG_MEM_WRITE_STMT (rdg
, i
))
4574 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
4577 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4578 switch (RDGE_TYPE (e
))
4581 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
4585 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
4589 /* These are the most common dependences: don't print these. */
4590 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
4594 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
4602 fprintf (file
, "}\n\n");
4605 /* Display SCOP using dotty. */
4608 dot_rdg (struct graph
*rdg
)
4610 FILE *file
= fopen ("/tmp/rdg.dot", "w");
4611 gcc_assert (file
!= NULL
);
4613 dot_rdg_1 (file
, rdg
);
4616 system ("dotty /tmp/rdg.dot");
4620 /* This structure is used for recording the mapping statement index in
4623 struct rdg_vertex_info
GTY(())
4629 /* Returns the index of STMT in RDG. */
4632 rdg_vertex_for_stmt (struct graph
*rdg
, gimple stmt
)
4634 struct rdg_vertex_info rvi
, *slot
;
4637 slot
= (struct rdg_vertex_info
*) htab_find (rdg
->indices
, &rvi
);
4645 /* Creates an edge in RDG for each distance vector from DDR. The
4646 order that we keep track of in the RDG is the order in which
4647 statements have to be executed. */
4650 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4652 struct graph_edge
*e
;
4654 data_reference_p dra
= DDR_A (ddr
);
4655 data_reference_p drb
= DDR_B (ddr
);
4656 unsigned level
= ddr_dependence_level (ddr
);
4658 /* For non scalar dependences, when the dependence is REVERSED,
4659 statement B has to be executed before statement A. */
4661 && !DDR_REVERSED_P (ddr
))
4663 data_reference_p tmp
= dra
;
4668 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4669 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4671 if (va
< 0 || vb
< 0)
4674 e
= add_edge (rdg
, va
, vb
);
4675 e
->data
= XNEW (struct rdg_edge
);
4677 RDGE_LEVEL (e
) = level
;
4678 RDGE_RELATION (e
) = ddr
;
4680 /* Determines the type of the data dependence. */
4681 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4682 RDGE_TYPE (e
) = input_dd
;
4683 else if (!DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4684 RDGE_TYPE (e
) = output_dd
;
4685 else if (!DR_IS_READ (dra
) && DR_IS_READ (drb
))
4686 RDGE_TYPE (e
) = flow_dd
;
4687 else if (DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4688 RDGE_TYPE (e
) = anti_dd
;
4691 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4692 the index of DEF in RDG. */
4695 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4697 use_operand_p imm_use_p
;
4698 imm_use_iterator iterator
;
4700 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4702 struct graph_edge
*e
;
4703 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4708 e
= add_edge (rdg
, idef
, use
);
4709 e
->data
= XNEW (struct rdg_edge
);
4710 RDGE_TYPE (e
) = flow_dd
;
4711 RDGE_RELATION (e
) = NULL
;
4715 /* Creates the edges of the reduced dependence graph RDG. */
4718 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4721 struct data_dependence_relation
*ddr
;
4722 def_operand_p def_p
;
4725 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
4726 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4727 create_rdg_edge_for_ddr (rdg
, ddr
);
4729 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4730 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4732 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4735 /* Build the vertices of the reduced dependence graph RDG. */
4738 create_rdg_vertices (struct graph
*rdg
, VEC (gimple
, heap
) *stmts
)
4743 for (i
= 0; VEC_iterate (gimple
, stmts
, i
, stmt
); i
++)
4745 VEC (data_ref_loc
, heap
) *references
;
4747 struct vertex
*v
= &(rdg
->vertices
[i
]);
4748 struct rdg_vertex_info
*rvi
= XNEW (struct rdg_vertex_info
);
4749 struct rdg_vertex_info
**slot
;
4753 slot
= (struct rdg_vertex_info
**) htab_find_slot (rdg
->indices
, rvi
, INSERT
);
4760 v
->data
= XNEW (struct rdg_vertex
);
4761 RDG_STMT (rdg
, i
) = stmt
;
4763 RDG_MEM_WRITE_STMT (rdg
, i
) = false;
4764 RDG_MEM_READS_STMT (rdg
, i
) = false;
4765 if (gimple_code (stmt
) == GIMPLE_PHI
)
4768 get_references_in_stmt (stmt
, &references
);
4769 for (j
= 0; VEC_iterate (data_ref_loc
, references
, j
, ref
); j
++)
4771 RDG_MEM_WRITE_STMT (rdg
, i
) = true;
4773 RDG_MEM_READS_STMT (rdg
, i
) = true;
4775 VEC_free (data_ref_loc
, heap
, references
);
4779 /* Initialize STMTS with all the statements of LOOP. When
4780 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4781 which we discover statements is important as
4782 generate_loops_for_partition is using the same traversal for
4783 identifying statements. */
4786 stmts_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4789 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4791 for (i
= 0; i
< loop
->num_nodes
; i
++)
4793 basic_block bb
= bbs
[i
];
4794 gimple_stmt_iterator bsi
;
4797 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4798 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4800 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4802 stmt
= gsi_stmt (bsi
);
4803 if (gimple_code (stmt
) != GIMPLE_LABEL
)
4804 VEC_safe_push (gimple
, heap
, *stmts
, stmt
);
4811 /* Returns true when all the dependences are computable. */
4814 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
4819 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4820 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4826 /* Computes a hash function for element ELT. */
4829 hash_stmt_vertex_info (const void *elt
)
4831 const struct rdg_vertex_info
*const rvi
=
4832 (const struct rdg_vertex_info
*) elt
;
4833 gimple stmt
= rvi
->stmt
;
4835 return htab_hash_pointer (stmt
);
4838 /* Compares database elements E1 and E2. */
4841 eq_stmt_vertex_info (const void *e1
, const void *e2
)
4843 const struct rdg_vertex_info
*elt1
= (const struct rdg_vertex_info
*) e1
;
4844 const struct rdg_vertex_info
*elt2
= (const struct rdg_vertex_info
*) e2
;
4846 return elt1
->stmt
== elt2
->stmt
;
4849 /* Free the element E. */
4852 hash_stmt_vertex_del (void *e
)
4857 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4858 statement of the loop nest, and one edge per data dependence or
4859 scalar dependence. */
4862 build_empty_rdg (int n_stmts
)
4864 int nb_data_refs
= 10;
4865 struct graph
*rdg
= new_graph (n_stmts
);
4867 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4868 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4872 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4873 statement of the loop nest, and one edge per data dependence or
4874 scalar dependence. */
4877 build_rdg (struct loop
*loop
)
4879 int nb_data_refs
= 10;
4880 struct graph
*rdg
= NULL
;
4881 VEC (ddr_p
, heap
) *dependence_relations
;
4882 VEC (data_reference_p
, heap
) *datarefs
;
4883 VEC (gimple
, heap
) *stmts
= VEC_alloc (gimple
, heap
, nb_data_refs
);
4885 dependence_relations
= VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
) ;
4886 datarefs
= VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4887 compute_data_dependences_for_loop (loop
,
4890 &dependence_relations
);
4892 if (!known_dependences_p (dependence_relations
))
4894 free_dependence_relations (dependence_relations
);
4895 free_data_refs (datarefs
);
4896 VEC_free (gimple
, heap
, stmts
);
4901 stmts_from_loop (loop
, &stmts
);
4902 rdg
= build_empty_rdg (VEC_length (gimple
, stmts
));
4904 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4905 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4906 create_rdg_vertices (rdg
, stmts
);
4907 create_rdg_edges (rdg
, dependence_relations
);
4909 VEC_free (gimple
, heap
, stmts
);
4913 /* Free the reduced dependence graph RDG. */
4916 free_rdg (struct graph
*rdg
)
4920 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4921 free (rdg
->vertices
[i
].data
);
4923 htab_delete (rdg
->indices
);
4927 /* Initialize STMTS with all the statements of LOOP that contain a
4931 stores_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4934 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4936 for (i
= 0; i
< loop
->num_nodes
; i
++)
4938 basic_block bb
= bbs
[i
];
4939 gimple_stmt_iterator bsi
;
4941 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4942 if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi
), SSA_OP_VDEF
))
4943 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4949 /* For a data reference REF, return the declaration of its base
4950 address or NULL_TREE if the base is not determined. */
4953 ref_base_address (gimple stmt
, data_ref_loc
*ref
)
4955 tree base
= NULL_TREE
;
4957 struct data_reference
*dr
= XCNEW (struct data_reference
);
4959 DR_STMT (dr
) = stmt
;
4960 DR_REF (dr
) = *ref
->pos
;
4961 dr_analyze_innermost (dr
);
4962 base_address
= DR_BASE_ADDRESS (dr
);
4967 switch (TREE_CODE (base_address
))
4970 base
= TREE_OPERAND (base_address
, 0);
4974 base
= base_address
;
4983 /* Determines whether the statement from vertex V of the RDG has a
4984 definition used outside the loop that contains this statement. */
4987 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
4989 gimple stmt
= RDG_STMT (rdg
, v
);
4990 struct loop
*loop
= loop_containing_stmt (stmt
);
4991 use_operand_p imm_use_p
;
4992 imm_use_iterator iterator
;
4994 def_operand_p def_p
;
4999 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
5001 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
5003 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)
5011 /* Determines whether statements S1 and S2 access to similar memory
5012 locations. Two memory accesses are considered similar when they
5013 have the same base address declaration, i.e. when their
5014 ref_base_address is the same. */
5017 have_similar_memory_accesses (gimple s1
, gimple s2
)
5021 VEC (data_ref_loc
, heap
) *refs1
, *refs2
;
5022 data_ref_loc
*ref1
, *ref2
;
5024 get_references_in_stmt (s1
, &refs1
);
5025 get_references_in_stmt (s2
, &refs2
);
5027 for (i
= 0; VEC_iterate (data_ref_loc
, refs1
, i
, ref1
); i
++)
5029 tree base1
= ref_base_address (s1
, ref1
);
5032 for (j
= 0; VEC_iterate (data_ref_loc
, refs2
, j
, ref2
); j
++)
5033 if (base1
== ref_base_address (s2
, ref2
))
5041 VEC_free (data_ref_loc
, heap
, refs1
);
5042 VEC_free (data_ref_loc
, heap
, refs2
);
5046 /* Helper function for the hashtab. */
5049 have_similar_memory_accesses_1 (const void *s1
, const void *s2
)
5051 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple
) s1
),
5052 CONST_CAST_GIMPLE ((const_gimple
) s2
));
5055 /* Helper function for the hashtab. */
5058 ref_base_address_1 (const void *s
)
5060 gimple stmt
= CONST_CAST_GIMPLE ((const_gimple
) s
);
5062 VEC (data_ref_loc
, heap
) *refs
;
5066 get_references_in_stmt (stmt
, &refs
);
5068 for (i
= 0; VEC_iterate (data_ref_loc
, refs
, i
, ref
); i
++)
5071 res
= htab_hash_pointer (ref_base_address (stmt
, ref
));
5075 VEC_free (data_ref_loc
, heap
, refs
);
5079 /* Try to remove duplicated write data references from STMTS. */
5082 remove_similar_memory_refs (VEC (gimple
, heap
) **stmts
)
5086 htab_t seen
= htab_create (VEC_length (gimple
, *stmts
), ref_base_address_1
,
5087 have_similar_memory_accesses_1
, NULL
);
5089 for (i
= 0; VEC_iterate (gimple
, *stmts
, i
, stmt
); )
5093 slot
= htab_find_slot (seen
, stmt
, INSERT
);
5096 VEC_ordered_remove (gimple
, *stmts
, i
);
5099 *slot
= (void *) stmt
;
5107 /* Returns the index of PARAMETER in the parameters vector of the
5108 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5111 access_matrix_get_index_for_parameter (tree parameter
,
5112 struct access_matrix
*access_matrix
)
5115 VEC (tree
,heap
) *lambda_parameters
= AM_PARAMETERS (access_matrix
);
5116 tree lambda_parameter
;
5118 for (i
= 0; VEC_iterate (tree
, lambda_parameters
, i
, lambda_parameter
); i
++)
5119 if (lambda_parameter
== parameter
)
5120 return i
+ AM_NB_INDUCTION_VARS (access_matrix
);