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_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
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_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
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_EACH_VEC_ELT (lambda_vector
, dir_vects
, j
, v
)
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_EACH_VEC_ELT (lambda_vector
, dist_vects
, j
, v
)
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_EACH_VEC_ELT (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
)
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_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
499 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
501 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
)
503 fprintf (file
, "DISTANCE_V (");
504 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
505 fprintf (file
, ")\n");
508 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
)
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_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
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 if (TREE_CODE (base
) == MEM_REF
)
751 if (!integer_zerop (TREE_OPERAND (base
, 1)))
755 double_int moff
= mem_ref_offset (base
);
756 poffset
= double_int_to_tree (sizetype
, moff
);
759 poffset
= size_binop (PLUS_EXPR
, poffset
, TREE_OPERAND (base
, 1));
761 base
= TREE_OPERAND (base
, 0);
764 base
= build_fold_addr_expr (base
);
767 if (!simple_iv (loop
, loop_containing_stmt (stmt
), base
, &base_iv
,
770 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
771 fprintf (dump_file
, "failed: evolution of base is not affine.\n");
778 base_iv
.step
= ssize_int (0);
779 base_iv
.no_overflow
= true;
784 offset_iv
.base
= ssize_int (0);
785 offset_iv
.step
= ssize_int (0);
791 offset_iv
.base
= poffset
;
792 offset_iv
.step
= ssize_int (0);
794 else if (!simple_iv (loop
, loop_containing_stmt (stmt
),
795 poffset
, &offset_iv
, false))
797 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
798 fprintf (dump_file
, "failed: evolution of offset is not"
804 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
805 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
806 init
= size_binop (PLUS_EXPR
, init
, dinit
);
807 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
808 init
= size_binop (PLUS_EXPR
, init
, dinit
);
810 step
= size_binop (PLUS_EXPR
,
811 fold_convert (ssizetype
, base_iv
.step
),
812 fold_convert (ssizetype
, offset_iv
.step
));
814 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
816 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
820 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
823 fprintf (dump_file
, "success.\n");
828 /* Determines the base object and the list of indices of memory reference
829 DR, analyzed in loop nest NEST. */
832 dr_analyze_indices (struct data_reference
*dr
, struct loop
*nest
)
834 gimple stmt
= DR_STMT (dr
);
835 struct loop
*loop
= loop_containing_stmt (stmt
);
836 VEC (tree
, heap
) *access_fns
= NULL
;
837 tree ref
= unshare_expr (DR_REF (dr
)), aref
= ref
, op
;
838 tree base
, off
, access_fn
= NULL_TREE
;
839 basic_block before_loop
= NULL
;
842 before_loop
= block_before_loop (nest
);
844 while (handled_component_p (aref
))
846 if (TREE_CODE (aref
) == ARRAY_REF
)
848 op
= TREE_OPERAND (aref
, 1);
851 access_fn
= analyze_scalar_evolution (loop
, op
);
852 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
853 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
856 TREE_OPERAND (aref
, 1) = build_int_cst (TREE_TYPE (op
), 0);
859 aref
= TREE_OPERAND (aref
, 0);
863 && (INDIRECT_REF_P (aref
)
864 || TREE_CODE (aref
) == MEM_REF
))
866 op
= TREE_OPERAND (aref
, 0);
867 access_fn
= analyze_scalar_evolution (loop
, op
);
868 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
869 base
= initial_condition (access_fn
);
870 split_constant_offset (base
, &base
, &off
);
871 if (TREE_CODE (aref
) == MEM_REF
)
872 off
= size_binop (PLUS_EXPR
, off
,
873 fold_convert (ssizetype
, TREE_OPERAND (aref
, 1)));
874 access_fn
= chrec_replace_initial_condition (access_fn
,
875 fold_convert (TREE_TYPE (base
), off
));
877 TREE_OPERAND (aref
, 0) = base
;
878 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
881 if (TREE_CODE (aref
) == MEM_REF
)
882 TREE_OPERAND (aref
, 1)
883 = build_int_cst (TREE_TYPE (TREE_OPERAND (aref
, 1)), 0);
885 if (TREE_CODE (ref
) == MEM_REF
886 && TREE_CODE (TREE_OPERAND (ref
, 0)) == ADDR_EXPR
887 && integer_zerop (TREE_OPERAND (ref
, 1)))
888 ref
= TREE_OPERAND (TREE_OPERAND (ref
, 0), 0);
890 /* For canonicalization purposes we'd like to strip all outermost
891 zero-offset component-refs.
892 ??? For now simply handle zero-index array-refs. */
893 while (TREE_CODE (ref
) == ARRAY_REF
894 && integer_zerop (TREE_OPERAND (ref
, 1)))
895 ref
= TREE_OPERAND (ref
, 0);
897 DR_BASE_OBJECT (dr
) = ref
;
898 DR_ACCESS_FNS (dr
) = access_fns
;
901 /* Extracts the alias analysis information from the memory reference DR. */
904 dr_analyze_alias (struct data_reference
*dr
)
906 tree ref
= DR_REF (dr
);
907 tree base
= get_base_address (ref
), addr
;
909 if (INDIRECT_REF_P (base
)
910 || TREE_CODE (base
) == MEM_REF
)
912 addr
= TREE_OPERAND (base
, 0);
913 if (TREE_CODE (addr
) == SSA_NAME
)
914 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
918 /* Returns true if the address of DR is invariant. */
921 dr_address_invariant_p (struct data_reference
*dr
)
926 FOR_EACH_VEC_ELT (tree
, DR_ACCESS_FNS (dr
), i
, idx
)
927 if (tree_contains_chrecs (idx
, NULL
))
933 /* Frees data reference DR. */
936 free_data_ref (data_reference_p dr
)
938 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
942 /* Analyzes memory reference MEMREF accessed in STMT. The reference
943 is read if IS_READ is true, write otherwise. Returns the
944 data_reference description of MEMREF. NEST is the outermost loop of the
945 loop nest in that the reference should be analyzed. */
947 struct data_reference
*
948 create_data_ref (struct loop
*nest
, tree memref
, gimple stmt
, bool is_read
)
950 struct data_reference
*dr
;
952 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
954 fprintf (dump_file
, "Creating dr for ");
955 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
956 fprintf (dump_file
, "\n");
959 dr
= XCNEW (struct data_reference
);
961 DR_REF (dr
) = memref
;
962 DR_IS_READ (dr
) = is_read
;
964 dr_analyze_innermost (dr
);
965 dr_analyze_indices (dr
, nest
);
966 dr_analyze_alias (dr
);
968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
970 fprintf (dump_file
, "\tbase_address: ");
971 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
972 fprintf (dump_file
, "\n\toffset from base address: ");
973 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
974 fprintf (dump_file
, "\n\tconstant offset from base address: ");
975 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
976 fprintf (dump_file
, "\n\tstep: ");
977 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
978 fprintf (dump_file
, "\n\taligned to: ");
979 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
980 fprintf (dump_file
, "\n\tbase_object: ");
981 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
982 fprintf (dump_file
, "\n");
988 /* Returns true if FNA == FNB. */
991 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
993 unsigned i
, n
= VEC_length (tree
, fna
);
995 if (n
!= VEC_length (tree
, fnb
))
998 for (i
= 0; i
< n
; i
++)
999 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
1000 VEC_index (tree
, fnb
, i
), 0))
1006 /* If all the functions in CF are the same, returns one of them,
1007 otherwise returns NULL. */
1010 common_affine_function (conflict_function
*cf
)
1015 if (!CF_NONTRIVIAL_P (cf
))
1020 for (i
= 1; i
< cf
->n
; i
++)
1021 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
1027 /* Returns the base of the affine function FN. */
1030 affine_function_base (affine_fn fn
)
1032 return VEC_index (tree
, fn
, 0);
1035 /* Returns true if FN is a constant. */
1038 affine_function_constant_p (affine_fn fn
)
1043 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
1044 if (!integer_zerop (coef
))
1050 /* Returns true if FN is the zero constant function. */
1053 affine_function_zero_p (affine_fn fn
)
1055 return (integer_zerop (affine_function_base (fn
))
1056 && affine_function_constant_p (fn
));
1059 /* Returns a signed integer type with the largest precision from TA
1063 signed_type_for_types (tree ta
, tree tb
)
1065 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
1066 return signed_type_for (ta
);
1068 return signed_type_for (tb
);
1071 /* Applies operation OP on affine functions FNA and FNB, and returns the
1075 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
1081 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
1083 n
= VEC_length (tree
, fna
);
1084 m
= VEC_length (tree
, fnb
);
1088 n
= VEC_length (tree
, fnb
);
1089 m
= VEC_length (tree
, fna
);
1092 ret
= VEC_alloc (tree
, heap
, m
);
1093 for (i
= 0; i
< n
; i
++)
1095 tree type
= signed_type_for_types (TREE_TYPE (VEC_index (tree
, fna
, i
)),
1096 TREE_TYPE (VEC_index (tree
, fnb
, i
)));
1098 VEC_quick_push (tree
, ret
,
1099 fold_build2 (op
, type
,
1100 VEC_index (tree
, fna
, i
),
1101 VEC_index (tree
, fnb
, i
)));
1104 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
1105 VEC_quick_push (tree
, ret
,
1106 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1107 coef
, integer_zero_node
));
1108 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
1109 VEC_quick_push (tree
, ret
,
1110 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1111 integer_zero_node
, coef
));
1116 /* Returns the sum of affine functions FNA and FNB. */
1119 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1121 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1124 /* Returns the difference of affine functions FNA and FNB. */
1127 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1129 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1132 /* Frees affine function FN. */
1135 affine_fn_free (affine_fn fn
)
1137 VEC_free (tree
, heap
, fn
);
1140 /* Determine for each subscript in the data dependence relation DDR
1144 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1146 conflict_function
*cf_a
, *cf_b
;
1147 affine_fn fn_a
, fn_b
, diff
;
1149 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1153 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1155 struct subscript
*subscript
;
1157 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1158 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1159 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1161 fn_a
= common_affine_function (cf_a
);
1162 fn_b
= common_affine_function (cf_b
);
1165 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1168 diff
= affine_fn_minus (fn_a
, fn_b
);
1170 if (affine_function_constant_p (diff
))
1171 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1173 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1175 affine_fn_free (diff
);
1180 /* Returns the conflict function for "unknown". */
1182 static conflict_function
*
1183 conflict_fn_not_known (void)
1185 conflict_function
*fn
= XCNEW (conflict_function
);
1191 /* Returns the conflict function for "independent". */
1193 static conflict_function
*
1194 conflict_fn_no_dependence (void)
1196 conflict_function
*fn
= XCNEW (conflict_function
);
1197 fn
->n
= NO_DEPENDENCE
;
1202 /* Returns true if the address of OBJ is invariant in LOOP. */
1205 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1207 while (handled_component_p (obj
))
1209 if (TREE_CODE (obj
) == ARRAY_REF
)
1211 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1212 need to check the stride and the lower bound of the reference. */
1213 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1215 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1219 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1221 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1225 obj
= TREE_OPERAND (obj
, 0);
1228 if (!INDIRECT_REF_P (obj
)
1229 && TREE_CODE (obj
) != MEM_REF
)
1232 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1236 /* Returns false if we can prove that data references A and B do not alias,
1240 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
)
1242 tree addr_a
= DR_BASE_OBJECT (a
);
1243 tree addr_b
= DR_BASE_OBJECT (b
);
1245 if (DR_IS_WRITE (a
) && DR_IS_WRITE (b
))
1246 return refs_output_dependent_p (addr_a
, addr_b
);
1247 else if (DR_IS_READ (a
) && DR_IS_WRITE (b
))
1248 return refs_anti_dependent_p (addr_a
, addr_b
);
1249 return refs_may_alias_p (addr_a
, addr_b
);
1252 static void compute_self_dependence (struct data_dependence_relation
*);
1254 /* Initialize a data dependence relation between data accesses A and
1255 B. NB_LOOPS is the number of loops surrounding the references: the
1256 size of the classic distance/direction vectors. */
1258 static struct data_dependence_relation
*
1259 initialize_data_dependence_relation (struct data_reference
*a
,
1260 struct data_reference
*b
,
1261 VEC (loop_p
, heap
) *loop_nest
)
1263 struct data_dependence_relation
*res
;
1266 res
= XNEW (struct data_dependence_relation
);
1269 DDR_LOOP_NEST (res
) = NULL
;
1270 DDR_REVERSED_P (res
) = false;
1271 DDR_SUBSCRIPTS (res
) = NULL
;
1272 DDR_DIR_VECTS (res
) = NULL
;
1273 DDR_DIST_VECTS (res
) = NULL
;
1275 if (a
== NULL
|| b
== NULL
)
1277 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1281 /* If the data references do not alias, then they are independent. */
1282 if (!dr_may_alias_p (a
, b
))
1284 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1288 /* When the references are exactly the same, don't spend time doing
1289 the data dependence tests, just initialize the ddr and return. */
1290 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1292 DDR_AFFINE_P (res
) = true;
1293 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1294 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1295 DDR_LOOP_NEST (res
) = loop_nest
;
1296 DDR_INNER_LOOP (res
) = 0;
1297 DDR_SELF_REFERENCE (res
) = true;
1298 compute_self_dependence (res
);
1302 /* If the references do not access the same object, we do not know
1303 whether they alias or not. */
1304 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1306 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1310 /* If the base of the object is not invariant in the loop nest, we cannot
1311 analyze it. TODO -- in fact, it would suffice to record that there may
1312 be arbitrary dependences in the loops where the base object varies. */
1314 && !object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1315 DR_BASE_OBJECT (a
)))
1317 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1321 /* If the number of dimensions of the access to not agree we can have
1322 a pointer access to a component of the array element type and an
1323 array access while the base-objects are still the same. Punt. */
1324 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
1326 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1330 DDR_AFFINE_P (res
) = true;
1331 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1332 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1333 DDR_LOOP_NEST (res
) = loop_nest
;
1334 DDR_INNER_LOOP (res
) = 0;
1335 DDR_SELF_REFERENCE (res
) = false;
1337 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1339 struct subscript
*subscript
;
1341 subscript
= XNEW (struct subscript
);
1342 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1343 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1344 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1345 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1346 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1352 /* Frees memory used by the conflict function F. */
1355 free_conflict_function (conflict_function
*f
)
1359 if (CF_NONTRIVIAL_P (f
))
1361 for (i
= 0; i
< f
->n
; i
++)
1362 affine_fn_free (f
->fns
[i
]);
1367 /* Frees memory used by SUBSCRIPTS. */
1370 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1375 FOR_EACH_VEC_ELT (subscript_p
, subscripts
, i
, s
)
1377 free_conflict_function (s
->conflicting_iterations_in_a
);
1378 free_conflict_function (s
->conflicting_iterations_in_b
);
1381 VEC_free (subscript_p
, heap
, subscripts
);
1384 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1388 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1391 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1393 fprintf (dump_file
, "(dependence classified: ");
1394 print_generic_expr (dump_file
, chrec
, 0);
1395 fprintf (dump_file
, ")\n");
1398 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1399 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1400 DDR_SUBSCRIPTS (ddr
) = NULL
;
1403 /* The dependence relation DDR cannot be represented by a distance
1407 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1409 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1410 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1412 DDR_AFFINE_P (ddr
) = false;
1417 /* This section contains the classic Banerjee tests. */
1419 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1420 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1423 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1425 return (evolution_function_is_constant_p (chrec_a
)
1426 && evolution_function_is_constant_p (chrec_b
));
1429 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1430 variable, i.e., if the SIV (Single Index Variable) test is true. */
1433 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1435 if ((evolution_function_is_constant_p (chrec_a
)
1436 && evolution_function_is_univariate_p (chrec_b
))
1437 || (evolution_function_is_constant_p (chrec_b
)
1438 && evolution_function_is_univariate_p (chrec_a
)))
1441 if (evolution_function_is_univariate_p (chrec_a
)
1442 && evolution_function_is_univariate_p (chrec_b
))
1444 switch (TREE_CODE (chrec_a
))
1446 case POLYNOMIAL_CHREC
:
1447 switch (TREE_CODE (chrec_b
))
1449 case POLYNOMIAL_CHREC
:
1450 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1465 /* Creates a conflict function with N dimensions. The affine functions
1466 in each dimension follow. */
1468 static conflict_function
*
1469 conflict_fn (unsigned n
, ...)
1472 conflict_function
*ret
= XCNEW (conflict_function
);
1475 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1479 for (i
= 0; i
< n
; i
++)
1480 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1486 /* Returns constant affine function with value CST. */
1489 affine_fn_cst (tree cst
)
1491 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1492 VEC_quick_push (tree
, fn
, cst
);
1496 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1499 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1501 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1504 gcc_assert (dim
> 0);
1505 VEC_quick_push (tree
, fn
, cst
);
1506 for (i
= 1; i
< dim
; i
++)
1507 VEC_quick_push (tree
, fn
, integer_zero_node
);
1508 VEC_quick_push (tree
, fn
, coef
);
1512 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1513 *OVERLAPS_B are initialized to the functions that describe the
1514 relation between the elements accessed twice by CHREC_A and
1515 CHREC_B. For k >= 0, the following property is verified:
1517 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1520 analyze_ziv_subscript (tree chrec_a
,
1522 conflict_function
**overlaps_a
,
1523 conflict_function
**overlaps_b
,
1524 tree
*last_conflicts
)
1526 tree type
, difference
;
1527 dependence_stats
.num_ziv
++;
1529 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1530 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1532 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1533 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1534 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1535 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1537 switch (TREE_CODE (difference
))
1540 if (integer_zerop (difference
))
1542 /* The difference is equal to zero: the accessed index
1543 overlaps for each iteration in the loop. */
1544 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1545 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1546 *last_conflicts
= chrec_dont_know
;
1547 dependence_stats
.num_ziv_dependent
++;
1551 /* The accesses do not overlap. */
1552 *overlaps_a
= conflict_fn_no_dependence ();
1553 *overlaps_b
= conflict_fn_no_dependence ();
1554 *last_conflicts
= integer_zero_node
;
1555 dependence_stats
.num_ziv_independent
++;
1560 /* We're not sure whether the indexes overlap. For the moment,
1561 conservatively answer "don't know". */
1562 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1563 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1565 *overlaps_a
= conflict_fn_not_known ();
1566 *overlaps_b
= conflict_fn_not_known ();
1567 *last_conflicts
= chrec_dont_know
;
1568 dependence_stats
.num_ziv_unimplemented
++;
1572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1573 fprintf (dump_file
, ")\n");
1576 /* Sets NIT to the estimated number of executions of the statements in
1577 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1578 large as the number of iterations. If we have no reliable estimate,
1579 the function returns false, otherwise returns true. */
1582 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
1585 estimate_numbers_of_iterations_loop (loop
, true);
1588 if (!loop
->any_upper_bound
)
1591 *nit
= loop
->nb_iterations_upper_bound
;
1595 if (!loop
->any_estimate
)
1598 *nit
= loop
->nb_iterations_estimate
;
1604 /* Similar to estimated_loop_iterations, but returns the estimate only
1605 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1606 on the number of iterations of LOOP could not be derived, returns -1. */
1609 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
1612 HOST_WIDE_INT hwi_nit
;
1614 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1617 if (!double_int_fits_in_shwi_p (nit
))
1619 hwi_nit
= double_int_to_shwi (nit
);
1621 return hwi_nit
< 0 ? -1 : hwi_nit
;
1624 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1625 and only if it fits to the int type. If this is not the case, or the
1626 estimate on the number of iterations of LOOP could not be derived, returns
1630 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
1635 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
1636 return chrec_dont_know
;
1638 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
1639 if (!double_int_fits_to_tree_p (type
, nit
))
1640 return chrec_dont_know
;
1642 return double_int_to_tree (type
, nit
);
1645 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1646 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1647 *OVERLAPS_B are initialized to the functions that describe the
1648 relation between the elements accessed twice by CHREC_A and
1649 CHREC_B. For k >= 0, the following property is verified:
1651 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1654 analyze_siv_subscript_cst_affine (tree chrec_a
,
1656 conflict_function
**overlaps_a
,
1657 conflict_function
**overlaps_b
,
1658 tree
*last_conflicts
)
1660 bool value0
, value1
, value2
;
1661 tree type
, difference
, tmp
;
1663 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1664 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1665 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1666 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1668 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1670 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1671 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1673 dependence_stats
.num_siv_unimplemented
++;
1674 *overlaps_a
= conflict_fn_not_known ();
1675 *overlaps_b
= conflict_fn_not_known ();
1676 *last_conflicts
= chrec_dont_know
;
1681 if (value0
== false)
1683 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1685 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1686 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1688 *overlaps_a
= conflict_fn_not_known ();
1689 *overlaps_b
= conflict_fn_not_known ();
1690 *last_conflicts
= chrec_dont_know
;
1691 dependence_stats
.num_siv_unimplemented
++;
1700 chrec_b = {10, +, 1}
1703 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1705 HOST_WIDE_INT numiter
;
1706 struct loop
*loop
= get_chrec_loop (chrec_b
);
1708 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1709 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1710 fold_build1 (ABS_EXPR
, type
, difference
),
1711 CHREC_RIGHT (chrec_b
));
1712 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1713 *last_conflicts
= integer_one_node
;
1716 /* Perform weak-zero siv test to see if overlap is
1717 outside the loop bounds. */
1718 numiter
= estimated_loop_iterations_int (loop
, false);
1721 && compare_tree_int (tmp
, numiter
) > 0)
1723 free_conflict_function (*overlaps_a
);
1724 free_conflict_function (*overlaps_b
);
1725 *overlaps_a
= conflict_fn_no_dependence ();
1726 *overlaps_b
= conflict_fn_no_dependence ();
1727 *last_conflicts
= integer_zero_node
;
1728 dependence_stats
.num_siv_independent
++;
1731 dependence_stats
.num_siv_dependent
++;
1735 /* When the step does not divide the difference, there are
1739 *overlaps_a
= conflict_fn_no_dependence ();
1740 *overlaps_b
= conflict_fn_no_dependence ();
1741 *last_conflicts
= integer_zero_node
;
1742 dependence_stats
.num_siv_independent
++;
1751 chrec_b = {10, +, -1}
1753 In this case, chrec_a will not overlap with chrec_b. */
1754 *overlaps_a
= conflict_fn_no_dependence ();
1755 *overlaps_b
= conflict_fn_no_dependence ();
1756 *last_conflicts
= integer_zero_node
;
1757 dependence_stats
.num_siv_independent
++;
1764 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1766 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1767 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1769 *overlaps_a
= conflict_fn_not_known ();
1770 *overlaps_b
= conflict_fn_not_known ();
1771 *last_conflicts
= chrec_dont_know
;
1772 dependence_stats
.num_siv_unimplemented
++;
1777 if (value2
== false)
1781 chrec_b = {10, +, -1}
1783 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1785 HOST_WIDE_INT numiter
;
1786 struct loop
*loop
= get_chrec_loop (chrec_b
);
1788 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1789 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1790 CHREC_RIGHT (chrec_b
));
1791 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1792 *last_conflicts
= integer_one_node
;
1794 /* Perform weak-zero siv test to see if overlap is
1795 outside the loop bounds. */
1796 numiter
= estimated_loop_iterations_int (loop
, false);
1799 && compare_tree_int (tmp
, numiter
) > 0)
1801 free_conflict_function (*overlaps_a
);
1802 free_conflict_function (*overlaps_b
);
1803 *overlaps_a
= conflict_fn_no_dependence ();
1804 *overlaps_b
= conflict_fn_no_dependence ();
1805 *last_conflicts
= integer_zero_node
;
1806 dependence_stats
.num_siv_independent
++;
1809 dependence_stats
.num_siv_dependent
++;
1813 /* When the step does not divide the difference, there
1817 *overlaps_a
= conflict_fn_no_dependence ();
1818 *overlaps_b
= conflict_fn_no_dependence ();
1819 *last_conflicts
= integer_zero_node
;
1820 dependence_stats
.num_siv_independent
++;
1830 In this case, chrec_a will not overlap with chrec_b. */
1831 *overlaps_a
= conflict_fn_no_dependence ();
1832 *overlaps_b
= conflict_fn_no_dependence ();
1833 *last_conflicts
= integer_zero_node
;
1834 dependence_stats
.num_siv_independent
++;
1842 /* Helper recursive function for initializing the matrix A. Returns
1843 the initial value of CHREC. */
1846 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1850 switch (TREE_CODE (chrec
))
1852 case POLYNOMIAL_CHREC
:
1853 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
1855 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1856 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1862 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1863 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
1865 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
1870 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1871 return chrec_convert (chrec_type (chrec
), op
, NULL
);
1876 /* Handle ~X as -1 - X. */
1877 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1878 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
1879 build_int_cst (TREE_TYPE (chrec
), -1), op
);
1891 #define FLOOR_DIV(x,y) ((x) / (y))
1893 /* Solves the special case of the Diophantine equation:
1894 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1896 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1897 number of iterations that loops X and Y run. The overlaps will be
1898 constructed as evolutions in dimension DIM. */
1901 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1902 affine_fn
*overlaps_a
,
1903 affine_fn
*overlaps_b
,
1904 tree
*last_conflicts
, int dim
)
1906 if (((step_a
> 0 && step_b
> 0)
1907 || (step_a
< 0 && step_b
< 0)))
1909 int step_overlaps_a
, step_overlaps_b
;
1910 int gcd_steps_a_b
, last_conflict
, tau2
;
1912 gcd_steps_a_b
= gcd (step_a
, step_b
);
1913 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1914 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1918 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1919 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1920 last_conflict
= tau2
;
1921 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1924 *last_conflicts
= chrec_dont_know
;
1926 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
1927 build_int_cst (NULL_TREE
,
1929 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
1930 build_int_cst (NULL_TREE
,
1936 *overlaps_a
= affine_fn_cst (integer_zero_node
);
1937 *overlaps_b
= affine_fn_cst (integer_zero_node
);
1938 *last_conflicts
= integer_zero_node
;
1942 /* Solves the special case of a Diophantine equation where CHREC_A is
1943 an affine bivariate function, and CHREC_B is an affine univariate
1944 function. For example,
1946 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1948 has the following overlapping functions:
1950 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1951 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1952 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1954 FORNOW: This is a specialized implementation for a case occurring in
1955 a common benchmark. Implement the general algorithm. */
1958 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1959 conflict_function
**overlaps_a
,
1960 conflict_function
**overlaps_b
,
1961 tree
*last_conflicts
)
1963 bool xz_p
, yz_p
, xyz_p
;
1964 int step_x
, step_y
, step_z
;
1965 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
1966 affine_fn overlaps_a_xz
, overlaps_b_xz
;
1967 affine_fn overlaps_a_yz
, overlaps_b_yz
;
1968 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
1969 affine_fn ova1
, ova2
, ovb
;
1970 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
1972 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
1973 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
1974 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
1977 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a
)),
1979 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), false);
1980 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), false);
1982 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
1984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1985 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
1987 *overlaps_a
= conflict_fn_not_known ();
1988 *overlaps_b
= conflict_fn_not_known ();
1989 *last_conflicts
= chrec_dont_know
;
1993 niter
= MIN (niter_x
, niter_z
);
1994 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
1997 &last_conflicts_xz
, 1);
1998 niter
= MIN (niter_y
, niter_z
);
1999 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2002 &last_conflicts_yz
, 2);
2003 niter
= MIN (niter_x
, niter_z
);
2004 niter
= MIN (niter_y
, niter
);
2005 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2008 &last_conflicts_xyz
, 3);
2010 xz_p
= !integer_zerop (last_conflicts_xz
);
2011 yz_p
= !integer_zerop (last_conflicts_yz
);
2012 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2014 if (xz_p
|| yz_p
|| xyz_p
)
2016 ova1
= affine_fn_cst (integer_zero_node
);
2017 ova2
= affine_fn_cst (integer_zero_node
);
2018 ovb
= affine_fn_cst (integer_zero_node
);
2021 affine_fn t0
= ova1
;
2024 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2025 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2026 affine_fn_free (t0
);
2027 affine_fn_free (t2
);
2028 *last_conflicts
= last_conflicts_xz
;
2032 affine_fn t0
= ova2
;
2035 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2036 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2037 affine_fn_free (t0
);
2038 affine_fn_free (t2
);
2039 *last_conflicts
= last_conflicts_yz
;
2043 affine_fn t0
= ova1
;
2044 affine_fn t2
= ova2
;
2047 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2048 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2049 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2050 affine_fn_free (t0
);
2051 affine_fn_free (t2
);
2052 affine_fn_free (t4
);
2053 *last_conflicts
= last_conflicts_xyz
;
2055 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2056 *overlaps_b
= conflict_fn (1, ovb
);
2060 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2061 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2062 *last_conflicts
= integer_zero_node
;
2065 affine_fn_free (overlaps_a_xz
);
2066 affine_fn_free (overlaps_b_xz
);
2067 affine_fn_free (overlaps_a_yz
);
2068 affine_fn_free (overlaps_b_yz
);
2069 affine_fn_free (overlaps_a_xyz
);
2070 affine_fn_free (overlaps_b_xyz
);
2073 /* Determines the overlapping elements due to accesses CHREC_A and
2074 CHREC_B, that are affine functions. This function cannot handle
2075 symbolic evolution functions, ie. when initial conditions are
2076 parameters, because it uses lambda matrices of integers. */
2079 analyze_subscript_affine_affine (tree chrec_a
,
2081 conflict_function
**overlaps_a
,
2082 conflict_function
**overlaps_b
,
2083 tree
*last_conflicts
)
2085 unsigned nb_vars_a
, nb_vars_b
, dim
;
2086 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2087 lambda_matrix A
, U
, S
;
2088 struct obstack scratch_obstack
;
2090 if (eq_evolutions_p (chrec_a
, chrec_b
))
2092 /* The accessed index overlaps for each iteration in the
2094 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2095 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2096 *last_conflicts
= chrec_dont_know
;
2099 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2100 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2102 /* For determining the initial intersection, we have to solve a
2103 Diophantine equation. This is the most time consuming part.
2105 For answering to the question: "Is there a dependence?" we have
2106 to prove that there exists a solution to the Diophantine
2107 equation, and that the solution is in the iteration domain,
2108 i.e. the solution is positive or zero, and that the solution
2109 happens before the upper bound loop.nb_iterations. Otherwise
2110 there is no dependence. This function outputs a description of
2111 the iterations that hold the intersections. */
2113 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2114 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2116 gcc_obstack_init (&scratch_obstack
);
2118 dim
= nb_vars_a
+ nb_vars_b
;
2119 U
= lambda_matrix_new (dim
, dim
, &scratch_obstack
);
2120 A
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2121 S
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2123 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2124 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2125 gamma
= init_b
- init_a
;
2127 /* Don't do all the hard work of solving the Diophantine equation
2128 when we already know the solution: for example,
2131 | gamma = 3 - 3 = 0.
2132 Then the first overlap occurs during the first iterations:
2133 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2137 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2139 HOST_WIDE_INT step_a
, step_b
;
2140 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2143 niter_a
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
),
2145 niter_b
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
),
2147 niter
= MIN (niter_a
, niter_b
);
2148 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2149 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2151 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2154 *overlaps_a
= conflict_fn (1, ova
);
2155 *overlaps_b
= conflict_fn (1, ovb
);
2158 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2159 compute_overlap_steps_for_affine_1_2
2160 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2162 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2163 compute_overlap_steps_for_affine_1_2
2164 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2168 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2169 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2170 *overlaps_a
= conflict_fn_not_known ();
2171 *overlaps_b
= conflict_fn_not_known ();
2172 *last_conflicts
= chrec_dont_know
;
2174 goto end_analyze_subs_aa
;
2178 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2183 lambda_matrix_row_negate (U
, dim
, 0);
2185 gcd_alpha_beta
= S
[0][0];
2187 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2188 but that is a quite strange case. Instead of ICEing, answer
2190 if (gcd_alpha_beta
== 0)
2192 *overlaps_a
= conflict_fn_not_known ();
2193 *overlaps_b
= conflict_fn_not_known ();
2194 *last_conflicts
= chrec_dont_know
;
2195 goto end_analyze_subs_aa
;
2198 /* The classic "gcd-test". */
2199 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2201 /* The "gcd-test" has determined that there is no integer
2202 solution, i.e. there is no dependence. */
2203 *overlaps_a
= conflict_fn_no_dependence ();
2204 *overlaps_b
= conflict_fn_no_dependence ();
2205 *last_conflicts
= integer_zero_node
;
2208 /* Both access functions are univariate. This includes SIV and MIV cases. */
2209 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2211 /* Both functions should have the same evolution sign. */
2212 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2213 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2215 /* The solutions are given by:
2217 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2220 For a given integer t. Using the following variables,
2222 | i0 = u11 * gamma / gcd_alpha_beta
2223 | j0 = u12 * gamma / gcd_alpha_beta
2230 | y0 = j0 + j1 * t. */
2231 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2233 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2234 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2238 if ((i1
== 0 && i0
< 0)
2239 || (j1
== 0 && j0
< 0))
2241 /* There is no solution.
2242 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2243 falls in here, but for the moment we don't look at the
2244 upper bound of the iteration domain. */
2245 *overlaps_a
= conflict_fn_no_dependence ();
2246 *overlaps_b
= conflict_fn_no_dependence ();
2247 *last_conflicts
= integer_zero_node
;
2248 goto end_analyze_subs_aa
;
2251 if (i1
> 0 && j1
> 0)
2253 HOST_WIDE_INT niter_a
= estimated_loop_iterations_int
2254 (get_chrec_loop (chrec_a
), false);
2255 HOST_WIDE_INT niter_b
= estimated_loop_iterations_int
2256 (get_chrec_loop (chrec_b
), false);
2257 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2259 /* (X0, Y0) is a solution of the Diophantine equation:
2260 "chrec_a (X0) = chrec_b (Y0)". */
2261 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2263 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2264 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2266 /* (X1, Y1) is the smallest positive solution of the eq
2267 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2268 first conflict occurs. */
2269 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2270 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2271 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2275 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2276 FLOOR_DIV (niter
- j0
, j1
));
2277 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2279 /* If the overlap occurs outside of the bounds of the
2280 loop, there is no dependence. */
2281 if (x1
>= niter
|| y1
>= niter
)
2283 *overlaps_a
= conflict_fn_no_dependence ();
2284 *overlaps_b
= conflict_fn_no_dependence ();
2285 *last_conflicts
= integer_zero_node
;
2286 goto end_analyze_subs_aa
;
2289 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2292 *last_conflicts
= chrec_dont_know
;
2296 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2298 build_int_cst (NULL_TREE
, i1
)));
2301 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2303 build_int_cst (NULL_TREE
, j1
)));
2307 /* FIXME: For the moment, the upper bound of the
2308 iteration domain for i and j is not checked. */
2309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2310 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2311 *overlaps_a
= conflict_fn_not_known ();
2312 *overlaps_b
= conflict_fn_not_known ();
2313 *last_conflicts
= chrec_dont_know
;
2318 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2319 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2320 *overlaps_a
= conflict_fn_not_known ();
2321 *overlaps_b
= conflict_fn_not_known ();
2322 *last_conflicts
= chrec_dont_know
;
2327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2328 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2329 *overlaps_a
= conflict_fn_not_known ();
2330 *overlaps_b
= conflict_fn_not_known ();
2331 *last_conflicts
= chrec_dont_know
;
2334 end_analyze_subs_aa
:
2335 obstack_free (&scratch_obstack
, NULL
);
2336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2338 fprintf (dump_file
, " (overlaps_a = ");
2339 dump_conflict_function (dump_file
, *overlaps_a
);
2340 fprintf (dump_file
, ")\n (overlaps_b = ");
2341 dump_conflict_function (dump_file
, *overlaps_b
);
2342 fprintf (dump_file
, ")\n");
2343 fprintf (dump_file
, ")\n");
2347 /* Returns true when analyze_subscript_affine_affine can be used for
2348 determining the dependence relation between chrec_a and chrec_b,
2349 that contain symbols. This function modifies chrec_a and chrec_b
2350 such that the analysis result is the same, and such that they don't
2351 contain symbols, and then can safely be passed to the analyzer.
2353 Example: The analysis of the following tuples of evolutions produce
2354 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2357 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2358 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2362 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2364 tree diff
, type
, left_a
, left_b
, right_b
;
2366 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2367 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2368 /* FIXME: For the moment not handled. Might be refined later. */
2371 type
= chrec_type (*chrec_a
);
2372 left_a
= CHREC_LEFT (*chrec_a
);
2373 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2374 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2376 if (!evolution_function_is_constant_p (diff
))
2379 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2380 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2382 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2383 diff
, CHREC_RIGHT (*chrec_a
));
2384 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2385 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2386 build_int_cst (type
, 0),
2391 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2392 *OVERLAPS_B are initialized to the functions that describe the
2393 relation between the elements accessed twice by CHREC_A and
2394 CHREC_B. For k >= 0, the following property is verified:
2396 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2399 analyze_siv_subscript (tree chrec_a
,
2401 conflict_function
**overlaps_a
,
2402 conflict_function
**overlaps_b
,
2403 tree
*last_conflicts
,
2406 dependence_stats
.num_siv
++;
2408 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2409 fprintf (dump_file
, "(analyze_siv_subscript \n");
2411 if (evolution_function_is_constant_p (chrec_a
)
2412 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2413 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2414 overlaps_a
, overlaps_b
, last_conflicts
);
2416 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2417 && evolution_function_is_constant_p (chrec_b
))
2418 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2419 overlaps_b
, overlaps_a
, last_conflicts
);
2421 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2422 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2424 if (!chrec_contains_symbols (chrec_a
)
2425 && !chrec_contains_symbols (chrec_b
))
2427 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2428 overlaps_a
, overlaps_b
,
2431 if (CF_NOT_KNOWN_P (*overlaps_a
)
2432 || CF_NOT_KNOWN_P (*overlaps_b
))
2433 dependence_stats
.num_siv_unimplemented
++;
2434 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2435 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2436 dependence_stats
.num_siv_independent
++;
2438 dependence_stats
.num_siv_dependent
++;
2440 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2443 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2444 overlaps_a
, overlaps_b
,
2447 if (CF_NOT_KNOWN_P (*overlaps_a
)
2448 || CF_NOT_KNOWN_P (*overlaps_b
))
2449 dependence_stats
.num_siv_unimplemented
++;
2450 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2451 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2452 dependence_stats
.num_siv_independent
++;
2454 dependence_stats
.num_siv_dependent
++;
2457 goto siv_subscript_dontknow
;
2462 siv_subscript_dontknow
:;
2463 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2464 fprintf (dump_file
, "siv test failed: unimplemented.\n");
2465 *overlaps_a
= conflict_fn_not_known ();
2466 *overlaps_b
= conflict_fn_not_known ();
2467 *last_conflicts
= chrec_dont_know
;
2468 dependence_stats
.num_siv_unimplemented
++;
2471 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2472 fprintf (dump_file
, ")\n");
2475 /* Returns false if we can prove that the greatest common divisor of the steps
2476 of CHREC does not divide CST, false otherwise. */
2479 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2481 HOST_WIDE_INT cd
= 0, val
;
2484 if (!host_integerp (cst
, 0))
2486 val
= tree_low_cst (cst
, 0);
2488 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2490 step
= CHREC_RIGHT (chrec
);
2491 if (!host_integerp (step
, 0))
2493 cd
= gcd (cd
, tree_low_cst (step
, 0));
2494 chrec
= CHREC_LEFT (chrec
);
2497 return val
% cd
== 0;
2500 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2501 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2502 functions that describe the relation between the elements accessed
2503 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2506 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2509 analyze_miv_subscript (tree chrec_a
,
2511 conflict_function
**overlaps_a
,
2512 conflict_function
**overlaps_b
,
2513 tree
*last_conflicts
,
2514 struct loop
*loop_nest
)
2516 /* FIXME: This is a MIV subscript, not yet handled.
2517 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2520 In the SIV test we had to solve a Diophantine equation with two
2521 variables. In the MIV case we have to solve a Diophantine
2522 equation with 2*n variables (if the subscript uses n IVs).
2524 tree type
, difference
;
2526 dependence_stats
.num_miv
++;
2527 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2528 fprintf (dump_file
, "(analyze_miv_subscript \n");
2530 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2531 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2532 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2533 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2535 if (eq_evolutions_p (chrec_a
, chrec_b
))
2537 /* Access functions are the same: all the elements are accessed
2538 in the same order. */
2539 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2540 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2541 *last_conflicts
= estimated_loop_iterations_tree
2542 (get_chrec_loop (chrec_a
), true);
2543 dependence_stats
.num_miv_dependent
++;
2546 else if (evolution_function_is_constant_p (difference
)
2547 /* For the moment, the following is verified:
2548 evolution_function_is_affine_multivariate_p (chrec_a,
2550 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2552 /* testsuite/.../ssa-chrec-33.c
2553 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2555 The difference is 1, and all the evolution steps are multiples
2556 of 2, consequently there are no overlapping elements. */
2557 *overlaps_a
= conflict_fn_no_dependence ();
2558 *overlaps_b
= conflict_fn_no_dependence ();
2559 *last_conflicts
= integer_zero_node
;
2560 dependence_stats
.num_miv_independent
++;
2563 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2564 && !chrec_contains_symbols (chrec_a
)
2565 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2566 && !chrec_contains_symbols (chrec_b
))
2568 /* testsuite/.../ssa-chrec-35.c
2569 {0, +, 1}_2 vs. {0, +, 1}_3
2570 the overlapping elements are respectively located at iterations:
2571 {0, +, 1}_x and {0, +, 1}_x,
2572 in other words, we have the equality:
2573 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2576 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2577 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2579 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2580 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2582 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2583 overlaps_a
, overlaps_b
, last_conflicts
);
2585 if (CF_NOT_KNOWN_P (*overlaps_a
)
2586 || CF_NOT_KNOWN_P (*overlaps_b
))
2587 dependence_stats
.num_miv_unimplemented
++;
2588 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2589 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2590 dependence_stats
.num_miv_independent
++;
2592 dependence_stats
.num_miv_dependent
++;
2597 /* When the analysis is too difficult, answer "don't know". */
2598 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2599 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2601 *overlaps_a
= conflict_fn_not_known ();
2602 *overlaps_b
= conflict_fn_not_known ();
2603 *last_conflicts
= chrec_dont_know
;
2604 dependence_stats
.num_miv_unimplemented
++;
2607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2608 fprintf (dump_file
, ")\n");
2611 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2612 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2613 OVERLAP_ITERATIONS_B are initialized with two functions that
2614 describe the iterations that contain conflicting elements.
2616 Remark: For an integer k >= 0, the following equality is true:
2618 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2622 analyze_overlapping_iterations (tree chrec_a
,
2624 conflict_function
**overlap_iterations_a
,
2625 conflict_function
**overlap_iterations_b
,
2626 tree
*last_conflicts
, struct loop
*loop_nest
)
2628 unsigned int lnn
= loop_nest
->num
;
2630 dependence_stats
.num_subscript_tests
++;
2632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2634 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2635 fprintf (dump_file
, " (chrec_a = ");
2636 print_generic_expr (dump_file
, chrec_a
, 0);
2637 fprintf (dump_file
, ")\n (chrec_b = ");
2638 print_generic_expr (dump_file
, chrec_b
, 0);
2639 fprintf (dump_file
, ")\n");
2642 if (chrec_a
== NULL_TREE
2643 || chrec_b
== NULL_TREE
2644 || chrec_contains_undetermined (chrec_a
)
2645 || chrec_contains_undetermined (chrec_b
))
2647 dependence_stats
.num_subscript_undetermined
++;
2649 *overlap_iterations_a
= conflict_fn_not_known ();
2650 *overlap_iterations_b
= conflict_fn_not_known ();
2653 /* If they are the same chrec, and are affine, they overlap
2654 on every iteration. */
2655 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2656 && (evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2657 || operand_equal_p (chrec_a
, chrec_b
, 0)))
2659 dependence_stats
.num_same_subscript_function
++;
2660 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2661 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2662 *last_conflicts
= chrec_dont_know
;
2665 /* If they aren't the same, and aren't affine, we can't do anything
2667 else if ((chrec_contains_symbols (chrec_a
)
2668 || chrec_contains_symbols (chrec_b
))
2669 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2670 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2672 dependence_stats
.num_subscript_undetermined
++;
2673 *overlap_iterations_a
= conflict_fn_not_known ();
2674 *overlap_iterations_b
= conflict_fn_not_known ();
2677 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2678 analyze_ziv_subscript (chrec_a
, chrec_b
,
2679 overlap_iterations_a
, overlap_iterations_b
,
2682 else if (siv_subscript_p (chrec_a
, chrec_b
))
2683 analyze_siv_subscript (chrec_a
, chrec_b
,
2684 overlap_iterations_a
, overlap_iterations_b
,
2685 last_conflicts
, lnn
);
2688 analyze_miv_subscript (chrec_a
, chrec_b
,
2689 overlap_iterations_a
, overlap_iterations_b
,
2690 last_conflicts
, loop_nest
);
2692 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2694 fprintf (dump_file
, " (overlap_iterations_a = ");
2695 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2696 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2697 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2698 fprintf (dump_file
, ")\n");
2699 fprintf (dump_file
, ")\n");
2703 /* Helper function for uniquely inserting distance vectors. */
2706 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2711 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
)
2712 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2715 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2718 /* Helper function for uniquely inserting direction vectors. */
2721 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2726 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
)
2727 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2730 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2733 /* Add a distance of 1 on all the loops outer than INDEX. If we
2734 haven't yet determined a distance for this outer loop, push a new
2735 distance vector composed of the previous distance, and a distance
2736 of 1 for this outer loop. Example:
2744 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2745 save (0, 1), then we have to save (1, 0). */
2748 add_outer_distances (struct data_dependence_relation
*ddr
,
2749 lambda_vector dist_v
, int index
)
2751 /* For each outer loop where init_v is not set, the accesses are
2752 in dependence of distance 1 in the loop. */
2753 while (--index
>= 0)
2755 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2756 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2758 save_dist_v (ddr
, save_v
);
2762 /* Return false when fail to represent the data dependence as a
2763 distance vector. INIT_B is set to true when a component has been
2764 added to the distance vector DIST_V. INDEX_CARRY is then set to
2765 the index in DIST_V that carries the dependence. */
2768 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2769 struct data_reference
*ddr_a
,
2770 struct data_reference
*ddr_b
,
2771 lambda_vector dist_v
, bool *init_b
,
2775 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2777 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2779 tree access_fn_a
, access_fn_b
;
2780 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2782 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2784 non_affine_dependence_relation (ddr
);
2788 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2789 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2791 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2792 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2795 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2796 DDR_LOOP_NEST (ddr
));
2797 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2798 DDR_LOOP_NEST (ddr
));
2800 /* The dependence is carried by the outermost loop. Example:
2807 In this case, the dependence is carried by loop_1. */
2808 index
= index_a
< index_b
? index_a
: index_b
;
2809 *index_carry
= MIN (index
, *index_carry
);
2811 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2813 non_affine_dependence_relation (ddr
);
2817 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2819 /* This is the subscript coupling test. If we have already
2820 recorded a distance for this loop (a distance coming from
2821 another subscript), it should be the same. For example,
2822 in the following code, there is no dependence:
2829 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2831 finalize_ddr_dependent (ddr
, chrec_known
);
2835 dist_v
[index
] = dist
;
2839 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2841 /* This can be for example an affine vs. constant dependence
2842 (T[i] vs. T[3]) that is not an affine dependence and is
2843 not representable as a distance vector. */
2844 non_affine_dependence_relation (ddr
);
2852 /* Return true when the DDR contains only constant access functions. */
2855 constant_access_functions (const struct data_dependence_relation
*ddr
)
2859 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2860 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2861 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2867 /* Helper function for the case where DDR_A and DDR_B are the same
2868 multivariate access function with a constant step. For an example
2872 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2875 tree c_1
= CHREC_LEFT (c_2
);
2876 tree c_0
= CHREC_LEFT (c_1
);
2877 lambda_vector dist_v
;
2880 /* Polynomials with more than 2 variables are not handled yet. When
2881 the evolution steps are parameters, it is not possible to
2882 represent the dependence using classical distance vectors. */
2883 if (TREE_CODE (c_0
) != INTEGER_CST
2884 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
2885 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
2887 DDR_AFFINE_P (ddr
) = false;
2891 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2892 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2894 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2895 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2896 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2897 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2910 save_dist_v (ddr
, dist_v
);
2912 add_outer_distances (ddr
, dist_v
, x_1
);
2915 /* Helper function for the case where DDR_A and DDR_B are the same
2916 access functions. */
2919 add_other_self_distances (struct data_dependence_relation
*ddr
)
2921 lambda_vector dist_v
;
2923 int index_carry
= DDR_NB_LOOPS (ddr
);
2925 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2927 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
2929 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
2931 if (!evolution_function_is_univariate_p (access_fun
))
2933 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
2935 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2939 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
2941 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
2942 add_multivariate_self_dist (ddr
, access_fun
);
2944 /* The evolution step is not constant: it varies in
2945 the outer loop, so this cannot be represented by a
2946 distance vector. For example in pr34635.c the
2947 evolution is {0, +, {0, +, 4}_1}_2. */
2948 DDR_AFFINE_P (ddr
) = false;
2953 index_carry
= MIN (index_carry
,
2954 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
2955 DDR_LOOP_NEST (ddr
)));
2959 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2960 add_outer_distances (ddr
, dist_v
, index_carry
);
2964 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
2966 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2968 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
2969 save_dist_v (ddr
, dist_v
);
2972 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2973 is the case for example when access functions are the same and
2974 equal to a constant, as in:
2981 in which case the distance vectors are (0) and (1). */
2984 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
2988 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2990 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
2991 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
2992 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
2994 for (j
= 0; j
< ca
->n
; j
++)
2995 if (affine_function_zero_p (ca
->fns
[j
]))
2997 insert_innermost_unit_dist_vector (ddr
);
3001 for (j
= 0; j
< cb
->n
; j
++)
3002 if (affine_function_zero_p (cb
->fns
[j
]))
3004 insert_innermost_unit_dist_vector (ddr
);
3010 /* Compute the classic per loop distance vector. DDR is the data
3011 dependence relation to build a vector from. Return false when fail
3012 to represent the data dependence as a distance vector. */
3015 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3016 struct loop
*loop_nest
)
3018 bool init_b
= false;
3019 int index_carry
= DDR_NB_LOOPS (ddr
);
3020 lambda_vector dist_v
;
3022 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3025 if (same_access_functions (ddr
))
3027 /* Save the 0 vector. */
3028 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3029 save_dist_v (ddr
, dist_v
);
3031 if (constant_access_functions (ddr
))
3032 add_distance_for_zero_overlaps (ddr
);
3034 if (DDR_NB_LOOPS (ddr
) > 1)
3035 add_other_self_distances (ddr
);
3040 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3041 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3042 dist_v
, &init_b
, &index_carry
))
3045 /* Save the distance vector if we initialized one. */
3048 /* Verify a basic constraint: classic distance vectors should
3049 always be lexicographically positive.
3051 Data references are collected in the order of execution of
3052 the program, thus for the following loop
3054 | for (i = 1; i < 100; i++)
3055 | for (j = 1; j < 100; j++)
3057 | t = T[j+1][i-1]; // A
3058 | T[j][i] = t + 2; // B
3061 references are collected following the direction of the wind:
3062 A then B. The data dependence tests are performed also
3063 following this order, such that we're looking at the distance
3064 separating the elements accessed by A from the elements later
3065 accessed by B. But in this example, the distance returned by
3066 test_dep (A, B) is lexicographically negative (-1, 1), that
3067 means that the access A occurs later than B with respect to
3068 the outer loop, ie. we're actually looking upwind. In this
3069 case we solve test_dep (B, A) looking downwind to the
3070 lexicographically positive solution, that returns the
3071 distance vector (1, -1). */
3072 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3074 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3075 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3078 compute_subscript_distance (ddr
);
3079 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3080 save_v
, &init_b
, &index_carry
))
3082 save_dist_v (ddr
, save_v
);
3083 DDR_REVERSED_P (ddr
) = true;
3085 /* In this case there is a dependence forward for all the
3088 | for (k = 1; k < 100; k++)
3089 | for (i = 1; i < 100; i++)
3090 | for (j = 1; j < 100; j++)
3092 | t = T[j+1][i-1]; // A
3093 | T[j][i] = t + 2; // B
3101 if (DDR_NB_LOOPS (ddr
) > 1)
3103 add_outer_distances (ddr
, save_v
, index_carry
);
3104 add_outer_distances (ddr
, dist_v
, index_carry
);
3109 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3110 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3112 if (DDR_NB_LOOPS (ddr
) > 1)
3114 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3116 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3117 DDR_A (ddr
), loop_nest
))
3119 compute_subscript_distance (ddr
);
3120 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3121 opposite_v
, &init_b
,
3125 save_dist_v (ddr
, save_v
);
3126 add_outer_distances (ddr
, dist_v
, index_carry
);
3127 add_outer_distances (ddr
, opposite_v
, index_carry
);
3130 save_dist_v (ddr
, save_v
);
3135 /* There is a distance of 1 on all the outer loops: Example:
3136 there is a dependence of distance 1 on loop_1 for the array A.
3142 add_outer_distances (ddr
, dist_v
,
3143 lambda_vector_first_nz (dist_v
,
3144 DDR_NB_LOOPS (ddr
), 0));
3147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3151 fprintf (dump_file
, "(build_classic_dist_vector\n");
3152 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3154 fprintf (dump_file
, " dist_vector = (");
3155 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3156 DDR_NB_LOOPS (ddr
));
3157 fprintf (dump_file
, " )\n");
3159 fprintf (dump_file
, ")\n");
3165 /* Return the direction for a given distance.
3166 FIXME: Computing dir this way is suboptimal, since dir can catch
3167 cases that dist is unable to represent. */
3169 static inline enum data_dependence_direction
3170 dir_from_dist (int dist
)
3173 return dir_positive
;
3175 return dir_negative
;
3180 /* Compute the classic per loop direction vector. DDR is the data
3181 dependence relation to build a vector from. */
3184 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3187 lambda_vector dist_v
;
3189 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
)
3191 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3193 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3194 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3196 save_dir_v (ddr
, dir_v
);
3200 /* Helper function. Returns true when there is a dependence between
3201 data references DRA and DRB. */
3204 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3205 struct data_reference
*dra
,
3206 struct data_reference
*drb
,
3207 struct loop
*loop_nest
)
3210 tree last_conflicts
;
3211 struct subscript
*subscript
;
3213 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3216 conflict_function
*overlaps_a
, *overlaps_b
;
3218 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3219 DR_ACCESS_FN (drb
, i
),
3220 &overlaps_a
, &overlaps_b
,
3221 &last_conflicts
, loop_nest
);
3223 if (CF_NOT_KNOWN_P (overlaps_a
)
3224 || CF_NOT_KNOWN_P (overlaps_b
))
3226 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3227 dependence_stats
.num_dependence_undetermined
++;
3228 free_conflict_function (overlaps_a
);
3229 free_conflict_function (overlaps_b
);
3233 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3234 || CF_NO_DEPENDENCE_P (overlaps_b
))
3236 finalize_ddr_dependent (ddr
, chrec_known
);
3237 dependence_stats
.num_dependence_independent
++;
3238 free_conflict_function (overlaps_a
);
3239 free_conflict_function (overlaps_b
);
3245 if (SUB_CONFLICTS_IN_A (subscript
))
3246 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3247 if (SUB_CONFLICTS_IN_B (subscript
))
3248 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3250 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3251 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3252 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3259 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3262 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3263 struct loop
*loop_nest
)
3266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3267 fprintf (dump_file
, "(subscript_dependence_tester \n");
3269 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3270 dependence_stats
.num_dependence_dependent
++;
3272 compute_subscript_distance (ddr
);
3273 if (build_classic_dist_vector (ddr
, loop_nest
))
3274 build_classic_dir_vector (ddr
);
3276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3277 fprintf (dump_file
, ")\n");
3280 /* Returns true when all the access functions of A are affine or
3281 constant with respect to LOOP_NEST. */
3284 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3285 const struct loop
*loop_nest
)
3288 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3291 FOR_EACH_VEC_ELT (tree
, fns
, i
, t
)
3292 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3293 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3299 /* Initializes an equation for an OMEGA problem using the information
3300 contained in the ACCESS_FUN. Returns true when the operation
3303 PB is the omega constraint system.
3304 EQ is the number of the equation to be initialized.
3305 OFFSET is used for shifting the variables names in the constraints:
3306 a constrain is composed of 2 * the number of variables surrounding
3307 dependence accesses. OFFSET is set either to 0 for the first n variables,
3308 then it is set to n.
3309 ACCESS_FUN is expected to be an affine chrec. */
3312 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3313 unsigned int offset
, tree access_fun
,
3314 struct data_dependence_relation
*ddr
)
3316 switch (TREE_CODE (access_fun
))
3318 case POLYNOMIAL_CHREC
:
3320 tree left
= CHREC_LEFT (access_fun
);
3321 tree right
= CHREC_RIGHT (access_fun
);
3322 int var
= CHREC_VARIABLE (access_fun
);
3325 if (TREE_CODE (right
) != INTEGER_CST
)
3328 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3329 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3331 /* Compute the innermost loop index. */
3332 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3335 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3336 += int_cst_value (right
);
3338 switch (TREE_CODE (left
))
3340 case POLYNOMIAL_CHREC
:
3341 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3344 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3353 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3361 /* As explained in the comments preceding init_omega_for_ddr, we have
3362 to set up a system for each loop level, setting outer loops
3363 variation to zero, and current loop variation to positive or zero.
3364 Save each lexico positive distance vector. */
3367 omega_extract_distance_vectors (omega_pb pb
,
3368 struct data_dependence_relation
*ddr
)
3372 struct loop
*loopi
, *loopj
;
3373 enum omega_result res
;
3375 /* Set a new problem for each loop in the nest. The basis is the
3376 problem that we have initialized until now. On top of this we
3377 add new constraints. */
3378 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3379 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3382 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3383 DDR_NB_LOOPS (ddr
));
3385 omega_copy_problem (copy
, pb
);
3387 /* For all the outer loops "loop_j", add "dj = 0". */
3389 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3391 eq
= omega_add_zero_eq (copy
, omega_black
);
3392 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3395 /* For "loop_i", add "0 <= di". */
3396 geq
= omega_add_zero_geq (copy
, omega_black
);
3397 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3399 /* Reduce the constraint system, and test that the current
3400 problem is feasible. */
3401 res
= omega_simplify_problem (copy
);
3402 if (res
== omega_false
3403 || res
== omega_unknown
3404 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3407 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3408 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3410 dist
= copy
->subs
[eq
].coef
[0];
3416 /* Reinitialize problem... */
3417 omega_copy_problem (copy
, pb
);
3419 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3421 eq
= omega_add_zero_eq (copy
, omega_black
);
3422 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3425 /* ..., but this time "di = 1". */
3426 eq
= omega_add_zero_eq (copy
, omega_black
);
3427 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3428 copy
->eqs
[eq
].coef
[0] = -1;
3430 res
= omega_simplify_problem (copy
);
3431 if (res
== omega_false
3432 || res
== omega_unknown
3433 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3436 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3437 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3439 dist
= copy
->subs
[eq
].coef
[0];
3445 /* Save the lexicographically positive distance vector. */
3448 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3449 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3453 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3454 if (copy
->subs
[eq
].key
> 0)
3456 dist
= copy
->subs
[eq
].coef
[0];
3457 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3460 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3461 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3463 save_dist_v (ddr
, dist_v
);
3464 save_dir_v (ddr
, dir_v
);
3468 omega_free_problem (copy
);
3472 /* This is called for each subscript of a tuple of data references:
3473 insert an equality for representing the conflicts. */
3476 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3477 struct data_dependence_relation
*ddr
,
3478 omega_pb pb
, bool *maybe_dependent
)
3481 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3482 TREE_TYPE (access_fun_b
));
3483 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3484 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3485 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3488 /* When the fun_a - fun_b is not constant, the dependence is not
3489 captured by the classic distance vector representation. */
3490 if (TREE_CODE (difference
) != INTEGER_CST
)
3494 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3496 /* There is no dependence. */
3497 *maybe_dependent
= false;
3501 minus_one
= build_int_cst (type
, -1);
3502 fun_b
= chrec_fold_multiply (type
, fun_b
, minus_one
);
3504 eq
= omega_add_zero_eq (pb
, omega_black
);
3505 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3506 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3507 /* There is probably a dependence, but the system of
3508 constraints cannot be built: answer "don't know". */
3512 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3513 && !int_divides_p (lambda_vector_gcd
3514 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3515 2 * DDR_NB_LOOPS (ddr
)),
3516 pb
->eqs
[eq
].coef
[0]))
3518 /* There is no dependence. */
3519 *maybe_dependent
= false;
3526 /* Helper function, same as init_omega_for_ddr but specialized for
3527 data references A and B. */
3530 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3531 struct data_dependence_relation
*ddr
,
3532 omega_pb pb
, bool *maybe_dependent
)
3537 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3539 /* Insert an equality per subscript. */
3540 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3542 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3543 ddr
, pb
, maybe_dependent
))
3545 else if (*maybe_dependent
== false)
3547 /* There is no dependence. */
3548 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3553 /* Insert inequalities: constraints corresponding to the iteration
3554 domain, i.e. the loops surrounding the references "loop_x" and
3555 the distance variables "dx". The layout of the OMEGA
3556 representation is as follows:
3557 - coef[0] is the constant
3558 - coef[1..nb_loops] are the protected variables that will not be
3559 removed by the solver: the "dx"
3560 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3562 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3563 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3565 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3568 ineq
= omega_add_zero_geq (pb
, omega_black
);
3569 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3571 /* 0 <= loop_x + dx */
3572 ineq
= omega_add_zero_geq (pb
, omega_black
);
3573 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3574 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3578 /* loop_x <= nb_iters */
3579 ineq
= omega_add_zero_geq (pb
, omega_black
);
3580 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3581 pb
->geqs
[ineq
].coef
[0] = nbi
;
3583 /* loop_x + dx <= nb_iters */
3584 ineq
= omega_add_zero_geq (pb
, omega_black
);
3585 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3586 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3587 pb
->geqs
[ineq
].coef
[0] = nbi
;
3589 /* A step "dx" bigger than nb_iters is not feasible, so
3590 add "0 <= nb_iters + dx", */
3591 ineq
= omega_add_zero_geq (pb
, omega_black
);
3592 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3593 pb
->geqs
[ineq
].coef
[0] = nbi
;
3594 /* and "dx <= nb_iters". */
3595 ineq
= omega_add_zero_geq (pb
, omega_black
);
3596 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3597 pb
->geqs
[ineq
].coef
[0] = nbi
;
3601 omega_extract_distance_vectors (pb
, ddr
);
3606 /* Sets up the Omega dependence problem for the data dependence
3607 relation DDR. Returns false when the constraint system cannot be
3608 built, ie. when the test answers "don't know". Returns true
3609 otherwise, and when independence has been proved (using one of the
3610 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3611 set MAYBE_DEPENDENT to true.
3613 Example: for setting up the dependence system corresponding to the
3614 conflicting accesses
3619 | ... A[2*j, 2*(i + j)]
3623 the following constraints come from the iteration domain:
3630 where di, dj are the distance variables. The constraints
3631 representing the conflicting elements are:
3634 i + 1 = 2 * (i + di + j + dj)
3636 For asking that the resulting distance vector (di, dj) be
3637 lexicographically positive, we insert the constraint "di >= 0". If
3638 "di = 0" in the solution, we fix that component to zero, and we
3639 look at the inner loops: we set a new problem where all the outer
3640 loop distances are zero, and fix this inner component to be
3641 positive. When one of the components is positive, we save that
3642 distance, and set a new problem where the distance on this loop is
3643 zero, searching for other distances in the inner loops. Here is
3644 the classic example that illustrates that we have to set for each
3645 inner loop a new problem:
3653 we have to save two distances (1, 0) and (0, 1).
3655 Given two array references, refA and refB, we have to set the
3656 dependence problem twice, refA vs. refB and refB vs. refA, and we
3657 cannot do a single test, as refB might occur before refA in the
3658 inner loops, and the contrary when considering outer loops: ex.
3663 | T[{1,+,1}_2][{1,+,1}_1] // refA
3664 | T[{2,+,1}_2][{0,+,1}_1] // refB
3669 refB touches the elements in T before refA, and thus for the same
3670 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3671 but for successive loop_0 iterations, we have (1, -1, 1)
3673 The Omega solver expects the distance variables ("di" in the
3674 previous example) to come first in the constraint system (as
3675 variables to be protected, or "safe" variables), the constraint
3676 system is built using the following layout:
3678 "cst | distance vars | index vars".
3682 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3683 bool *maybe_dependent
)
3688 *maybe_dependent
= true;
3690 if (same_access_functions (ddr
))
3693 lambda_vector dir_v
;
3695 /* Save the 0 vector. */
3696 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3697 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3698 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3699 dir_v
[j
] = dir_equal
;
3700 save_dir_v (ddr
, dir_v
);
3702 /* Save the dependences carried by outer loops. */
3703 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3704 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3706 omega_free_problem (pb
);
3710 /* Omega expects the protected variables (those that have to be kept
3711 after elimination) to appear first in the constraint system.
3712 These variables are the distance variables. In the following
3713 initialization we declare NB_LOOPS safe variables, and the total
3714 number of variables for the constraint system is 2*NB_LOOPS. */
3715 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3716 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3718 omega_free_problem (pb
);
3720 /* Stop computation if not decidable, or no dependence. */
3721 if (res
== false || *maybe_dependent
== false)
3724 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3725 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3727 omega_free_problem (pb
);
3732 /* Return true when DDR contains the same information as that stored
3733 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3736 ddr_consistent_p (FILE *file
,
3737 struct data_dependence_relation
*ddr
,
3738 VEC (lambda_vector
, heap
) *dist_vects
,
3739 VEC (lambda_vector
, heap
) *dir_vects
)
3743 /* If dump_file is set, output there. */
3744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3747 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3749 lambda_vector b_dist_v
;
3750 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3751 VEC_length (lambda_vector
, dist_vects
),
3752 DDR_NUM_DIST_VECTS (ddr
));
3754 fprintf (file
, "Banerjee dist vectors:\n");
3755 FOR_EACH_VEC_ELT (lambda_vector
, dist_vects
, i
, b_dist_v
)
3756 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3758 fprintf (file
, "Omega dist vectors:\n");
3759 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3760 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3762 fprintf (file
, "data dependence relation:\n");
3763 dump_data_dependence_relation (file
, ddr
);
3765 fprintf (file
, ")\n");
3769 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3771 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3772 VEC_length (lambda_vector
, dir_vects
),
3773 DDR_NUM_DIR_VECTS (ddr
));
3777 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3779 lambda_vector a_dist_v
;
3780 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3782 /* Distance vectors are not ordered in the same way in the DDR
3783 and in the DIST_VECTS: search for a matching vector. */
3784 FOR_EACH_VEC_ELT (lambda_vector
, dist_vects
, j
, a_dist_v
)
3785 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3788 if (j
== VEC_length (lambda_vector
, dist_vects
))
3790 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3791 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3792 fprintf (file
, "not found in Omega dist vectors:\n");
3793 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3794 fprintf (file
, "data dependence relation:\n");
3795 dump_data_dependence_relation (file
, ddr
);
3796 fprintf (file
, ")\n");
3800 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3802 lambda_vector a_dir_v
;
3803 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3805 /* Direction vectors are not ordered in the same way in the DDR
3806 and in the DIR_VECTS: search for a matching vector. */
3807 FOR_EACH_VEC_ELT (lambda_vector
, dir_vects
, j
, a_dir_v
)
3808 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3811 if (j
== VEC_length (lambda_vector
, dist_vects
))
3813 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3814 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3815 fprintf (file
, "not found in Omega dir vectors:\n");
3816 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3817 fprintf (file
, "data dependence relation:\n");
3818 dump_data_dependence_relation (file
, ddr
);
3819 fprintf (file
, ")\n");
3826 /* This computes the affine dependence relation between A and B with
3827 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3828 independence between two accesses, while CHREC_DONT_KNOW is used
3829 for representing the unknown relation.
3831 Note that it is possible to stop the computation of the dependence
3832 relation the first time we detect a CHREC_KNOWN element for a given
3836 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3837 struct loop
*loop_nest
)
3839 struct data_reference
*dra
= DDR_A (ddr
);
3840 struct data_reference
*drb
= DDR_B (ddr
);
3842 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3844 fprintf (dump_file
, "(compute_affine_dependence\n");
3845 fprintf (dump_file
, " (stmt_a = \n");
3846 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, 0);
3847 fprintf (dump_file
, ")\n (stmt_b = \n");
3848 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, 0);
3849 fprintf (dump_file
, ")\n");
3852 /* Analyze only when the dependence relation is not yet known. */
3853 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
3854 && !DDR_SELF_REFERENCE (ddr
))
3856 dependence_stats
.num_dependence_tests
++;
3858 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3859 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3861 if (flag_check_data_deps
)
3863 /* Compute the dependences using the first algorithm. */
3864 subscript_dependence_tester (ddr
, loop_nest
);
3866 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3868 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3869 dump_data_dependence_relation (dump_file
, ddr
);
3872 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3874 bool maybe_dependent
;
3875 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3877 /* Save the result of the first DD analyzer. */
3878 dist_vects
= DDR_DIST_VECTS (ddr
);
3879 dir_vects
= DDR_DIR_VECTS (ddr
);
3881 /* Reset the information. */
3882 DDR_DIST_VECTS (ddr
) = NULL
;
3883 DDR_DIR_VECTS (ddr
) = NULL
;
3885 /* Compute the same information using Omega. */
3886 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3887 goto csys_dont_know
;
3889 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3891 fprintf (dump_file
, "Omega Analyzer\n");
3892 dump_data_dependence_relation (dump_file
, ddr
);
3895 /* Check that we get the same information. */
3896 if (maybe_dependent
)
3897 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3902 subscript_dependence_tester (ddr
, loop_nest
);
3905 /* As a last case, if the dependence cannot be determined, or if
3906 the dependence is considered too difficult to determine, answer
3911 dependence_stats
.num_dependence_undetermined
++;
3913 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3915 fprintf (dump_file
, "Data ref a:\n");
3916 dump_data_reference (dump_file
, dra
);
3917 fprintf (dump_file
, "Data ref b:\n");
3918 dump_data_reference (dump_file
, drb
);
3919 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3921 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3926 fprintf (dump_file
, ")\n");
3929 /* This computes the dependence relation for the same data
3930 reference into DDR. */
3933 compute_self_dependence (struct data_dependence_relation
*ddr
)
3936 struct subscript
*subscript
;
3938 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3941 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3944 if (SUB_CONFLICTS_IN_A (subscript
))
3945 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3946 if (SUB_CONFLICTS_IN_B (subscript
))
3947 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3949 /* The accessed index overlaps for each iteration. */
3950 SUB_CONFLICTS_IN_A (subscript
)
3951 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3952 SUB_CONFLICTS_IN_B (subscript
)
3953 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3954 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3957 /* The distance vector is the zero vector. */
3958 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3959 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3962 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3963 the data references in DATAREFS, in the LOOP_NEST. When
3964 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3968 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
3969 VEC (ddr_p
, heap
) **dependence_relations
,
3970 VEC (loop_p
, heap
) *loop_nest
,
3971 bool compute_self_and_rr
)
3973 struct data_dependence_relation
*ddr
;
3974 struct data_reference
*a
, *b
;
3977 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, a
)
3978 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
3979 if (DR_IS_WRITE (a
) || DR_IS_WRITE (b
) || compute_self_and_rr
)
3981 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
3982 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3984 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
3987 if (compute_self_and_rr
)
3988 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, a
)
3990 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
3991 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3992 compute_self_dependence (ddr
);
3996 /* Stores the locations of memory references in STMT to REFERENCES. Returns
3997 true if STMT clobbers memory, false otherwise. */
4000 get_references_in_stmt (gimple stmt
, VEC (data_ref_loc
, heap
) **references
)
4002 bool clobbers_memory
= false;
4005 enum gimple_code stmt_code
= gimple_code (stmt
);
4009 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4010 Calls have side-effects, except those to const or pure
4012 if ((stmt_code
== GIMPLE_CALL
4013 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4014 || (stmt_code
== GIMPLE_ASM
4015 && gimple_asm_volatile_p (stmt
)))
4016 clobbers_memory
= true;
4018 if (!gimple_vuse (stmt
))
4019 return clobbers_memory
;
4021 if (stmt_code
== GIMPLE_ASSIGN
)
4024 op0
= gimple_assign_lhs_ptr (stmt
);
4025 op1
= gimple_assign_rhs1_ptr (stmt
);
4028 || (REFERENCE_CLASS_P (*op1
)
4029 && (base
= get_base_address (*op1
))
4030 && TREE_CODE (base
) != SSA_NAME
))
4032 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4034 ref
->is_read
= true;
4038 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4040 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4042 ref
->is_read
= false;
4045 else if (stmt_code
== GIMPLE_CALL
)
4047 unsigned i
, n
= gimple_call_num_args (stmt
);
4049 for (i
= 0; i
< n
; i
++)
4051 op0
= gimple_call_arg_ptr (stmt
, i
);
4054 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4056 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4058 ref
->is_read
= true;
4063 return clobbers_memory
;
4066 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4067 reference, returns false, otherwise returns true. NEST is the outermost
4068 loop of the loop nest in which the references should be analyzed. */
4071 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4072 VEC (data_reference_p
, heap
) **datarefs
)
4075 VEC (data_ref_loc
, heap
) *references
;
4078 data_reference_p dr
;
4080 if (get_references_in_stmt (stmt
, &references
))
4082 VEC_free (data_ref_loc
, heap
, references
);
4086 FOR_EACH_VEC_ELT (data_ref_loc
, references
, i
, ref
)
4088 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4089 gcc_assert (dr
!= NULL
);
4091 /* FIXME -- data dependence analysis does not work correctly for objects
4092 with invariant addresses in loop nests. Let us fail here until the
4093 problem is fixed. */
4094 if (dr_address_invariant_p (dr
) && nest
)
4097 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4098 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
4103 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4105 VEC_free (data_ref_loc
, heap
, references
);
4109 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4110 reference, returns false, otherwise returns true. NEST is the outermost
4111 loop of the loop nest in which the references should be analyzed. */
4114 graphite_find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4115 VEC (data_reference_p
, heap
) **datarefs
)
4118 VEC (data_ref_loc
, heap
) *references
;
4121 data_reference_p dr
;
4123 if (get_references_in_stmt (stmt
, &references
))
4125 VEC_free (data_ref_loc
, heap
, references
);
4129 FOR_EACH_VEC_ELT (data_ref_loc
, references
, i
, ref
)
4131 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4132 gcc_assert (dr
!= NULL
);
4133 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4136 VEC_free (data_ref_loc
, heap
, references
);
4140 /* Search the data references in LOOP, and record the information into
4141 DATAREFS. Returns chrec_dont_know when failing to analyze a
4142 difficult case, returns NULL_TREE otherwise. */
4145 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4146 VEC (data_reference_p
, heap
) **datarefs
)
4148 gimple_stmt_iterator bsi
;
4150 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4152 gimple stmt
= gsi_stmt (bsi
);
4154 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4156 struct data_reference
*res
;
4157 res
= XCNEW (struct data_reference
);
4158 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4160 return chrec_dont_know
;
4167 /* Search the data references in LOOP, and record the information into
4168 DATAREFS. Returns chrec_dont_know when failing to analyze a
4169 difficult case, returns NULL_TREE otherwise.
4171 TODO: This function should be made smarter so that it can handle address
4172 arithmetic as if they were array accesses, etc. */
4175 find_data_references_in_loop (struct loop
*loop
,
4176 VEC (data_reference_p
, heap
) **datarefs
)
4178 basic_block bb
, *bbs
;
4181 bbs
= get_loop_body_in_dom_order (loop
);
4183 for (i
= 0; i
< loop
->num_nodes
; i
++)
4187 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4190 return chrec_dont_know
;
4198 /* Recursive helper function. */
4201 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4203 /* Inner loops of the nest should not contain siblings. Example:
4204 when there are two consecutive loops,
4215 the dependence relation cannot be captured by the distance
4220 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4222 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4226 /* Return false when the LOOP is not well nested. Otherwise return
4227 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4228 contain the loops from the outermost to the innermost, as they will
4229 appear in the classic distance vector. */
4232 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4234 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4236 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4240 /* Returns true when the data dependences have been computed, false otherwise.
4241 Given a loop nest LOOP, the following vectors are returned:
4242 DATAREFS is initialized to all the array elements contained in this loop,
4243 DEPENDENCE_RELATIONS contains the relations between the data references.
4244 Compute read-read and self relations if
4245 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4248 compute_data_dependences_for_loop (struct loop
*loop
,
4249 bool compute_self_and_read_read_dependences
,
4250 VEC (loop_p
, heap
) **loop_nest
,
4251 VEC (data_reference_p
, heap
) **datarefs
,
4252 VEC (ddr_p
, heap
) **dependence_relations
)
4256 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4258 /* If the loop nest is not well formed, or one of the data references
4259 is not computable, give up without spending time to compute other
4262 || !find_loop_nest (loop
, loop_nest
)
4263 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4265 struct data_dependence_relation
*ddr
;
4267 /* Insert a single relation into dependence_relations:
4269 ddr
= initialize_data_dependence_relation (NULL
, NULL
, *loop_nest
);
4270 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4274 compute_all_dependences (*datarefs
, dependence_relations
, *loop_nest
,
4275 compute_self_and_read_read_dependences
);
4277 if (dump_file
&& (dump_flags
& TDF_STATS
))
4279 fprintf (dump_file
, "Dependence tester statistics:\n");
4281 fprintf (dump_file
, "Number of dependence tests: %d\n",
4282 dependence_stats
.num_dependence_tests
);
4283 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4284 dependence_stats
.num_dependence_dependent
);
4285 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4286 dependence_stats
.num_dependence_independent
);
4287 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4288 dependence_stats
.num_dependence_undetermined
);
4290 fprintf (dump_file
, "Number of subscript tests: %d\n",
4291 dependence_stats
.num_subscript_tests
);
4292 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4293 dependence_stats
.num_subscript_undetermined
);
4294 fprintf (dump_file
, "Number of same subscript function: %d\n",
4295 dependence_stats
.num_same_subscript_function
);
4297 fprintf (dump_file
, "Number of ziv tests: %d\n",
4298 dependence_stats
.num_ziv
);
4299 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4300 dependence_stats
.num_ziv_dependent
);
4301 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4302 dependence_stats
.num_ziv_independent
);
4303 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4304 dependence_stats
.num_ziv_unimplemented
);
4306 fprintf (dump_file
, "Number of siv tests: %d\n",
4307 dependence_stats
.num_siv
);
4308 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4309 dependence_stats
.num_siv_dependent
);
4310 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4311 dependence_stats
.num_siv_independent
);
4312 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4313 dependence_stats
.num_siv_unimplemented
);
4315 fprintf (dump_file
, "Number of miv tests: %d\n",
4316 dependence_stats
.num_miv
);
4317 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4318 dependence_stats
.num_miv_dependent
);
4319 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4320 dependence_stats
.num_miv_independent
);
4321 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4322 dependence_stats
.num_miv_unimplemented
);
4328 /* Returns true when the data dependences for the basic block BB have been
4329 computed, false otherwise.
4330 DATAREFS is initialized to all the array elements contained in this basic
4331 block, DEPENDENCE_RELATIONS contains the relations between the data
4332 references. Compute read-read and self relations if
4333 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4335 compute_data_dependences_for_bb (basic_block bb
,
4336 bool compute_self_and_read_read_dependences
,
4337 VEC (data_reference_p
, heap
) **datarefs
,
4338 VEC (ddr_p
, heap
) **dependence_relations
)
4340 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4343 compute_all_dependences (*datarefs
, dependence_relations
, NULL
,
4344 compute_self_and_read_read_dependences
);
4348 /* Entry point (for testing only). Analyze all the data references
4349 and the dependence relations in LOOP.
4351 The data references are computed first.
4353 A relation on these nodes is represented by a complete graph. Some
4354 of the relations could be of no interest, thus the relations can be
4357 In the following function we compute all the relations. This is
4358 just a first implementation that is here for:
4359 - for showing how to ask for the dependence relations,
4360 - for the debugging the whole dependence graph,
4361 - for the dejagnu testcases and maintenance.
4363 It is possible to ask only for a part of the graph, avoiding to
4364 compute the whole dependence graph. The computed dependences are
4365 stored in a knowledge base (KB) such that later queries don't
4366 recompute the same information. The implementation of this KB is
4367 transparent to the optimizer, and thus the KB can be changed with a
4368 more efficient implementation, or the KB could be disabled. */
4370 analyze_all_data_dependences (struct loop
*loop
)
4373 int nb_data_refs
= 10;
4374 VEC (data_reference_p
, heap
) *datarefs
=
4375 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4376 VEC (ddr_p
, heap
) *dependence_relations
=
4377 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4378 VEC (loop_p
, heap
) *loop_nest
= VEC_alloc (loop_p
, heap
, 3);
4380 /* Compute DDs on the whole function. */
4381 compute_data_dependences_for_loop (loop
, false, &loop_nest
, &datarefs
,
4382 &dependence_relations
);
4386 dump_data_dependence_relations (dump_file
, dependence_relations
);
4387 fprintf (dump_file
, "\n\n");
4389 if (dump_flags
& TDF_DETAILS
)
4390 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4392 if (dump_flags
& TDF_STATS
)
4394 unsigned nb_top_relations
= 0;
4395 unsigned nb_bot_relations
= 0;
4396 unsigned nb_chrec_relations
= 0;
4397 struct data_dependence_relation
*ddr
;
4399 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4401 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4404 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4408 nb_chrec_relations
++;
4411 gather_stats_on_scev_database ();
4415 VEC_free (loop_p
, heap
, loop_nest
);
4416 free_dependence_relations (dependence_relations
);
4417 free_data_refs (datarefs
);
4420 /* Computes all the data dependences and check that the results of
4421 several analyzers are the same. */
4424 tree_check_data_deps (void)
4427 struct loop
*loop_nest
;
4429 FOR_EACH_LOOP (li
, loop_nest
, 0)
4430 analyze_all_data_dependences (loop_nest
);
4433 /* Free the memory used by a data dependence relation DDR. */
4436 free_dependence_relation (struct data_dependence_relation
*ddr
)
4441 if (DDR_SUBSCRIPTS (ddr
))
4442 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4443 if (DDR_DIST_VECTS (ddr
))
4444 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4445 if (DDR_DIR_VECTS (ddr
))
4446 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4451 /* Free the memory used by the data dependence relations from
4452 DEPENDENCE_RELATIONS. */
4455 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4458 struct data_dependence_relation
*ddr
;
4460 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4462 free_dependence_relation (ddr
);
4464 VEC_free (ddr_p
, heap
, dependence_relations
);
4467 /* Free the memory used by the data references from DATAREFS. */
4470 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4473 struct data_reference
*dr
;
4475 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
4477 VEC_free (data_reference_p
, heap
, datarefs
);
4482 /* Dump vertex I in RDG to FILE. */
4485 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4487 struct vertex
*v
= &(rdg
->vertices
[i
]);
4488 struct graph_edge
*e
;
4490 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4491 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4492 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4495 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4496 fprintf (file
, " %d", e
->src
);
4498 fprintf (file
, ") (out:");
4501 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4502 fprintf (file
, " %d", e
->dest
);
4504 fprintf (file
, ")\n");
4505 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4506 fprintf (file
, ")\n");
4509 /* Call dump_rdg_vertex on stderr. */
4512 debug_rdg_vertex (struct graph
*rdg
, int i
)
4514 dump_rdg_vertex (stderr
, rdg
, i
);
4517 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4518 dumped vertices to that bitmap. */
4520 void dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4524 fprintf (file
, "(%d\n", c
);
4526 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4527 if (rdg
->vertices
[i
].component
== c
)
4530 bitmap_set_bit (dumped
, i
);
4532 dump_rdg_vertex (file
, rdg
, i
);
4535 fprintf (file
, ")\n");
4538 /* Call dump_rdg_vertex on stderr. */
4541 debug_rdg_component (struct graph
*rdg
, int c
)
4543 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4546 /* Dump the reduced dependence graph RDG to FILE. */
4549 dump_rdg (FILE *file
, struct graph
*rdg
)
4552 bitmap dumped
= BITMAP_ALLOC (NULL
);
4554 fprintf (file
, "(rdg\n");
4556 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4557 if (!bitmap_bit_p (dumped
, i
))
4558 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4560 fprintf (file
, ")\n");
4561 BITMAP_FREE (dumped
);
4564 /* Call dump_rdg on stderr. */
4567 debug_rdg (struct graph
*rdg
)
4569 dump_rdg (stderr
, rdg
);
4573 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
4577 fprintf (file
, "digraph RDG {\n");
4579 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4581 struct vertex
*v
= &(rdg
->vertices
[i
]);
4582 struct graph_edge
*e
;
4584 /* Highlight reads from memory. */
4585 if (RDG_MEM_READS_STMT (rdg
, i
))
4586 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
4588 /* Highlight stores to memory. */
4589 if (RDG_MEM_WRITE_STMT (rdg
, i
))
4590 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
4593 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4594 switch (RDGE_TYPE (e
))
4597 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
4601 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
4605 /* These are the most common dependences: don't print these. */
4606 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
4610 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
4618 fprintf (file
, "}\n\n");
4621 /* Display the Reduced Dependence Graph using dotty. */
4622 extern void dot_rdg (struct graph
*);
4625 dot_rdg (struct graph
*rdg
)
4627 /* When debugging, enable the following code. This cannot be used
4628 in production compilers because it calls "system". */
4630 FILE *file
= fopen ("/tmp/rdg.dot", "w");
4631 gcc_assert (file
!= NULL
);
4633 dot_rdg_1 (file
, rdg
);
4636 system ("dotty /tmp/rdg.dot &");
4638 dot_rdg_1 (stderr
, rdg
);
4642 /* This structure is used for recording the mapping statement index in
4645 struct GTY(()) rdg_vertex_info
4651 /* Returns the index of STMT in RDG. */
4654 rdg_vertex_for_stmt (struct graph
*rdg
, gimple stmt
)
4656 struct rdg_vertex_info rvi
, *slot
;
4659 slot
= (struct rdg_vertex_info
*) htab_find (rdg
->indices
, &rvi
);
4667 /* Creates an edge in RDG for each distance vector from DDR. The
4668 order that we keep track of in the RDG is the order in which
4669 statements have to be executed. */
4672 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4674 struct graph_edge
*e
;
4676 data_reference_p dra
= DDR_A (ddr
);
4677 data_reference_p drb
= DDR_B (ddr
);
4678 unsigned level
= ddr_dependence_level (ddr
);
4680 /* For non scalar dependences, when the dependence is REVERSED,
4681 statement B has to be executed before statement A. */
4683 && !DDR_REVERSED_P (ddr
))
4685 data_reference_p tmp
= dra
;
4690 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4691 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4693 if (va
< 0 || vb
< 0)
4696 e
= add_edge (rdg
, va
, vb
);
4697 e
->data
= XNEW (struct rdg_edge
);
4699 RDGE_LEVEL (e
) = level
;
4700 RDGE_RELATION (e
) = ddr
;
4702 /* Determines the type of the data dependence. */
4703 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4704 RDGE_TYPE (e
) = input_dd
;
4705 else if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
4706 RDGE_TYPE (e
) = output_dd
;
4707 else if (DR_IS_WRITE (dra
) && DR_IS_READ (drb
))
4708 RDGE_TYPE (e
) = flow_dd
;
4709 else if (DR_IS_READ (dra
) && DR_IS_WRITE (drb
))
4710 RDGE_TYPE (e
) = anti_dd
;
4713 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4714 the index of DEF in RDG. */
4717 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4719 use_operand_p imm_use_p
;
4720 imm_use_iterator iterator
;
4722 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4724 struct graph_edge
*e
;
4725 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4730 e
= add_edge (rdg
, idef
, use
);
4731 e
->data
= XNEW (struct rdg_edge
);
4732 RDGE_TYPE (e
) = flow_dd
;
4733 RDGE_RELATION (e
) = NULL
;
4737 /* Creates the edges of the reduced dependence graph RDG. */
4740 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4743 struct data_dependence_relation
*ddr
;
4744 def_operand_p def_p
;
4747 FOR_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
4748 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4749 create_rdg_edge_for_ddr (rdg
, ddr
);
4751 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4752 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4754 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4757 /* Build the vertices of the reduced dependence graph RDG. */
4760 create_rdg_vertices (struct graph
*rdg
, VEC (gimple
, heap
) *stmts
)
4765 FOR_EACH_VEC_ELT (gimple
, stmts
, i
, stmt
)
4767 VEC (data_ref_loc
, heap
) *references
;
4769 struct vertex
*v
= &(rdg
->vertices
[i
]);
4770 struct rdg_vertex_info
*rvi
= XNEW (struct rdg_vertex_info
);
4771 struct rdg_vertex_info
**slot
;
4775 slot
= (struct rdg_vertex_info
**) htab_find_slot (rdg
->indices
, rvi
, INSERT
);
4782 v
->data
= XNEW (struct rdg_vertex
);
4783 RDG_STMT (rdg
, i
) = stmt
;
4785 RDG_MEM_WRITE_STMT (rdg
, i
) = false;
4786 RDG_MEM_READS_STMT (rdg
, i
) = false;
4787 if (gimple_code (stmt
) == GIMPLE_PHI
)
4790 get_references_in_stmt (stmt
, &references
);
4791 FOR_EACH_VEC_ELT (data_ref_loc
, references
, j
, ref
)
4793 RDG_MEM_WRITE_STMT (rdg
, i
) = true;
4795 RDG_MEM_READS_STMT (rdg
, i
) = true;
4797 VEC_free (data_ref_loc
, heap
, references
);
4801 /* Initialize STMTS with all the statements of LOOP. When
4802 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4803 which we discover statements is important as
4804 generate_loops_for_partition is using the same traversal for
4805 identifying statements. */
4808 stmts_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4811 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4813 for (i
= 0; i
< loop
->num_nodes
; i
++)
4815 basic_block bb
= bbs
[i
];
4816 gimple_stmt_iterator bsi
;
4819 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4820 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4822 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4824 stmt
= gsi_stmt (bsi
);
4825 if (gimple_code (stmt
) != GIMPLE_LABEL
)
4826 VEC_safe_push (gimple
, heap
, *stmts
, stmt
);
4833 /* Returns true when all the dependences are computable. */
4836 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
4841 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4842 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4848 /* Computes a hash function for element ELT. */
4851 hash_stmt_vertex_info (const void *elt
)
4853 const struct rdg_vertex_info
*const rvi
=
4854 (const struct rdg_vertex_info
*) elt
;
4855 gimple stmt
= rvi
->stmt
;
4857 return htab_hash_pointer (stmt
);
4860 /* Compares database elements E1 and E2. */
4863 eq_stmt_vertex_info (const void *e1
, const void *e2
)
4865 const struct rdg_vertex_info
*elt1
= (const struct rdg_vertex_info
*) e1
;
4866 const struct rdg_vertex_info
*elt2
= (const struct rdg_vertex_info
*) e2
;
4868 return elt1
->stmt
== elt2
->stmt
;
4871 /* Free the element E. */
4874 hash_stmt_vertex_del (void *e
)
4879 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4880 statement of the loop nest, and one edge per data dependence or
4881 scalar dependence. */
4884 build_empty_rdg (int n_stmts
)
4886 int nb_data_refs
= 10;
4887 struct graph
*rdg
= new_graph (n_stmts
);
4889 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4890 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4894 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4895 statement of the loop nest, and one edge per data dependence or
4896 scalar dependence. */
4899 build_rdg (struct loop
*loop
,
4900 VEC (loop_p
, heap
) **loop_nest
,
4901 VEC (ddr_p
, heap
) **dependence_relations
,
4902 VEC (data_reference_p
, heap
) **datarefs
)
4904 struct graph
*rdg
= NULL
;
4905 VEC (gimple
, heap
) *stmts
= VEC_alloc (gimple
, heap
, 10);
4907 compute_data_dependences_for_loop (loop
, false, loop_nest
, datarefs
,
4908 dependence_relations
);
4910 if (known_dependences_p (*dependence_relations
))
4912 stmts_from_loop (loop
, &stmts
);
4913 rdg
= build_empty_rdg (VEC_length (gimple
, stmts
));
4914 create_rdg_vertices (rdg
, stmts
);
4915 create_rdg_edges (rdg
, *dependence_relations
);
4918 VEC_free (gimple
, heap
, stmts
);
4922 /* Free the reduced dependence graph RDG. */
4925 free_rdg (struct graph
*rdg
)
4929 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4931 struct vertex
*v
= &(rdg
->vertices
[i
]);
4932 struct graph_edge
*e
;
4934 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4942 htab_delete (rdg
->indices
);
4946 /* Initialize STMTS with all the statements of LOOP that contain a
4950 stores_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4953 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4955 for (i
= 0; i
< loop
->num_nodes
; i
++)
4957 basic_block bb
= bbs
[i
];
4958 gimple_stmt_iterator bsi
;
4960 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4961 if (gimple_vdef (gsi_stmt (bsi
)))
4962 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4968 /* Returns true when the statement at STMT is of the form "A[i] = 0"
4969 that contains a data reference on its LHS with a stride of the same
4970 size as its unit type. */
4973 stmt_with_adjacent_zero_store_dr_p (gimple stmt
)
4977 struct data_reference
*dr
;
4980 || !gimple_vdef (stmt
)
4981 || !is_gimple_assign (stmt
)
4982 || !gimple_assign_single_p (stmt
)
4983 || !(op1
= gimple_assign_rhs1 (stmt
))
4984 || !(integer_zerop (op1
) || real_zerop (op1
)))
4987 dr
= XCNEW (struct data_reference
);
4988 op0
= gimple_assign_lhs (stmt
);
4990 DR_STMT (dr
) = stmt
;
4993 res
= dr_analyze_innermost (dr
)
4994 && stride_of_unit_type_p (DR_STEP (dr
), TREE_TYPE (op0
));
5000 /* Initialize STMTS with all the statements of LOOP that contain a
5001 store to memory of the form "A[i] = 0". */
5004 stores_zero_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
5008 gimple_stmt_iterator si
;
5010 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
5012 for (i
= 0; i
< loop
->num_nodes
; i
++)
5013 for (bb
= bbs
[i
], si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
5014 if ((stmt
= gsi_stmt (si
))
5015 && stmt_with_adjacent_zero_store_dr_p (stmt
))
5016 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (si
));
5021 /* For a data reference REF, return the declaration of its base
5022 address or NULL_TREE if the base is not determined. */
5025 ref_base_address (gimple stmt
, data_ref_loc
*ref
)
5027 tree base
= NULL_TREE
;
5029 struct data_reference
*dr
= XCNEW (struct data_reference
);
5031 DR_STMT (dr
) = stmt
;
5032 DR_REF (dr
) = *ref
->pos
;
5033 dr_analyze_innermost (dr
);
5034 base_address
= DR_BASE_ADDRESS (dr
);
5039 switch (TREE_CODE (base_address
))
5042 base
= TREE_OPERAND (base_address
, 0);
5046 base
= base_address
;
5055 /* Determines whether the statement from vertex V of the RDG has a
5056 definition used outside the loop that contains this statement. */
5059 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
5061 gimple stmt
= RDG_STMT (rdg
, v
);
5062 struct loop
*loop
= loop_containing_stmt (stmt
);
5063 use_operand_p imm_use_p
;
5064 imm_use_iterator iterator
;
5066 def_operand_p def_p
;
5071 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
5073 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
5075 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)
5083 /* Determines whether statements S1 and S2 access to similar memory
5084 locations. Two memory accesses are considered similar when they
5085 have the same base address declaration, i.e. when their
5086 ref_base_address is the same. */
5089 have_similar_memory_accesses (gimple s1
, gimple s2
)
5093 VEC (data_ref_loc
, heap
) *refs1
, *refs2
;
5094 data_ref_loc
*ref1
, *ref2
;
5096 get_references_in_stmt (s1
, &refs1
);
5097 get_references_in_stmt (s2
, &refs2
);
5099 FOR_EACH_VEC_ELT (data_ref_loc
, refs1
, i
, ref1
)
5101 tree base1
= ref_base_address (s1
, ref1
);
5104 FOR_EACH_VEC_ELT (data_ref_loc
, refs2
, j
, ref2
)
5105 if (base1
== ref_base_address (s2
, ref2
))
5113 VEC_free (data_ref_loc
, heap
, refs1
);
5114 VEC_free (data_ref_loc
, heap
, refs2
);
5118 /* Helper function for the hashtab. */
5121 have_similar_memory_accesses_1 (const void *s1
, const void *s2
)
5123 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple
) s1
),
5124 CONST_CAST_GIMPLE ((const_gimple
) s2
));
5127 /* Helper function for the hashtab. */
5130 ref_base_address_1 (const void *s
)
5132 gimple stmt
= CONST_CAST_GIMPLE ((const_gimple
) s
);
5134 VEC (data_ref_loc
, heap
) *refs
;
5138 get_references_in_stmt (stmt
, &refs
);
5140 FOR_EACH_VEC_ELT (data_ref_loc
, refs
, i
, ref
)
5143 res
= htab_hash_pointer (ref_base_address (stmt
, ref
));
5147 VEC_free (data_ref_loc
, heap
, refs
);
5151 /* Try to remove duplicated write data references from STMTS. */
5154 remove_similar_memory_refs (VEC (gimple
, heap
) **stmts
)
5158 htab_t seen
= htab_create (VEC_length (gimple
, *stmts
), ref_base_address_1
,
5159 have_similar_memory_accesses_1
, NULL
);
5161 for (i
= 0; VEC_iterate (gimple
, *stmts
, i
, stmt
); )
5165 slot
= htab_find_slot (seen
, stmt
, INSERT
);
5168 VEC_ordered_remove (gimple
, *stmts
, i
);
5171 *slot
= (void *) stmt
;
5179 /* Returns the index of PARAMETER in the parameters vector of the
5180 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5183 access_matrix_get_index_for_parameter (tree parameter
,
5184 struct access_matrix
*access_matrix
)
5187 VEC (tree
,heap
) *lambda_parameters
= AM_PARAMETERS (access_matrix
);
5188 tree lambda_parameter
;
5190 FOR_EACH_VEC_ELT (tree
, lambda_parameters
, i
, lambda_parameter
)
5191 if (lambda_parameter
== parameter
)
5192 return i
+ AM_NB_INDUCTION_VARS (access_matrix
);