1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass walks a given loop structure searching for array
22 references. The information about the array accesses is recorded
23 in DATA_REFERENCE structures.
25 The basic test for determining the dependences is:
26 given two access functions chrec1 and chrec2 to a same array, and
27 x and y two vectors from the iteration domain, the same element of
28 the array is accessed twice at iterations x and y if and only if:
29 | chrec1 (x) == chrec2 (y).
31 The goals of this analysis are:
33 - to determine the independence: the relation between two
34 independent accesses is qualified with the chrec_known (this
35 information allows a loop parallelization),
37 - when two data references access the same data, to qualify the
38 dependence relation with classic dependence representations:
42 - loop carried level dependence
43 - polyhedron dependence
44 or with the chains of recurrences based representation,
46 - to define a knowledge base for storing the data dependence
49 - to define an interface to access this data.
54 - subscript: given two array accesses a subscript is the tuple
55 composed of the access functions for a given dimension. Example:
56 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
57 (f1, g1), (f2, g2), (f3, g3).
59 - Diophantine equation: an equation whose coefficients and
60 solutions are integer constants, for example the equation
62 has an integer solution x = 1 and y = -1.
66 - "Advanced Compilation for High Performance Computing" by Randy
67 Allen and Ken Kennedy.
68 http://citeseer.ist.psu.edu/goff91practical.html
70 - "Loop Transformations for Restructuring Compilers - The Foundations"
78 #include "coretypes.h"
83 /* These RTL headers are needed for basic-block.h. */
85 #include "basic-block.h"
86 #include "diagnostic.h"
87 #include "tree-flow.h"
88 #include "tree-dump.h"
91 #include "tree-data-ref.h"
92 #include "tree-scalar-evolution.h"
93 #include "tree-pass.h"
94 #include "langhooks.h"
96 static struct datadep_stats
98 int num_dependence_tests
;
99 int num_dependence_dependent
;
100 int num_dependence_independent
;
101 int num_dependence_undetermined
;
103 int num_subscript_tests
;
104 int num_subscript_undetermined
;
105 int num_same_subscript_function
;
108 int num_ziv_independent
;
109 int num_ziv_dependent
;
110 int num_ziv_unimplemented
;
113 int num_siv_independent
;
114 int num_siv_dependent
;
115 int num_siv_unimplemented
;
118 int num_miv_independent
;
119 int num_miv_dependent
;
120 int num_miv_unimplemented
;
123 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
124 struct data_reference
*,
125 struct data_reference
*,
127 /* Returns true iff A divides B. */
130 tree_fold_divides_p (const_tree a
, const_tree b
)
132 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
133 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
134 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
, 0));
137 /* Returns true iff A divides B. */
140 int_divides_p (int a
, int b
)
142 return ((b
% a
) == 0);
147 /* Dump into FILE all the data references from DATAREFS. */
150 dump_data_references (FILE *file
, VEC (data_reference_p
, heap
) *datarefs
)
153 struct data_reference
*dr
;
155 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
156 dump_data_reference (file
, dr
);
159 /* Dump to STDERR all the dependence relations from DDRS. */
162 debug_data_dependence_relations (VEC (ddr_p
, heap
) *ddrs
)
164 dump_data_dependence_relations (stderr
, ddrs
);
167 /* Dump into FILE all the dependence relations from DDRS. */
170 dump_data_dependence_relations (FILE *file
,
171 VEC (ddr_p
, heap
) *ddrs
)
174 struct data_dependence_relation
*ddr
;
176 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
177 dump_data_dependence_relation (file
, ddr
);
180 /* Dump function for a DATA_REFERENCE structure. */
183 dump_data_reference (FILE *outf
,
184 struct data_reference
*dr
)
188 fprintf (outf
, "(Data Ref: \n stmt: ");
189 print_gimple_stmt (outf
, DR_STMT (dr
), 0, 0);
190 fprintf (outf
, " ref: ");
191 print_generic_stmt (outf
, DR_REF (dr
), 0);
192 fprintf (outf
, " base_object: ");
193 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
195 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
197 fprintf (outf
, " Access function %d: ", i
);
198 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
200 fprintf (outf
, ")\n");
203 /* Dumps the affine function described by FN to the file OUTF. */
206 dump_affine_function (FILE *outf
, affine_fn fn
)
211 print_generic_expr (outf
, VEC_index (tree
, fn
, 0), TDF_SLIM
);
212 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
214 fprintf (outf
, " + ");
215 print_generic_expr (outf
, coef
, TDF_SLIM
);
216 fprintf (outf
, " * x_%u", i
);
220 /* Dumps the conflict function CF to the file OUTF. */
223 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
227 if (cf
->n
== NO_DEPENDENCE
)
228 fprintf (outf
, "no dependence\n");
229 else if (cf
->n
== NOT_KNOWN
)
230 fprintf (outf
, "not known\n");
233 for (i
= 0; i
< cf
->n
; i
++)
236 dump_affine_function (outf
, cf
->fns
[i
]);
237 fprintf (outf
, "]\n");
242 /* Dump function for a SUBSCRIPT structure. */
245 dump_subscript (FILE *outf
, struct subscript
*subscript
)
247 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
249 fprintf (outf
, "\n (subscript \n");
250 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
251 dump_conflict_function (outf
, cf
);
252 if (CF_NONTRIVIAL_P (cf
))
254 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
255 fprintf (outf
, " last_conflict: ");
256 print_generic_stmt (outf
, last_iteration
, 0);
259 cf
= SUB_CONFLICTS_IN_B (subscript
);
260 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
261 dump_conflict_function (outf
, cf
);
262 if (CF_NONTRIVIAL_P (cf
))
264 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
265 fprintf (outf
, " last_conflict: ");
266 print_generic_stmt (outf
, last_iteration
, 0);
269 fprintf (outf
, " (Subscript distance: ");
270 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
271 fprintf (outf
, " )\n");
272 fprintf (outf
, " )\n");
275 /* Print the classic direction vector DIRV to OUTF. */
278 print_direction_vector (FILE *outf
,
284 for (eq
= 0; eq
< length
; eq
++)
286 enum data_dependence_direction dir
= dirv
[eq
];
291 fprintf (outf
, " +");
294 fprintf (outf
, " -");
297 fprintf (outf
, " =");
299 case dir_positive_or_equal
:
300 fprintf (outf
, " +=");
302 case dir_positive_or_negative
:
303 fprintf (outf
, " +-");
305 case dir_negative_or_equal
:
306 fprintf (outf
, " -=");
309 fprintf (outf
, " *");
312 fprintf (outf
, "indep");
316 fprintf (outf
, "\n");
319 /* Print a vector of direction vectors. */
322 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
328 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
329 print_direction_vector (outf
, v
, length
);
332 /* Print a vector of distance vectors. */
335 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
341 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
342 print_lambda_vector (outf
, v
, length
);
348 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
350 dump_data_dependence_relation (stderr
, ddr
);
353 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
356 dump_data_dependence_relation (FILE *outf
,
357 struct data_dependence_relation
*ddr
)
359 struct data_reference
*dra
, *drb
;
361 fprintf (outf
, "(Data Dep: \n");
363 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
365 fprintf (outf
, " (don't know)\n)\n");
371 dump_data_reference (outf
, dra
);
372 dump_data_reference (outf
, drb
);
374 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
375 fprintf (outf
, " (no dependence)\n");
377 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
382 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
384 fprintf (outf
, " access_fn_A: ");
385 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
386 fprintf (outf
, " access_fn_B: ");
387 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
388 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
391 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
392 fprintf (outf
, " loop nest: (");
393 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
394 fprintf (outf
, "%d ", loopi
->num
);
395 fprintf (outf
, ")\n");
397 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
399 fprintf (outf
, " distance_vector: ");
400 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
404 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
406 fprintf (outf
, " direction_vector: ");
407 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
412 fprintf (outf
, ")\n");
415 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
418 dump_data_dependence_direction (FILE *file
,
419 enum data_dependence_direction dir
)
435 case dir_positive_or_negative
:
436 fprintf (file
, "+-");
439 case dir_positive_or_equal
:
440 fprintf (file
, "+=");
443 case dir_negative_or_equal
:
444 fprintf (file
, "-=");
456 /* Dumps the distance and direction vectors in FILE. DDRS contains
457 the dependence relations, and VECT_SIZE is the size of the
458 dependence vectors, or in other words the number of loops in the
462 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
465 struct data_dependence_relation
*ddr
;
468 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
469 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
471 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
473 fprintf (file
, "DISTANCE_V (");
474 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
475 fprintf (file
, ")\n");
478 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
480 fprintf (file
, "DIRECTION_V (");
481 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
482 fprintf (file
, ")\n");
486 fprintf (file
, "\n\n");
489 /* Dumps the data dependence relations DDRS in FILE. */
492 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
495 struct data_dependence_relation
*ddr
;
497 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
498 dump_data_dependence_relation (file
, ddr
);
500 fprintf (file
, "\n\n");
503 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
504 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
505 constant of type ssizetype, and returns true. If we cannot do this
506 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
510 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
511 tree
*var
, tree
*off
)
515 enum tree_code ocode
= code
;
523 *var
= build_int_cst (type
, 0);
524 *off
= fold_convert (ssizetype
, op0
);
527 case POINTER_PLUS_EXPR
:
532 split_constant_offset (op0
, &var0
, &off0
);
533 split_constant_offset (op1
, &var1
, &off1
);
534 *var
= fold_build2 (code
, type
, var0
, var1
);
535 *off
= size_binop (ocode
, off0
, off1
);
539 if (TREE_CODE (op1
) != INTEGER_CST
)
542 split_constant_offset (op0
, &var0
, &off0
);
543 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
544 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
550 HOST_WIDE_INT pbitsize
, pbitpos
;
551 enum machine_mode pmode
;
552 int punsignedp
, pvolatilep
;
554 op0
= TREE_OPERAND (op0
, 0);
555 if (!handled_component_p (op0
))
558 base
= get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
,
559 &pmode
, &punsignedp
, &pvolatilep
, false);
561 if (pbitpos
% BITS_PER_UNIT
!= 0)
563 base
= build_fold_addr_expr (base
);
564 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
568 split_constant_offset (poffset
, &poffset
, &off1
);
569 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
570 if (POINTER_TYPE_P (TREE_TYPE (base
)))
571 base
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (base
),
572 base
, fold_convert (sizetype
, poffset
));
574 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
575 fold_convert (TREE_TYPE (base
), poffset
));
578 var0
= fold_convert (type
, base
);
580 /* If variable length types are involved, punt, otherwise casts
581 might be converted into ARRAY_REFs in gimplify_conversion.
582 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
583 possibly no longer appears in current GIMPLE, might resurface.
584 This perhaps could run
585 if (CONVERT_EXPR_P (var0))
587 gimplify_conversion (&var0);
588 // Attempt to fill in any within var0 found ARRAY_REF's
589 // element size from corresponding op embedded ARRAY_REF,
590 // if unsuccessful, just punt.
592 while (POINTER_TYPE_P (type
))
593 type
= TREE_TYPE (type
);
594 if (int_size_in_bytes (type
) < 0)
604 gimple def_stmt
= SSA_NAME_DEF_STMT (op0
);
605 enum tree_code subcode
;
607 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
610 var0
= gimple_assign_rhs1 (def_stmt
);
611 subcode
= gimple_assign_rhs_code (def_stmt
);
612 var1
= gimple_assign_rhs2 (def_stmt
);
614 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
622 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
623 will be ssizetype. */
626 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
628 tree type
= TREE_TYPE (exp
), otype
, op0
, op1
, e
, o
;
632 *off
= ssize_int (0);
635 if (automatically_generated_chrec_p (exp
))
638 otype
= TREE_TYPE (exp
);
639 code
= TREE_CODE (exp
);
640 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
641 if (split_constant_offset_1 (otype
, op0
, code
, op1
, &e
, &o
))
643 *var
= fold_convert (type
, e
);
648 /* Returns the address ADDR of an object in a canonical shape (without nop
649 casts, and with type of pointer to the object). */
652 canonicalize_base_object_address (tree addr
)
658 /* The base address may be obtained by casting from integer, in that case
660 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
663 if (TREE_CODE (addr
) != ADDR_EXPR
)
666 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
669 /* Analyzes the behavior of the memory reference DR in the innermost loop that
670 contains it. Returns true if analysis succeed or false otherwise. */
673 dr_analyze_innermost (struct data_reference
*dr
)
675 gimple stmt
= DR_STMT (dr
);
676 struct loop
*loop
= loop_containing_stmt (stmt
);
677 tree ref
= DR_REF (dr
);
678 HOST_WIDE_INT pbitsize
, pbitpos
;
680 enum machine_mode pmode
;
681 int punsignedp
, pvolatilep
;
682 affine_iv base_iv
, offset_iv
;
683 tree init
, dinit
, step
;
685 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
686 fprintf (dump_file
, "analyze_innermost: ");
688 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
689 &pmode
, &punsignedp
, &pvolatilep
, false);
690 gcc_assert (base
!= NULL_TREE
);
692 if (pbitpos
% BITS_PER_UNIT
!= 0)
694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
695 fprintf (dump_file
, "failed: bit offset alignment.\n");
699 base
= build_fold_addr_expr (base
);
700 if (!simple_iv (loop
, stmt
, base
, &base_iv
, false))
702 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
703 fprintf (dump_file
, "failed: evolution of base is not affine.\n");
708 offset_iv
.base
= ssize_int (0);
709 offset_iv
.step
= ssize_int (0);
711 else if (!simple_iv (loop
, stmt
, poffset
, &offset_iv
, false))
713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
714 fprintf (dump_file
, "failed: evolution of offset is not affine.\n");
718 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
719 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
720 init
= size_binop (PLUS_EXPR
, init
, dinit
);
721 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
722 init
= size_binop (PLUS_EXPR
, init
, dinit
);
724 step
= size_binop (PLUS_EXPR
,
725 fold_convert (ssizetype
, base_iv
.step
),
726 fold_convert (ssizetype
, offset_iv
.step
));
728 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
730 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
734 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
736 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
737 fprintf (dump_file
, "success.\n");
742 /* Determines the base object and the list of indices of memory reference
743 DR, analyzed in loop nest NEST. */
746 dr_analyze_indices (struct data_reference
*dr
, struct loop
*nest
)
748 gimple stmt
= DR_STMT (dr
);
749 struct loop
*loop
= loop_containing_stmt (stmt
);
750 VEC (tree
, heap
) *access_fns
= NULL
;
751 tree ref
= unshare_expr (DR_REF (dr
)), aref
= ref
, op
;
752 tree base
, off
, access_fn
;
753 basic_block before_loop
= block_before_loop (nest
);
755 while (handled_component_p (aref
))
757 if (TREE_CODE (aref
) == ARRAY_REF
)
759 op
= TREE_OPERAND (aref
, 1);
760 access_fn
= analyze_scalar_evolution (loop
, op
);
761 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
762 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
764 TREE_OPERAND (aref
, 1) = build_int_cst (TREE_TYPE (op
), 0);
767 aref
= TREE_OPERAND (aref
, 0);
770 if (INDIRECT_REF_P (aref
))
772 op
= TREE_OPERAND (aref
, 0);
773 access_fn
= analyze_scalar_evolution (loop
, op
);
774 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
775 base
= initial_condition (access_fn
);
776 split_constant_offset (base
, &base
, &off
);
777 access_fn
= chrec_replace_initial_condition (access_fn
,
778 fold_convert (TREE_TYPE (base
), off
));
780 TREE_OPERAND (aref
, 0) = base
;
781 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
784 DR_BASE_OBJECT (dr
) = ref
;
785 DR_ACCESS_FNS (dr
) = access_fns
;
788 /* Extracts the alias analysis information from the memory reference DR. */
791 dr_analyze_alias (struct data_reference
*dr
)
793 gimple stmt
= DR_STMT (dr
);
794 tree ref
= DR_REF (dr
);
795 tree base
= get_base_address (ref
), addr
, smt
= NULL_TREE
;
802 else if (INDIRECT_REF_P (base
))
804 addr
= TREE_OPERAND (base
, 0);
805 if (TREE_CODE (addr
) == SSA_NAME
)
807 smt
= symbol_mem_tag (SSA_NAME_VAR (addr
));
808 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
812 DR_SYMBOL_TAG (dr
) = smt
;
814 vops
= BITMAP_ALLOC (NULL
);
815 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, it
, SSA_OP_VIRTUAL_USES
)
817 bitmap_set_bit (vops
, DECL_UID (SSA_NAME_VAR (op
)));
823 /* Returns true if the address of DR is invariant. */
826 dr_address_invariant_p (struct data_reference
*dr
)
831 for (i
= 0; VEC_iterate (tree
, DR_ACCESS_FNS (dr
), i
, idx
); i
++)
832 if (tree_contains_chrecs (idx
, NULL
))
838 /* Frees data reference DR. */
841 free_data_ref (data_reference_p dr
)
843 BITMAP_FREE (DR_VOPS (dr
));
844 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
848 /* Analyzes memory reference MEMREF accessed in STMT. The reference
849 is read if IS_READ is true, write otherwise. Returns the
850 data_reference description of MEMREF. NEST is the outermost loop of the
851 loop nest in that the reference should be analyzed. */
853 struct data_reference
*
854 create_data_ref (struct loop
*nest
, tree memref
, gimple stmt
, bool is_read
)
856 struct data_reference
*dr
;
858 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
860 fprintf (dump_file
, "Creating dr for ");
861 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
862 fprintf (dump_file
, "\n");
865 dr
= XCNEW (struct data_reference
);
867 DR_REF (dr
) = memref
;
868 DR_IS_READ (dr
) = is_read
;
870 dr_analyze_innermost (dr
);
871 dr_analyze_indices (dr
, nest
);
872 dr_analyze_alias (dr
);
874 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 fprintf (dump_file
, "\tbase_address: ");
877 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
878 fprintf (dump_file
, "\n\toffset from base address: ");
879 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
880 fprintf (dump_file
, "\n\tconstant offset from base address: ");
881 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
882 fprintf (dump_file
, "\n\tstep: ");
883 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
884 fprintf (dump_file
, "\n\taligned to: ");
885 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
886 fprintf (dump_file
, "\n\tbase_object: ");
887 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
888 fprintf (dump_file
, "\n\tsymbol tag: ");
889 print_generic_expr (dump_file
, DR_SYMBOL_TAG (dr
), TDF_SLIM
);
890 fprintf (dump_file
, "\n");
896 /* Returns true if FNA == FNB. */
899 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
901 unsigned i
, n
= VEC_length (tree
, fna
);
903 if (n
!= VEC_length (tree
, fnb
))
906 for (i
= 0; i
< n
; i
++)
907 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
908 VEC_index (tree
, fnb
, i
), 0))
914 /* If all the functions in CF are the same, returns one of them,
915 otherwise returns NULL. */
918 common_affine_function (conflict_function
*cf
)
923 if (!CF_NONTRIVIAL_P (cf
))
928 for (i
= 1; i
< cf
->n
; i
++)
929 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
935 /* Returns the base of the affine function FN. */
938 affine_function_base (affine_fn fn
)
940 return VEC_index (tree
, fn
, 0);
943 /* Returns true if FN is a constant. */
946 affine_function_constant_p (affine_fn fn
)
951 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
952 if (!integer_zerop (coef
))
958 /* Returns true if FN is the zero constant function. */
961 affine_function_zero_p (affine_fn fn
)
963 return (integer_zerop (affine_function_base (fn
))
964 && affine_function_constant_p (fn
));
967 /* Returns a signed integer type with the largest precision from TA
971 signed_type_for_types (tree ta
, tree tb
)
973 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
974 return signed_type_for (ta
);
976 return signed_type_for (tb
);
979 /* Applies operation OP on affine functions FNA and FNB, and returns the
983 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
989 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
991 n
= VEC_length (tree
, fna
);
992 m
= VEC_length (tree
, fnb
);
996 n
= VEC_length (tree
, fnb
);
997 m
= VEC_length (tree
, fna
);
1000 ret
= VEC_alloc (tree
, heap
, m
);
1001 for (i
= 0; i
< n
; i
++)
1003 tree type
= signed_type_for_types (TREE_TYPE (VEC_index (tree
, fna
, i
)),
1004 TREE_TYPE (VEC_index (tree
, fnb
, i
)));
1006 VEC_quick_push (tree
, ret
,
1007 fold_build2 (op
, type
,
1008 VEC_index (tree
, fna
, i
),
1009 VEC_index (tree
, fnb
, i
)));
1012 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
1013 VEC_quick_push (tree
, ret
,
1014 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1015 coef
, integer_zero_node
));
1016 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
1017 VEC_quick_push (tree
, ret
,
1018 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1019 integer_zero_node
, coef
));
1024 /* Returns the sum of affine functions FNA and FNB. */
1027 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1029 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1032 /* Returns the difference of affine functions FNA and FNB. */
1035 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1037 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1040 /* Frees affine function FN. */
1043 affine_fn_free (affine_fn fn
)
1045 VEC_free (tree
, heap
, fn
);
1048 /* Determine for each subscript in the data dependence relation DDR
1052 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1054 conflict_function
*cf_a
, *cf_b
;
1055 affine_fn fn_a
, fn_b
, diff
;
1057 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1061 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1063 struct subscript
*subscript
;
1065 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1066 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1067 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1069 fn_a
= common_affine_function (cf_a
);
1070 fn_b
= common_affine_function (cf_b
);
1073 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1076 diff
= affine_fn_minus (fn_a
, fn_b
);
1078 if (affine_function_constant_p (diff
))
1079 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1081 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1083 affine_fn_free (diff
);
1088 /* Returns the conflict function for "unknown". */
1090 static conflict_function
*
1091 conflict_fn_not_known (void)
1093 conflict_function
*fn
= XCNEW (conflict_function
);
1099 /* Returns the conflict function for "independent". */
1101 static conflict_function
*
1102 conflict_fn_no_dependence (void)
1104 conflict_function
*fn
= XCNEW (conflict_function
);
1105 fn
->n
= NO_DEPENDENCE
;
1110 /* Returns true if the address of OBJ is invariant in LOOP. */
1113 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1115 while (handled_component_p (obj
))
1117 if (TREE_CODE (obj
) == ARRAY_REF
)
1119 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1120 need to check the stride and the lower bound of the reference. */
1121 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1123 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1127 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1129 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1133 obj
= TREE_OPERAND (obj
, 0);
1136 if (!INDIRECT_REF_P (obj
))
1139 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1143 /* Returns true if A and B are accesses to different objects, or to different
1144 fields of the same object. */
1147 disjoint_objects_p (tree a
, tree b
)
1149 tree base_a
, base_b
;
1150 VEC (tree
, heap
) *comp_a
= NULL
, *comp_b
= NULL
;
1153 base_a
= get_base_address (a
);
1154 base_b
= get_base_address (b
);
1158 && base_a
!= base_b
)
1161 if (!operand_equal_p (base_a
, base_b
, 0))
1164 /* Compare the component references of A and B. We must start from the inner
1165 ones, so record them to the vector first. */
1166 while (handled_component_p (a
))
1168 VEC_safe_push (tree
, heap
, comp_a
, a
);
1169 a
= TREE_OPERAND (a
, 0);
1171 while (handled_component_p (b
))
1173 VEC_safe_push (tree
, heap
, comp_b
, b
);
1174 b
= TREE_OPERAND (b
, 0);
1180 if (VEC_length (tree
, comp_a
) == 0
1181 || VEC_length (tree
, comp_b
) == 0)
1184 a
= VEC_pop (tree
, comp_a
);
1185 b
= VEC_pop (tree
, comp_b
);
1187 /* Real and imaginary part of a variable do not alias. */
1188 if ((TREE_CODE (a
) == REALPART_EXPR
1189 && TREE_CODE (b
) == IMAGPART_EXPR
)
1190 || (TREE_CODE (a
) == IMAGPART_EXPR
1191 && TREE_CODE (b
) == REALPART_EXPR
))
1197 if (TREE_CODE (a
) != TREE_CODE (b
))
1200 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1201 DR_BASE_OBJECT are always zero. */
1202 if (TREE_CODE (a
) == ARRAY_REF
)
1204 else if (TREE_CODE (a
) == COMPONENT_REF
)
1206 if (operand_equal_p (TREE_OPERAND (a
, 1), TREE_OPERAND (b
, 1), 0))
1209 /* Different fields of unions may overlap. */
1210 base_a
= TREE_OPERAND (a
, 0);
1211 if (TREE_CODE (TREE_TYPE (base_a
)) == UNION_TYPE
)
1214 /* Different fields of structures cannot. */
1222 VEC_free (tree
, heap
, comp_a
);
1223 VEC_free (tree
, heap
, comp_b
);
1228 /* Returns false if we can prove that data references A and B do not alias,
1232 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
)
1234 const_tree addr_a
= DR_BASE_ADDRESS (a
);
1235 const_tree addr_b
= DR_BASE_ADDRESS (b
);
1236 const_tree type_a
, type_b
;
1237 const_tree decl_a
= NULL_TREE
, decl_b
= NULL_TREE
;
1239 /* If the sets of virtual operands are disjoint, the memory references do not
1241 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
1244 /* If the accessed objects are disjoint, the memory references do not
1246 if (disjoint_objects_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
)))
1249 if (!addr_a
|| !addr_b
)
1252 /* If the references are based on different static objects, they cannot alias
1253 (PTA should be able to disambiguate such accesses, but often it fails to,
1254 since currently we cannot distinguish between pointer and offset in pointer
1256 if (TREE_CODE (addr_a
) == ADDR_EXPR
1257 && TREE_CODE (addr_b
) == ADDR_EXPR
)
1258 return TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0);
1260 /* An instruction writing through a restricted pointer is "independent" of any
1261 instruction reading or writing through a different restricted pointer,
1262 in the same block/scope. */
1264 type_a
= TREE_TYPE (addr_a
);
1265 type_b
= TREE_TYPE (addr_b
);
1266 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
1268 if (TREE_CODE (addr_a
) == SSA_NAME
)
1269 decl_a
= SSA_NAME_VAR (addr_a
);
1270 if (TREE_CODE (addr_b
) == SSA_NAME
)
1271 decl_b
= SSA_NAME_VAR (addr_b
);
1273 if (TYPE_RESTRICT (type_a
) && TYPE_RESTRICT (type_b
)
1274 && (!DR_IS_READ (a
) || !DR_IS_READ (b
))
1275 && decl_a
&& DECL_P (decl_a
)
1276 && decl_b
&& DECL_P (decl_b
)
1278 && TREE_CODE (DECL_CONTEXT (decl_a
)) == FUNCTION_DECL
1279 && DECL_CONTEXT (decl_a
) == DECL_CONTEXT (decl_b
))
1285 static void compute_self_dependence (struct data_dependence_relation
*);
1287 /* Initialize a data dependence relation between data accesses A and
1288 B. NB_LOOPS is the number of loops surrounding the references: the
1289 size of the classic distance/direction vectors. */
1291 static struct data_dependence_relation
*
1292 initialize_data_dependence_relation (struct data_reference
*a
,
1293 struct data_reference
*b
,
1294 VEC (loop_p
, heap
) *loop_nest
)
1296 struct data_dependence_relation
*res
;
1299 res
= XNEW (struct data_dependence_relation
);
1302 DDR_LOOP_NEST (res
) = NULL
;
1303 DDR_REVERSED_P (res
) = false;
1304 DDR_SUBSCRIPTS (res
) = NULL
;
1305 DDR_DIR_VECTS (res
) = NULL
;
1306 DDR_DIST_VECTS (res
) = NULL
;
1308 if (a
== NULL
|| b
== NULL
)
1310 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1314 /* If the data references do not alias, then they are independent. */
1315 if (!dr_may_alias_p (a
, b
))
1317 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1321 /* When the references are exactly the same, don't spend time doing
1322 the data dependence tests, just initialize the ddr and return. */
1323 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1325 DDR_AFFINE_P (res
) = true;
1326 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1327 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1328 DDR_LOOP_NEST (res
) = loop_nest
;
1329 DDR_INNER_LOOP (res
) = 0;
1330 DDR_SELF_REFERENCE (res
) = true;
1331 compute_self_dependence (res
);
1335 /* If the references do not access the same object, we do not know
1336 whether they alias or not. */
1337 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1339 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1343 /* If the base of the object is not invariant in the loop nest, we cannot
1344 analyze it. TODO -- in fact, it would suffice to record that there may
1345 be arbitrary dependences in the loops where the base object varies. */
1346 if (!object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1347 DR_BASE_OBJECT (a
)))
1349 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1353 gcc_assert (DR_NUM_DIMENSIONS (a
) == DR_NUM_DIMENSIONS (b
));
1355 DDR_AFFINE_P (res
) = true;
1356 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1357 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1358 DDR_LOOP_NEST (res
) = loop_nest
;
1359 DDR_INNER_LOOP (res
) = 0;
1360 DDR_SELF_REFERENCE (res
) = false;
1362 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1364 struct subscript
*subscript
;
1366 subscript
= XNEW (struct subscript
);
1367 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1368 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1369 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1370 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1371 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1377 /* Frees memory used by the conflict function F. */
1380 free_conflict_function (conflict_function
*f
)
1384 if (CF_NONTRIVIAL_P (f
))
1386 for (i
= 0; i
< f
->n
; i
++)
1387 affine_fn_free (f
->fns
[i
]);
1392 /* Frees memory used by SUBSCRIPTS. */
1395 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1400 for (i
= 0; VEC_iterate (subscript_p
, subscripts
, i
, s
); i
++)
1402 free_conflict_function (s
->conflicting_iterations_in_a
);
1403 free_conflict_function (s
->conflicting_iterations_in_b
);
1406 VEC_free (subscript_p
, heap
, subscripts
);
1409 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1413 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1418 fprintf (dump_file
, "(dependence classified: ");
1419 print_generic_expr (dump_file
, chrec
, 0);
1420 fprintf (dump_file
, ")\n");
1423 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1424 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1425 DDR_SUBSCRIPTS (ddr
) = NULL
;
1428 /* The dependence relation DDR cannot be represented by a distance
1432 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1434 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1435 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1437 DDR_AFFINE_P (ddr
) = false;
1442 /* This section contains the classic Banerjee tests. */
1444 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1445 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1448 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1450 return (evolution_function_is_constant_p (chrec_a
)
1451 && evolution_function_is_constant_p (chrec_b
));
1454 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1455 variable, i.e., if the SIV (Single Index Variable) test is true. */
1458 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1460 if ((evolution_function_is_constant_p (chrec_a
)
1461 && evolution_function_is_univariate_p (chrec_b
))
1462 || (evolution_function_is_constant_p (chrec_b
)
1463 && evolution_function_is_univariate_p (chrec_a
)))
1466 if (evolution_function_is_univariate_p (chrec_a
)
1467 && evolution_function_is_univariate_p (chrec_b
))
1469 switch (TREE_CODE (chrec_a
))
1471 case POLYNOMIAL_CHREC
:
1472 switch (TREE_CODE (chrec_b
))
1474 case POLYNOMIAL_CHREC
:
1475 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1490 /* Creates a conflict function with N dimensions. The affine functions
1491 in each dimension follow. */
1493 static conflict_function
*
1494 conflict_fn (unsigned n
, ...)
1497 conflict_function
*ret
= XCNEW (conflict_function
);
1500 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1504 for (i
= 0; i
< n
; i
++)
1505 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1511 /* Returns constant affine function with value CST. */
1514 affine_fn_cst (tree cst
)
1516 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1517 VEC_quick_push (tree
, fn
, cst
);
1521 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1524 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1526 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1529 gcc_assert (dim
> 0);
1530 VEC_quick_push (tree
, fn
, cst
);
1531 for (i
= 1; i
< dim
; i
++)
1532 VEC_quick_push (tree
, fn
, integer_zero_node
);
1533 VEC_quick_push (tree
, fn
, coef
);
1537 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1538 *OVERLAPS_B are initialized to the functions that describe the
1539 relation between the elements accessed twice by CHREC_A and
1540 CHREC_B. For k >= 0, the following property is verified:
1542 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1545 analyze_ziv_subscript (tree chrec_a
,
1547 conflict_function
**overlaps_a
,
1548 conflict_function
**overlaps_b
,
1549 tree
*last_conflicts
)
1551 tree type
, difference
;
1552 dependence_stats
.num_ziv
++;
1554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1555 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1557 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1558 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1559 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1560 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1562 switch (TREE_CODE (difference
))
1565 if (integer_zerop (difference
))
1567 /* The difference is equal to zero: the accessed index
1568 overlaps for each iteration in the loop. */
1569 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1570 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1571 *last_conflicts
= chrec_dont_know
;
1572 dependence_stats
.num_ziv_dependent
++;
1576 /* The accesses do not overlap. */
1577 *overlaps_a
= conflict_fn_no_dependence ();
1578 *overlaps_b
= conflict_fn_no_dependence ();
1579 *last_conflicts
= integer_zero_node
;
1580 dependence_stats
.num_ziv_independent
++;
1585 /* We're not sure whether the indexes overlap. For the moment,
1586 conservatively answer "don't know". */
1587 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1588 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1590 *overlaps_a
= conflict_fn_not_known ();
1591 *overlaps_b
= conflict_fn_not_known ();
1592 *last_conflicts
= chrec_dont_know
;
1593 dependence_stats
.num_ziv_unimplemented
++;
1597 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1598 fprintf (dump_file
, ")\n");
1601 /* Sets NIT to the estimated number of executions of the statements in
1602 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1603 large as the number of iterations. If we have no reliable estimate,
1604 the function returns false, otherwise returns true. */
1607 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
1610 estimate_numbers_of_iterations_loop (loop
);
1613 if (!loop
->any_upper_bound
)
1616 *nit
= loop
->nb_iterations_upper_bound
;
1620 if (!loop
->any_estimate
)
1623 *nit
= loop
->nb_iterations_estimate
;
1629 /* Similar to estimated_loop_iterations, but returns the estimate only
1630 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1631 on the number of iterations of LOOP could not be derived, returns -1. */
1634 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
1637 HOST_WIDE_INT hwi_nit
;
1639 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1642 if (!double_int_fits_in_shwi_p (nit
))
1644 hwi_nit
= double_int_to_shwi (nit
);
1646 return hwi_nit
< 0 ? -1 : hwi_nit
;
1649 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1650 and only if it fits to the int type. If this is not the case, or the
1651 estimate on the number of iterations of LOOP could not be derived, returns
1655 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
1660 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1661 return chrec_dont_know
;
1663 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
1664 if (!double_int_fits_to_tree_p (type
, nit
))
1665 return chrec_dont_know
;
1667 return double_int_to_tree (type
, nit
);
1670 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1671 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1672 *OVERLAPS_B are initialized to the functions that describe the
1673 relation between the elements accessed twice by CHREC_A and
1674 CHREC_B. For k >= 0, the following property is verified:
1676 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1679 analyze_siv_subscript_cst_affine (tree chrec_a
,
1681 conflict_function
**overlaps_a
,
1682 conflict_function
**overlaps_b
,
1683 tree
*last_conflicts
)
1685 bool value0
, value1
, value2
;
1686 tree type
, difference
, tmp
;
1688 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1689 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1690 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1691 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1693 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1695 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1696 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1698 dependence_stats
.num_siv_unimplemented
++;
1699 *overlaps_a
= conflict_fn_not_known ();
1700 *overlaps_b
= conflict_fn_not_known ();
1701 *last_conflicts
= chrec_dont_know
;
1706 if (value0
== false)
1708 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1711 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1713 *overlaps_a
= conflict_fn_not_known ();
1714 *overlaps_b
= conflict_fn_not_known ();
1715 *last_conflicts
= chrec_dont_know
;
1716 dependence_stats
.num_siv_unimplemented
++;
1725 chrec_b = {10, +, 1}
1728 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1730 HOST_WIDE_INT numiter
;
1731 struct loop
*loop
= get_chrec_loop (chrec_b
);
1733 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1734 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1735 fold_build1 (ABS_EXPR
, type
, difference
),
1736 CHREC_RIGHT (chrec_b
));
1737 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1738 *last_conflicts
= integer_one_node
;
1741 /* Perform weak-zero siv test to see if overlap is
1742 outside the loop bounds. */
1743 numiter
= estimated_loop_iterations_int (loop
, false);
1746 && compare_tree_int (tmp
, numiter
) > 0)
1748 free_conflict_function (*overlaps_a
);
1749 free_conflict_function (*overlaps_b
);
1750 *overlaps_a
= conflict_fn_no_dependence ();
1751 *overlaps_b
= conflict_fn_no_dependence ();
1752 *last_conflicts
= integer_zero_node
;
1753 dependence_stats
.num_siv_independent
++;
1756 dependence_stats
.num_siv_dependent
++;
1760 /* When the step does not divide the difference, there are
1764 *overlaps_a
= conflict_fn_no_dependence ();
1765 *overlaps_b
= conflict_fn_no_dependence ();
1766 *last_conflicts
= integer_zero_node
;
1767 dependence_stats
.num_siv_independent
++;
1776 chrec_b = {10, +, -1}
1778 In this case, chrec_a will not overlap with chrec_b. */
1779 *overlaps_a
= conflict_fn_no_dependence ();
1780 *overlaps_b
= conflict_fn_no_dependence ();
1781 *last_conflicts
= integer_zero_node
;
1782 dependence_stats
.num_siv_independent
++;
1789 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1791 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1792 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1794 *overlaps_a
= conflict_fn_not_known ();
1795 *overlaps_b
= conflict_fn_not_known ();
1796 *last_conflicts
= chrec_dont_know
;
1797 dependence_stats
.num_siv_unimplemented
++;
1802 if (value2
== false)
1806 chrec_b = {10, +, -1}
1808 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1810 HOST_WIDE_INT numiter
;
1811 struct loop
*loop
= get_chrec_loop (chrec_b
);
1813 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1814 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1815 CHREC_RIGHT (chrec_b
));
1816 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1817 *last_conflicts
= integer_one_node
;
1819 /* Perform weak-zero siv test to see if overlap is
1820 outside the loop bounds. */
1821 numiter
= estimated_loop_iterations_int (loop
, false);
1824 && compare_tree_int (tmp
, numiter
) > 0)
1826 free_conflict_function (*overlaps_a
);
1827 free_conflict_function (*overlaps_b
);
1828 *overlaps_a
= conflict_fn_no_dependence ();
1829 *overlaps_b
= conflict_fn_no_dependence ();
1830 *last_conflicts
= integer_zero_node
;
1831 dependence_stats
.num_siv_independent
++;
1834 dependence_stats
.num_siv_dependent
++;
1838 /* When the step does not divide the difference, there
1842 *overlaps_a
= conflict_fn_no_dependence ();
1843 *overlaps_b
= conflict_fn_no_dependence ();
1844 *last_conflicts
= integer_zero_node
;
1845 dependence_stats
.num_siv_independent
++;
1855 In this case, chrec_a will not overlap with chrec_b. */
1856 *overlaps_a
= conflict_fn_no_dependence ();
1857 *overlaps_b
= conflict_fn_no_dependence ();
1858 *last_conflicts
= integer_zero_node
;
1859 dependence_stats
.num_siv_independent
++;
1867 /* Helper recursive function for initializing the matrix A. Returns
1868 the initial value of CHREC. */
1871 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1875 switch (TREE_CODE (chrec
))
1877 case POLYNOMIAL_CHREC
:
1878 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
1880 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1881 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1887 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1888 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
1890 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
1895 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1896 return chrec_convert (chrec_type (chrec
), op
, NULL
);
1908 #define FLOOR_DIV(x,y) ((x) / (y))
1910 /* Solves the special case of the Diophantine equation:
1911 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1913 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1914 number of iterations that loops X and Y run. The overlaps will be
1915 constructed as evolutions in dimension DIM. */
1918 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1919 affine_fn
*overlaps_a
,
1920 affine_fn
*overlaps_b
,
1921 tree
*last_conflicts
, int dim
)
1923 if (((step_a
> 0 && step_b
> 0)
1924 || (step_a
< 0 && step_b
< 0)))
1926 int step_overlaps_a
, step_overlaps_b
;
1927 int gcd_steps_a_b
, last_conflict
, tau2
;
1929 gcd_steps_a_b
= gcd (step_a
, step_b
);
1930 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1931 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1935 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1936 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1937 last_conflict
= tau2
;
1938 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1941 *last_conflicts
= chrec_dont_know
;
1943 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
1944 build_int_cst (NULL_TREE
,
1946 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
1947 build_int_cst (NULL_TREE
,
1953 *overlaps_a
= affine_fn_cst (integer_zero_node
);
1954 *overlaps_b
= affine_fn_cst (integer_zero_node
);
1955 *last_conflicts
= integer_zero_node
;
1959 /* Solves the special case of a Diophantine equation where CHREC_A is
1960 an affine bivariate function, and CHREC_B is an affine univariate
1961 function. For example,
1963 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1965 has the following overlapping functions:
1967 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1968 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1969 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1971 FORNOW: This is a specialized implementation for a case occurring in
1972 a common benchmark. Implement the general algorithm. */
1975 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1976 conflict_function
**overlaps_a
,
1977 conflict_function
**overlaps_b
,
1978 tree
*last_conflicts
)
1980 bool xz_p
, yz_p
, xyz_p
;
1981 int step_x
, step_y
, step_z
;
1982 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
1983 affine_fn overlaps_a_xz
, overlaps_b_xz
;
1984 affine_fn overlaps_a_yz
, overlaps_b_yz
;
1985 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
1986 affine_fn ova1
, ova2
, ovb
;
1987 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
1989 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
1990 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
1991 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
1994 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a
)),
1996 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), false);
1997 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), false);
1999 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2001 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2002 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2004 *overlaps_a
= conflict_fn_not_known ();
2005 *overlaps_b
= conflict_fn_not_known ();
2006 *last_conflicts
= chrec_dont_know
;
2010 niter
= MIN (niter_x
, niter_z
);
2011 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2014 &last_conflicts_xz
, 1);
2015 niter
= MIN (niter_y
, niter_z
);
2016 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2019 &last_conflicts_yz
, 2);
2020 niter
= MIN (niter_x
, niter_z
);
2021 niter
= MIN (niter_y
, niter
);
2022 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2025 &last_conflicts_xyz
, 3);
2027 xz_p
= !integer_zerop (last_conflicts_xz
);
2028 yz_p
= !integer_zerop (last_conflicts_yz
);
2029 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2031 if (xz_p
|| yz_p
|| xyz_p
)
2033 ova1
= affine_fn_cst (integer_zero_node
);
2034 ova2
= affine_fn_cst (integer_zero_node
);
2035 ovb
= affine_fn_cst (integer_zero_node
);
2038 affine_fn t0
= ova1
;
2041 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2042 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2043 affine_fn_free (t0
);
2044 affine_fn_free (t2
);
2045 *last_conflicts
= last_conflicts_xz
;
2049 affine_fn t0
= ova2
;
2052 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2053 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2054 affine_fn_free (t0
);
2055 affine_fn_free (t2
);
2056 *last_conflicts
= last_conflicts_yz
;
2060 affine_fn t0
= ova1
;
2061 affine_fn t2
= ova2
;
2064 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2065 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2066 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2067 affine_fn_free (t0
);
2068 affine_fn_free (t2
);
2069 affine_fn_free (t4
);
2070 *last_conflicts
= last_conflicts_xyz
;
2072 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2073 *overlaps_b
= conflict_fn (1, ovb
);
2077 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2078 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2079 *last_conflicts
= integer_zero_node
;
2082 affine_fn_free (overlaps_a_xz
);
2083 affine_fn_free (overlaps_b_xz
);
2084 affine_fn_free (overlaps_a_yz
);
2085 affine_fn_free (overlaps_b_yz
);
2086 affine_fn_free (overlaps_a_xyz
);
2087 affine_fn_free (overlaps_b_xyz
);
2090 /* Determines the overlapping elements due to accesses CHREC_A and
2091 CHREC_B, that are affine functions. This function cannot handle
2092 symbolic evolution functions, ie. when initial conditions are
2093 parameters, because it uses lambda matrices of integers. */
2096 analyze_subscript_affine_affine (tree chrec_a
,
2098 conflict_function
**overlaps_a
,
2099 conflict_function
**overlaps_b
,
2100 tree
*last_conflicts
)
2102 unsigned nb_vars_a
, nb_vars_b
, dim
;
2103 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2104 lambda_matrix A
, U
, S
;
2106 if (eq_evolutions_p (chrec_a
, chrec_b
))
2108 /* The accessed index overlaps for each iteration in the
2110 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2111 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2112 *last_conflicts
= chrec_dont_know
;
2115 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2116 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2118 /* For determining the initial intersection, we have to solve a
2119 Diophantine equation. This is the most time consuming part.
2121 For answering to the question: "Is there a dependence?" we have
2122 to prove that there exists a solution to the Diophantine
2123 equation, and that the solution is in the iteration domain,
2124 i.e. the solution is positive or zero, and that the solution
2125 happens before the upper bound loop.nb_iterations. Otherwise
2126 there is no dependence. This function outputs a description of
2127 the iterations that hold the intersections. */
2129 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2130 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2132 dim
= nb_vars_a
+ nb_vars_b
;
2133 U
= lambda_matrix_new (dim
, dim
);
2134 A
= lambda_matrix_new (dim
, 1);
2135 S
= lambda_matrix_new (dim
, 1);
2137 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2138 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2139 gamma
= init_b
- init_a
;
2141 /* Don't do all the hard work of solving the Diophantine equation
2142 when we already know the solution: for example,
2145 | gamma = 3 - 3 = 0.
2146 Then the first overlap occurs during the first iterations:
2147 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2151 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2153 HOST_WIDE_INT step_a
, step_b
;
2154 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2157 niter_a
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
),
2159 niter_b
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
),
2161 niter
= MIN (niter_a
, niter_b
);
2162 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2163 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2165 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2168 *overlaps_a
= conflict_fn (1, ova
);
2169 *overlaps_b
= conflict_fn (1, ovb
);
2172 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2173 compute_overlap_steps_for_affine_1_2
2174 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2176 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2177 compute_overlap_steps_for_affine_1_2
2178 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2182 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2183 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2184 *overlaps_a
= conflict_fn_not_known ();
2185 *overlaps_b
= conflict_fn_not_known ();
2186 *last_conflicts
= chrec_dont_know
;
2188 goto end_analyze_subs_aa
;
2192 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2197 lambda_matrix_row_negate (U
, dim
, 0);
2199 gcd_alpha_beta
= S
[0][0];
2201 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2202 but that is a quite strange case. Instead of ICEing, answer
2204 if (gcd_alpha_beta
== 0)
2206 *overlaps_a
= conflict_fn_not_known ();
2207 *overlaps_b
= conflict_fn_not_known ();
2208 *last_conflicts
= chrec_dont_know
;
2209 goto end_analyze_subs_aa
;
2212 /* The classic "gcd-test". */
2213 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2215 /* The "gcd-test" has determined that there is no integer
2216 solution, i.e. there is no dependence. */
2217 *overlaps_a
= conflict_fn_no_dependence ();
2218 *overlaps_b
= conflict_fn_no_dependence ();
2219 *last_conflicts
= integer_zero_node
;
2222 /* Both access functions are univariate. This includes SIV and MIV cases. */
2223 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2225 /* Both functions should have the same evolution sign. */
2226 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2227 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2229 /* The solutions are given by:
2231 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2234 For a given integer t. Using the following variables,
2236 | i0 = u11 * gamma / gcd_alpha_beta
2237 | j0 = u12 * gamma / gcd_alpha_beta
2244 | y0 = j0 + j1 * t. */
2245 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2247 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2248 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2252 if ((i1
== 0 && i0
< 0)
2253 || (j1
== 0 && j0
< 0))
2255 /* There is no solution.
2256 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2257 falls in here, but for the moment we don't look at the
2258 upper bound of the iteration domain. */
2259 *overlaps_a
= conflict_fn_no_dependence ();
2260 *overlaps_b
= conflict_fn_no_dependence ();
2261 *last_conflicts
= integer_zero_node
;
2262 goto end_analyze_subs_aa
;
2265 if (i1
> 0 && j1
> 0)
2267 HOST_WIDE_INT niter_a
= estimated_loop_iterations_int
2268 (get_chrec_loop (chrec_a
), false);
2269 HOST_WIDE_INT niter_b
= estimated_loop_iterations_int
2270 (get_chrec_loop (chrec_b
), false);
2271 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2273 /* (X0, Y0) is a solution of the Diophantine equation:
2274 "chrec_a (X0) = chrec_b (Y0)". */
2275 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2277 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2278 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2280 /* (X1, Y1) is the smallest positive solution of the eq
2281 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2282 first conflict occurs. */
2283 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2284 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2285 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2289 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2290 FLOOR_DIV (niter
- j0
, j1
));
2291 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2293 /* If the overlap occurs outside of the bounds of the
2294 loop, there is no dependence. */
2295 if (x1
> niter
|| y1
> niter
)
2297 *overlaps_a
= conflict_fn_no_dependence ();
2298 *overlaps_b
= conflict_fn_no_dependence ();
2299 *last_conflicts
= integer_zero_node
;
2300 goto end_analyze_subs_aa
;
2303 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2306 *last_conflicts
= chrec_dont_know
;
2310 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2312 build_int_cst (NULL_TREE
, i1
)));
2315 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2317 build_int_cst (NULL_TREE
, j1
)));
2321 /* FIXME: For the moment, the upper bound of the
2322 iteration domain for i and j is not checked. */
2323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2324 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2325 *overlaps_a
= conflict_fn_not_known ();
2326 *overlaps_b
= conflict_fn_not_known ();
2327 *last_conflicts
= chrec_dont_know
;
2332 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2333 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2334 *overlaps_a
= conflict_fn_not_known ();
2335 *overlaps_b
= conflict_fn_not_known ();
2336 *last_conflicts
= chrec_dont_know
;
2341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2342 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2343 *overlaps_a
= conflict_fn_not_known ();
2344 *overlaps_b
= conflict_fn_not_known ();
2345 *last_conflicts
= chrec_dont_know
;
2348 end_analyze_subs_aa
:
2349 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2351 fprintf (dump_file
, " (overlaps_a = ");
2352 dump_conflict_function (dump_file
, *overlaps_a
);
2353 fprintf (dump_file
, ")\n (overlaps_b = ");
2354 dump_conflict_function (dump_file
, *overlaps_b
);
2355 fprintf (dump_file
, ")\n");
2356 fprintf (dump_file
, ")\n");
2360 /* Returns true when analyze_subscript_affine_affine can be used for
2361 determining the dependence relation between chrec_a and chrec_b,
2362 that contain symbols. This function modifies chrec_a and chrec_b
2363 such that the analysis result is the same, and such that they don't
2364 contain symbols, and then can safely be passed to the analyzer.
2366 Example: The analysis of the following tuples of evolutions produce
2367 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2370 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2371 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2375 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2377 tree diff
, type
, left_a
, left_b
, right_b
;
2379 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2380 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2381 /* FIXME: For the moment not handled. Might be refined later. */
2384 type
= chrec_type (*chrec_a
);
2385 left_a
= CHREC_LEFT (*chrec_a
);
2386 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2387 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2389 if (!evolution_function_is_constant_p (diff
))
2392 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2393 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2395 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2396 diff
, CHREC_RIGHT (*chrec_a
));
2397 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2398 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2399 build_int_cst (type
, 0),
2404 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2405 *OVERLAPS_B are initialized to the functions that describe the
2406 relation between the elements accessed twice by CHREC_A and
2407 CHREC_B. For k >= 0, the following property is verified:
2409 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2412 analyze_siv_subscript (tree chrec_a
,
2414 conflict_function
**overlaps_a
,
2415 conflict_function
**overlaps_b
,
2416 tree
*last_conflicts
,
2419 dependence_stats
.num_siv
++;
2421 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2422 fprintf (dump_file
, "(analyze_siv_subscript \n");
2424 if (evolution_function_is_constant_p (chrec_a
)
2425 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2426 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2427 overlaps_a
, overlaps_b
, last_conflicts
);
2429 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2430 && evolution_function_is_constant_p (chrec_b
))
2431 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2432 overlaps_b
, overlaps_a
, last_conflicts
);
2434 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2435 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2437 if (!chrec_contains_symbols (chrec_a
)
2438 && !chrec_contains_symbols (chrec_b
))
2440 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2441 overlaps_a
, overlaps_b
,
2444 if (CF_NOT_KNOWN_P (*overlaps_a
)
2445 || CF_NOT_KNOWN_P (*overlaps_b
))
2446 dependence_stats
.num_siv_unimplemented
++;
2447 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2448 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2449 dependence_stats
.num_siv_independent
++;
2451 dependence_stats
.num_siv_dependent
++;
2453 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2456 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2457 overlaps_a
, overlaps_b
,
2460 if (CF_NOT_KNOWN_P (*overlaps_a
)
2461 || CF_NOT_KNOWN_P (*overlaps_b
))
2462 dependence_stats
.num_siv_unimplemented
++;
2463 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2464 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2465 dependence_stats
.num_siv_independent
++;
2467 dependence_stats
.num_siv_dependent
++;
2470 goto siv_subscript_dontknow
;
2475 siv_subscript_dontknow
:;
2476 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2477 fprintf (dump_file
, "siv test failed: unimplemented.\n");
2478 *overlaps_a
= conflict_fn_not_known ();
2479 *overlaps_b
= conflict_fn_not_known ();
2480 *last_conflicts
= chrec_dont_know
;
2481 dependence_stats
.num_siv_unimplemented
++;
2484 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2485 fprintf (dump_file
, ")\n");
2488 /* Returns false if we can prove that the greatest common divisor of the steps
2489 of CHREC does not divide CST, false otherwise. */
2492 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2494 HOST_WIDE_INT cd
= 0, val
;
2497 if (!host_integerp (cst
, 0))
2499 val
= tree_low_cst (cst
, 0);
2501 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2503 step
= CHREC_RIGHT (chrec
);
2504 if (!host_integerp (step
, 0))
2506 cd
= gcd (cd
, tree_low_cst (step
, 0));
2507 chrec
= CHREC_LEFT (chrec
);
2510 return val
% cd
== 0;
2513 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2514 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2515 functions that describe the relation between the elements accessed
2516 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2519 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2522 analyze_miv_subscript (tree chrec_a
,
2524 conflict_function
**overlaps_a
,
2525 conflict_function
**overlaps_b
,
2526 tree
*last_conflicts
,
2527 struct loop
*loop_nest
)
2529 /* FIXME: This is a MIV subscript, not yet handled.
2530 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2533 In the SIV test we had to solve a Diophantine equation with two
2534 variables. In the MIV case we have to solve a Diophantine
2535 equation with 2*n variables (if the subscript uses n IVs).
2537 tree type
, difference
;
2539 dependence_stats
.num_miv
++;
2540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2541 fprintf (dump_file
, "(analyze_miv_subscript \n");
2543 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2544 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2545 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2546 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2548 if (eq_evolutions_p (chrec_a
, chrec_b
))
2550 /* Access functions are the same: all the elements are accessed
2551 in the same order. */
2552 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2553 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2554 *last_conflicts
= estimated_loop_iterations_tree
2555 (get_chrec_loop (chrec_a
), true);
2556 dependence_stats
.num_miv_dependent
++;
2559 else if (evolution_function_is_constant_p (difference
)
2560 /* For the moment, the following is verified:
2561 evolution_function_is_affine_multivariate_p (chrec_a,
2563 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2565 /* testsuite/.../ssa-chrec-33.c
2566 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2568 The difference is 1, and all the evolution steps are multiples
2569 of 2, consequently there are no overlapping elements. */
2570 *overlaps_a
= conflict_fn_no_dependence ();
2571 *overlaps_b
= conflict_fn_no_dependence ();
2572 *last_conflicts
= integer_zero_node
;
2573 dependence_stats
.num_miv_independent
++;
2576 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2577 && !chrec_contains_symbols (chrec_a
)
2578 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2579 && !chrec_contains_symbols (chrec_b
))
2581 /* testsuite/.../ssa-chrec-35.c
2582 {0, +, 1}_2 vs. {0, +, 1}_3
2583 the overlapping elements are respectively located at iterations:
2584 {0, +, 1}_x and {0, +, 1}_x,
2585 in other words, we have the equality:
2586 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2589 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2590 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2592 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2593 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2595 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2596 overlaps_a
, overlaps_b
, last_conflicts
);
2598 if (CF_NOT_KNOWN_P (*overlaps_a
)
2599 || CF_NOT_KNOWN_P (*overlaps_b
))
2600 dependence_stats
.num_miv_unimplemented
++;
2601 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2602 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2603 dependence_stats
.num_miv_independent
++;
2605 dependence_stats
.num_miv_dependent
++;
2610 /* When the analysis is too difficult, answer "don't know". */
2611 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2612 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2614 *overlaps_a
= conflict_fn_not_known ();
2615 *overlaps_b
= conflict_fn_not_known ();
2616 *last_conflicts
= chrec_dont_know
;
2617 dependence_stats
.num_miv_unimplemented
++;
2620 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2621 fprintf (dump_file
, ")\n");
2624 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2625 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2626 OVERLAP_ITERATIONS_B are initialized with two functions that
2627 describe the iterations that contain conflicting elements.
2629 Remark: For an integer k >= 0, the following equality is true:
2631 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2635 analyze_overlapping_iterations (tree chrec_a
,
2637 conflict_function
**overlap_iterations_a
,
2638 conflict_function
**overlap_iterations_b
,
2639 tree
*last_conflicts
, struct loop
*loop_nest
)
2641 unsigned int lnn
= loop_nest
->num
;
2643 dependence_stats
.num_subscript_tests
++;
2645 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2647 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2648 fprintf (dump_file
, " (chrec_a = ");
2649 print_generic_expr (dump_file
, chrec_a
, 0);
2650 fprintf (dump_file
, ")\n (chrec_b = ");
2651 print_generic_expr (dump_file
, chrec_b
, 0);
2652 fprintf (dump_file
, ")\n");
2655 if (chrec_a
== NULL_TREE
2656 || chrec_b
== NULL_TREE
2657 || chrec_contains_undetermined (chrec_a
)
2658 || chrec_contains_undetermined (chrec_b
))
2660 dependence_stats
.num_subscript_undetermined
++;
2662 *overlap_iterations_a
= conflict_fn_not_known ();
2663 *overlap_iterations_b
= conflict_fn_not_known ();
2666 /* If they are the same chrec, and are affine, they overlap
2667 on every iteration. */
2668 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2669 && evolution_function_is_affine_multivariate_p (chrec_a
, lnn
))
2671 dependence_stats
.num_same_subscript_function
++;
2672 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2673 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2674 *last_conflicts
= chrec_dont_know
;
2677 /* If they aren't the same, and aren't affine, we can't do anything
2679 else if ((chrec_contains_symbols (chrec_a
)
2680 || chrec_contains_symbols (chrec_b
))
2681 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2682 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2684 dependence_stats
.num_subscript_undetermined
++;
2685 *overlap_iterations_a
= conflict_fn_not_known ();
2686 *overlap_iterations_b
= conflict_fn_not_known ();
2689 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2690 analyze_ziv_subscript (chrec_a
, chrec_b
,
2691 overlap_iterations_a
, overlap_iterations_b
,
2694 else if (siv_subscript_p (chrec_a
, chrec_b
))
2695 analyze_siv_subscript (chrec_a
, chrec_b
,
2696 overlap_iterations_a
, overlap_iterations_b
,
2697 last_conflicts
, lnn
);
2700 analyze_miv_subscript (chrec_a
, chrec_b
,
2701 overlap_iterations_a
, overlap_iterations_b
,
2702 last_conflicts
, loop_nest
);
2704 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2706 fprintf (dump_file
, " (overlap_iterations_a = ");
2707 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2708 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2709 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2710 fprintf (dump_file
, ")\n");
2711 fprintf (dump_file
, ")\n");
2715 /* Helper function for uniquely inserting distance vectors. */
2718 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2723 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
2724 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2727 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2730 /* Helper function for uniquely inserting direction vectors. */
2733 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2738 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
2739 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2742 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2745 /* Add a distance of 1 on all the loops outer than INDEX. If we
2746 haven't yet determined a distance for this outer loop, push a new
2747 distance vector composed of the previous distance, and a distance
2748 of 1 for this outer loop. Example:
2756 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2757 save (0, 1), then we have to save (1, 0). */
2760 add_outer_distances (struct data_dependence_relation
*ddr
,
2761 lambda_vector dist_v
, int index
)
2763 /* For each outer loop where init_v is not set, the accesses are
2764 in dependence of distance 1 in the loop. */
2765 while (--index
>= 0)
2767 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2768 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2770 save_dist_v (ddr
, save_v
);
2774 /* Return false when fail to represent the data dependence as a
2775 distance vector. INIT_B is set to true when a component has been
2776 added to the distance vector DIST_V. INDEX_CARRY is then set to
2777 the index in DIST_V that carries the dependence. */
2780 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2781 struct data_reference
*ddr_a
,
2782 struct data_reference
*ddr_b
,
2783 lambda_vector dist_v
, bool *init_b
,
2787 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2789 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2791 tree access_fn_a
, access_fn_b
;
2792 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2794 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2796 non_affine_dependence_relation (ddr
);
2800 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2801 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2803 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2804 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2807 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2808 DDR_LOOP_NEST (ddr
));
2809 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2810 DDR_LOOP_NEST (ddr
));
2812 /* The dependence is carried by the outermost loop. Example:
2819 In this case, the dependence is carried by loop_1. */
2820 index
= index_a
< index_b
? index_a
: index_b
;
2821 *index_carry
= MIN (index
, *index_carry
);
2823 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2825 non_affine_dependence_relation (ddr
);
2829 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2831 /* This is the subscript coupling test. If we have already
2832 recorded a distance for this loop (a distance coming from
2833 another subscript), it should be the same. For example,
2834 in the following code, there is no dependence:
2841 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2843 finalize_ddr_dependent (ddr
, chrec_known
);
2847 dist_v
[index
] = dist
;
2851 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2853 /* This can be for example an affine vs. constant dependence
2854 (T[i] vs. T[3]) that is not an affine dependence and is
2855 not representable as a distance vector. */
2856 non_affine_dependence_relation (ddr
);
2864 /* Return true when the DDR contains only constant access functions. */
2867 constant_access_functions (const struct data_dependence_relation
*ddr
)
2871 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2872 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2873 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2879 /* Helper function for the case where DDR_A and DDR_B are the same
2880 multivariate access function with a constant step. For an example
2884 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2887 tree c_1
= CHREC_LEFT (c_2
);
2888 tree c_0
= CHREC_LEFT (c_1
);
2889 lambda_vector dist_v
;
2892 /* Polynomials with more than 2 variables are not handled yet. When
2893 the evolution steps are parameters, it is not possible to
2894 represent the dependence using classical distance vectors. */
2895 if (TREE_CODE (c_0
) != INTEGER_CST
2896 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
2897 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
2899 DDR_AFFINE_P (ddr
) = false;
2903 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2904 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2906 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2907 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2908 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2909 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2922 save_dist_v (ddr
, dist_v
);
2924 add_outer_distances (ddr
, dist_v
, x_1
);
2927 /* Helper function for the case where DDR_A and DDR_B are the same
2928 access functions. */
2931 add_other_self_distances (struct data_dependence_relation
*ddr
)
2933 lambda_vector dist_v
;
2935 int index_carry
= DDR_NB_LOOPS (ddr
);
2937 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2939 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
2941 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
2943 if (!evolution_function_is_univariate_p (access_fun
))
2945 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
2947 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2951 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
2953 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
2954 add_multivariate_self_dist (ddr
, access_fun
);
2956 /* The evolution step is not constant: it varies in
2957 the outer loop, so this cannot be represented by a
2958 distance vector. For example in pr34635.c the
2959 evolution is {0, +, {0, +, 4}_1}_2. */
2960 DDR_AFFINE_P (ddr
) = false;
2965 index_carry
= MIN (index_carry
,
2966 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
2967 DDR_LOOP_NEST (ddr
)));
2971 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2972 add_outer_distances (ddr
, dist_v
, index_carry
);
2976 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
2978 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2980 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
2981 save_dist_v (ddr
, dist_v
);
2984 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2985 is the case for example when access functions are the same and
2986 equal to a constant, as in:
2993 in which case the distance vectors are (0) and (1). */
2996 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
3000 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3002 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
3003 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
3004 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
3006 for (j
= 0; j
< ca
->n
; j
++)
3007 if (affine_function_zero_p (ca
->fns
[j
]))
3009 insert_innermost_unit_dist_vector (ddr
);
3013 for (j
= 0; j
< cb
->n
; j
++)
3014 if (affine_function_zero_p (cb
->fns
[j
]))
3016 insert_innermost_unit_dist_vector (ddr
);
3022 /* Compute the classic per loop distance vector. DDR is the data
3023 dependence relation to build a vector from. Return false when fail
3024 to represent the data dependence as a distance vector. */
3027 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3028 struct loop
*loop_nest
)
3030 bool init_b
= false;
3031 int index_carry
= DDR_NB_LOOPS (ddr
);
3032 lambda_vector dist_v
;
3034 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3037 if (same_access_functions (ddr
))
3039 /* Save the 0 vector. */
3040 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3041 save_dist_v (ddr
, dist_v
);
3043 if (constant_access_functions (ddr
))
3044 add_distance_for_zero_overlaps (ddr
);
3046 if (DDR_NB_LOOPS (ddr
) > 1)
3047 add_other_self_distances (ddr
);
3052 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3053 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3054 dist_v
, &init_b
, &index_carry
))
3057 /* Save the distance vector if we initialized one. */
3060 /* Verify a basic constraint: classic distance vectors should
3061 always be lexicographically positive.
3063 Data references are collected in the order of execution of
3064 the program, thus for the following loop
3066 | for (i = 1; i < 100; i++)
3067 | for (j = 1; j < 100; j++)
3069 | t = T[j+1][i-1]; // A
3070 | T[j][i] = t + 2; // B
3073 references are collected following the direction of the wind:
3074 A then B. The data dependence tests are performed also
3075 following this order, such that we're looking at the distance
3076 separating the elements accessed by A from the elements later
3077 accessed by B. But in this example, the distance returned by
3078 test_dep (A, B) is lexicographically negative (-1, 1), that
3079 means that the access A occurs later than B with respect to
3080 the outer loop, ie. we're actually looking upwind. In this
3081 case we solve test_dep (B, A) looking downwind to the
3082 lexicographically positive solution, that returns the
3083 distance vector (1, -1). */
3084 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3086 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3087 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3090 compute_subscript_distance (ddr
);
3091 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3092 save_v
, &init_b
, &index_carry
))
3094 save_dist_v (ddr
, save_v
);
3095 DDR_REVERSED_P (ddr
) = true;
3097 /* In this case there is a dependence forward for all the
3100 | for (k = 1; k < 100; k++)
3101 | for (i = 1; i < 100; i++)
3102 | for (j = 1; j < 100; j++)
3104 | t = T[j+1][i-1]; // A
3105 | T[j][i] = t + 2; // B
3113 if (DDR_NB_LOOPS (ddr
) > 1)
3115 add_outer_distances (ddr
, save_v
, index_carry
);
3116 add_outer_distances (ddr
, dist_v
, index_carry
);
3121 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3122 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3124 if (DDR_NB_LOOPS (ddr
) > 1)
3126 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3128 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3129 DDR_A (ddr
), loop_nest
))
3131 compute_subscript_distance (ddr
);
3132 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3133 opposite_v
, &init_b
,
3137 save_dist_v (ddr
, save_v
);
3138 add_outer_distances (ddr
, dist_v
, index_carry
);
3139 add_outer_distances (ddr
, opposite_v
, index_carry
);
3142 save_dist_v (ddr
, save_v
);
3147 /* There is a distance of 1 on all the outer loops: Example:
3148 there is a dependence of distance 1 on loop_1 for the array A.
3154 add_outer_distances (ddr
, dist_v
,
3155 lambda_vector_first_nz (dist_v
,
3156 DDR_NB_LOOPS (ddr
), 0));
3159 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3163 fprintf (dump_file
, "(build_classic_dist_vector\n");
3164 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3166 fprintf (dump_file
, " dist_vector = (");
3167 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3168 DDR_NB_LOOPS (ddr
));
3169 fprintf (dump_file
, " )\n");
3171 fprintf (dump_file
, ")\n");
3177 /* Return the direction for a given distance.
3178 FIXME: Computing dir this way is suboptimal, since dir can catch
3179 cases that dist is unable to represent. */
3181 static inline enum data_dependence_direction
3182 dir_from_dist (int dist
)
3185 return dir_positive
;
3187 return dir_negative
;
3192 /* Compute the classic per loop direction vector. DDR is the data
3193 dependence relation to build a vector from. */
3196 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3199 lambda_vector dist_v
;
3201 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3203 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3205 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3206 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3208 save_dir_v (ddr
, dir_v
);
3212 /* Helper function. Returns true when there is a dependence between
3213 data references DRA and DRB. */
3216 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3217 struct data_reference
*dra
,
3218 struct data_reference
*drb
,
3219 struct loop
*loop_nest
)
3222 tree last_conflicts
;
3223 struct subscript
*subscript
;
3225 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3228 conflict_function
*overlaps_a
, *overlaps_b
;
3230 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3231 DR_ACCESS_FN (drb
, i
),
3232 &overlaps_a
, &overlaps_b
,
3233 &last_conflicts
, loop_nest
);
3235 if (CF_NOT_KNOWN_P (overlaps_a
)
3236 || CF_NOT_KNOWN_P (overlaps_b
))
3238 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3239 dependence_stats
.num_dependence_undetermined
++;
3240 free_conflict_function (overlaps_a
);
3241 free_conflict_function (overlaps_b
);
3245 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3246 || CF_NO_DEPENDENCE_P (overlaps_b
))
3248 finalize_ddr_dependent (ddr
, chrec_known
);
3249 dependence_stats
.num_dependence_independent
++;
3250 free_conflict_function (overlaps_a
);
3251 free_conflict_function (overlaps_b
);
3257 if (SUB_CONFLICTS_IN_A (subscript
))
3258 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3259 if (SUB_CONFLICTS_IN_B (subscript
))
3260 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3262 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3263 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3264 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3271 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3274 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3275 struct loop
*loop_nest
)
3278 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3279 fprintf (dump_file
, "(subscript_dependence_tester \n");
3281 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3282 dependence_stats
.num_dependence_dependent
++;
3284 compute_subscript_distance (ddr
);
3285 if (build_classic_dist_vector (ddr
, loop_nest
))
3286 build_classic_dir_vector (ddr
);
3288 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3289 fprintf (dump_file
, ")\n");
3292 /* Returns true when all the access functions of A are affine or
3293 constant with respect to LOOP_NEST. */
3296 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3297 const struct loop
*loop_nest
)
3300 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3303 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
3304 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3305 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3311 /* Return true if we can create an affine data-ref for OP in STMT. */
3314 stmt_simple_memref_p (struct loop
*loop
, gimple stmt
, tree op
)
3316 data_reference_p dr
;
3319 dr
= create_data_ref (loop
, op
, stmt
, true);
3320 if (!access_functions_are_affine_or_constant_p (dr
, loop
))
3327 /* Initializes an equation for an OMEGA problem using the information
3328 contained in the ACCESS_FUN. Returns true when the operation
3331 PB is the omega constraint system.
3332 EQ is the number of the equation to be initialized.
3333 OFFSET is used for shifting the variables names in the constraints:
3334 a constrain is composed of 2 * the number of variables surrounding
3335 dependence accesses. OFFSET is set either to 0 for the first n variables,
3336 then it is set to n.
3337 ACCESS_FUN is expected to be an affine chrec. */
3340 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3341 unsigned int offset
, tree access_fun
,
3342 struct data_dependence_relation
*ddr
)
3344 switch (TREE_CODE (access_fun
))
3346 case POLYNOMIAL_CHREC
:
3348 tree left
= CHREC_LEFT (access_fun
);
3349 tree right
= CHREC_RIGHT (access_fun
);
3350 int var
= CHREC_VARIABLE (access_fun
);
3353 if (TREE_CODE (right
) != INTEGER_CST
)
3356 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3357 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3359 /* Compute the innermost loop index. */
3360 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3363 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3364 += int_cst_value (right
);
3366 switch (TREE_CODE (left
))
3368 case POLYNOMIAL_CHREC
:
3369 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3372 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3381 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3389 /* As explained in the comments preceding init_omega_for_ddr, we have
3390 to set up a system for each loop level, setting outer loops
3391 variation to zero, and current loop variation to positive or zero.
3392 Save each lexico positive distance vector. */
3395 omega_extract_distance_vectors (omega_pb pb
,
3396 struct data_dependence_relation
*ddr
)
3400 struct loop
*loopi
, *loopj
;
3401 enum omega_result res
;
3403 /* Set a new problem for each loop in the nest. The basis is the
3404 problem that we have initialized until now. On top of this we
3405 add new constraints. */
3406 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3407 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3410 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3411 DDR_NB_LOOPS (ddr
));
3413 omega_copy_problem (copy
, pb
);
3415 /* For all the outer loops "loop_j", add "dj = 0". */
3417 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3419 eq
= omega_add_zero_eq (copy
, omega_black
);
3420 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3423 /* For "loop_i", add "0 <= di". */
3424 geq
= omega_add_zero_geq (copy
, omega_black
);
3425 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3427 /* Reduce the constraint system, and test that the current
3428 problem is feasible. */
3429 res
= omega_simplify_problem (copy
);
3430 if (res
== omega_false
3431 || res
== omega_unknown
3432 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3435 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3436 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3438 dist
= copy
->subs
[eq
].coef
[0];
3444 /* Reinitialize problem... */
3445 omega_copy_problem (copy
, pb
);
3447 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3449 eq
= omega_add_zero_eq (copy
, omega_black
);
3450 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3453 /* ..., but this time "di = 1". */
3454 eq
= omega_add_zero_eq (copy
, omega_black
);
3455 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3456 copy
->eqs
[eq
].coef
[0] = -1;
3458 res
= omega_simplify_problem (copy
);
3459 if (res
== omega_false
3460 || res
== omega_unknown
3461 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3464 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3465 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3467 dist
= copy
->subs
[eq
].coef
[0];
3473 /* Save the lexicographically positive distance vector. */
3476 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3477 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3481 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3482 if (copy
->subs
[eq
].key
> 0)
3484 dist
= copy
->subs
[eq
].coef
[0];
3485 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3488 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3489 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3491 save_dist_v (ddr
, dist_v
);
3492 save_dir_v (ddr
, dir_v
);
3496 omega_free_problem (copy
);
3500 /* This is called for each subscript of a tuple of data references:
3501 insert an equality for representing the conflicts. */
3504 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3505 struct data_dependence_relation
*ddr
,
3506 omega_pb pb
, bool *maybe_dependent
)
3509 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3510 TREE_TYPE (access_fun_b
));
3511 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3512 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3513 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3515 /* When the fun_a - fun_b is not constant, the dependence is not
3516 captured by the classic distance vector representation. */
3517 if (TREE_CODE (difference
) != INTEGER_CST
)
3521 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3523 /* There is no dependence. */
3524 *maybe_dependent
= false;
3528 fun_b
= chrec_fold_multiply (type
, fun_b
, integer_minus_one_node
);
3530 eq
= omega_add_zero_eq (pb
, omega_black
);
3531 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3532 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3533 /* There is probably a dependence, but the system of
3534 constraints cannot be built: answer "don't know". */
3538 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3539 && !int_divides_p (lambda_vector_gcd
3540 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3541 2 * DDR_NB_LOOPS (ddr
)),
3542 pb
->eqs
[eq
].coef
[0]))
3544 /* There is no dependence. */
3545 *maybe_dependent
= false;
3552 /* Helper function, same as init_omega_for_ddr but specialized for
3553 data references A and B. */
3556 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3557 struct data_dependence_relation
*ddr
,
3558 omega_pb pb
, bool *maybe_dependent
)
3563 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3565 /* Insert an equality per subscript. */
3566 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3568 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3569 ddr
, pb
, maybe_dependent
))
3571 else if (*maybe_dependent
== false)
3573 /* There is no dependence. */
3574 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3579 /* Insert inequalities: constraints corresponding to the iteration
3580 domain, i.e. the loops surrounding the references "loop_x" and
3581 the distance variables "dx". The layout of the OMEGA
3582 representation is as follows:
3583 - coef[0] is the constant
3584 - coef[1..nb_loops] are the protected variables that will not be
3585 removed by the solver: the "dx"
3586 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3588 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3589 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3591 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3594 ineq
= omega_add_zero_geq (pb
, omega_black
);
3595 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3597 /* 0 <= loop_x + dx */
3598 ineq
= omega_add_zero_geq (pb
, omega_black
);
3599 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3600 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3604 /* loop_x <= nb_iters */
3605 ineq
= omega_add_zero_geq (pb
, omega_black
);
3606 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3607 pb
->geqs
[ineq
].coef
[0] = nbi
;
3609 /* loop_x + dx <= nb_iters */
3610 ineq
= omega_add_zero_geq (pb
, omega_black
);
3611 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3612 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3613 pb
->geqs
[ineq
].coef
[0] = nbi
;
3615 /* A step "dx" bigger than nb_iters is not feasible, so
3616 add "0 <= nb_iters + dx", */
3617 ineq
= omega_add_zero_geq (pb
, omega_black
);
3618 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3619 pb
->geqs
[ineq
].coef
[0] = nbi
;
3620 /* and "dx <= nb_iters". */
3621 ineq
= omega_add_zero_geq (pb
, omega_black
);
3622 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3623 pb
->geqs
[ineq
].coef
[0] = nbi
;
3627 omega_extract_distance_vectors (pb
, ddr
);
3632 /* Sets up the Omega dependence problem for the data dependence
3633 relation DDR. Returns false when the constraint system cannot be
3634 built, ie. when the test answers "don't know". Returns true
3635 otherwise, and when independence has been proved (using one of the
3636 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3637 set MAYBE_DEPENDENT to true.
3639 Example: for setting up the dependence system corresponding to the
3640 conflicting accesses
3645 | ... A[2*j, 2*(i + j)]
3649 the following constraints come from the iteration domain:
3656 where di, dj are the distance variables. The constraints
3657 representing the conflicting elements are:
3660 i + 1 = 2 * (i + di + j + dj)
3662 For asking that the resulting distance vector (di, dj) be
3663 lexicographically positive, we insert the constraint "di >= 0". If
3664 "di = 0" in the solution, we fix that component to zero, and we
3665 look at the inner loops: we set a new problem where all the outer
3666 loop distances are zero, and fix this inner component to be
3667 positive. When one of the components is positive, we save that
3668 distance, and set a new problem where the distance on this loop is
3669 zero, searching for other distances in the inner loops. Here is
3670 the classic example that illustrates that we have to set for each
3671 inner loop a new problem:
3679 we have to save two distances (1, 0) and (0, 1).
3681 Given two array references, refA and refB, we have to set the
3682 dependence problem twice, refA vs. refB and refB vs. refA, and we
3683 cannot do a single test, as refB might occur before refA in the
3684 inner loops, and the contrary when considering outer loops: ex.
3689 | T[{1,+,1}_2][{1,+,1}_1] // refA
3690 | T[{2,+,1}_2][{0,+,1}_1] // refB
3695 refB touches the elements in T before refA, and thus for the same
3696 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3697 but for successive loop_0 iterations, we have (1, -1, 1)
3699 The Omega solver expects the distance variables ("di" in the
3700 previous example) to come first in the constraint system (as
3701 variables to be protected, or "safe" variables), the constraint
3702 system is built using the following layout:
3704 "cst | distance vars | index vars".
3708 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3709 bool *maybe_dependent
)
3714 *maybe_dependent
= true;
3716 if (same_access_functions (ddr
))
3719 lambda_vector dir_v
;
3721 /* Save the 0 vector. */
3722 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3723 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3724 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3725 dir_v
[j
] = dir_equal
;
3726 save_dir_v (ddr
, dir_v
);
3728 /* Save the dependences carried by outer loops. */
3729 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3730 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3732 omega_free_problem (pb
);
3736 /* Omega expects the protected variables (those that have to be kept
3737 after elimination) to appear first in the constraint system.
3738 These variables are the distance variables. In the following
3739 initialization we declare NB_LOOPS safe variables, and the total
3740 number of variables for the constraint system is 2*NB_LOOPS. */
3741 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3742 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3744 omega_free_problem (pb
);
3746 /* Stop computation if not decidable, or no dependence. */
3747 if (res
== false || *maybe_dependent
== false)
3750 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3751 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3753 omega_free_problem (pb
);
3758 /* Return true when DDR contains the same information as that stored
3759 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3762 ddr_consistent_p (FILE *file
,
3763 struct data_dependence_relation
*ddr
,
3764 VEC (lambda_vector
, heap
) *dist_vects
,
3765 VEC (lambda_vector
, heap
) *dir_vects
)
3769 /* If dump_file is set, output there. */
3770 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3773 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3775 lambda_vector b_dist_v
;
3776 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3777 VEC_length (lambda_vector
, dist_vects
),
3778 DDR_NUM_DIST_VECTS (ddr
));
3780 fprintf (file
, "Banerjee dist vectors:\n");
3781 for (i
= 0; VEC_iterate (lambda_vector
, dist_vects
, i
, b_dist_v
); i
++)
3782 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3784 fprintf (file
, "Omega dist vectors:\n");
3785 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3786 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3788 fprintf (file
, "data dependence relation:\n");
3789 dump_data_dependence_relation (file
, ddr
);
3791 fprintf (file
, ")\n");
3795 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3797 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3798 VEC_length (lambda_vector
, dir_vects
),
3799 DDR_NUM_DIR_VECTS (ddr
));
3803 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3805 lambda_vector a_dist_v
;
3806 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3808 /* Distance vectors are not ordered in the same way in the DDR
3809 and in the DIST_VECTS: search for a matching vector. */
3810 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, a_dist_v
); j
++)
3811 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3814 if (j
== VEC_length (lambda_vector
, dist_vects
))
3816 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3817 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3818 fprintf (file
, "not found in Omega dist vectors:\n");
3819 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3820 fprintf (file
, "data dependence relation:\n");
3821 dump_data_dependence_relation (file
, ddr
);
3822 fprintf (file
, ")\n");
3826 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3828 lambda_vector a_dir_v
;
3829 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3831 /* Direction vectors are not ordered in the same way in the DDR
3832 and in the DIR_VECTS: search for a matching vector. */
3833 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, a_dir_v
); j
++)
3834 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3837 if (j
== VEC_length (lambda_vector
, dist_vects
))
3839 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3840 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3841 fprintf (file
, "not found in Omega dir vectors:\n");
3842 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3843 fprintf (file
, "data dependence relation:\n");
3844 dump_data_dependence_relation (file
, ddr
);
3845 fprintf (file
, ")\n");
3852 /* This computes the affine dependence relation between A and B with
3853 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3854 independence between two accesses, while CHREC_DONT_KNOW is used
3855 for representing the unknown relation.
3857 Note that it is possible to stop the computation of the dependence
3858 relation the first time we detect a CHREC_KNOWN element for a given
3862 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3863 struct loop
*loop_nest
)
3865 struct data_reference
*dra
= DDR_A (ddr
);
3866 struct data_reference
*drb
= DDR_B (ddr
);
3868 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3870 fprintf (dump_file
, "(compute_affine_dependence\n");
3871 fprintf (dump_file
, " (stmt_a = \n");
3872 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, 0);
3873 fprintf (dump_file
, ")\n (stmt_b = \n");
3874 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, 0);
3875 fprintf (dump_file
, ")\n");
3878 /* Analyze only when the dependence relation is not yet known. */
3879 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
3880 && !DDR_SELF_REFERENCE (ddr
))
3882 dependence_stats
.num_dependence_tests
++;
3884 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3885 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3887 if (flag_check_data_deps
)
3889 /* Compute the dependences using the first algorithm. */
3890 subscript_dependence_tester (ddr
, loop_nest
);
3892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3894 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3895 dump_data_dependence_relation (dump_file
, ddr
);
3898 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3900 bool maybe_dependent
;
3901 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3903 /* Save the result of the first DD analyzer. */
3904 dist_vects
= DDR_DIST_VECTS (ddr
);
3905 dir_vects
= DDR_DIR_VECTS (ddr
);
3907 /* Reset the information. */
3908 DDR_DIST_VECTS (ddr
) = NULL
;
3909 DDR_DIR_VECTS (ddr
) = NULL
;
3911 /* Compute the same information using Omega. */
3912 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3913 goto csys_dont_know
;
3915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3917 fprintf (dump_file
, "Omega Analyzer\n");
3918 dump_data_dependence_relation (dump_file
, ddr
);
3921 /* Check that we get the same information. */
3922 if (maybe_dependent
)
3923 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3928 subscript_dependence_tester (ddr
, loop_nest
);
3931 /* As a last case, if the dependence cannot be determined, or if
3932 the dependence is considered too difficult to determine, answer
3937 dependence_stats
.num_dependence_undetermined
++;
3939 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3941 fprintf (dump_file
, "Data ref a:\n");
3942 dump_data_reference (dump_file
, dra
);
3943 fprintf (dump_file
, "Data ref b:\n");
3944 dump_data_reference (dump_file
, drb
);
3945 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3947 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3951 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3952 fprintf (dump_file
, ")\n");
3955 /* This computes the dependence relation for the same data
3956 reference into DDR. */
3959 compute_self_dependence (struct data_dependence_relation
*ddr
)
3962 struct subscript
*subscript
;
3964 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3967 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3970 if (SUB_CONFLICTS_IN_A (subscript
))
3971 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3972 if (SUB_CONFLICTS_IN_B (subscript
))
3973 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3975 /* The accessed index overlaps for each iteration. */
3976 SUB_CONFLICTS_IN_A (subscript
)
3977 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3978 SUB_CONFLICTS_IN_B (subscript
)
3979 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3980 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3983 /* The distance vector is the zero vector. */
3984 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3985 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3988 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3989 the data references in DATAREFS, in the LOOP_NEST. When
3990 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3994 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
3995 VEC (ddr_p
, heap
) **dependence_relations
,
3996 VEC (loop_p
, heap
) *loop_nest
,
3997 bool compute_self_and_rr
)
3999 struct data_dependence_relation
*ddr
;
4000 struct data_reference
*a
, *b
;
4003 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4004 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
4005 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
4007 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4008 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4009 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
4012 if (compute_self_and_rr
)
4013 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4015 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4016 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4017 compute_self_dependence (ddr
);
4021 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4022 true if STMT clobbers memory, false otherwise. */
4025 get_references_in_stmt (gimple stmt
, VEC (data_ref_loc
, heap
) **references
)
4027 bool clobbers_memory
= false;
4030 enum gimple_code stmt_code
= gimple_code (stmt
);
4034 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4035 Calls have side-effects, except those to const or pure
4037 if ((stmt_code
== GIMPLE_CALL
4038 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4039 || (stmt_code
== GIMPLE_ASM
4040 && gimple_asm_volatile_p (stmt
)))
4041 clobbers_memory
= true;
4043 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
4044 return clobbers_memory
;
4046 if (stmt_code
== GIMPLE_ASSIGN
)
4049 op0
= gimple_assign_lhs_ptr (stmt
);
4050 op1
= gimple_assign_rhs1_ptr (stmt
);
4053 || (REFERENCE_CLASS_P (*op1
)
4054 && (base
= get_base_address (*op1
))
4055 && TREE_CODE (base
) != SSA_NAME
))
4057 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4059 ref
->is_read
= true;
4063 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4065 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4067 ref
->is_read
= false;
4070 else if (stmt_code
== GIMPLE_CALL
)
4072 unsigned i
, n
= gimple_call_num_args (stmt
);
4074 for (i
= 0; i
< n
; i
++)
4076 op0
= gimple_call_arg_ptr (stmt
, i
);
4079 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4081 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4083 ref
->is_read
= true;
4088 return clobbers_memory
;
4091 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4092 reference, returns false, otherwise returns true. NEST is the outermost
4093 loop of the loop nest in which the references should be analyzed. */
4096 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4097 VEC (data_reference_p
, heap
) **datarefs
)
4100 VEC (data_ref_loc
, heap
) *references
;
4103 data_reference_p dr
;
4105 if (get_references_in_stmt (stmt
, &references
))
4107 VEC_free (data_ref_loc
, heap
, references
);
4111 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
4113 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4114 gcc_assert (dr
!= NULL
);
4116 /* FIXME -- data dependence analysis does not work correctly for objects with
4117 invariant addresses. Let us fail here until the problem is fixed. */
4118 if (dr_address_invariant_p (dr
))
4121 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4122 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
4127 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4129 VEC_free (data_ref_loc
, heap
, references
);
4133 /* Search the data references in LOOP, and record the information into
4134 DATAREFS. Returns chrec_dont_know when failing to analyze a
4135 difficult case, returns NULL_TREE otherwise.
4137 TODO: This function should be made smarter so that it can handle address
4138 arithmetic as if they were array accesses, etc. */
4141 find_data_references_in_loop (struct loop
*loop
,
4142 VEC (data_reference_p
, heap
) **datarefs
)
4144 basic_block bb
, *bbs
;
4146 gimple_stmt_iterator bsi
;
4148 bbs
= get_loop_body_in_dom_order (loop
);
4150 for (i
= 0; i
< loop
->num_nodes
; i
++)
4154 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4156 gimple stmt
= gsi_stmt (bsi
);
4158 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4160 struct data_reference
*res
;
4161 res
= XCNEW (struct data_reference
);
4162 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4165 return chrec_dont_know
;
4174 /* Recursive helper function. */
4177 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4179 /* Inner loops of the nest should not contain siblings. Example:
4180 when there are two consecutive loops,
4191 the dependence relation cannot be captured by the distance
4196 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4198 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4202 /* Return false when the LOOP is not well nested. Otherwise return
4203 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4204 contain the loops from the outermost to the innermost, as they will
4205 appear in the classic distance vector. */
4208 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4210 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4212 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4216 /* Returns true when the data dependences have been computed, false otherwise.
4217 Given a loop nest LOOP, the following vectors are returned:
4218 DATAREFS is initialized to all the array elements contained in this loop,
4219 DEPENDENCE_RELATIONS contains the relations between the data references.
4220 Compute read-read and self relations if
4221 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4224 compute_data_dependences_for_loop (struct loop
*loop
,
4225 bool compute_self_and_read_read_dependences
,
4226 VEC (data_reference_p
, heap
) **datarefs
,
4227 VEC (ddr_p
, heap
) **dependence_relations
)
4230 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4232 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4234 /* If the loop nest is not well formed, or one of the data references
4235 is not computable, give up without spending time to compute other
4238 || !find_loop_nest (loop
, &vloops
)
4239 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4241 struct data_dependence_relation
*ddr
;
4243 /* Insert a single relation into dependence_relations:
4245 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4246 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4250 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4251 compute_self_and_read_read_dependences
);
4253 if (dump_file
&& (dump_flags
& TDF_STATS
))
4255 fprintf (dump_file
, "Dependence tester statistics:\n");
4257 fprintf (dump_file
, "Number of dependence tests: %d\n",
4258 dependence_stats
.num_dependence_tests
);
4259 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4260 dependence_stats
.num_dependence_dependent
);
4261 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4262 dependence_stats
.num_dependence_independent
);
4263 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4264 dependence_stats
.num_dependence_undetermined
);
4266 fprintf (dump_file
, "Number of subscript tests: %d\n",
4267 dependence_stats
.num_subscript_tests
);
4268 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4269 dependence_stats
.num_subscript_undetermined
);
4270 fprintf (dump_file
, "Number of same subscript function: %d\n",
4271 dependence_stats
.num_same_subscript_function
);
4273 fprintf (dump_file
, "Number of ziv tests: %d\n",
4274 dependence_stats
.num_ziv
);
4275 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4276 dependence_stats
.num_ziv_dependent
);
4277 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4278 dependence_stats
.num_ziv_independent
);
4279 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4280 dependence_stats
.num_ziv_unimplemented
);
4282 fprintf (dump_file
, "Number of siv tests: %d\n",
4283 dependence_stats
.num_siv
);
4284 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4285 dependence_stats
.num_siv_dependent
);
4286 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4287 dependence_stats
.num_siv_independent
);
4288 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4289 dependence_stats
.num_siv_unimplemented
);
4291 fprintf (dump_file
, "Number of miv tests: %d\n",
4292 dependence_stats
.num_miv
);
4293 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4294 dependence_stats
.num_miv_dependent
);
4295 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4296 dependence_stats
.num_miv_independent
);
4297 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4298 dependence_stats
.num_miv_unimplemented
);
4304 /* Entry point (for testing only). Analyze all the data references
4305 and the dependence relations in LOOP.
4307 The data references are computed first.
4309 A relation on these nodes is represented by a complete graph. Some
4310 of the relations could be of no interest, thus the relations can be
4313 In the following function we compute all the relations. This is
4314 just a first implementation that is here for:
4315 - for showing how to ask for the dependence relations,
4316 - for the debugging the whole dependence graph,
4317 - for the dejagnu testcases and maintenance.
4319 It is possible to ask only for a part of the graph, avoiding to
4320 compute the whole dependence graph. The computed dependences are
4321 stored in a knowledge base (KB) such that later queries don't
4322 recompute the same information. The implementation of this KB is
4323 transparent to the optimizer, and thus the KB can be changed with a
4324 more efficient implementation, or the KB could be disabled. */
4326 analyze_all_data_dependences (struct loop
*loop
)
4329 int nb_data_refs
= 10;
4330 VEC (data_reference_p
, heap
) *datarefs
=
4331 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4332 VEC (ddr_p
, heap
) *dependence_relations
=
4333 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4335 /* Compute DDs on the whole function. */
4336 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4337 &dependence_relations
);
4341 dump_data_dependence_relations (dump_file
, dependence_relations
);
4342 fprintf (dump_file
, "\n\n");
4344 if (dump_flags
& TDF_DETAILS
)
4345 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4347 if (dump_flags
& TDF_STATS
)
4349 unsigned nb_top_relations
= 0;
4350 unsigned nb_bot_relations
= 0;
4351 unsigned nb_basename_differ
= 0;
4352 unsigned nb_chrec_relations
= 0;
4353 struct data_dependence_relation
*ddr
;
4355 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4357 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4360 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4362 struct data_reference
*a
= DDR_A (ddr
);
4363 struct data_reference
*b
= DDR_B (ddr
);
4365 if (!bitmap_intersect_p (DR_VOPS (a
), DR_VOPS (b
)))
4366 nb_basename_differ
++;
4372 nb_chrec_relations
++;
4375 gather_stats_on_scev_database ();
4379 free_dependence_relations (dependence_relations
);
4380 free_data_refs (datarefs
);
4383 /* Computes all the data dependences and check that the results of
4384 several analyzers are the same. */
4387 tree_check_data_deps (void)
4390 struct loop
*loop_nest
;
4392 FOR_EACH_LOOP (li
, loop_nest
, 0)
4393 analyze_all_data_dependences (loop_nest
);
4396 /* Free the memory used by a data dependence relation DDR. */
4399 free_dependence_relation (struct data_dependence_relation
*ddr
)
4404 if (DDR_SUBSCRIPTS (ddr
))
4405 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4406 if (DDR_DIST_VECTS (ddr
))
4407 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4408 if (DDR_DIR_VECTS (ddr
))
4409 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4414 /* Free the memory used by the data dependence relations from
4415 DEPENDENCE_RELATIONS. */
4418 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4421 struct data_dependence_relation
*ddr
;
4422 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4424 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4428 if (loop_nest
== NULL
)
4429 loop_nest
= DDR_LOOP_NEST (ddr
);
4431 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4432 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4433 free_dependence_relation (ddr
);
4437 VEC_free (loop_p
, heap
, loop_nest
);
4438 VEC_free (ddr_p
, heap
, dependence_relations
);
4441 /* Free the memory used by the data references from DATAREFS. */
4444 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4447 struct data_reference
*dr
;
4449 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4451 VEC_free (data_reference_p
, heap
, datarefs
);
4456 /* Dump vertex I in RDG to FILE. */
4459 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4461 struct vertex
*v
= &(rdg
->vertices
[i
]);
4462 struct graph_edge
*e
;
4464 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4465 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4466 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4469 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4470 fprintf (file
, " %d", e
->src
);
4472 fprintf (file
, ") (out:");
4475 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4476 fprintf (file
, " %d", e
->dest
);
4478 fprintf (file
, ") \n");
4479 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4480 fprintf (file
, ")\n");
4483 /* Call dump_rdg_vertex on stderr. */
4486 debug_rdg_vertex (struct graph
*rdg
, int i
)
4488 dump_rdg_vertex (stderr
, rdg
, i
);
4491 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4492 dumped vertices to that bitmap. */
4494 void dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4498 fprintf (file
, "(%d\n", c
);
4500 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4501 if (rdg
->vertices
[i
].component
== c
)
4504 bitmap_set_bit (dumped
, i
);
4506 dump_rdg_vertex (file
, rdg
, i
);
4509 fprintf (file
, ")\n");
4512 /* Call dump_rdg_vertex on stderr. */
4515 debug_rdg_component (struct graph
*rdg
, int c
)
4517 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4520 /* Dump the reduced dependence graph RDG to FILE. */
4523 dump_rdg (FILE *file
, struct graph
*rdg
)
4526 bitmap dumped
= BITMAP_ALLOC (NULL
);
4528 fprintf (file
, "(rdg\n");
4530 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4531 if (!bitmap_bit_p (dumped
, i
))
4532 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4534 fprintf (file
, ")\n");
4535 BITMAP_FREE (dumped
);
4538 /* Call dump_rdg on stderr. */
4541 debug_rdg (struct graph
*rdg
)
4543 dump_rdg (stderr
, rdg
);
4547 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
4551 fprintf (file
, "digraph RDG {\n");
4553 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4555 struct vertex
*v
= &(rdg
->vertices
[i
]);
4556 struct graph_edge
*e
;
4558 /* Highlight reads from memory. */
4559 if (RDG_MEM_READS_STMT (rdg
, i
))
4560 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
4562 /* Highlight stores to memory. */
4563 if (RDG_MEM_WRITE_STMT (rdg
, i
))
4564 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
4567 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4568 switch (RDGE_TYPE (e
))
4571 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
4575 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
4579 /* These are the most common dependences: don't print these. */
4580 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
4584 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
4592 fprintf (file
, "}\n\n");
4595 /* Display SCOP using dotty. */
4598 dot_rdg (struct graph
*rdg
)
4600 FILE *file
= fopen ("/tmp/rdg.dot", "w");
4601 gcc_assert (file
!= NULL
);
4603 dot_rdg_1 (file
, rdg
);
4606 system ("dotty /tmp/rdg.dot");
4610 /* This structure is used for recording the mapping statement index in
4613 struct rdg_vertex_info
GTY(())
4619 /* Returns the index of STMT in RDG. */
4622 rdg_vertex_for_stmt (struct graph
*rdg
, gimple stmt
)
4624 struct rdg_vertex_info rvi
, *slot
;
4627 slot
= (struct rdg_vertex_info
*) htab_find (rdg
->indices
, &rvi
);
4635 /* Creates an edge in RDG for each distance vector from DDR. The
4636 order that we keep track of in the RDG is the order in which
4637 statements have to be executed. */
4640 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4642 struct graph_edge
*e
;
4644 data_reference_p dra
= DDR_A (ddr
);
4645 data_reference_p drb
= DDR_B (ddr
);
4646 unsigned level
= ddr_dependence_level (ddr
);
4648 /* For non scalar dependences, when the dependence is REVERSED,
4649 statement B has to be executed before statement A. */
4651 && !DDR_REVERSED_P (ddr
))
4653 data_reference_p tmp
= dra
;
4658 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4659 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4661 if (va
< 0 || vb
< 0)
4664 e
= add_edge (rdg
, va
, vb
);
4665 e
->data
= XNEW (struct rdg_edge
);
4667 RDGE_LEVEL (e
) = level
;
4668 RDGE_RELATION (e
) = ddr
;
4670 /* Determines the type of the data dependence. */
4671 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4672 RDGE_TYPE (e
) = input_dd
;
4673 else if (!DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4674 RDGE_TYPE (e
) = output_dd
;
4675 else if (!DR_IS_READ (dra
) && DR_IS_READ (drb
))
4676 RDGE_TYPE (e
) = flow_dd
;
4677 else if (DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4678 RDGE_TYPE (e
) = anti_dd
;
4681 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4682 the index of DEF in RDG. */
4685 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4687 use_operand_p imm_use_p
;
4688 imm_use_iterator iterator
;
4690 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4692 struct graph_edge
*e
;
4693 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4698 e
= add_edge (rdg
, idef
, use
);
4699 e
->data
= XNEW (struct rdg_edge
);
4700 RDGE_TYPE (e
) = flow_dd
;
4701 RDGE_RELATION (e
) = NULL
;
4705 /* Creates the edges of the reduced dependence graph RDG. */
4708 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4711 struct data_dependence_relation
*ddr
;
4712 def_operand_p def_p
;
4715 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
4716 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4717 create_rdg_edge_for_ddr (rdg
, ddr
);
4719 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4720 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4722 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4725 /* Build the vertices of the reduced dependence graph RDG. */
4728 create_rdg_vertices (struct graph
*rdg
, VEC (gimple
, heap
) *stmts
)
4733 for (i
= 0; VEC_iterate (gimple
, stmts
, i
, stmt
); i
++)
4735 VEC (data_ref_loc
, heap
) *references
;
4737 struct vertex
*v
= &(rdg
->vertices
[i
]);
4738 struct rdg_vertex_info
*rvi
= XNEW (struct rdg_vertex_info
);
4739 struct rdg_vertex_info
**slot
;
4743 slot
= (struct rdg_vertex_info
**) htab_find_slot (rdg
->indices
, rvi
, INSERT
);
4750 v
->data
= XNEW (struct rdg_vertex
);
4751 RDG_STMT (rdg
, i
) = stmt
;
4753 RDG_MEM_WRITE_STMT (rdg
, i
) = false;
4754 RDG_MEM_READS_STMT (rdg
, i
) = false;
4755 if (gimple_code (stmt
) == GIMPLE_PHI
)
4758 get_references_in_stmt (stmt
, &references
);
4759 for (j
= 0; VEC_iterate (data_ref_loc
, references
, j
, ref
); j
++)
4761 RDG_MEM_WRITE_STMT (rdg
, i
) = true;
4763 RDG_MEM_READS_STMT (rdg
, i
) = true;
4765 VEC_free (data_ref_loc
, heap
, references
);
4769 /* Initialize STMTS with all the statements of LOOP. When
4770 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4771 which we discover statements is important as
4772 generate_loops_for_partition is using the same traversal for
4773 identifying statements. */
4776 stmts_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4779 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4781 for (i
= 0; i
< loop
->num_nodes
; i
++)
4783 basic_block bb
= bbs
[i
];
4784 gimple_stmt_iterator bsi
;
4787 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4788 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4790 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4792 stmt
= gsi_stmt (bsi
);
4793 if (gimple_code (stmt
) != GIMPLE_LABEL
)
4794 VEC_safe_push (gimple
, heap
, *stmts
, stmt
);
4801 /* Returns true when all the dependences are computable. */
4804 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
4809 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4810 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4816 /* Computes a hash function for element ELT. */
4819 hash_stmt_vertex_info (const void *elt
)
4821 const struct rdg_vertex_info
*const rvi
=
4822 (const struct rdg_vertex_info
*) elt
;
4823 gimple stmt
= rvi
->stmt
;
4825 return htab_hash_pointer (stmt
);
4828 /* Compares database elements E1 and E2. */
4831 eq_stmt_vertex_info (const void *e1
, const void *e2
)
4833 const struct rdg_vertex_info
*elt1
= (const struct rdg_vertex_info
*) e1
;
4834 const struct rdg_vertex_info
*elt2
= (const struct rdg_vertex_info
*) e2
;
4836 return elt1
->stmt
== elt2
->stmt
;
4839 /* Free the element E. */
4842 hash_stmt_vertex_del (void *e
)
4847 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4848 statement of the loop nest, and one edge per data dependence or
4849 scalar dependence. */
4852 build_empty_rdg (int n_stmts
)
4854 int nb_data_refs
= 10;
4855 struct graph
*rdg
= new_graph (n_stmts
);
4857 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4858 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4862 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4863 statement of the loop nest, and one edge per data dependence or
4864 scalar dependence. */
4867 build_rdg (struct loop
*loop
)
4869 int nb_data_refs
= 10;
4870 struct graph
*rdg
= NULL
;
4871 VEC (ddr_p
, heap
) *dependence_relations
;
4872 VEC (data_reference_p
, heap
) *datarefs
;
4873 VEC (gimple
, heap
) *stmts
= VEC_alloc (gimple
, heap
, nb_data_refs
);
4875 dependence_relations
= VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
) ;
4876 datarefs
= VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4877 compute_data_dependences_for_loop (loop
,
4880 &dependence_relations
);
4882 if (!known_dependences_p (dependence_relations
))
4884 free_dependence_relations (dependence_relations
);
4885 free_data_refs (datarefs
);
4886 VEC_free (gimple
, heap
, stmts
);
4891 stmts_from_loop (loop
, &stmts
);
4892 rdg
= build_empty_rdg (VEC_length (gimple
, stmts
));
4894 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4895 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4896 create_rdg_vertices (rdg
, stmts
);
4897 create_rdg_edges (rdg
, dependence_relations
);
4899 VEC_free (gimple
, heap
, stmts
);
4903 /* Free the reduced dependence graph RDG. */
4906 free_rdg (struct graph
*rdg
)
4910 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4911 free (rdg
->vertices
[i
].data
);
4913 htab_delete (rdg
->indices
);
4917 /* Initialize STMTS with all the statements of LOOP that contain a
4921 stores_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4924 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4926 for (i
= 0; i
< loop
->num_nodes
; i
++)
4928 basic_block bb
= bbs
[i
];
4929 gimple_stmt_iterator bsi
;
4931 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4932 if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi
), SSA_OP_VDEF
))
4933 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4939 /* For a data reference REF, return the declaration of its base
4940 address or NULL_TREE if the base is not determined. */
4943 ref_base_address (gimple stmt
, data_ref_loc
*ref
)
4945 tree base
= NULL_TREE
;
4947 struct data_reference
*dr
= XCNEW (struct data_reference
);
4949 DR_STMT (dr
) = stmt
;
4950 DR_REF (dr
) = *ref
->pos
;
4951 dr_analyze_innermost (dr
);
4952 base_address
= DR_BASE_ADDRESS (dr
);
4957 switch (TREE_CODE (base_address
))
4960 base
= TREE_OPERAND (base_address
, 0);
4964 base
= base_address
;
4973 /* Determines whether the statement from vertex V of the RDG has a
4974 definition used outside the loop that contains this statement. */
4977 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
4979 gimple stmt
= RDG_STMT (rdg
, v
);
4980 struct loop
*loop
= loop_containing_stmt (stmt
);
4981 use_operand_p imm_use_p
;
4982 imm_use_iterator iterator
;
4984 def_operand_p def_p
;
4989 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
4991 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
4993 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)
5001 /* Determines whether statements S1 and S2 access to similar memory
5002 locations. Two memory accesses are considered similar when they
5003 have the same base address declaration, i.e. when their
5004 ref_base_address is the same. */
5007 have_similar_memory_accesses (gimple s1
, gimple s2
)
5011 VEC (data_ref_loc
, heap
) *refs1
, *refs2
;
5012 data_ref_loc
*ref1
, *ref2
;
5014 get_references_in_stmt (s1
, &refs1
);
5015 get_references_in_stmt (s2
, &refs2
);
5017 for (i
= 0; VEC_iterate (data_ref_loc
, refs1
, i
, ref1
); i
++)
5019 tree base1
= ref_base_address (s1
, ref1
);
5022 for (j
= 0; VEC_iterate (data_ref_loc
, refs2
, j
, ref2
); j
++)
5023 if (base1
== ref_base_address (s2
, ref2
))
5031 VEC_free (data_ref_loc
, heap
, refs1
);
5032 VEC_free (data_ref_loc
, heap
, refs2
);
5036 /* Helper function for the hashtab. */
5039 have_similar_memory_accesses_1 (const void *s1
, const void *s2
)
5041 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple
) s1
),
5042 CONST_CAST_GIMPLE ((const_gimple
) s2
));
5045 /* Helper function for the hashtab. */
5048 ref_base_address_1 (const void *s
)
5050 gimple stmt
= CONST_CAST_GIMPLE ((const_gimple
) s
);
5052 VEC (data_ref_loc
, heap
) *refs
;
5056 get_references_in_stmt (stmt
, &refs
);
5058 for (i
= 0; VEC_iterate (data_ref_loc
, refs
, i
, ref
); i
++)
5061 res
= htab_hash_pointer (ref_base_address (stmt
, ref
));
5065 VEC_free (data_ref_loc
, heap
, refs
);
5069 /* Try to remove duplicated write data references from STMTS. */
5072 remove_similar_memory_refs (VEC (gimple
, heap
) **stmts
)
5076 htab_t seen
= htab_create (VEC_length (gimple
, *stmts
), ref_base_address_1
,
5077 have_similar_memory_accesses_1
, NULL
);
5079 for (i
= 0; VEC_iterate (gimple
, *stmts
, i
, stmt
); )
5083 slot
= htab_find_slot (seen
, stmt
, INSERT
);
5086 VEC_ordered_remove (gimple
, *stmts
, i
);
5089 *slot
= (void *) stmt
;
5097 /* Returns the index of PARAMETER in the parameters vector of the
5098 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5101 access_matrix_get_index_for_parameter (tree parameter
,
5102 struct access_matrix
*access_matrix
)
5105 VEC (tree
,heap
) *lambda_parameters
= AM_PARAMETERS (access_matrix
);
5106 tree lambda_parameter
;
5108 for (i
= 0; VEC_iterate (tree
, lambda_parameters
, i
, lambda_parameter
); i
++)
5109 if (lambda_parameter
== parameter
)
5110 return i
+ AM_NB_INDUCTION_VARS (access_matrix
);