1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
84 #include "basic-block.h"
85 #include "tree-pretty-print.h"
86 #include "gimple-pretty-print.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 into STDERR all the data references from DATAREFS. */
162 debug_data_references (VEC (data_reference_p
, heap
) *datarefs
)
164 dump_data_references (stderr
, datarefs
);
167 /* Dump to STDERR all the dependence relations from DDRS. */
170 debug_data_dependence_relations (VEC (ddr_p
, heap
) *ddrs
)
172 dump_data_dependence_relations (stderr
, ddrs
);
175 /* Dump into FILE all the dependence relations from DDRS. */
178 dump_data_dependence_relations (FILE *file
,
179 VEC (ddr_p
, heap
) *ddrs
)
182 struct data_dependence_relation
*ddr
;
184 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
185 dump_data_dependence_relation (file
, ddr
);
188 /* Print to STDERR the data_reference DR. */
191 debug_data_reference (struct data_reference
*dr
)
193 dump_data_reference (stderr
, dr
);
196 /* Dump function for a DATA_REFERENCE structure. */
199 dump_data_reference (FILE *outf
,
200 struct data_reference
*dr
)
204 fprintf (outf
, "#(Data Ref: \n# stmt: ");
205 print_gimple_stmt (outf
, DR_STMT (dr
), 0, 0);
206 fprintf (outf
, "# ref: ");
207 print_generic_stmt (outf
, DR_REF (dr
), 0);
208 fprintf (outf
, "# base_object: ");
209 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
211 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
213 fprintf (outf
, "# Access function %d: ", i
);
214 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
216 fprintf (outf
, "#)\n");
219 /* Dumps the affine function described by FN to the file OUTF. */
222 dump_affine_function (FILE *outf
, affine_fn fn
)
227 print_generic_expr (outf
, VEC_index (tree
, fn
, 0), TDF_SLIM
);
228 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
230 fprintf (outf
, " + ");
231 print_generic_expr (outf
, coef
, TDF_SLIM
);
232 fprintf (outf
, " * x_%u", i
);
236 /* Dumps the conflict function CF to the file OUTF. */
239 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
243 if (cf
->n
== NO_DEPENDENCE
)
244 fprintf (outf
, "no dependence\n");
245 else if (cf
->n
== NOT_KNOWN
)
246 fprintf (outf
, "not known\n");
249 for (i
= 0; i
< cf
->n
; i
++)
252 dump_affine_function (outf
, cf
->fns
[i
]);
253 fprintf (outf
, "]\n");
258 /* Dump function for a SUBSCRIPT structure. */
261 dump_subscript (FILE *outf
, struct subscript
*subscript
)
263 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
265 fprintf (outf
, "\n (subscript \n");
266 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
267 dump_conflict_function (outf
, cf
);
268 if (CF_NONTRIVIAL_P (cf
))
270 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
271 fprintf (outf
, " last_conflict: ");
272 print_generic_stmt (outf
, last_iteration
, 0);
275 cf
= SUB_CONFLICTS_IN_B (subscript
);
276 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
277 dump_conflict_function (outf
, cf
);
278 if (CF_NONTRIVIAL_P (cf
))
280 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
281 fprintf (outf
, " last_conflict: ");
282 print_generic_stmt (outf
, last_iteration
, 0);
285 fprintf (outf
, " (Subscript distance: ");
286 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
287 fprintf (outf
, " )\n");
288 fprintf (outf
, " )\n");
291 /* Print the classic direction vector DIRV to OUTF. */
294 print_direction_vector (FILE *outf
,
300 for (eq
= 0; eq
< length
; eq
++)
302 enum data_dependence_direction dir
= ((enum data_dependence_direction
)
308 fprintf (outf
, " +");
311 fprintf (outf
, " -");
314 fprintf (outf
, " =");
316 case dir_positive_or_equal
:
317 fprintf (outf
, " +=");
319 case dir_positive_or_negative
:
320 fprintf (outf
, " +-");
322 case dir_negative_or_equal
:
323 fprintf (outf
, " -=");
326 fprintf (outf
, " *");
329 fprintf (outf
, "indep");
333 fprintf (outf
, "\n");
336 /* Print a vector of direction vectors. */
339 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
345 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
346 print_direction_vector (outf
, v
, length
);
349 /* Print a vector of distance vectors. */
352 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
358 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
359 print_lambda_vector (outf
, v
, length
);
365 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
367 dump_data_dependence_relation (stderr
, ddr
);
370 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
373 dump_data_dependence_relation (FILE *outf
,
374 struct data_dependence_relation
*ddr
)
376 struct data_reference
*dra
, *drb
;
378 fprintf (outf
, "(Data Dep: \n");
380 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
387 dump_data_reference (outf
, dra
);
389 fprintf (outf
, " (nil)\n");
391 dump_data_reference (outf
, drb
);
393 fprintf (outf
, " (nil)\n");
395 fprintf (outf
, " (don't know)\n)\n");
401 dump_data_reference (outf
, dra
);
402 dump_data_reference (outf
, drb
);
404 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
405 fprintf (outf
, " (no dependence)\n");
407 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
412 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
414 fprintf (outf
, " access_fn_A: ");
415 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
416 fprintf (outf
, " access_fn_B: ");
417 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
418 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
421 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
422 fprintf (outf
, " loop nest: (");
423 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
424 fprintf (outf
, "%d ", loopi
->num
);
425 fprintf (outf
, ")\n");
427 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
429 fprintf (outf
, " distance_vector: ");
430 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
434 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
436 fprintf (outf
, " direction_vector: ");
437 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
442 fprintf (outf
, ")\n");
445 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
448 dump_data_dependence_direction (FILE *file
,
449 enum data_dependence_direction dir
)
465 case dir_positive_or_negative
:
466 fprintf (file
, "+-");
469 case dir_positive_or_equal
:
470 fprintf (file
, "+=");
473 case dir_negative_or_equal
:
474 fprintf (file
, "-=");
486 /* Dumps the distance and direction vectors in FILE. DDRS contains
487 the dependence relations, and VECT_SIZE is the size of the
488 dependence vectors, or in other words the number of loops in the
492 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
495 struct data_dependence_relation
*ddr
;
498 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
499 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
501 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
503 fprintf (file
, "DISTANCE_V (");
504 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
505 fprintf (file
, ")\n");
508 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
510 fprintf (file
, "DIRECTION_V (");
511 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
512 fprintf (file
, ")\n");
516 fprintf (file
, "\n\n");
519 /* Dumps the data dependence relations DDRS in FILE. */
522 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
525 struct data_dependence_relation
*ddr
;
527 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
528 dump_data_dependence_relation (file
, ddr
);
530 fprintf (file
, "\n\n");
533 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
534 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
535 constant of type ssizetype, and returns true. If we cannot do this
536 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
540 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
541 tree
*var
, tree
*off
)
545 enum tree_code ocode
= code
;
553 *var
= build_int_cst (type
, 0);
554 *off
= fold_convert (ssizetype
, op0
);
557 case POINTER_PLUS_EXPR
:
562 split_constant_offset (op0
, &var0
, &off0
);
563 split_constant_offset (op1
, &var1
, &off1
);
564 *var
= fold_build2 (code
, type
, var0
, var1
);
565 *off
= size_binop (ocode
, off0
, off1
);
569 if (TREE_CODE (op1
) != INTEGER_CST
)
572 split_constant_offset (op0
, &var0
, &off0
);
573 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
574 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
580 HOST_WIDE_INT pbitsize
, pbitpos
;
581 enum machine_mode pmode
;
582 int punsignedp
, pvolatilep
;
584 op0
= TREE_OPERAND (op0
, 0);
585 if (!handled_component_p (op0
))
588 base
= get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
,
589 &pmode
, &punsignedp
, &pvolatilep
, false);
591 if (pbitpos
% BITS_PER_UNIT
!= 0)
593 base
= build_fold_addr_expr (base
);
594 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
598 split_constant_offset (poffset
, &poffset
, &off1
);
599 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
600 if (POINTER_TYPE_P (TREE_TYPE (base
)))
601 base
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (base
),
602 base
, fold_convert (sizetype
, poffset
));
604 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
605 fold_convert (TREE_TYPE (base
), poffset
));
608 var0
= fold_convert (type
, base
);
610 /* If variable length types are involved, punt, otherwise casts
611 might be converted into ARRAY_REFs in gimplify_conversion.
612 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
613 possibly no longer appears in current GIMPLE, might resurface.
614 This perhaps could run
615 if (CONVERT_EXPR_P (var0))
617 gimplify_conversion (&var0);
618 // Attempt to fill in any within var0 found ARRAY_REF's
619 // element size from corresponding op embedded ARRAY_REF,
620 // if unsuccessful, just punt.
622 while (POINTER_TYPE_P (type
))
623 type
= TREE_TYPE (type
);
624 if (int_size_in_bytes (type
) < 0)
634 gimple def_stmt
= SSA_NAME_DEF_STMT (op0
);
635 enum tree_code subcode
;
637 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
640 var0
= gimple_assign_rhs1 (def_stmt
);
641 subcode
= gimple_assign_rhs_code (def_stmt
);
642 var1
= gimple_assign_rhs2 (def_stmt
);
644 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
648 /* We must not introduce undefined overflow, and we must not change the value.
649 Hence we're okay if the inner type doesn't overflow to start with
650 (pointer or signed), the outer type also is an integer or pointer
651 and the outer precision is at least as large as the inner. */
652 tree itype
= TREE_TYPE (op0
);
653 if ((POINTER_TYPE_P (itype
)
654 || (INTEGRAL_TYPE_P (itype
) && TYPE_OVERFLOW_UNDEFINED (itype
)))
655 && TYPE_PRECISION (type
) >= TYPE_PRECISION (itype
)
656 && (POINTER_TYPE_P (type
) || INTEGRAL_TYPE_P (type
)))
658 split_constant_offset (op0
, &var0
, off
);
659 *var
= fold_convert (type
, var0
);
670 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
671 will be ssizetype. */
674 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
676 tree type
= TREE_TYPE (exp
), otype
, op0
, op1
, e
, o
;
680 *off
= ssize_int (0);
683 if (automatically_generated_chrec_p (exp
))
686 otype
= TREE_TYPE (exp
);
687 code
= TREE_CODE (exp
);
688 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
689 if (split_constant_offset_1 (otype
, op0
, code
, op1
, &e
, &o
))
691 *var
= fold_convert (type
, e
);
696 /* Returns the address ADDR of an object in a canonical shape (without nop
697 casts, and with type of pointer to the object). */
700 canonicalize_base_object_address (tree addr
)
706 /* The base address may be obtained by casting from integer, in that case
708 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
711 if (TREE_CODE (addr
) != ADDR_EXPR
)
714 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
717 /* Analyzes the behavior of the memory reference DR in the innermost loop or
718 basic block that contains it. Returns true if analysis succeed or false
722 dr_analyze_innermost (struct data_reference
*dr
)
724 gimple stmt
= DR_STMT (dr
);
725 struct loop
*loop
= loop_containing_stmt (stmt
);
726 tree ref
= DR_REF (dr
);
727 HOST_WIDE_INT pbitsize
, pbitpos
;
729 enum machine_mode pmode
;
730 int punsignedp
, pvolatilep
;
731 affine_iv base_iv
, offset_iv
;
732 tree init
, dinit
, step
;
733 bool in_loop
= (loop
&& loop
->num
);
735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
736 fprintf (dump_file
, "analyze_innermost: ");
738 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
739 &pmode
, &punsignedp
, &pvolatilep
, false);
740 gcc_assert (base
!= NULL_TREE
);
742 if (pbitpos
% BITS_PER_UNIT
!= 0)
744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
745 fprintf (dump_file
, "failed: bit offset alignment.\n");
749 base
= build_fold_addr_expr (base
);
752 if (!simple_iv (loop
, loop_containing_stmt (stmt
), base
, &base_iv
,
755 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
756 fprintf (dump_file
, "failed: evolution of base is not affine.\n");
763 base_iv
.step
= ssize_int (0);
764 base_iv
.no_overflow
= true;
769 offset_iv
.base
= ssize_int (0);
770 offset_iv
.step
= ssize_int (0);
776 offset_iv
.base
= poffset
;
777 offset_iv
.step
= ssize_int (0);
779 else if (!simple_iv (loop
, loop_containing_stmt (stmt
),
780 poffset
, &offset_iv
, false))
782 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
783 fprintf (dump_file
, "failed: evolution of offset is not"
789 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
790 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
791 init
= size_binop (PLUS_EXPR
, init
, dinit
);
792 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
793 init
= size_binop (PLUS_EXPR
, init
, dinit
);
795 step
= size_binop (PLUS_EXPR
,
796 fold_convert (ssizetype
, base_iv
.step
),
797 fold_convert (ssizetype
, offset_iv
.step
));
799 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
801 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
805 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
807 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
808 fprintf (dump_file
, "success.\n");
813 /* Determines the base object and the list of indices of memory reference
814 DR, analyzed in loop nest NEST. */
817 dr_analyze_indices (struct data_reference
*dr
, struct loop
*nest
)
819 gimple stmt
= DR_STMT (dr
);
820 struct loop
*loop
= loop_containing_stmt (stmt
);
821 VEC (tree
, heap
) *access_fns
= NULL
;
822 tree ref
= unshare_expr (DR_REF (dr
)), aref
= ref
, op
;
823 tree base
, off
, access_fn
= NULL_TREE
;
824 basic_block before_loop
= NULL
;
827 before_loop
= block_before_loop (nest
);
829 while (handled_component_p (aref
))
831 if (TREE_CODE (aref
) == ARRAY_REF
)
833 op
= TREE_OPERAND (aref
, 1);
836 access_fn
= analyze_scalar_evolution (loop
, op
);
837 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
838 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
841 TREE_OPERAND (aref
, 1) = build_int_cst (TREE_TYPE (op
), 0);
844 aref
= TREE_OPERAND (aref
, 0);
847 if (nest
&& INDIRECT_REF_P (aref
))
849 op
= TREE_OPERAND (aref
, 0);
850 access_fn
= analyze_scalar_evolution (loop
, op
);
851 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
852 base
= initial_condition (access_fn
);
853 split_constant_offset (base
, &base
, &off
);
854 access_fn
= chrec_replace_initial_condition (access_fn
,
855 fold_convert (TREE_TYPE (base
), off
));
857 TREE_OPERAND (aref
, 0) = base
;
858 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
861 DR_BASE_OBJECT (dr
) = ref
;
862 DR_ACCESS_FNS (dr
) = access_fns
;
865 /* Extracts the alias analysis information from the memory reference DR. */
868 dr_analyze_alias (struct data_reference
*dr
)
870 tree ref
= DR_REF (dr
);
871 tree base
= get_base_address (ref
), addr
;
873 if (INDIRECT_REF_P (base
))
875 addr
= TREE_OPERAND (base
, 0);
876 if (TREE_CODE (addr
) == SSA_NAME
)
877 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
881 /* Returns true if the address of DR is invariant. */
884 dr_address_invariant_p (struct data_reference
*dr
)
889 for (i
= 0; VEC_iterate (tree
, DR_ACCESS_FNS (dr
), i
, idx
); i
++)
890 if (tree_contains_chrecs (idx
, NULL
))
896 /* Frees data reference DR. */
899 free_data_ref (data_reference_p dr
)
901 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
905 /* Analyzes memory reference MEMREF accessed in STMT. The reference
906 is read if IS_READ is true, write otherwise. Returns the
907 data_reference description of MEMREF. NEST is the outermost loop of the
908 loop nest in that the reference should be analyzed. */
910 struct data_reference
*
911 create_data_ref (struct loop
*nest
, tree memref
, gimple stmt
, bool is_read
)
913 struct data_reference
*dr
;
915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
917 fprintf (dump_file
, "Creating dr for ");
918 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
919 fprintf (dump_file
, "\n");
922 dr
= XCNEW (struct data_reference
);
924 DR_REF (dr
) = memref
;
925 DR_IS_READ (dr
) = is_read
;
927 dr_analyze_innermost (dr
);
928 dr_analyze_indices (dr
, nest
);
929 dr_analyze_alias (dr
);
931 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
933 fprintf (dump_file
, "\tbase_address: ");
934 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
935 fprintf (dump_file
, "\n\toffset from base address: ");
936 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
937 fprintf (dump_file
, "\n\tconstant offset from base address: ");
938 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
939 fprintf (dump_file
, "\n\tstep: ");
940 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
941 fprintf (dump_file
, "\n\taligned to: ");
942 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
943 fprintf (dump_file
, "\n\tbase_object: ");
944 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
945 fprintf (dump_file
, "\n");
951 /* Returns true if FNA == FNB. */
954 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
956 unsigned i
, n
= VEC_length (tree
, fna
);
958 if (n
!= VEC_length (tree
, fnb
))
961 for (i
= 0; i
< n
; i
++)
962 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
963 VEC_index (tree
, fnb
, i
), 0))
969 /* If all the functions in CF are the same, returns one of them,
970 otherwise returns NULL. */
973 common_affine_function (conflict_function
*cf
)
978 if (!CF_NONTRIVIAL_P (cf
))
983 for (i
= 1; i
< cf
->n
; i
++)
984 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
990 /* Returns the base of the affine function FN. */
993 affine_function_base (affine_fn fn
)
995 return VEC_index (tree
, fn
, 0);
998 /* Returns true if FN is a constant. */
1001 affine_function_constant_p (affine_fn fn
)
1006 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
1007 if (!integer_zerop (coef
))
1013 /* Returns true if FN is the zero constant function. */
1016 affine_function_zero_p (affine_fn fn
)
1018 return (integer_zerop (affine_function_base (fn
))
1019 && affine_function_constant_p (fn
));
1022 /* Returns a signed integer type with the largest precision from TA
1026 signed_type_for_types (tree ta
, tree tb
)
1028 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
1029 return signed_type_for (ta
);
1031 return signed_type_for (tb
);
1034 /* Applies operation OP on affine functions FNA and FNB, and returns the
1038 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
1044 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
1046 n
= VEC_length (tree
, fna
);
1047 m
= VEC_length (tree
, fnb
);
1051 n
= VEC_length (tree
, fnb
);
1052 m
= VEC_length (tree
, fna
);
1055 ret
= VEC_alloc (tree
, heap
, m
);
1056 for (i
= 0; i
< n
; i
++)
1058 tree type
= signed_type_for_types (TREE_TYPE (VEC_index (tree
, fna
, i
)),
1059 TREE_TYPE (VEC_index (tree
, fnb
, i
)));
1061 VEC_quick_push (tree
, ret
,
1062 fold_build2 (op
, type
,
1063 VEC_index (tree
, fna
, i
),
1064 VEC_index (tree
, fnb
, i
)));
1067 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
1068 VEC_quick_push (tree
, ret
,
1069 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1070 coef
, integer_zero_node
));
1071 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
1072 VEC_quick_push (tree
, ret
,
1073 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1074 integer_zero_node
, coef
));
1079 /* Returns the sum of affine functions FNA and FNB. */
1082 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1084 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1087 /* Returns the difference of affine functions FNA and FNB. */
1090 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1092 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1095 /* Frees affine function FN. */
1098 affine_fn_free (affine_fn fn
)
1100 VEC_free (tree
, heap
, fn
);
1103 /* Determine for each subscript in the data dependence relation DDR
1107 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1109 conflict_function
*cf_a
, *cf_b
;
1110 affine_fn fn_a
, fn_b
, diff
;
1112 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1116 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1118 struct subscript
*subscript
;
1120 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1121 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1122 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1124 fn_a
= common_affine_function (cf_a
);
1125 fn_b
= common_affine_function (cf_b
);
1128 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1131 diff
= affine_fn_minus (fn_a
, fn_b
);
1133 if (affine_function_constant_p (diff
))
1134 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1136 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1138 affine_fn_free (diff
);
1143 /* Returns the conflict function for "unknown". */
1145 static conflict_function
*
1146 conflict_fn_not_known (void)
1148 conflict_function
*fn
= XCNEW (conflict_function
);
1154 /* Returns the conflict function for "independent". */
1156 static conflict_function
*
1157 conflict_fn_no_dependence (void)
1159 conflict_function
*fn
= XCNEW (conflict_function
);
1160 fn
->n
= NO_DEPENDENCE
;
1165 /* Returns true if the address of OBJ is invariant in LOOP. */
1168 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1170 while (handled_component_p (obj
))
1172 if (TREE_CODE (obj
) == ARRAY_REF
)
1174 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1175 need to check the stride and the lower bound of the reference. */
1176 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1178 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1182 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1184 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1188 obj
= TREE_OPERAND (obj
, 0);
1191 if (!INDIRECT_REF_P (obj
))
1194 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1198 /* Returns true if A and B are accesses to different objects, or to different
1199 fields of the same object. */
1202 disjoint_objects_p (tree a
, tree b
)
1204 tree base_a
, base_b
;
1205 VEC (tree
, heap
) *comp_a
= NULL
, *comp_b
= NULL
;
1208 base_a
= get_base_address (a
);
1209 base_b
= get_base_address (b
);
1213 && base_a
!= base_b
)
1216 if (!operand_equal_p (base_a
, base_b
, 0))
1219 /* Compare the component references of A and B. We must start from the inner
1220 ones, so record them to the vector first. */
1221 while (handled_component_p (a
))
1223 VEC_safe_push (tree
, heap
, comp_a
, a
);
1224 a
= TREE_OPERAND (a
, 0);
1226 while (handled_component_p (b
))
1228 VEC_safe_push (tree
, heap
, comp_b
, b
);
1229 b
= TREE_OPERAND (b
, 0);
1235 if (VEC_length (tree
, comp_a
) == 0
1236 || VEC_length (tree
, comp_b
) == 0)
1239 a
= VEC_pop (tree
, comp_a
);
1240 b
= VEC_pop (tree
, comp_b
);
1242 /* Real and imaginary part of a variable do not alias. */
1243 if ((TREE_CODE (a
) == REALPART_EXPR
1244 && TREE_CODE (b
) == IMAGPART_EXPR
)
1245 || (TREE_CODE (a
) == IMAGPART_EXPR
1246 && TREE_CODE (b
) == REALPART_EXPR
))
1252 if (TREE_CODE (a
) != TREE_CODE (b
))
1255 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1256 DR_BASE_OBJECT are always zero. */
1257 if (TREE_CODE (a
) == ARRAY_REF
)
1259 else if (TREE_CODE (a
) == COMPONENT_REF
)
1261 if (operand_equal_p (TREE_OPERAND (a
, 1), TREE_OPERAND (b
, 1), 0))
1264 /* Different fields of unions may overlap. */
1265 base_a
= TREE_OPERAND (a
, 0);
1266 if (TREE_CODE (TREE_TYPE (base_a
)) == UNION_TYPE
)
1269 /* Different fields of structures cannot. */
1277 VEC_free (tree
, heap
, comp_a
);
1278 VEC_free (tree
, heap
, comp_b
);
1283 /* Returns false if we can prove that data references A and B do not alias,
1287 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
)
1289 const_tree addr_a
= DR_BASE_ADDRESS (a
);
1290 const_tree addr_b
= DR_BASE_ADDRESS (b
);
1291 const_tree type_a
, type_b
;
1292 const_tree decl_a
= NULL_TREE
, decl_b
= NULL_TREE
;
1294 /* If the accessed objects are disjoint, the memory references do not
1296 if (disjoint_objects_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
)))
1299 /* Query the alias oracle. */
1300 if (!DR_IS_READ (a
) && !DR_IS_READ (b
))
1302 if (!refs_output_dependent_p (DR_REF (a
), DR_REF (b
)))
1305 else if (DR_IS_READ (a
) && !DR_IS_READ (b
))
1307 if (!refs_anti_dependent_p (DR_REF (a
), DR_REF (b
)))
1310 else if (!refs_may_alias_p (DR_REF (a
), DR_REF (b
)))
1313 if (!addr_a
|| !addr_b
)
1316 /* If the references are based on different static objects, they cannot
1317 alias (PTA should be able to disambiguate such accesses, but often
1319 if (TREE_CODE (addr_a
) == ADDR_EXPR
1320 && TREE_CODE (addr_b
) == ADDR_EXPR
)
1321 return TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0);
1323 /* An instruction writing through a restricted pointer is "independent" of any
1324 instruction reading or writing through a different restricted pointer,
1325 in the same block/scope. */
1327 type_a
= TREE_TYPE (addr_a
);
1328 type_b
= TREE_TYPE (addr_b
);
1329 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
1331 if (TREE_CODE (addr_a
) == SSA_NAME
)
1332 decl_a
= SSA_NAME_VAR (addr_a
);
1333 if (TREE_CODE (addr_b
) == SSA_NAME
)
1334 decl_b
= SSA_NAME_VAR (addr_b
);
1336 if (TYPE_RESTRICT (type_a
) && TYPE_RESTRICT (type_b
)
1337 && (!DR_IS_READ (a
) || !DR_IS_READ (b
))
1338 && decl_a
&& DECL_P (decl_a
)
1339 && decl_b
&& DECL_P (decl_b
)
1341 && TREE_CODE (DECL_CONTEXT (decl_a
)) == FUNCTION_DECL
1342 && DECL_CONTEXT (decl_a
) == DECL_CONTEXT (decl_b
))
1348 static void compute_self_dependence (struct data_dependence_relation
*);
1350 /* Initialize a data dependence relation between data accesses A and
1351 B. NB_LOOPS is the number of loops surrounding the references: the
1352 size of the classic distance/direction vectors. */
1354 static struct data_dependence_relation
*
1355 initialize_data_dependence_relation (struct data_reference
*a
,
1356 struct data_reference
*b
,
1357 VEC (loop_p
, heap
) *loop_nest
)
1359 struct data_dependence_relation
*res
;
1362 res
= XNEW (struct data_dependence_relation
);
1365 DDR_LOOP_NEST (res
) = NULL
;
1366 DDR_REVERSED_P (res
) = false;
1367 DDR_SUBSCRIPTS (res
) = NULL
;
1368 DDR_DIR_VECTS (res
) = NULL
;
1369 DDR_DIST_VECTS (res
) = NULL
;
1371 if (a
== NULL
|| b
== NULL
)
1373 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1377 /* If the data references do not alias, then they are independent. */
1378 if (!dr_may_alias_p (a
, b
))
1380 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1384 /* When the references are exactly the same, don't spend time doing
1385 the data dependence tests, just initialize the ddr and return. */
1386 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1388 DDR_AFFINE_P (res
) = true;
1389 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1390 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1391 DDR_LOOP_NEST (res
) = loop_nest
;
1392 DDR_INNER_LOOP (res
) = 0;
1393 DDR_SELF_REFERENCE (res
) = true;
1394 compute_self_dependence (res
);
1398 /* If the references do not access the same object, we do not know
1399 whether they alias or not. */
1400 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1402 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1406 /* If the base of the object is not invariant in the loop nest, we cannot
1407 analyze it. TODO -- in fact, it would suffice to record that there may
1408 be arbitrary dependences in the loops where the base object varies. */
1410 && !object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1411 DR_BASE_OBJECT (a
)))
1413 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1417 gcc_assert (DR_NUM_DIMENSIONS (a
) == DR_NUM_DIMENSIONS (b
));
1419 DDR_AFFINE_P (res
) = true;
1420 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1421 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1422 DDR_LOOP_NEST (res
) = loop_nest
;
1423 DDR_INNER_LOOP (res
) = 0;
1424 DDR_SELF_REFERENCE (res
) = false;
1426 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1428 struct subscript
*subscript
;
1430 subscript
= XNEW (struct subscript
);
1431 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1432 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1433 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1434 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1435 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1441 /* Frees memory used by the conflict function F. */
1444 free_conflict_function (conflict_function
*f
)
1448 if (CF_NONTRIVIAL_P (f
))
1450 for (i
= 0; i
< f
->n
; i
++)
1451 affine_fn_free (f
->fns
[i
]);
1456 /* Frees memory used by SUBSCRIPTS. */
1459 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1464 for (i
= 0; VEC_iterate (subscript_p
, subscripts
, i
, s
); i
++)
1466 free_conflict_function (s
->conflicting_iterations_in_a
);
1467 free_conflict_function (s
->conflicting_iterations_in_b
);
1470 VEC_free (subscript_p
, heap
, subscripts
);
1473 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1477 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1480 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1482 fprintf (dump_file
, "(dependence classified: ");
1483 print_generic_expr (dump_file
, chrec
, 0);
1484 fprintf (dump_file
, ")\n");
1487 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1488 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1489 DDR_SUBSCRIPTS (ddr
) = NULL
;
1492 /* The dependence relation DDR cannot be represented by a distance
1496 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1499 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1501 DDR_AFFINE_P (ddr
) = false;
1506 /* This section contains the classic Banerjee tests. */
1508 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1509 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1512 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1514 return (evolution_function_is_constant_p (chrec_a
)
1515 && evolution_function_is_constant_p (chrec_b
));
1518 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1519 variable, i.e., if the SIV (Single Index Variable) test is true. */
1522 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1524 if ((evolution_function_is_constant_p (chrec_a
)
1525 && evolution_function_is_univariate_p (chrec_b
))
1526 || (evolution_function_is_constant_p (chrec_b
)
1527 && evolution_function_is_univariate_p (chrec_a
)))
1530 if (evolution_function_is_univariate_p (chrec_a
)
1531 && evolution_function_is_univariate_p (chrec_b
))
1533 switch (TREE_CODE (chrec_a
))
1535 case POLYNOMIAL_CHREC
:
1536 switch (TREE_CODE (chrec_b
))
1538 case POLYNOMIAL_CHREC
:
1539 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1554 /* Creates a conflict function with N dimensions. The affine functions
1555 in each dimension follow. */
1557 static conflict_function
*
1558 conflict_fn (unsigned n
, ...)
1561 conflict_function
*ret
= XCNEW (conflict_function
);
1564 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1568 for (i
= 0; i
< n
; i
++)
1569 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1575 /* Returns constant affine function with value CST. */
1578 affine_fn_cst (tree cst
)
1580 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1581 VEC_quick_push (tree
, fn
, cst
);
1585 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1588 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1590 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1593 gcc_assert (dim
> 0);
1594 VEC_quick_push (tree
, fn
, cst
);
1595 for (i
= 1; i
< dim
; i
++)
1596 VEC_quick_push (tree
, fn
, integer_zero_node
);
1597 VEC_quick_push (tree
, fn
, coef
);
1601 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1602 *OVERLAPS_B are initialized to the functions that describe the
1603 relation between the elements accessed twice by CHREC_A and
1604 CHREC_B. For k >= 0, the following property is verified:
1606 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1609 analyze_ziv_subscript (tree chrec_a
,
1611 conflict_function
**overlaps_a
,
1612 conflict_function
**overlaps_b
,
1613 tree
*last_conflicts
)
1615 tree type
, difference
;
1616 dependence_stats
.num_ziv
++;
1618 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1619 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1621 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1622 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1623 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1624 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1626 switch (TREE_CODE (difference
))
1629 if (integer_zerop (difference
))
1631 /* The difference is equal to zero: the accessed index
1632 overlaps for each iteration in the loop. */
1633 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1634 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1635 *last_conflicts
= chrec_dont_know
;
1636 dependence_stats
.num_ziv_dependent
++;
1640 /* The accesses do not overlap. */
1641 *overlaps_a
= conflict_fn_no_dependence ();
1642 *overlaps_b
= conflict_fn_no_dependence ();
1643 *last_conflicts
= integer_zero_node
;
1644 dependence_stats
.num_ziv_independent
++;
1649 /* We're not sure whether the indexes overlap. For the moment,
1650 conservatively answer "don't know". */
1651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1652 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1654 *overlaps_a
= conflict_fn_not_known ();
1655 *overlaps_b
= conflict_fn_not_known ();
1656 *last_conflicts
= chrec_dont_know
;
1657 dependence_stats
.num_ziv_unimplemented
++;
1661 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1662 fprintf (dump_file
, ")\n");
1665 /* Sets NIT to the estimated number of executions of the statements in
1666 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1667 large as the number of iterations. If we have no reliable estimate,
1668 the function returns false, otherwise returns true. */
1671 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
1674 estimate_numbers_of_iterations_loop (loop
);
1677 if (!loop
->any_upper_bound
)
1680 *nit
= loop
->nb_iterations_upper_bound
;
1684 if (!loop
->any_estimate
)
1687 *nit
= loop
->nb_iterations_estimate
;
1693 /* Similar to estimated_loop_iterations, but returns the estimate only
1694 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1695 on the number of iterations of LOOP could not be derived, returns -1. */
1698 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
1701 HOST_WIDE_INT hwi_nit
;
1703 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1706 if (!double_int_fits_in_shwi_p (nit
))
1708 hwi_nit
= double_int_to_shwi (nit
);
1710 return hwi_nit
< 0 ? -1 : hwi_nit
;
1713 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1714 and only if it fits to the int type. If this is not the case, or the
1715 estimate on the number of iterations of LOOP could not be derived, returns
1719 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
1724 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1725 return chrec_dont_know
;
1727 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
1728 if (!double_int_fits_to_tree_p (type
, nit
))
1729 return chrec_dont_know
;
1731 return double_int_to_tree (type
, nit
);
1734 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1735 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1736 *OVERLAPS_B are initialized to the functions that describe the
1737 relation between the elements accessed twice by CHREC_A and
1738 CHREC_B. For k >= 0, the following property is verified:
1740 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1743 analyze_siv_subscript_cst_affine (tree chrec_a
,
1745 conflict_function
**overlaps_a
,
1746 conflict_function
**overlaps_b
,
1747 tree
*last_conflicts
)
1749 bool value0
, value1
, value2
;
1750 tree type
, difference
, tmp
;
1752 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1753 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1754 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1755 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1757 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1759 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1760 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1762 dependence_stats
.num_siv_unimplemented
++;
1763 *overlaps_a
= conflict_fn_not_known ();
1764 *overlaps_b
= conflict_fn_not_known ();
1765 *last_conflicts
= chrec_dont_know
;
1770 if (value0
== false)
1772 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1775 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1777 *overlaps_a
= conflict_fn_not_known ();
1778 *overlaps_b
= conflict_fn_not_known ();
1779 *last_conflicts
= chrec_dont_know
;
1780 dependence_stats
.num_siv_unimplemented
++;
1789 chrec_b = {10, +, 1}
1792 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1794 HOST_WIDE_INT numiter
;
1795 struct loop
*loop
= get_chrec_loop (chrec_b
);
1797 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1798 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1799 fold_build1 (ABS_EXPR
, type
, difference
),
1800 CHREC_RIGHT (chrec_b
));
1801 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1802 *last_conflicts
= integer_one_node
;
1805 /* Perform weak-zero siv test to see if overlap is
1806 outside the loop bounds. */
1807 numiter
= estimated_loop_iterations_int (loop
, false);
1810 && compare_tree_int (tmp
, numiter
) > 0)
1812 free_conflict_function (*overlaps_a
);
1813 free_conflict_function (*overlaps_b
);
1814 *overlaps_a
= conflict_fn_no_dependence ();
1815 *overlaps_b
= conflict_fn_no_dependence ();
1816 *last_conflicts
= integer_zero_node
;
1817 dependence_stats
.num_siv_independent
++;
1820 dependence_stats
.num_siv_dependent
++;
1824 /* When the step does not divide the difference, there are
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
++;
1840 chrec_b = {10, +, -1}
1842 In this case, chrec_a will not overlap with chrec_b. */
1843 *overlaps_a
= conflict_fn_no_dependence ();
1844 *overlaps_b
= conflict_fn_no_dependence ();
1845 *last_conflicts
= integer_zero_node
;
1846 dependence_stats
.num_siv_independent
++;
1853 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1855 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1856 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1858 *overlaps_a
= conflict_fn_not_known ();
1859 *overlaps_b
= conflict_fn_not_known ();
1860 *last_conflicts
= chrec_dont_know
;
1861 dependence_stats
.num_siv_unimplemented
++;
1866 if (value2
== false)
1870 chrec_b = {10, +, -1}
1872 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1874 HOST_WIDE_INT numiter
;
1875 struct loop
*loop
= get_chrec_loop (chrec_b
);
1877 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1878 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1879 CHREC_RIGHT (chrec_b
));
1880 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1881 *last_conflicts
= integer_one_node
;
1883 /* Perform weak-zero siv test to see if overlap is
1884 outside the loop bounds. */
1885 numiter
= estimated_loop_iterations_int (loop
, false);
1888 && compare_tree_int (tmp
, numiter
) > 0)
1890 free_conflict_function (*overlaps_a
);
1891 free_conflict_function (*overlaps_b
);
1892 *overlaps_a
= conflict_fn_no_dependence ();
1893 *overlaps_b
= conflict_fn_no_dependence ();
1894 *last_conflicts
= integer_zero_node
;
1895 dependence_stats
.num_siv_independent
++;
1898 dependence_stats
.num_siv_dependent
++;
1902 /* When the step does not divide the difference, there
1906 *overlaps_a
= conflict_fn_no_dependence ();
1907 *overlaps_b
= conflict_fn_no_dependence ();
1908 *last_conflicts
= integer_zero_node
;
1909 dependence_stats
.num_siv_independent
++;
1919 In this case, chrec_a will not overlap with chrec_b. */
1920 *overlaps_a
= conflict_fn_no_dependence ();
1921 *overlaps_b
= conflict_fn_no_dependence ();
1922 *last_conflicts
= integer_zero_node
;
1923 dependence_stats
.num_siv_independent
++;
1931 /* Helper recursive function for initializing the matrix A. Returns
1932 the initial value of CHREC. */
1935 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1939 switch (TREE_CODE (chrec
))
1941 case POLYNOMIAL_CHREC
:
1942 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
1944 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1945 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1951 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1952 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
1954 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
1959 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1960 return chrec_convert (chrec_type (chrec
), op
, NULL
);
1965 /* Handle ~X as -1 - X. */
1966 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1967 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
1968 build_int_cst (TREE_TYPE (chrec
), -1), op
);
1980 #define FLOOR_DIV(x,y) ((x) / (y))
1982 /* Solves the special case of the Diophantine equation:
1983 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1985 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1986 number of iterations that loops X and Y run. The overlaps will be
1987 constructed as evolutions in dimension DIM. */
1990 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1991 affine_fn
*overlaps_a
,
1992 affine_fn
*overlaps_b
,
1993 tree
*last_conflicts
, int dim
)
1995 if (((step_a
> 0 && step_b
> 0)
1996 || (step_a
< 0 && step_b
< 0)))
1998 int step_overlaps_a
, step_overlaps_b
;
1999 int gcd_steps_a_b
, last_conflict
, tau2
;
2001 gcd_steps_a_b
= gcd (step_a
, step_b
);
2002 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2003 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2007 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2008 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2009 last_conflict
= tau2
;
2010 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2013 *last_conflicts
= chrec_dont_know
;
2015 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
2016 build_int_cst (NULL_TREE
,
2018 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
2019 build_int_cst (NULL_TREE
,
2025 *overlaps_a
= affine_fn_cst (integer_zero_node
);
2026 *overlaps_b
= affine_fn_cst (integer_zero_node
);
2027 *last_conflicts
= integer_zero_node
;
2031 /* Solves the special case of a Diophantine equation where CHREC_A is
2032 an affine bivariate function, and CHREC_B is an affine univariate
2033 function. For example,
2035 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2037 has the following overlapping functions:
2039 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2040 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2041 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2043 FORNOW: This is a specialized implementation for a case occurring in
2044 a common benchmark. Implement the general algorithm. */
2047 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2048 conflict_function
**overlaps_a
,
2049 conflict_function
**overlaps_b
,
2050 tree
*last_conflicts
)
2052 bool xz_p
, yz_p
, xyz_p
;
2053 int step_x
, step_y
, step_z
;
2054 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
2055 affine_fn overlaps_a_xz
, overlaps_b_xz
;
2056 affine_fn overlaps_a_yz
, overlaps_b_yz
;
2057 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
2058 affine_fn ova1
, ova2
, ovb
;
2059 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
2061 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2062 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2063 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2066 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a
)),
2068 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), false);
2069 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), false);
2071 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2073 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2074 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2076 *overlaps_a
= conflict_fn_not_known ();
2077 *overlaps_b
= conflict_fn_not_known ();
2078 *last_conflicts
= chrec_dont_know
;
2082 niter
= MIN (niter_x
, niter_z
);
2083 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2086 &last_conflicts_xz
, 1);
2087 niter
= MIN (niter_y
, niter_z
);
2088 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2091 &last_conflicts_yz
, 2);
2092 niter
= MIN (niter_x
, niter_z
);
2093 niter
= MIN (niter_y
, niter
);
2094 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2097 &last_conflicts_xyz
, 3);
2099 xz_p
= !integer_zerop (last_conflicts_xz
);
2100 yz_p
= !integer_zerop (last_conflicts_yz
);
2101 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2103 if (xz_p
|| yz_p
|| xyz_p
)
2105 ova1
= affine_fn_cst (integer_zero_node
);
2106 ova2
= affine_fn_cst (integer_zero_node
);
2107 ovb
= affine_fn_cst (integer_zero_node
);
2110 affine_fn t0
= ova1
;
2113 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2114 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2115 affine_fn_free (t0
);
2116 affine_fn_free (t2
);
2117 *last_conflicts
= last_conflicts_xz
;
2121 affine_fn t0
= ova2
;
2124 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2125 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2126 affine_fn_free (t0
);
2127 affine_fn_free (t2
);
2128 *last_conflicts
= last_conflicts_yz
;
2132 affine_fn t0
= ova1
;
2133 affine_fn t2
= ova2
;
2136 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2137 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2138 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2139 affine_fn_free (t0
);
2140 affine_fn_free (t2
);
2141 affine_fn_free (t4
);
2142 *last_conflicts
= last_conflicts_xyz
;
2144 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2145 *overlaps_b
= conflict_fn (1, ovb
);
2149 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2150 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2151 *last_conflicts
= integer_zero_node
;
2154 affine_fn_free (overlaps_a_xz
);
2155 affine_fn_free (overlaps_b_xz
);
2156 affine_fn_free (overlaps_a_yz
);
2157 affine_fn_free (overlaps_b_yz
);
2158 affine_fn_free (overlaps_a_xyz
);
2159 affine_fn_free (overlaps_b_xyz
);
2162 /* Determines the overlapping elements due to accesses CHREC_A and
2163 CHREC_B, that are affine functions. This function cannot handle
2164 symbolic evolution functions, ie. when initial conditions are
2165 parameters, because it uses lambda matrices of integers. */
2168 analyze_subscript_affine_affine (tree chrec_a
,
2170 conflict_function
**overlaps_a
,
2171 conflict_function
**overlaps_b
,
2172 tree
*last_conflicts
)
2174 unsigned nb_vars_a
, nb_vars_b
, dim
;
2175 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2176 lambda_matrix A
, U
, S
;
2177 struct obstack scratch_obstack
;
2179 if (eq_evolutions_p (chrec_a
, chrec_b
))
2181 /* The accessed index overlaps for each iteration in the
2183 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2184 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2185 *last_conflicts
= chrec_dont_know
;
2188 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2189 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2191 /* For determining the initial intersection, we have to solve a
2192 Diophantine equation. This is the most time consuming part.
2194 For answering to the question: "Is there a dependence?" we have
2195 to prove that there exists a solution to the Diophantine
2196 equation, and that the solution is in the iteration domain,
2197 i.e. the solution is positive or zero, and that the solution
2198 happens before the upper bound loop.nb_iterations. Otherwise
2199 there is no dependence. This function outputs a description of
2200 the iterations that hold the intersections. */
2202 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2203 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2205 gcc_obstack_init (&scratch_obstack
);
2207 dim
= nb_vars_a
+ nb_vars_b
;
2208 U
= lambda_matrix_new (dim
, dim
, &scratch_obstack
);
2209 A
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2210 S
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2212 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2213 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2214 gamma
= init_b
- init_a
;
2216 /* Don't do all the hard work of solving the Diophantine equation
2217 when we already know the solution: for example,
2220 | gamma = 3 - 3 = 0.
2221 Then the first overlap occurs during the first iterations:
2222 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2226 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2228 HOST_WIDE_INT step_a
, step_b
;
2229 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2232 niter_a
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
),
2234 niter_b
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
),
2236 niter
= MIN (niter_a
, niter_b
);
2237 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2238 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2240 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2243 *overlaps_a
= conflict_fn (1, ova
);
2244 *overlaps_b
= conflict_fn (1, ovb
);
2247 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2248 compute_overlap_steps_for_affine_1_2
2249 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2251 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2252 compute_overlap_steps_for_affine_1_2
2253 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2257 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2258 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2259 *overlaps_a
= conflict_fn_not_known ();
2260 *overlaps_b
= conflict_fn_not_known ();
2261 *last_conflicts
= chrec_dont_know
;
2263 goto end_analyze_subs_aa
;
2267 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2272 lambda_matrix_row_negate (U
, dim
, 0);
2274 gcd_alpha_beta
= S
[0][0];
2276 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2277 but that is a quite strange case. Instead of ICEing, answer
2279 if (gcd_alpha_beta
== 0)
2281 *overlaps_a
= conflict_fn_not_known ();
2282 *overlaps_b
= conflict_fn_not_known ();
2283 *last_conflicts
= chrec_dont_know
;
2284 goto end_analyze_subs_aa
;
2287 /* The classic "gcd-test". */
2288 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2290 /* The "gcd-test" has determined that there is no integer
2291 solution, i.e. there is no dependence. */
2292 *overlaps_a
= conflict_fn_no_dependence ();
2293 *overlaps_b
= conflict_fn_no_dependence ();
2294 *last_conflicts
= integer_zero_node
;
2297 /* Both access functions are univariate. This includes SIV and MIV cases. */
2298 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2300 /* Both functions should have the same evolution sign. */
2301 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2302 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2304 /* The solutions are given by:
2306 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2309 For a given integer t. Using the following variables,
2311 | i0 = u11 * gamma / gcd_alpha_beta
2312 | j0 = u12 * gamma / gcd_alpha_beta
2319 | y0 = j0 + j1 * t. */
2320 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2322 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2323 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2327 if ((i1
== 0 && i0
< 0)
2328 || (j1
== 0 && j0
< 0))
2330 /* There is no solution.
2331 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2332 falls in here, but for the moment we don't look at the
2333 upper bound of the iteration domain. */
2334 *overlaps_a
= conflict_fn_no_dependence ();
2335 *overlaps_b
= conflict_fn_no_dependence ();
2336 *last_conflicts
= integer_zero_node
;
2337 goto end_analyze_subs_aa
;
2340 if (i1
> 0 && j1
> 0)
2342 HOST_WIDE_INT niter_a
= estimated_loop_iterations_int
2343 (get_chrec_loop (chrec_a
), false);
2344 HOST_WIDE_INT niter_b
= estimated_loop_iterations_int
2345 (get_chrec_loop (chrec_b
), false);
2346 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2348 /* (X0, Y0) is a solution of the Diophantine equation:
2349 "chrec_a (X0) = chrec_b (Y0)". */
2350 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2352 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2353 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2355 /* (X1, Y1) is the smallest positive solution of the eq
2356 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2357 first conflict occurs. */
2358 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2359 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2360 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2364 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2365 FLOOR_DIV (niter
- j0
, j1
));
2366 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2368 /* If the overlap occurs outside of the bounds of the
2369 loop, there is no dependence. */
2370 if (x1
>= niter
|| y1
>= niter
)
2372 *overlaps_a
= conflict_fn_no_dependence ();
2373 *overlaps_b
= conflict_fn_no_dependence ();
2374 *last_conflicts
= integer_zero_node
;
2375 goto end_analyze_subs_aa
;
2378 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2381 *last_conflicts
= chrec_dont_know
;
2385 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2387 build_int_cst (NULL_TREE
, i1
)));
2390 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2392 build_int_cst (NULL_TREE
, j1
)));
2396 /* FIXME: For the moment, the upper bound of the
2397 iteration domain for i and j is not checked. */
2398 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2399 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2400 *overlaps_a
= conflict_fn_not_known ();
2401 *overlaps_b
= conflict_fn_not_known ();
2402 *last_conflicts
= chrec_dont_know
;
2407 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2408 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2409 *overlaps_a
= conflict_fn_not_known ();
2410 *overlaps_b
= conflict_fn_not_known ();
2411 *last_conflicts
= chrec_dont_know
;
2416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2417 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2418 *overlaps_a
= conflict_fn_not_known ();
2419 *overlaps_b
= conflict_fn_not_known ();
2420 *last_conflicts
= chrec_dont_know
;
2423 end_analyze_subs_aa
:
2424 obstack_free (&scratch_obstack
, NULL
);
2425 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2427 fprintf (dump_file
, " (overlaps_a = ");
2428 dump_conflict_function (dump_file
, *overlaps_a
);
2429 fprintf (dump_file
, ")\n (overlaps_b = ");
2430 dump_conflict_function (dump_file
, *overlaps_b
);
2431 fprintf (dump_file
, ")\n");
2432 fprintf (dump_file
, ")\n");
2436 /* Returns true when analyze_subscript_affine_affine can be used for
2437 determining the dependence relation between chrec_a and chrec_b,
2438 that contain symbols. This function modifies chrec_a and chrec_b
2439 such that the analysis result is the same, and such that they don't
2440 contain symbols, and then can safely be passed to the analyzer.
2442 Example: The analysis of the following tuples of evolutions produce
2443 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2446 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2447 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2451 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2453 tree diff
, type
, left_a
, left_b
, right_b
;
2455 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2456 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2457 /* FIXME: For the moment not handled. Might be refined later. */
2460 type
= chrec_type (*chrec_a
);
2461 left_a
= CHREC_LEFT (*chrec_a
);
2462 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2463 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2465 if (!evolution_function_is_constant_p (diff
))
2468 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2469 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2471 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2472 diff
, CHREC_RIGHT (*chrec_a
));
2473 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2474 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2475 build_int_cst (type
, 0),
2480 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2481 *OVERLAPS_B are initialized to the functions that describe the
2482 relation between the elements accessed twice by CHREC_A and
2483 CHREC_B. For k >= 0, the following property is verified:
2485 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2488 analyze_siv_subscript (tree chrec_a
,
2490 conflict_function
**overlaps_a
,
2491 conflict_function
**overlaps_b
,
2492 tree
*last_conflicts
,
2495 dependence_stats
.num_siv
++;
2497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2498 fprintf (dump_file
, "(analyze_siv_subscript \n");
2500 if (evolution_function_is_constant_p (chrec_a
)
2501 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2502 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2503 overlaps_a
, overlaps_b
, last_conflicts
);
2505 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2506 && evolution_function_is_constant_p (chrec_b
))
2507 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2508 overlaps_b
, overlaps_a
, last_conflicts
);
2510 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2511 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2513 if (!chrec_contains_symbols (chrec_a
)
2514 && !chrec_contains_symbols (chrec_b
))
2516 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2517 overlaps_a
, overlaps_b
,
2520 if (CF_NOT_KNOWN_P (*overlaps_a
)
2521 || CF_NOT_KNOWN_P (*overlaps_b
))
2522 dependence_stats
.num_siv_unimplemented
++;
2523 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2524 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2525 dependence_stats
.num_siv_independent
++;
2527 dependence_stats
.num_siv_dependent
++;
2529 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2532 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2533 overlaps_a
, overlaps_b
,
2536 if (CF_NOT_KNOWN_P (*overlaps_a
)
2537 || CF_NOT_KNOWN_P (*overlaps_b
))
2538 dependence_stats
.num_siv_unimplemented
++;
2539 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2540 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2541 dependence_stats
.num_siv_independent
++;
2543 dependence_stats
.num_siv_dependent
++;
2546 goto siv_subscript_dontknow
;
2551 siv_subscript_dontknow
:;
2552 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2553 fprintf (dump_file
, "siv test failed: unimplemented.\n");
2554 *overlaps_a
= conflict_fn_not_known ();
2555 *overlaps_b
= conflict_fn_not_known ();
2556 *last_conflicts
= chrec_dont_know
;
2557 dependence_stats
.num_siv_unimplemented
++;
2560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2561 fprintf (dump_file
, ")\n");
2564 /* Returns false if we can prove that the greatest common divisor of the steps
2565 of CHREC does not divide CST, false otherwise. */
2568 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2570 HOST_WIDE_INT cd
= 0, val
;
2573 if (!host_integerp (cst
, 0))
2575 val
= tree_low_cst (cst
, 0);
2577 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2579 step
= CHREC_RIGHT (chrec
);
2580 if (!host_integerp (step
, 0))
2582 cd
= gcd (cd
, tree_low_cst (step
, 0));
2583 chrec
= CHREC_LEFT (chrec
);
2586 return val
% cd
== 0;
2589 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2590 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2591 functions that describe the relation between the elements accessed
2592 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2595 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2598 analyze_miv_subscript (tree chrec_a
,
2600 conflict_function
**overlaps_a
,
2601 conflict_function
**overlaps_b
,
2602 tree
*last_conflicts
,
2603 struct loop
*loop_nest
)
2605 /* FIXME: This is a MIV subscript, not yet handled.
2606 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2609 In the SIV test we had to solve a Diophantine equation with two
2610 variables. In the MIV case we have to solve a Diophantine
2611 equation with 2*n variables (if the subscript uses n IVs).
2613 tree type
, difference
;
2615 dependence_stats
.num_miv
++;
2616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2617 fprintf (dump_file
, "(analyze_miv_subscript \n");
2619 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2620 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2621 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2622 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2624 if (eq_evolutions_p (chrec_a
, chrec_b
))
2626 /* Access functions are the same: all the elements are accessed
2627 in the same order. */
2628 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2629 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2630 *last_conflicts
= estimated_loop_iterations_tree
2631 (get_chrec_loop (chrec_a
), true);
2632 dependence_stats
.num_miv_dependent
++;
2635 else if (evolution_function_is_constant_p (difference
)
2636 /* For the moment, the following is verified:
2637 evolution_function_is_affine_multivariate_p (chrec_a,
2639 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2641 /* testsuite/.../ssa-chrec-33.c
2642 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2644 The difference is 1, and all the evolution steps are multiples
2645 of 2, consequently there are no overlapping elements. */
2646 *overlaps_a
= conflict_fn_no_dependence ();
2647 *overlaps_b
= conflict_fn_no_dependence ();
2648 *last_conflicts
= integer_zero_node
;
2649 dependence_stats
.num_miv_independent
++;
2652 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2653 && !chrec_contains_symbols (chrec_a
)
2654 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2655 && !chrec_contains_symbols (chrec_b
))
2657 /* testsuite/.../ssa-chrec-35.c
2658 {0, +, 1}_2 vs. {0, +, 1}_3
2659 the overlapping elements are respectively located at iterations:
2660 {0, +, 1}_x and {0, +, 1}_x,
2661 in other words, we have the equality:
2662 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2665 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2666 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2668 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2669 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2671 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2672 overlaps_a
, overlaps_b
, last_conflicts
);
2674 if (CF_NOT_KNOWN_P (*overlaps_a
)
2675 || CF_NOT_KNOWN_P (*overlaps_b
))
2676 dependence_stats
.num_miv_unimplemented
++;
2677 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2678 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2679 dependence_stats
.num_miv_independent
++;
2681 dependence_stats
.num_miv_dependent
++;
2686 /* When the analysis is too difficult, answer "don't know". */
2687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2688 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2690 *overlaps_a
= conflict_fn_not_known ();
2691 *overlaps_b
= conflict_fn_not_known ();
2692 *last_conflicts
= chrec_dont_know
;
2693 dependence_stats
.num_miv_unimplemented
++;
2696 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2697 fprintf (dump_file
, ")\n");
2700 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2701 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2702 OVERLAP_ITERATIONS_B are initialized with two functions that
2703 describe the iterations that contain conflicting elements.
2705 Remark: For an integer k >= 0, the following equality is true:
2707 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2711 analyze_overlapping_iterations (tree chrec_a
,
2713 conflict_function
**overlap_iterations_a
,
2714 conflict_function
**overlap_iterations_b
,
2715 tree
*last_conflicts
, struct loop
*loop_nest
)
2717 unsigned int lnn
= loop_nest
->num
;
2719 dependence_stats
.num_subscript_tests
++;
2721 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2723 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2724 fprintf (dump_file
, " (chrec_a = ");
2725 print_generic_expr (dump_file
, chrec_a
, 0);
2726 fprintf (dump_file
, ")\n (chrec_b = ");
2727 print_generic_expr (dump_file
, chrec_b
, 0);
2728 fprintf (dump_file
, ")\n");
2731 if (chrec_a
== NULL_TREE
2732 || chrec_b
== NULL_TREE
2733 || chrec_contains_undetermined (chrec_a
)
2734 || chrec_contains_undetermined (chrec_b
))
2736 dependence_stats
.num_subscript_undetermined
++;
2738 *overlap_iterations_a
= conflict_fn_not_known ();
2739 *overlap_iterations_b
= conflict_fn_not_known ();
2742 /* If they are the same chrec, and are affine, they overlap
2743 on every iteration. */
2744 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2745 && evolution_function_is_affine_multivariate_p (chrec_a
, lnn
))
2747 dependence_stats
.num_same_subscript_function
++;
2748 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2749 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2750 *last_conflicts
= chrec_dont_know
;
2753 /* If they aren't the same, and aren't affine, we can't do anything
2755 else if ((chrec_contains_symbols (chrec_a
)
2756 || chrec_contains_symbols (chrec_b
))
2757 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2758 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2760 dependence_stats
.num_subscript_undetermined
++;
2761 *overlap_iterations_a
= conflict_fn_not_known ();
2762 *overlap_iterations_b
= conflict_fn_not_known ();
2765 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2766 analyze_ziv_subscript (chrec_a
, chrec_b
,
2767 overlap_iterations_a
, overlap_iterations_b
,
2770 else if (siv_subscript_p (chrec_a
, chrec_b
))
2771 analyze_siv_subscript (chrec_a
, chrec_b
,
2772 overlap_iterations_a
, overlap_iterations_b
,
2773 last_conflicts
, lnn
);
2776 analyze_miv_subscript (chrec_a
, chrec_b
,
2777 overlap_iterations_a
, overlap_iterations_b
,
2778 last_conflicts
, loop_nest
);
2780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2782 fprintf (dump_file
, " (overlap_iterations_a = ");
2783 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2784 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2785 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2786 fprintf (dump_file
, ")\n");
2787 fprintf (dump_file
, ")\n");
2791 /* Helper function for uniquely inserting distance vectors. */
2794 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2799 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
2800 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2803 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2806 /* Helper function for uniquely inserting direction vectors. */
2809 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2814 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
2815 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2818 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2821 /* Add a distance of 1 on all the loops outer than INDEX. If we
2822 haven't yet determined a distance for this outer loop, push a new
2823 distance vector composed of the previous distance, and a distance
2824 of 1 for this outer loop. Example:
2832 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2833 save (0, 1), then we have to save (1, 0). */
2836 add_outer_distances (struct data_dependence_relation
*ddr
,
2837 lambda_vector dist_v
, int index
)
2839 /* For each outer loop where init_v is not set, the accesses are
2840 in dependence of distance 1 in the loop. */
2841 while (--index
>= 0)
2843 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2844 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2846 save_dist_v (ddr
, save_v
);
2850 /* Return false when fail to represent the data dependence as a
2851 distance vector. INIT_B is set to true when a component has been
2852 added to the distance vector DIST_V. INDEX_CARRY is then set to
2853 the index in DIST_V that carries the dependence. */
2856 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2857 struct data_reference
*ddr_a
,
2858 struct data_reference
*ddr_b
,
2859 lambda_vector dist_v
, bool *init_b
,
2863 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2865 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2867 tree access_fn_a
, access_fn_b
;
2868 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2870 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2872 non_affine_dependence_relation (ddr
);
2876 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2877 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2879 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2880 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2883 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2884 DDR_LOOP_NEST (ddr
));
2885 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2886 DDR_LOOP_NEST (ddr
));
2888 /* The dependence is carried by the outermost loop. Example:
2895 In this case, the dependence is carried by loop_1. */
2896 index
= index_a
< index_b
? index_a
: index_b
;
2897 *index_carry
= MIN (index
, *index_carry
);
2899 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2901 non_affine_dependence_relation (ddr
);
2905 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2907 /* This is the subscript coupling test. If we have already
2908 recorded a distance for this loop (a distance coming from
2909 another subscript), it should be the same. For example,
2910 in the following code, there is no dependence:
2917 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2919 finalize_ddr_dependent (ddr
, chrec_known
);
2923 dist_v
[index
] = dist
;
2927 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2929 /* This can be for example an affine vs. constant dependence
2930 (T[i] vs. T[3]) that is not an affine dependence and is
2931 not representable as a distance vector. */
2932 non_affine_dependence_relation (ddr
);
2940 /* Return true when the DDR contains only constant access functions. */
2943 constant_access_functions (const struct data_dependence_relation
*ddr
)
2947 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2948 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2949 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2955 /* Helper function for the case where DDR_A and DDR_B are the same
2956 multivariate access function with a constant step. For an example
2960 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2963 tree c_1
= CHREC_LEFT (c_2
);
2964 tree c_0
= CHREC_LEFT (c_1
);
2965 lambda_vector dist_v
;
2968 /* Polynomials with more than 2 variables are not handled yet. When
2969 the evolution steps are parameters, it is not possible to
2970 represent the dependence using classical distance vectors. */
2971 if (TREE_CODE (c_0
) != INTEGER_CST
2972 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
2973 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
2975 DDR_AFFINE_P (ddr
) = false;
2979 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2980 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2982 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2983 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2984 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2985 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2998 save_dist_v (ddr
, dist_v
);
3000 add_outer_distances (ddr
, dist_v
, x_1
);
3003 /* Helper function for the case where DDR_A and DDR_B are the same
3004 access functions. */
3007 add_other_self_distances (struct data_dependence_relation
*ddr
)
3009 lambda_vector dist_v
;
3011 int index_carry
= DDR_NB_LOOPS (ddr
);
3013 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3015 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3017 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3019 if (!evolution_function_is_univariate_p (access_fun
))
3021 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3023 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3027 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
3029 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
3030 add_multivariate_self_dist (ddr
, access_fun
);
3032 /* The evolution step is not constant: it varies in
3033 the outer loop, so this cannot be represented by a
3034 distance vector. For example in pr34635.c the
3035 evolution is {0, +, {0, +, 4}_1}_2. */
3036 DDR_AFFINE_P (ddr
) = false;
3041 index_carry
= MIN (index_carry
,
3042 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3043 DDR_LOOP_NEST (ddr
)));
3047 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3048 add_outer_distances (ddr
, dist_v
, index_carry
);
3052 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
3054 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3056 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
3057 save_dist_v (ddr
, dist_v
);
3060 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3061 is the case for example when access functions are the same and
3062 equal to a constant, as in:
3069 in which case the distance vectors are (0) and (1). */
3072 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
3076 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3078 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
3079 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
3080 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
3082 for (j
= 0; j
< ca
->n
; j
++)
3083 if (affine_function_zero_p (ca
->fns
[j
]))
3085 insert_innermost_unit_dist_vector (ddr
);
3089 for (j
= 0; j
< cb
->n
; j
++)
3090 if (affine_function_zero_p (cb
->fns
[j
]))
3092 insert_innermost_unit_dist_vector (ddr
);
3098 /* Compute the classic per loop distance vector. DDR is the data
3099 dependence relation to build a vector from. Return false when fail
3100 to represent the data dependence as a distance vector. */
3103 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3104 struct loop
*loop_nest
)
3106 bool init_b
= false;
3107 int index_carry
= DDR_NB_LOOPS (ddr
);
3108 lambda_vector dist_v
;
3110 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3113 if (same_access_functions (ddr
))
3115 /* Save the 0 vector. */
3116 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3117 save_dist_v (ddr
, dist_v
);
3119 if (constant_access_functions (ddr
))
3120 add_distance_for_zero_overlaps (ddr
);
3122 if (DDR_NB_LOOPS (ddr
) > 1)
3123 add_other_self_distances (ddr
);
3128 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3129 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3130 dist_v
, &init_b
, &index_carry
))
3133 /* Save the distance vector if we initialized one. */
3136 /* Verify a basic constraint: classic distance vectors should
3137 always be lexicographically positive.
3139 Data references are collected in the order of execution of
3140 the program, thus for the following loop
3142 | for (i = 1; i < 100; i++)
3143 | for (j = 1; j < 100; j++)
3145 | t = T[j+1][i-1]; // A
3146 | T[j][i] = t + 2; // B
3149 references are collected following the direction of the wind:
3150 A then B. The data dependence tests are performed also
3151 following this order, such that we're looking at the distance
3152 separating the elements accessed by A from the elements later
3153 accessed by B. But in this example, the distance returned by
3154 test_dep (A, B) is lexicographically negative (-1, 1), that
3155 means that the access A occurs later than B with respect to
3156 the outer loop, ie. we're actually looking upwind. In this
3157 case we solve test_dep (B, A) looking downwind to the
3158 lexicographically positive solution, that returns the
3159 distance vector (1, -1). */
3160 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3162 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3163 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3166 compute_subscript_distance (ddr
);
3167 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3168 save_v
, &init_b
, &index_carry
))
3170 save_dist_v (ddr
, save_v
);
3171 DDR_REVERSED_P (ddr
) = true;
3173 /* In this case there is a dependence forward for all the
3176 | for (k = 1; k < 100; k++)
3177 | for (i = 1; i < 100; i++)
3178 | for (j = 1; j < 100; j++)
3180 | t = T[j+1][i-1]; // A
3181 | T[j][i] = t + 2; // B
3189 if (DDR_NB_LOOPS (ddr
) > 1)
3191 add_outer_distances (ddr
, save_v
, index_carry
);
3192 add_outer_distances (ddr
, dist_v
, index_carry
);
3197 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3198 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3200 if (DDR_NB_LOOPS (ddr
) > 1)
3202 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3204 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3205 DDR_A (ddr
), loop_nest
))
3207 compute_subscript_distance (ddr
);
3208 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3209 opposite_v
, &init_b
,
3213 save_dist_v (ddr
, save_v
);
3214 add_outer_distances (ddr
, dist_v
, index_carry
);
3215 add_outer_distances (ddr
, opposite_v
, index_carry
);
3218 save_dist_v (ddr
, save_v
);
3223 /* There is a distance of 1 on all the outer loops: Example:
3224 there is a dependence of distance 1 on loop_1 for the array A.
3230 add_outer_distances (ddr
, dist_v
,
3231 lambda_vector_first_nz (dist_v
,
3232 DDR_NB_LOOPS (ddr
), 0));
3235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3239 fprintf (dump_file
, "(build_classic_dist_vector\n");
3240 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3242 fprintf (dump_file
, " dist_vector = (");
3243 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3244 DDR_NB_LOOPS (ddr
));
3245 fprintf (dump_file
, " )\n");
3247 fprintf (dump_file
, ")\n");
3253 /* Return the direction for a given distance.
3254 FIXME: Computing dir this way is suboptimal, since dir can catch
3255 cases that dist is unable to represent. */
3257 static inline enum data_dependence_direction
3258 dir_from_dist (int dist
)
3261 return dir_positive
;
3263 return dir_negative
;
3268 /* Compute the classic per loop direction vector. DDR is the data
3269 dependence relation to build a vector from. */
3272 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3275 lambda_vector dist_v
;
3277 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3279 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3281 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3282 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3284 save_dir_v (ddr
, dir_v
);
3288 /* Helper function. Returns true when there is a dependence between
3289 data references DRA and DRB. */
3292 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3293 struct data_reference
*dra
,
3294 struct data_reference
*drb
,
3295 struct loop
*loop_nest
)
3298 tree last_conflicts
;
3299 struct subscript
*subscript
;
3301 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3304 conflict_function
*overlaps_a
, *overlaps_b
;
3306 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3307 DR_ACCESS_FN (drb
, i
),
3308 &overlaps_a
, &overlaps_b
,
3309 &last_conflicts
, loop_nest
);
3311 if (CF_NOT_KNOWN_P (overlaps_a
)
3312 || CF_NOT_KNOWN_P (overlaps_b
))
3314 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3315 dependence_stats
.num_dependence_undetermined
++;
3316 free_conflict_function (overlaps_a
);
3317 free_conflict_function (overlaps_b
);
3321 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3322 || CF_NO_DEPENDENCE_P (overlaps_b
))
3324 finalize_ddr_dependent (ddr
, chrec_known
);
3325 dependence_stats
.num_dependence_independent
++;
3326 free_conflict_function (overlaps_a
);
3327 free_conflict_function (overlaps_b
);
3333 if (SUB_CONFLICTS_IN_A (subscript
))
3334 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3335 if (SUB_CONFLICTS_IN_B (subscript
))
3336 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3338 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3339 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3340 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3347 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3350 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3351 struct loop
*loop_nest
)
3354 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3355 fprintf (dump_file
, "(subscript_dependence_tester \n");
3357 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3358 dependence_stats
.num_dependence_dependent
++;
3360 compute_subscript_distance (ddr
);
3361 if (build_classic_dist_vector (ddr
, loop_nest
))
3362 build_classic_dir_vector (ddr
);
3364 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3365 fprintf (dump_file
, ")\n");
3368 /* Returns true when all the access functions of A are affine or
3369 constant with respect to LOOP_NEST. */
3372 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3373 const struct loop
*loop_nest
)
3376 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3379 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
3380 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3381 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3387 /* Initializes an equation for an OMEGA problem using the information
3388 contained in the ACCESS_FUN. Returns true when the operation
3391 PB is the omega constraint system.
3392 EQ is the number of the equation to be initialized.
3393 OFFSET is used for shifting the variables names in the constraints:
3394 a constrain is composed of 2 * the number of variables surrounding
3395 dependence accesses. OFFSET is set either to 0 for the first n variables,
3396 then it is set to n.
3397 ACCESS_FUN is expected to be an affine chrec. */
3400 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3401 unsigned int offset
, tree access_fun
,
3402 struct data_dependence_relation
*ddr
)
3404 switch (TREE_CODE (access_fun
))
3406 case POLYNOMIAL_CHREC
:
3408 tree left
= CHREC_LEFT (access_fun
);
3409 tree right
= CHREC_RIGHT (access_fun
);
3410 int var
= CHREC_VARIABLE (access_fun
);
3413 if (TREE_CODE (right
) != INTEGER_CST
)
3416 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3417 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3419 /* Compute the innermost loop index. */
3420 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3423 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3424 += int_cst_value (right
);
3426 switch (TREE_CODE (left
))
3428 case POLYNOMIAL_CHREC
:
3429 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3432 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3441 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3449 /* As explained in the comments preceding init_omega_for_ddr, we have
3450 to set up a system for each loop level, setting outer loops
3451 variation to zero, and current loop variation to positive or zero.
3452 Save each lexico positive distance vector. */
3455 omega_extract_distance_vectors (omega_pb pb
,
3456 struct data_dependence_relation
*ddr
)
3460 struct loop
*loopi
, *loopj
;
3461 enum omega_result res
;
3463 /* Set a new problem for each loop in the nest. The basis is the
3464 problem that we have initialized until now. On top of this we
3465 add new constraints. */
3466 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3467 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3470 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3471 DDR_NB_LOOPS (ddr
));
3473 omega_copy_problem (copy
, pb
);
3475 /* For all the outer loops "loop_j", add "dj = 0". */
3477 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3479 eq
= omega_add_zero_eq (copy
, omega_black
);
3480 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3483 /* For "loop_i", add "0 <= di". */
3484 geq
= omega_add_zero_geq (copy
, omega_black
);
3485 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3487 /* Reduce the constraint system, and test that the current
3488 problem is feasible. */
3489 res
= omega_simplify_problem (copy
);
3490 if (res
== omega_false
3491 || res
== omega_unknown
3492 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3495 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3496 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3498 dist
= copy
->subs
[eq
].coef
[0];
3504 /* Reinitialize problem... */
3505 omega_copy_problem (copy
, pb
);
3507 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3509 eq
= omega_add_zero_eq (copy
, omega_black
);
3510 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3513 /* ..., but this time "di = 1". */
3514 eq
= omega_add_zero_eq (copy
, omega_black
);
3515 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3516 copy
->eqs
[eq
].coef
[0] = -1;
3518 res
= omega_simplify_problem (copy
);
3519 if (res
== omega_false
3520 || res
== omega_unknown
3521 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3524 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3525 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3527 dist
= copy
->subs
[eq
].coef
[0];
3533 /* Save the lexicographically positive distance vector. */
3536 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3537 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3541 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3542 if (copy
->subs
[eq
].key
> 0)
3544 dist
= copy
->subs
[eq
].coef
[0];
3545 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3548 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3549 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3551 save_dist_v (ddr
, dist_v
);
3552 save_dir_v (ddr
, dir_v
);
3556 omega_free_problem (copy
);
3560 /* This is called for each subscript of a tuple of data references:
3561 insert an equality for representing the conflicts. */
3564 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3565 struct data_dependence_relation
*ddr
,
3566 omega_pb pb
, bool *maybe_dependent
)
3569 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3570 TREE_TYPE (access_fun_b
));
3571 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3572 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3573 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3575 /* When the fun_a - fun_b is not constant, the dependence is not
3576 captured by the classic distance vector representation. */
3577 if (TREE_CODE (difference
) != INTEGER_CST
)
3581 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3583 /* There is no dependence. */
3584 *maybe_dependent
= false;
3588 fun_b
= chrec_fold_multiply (type
, fun_b
, integer_minus_one_node
);
3590 eq
= omega_add_zero_eq (pb
, omega_black
);
3591 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3592 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3593 /* There is probably a dependence, but the system of
3594 constraints cannot be built: answer "don't know". */
3598 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3599 && !int_divides_p (lambda_vector_gcd
3600 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3601 2 * DDR_NB_LOOPS (ddr
)),
3602 pb
->eqs
[eq
].coef
[0]))
3604 /* There is no dependence. */
3605 *maybe_dependent
= false;
3612 /* Helper function, same as init_omega_for_ddr but specialized for
3613 data references A and B. */
3616 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3617 struct data_dependence_relation
*ddr
,
3618 omega_pb pb
, bool *maybe_dependent
)
3623 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3625 /* Insert an equality per subscript. */
3626 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3628 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3629 ddr
, pb
, maybe_dependent
))
3631 else if (*maybe_dependent
== false)
3633 /* There is no dependence. */
3634 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3639 /* Insert inequalities: constraints corresponding to the iteration
3640 domain, i.e. the loops surrounding the references "loop_x" and
3641 the distance variables "dx". The layout of the OMEGA
3642 representation is as follows:
3643 - coef[0] is the constant
3644 - coef[1..nb_loops] are the protected variables that will not be
3645 removed by the solver: the "dx"
3646 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3648 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3649 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3651 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3654 ineq
= omega_add_zero_geq (pb
, omega_black
);
3655 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3657 /* 0 <= loop_x + dx */
3658 ineq
= omega_add_zero_geq (pb
, omega_black
);
3659 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3660 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3664 /* loop_x <= nb_iters */
3665 ineq
= omega_add_zero_geq (pb
, omega_black
);
3666 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3667 pb
->geqs
[ineq
].coef
[0] = nbi
;
3669 /* loop_x + dx <= nb_iters */
3670 ineq
= omega_add_zero_geq (pb
, omega_black
);
3671 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3672 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3673 pb
->geqs
[ineq
].coef
[0] = nbi
;
3675 /* A step "dx" bigger than nb_iters is not feasible, so
3676 add "0 <= nb_iters + dx", */
3677 ineq
= omega_add_zero_geq (pb
, omega_black
);
3678 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3679 pb
->geqs
[ineq
].coef
[0] = nbi
;
3680 /* and "dx <= nb_iters". */
3681 ineq
= omega_add_zero_geq (pb
, omega_black
);
3682 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3683 pb
->geqs
[ineq
].coef
[0] = nbi
;
3687 omega_extract_distance_vectors (pb
, ddr
);
3692 /* Sets up the Omega dependence problem for the data dependence
3693 relation DDR. Returns false when the constraint system cannot be
3694 built, ie. when the test answers "don't know". Returns true
3695 otherwise, and when independence has been proved (using one of the
3696 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3697 set MAYBE_DEPENDENT to true.
3699 Example: for setting up the dependence system corresponding to the
3700 conflicting accesses
3705 | ... A[2*j, 2*(i + j)]
3709 the following constraints come from the iteration domain:
3716 where di, dj are the distance variables. The constraints
3717 representing the conflicting elements are:
3720 i + 1 = 2 * (i + di + j + dj)
3722 For asking that the resulting distance vector (di, dj) be
3723 lexicographically positive, we insert the constraint "di >= 0". If
3724 "di = 0" in the solution, we fix that component to zero, and we
3725 look at the inner loops: we set a new problem where all the outer
3726 loop distances are zero, and fix this inner component to be
3727 positive. When one of the components is positive, we save that
3728 distance, and set a new problem where the distance on this loop is
3729 zero, searching for other distances in the inner loops. Here is
3730 the classic example that illustrates that we have to set for each
3731 inner loop a new problem:
3739 we have to save two distances (1, 0) and (0, 1).
3741 Given two array references, refA and refB, we have to set the
3742 dependence problem twice, refA vs. refB and refB vs. refA, and we
3743 cannot do a single test, as refB might occur before refA in the
3744 inner loops, and the contrary when considering outer loops: ex.
3749 | T[{1,+,1}_2][{1,+,1}_1] // refA
3750 | T[{2,+,1}_2][{0,+,1}_1] // refB
3755 refB touches the elements in T before refA, and thus for the same
3756 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3757 but for successive loop_0 iterations, we have (1, -1, 1)
3759 The Omega solver expects the distance variables ("di" in the
3760 previous example) to come first in the constraint system (as
3761 variables to be protected, or "safe" variables), the constraint
3762 system is built using the following layout:
3764 "cst | distance vars | index vars".
3768 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3769 bool *maybe_dependent
)
3774 *maybe_dependent
= true;
3776 if (same_access_functions (ddr
))
3779 lambda_vector dir_v
;
3781 /* Save the 0 vector. */
3782 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3783 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3784 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3785 dir_v
[j
] = dir_equal
;
3786 save_dir_v (ddr
, dir_v
);
3788 /* Save the dependences carried by outer loops. */
3789 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3790 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3792 omega_free_problem (pb
);
3796 /* Omega expects the protected variables (those that have to be kept
3797 after elimination) to appear first in the constraint system.
3798 These variables are the distance variables. In the following
3799 initialization we declare NB_LOOPS safe variables, and the total
3800 number of variables for the constraint system is 2*NB_LOOPS. */
3801 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3802 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3804 omega_free_problem (pb
);
3806 /* Stop computation if not decidable, or no dependence. */
3807 if (res
== false || *maybe_dependent
== false)
3810 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3811 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3813 omega_free_problem (pb
);
3818 /* Return true when DDR contains the same information as that stored
3819 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3822 ddr_consistent_p (FILE *file
,
3823 struct data_dependence_relation
*ddr
,
3824 VEC (lambda_vector
, heap
) *dist_vects
,
3825 VEC (lambda_vector
, heap
) *dir_vects
)
3829 /* If dump_file is set, output there. */
3830 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3833 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3835 lambda_vector b_dist_v
;
3836 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3837 VEC_length (lambda_vector
, dist_vects
),
3838 DDR_NUM_DIST_VECTS (ddr
));
3840 fprintf (file
, "Banerjee dist vectors:\n");
3841 for (i
= 0; VEC_iterate (lambda_vector
, dist_vects
, i
, b_dist_v
); i
++)
3842 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3844 fprintf (file
, "Omega dist vectors:\n");
3845 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3846 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3848 fprintf (file
, "data dependence relation:\n");
3849 dump_data_dependence_relation (file
, ddr
);
3851 fprintf (file
, ")\n");
3855 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3857 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3858 VEC_length (lambda_vector
, dir_vects
),
3859 DDR_NUM_DIR_VECTS (ddr
));
3863 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3865 lambda_vector a_dist_v
;
3866 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3868 /* Distance vectors are not ordered in the same way in the DDR
3869 and in the DIST_VECTS: search for a matching vector. */
3870 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, a_dist_v
); j
++)
3871 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3874 if (j
== VEC_length (lambda_vector
, dist_vects
))
3876 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3877 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3878 fprintf (file
, "not found in Omega dist vectors:\n");
3879 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3880 fprintf (file
, "data dependence relation:\n");
3881 dump_data_dependence_relation (file
, ddr
);
3882 fprintf (file
, ")\n");
3886 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3888 lambda_vector a_dir_v
;
3889 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3891 /* Direction vectors are not ordered in the same way in the DDR
3892 and in the DIR_VECTS: search for a matching vector. */
3893 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, a_dir_v
); j
++)
3894 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3897 if (j
== VEC_length (lambda_vector
, dist_vects
))
3899 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3900 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3901 fprintf (file
, "not found in Omega dir vectors:\n");
3902 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3903 fprintf (file
, "data dependence relation:\n");
3904 dump_data_dependence_relation (file
, ddr
);
3905 fprintf (file
, ")\n");
3912 /* This computes the affine dependence relation between A and B with
3913 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3914 independence between two accesses, while CHREC_DONT_KNOW is used
3915 for representing the unknown relation.
3917 Note that it is possible to stop the computation of the dependence
3918 relation the first time we detect a CHREC_KNOWN element for a given
3922 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3923 struct loop
*loop_nest
)
3925 struct data_reference
*dra
= DDR_A (ddr
);
3926 struct data_reference
*drb
= DDR_B (ddr
);
3928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3930 fprintf (dump_file
, "(compute_affine_dependence\n");
3931 fprintf (dump_file
, " (stmt_a = \n");
3932 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, 0);
3933 fprintf (dump_file
, ")\n (stmt_b = \n");
3934 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, 0);
3935 fprintf (dump_file
, ")\n");
3938 /* Analyze only when the dependence relation is not yet known. */
3939 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
3940 && !DDR_SELF_REFERENCE (ddr
))
3942 dependence_stats
.num_dependence_tests
++;
3944 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3945 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3947 if (flag_check_data_deps
)
3949 /* Compute the dependences using the first algorithm. */
3950 subscript_dependence_tester (ddr
, loop_nest
);
3952 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3954 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3955 dump_data_dependence_relation (dump_file
, ddr
);
3958 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3960 bool maybe_dependent
;
3961 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3963 /* Save the result of the first DD analyzer. */
3964 dist_vects
= DDR_DIST_VECTS (ddr
);
3965 dir_vects
= DDR_DIR_VECTS (ddr
);
3967 /* Reset the information. */
3968 DDR_DIST_VECTS (ddr
) = NULL
;
3969 DDR_DIR_VECTS (ddr
) = NULL
;
3971 /* Compute the same information using Omega. */
3972 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3973 goto csys_dont_know
;
3975 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3977 fprintf (dump_file
, "Omega Analyzer\n");
3978 dump_data_dependence_relation (dump_file
, ddr
);
3981 /* Check that we get the same information. */
3982 if (maybe_dependent
)
3983 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3988 subscript_dependence_tester (ddr
, loop_nest
);
3991 /* As a last case, if the dependence cannot be determined, or if
3992 the dependence is considered too difficult to determine, answer
3997 dependence_stats
.num_dependence_undetermined
++;
3999 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4001 fprintf (dump_file
, "Data ref a:\n");
4002 dump_data_reference (dump_file
, dra
);
4003 fprintf (dump_file
, "Data ref b:\n");
4004 dump_data_reference (dump_file
, drb
);
4005 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
4007 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4012 fprintf (dump_file
, ")\n");
4015 /* This computes the dependence relation for the same data
4016 reference into DDR. */
4019 compute_self_dependence (struct data_dependence_relation
*ddr
)
4022 struct subscript
*subscript
;
4024 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
4027 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
4030 if (SUB_CONFLICTS_IN_A (subscript
))
4031 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
4032 if (SUB_CONFLICTS_IN_B (subscript
))
4033 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
4035 /* The accessed index overlaps for each iteration. */
4036 SUB_CONFLICTS_IN_A (subscript
)
4037 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
4038 SUB_CONFLICTS_IN_B (subscript
)
4039 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
4040 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
4043 /* The distance vector is the zero vector. */
4044 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4045 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4048 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4049 the data references in DATAREFS, in the LOOP_NEST. When
4050 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4054 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
4055 VEC (ddr_p
, heap
) **dependence_relations
,
4056 VEC (loop_p
, heap
) *loop_nest
,
4057 bool compute_self_and_rr
)
4059 struct data_dependence_relation
*ddr
;
4060 struct data_reference
*a
, *b
;
4063 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4064 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
4065 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
4067 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4068 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4070 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
4073 if (compute_self_and_rr
)
4074 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4076 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4077 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4078 compute_self_dependence (ddr
);
4082 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4083 true if STMT clobbers memory, false otherwise. */
4086 get_references_in_stmt (gimple stmt
, VEC (data_ref_loc
, heap
) **references
)
4088 bool clobbers_memory
= false;
4091 enum gimple_code stmt_code
= gimple_code (stmt
);
4095 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4096 Calls have side-effects, except those to const or pure
4098 if ((stmt_code
== GIMPLE_CALL
4099 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4100 || (stmt_code
== GIMPLE_ASM
4101 && gimple_asm_volatile_p (stmt
)))
4102 clobbers_memory
= true;
4104 if (!gimple_vuse (stmt
))
4105 return clobbers_memory
;
4107 if (stmt_code
== GIMPLE_ASSIGN
)
4110 op0
= gimple_assign_lhs_ptr (stmt
);
4111 op1
= gimple_assign_rhs1_ptr (stmt
);
4114 || (REFERENCE_CLASS_P (*op1
)
4115 && (base
= get_base_address (*op1
))
4116 && TREE_CODE (base
) != SSA_NAME
))
4118 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4120 ref
->is_read
= true;
4124 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4126 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4128 ref
->is_read
= false;
4131 else if (stmt_code
== GIMPLE_CALL
)
4133 unsigned i
, n
= gimple_call_num_args (stmt
);
4135 for (i
= 0; i
< n
; i
++)
4137 op0
= gimple_call_arg_ptr (stmt
, i
);
4140 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4142 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4144 ref
->is_read
= true;
4149 return clobbers_memory
;
4152 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4153 reference, returns false, otherwise returns true. NEST is the outermost
4154 loop of the loop nest in which the references should be analyzed. */
4157 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4158 VEC (data_reference_p
, heap
) **datarefs
)
4161 VEC (data_ref_loc
, heap
) *references
;
4164 data_reference_p dr
;
4166 if (get_references_in_stmt (stmt
, &references
))
4168 VEC_free (data_ref_loc
, heap
, references
);
4172 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
4174 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4175 gcc_assert (dr
!= NULL
);
4177 /* FIXME -- data dependence analysis does not work correctly for objects
4178 with invariant addresses in loop nests. Let us fail here until the
4179 problem is fixed. */
4180 if (dr_address_invariant_p (dr
) && nest
)
4183 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4184 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
4189 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4191 VEC_free (data_ref_loc
, heap
, references
);
4195 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4196 reference, returns false, otherwise returns true. NEST is the outermost
4197 loop of the loop nest in which the references should be analyzed. */
4200 graphite_find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4201 VEC (data_reference_p
, heap
) **datarefs
)
4204 VEC (data_ref_loc
, heap
) *references
;
4207 data_reference_p dr
;
4209 if (get_references_in_stmt (stmt
, &references
))
4211 VEC_free (data_ref_loc
, heap
, references
);
4215 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
4217 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4218 gcc_assert (dr
!= NULL
);
4219 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4222 VEC_free (data_ref_loc
, heap
, references
);
4226 /* Search the data references in LOOP, and record the information into
4227 DATAREFS. Returns chrec_dont_know when failing to analyze a
4228 difficult case, returns NULL_TREE otherwise. */
4231 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4232 VEC (data_reference_p
, heap
) **datarefs
)
4234 gimple_stmt_iterator bsi
;
4236 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4238 gimple stmt
= gsi_stmt (bsi
);
4240 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4242 struct data_reference
*res
;
4243 res
= XCNEW (struct data_reference
);
4244 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4246 return chrec_dont_know
;
4253 /* Search the data references in LOOP, and record the information into
4254 DATAREFS. Returns chrec_dont_know when failing to analyze a
4255 difficult case, returns NULL_TREE otherwise.
4257 TODO: This function should be made smarter so that it can handle address
4258 arithmetic as if they were array accesses, etc. */
4261 find_data_references_in_loop (struct loop
*loop
,
4262 VEC (data_reference_p
, heap
) **datarefs
)
4264 basic_block bb
, *bbs
;
4267 bbs
= get_loop_body_in_dom_order (loop
);
4269 for (i
= 0; i
< loop
->num_nodes
; i
++)
4273 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4276 return chrec_dont_know
;
4284 /* Recursive helper function. */
4287 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4289 /* Inner loops of the nest should not contain siblings. Example:
4290 when there are two consecutive loops,
4301 the dependence relation cannot be captured by the distance
4306 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4308 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4312 /* Return false when the LOOP is not well nested. Otherwise return
4313 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4314 contain the loops from the outermost to the innermost, as they will
4315 appear in the classic distance vector. */
4318 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4320 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4322 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4326 /* Returns true when the data dependences have been computed, false otherwise.
4327 Given a loop nest LOOP, the following vectors are returned:
4328 DATAREFS is initialized to all the array elements contained in this loop,
4329 DEPENDENCE_RELATIONS contains the relations between the data references.
4330 Compute read-read and self relations if
4331 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4334 compute_data_dependences_for_loop (struct loop
*loop
,
4335 bool compute_self_and_read_read_dependences
,
4336 VEC (data_reference_p
, heap
) **datarefs
,
4337 VEC (ddr_p
, heap
) **dependence_relations
)
4340 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4342 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4344 /* If the loop nest is not well formed, or one of the data references
4345 is not computable, give up without spending time to compute other
4348 || !find_loop_nest (loop
, &vloops
)
4349 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4351 struct data_dependence_relation
*ddr
;
4353 /* Insert a single relation into dependence_relations:
4355 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4356 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4360 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4361 compute_self_and_read_read_dependences
);
4363 if (dump_file
&& (dump_flags
& TDF_STATS
))
4365 fprintf (dump_file
, "Dependence tester statistics:\n");
4367 fprintf (dump_file
, "Number of dependence tests: %d\n",
4368 dependence_stats
.num_dependence_tests
);
4369 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4370 dependence_stats
.num_dependence_dependent
);
4371 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4372 dependence_stats
.num_dependence_independent
);
4373 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4374 dependence_stats
.num_dependence_undetermined
);
4376 fprintf (dump_file
, "Number of subscript tests: %d\n",
4377 dependence_stats
.num_subscript_tests
);
4378 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4379 dependence_stats
.num_subscript_undetermined
);
4380 fprintf (dump_file
, "Number of same subscript function: %d\n",
4381 dependence_stats
.num_same_subscript_function
);
4383 fprintf (dump_file
, "Number of ziv tests: %d\n",
4384 dependence_stats
.num_ziv
);
4385 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4386 dependence_stats
.num_ziv_dependent
);
4387 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4388 dependence_stats
.num_ziv_independent
);
4389 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4390 dependence_stats
.num_ziv_unimplemented
);
4392 fprintf (dump_file
, "Number of siv tests: %d\n",
4393 dependence_stats
.num_siv
);
4394 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4395 dependence_stats
.num_siv_dependent
);
4396 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4397 dependence_stats
.num_siv_independent
);
4398 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4399 dependence_stats
.num_siv_unimplemented
);
4401 fprintf (dump_file
, "Number of miv tests: %d\n",
4402 dependence_stats
.num_miv
);
4403 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4404 dependence_stats
.num_miv_dependent
);
4405 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4406 dependence_stats
.num_miv_independent
);
4407 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4408 dependence_stats
.num_miv_unimplemented
);
4414 /* Returns true when the data dependences for the basic block BB have been
4415 computed, false otherwise.
4416 DATAREFS is initialized to all the array elements contained in this basic
4417 block, DEPENDENCE_RELATIONS contains the relations between the data
4418 references. Compute read-read and self relations if
4419 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4421 compute_data_dependences_for_bb (basic_block bb
,
4422 bool compute_self_and_read_read_dependences
,
4423 VEC (data_reference_p
, heap
) **datarefs
,
4424 VEC (ddr_p
, heap
) **dependence_relations
)
4426 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4429 compute_all_dependences (*datarefs
, dependence_relations
, NULL
,
4430 compute_self_and_read_read_dependences
);
4434 /* Entry point (for testing only). Analyze all the data references
4435 and the dependence relations in LOOP.
4437 The data references are computed first.
4439 A relation on these nodes is represented by a complete graph. Some
4440 of the relations could be of no interest, thus the relations can be
4443 In the following function we compute all the relations. This is
4444 just a first implementation that is here for:
4445 - for showing how to ask for the dependence relations,
4446 - for the debugging the whole dependence graph,
4447 - for the dejagnu testcases and maintenance.
4449 It is possible to ask only for a part of the graph, avoiding to
4450 compute the whole dependence graph. The computed dependences are
4451 stored in a knowledge base (KB) such that later queries don't
4452 recompute the same information. The implementation of this KB is
4453 transparent to the optimizer, and thus the KB can be changed with a
4454 more efficient implementation, or the KB could be disabled. */
4456 analyze_all_data_dependences (struct loop
*loop
)
4459 int nb_data_refs
= 10;
4460 VEC (data_reference_p
, heap
) *datarefs
=
4461 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4462 VEC (ddr_p
, heap
) *dependence_relations
=
4463 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4465 /* Compute DDs on the whole function. */
4466 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4467 &dependence_relations
);
4471 dump_data_dependence_relations (dump_file
, dependence_relations
);
4472 fprintf (dump_file
, "\n\n");
4474 if (dump_flags
& TDF_DETAILS
)
4475 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4477 if (dump_flags
& TDF_STATS
)
4479 unsigned nb_top_relations
= 0;
4480 unsigned nb_bot_relations
= 0;
4481 unsigned nb_chrec_relations
= 0;
4482 struct data_dependence_relation
*ddr
;
4484 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4486 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4489 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4493 nb_chrec_relations
++;
4496 gather_stats_on_scev_database ();
4500 free_dependence_relations (dependence_relations
);
4501 free_data_refs (datarefs
);
4504 /* Computes all the data dependences and check that the results of
4505 several analyzers are the same. */
4508 tree_check_data_deps (void)
4511 struct loop
*loop_nest
;
4513 FOR_EACH_LOOP (li
, loop_nest
, 0)
4514 analyze_all_data_dependences (loop_nest
);
4517 /* Free the memory used by a data dependence relation DDR. */
4520 free_dependence_relation (struct data_dependence_relation
*ddr
)
4525 if (DDR_SUBSCRIPTS (ddr
))
4526 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4527 if (DDR_DIST_VECTS (ddr
))
4528 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4529 if (DDR_DIR_VECTS (ddr
))
4530 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4535 /* Free the memory used by the data dependence relations from
4536 DEPENDENCE_RELATIONS. */
4539 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4542 struct data_dependence_relation
*ddr
;
4543 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4545 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4549 if (loop_nest
== NULL
)
4550 loop_nest
= DDR_LOOP_NEST (ddr
);
4552 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4553 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4554 free_dependence_relation (ddr
);
4558 VEC_free (loop_p
, heap
, loop_nest
);
4559 VEC_free (ddr_p
, heap
, dependence_relations
);
4562 /* Free the memory used by the data references from DATAREFS. */
4565 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4568 struct data_reference
*dr
;
4570 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4572 VEC_free (data_reference_p
, heap
, datarefs
);
4577 /* Dump vertex I in RDG to FILE. */
4580 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4582 struct vertex
*v
= &(rdg
->vertices
[i
]);
4583 struct graph_edge
*e
;
4585 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4586 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4587 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4590 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4591 fprintf (file
, " %d", e
->src
);
4593 fprintf (file
, ") (out:");
4596 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4597 fprintf (file
, " %d", e
->dest
);
4599 fprintf (file
, ") \n");
4600 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4601 fprintf (file
, ")\n");
4604 /* Call dump_rdg_vertex on stderr. */
4607 debug_rdg_vertex (struct graph
*rdg
, int i
)
4609 dump_rdg_vertex (stderr
, rdg
, i
);
4612 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4613 dumped vertices to that bitmap. */
4615 void dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4619 fprintf (file
, "(%d\n", c
);
4621 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4622 if (rdg
->vertices
[i
].component
== c
)
4625 bitmap_set_bit (dumped
, i
);
4627 dump_rdg_vertex (file
, rdg
, i
);
4630 fprintf (file
, ")\n");
4633 /* Call dump_rdg_vertex on stderr. */
4636 debug_rdg_component (struct graph
*rdg
, int c
)
4638 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4641 /* Dump the reduced dependence graph RDG to FILE. */
4644 dump_rdg (FILE *file
, struct graph
*rdg
)
4647 bitmap dumped
= BITMAP_ALLOC (NULL
);
4649 fprintf (file
, "(rdg\n");
4651 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4652 if (!bitmap_bit_p (dumped
, i
))
4653 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4655 fprintf (file
, ")\n");
4656 BITMAP_FREE (dumped
);
4659 /* Call dump_rdg on stderr. */
4662 debug_rdg (struct graph
*rdg
)
4664 dump_rdg (stderr
, rdg
);
4667 /* This structure is used for recording the mapping statement index in
4670 struct GTY(()) rdg_vertex_info
4676 /* Returns the index of STMT in RDG. */
4679 rdg_vertex_for_stmt (struct graph
*rdg
, gimple stmt
)
4681 struct rdg_vertex_info rvi
, *slot
;
4684 slot
= (struct rdg_vertex_info
*) htab_find (rdg
->indices
, &rvi
);
4692 /* Creates an edge in RDG for each distance vector from DDR. The
4693 order that we keep track of in the RDG is the order in which
4694 statements have to be executed. */
4697 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4699 struct graph_edge
*e
;
4701 data_reference_p dra
= DDR_A (ddr
);
4702 data_reference_p drb
= DDR_B (ddr
);
4703 unsigned level
= ddr_dependence_level (ddr
);
4705 /* For non scalar dependences, when the dependence is REVERSED,
4706 statement B has to be executed before statement A. */
4708 && !DDR_REVERSED_P (ddr
))
4710 data_reference_p tmp
= dra
;
4715 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4716 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4718 if (va
< 0 || vb
< 0)
4721 e
= add_edge (rdg
, va
, vb
);
4722 e
->data
= XNEW (struct rdg_edge
);
4724 RDGE_LEVEL (e
) = level
;
4725 RDGE_RELATION (e
) = ddr
;
4727 /* Determines the type of the data dependence. */
4728 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4729 RDGE_TYPE (e
) = input_dd
;
4730 else if (!DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4731 RDGE_TYPE (e
) = output_dd
;
4732 else if (!DR_IS_READ (dra
) && DR_IS_READ (drb
))
4733 RDGE_TYPE (e
) = flow_dd
;
4734 else if (DR_IS_READ (dra
) && !DR_IS_READ (drb
))
4735 RDGE_TYPE (e
) = anti_dd
;
4738 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4739 the index of DEF in RDG. */
4742 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4744 use_operand_p imm_use_p
;
4745 imm_use_iterator iterator
;
4747 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4749 struct graph_edge
*e
;
4750 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4755 e
= add_edge (rdg
, idef
, use
);
4756 e
->data
= XNEW (struct rdg_edge
);
4757 RDGE_TYPE (e
) = flow_dd
;
4758 RDGE_RELATION (e
) = NULL
;
4762 /* Creates the edges of the reduced dependence graph RDG. */
4765 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4768 struct data_dependence_relation
*ddr
;
4769 def_operand_p def_p
;
4772 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
4773 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4774 create_rdg_edge_for_ddr (rdg
, ddr
);
4776 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4777 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4779 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4782 /* Build the vertices of the reduced dependence graph RDG. */
4785 create_rdg_vertices (struct graph
*rdg
, VEC (gimple
, heap
) *stmts
)
4790 for (i
= 0; VEC_iterate (gimple
, stmts
, i
, stmt
); i
++)
4792 VEC (data_ref_loc
, heap
) *references
;
4794 struct vertex
*v
= &(rdg
->vertices
[i
]);
4795 struct rdg_vertex_info
*rvi
= XNEW (struct rdg_vertex_info
);
4796 struct rdg_vertex_info
**slot
;
4800 slot
= (struct rdg_vertex_info
**) htab_find_slot (rdg
->indices
, rvi
, INSERT
);
4807 v
->data
= XNEW (struct rdg_vertex
);
4808 RDG_STMT (rdg
, i
) = stmt
;
4810 RDG_MEM_WRITE_STMT (rdg
, i
) = false;
4811 RDG_MEM_READS_STMT (rdg
, i
) = false;
4812 if (gimple_code (stmt
) == GIMPLE_PHI
)
4815 get_references_in_stmt (stmt
, &references
);
4816 for (j
= 0; VEC_iterate (data_ref_loc
, references
, j
, ref
); j
++)
4818 RDG_MEM_WRITE_STMT (rdg
, i
) = true;
4820 RDG_MEM_READS_STMT (rdg
, i
) = true;
4822 VEC_free (data_ref_loc
, heap
, references
);
4826 /* Initialize STMTS with all the statements of LOOP. When
4827 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4828 which we discover statements is important as
4829 generate_loops_for_partition is using the same traversal for
4830 identifying statements. */
4833 stmts_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4836 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4838 for (i
= 0; i
< loop
->num_nodes
; i
++)
4840 basic_block bb
= bbs
[i
];
4841 gimple_stmt_iterator bsi
;
4844 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4845 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4847 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4849 stmt
= gsi_stmt (bsi
);
4850 if (gimple_code (stmt
) != GIMPLE_LABEL
)
4851 VEC_safe_push (gimple
, heap
, *stmts
, stmt
);
4858 /* Returns true when all the dependences are computable. */
4861 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
4866 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4867 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4873 /* Computes a hash function for element ELT. */
4876 hash_stmt_vertex_info (const void *elt
)
4878 const struct rdg_vertex_info
*const rvi
=
4879 (const struct rdg_vertex_info
*) elt
;
4880 gimple stmt
= rvi
->stmt
;
4882 return htab_hash_pointer (stmt
);
4885 /* Compares database elements E1 and E2. */
4888 eq_stmt_vertex_info (const void *e1
, const void *e2
)
4890 const struct rdg_vertex_info
*elt1
= (const struct rdg_vertex_info
*) e1
;
4891 const struct rdg_vertex_info
*elt2
= (const struct rdg_vertex_info
*) e2
;
4893 return elt1
->stmt
== elt2
->stmt
;
4896 /* Free the element E. */
4899 hash_stmt_vertex_del (void *e
)
4904 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4905 statement of the loop nest, and one edge per data dependence or
4906 scalar dependence. */
4909 build_empty_rdg (int n_stmts
)
4911 int nb_data_refs
= 10;
4912 struct graph
*rdg
= new_graph (n_stmts
);
4914 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4915 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4919 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4920 statement of the loop nest, and one edge per data dependence or
4921 scalar dependence. */
4924 build_rdg (struct loop
*loop
)
4926 int nb_data_refs
= 10;
4927 struct graph
*rdg
= NULL
;
4928 VEC (ddr_p
, heap
) *dependence_relations
;
4929 VEC (data_reference_p
, heap
) *datarefs
;
4930 VEC (gimple
, heap
) *stmts
= VEC_alloc (gimple
, heap
, nb_data_refs
);
4932 dependence_relations
= VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
) ;
4933 datarefs
= VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4934 compute_data_dependences_for_loop (loop
,
4937 &dependence_relations
);
4939 if (!known_dependences_p (dependence_relations
))
4941 free_dependence_relations (dependence_relations
);
4942 free_data_refs (datarefs
);
4943 VEC_free (gimple
, heap
, stmts
);
4948 stmts_from_loop (loop
, &stmts
);
4949 rdg
= build_empty_rdg (VEC_length (gimple
, stmts
));
4951 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4952 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4953 create_rdg_vertices (rdg
, stmts
);
4954 create_rdg_edges (rdg
, dependence_relations
);
4956 VEC_free (gimple
, heap
, stmts
);
4960 /* Free the reduced dependence graph RDG. */
4963 free_rdg (struct graph
*rdg
)
4967 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4968 free (rdg
->vertices
[i
].data
);
4970 htab_delete (rdg
->indices
);
4974 /* Initialize STMTS with all the statements of LOOP that contain a
4978 stores_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4981 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4983 for (i
= 0; i
< loop
->num_nodes
; i
++)
4985 basic_block bb
= bbs
[i
];
4986 gimple_stmt_iterator bsi
;
4988 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4989 if (gimple_vdef (gsi_stmt (bsi
)))
4990 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4996 /* For a data reference REF, return the declaration of its base
4997 address or NULL_TREE if the base is not determined. */
5000 ref_base_address (gimple stmt
, data_ref_loc
*ref
)
5002 tree base
= NULL_TREE
;
5004 struct data_reference
*dr
= XCNEW (struct data_reference
);
5006 DR_STMT (dr
) = stmt
;
5007 DR_REF (dr
) = *ref
->pos
;
5008 dr_analyze_innermost (dr
);
5009 base_address
= DR_BASE_ADDRESS (dr
);
5014 switch (TREE_CODE (base_address
))
5017 base
= TREE_OPERAND (base_address
, 0);
5021 base
= base_address
;
5030 /* Determines whether the statement from vertex V of the RDG has a
5031 definition used outside the loop that contains this statement. */
5034 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
5036 gimple stmt
= RDG_STMT (rdg
, v
);
5037 struct loop
*loop
= loop_containing_stmt (stmt
);
5038 use_operand_p imm_use_p
;
5039 imm_use_iterator iterator
;
5041 def_operand_p def_p
;
5046 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
5048 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
5050 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)
5058 /* Determines whether statements S1 and S2 access to similar memory
5059 locations. Two memory accesses are considered similar when they
5060 have the same base address declaration, i.e. when their
5061 ref_base_address is the same. */
5064 have_similar_memory_accesses (gimple s1
, gimple s2
)
5068 VEC (data_ref_loc
, heap
) *refs1
, *refs2
;
5069 data_ref_loc
*ref1
, *ref2
;
5071 get_references_in_stmt (s1
, &refs1
);
5072 get_references_in_stmt (s2
, &refs2
);
5074 for (i
= 0; VEC_iterate (data_ref_loc
, refs1
, i
, ref1
); i
++)
5076 tree base1
= ref_base_address (s1
, ref1
);
5079 for (j
= 0; VEC_iterate (data_ref_loc
, refs2
, j
, ref2
); j
++)
5080 if (base1
== ref_base_address (s2
, ref2
))
5088 VEC_free (data_ref_loc
, heap
, refs1
);
5089 VEC_free (data_ref_loc
, heap
, refs2
);
5093 /* Helper function for the hashtab. */
5096 have_similar_memory_accesses_1 (const void *s1
, const void *s2
)
5098 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple
) s1
),
5099 CONST_CAST_GIMPLE ((const_gimple
) s2
));
5102 /* Helper function for the hashtab. */
5105 ref_base_address_1 (const void *s
)
5107 gimple stmt
= CONST_CAST_GIMPLE ((const_gimple
) s
);
5109 VEC (data_ref_loc
, heap
) *refs
;
5113 get_references_in_stmt (stmt
, &refs
);
5115 for (i
= 0; VEC_iterate (data_ref_loc
, refs
, i
, ref
); i
++)
5118 res
= htab_hash_pointer (ref_base_address (stmt
, ref
));
5122 VEC_free (data_ref_loc
, heap
, refs
);
5126 /* Try to remove duplicated write data references from STMTS. */
5129 remove_similar_memory_refs (VEC (gimple
, heap
) **stmts
)
5133 htab_t seen
= htab_create (VEC_length (gimple
, *stmts
), ref_base_address_1
,
5134 have_similar_memory_accesses_1
, NULL
);
5136 for (i
= 0; VEC_iterate (gimple
, *stmts
, i
, stmt
); )
5140 slot
= htab_find_slot (seen
, stmt
, INSERT
);
5143 VEC_ordered_remove (gimple
, *stmts
, i
);
5146 *slot
= (void *) stmt
;
5154 /* Returns the index of PARAMETER in the parameters vector of the
5155 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5158 access_matrix_get_index_for_parameter (tree parameter
,
5159 struct access_matrix
*access_matrix
)
5162 VEC (tree
,heap
) *lambda_parameters
= AM_PARAMETERS (access_matrix
);
5163 tree lambda_parameter
;
5165 for (i
= 0; VEC_iterate (tree
, lambda_parameters
, i
, lambda_parameter
); i
++)
5166 if (lambda_parameter
== parameter
)
5167 return i
+ AM_NB_INDUCTION_VARS (access_matrix
);