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
))
2658 dependence_stats
.num_same_subscript_function
++;
2659 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2660 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2661 *last_conflicts
= chrec_dont_know
;
2664 /* If they aren't the same, and aren't affine, we can't do anything
2666 else if ((chrec_contains_symbols (chrec_a
)
2667 || chrec_contains_symbols (chrec_b
))
2668 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2669 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2671 dependence_stats
.num_subscript_undetermined
++;
2672 *overlap_iterations_a
= conflict_fn_not_known ();
2673 *overlap_iterations_b
= conflict_fn_not_known ();
2676 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2677 analyze_ziv_subscript (chrec_a
, chrec_b
,
2678 overlap_iterations_a
, overlap_iterations_b
,
2681 else if (siv_subscript_p (chrec_a
, chrec_b
))
2682 analyze_siv_subscript (chrec_a
, chrec_b
,
2683 overlap_iterations_a
, overlap_iterations_b
,
2684 last_conflicts
, lnn
);
2687 analyze_miv_subscript (chrec_a
, chrec_b
,
2688 overlap_iterations_a
, overlap_iterations_b
,
2689 last_conflicts
, loop_nest
);
2691 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2693 fprintf (dump_file
, " (overlap_iterations_a = ");
2694 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2695 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2696 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2697 fprintf (dump_file
, ")\n");
2698 fprintf (dump_file
, ")\n");
2702 /* Helper function for uniquely inserting distance vectors. */
2705 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2710 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
)
2711 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2714 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2717 /* Helper function for uniquely inserting direction vectors. */
2720 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2725 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
)
2726 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2729 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2732 /* Add a distance of 1 on all the loops outer than INDEX. If we
2733 haven't yet determined a distance for this outer loop, push a new
2734 distance vector composed of the previous distance, and a distance
2735 of 1 for this outer loop. Example:
2743 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2744 save (0, 1), then we have to save (1, 0). */
2747 add_outer_distances (struct data_dependence_relation
*ddr
,
2748 lambda_vector dist_v
, int index
)
2750 /* For each outer loop where init_v is not set, the accesses are
2751 in dependence of distance 1 in the loop. */
2752 while (--index
>= 0)
2754 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2755 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
2757 save_dist_v (ddr
, save_v
);
2761 /* Return false when fail to represent the data dependence as a
2762 distance vector. INIT_B is set to true when a component has been
2763 added to the distance vector DIST_V. INDEX_CARRY is then set to
2764 the index in DIST_V that carries the dependence. */
2767 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
2768 struct data_reference
*ddr_a
,
2769 struct data_reference
*ddr_b
,
2770 lambda_vector dist_v
, bool *init_b
,
2774 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2776 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2778 tree access_fn_a
, access_fn_b
;
2779 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2781 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2783 non_affine_dependence_relation (ddr
);
2787 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
2788 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
2790 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
2791 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
2794 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
2795 DDR_LOOP_NEST (ddr
));
2796 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
2797 DDR_LOOP_NEST (ddr
));
2799 /* The dependence is carried by the outermost loop. Example:
2806 In this case, the dependence is carried by loop_1. */
2807 index
= index_a
< index_b
? index_a
: index_b
;
2808 *index_carry
= MIN (index
, *index_carry
);
2810 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2812 non_affine_dependence_relation (ddr
);
2816 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2818 /* This is the subscript coupling test. If we have already
2819 recorded a distance for this loop (a distance coming from
2820 another subscript), it should be the same. For example,
2821 in the following code, there is no dependence:
2828 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
2830 finalize_ddr_dependent (ddr
, chrec_known
);
2834 dist_v
[index
] = dist
;
2838 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
2840 /* This can be for example an affine vs. constant dependence
2841 (T[i] vs. T[3]) that is not an affine dependence and is
2842 not representable as a distance vector. */
2843 non_affine_dependence_relation (ddr
);
2851 /* Return true when the DDR contains only constant access functions. */
2854 constant_access_functions (const struct data_dependence_relation
*ddr
)
2858 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2859 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
2860 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
2866 /* Helper function for the case where DDR_A and DDR_B are the same
2867 multivariate access function with a constant step. For an example
2871 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
2874 tree c_1
= CHREC_LEFT (c_2
);
2875 tree c_0
= CHREC_LEFT (c_1
);
2876 lambda_vector dist_v
;
2879 /* Polynomials with more than 2 variables are not handled yet. When
2880 the evolution steps are parameters, it is not possible to
2881 represent the dependence using classical distance vectors. */
2882 if (TREE_CODE (c_0
) != INTEGER_CST
2883 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
2884 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
2886 DDR_AFFINE_P (ddr
) = false;
2890 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
2891 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
2893 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2894 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2895 v1
= int_cst_value (CHREC_RIGHT (c_1
));
2896 v2
= int_cst_value (CHREC_RIGHT (c_2
));
2909 save_dist_v (ddr
, dist_v
);
2911 add_outer_distances (ddr
, dist_v
, x_1
);
2914 /* Helper function for the case where DDR_A and DDR_B are the same
2915 access functions. */
2918 add_other_self_distances (struct data_dependence_relation
*ddr
)
2920 lambda_vector dist_v
;
2922 int index_carry
= DDR_NB_LOOPS (ddr
);
2924 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2926 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
2928 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
2930 if (!evolution_function_is_univariate_p (access_fun
))
2932 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
2934 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
2938 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
2940 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
2941 add_multivariate_self_dist (ddr
, access_fun
);
2943 /* The evolution step is not constant: it varies in
2944 the outer loop, so this cannot be represented by a
2945 distance vector. For example in pr34635.c the
2946 evolution is {0, +, {0, +, 4}_1}_2. */
2947 DDR_AFFINE_P (ddr
) = false;
2952 index_carry
= MIN (index_carry
,
2953 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
2954 DDR_LOOP_NEST (ddr
)));
2958 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2959 add_outer_distances (ddr
, dist_v
, index_carry
);
2963 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
2965 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
2967 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
2968 save_dist_v (ddr
, dist_v
);
2971 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2972 is the case for example when access functions are the same and
2973 equal to a constant, as in:
2980 in which case the distance vectors are (0) and (1). */
2983 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
2987 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2989 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
2990 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
2991 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
2993 for (j
= 0; j
< ca
->n
; j
++)
2994 if (affine_function_zero_p (ca
->fns
[j
]))
2996 insert_innermost_unit_dist_vector (ddr
);
3000 for (j
= 0; j
< cb
->n
; j
++)
3001 if (affine_function_zero_p (cb
->fns
[j
]))
3003 insert_innermost_unit_dist_vector (ddr
);
3009 /* Compute the classic per loop distance vector. DDR is the data
3010 dependence relation to build a vector from. Return false when fail
3011 to represent the data dependence as a distance vector. */
3014 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3015 struct loop
*loop_nest
)
3017 bool init_b
= false;
3018 int index_carry
= DDR_NB_LOOPS (ddr
);
3019 lambda_vector dist_v
;
3021 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3024 if (same_access_functions (ddr
))
3026 /* Save the 0 vector. */
3027 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3028 save_dist_v (ddr
, dist_v
);
3030 if (constant_access_functions (ddr
))
3031 add_distance_for_zero_overlaps (ddr
);
3033 if (DDR_NB_LOOPS (ddr
) > 1)
3034 add_other_self_distances (ddr
);
3039 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3040 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3041 dist_v
, &init_b
, &index_carry
))
3044 /* Save the distance vector if we initialized one. */
3047 /* Verify a basic constraint: classic distance vectors should
3048 always be lexicographically positive.
3050 Data references are collected in the order of execution of
3051 the program, thus for the following loop
3053 | for (i = 1; i < 100; i++)
3054 | for (j = 1; j < 100; j++)
3056 | t = T[j+1][i-1]; // A
3057 | T[j][i] = t + 2; // B
3060 references are collected following the direction of the wind:
3061 A then B. The data dependence tests are performed also
3062 following this order, such that we're looking at the distance
3063 separating the elements accessed by A from the elements later
3064 accessed by B. But in this example, the distance returned by
3065 test_dep (A, B) is lexicographically negative (-1, 1), that
3066 means that the access A occurs later than B with respect to
3067 the outer loop, ie. we're actually looking upwind. In this
3068 case we solve test_dep (B, A) looking downwind to the
3069 lexicographically positive solution, that returns the
3070 distance vector (1, -1). */
3071 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3073 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3074 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3077 compute_subscript_distance (ddr
);
3078 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3079 save_v
, &init_b
, &index_carry
))
3081 save_dist_v (ddr
, save_v
);
3082 DDR_REVERSED_P (ddr
) = true;
3084 /* In this case there is a dependence forward for all the
3087 | for (k = 1; k < 100; k++)
3088 | for (i = 1; i < 100; i++)
3089 | for (j = 1; j < 100; j++)
3091 | t = T[j+1][i-1]; // A
3092 | T[j][i] = t + 2; // B
3100 if (DDR_NB_LOOPS (ddr
) > 1)
3102 add_outer_distances (ddr
, save_v
, index_carry
);
3103 add_outer_distances (ddr
, dist_v
, index_carry
);
3108 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3109 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3111 if (DDR_NB_LOOPS (ddr
) > 1)
3113 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3115 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3116 DDR_A (ddr
), loop_nest
))
3118 compute_subscript_distance (ddr
);
3119 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3120 opposite_v
, &init_b
,
3124 save_dist_v (ddr
, save_v
);
3125 add_outer_distances (ddr
, dist_v
, index_carry
);
3126 add_outer_distances (ddr
, opposite_v
, index_carry
);
3129 save_dist_v (ddr
, save_v
);
3134 /* There is a distance of 1 on all the outer loops: Example:
3135 there is a dependence of distance 1 on loop_1 for the array A.
3141 add_outer_distances (ddr
, dist_v
,
3142 lambda_vector_first_nz (dist_v
,
3143 DDR_NB_LOOPS (ddr
), 0));
3146 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3150 fprintf (dump_file
, "(build_classic_dist_vector\n");
3151 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3153 fprintf (dump_file
, " dist_vector = (");
3154 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3155 DDR_NB_LOOPS (ddr
));
3156 fprintf (dump_file
, " )\n");
3158 fprintf (dump_file
, ")\n");
3164 /* Return the direction for a given distance.
3165 FIXME: Computing dir this way is suboptimal, since dir can catch
3166 cases that dist is unable to represent. */
3168 static inline enum data_dependence_direction
3169 dir_from_dist (int dist
)
3172 return dir_positive
;
3174 return dir_negative
;
3179 /* Compute the classic per loop direction vector. DDR is the data
3180 dependence relation to build a vector from. */
3183 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3186 lambda_vector dist_v
;
3188 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
)
3190 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3192 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3193 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3195 save_dir_v (ddr
, dir_v
);
3199 /* Helper function. Returns true when there is a dependence between
3200 data references DRA and DRB. */
3203 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3204 struct data_reference
*dra
,
3205 struct data_reference
*drb
,
3206 struct loop
*loop_nest
)
3209 tree last_conflicts
;
3210 struct subscript
*subscript
;
3212 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3215 conflict_function
*overlaps_a
, *overlaps_b
;
3217 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3218 DR_ACCESS_FN (drb
, i
),
3219 &overlaps_a
, &overlaps_b
,
3220 &last_conflicts
, loop_nest
);
3222 if (CF_NOT_KNOWN_P (overlaps_a
)
3223 || CF_NOT_KNOWN_P (overlaps_b
))
3225 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3226 dependence_stats
.num_dependence_undetermined
++;
3227 free_conflict_function (overlaps_a
);
3228 free_conflict_function (overlaps_b
);
3232 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3233 || CF_NO_DEPENDENCE_P (overlaps_b
))
3235 finalize_ddr_dependent (ddr
, chrec_known
);
3236 dependence_stats
.num_dependence_independent
++;
3237 free_conflict_function (overlaps_a
);
3238 free_conflict_function (overlaps_b
);
3244 if (SUB_CONFLICTS_IN_A (subscript
))
3245 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3246 if (SUB_CONFLICTS_IN_B (subscript
))
3247 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3249 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3250 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3251 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3258 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3261 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3262 struct loop
*loop_nest
)
3265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3266 fprintf (dump_file
, "(subscript_dependence_tester \n");
3268 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3269 dependence_stats
.num_dependence_dependent
++;
3271 compute_subscript_distance (ddr
);
3272 if (build_classic_dist_vector (ddr
, loop_nest
))
3273 build_classic_dir_vector (ddr
);
3275 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3276 fprintf (dump_file
, ")\n");
3279 /* Returns true when all the access functions of A are affine or
3280 constant with respect to LOOP_NEST. */
3283 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3284 const struct loop
*loop_nest
)
3287 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3290 FOR_EACH_VEC_ELT (tree
, fns
, i
, t
)
3291 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3292 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3298 /* Initializes an equation for an OMEGA problem using the information
3299 contained in the ACCESS_FUN. Returns true when the operation
3302 PB is the omega constraint system.
3303 EQ is the number of the equation to be initialized.
3304 OFFSET is used for shifting the variables names in the constraints:
3305 a constrain is composed of 2 * the number of variables surrounding
3306 dependence accesses. OFFSET is set either to 0 for the first n variables,
3307 then it is set to n.
3308 ACCESS_FUN is expected to be an affine chrec. */
3311 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3312 unsigned int offset
, tree access_fun
,
3313 struct data_dependence_relation
*ddr
)
3315 switch (TREE_CODE (access_fun
))
3317 case POLYNOMIAL_CHREC
:
3319 tree left
= CHREC_LEFT (access_fun
);
3320 tree right
= CHREC_RIGHT (access_fun
);
3321 int var
= CHREC_VARIABLE (access_fun
);
3324 if (TREE_CODE (right
) != INTEGER_CST
)
3327 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3328 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3330 /* Compute the innermost loop index. */
3331 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3334 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3335 += int_cst_value (right
);
3337 switch (TREE_CODE (left
))
3339 case POLYNOMIAL_CHREC
:
3340 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3343 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3352 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3360 /* As explained in the comments preceding init_omega_for_ddr, we have
3361 to set up a system for each loop level, setting outer loops
3362 variation to zero, and current loop variation to positive or zero.
3363 Save each lexico positive distance vector. */
3366 omega_extract_distance_vectors (omega_pb pb
,
3367 struct data_dependence_relation
*ddr
)
3371 struct loop
*loopi
, *loopj
;
3372 enum omega_result res
;
3374 /* Set a new problem for each loop in the nest. The basis is the
3375 problem that we have initialized until now. On top of this we
3376 add new constraints. */
3377 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3378 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3381 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3382 DDR_NB_LOOPS (ddr
));
3384 omega_copy_problem (copy
, pb
);
3386 /* For all the outer loops "loop_j", add "dj = 0". */
3388 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3390 eq
= omega_add_zero_eq (copy
, omega_black
);
3391 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3394 /* For "loop_i", add "0 <= di". */
3395 geq
= omega_add_zero_geq (copy
, omega_black
);
3396 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3398 /* Reduce the constraint system, and test that the current
3399 problem is feasible. */
3400 res
= omega_simplify_problem (copy
);
3401 if (res
== omega_false
3402 || res
== omega_unknown
3403 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3406 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3407 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3409 dist
= copy
->subs
[eq
].coef
[0];
3415 /* Reinitialize problem... */
3416 omega_copy_problem (copy
, pb
);
3418 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3420 eq
= omega_add_zero_eq (copy
, omega_black
);
3421 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3424 /* ..., but this time "di = 1". */
3425 eq
= omega_add_zero_eq (copy
, omega_black
);
3426 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3427 copy
->eqs
[eq
].coef
[0] = -1;
3429 res
= omega_simplify_problem (copy
);
3430 if (res
== omega_false
3431 || res
== omega_unknown
3432 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3435 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3436 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3438 dist
= copy
->subs
[eq
].coef
[0];
3444 /* Save the lexicographically positive distance vector. */
3447 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3448 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3452 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3453 if (copy
->subs
[eq
].key
> 0)
3455 dist
= copy
->subs
[eq
].coef
[0];
3456 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3459 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3460 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3462 save_dist_v (ddr
, dist_v
);
3463 save_dir_v (ddr
, dir_v
);
3467 omega_free_problem (copy
);
3471 /* This is called for each subscript of a tuple of data references:
3472 insert an equality for representing the conflicts. */
3475 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3476 struct data_dependence_relation
*ddr
,
3477 omega_pb pb
, bool *maybe_dependent
)
3480 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3481 TREE_TYPE (access_fun_b
));
3482 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3483 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3484 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3486 /* When the fun_a - fun_b is not constant, the dependence is not
3487 captured by the classic distance vector representation. */
3488 if (TREE_CODE (difference
) != INTEGER_CST
)
3492 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3494 /* There is no dependence. */
3495 *maybe_dependent
= false;
3499 fun_b
= chrec_fold_multiply (type
, fun_b
, integer_minus_one_node
);
3501 eq
= omega_add_zero_eq (pb
, omega_black
);
3502 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3503 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3504 /* There is probably a dependence, but the system of
3505 constraints cannot be built: answer "don't know". */
3509 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3510 && !int_divides_p (lambda_vector_gcd
3511 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3512 2 * DDR_NB_LOOPS (ddr
)),
3513 pb
->eqs
[eq
].coef
[0]))
3515 /* There is no dependence. */
3516 *maybe_dependent
= false;
3523 /* Helper function, same as init_omega_for_ddr but specialized for
3524 data references A and B. */
3527 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3528 struct data_dependence_relation
*ddr
,
3529 omega_pb pb
, bool *maybe_dependent
)
3534 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3536 /* Insert an equality per subscript. */
3537 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3539 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3540 ddr
, pb
, maybe_dependent
))
3542 else if (*maybe_dependent
== false)
3544 /* There is no dependence. */
3545 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3550 /* Insert inequalities: constraints corresponding to the iteration
3551 domain, i.e. the loops surrounding the references "loop_x" and
3552 the distance variables "dx". The layout of the OMEGA
3553 representation is as follows:
3554 - coef[0] is the constant
3555 - coef[1..nb_loops] are the protected variables that will not be
3556 removed by the solver: the "dx"
3557 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3559 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3560 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3562 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3565 ineq
= omega_add_zero_geq (pb
, omega_black
);
3566 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3568 /* 0 <= loop_x + dx */
3569 ineq
= omega_add_zero_geq (pb
, omega_black
);
3570 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3571 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3575 /* loop_x <= nb_iters */
3576 ineq
= omega_add_zero_geq (pb
, omega_black
);
3577 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3578 pb
->geqs
[ineq
].coef
[0] = nbi
;
3580 /* loop_x + dx <= nb_iters */
3581 ineq
= omega_add_zero_geq (pb
, omega_black
);
3582 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3583 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3584 pb
->geqs
[ineq
].coef
[0] = nbi
;
3586 /* A step "dx" bigger than nb_iters is not feasible, so
3587 add "0 <= nb_iters + dx", */
3588 ineq
= omega_add_zero_geq (pb
, omega_black
);
3589 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3590 pb
->geqs
[ineq
].coef
[0] = nbi
;
3591 /* and "dx <= nb_iters". */
3592 ineq
= omega_add_zero_geq (pb
, omega_black
);
3593 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3594 pb
->geqs
[ineq
].coef
[0] = nbi
;
3598 omega_extract_distance_vectors (pb
, ddr
);
3603 /* Sets up the Omega dependence problem for the data dependence
3604 relation DDR. Returns false when the constraint system cannot be
3605 built, ie. when the test answers "don't know". Returns true
3606 otherwise, and when independence has been proved (using one of the
3607 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3608 set MAYBE_DEPENDENT to true.
3610 Example: for setting up the dependence system corresponding to the
3611 conflicting accesses
3616 | ... A[2*j, 2*(i + j)]
3620 the following constraints come from the iteration domain:
3627 where di, dj are the distance variables. The constraints
3628 representing the conflicting elements are:
3631 i + 1 = 2 * (i + di + j + dj)
3633 For asking that the resulting distance vector (di, dj) be
3634 lexicographically positive, we insert the constraint "di >= 0". If
3635 "di = 0" in the solution, we fix that component to zero, and we
3636 look at the inner loops: we set a new problem where all the outer
3637 loop distances are zero, and fix this inner component to be
3638 positive. When one of the components is positive, we save that
3639 distance, and set a new problem where the distance on this loop is
3640 zero, searching for other distances in the inner loops. Here is
3641 the classic example that illustrates that we have to set for each
3642 inner loop a new problem:
3650 we have to save two distances (1, 0) and (0, 1).
3652 Given two array references, refA and refB, we have to set the
3653 dependence problem twice, refA vs. refB and refB vs. refA, and we
3654 cannot do a single test, as refB might occur before refA in the
3655 inner loops, and the contrary when considering outer loops: ex.
3660 | T[{1,+,1}_2][{1,+,1}_1] // refA
3661 | T[{2,+,1}_2][{0,+,1}_1] // refB
3666 refB touches the elements in T before refA, and thus for the same
3667 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3668 but for successive loop_0 iterations, we have (1, -1, 1)
3670 The Omega solver expects the distance variables ("di" in the
3671 previous example) to come first in the constraint system (as
3672 variables to be protected, or "safe" variables), the constraint
3673 system is built using the following layout:
3675 "cst | distance vars | index vars".
3679 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3680 bool *maybe_dependent
)
3685 *maybe_dependent
= true;
3687 if (same_access_functions (ddr
))
3690 lambda_vector dir_v
;
3692 /* Save the 0 vector. */
3693 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3694 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3695 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3696 dir_v
[j
] = dir_equal
;
3697 save_dir_v (ddr
, dir_v
);
3699 /* Save the dependences carried by outer loops. */
3700 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3701 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3703 omega_free_problem (pb
);
3707 /* Omega expects the protected variables (those that have to be kept
3708 after elimination) to appear first in the constraint system.
3709 These variables are the distance variables. In the following
3710 initialization we declare NB_LOOPS safe variables, and the total
3711 number of variables for the constraint system is 2*NB_LOOPS. */
3712 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3713 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3715 omega_free_problem (pb
);
3717 /* Stop computation if not decidable, or no dependence. */
3718 if (res
== false || *maybe_dependent
== false)
3721 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3722 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3724 omega_free_problem (pb
);
3729 /* Return true when DDR contains the same information as that stored
3730 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3733 ddr_consistent_p (FILE *file
,
3734 struct data_dependence_relation
*ddr
,
3735 VEC (lambda_vector
, heap
) *dist_vects
,
3736 VEC (lambda_vector
, heap
) *dir_vects
)
3740 /* If dump_file is set, output there. */
3741 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3744 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3746 lambda_vector b_dist_v
;
3747 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3748 VEC_length (lambda_vector
, dist_vects
),
3749 DDR_NUM_DIST_VECTS (ddr
));
3751 fprintf (file
, "Banerjee dist vectors:\n");
3752 FOR_EACH_VEC_ELT (lambda_vector
, dist_vects
, i
, b_dist_v
)
3753 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3755 fprintf (file
, "Omega dist vectors:\n");
3756 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3757 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3759 fprintf (file
, "data dependence relation:\n");
3760 dump_data_dependence_relation (file
, ddr
);
3762 fprintf (file
, ")\n");
3766 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3768 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3769 VEC_length (lambda_vector
, dir_vects
),
3770 DDR_NUM_DIR_VECTS (ddr
));
3774 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3776 lambda_vector a_dist_v
;
3777 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3779 /* Distance vectors are not ordered in the same way in the DDR
3780 and in the DIST_VECTS: search for a matching vector. */
3781 FOR_EACH_VEC_ELT (lambda_vector
, dist_vects
, j
, a_dist_v
)
3782 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3785 if (j
== VEC_length (lambda_vector
, dist_vects
))
3787 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3788 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3789 fprintf (file
, "not found in Omega dist vectors:\n");
3790 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3791 fprintf (file
, "data dependence relation:\n");
3792 dump_data_dependence_relation (file
, ddr
);
3793 fprintf (file
, ")\n");
3797 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3799 lambda_vector a_dir_v
;
3800 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3802 /* Direction vectors are not ordered in the same way in the DDR
3803 and in the DIR_VECTS: search for a matching vector. */
3804 FOR_EACH_VEC_ELT (lambda_vector
, dir_vects
, j
, a_dir_v
)
3805 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3808 if (j
== VEC_length (lambda_vector
, dist_vects
))
3810 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3811 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3812 fprintf (file
, "not found in Omega dir vectors:\n");
3813 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3814 fprintf (file
, "data dependence relation:\n");
3815 dump_data_dependence_relation (file
, ddr
);
3816 fprintf (file
, ")\n");
3823 /* This computes the affine dependence relation between A and B with
3824 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3825 independence between two accesses, while CHREC_DONT_KNOW is used
3826 for representing the unknown relation.
3828 Note that it is possible to stop the computation of the dependence
3829 relation the first time we detect a CHREC_KNOWN element for a given
3833 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3834 struct loop
*loop_nest
)
3836 struct data_reference
*dra
= DDR_A (ddr
);
3837 struct data_reference
*drb
= DDR_B (ddr
);
3839 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3841 fprintf (dump_file
, "(compute_affine_dependence\n");
3842 fprintf (dump_file
, " (stmt_a = \n");
3843 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, 0);
3844 fprintf (dump_file
, ")\n (stmt_b = \n");
3845 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, 0);
3846 fprintf (dump_file
, ")\n");
3849 /* Analyze only when the dependence relation is not yet known. */
3850 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
3851 && !DDR_SELF_REFERENCE (ddr
))
3853 dependence_stats
.num_dependence_tests
++;
3855 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3856 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3858 if (flag_check_data_deps
)
3860 /* Compute the dependences using the first algorithm. */
3861 subscript_dependence_tester (ddr
, loop_nest
);
3863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3865 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3866 dump_data_dependence_relation (dump_file
, ddr
);
3869 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3871 bool maybe_dependent
;
3872 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3874 /* Save the result of the first DD analyzer. */
3875 dist_vects
= DDR_DIST_VECTS (ddr
);
3876 dir_vects
= DDR_DIR_VECTS (ddr
);
3878 /* Reset the information. */
3879 DDR_DIST_VECTS (ddr
) = NULL
;
3880 DDR_DIR_VECTS (ddr
) = NULL
;
3882 /* Compute the same information using Omega. */
3883 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3884 goto csys_dont_know
;
3886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3888 fprintf (dump_file
, "Omega Analyzer\n");
3889 dump_data_dependence_relation (dump_file
, ddr
);
3892 /* Check that we get the same information. */
3893 if (maybe_dependent
)
3894 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3899 subscript_dependence_tester (ddr
, loop_nest
);
3902 /* As a last case, if the dependence cannot be determined, or if
3903 the dependence is considered too difficult to determine, answer
3908 dependence_stats
.num_dependence_undetermined
++;
3910 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3912 fprintf (dump_file
, "Data ref a:\n");
3913 dump_data_reference (dump_file
, dra
);
3914 fprintf (dump_file
, "Data ref b:\n");
3915 dump_data_reference (dump_file
, drb
);
3916 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3918 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3922 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3923 fprintf (dump_file
, ")\n");
3926 /* This computes the dependence relation for the same data
3927 reference into DDR. */
3930 compute_self_dependence (struct data_dependence_relation
*ddr
)
3933 struct subscript
*subscript
;
3935 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3938 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3941 if (SUB_CONFLICTS_IN_A (subscript
))
3942 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3943 if (SUB_CONFLICTS_IN_B (subscript
))
3944 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3946 /* The accessed index overlaps for each iteration. */
3947 SUB_CONFLICTS_IN_A (subscript
)
3948 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3949 SUB_CONFLICTS_IN_B (subscript
)
3950 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3951 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3954 /* The distance vector is the zero vector. */
3955 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3956 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3959 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3960 the data references in DATAREFS, in the LOOP_NEST. When
3961 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3965 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
3966 VEC (ddr_p
, heap
) **dependence_relations
,
3967 VEC (loop_p
, heap
) *loop_nest
,
3968 bool compute_self_and_rr
)
3970 struct data_dependence_relation
*ddr
;
3971 struct data_reference
*a
, *b
;
3974 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, a
)
3975 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
3976 if (DR_IS_WRITE (a
) || DR_IS_WRITE (b
) || compute_self_and_rr
)
3978 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
3979 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3981 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
3984 if (compute_self_and_rr
)
3985 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, a
)
3987 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
3988 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3989 compute_self_dependence (ddr
);
3993 /* Stores the locations of memory references in STMT to REFERENCES. Returns
3994 true if STMT clobbers memory, false otherwise. */
3997 get_references_in_stmt (gimple stmt
, VEC (data_ref_loc
, heap
) **references
)
3999 bool clobbers_memory
= false;
4002 enum gimple_code stmt_code
= gimple_code (stmt
);
4006 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4007 Calls have side-effects, except those to const or pure
4009 if ((stmt_code
== GIMPLE_CALL
4010 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4011 || (stmt_code
== GIMPLE_ASM
4012 && gimple_asm_volatile_p (stmt
)))
4013 clobbers_memory
= true;
4015 if (!gimple_vuse (stmt
))
4016 return clobbers_memory
;
4018 if (stmt_code
== GIMPLE_ASSIGN
)
4021 op0
= gimple_assign_lhs_ptr (stmt
);
4022 op1
= gimple_assign_rhs1_ptr (stmt
);
4025 || (REFERENCE_CLASS_P (*op1
)
4026 && (base
= get_base_address (*op1
))
4027 && TREE_CODE (base
) != SSA_NAME
))
4029 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4031 ref
->is_read
= true;
4035 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4037 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4039 ref
->is_read
= false;
4042 else if (stmt_code
== GIMPLE_CALL
)
4044 unsigned i
, n
= gimple_call_num_args (stmt
);
4046 for (i
= 0; i
< n
; i
++)
4048 op0
= gimple_call_arg_ptr (stmt
, i
);
4051 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4053 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4055 ref
->is_read
= true;
4060 return clobbers_memory
;
4063 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4064 reference, returns false, otherwise returns true. NEST is the outermost
4065 loop of the loop nest in which the references should be analyzed. */
4068 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4069 VEC (data_reference_p
, heap
) **datarefs
)
4072 VEC (data_ref_loc
, heap
) *references
;
4075 data_reference_p dr
;
4077 if (get_references_in_stmt (stmt
, &references
))
4079 VEC_free (data_ref_loc
, heap
, references
);
4083 FOR_EACH_VEC_ELT (data_ref_loc
, references
, i
, ref
)
4085 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4086 gcc_assert (dr
!= NULL
);
4088 /* FIXME -- data dependence analysis does not work correctly for objects
4089 with invariant addresses in loop nests. Let us fail here until the
4090 problem is fixed. */
4091 if (dr_address_invariant_p (dr
) && nest
)
4094 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4095 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
4100 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4102 VEC_free (data_ref_loc
, heap
, references
);
4106 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4107 reference, returns false, otherwise returns true. NEST is the outermost
4108 loop of the loop nest in which the references should be analyzed. */
4111 graphite_find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4112 VEC (data_reference_p
, heap
) **datarefs
)
4115 VEC (data_ref_loc
, heap
) *references
;
4118 data_reference_p dr
;
4120 if (get_references_in_stmt (stmt
, &references
))
4122 VEC_free (data_ref_loc
, heap
, references
);
4126 FOR_EACH_VEC_ELT (data_ref_loc
, references
, i
, ref
)
4128 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4129 gcc_assert (dr
!= NULL
);
4130 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4133 VEC_free (data_ref_loc
, heap
, references
);
4137 /* Search the data references in LOOP, and record the information into
4138 DATAREFS. Returns chrec_dont_know when failing to analyze a
4139 difficult case, returns NULL_TREE otherwise. */
4142 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4143 VEC (data_reference_p
, heap
) **datarefs
)
4145 gimple_stmt_iterator bsi
;
4147 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4149 gimple stmt
= gsi_stmt (bsi
);
4151 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4153 struct data_reference
*res
;
4154 res
= XCNEW (struct data_reference
);
4155 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4157 return chrec_dont_know
;
4164 /* Search the data references in LOOP, and record the information into
4165 DATAREFS. Returns chrec_dont_know when failing to analyze a
4166 difficult case, returns NULL_TREE otherwise.
4168 TODO: This function should be made smarter so that it can handle address
4169 arithmetic as if they were array accesses, etc. */
4172 find_data_references_in_loop (struct loop
*loop
,
4173 VEC (data_reference_p
, heap
) **datarefs
)
4175 basic_block bb
, *bbs
;
4178 bbs
= get_loop_body_in_dom_order (loop
);
4180 for (i
= 0; i
< loop
->num_nodes
; i
++)
4184 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4187 return chrec_dont_know
;
4195 /* Recursive helper function. */
4198 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4200 /* Inner loops of the nest should not contain siblings. Example:
4201 when there are two consecutive loops,
4212 the dependence relation cannot be captured by the distance
4217 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4219 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4223 /* Return false when the LOOP is not well nested. Otherwise return
4224 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4225 contain the loops from the outermost to the innermost, as they will
4226 appear in the classic distance vector. */
4229 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4231 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4233 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4237 /* Returns true when the data dependences have been computed, false otherwise.
4238 Given a loop nest LOOP, the following vectors are returned:
4239 DATAREFS is initialized to all the array elements contained in this loop,
4240 DEPENDENCE_RELATIONS contains the relations between the data references.
4241 Compute read-read and self relations if
4242 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4245 compute_data_dependences_for_loop (struct loop
*loop
,
4246 bool compute_self_and_read_read_dependences
,
4247 VEC (data_reference_p
, heap
) **datarefs
,
4248 VEC (ddr_p
, heap
) **dependence_relations
)
4251 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4253 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4255 /* If the loop nest is not well formed, or one of the data references
4256 is not computable, give up without spending time to compute other
4259 || !find_loop_nest (loop
, &vloops
)
4260 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4262 struct data_dependence_relation
*ddr
;
4264 /* Insert a single relation into dependence_relations:
4266 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4267 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4271 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4272 compute_self_and_read_read_dependences
);
4274 if (dump_file
&& (dump_flags
& TDF_STATS
))
4276 fprintf (dump_file
, "Dependence tester statistics:\n");
4278 fprintf (dump_file
, "Number of dependence tests: %d\n",
4279 dependence_stats
.num_dependence_tests
);
4280 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4281 dependence_stats
.num_dependence_dependent
);
4282 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4283 dependence_stats
.num_dependence_independent
);
4284 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4285 dependence_stats
.num_dependence_undetermined
);
4287 fprintf (dump_file
, "Number of subscript tests: %d\n",
4288 dependence_stats
.num_subscript_tests
);
4289 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4290 dependence_stats
.num_subscript_undetermined
);
4291 fprintf (dump_file
, "Number of same subscript function: %d\n",
4292 dependence_stats
.num_same_subscript_function
);
4294 fprintf (dump_file
, "Number of ziv tests: %d\n",
4295 dependence_stats
.num_ziv
);
4296 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4297 dependence_stats
.num_ziv_dependent
);
4298 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4299 dependence_stats
.num_ziv_independent
);
4300 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4301 dependence_stats
.num_ziv_unimplemented
);
4303 fprintf (dump_file
, "Number of siv tests: %d\n",
4304 dependence_stats
.num_siv
);
4305 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4306 dependence_stats
.num_siv_dependent
);
4307 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4308 dependence_stats
.num_siv_independent
);
4309 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4310 dependence_stats
.num_siv_unimplemented
);
4312 fprintf (dump_file
, "Number of miv tests: %d\n",
4313 dependence_stats
.num_miv
);
4314 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4315 dependence_stats
.num_miv_dependent
);
4316 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4317 dependence_stats
.num_miv_independent
);
4318 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4319 dependence_stats
.num_miv_unimplemented
);
4325 /* Returns true when the data dependences for the basic block BB have been
4326 computed, false otherwise.
4327 DATAREFS is initialized to all the array elements contained in this basic
4328 block, DEPENDENCE_RELATIONS contains the relations between the data
4329 references. Compute read-read and self relations if
4330 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4332 compute_data_dependences_for_bb (basic_block bb
,
4333 bool compute_self_and_read_read_dependences
,
4334 VEC (data_reference_p
, heap
) **datarefs
,
4335 VEC (ddr_p
, heap
) **dependence_relations
)
4337 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4340 compute_all_dependences (*datarefs
, dependence_relations
, NULL
,
4341 compute_self_and_read_read_dependences
);
4345 /* Entry point (for testing only). Analyze all the data references
4346 and the dependence relations in LOOP.
4348 The data references are computed first.
4350 A relation on these nodes is represented by a complete graph. Some
4351 of the relations could be of no interest, thus the relations can be
4354 In the following function we compute all the relations. This is
4355 just a first implementation that is here for:
4356 - for showing how to ask for the dependence relations,
4357 - for the debugging the whole dependence graph,
4358 - for the dejagnu testcases and maintenance.
4360 It is possible to ask only for a part of the graph, avoiding to
4361 compute the whole dependence graph. The computed dependences are
4362 stored in a knowledge base (KB) such that later queries don't
4363 recompute the same information. The implementation of this KB is
4364 transparent to the optimizer, and thus the KB can be changed with a
4365 more efficient implementation, or the KB could be disabled. */
4367 analyze_all_data_dependences (struct loop
*loop
)
4370 int nb_data_refs
= 10;
4371 VEC (data_reference_p
, heap
) *datarefs
=
4372 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4373 VEC (ddr_p
, heap
) *dependence_relations
=
4374 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4376 /* Compute DDs on the whole function. */
4377 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4378 &dependence_relations
);
4382 dump_data_dependence_relations (dump_file
, dependence_relations
);
4383 fprintf (dump_file
, "\n\n");
4385 if (dump_flags
& TDF_DETAILS
)
4386 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4388 if (dump_flags
& TDF_STATS
)
4390 unsigned nb_top_relations
= 0;
4391 unsigned nb_bot_relations
= 0;
4392 unsigned nb_chrec_relations
= 0;
4393 struct data_dependence_relation
*ddr
;
4395 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4397 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4400 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4404 nb_chrec_relations
++;
4407 gather_stats_on_scev_database ();
4411 free_dependence_relations (dependence_relations
);
4412 free_data_refs (datarefs
);
4415 /* Computes all the data dependences and check that the results of
4416 several analyzers are the same. */
4419 tree_check_data_deps (void)
4422 struct loop
*loop_nest
;
4424 FOR_EACH_LOOP (li
, loop_nest
, 0)
4425 analyze_all_data_dependences (loop_nest
);
4428 /* Free the memory used by a data dependence relation DDR. */
4431 free_dependence_relation (struct data_dependence_relation
*ddr
)
4436 if (DDR_SUBSCRIPTS (ddr
))
4437 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4438 if (DDR_DIST_VECTS (ddr
))
4439 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4440 if (DDR_DIR_VECTS (ddr
))
4441 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4446 /* Free the memory used by the data dependence relations from
4447 DEPENDENCE_RELATIONS. */
4450 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4453 struct data_dependence_relation
*ddr
;
4454 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4456 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4460 if (loop_nest
== NULL
)
4461 loop_nest
= DDR_LOOP_NEST (ddr
);
4463 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4464 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4465 free_dependence_relation (ddr
);
4469 VEC_free (loop_p
, heap
, loop_nest
);
4470 VEC_free (ddr_p
, heap
, dependence_relations
);
4473 /* Free the memory used by the data references from DATAREFS. */
4476 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4479 struct data_reference
*dr
;
4481 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
4483 VEC_free (data_reference_p
, heap
, datarefs
);
4488 /* Dump vertex I in RDG to FILE. */
4491 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4493 struct vertex
*v
= &(rdg
->vertices
[i
]);
4494 struct graph_edge
*e
;
4496 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4497 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4498 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4501 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4502 fprintf (file
, " %d", e
->src
);
4504 fprintf (file
, ") (out:");
4507 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4508 fprintf (file
, " %d", e
->dest
);
4510 fprintf (file
, ") \n");
4511 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4512 fprintf (file
, ")\n");
4515 /* Call dump_rdg_vertex on stderr. */
4518 debug_rdg_vertex (struct graph
*rdg
, int i
)
4520 dump_rdg_vertex (stderr
, rdg
, i
);
4523 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4524 dumped vertices to that bitmap. */
4526 void dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4530 fprintf (file
, "(%d\n", c
);
4532 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4533 if (rdg
->vertices
[i
].component
== c
)
4536 bitmap_set_bit (dumped
, i
);
4538 dump_rdg_vertex (file
, rdg
, i
);
4541 fprintf (file
, ")\n");
4544 /* Call dump_rdg_vertex on stderr. */
4547 debug_rdg_component (struct graph
*rdg
, int c
)
4549 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4552 /* Dump the reduced dependence graph RDG to FILE. */
4555 dump_rdg (FILE *file
, struct graph
*rdg
)
4558 bitmap dumped
= BITMAP_ALLOC (NULL
);
4560 fprintf (file
, "(rdg\n");
4562 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4563 if (!bitmap_bit_p (dumped
, i
))
4564 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4566 fprintf (file
, ")\n");
4567 BITMAP_FREE (dumped
);
4570 /* Call dump_rdg on stderr. */
4573 debug_rdg (struct graph
*rdg
)
4575 dump_rdg (stderr
, rdg
);
4579 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
4583 fprintf (file
, "digraph RDG {\n");
4585 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4587 struct vertex
*v
= &(rdg
->vertices
[i
]);
4588 struct graph_edge
*e
;
4590 /* Highlight reads from memory. */
4591 if (RDG_MEM_READS_STMT (rdg
, i
))
4592 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
4594 /* Highlight stores to memory. */
4595 if (RDG_MEM_WRITE_STMT (rdg
, i
))
4596 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
4599 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4600 switch (RDGE_TYPE (e
))
4603 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
4607 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
4611 /* These are the most common dependences: don't print these. */
4612 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
4616 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
4624 fprintf (file
, "}\n\n");
4627 /* Display the Reduced Dependence Graph using dotty. */
4628 extern void dot_rdg (struct graph
*);
4631 dot_rdg (struct graph
*rdg
)
4633 /* When debugging, enable the following code. This cannot be used
4634 in production compilers because it calls "system". */
4636 FILE *file
= fopen ("/tmp/rdg.dot", "w");
4637 gcc_assert (file
!= NULL
);
4639 dot_rdg_1 (file
, rdg
);
4642 system ("dotty /tmp/rdg.dot &");
4644 dot_rdg_1 (stderr
, rdg
);
4648 /* This structure is used for recording the mapping statement index in
4651 struct GTY(()) rdg_vertex_info
4657 /* Returns the index of STMT in RDG. */
4660 rdg_vertex_for_stmt (struct graph
*rdg
, gimple stmt
)
4662 struct rdg_vertex_info rvi
, *slot
;
4665 slot
= (struct rdg_vertex_info
*) htab_find (rdg
->indices
, &rvi
);
4673 /* Creates an edge in RDG for each distance vector from DDR. The
4674 order that we keep track of in the RDG is the order in which
4675 statements have to be executed. */
4678 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4680 struct graph_edge
*e
;
4682 data_reference_p dra
= DDR_A (ddr
);
4683 data_reference_p drb
= DDR_B (ddr
);
4684 unsigned level
= ddr_dependence_level (ddr
);
4686 /* For non scalar dependences, when the dependence is REVERSED,
4687 statement B has to be executed before statement A. */
4689 && !DDR_REVERSED_P (ddr
))
4691 data_reference_p tmp
= dra
;
4696 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4697 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4699 if (va
< 0 || vb
< 0)
4702 e
= add_edge (rdg
, va
, vb
);
4703 e
->data
= XNEW (struct rdg_edge
);
4705 RDGE_LEVEL (e
) = level
;
4706 RDGE_RELATION (e
) = ddr
;
4708 /* Determines the type of the data dependence. */
4709 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4710 RDGE_TYPE (e
) = input_dd
;
4711 else if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
4712 RDGE_TYPE (e
) = output_dd
;
4713 else if (DR_IS_WRITE (dra
) && DR_IS_READ (drb
))
4714 RDGE_TYPE (e
) = flow_dd
;
4715 else if (DR_IS_READ (dra
) && DR_IS_WRITE (drb
))
4716 RDGE_TYPE (e
) = anti_dd
;
4719 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4720 the index of DEF in RDG. */
4723 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4725 use_operand_p imm_use_p
;
4726 imm_use_iterator iterator
;
4728 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4730 struct graph_edge
*e
;
4731 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4736 e
= add_edge (rdg
, idef
, use
);
4737 e
->data
= XNEW (struct rdg_edge
);
4738 RDGE_TYPE (e
) = flow_dd
;
4739 RDGE_RELATION (e
) = NULL
;
4743 /* Creates the edges of the reduced dependence graph RDG. */
4746 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4749 struct data_dependence_relation
*ddr
;
4750 def_operand_p def_p
;
4753 FOR_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
4754 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4755 create_rdg_edge_for_ddr (rdg
, ddr
);
4757 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4758 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4760 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4763 /* Build the vertices of the reduced dependence graph RDG. */
4766 create_rdg_vertices (struct graph
*rdg
, VEC (gimple
, heap
) *stmts
)
4771 FOR_EACH_VEC_ELT (gimple
, stmts
, i
, stmt
)
4773 VEC (data_ref_loc
, heap
) *references
;
4775 struct vertex
*v
= &(rdg
->vertices
[i
]);
4776 struct rdg_vertex_info
*rvi
= XNEW (struct rdg_vertex_info
);
4777 struct rdg_vertex_info
**slot
;
4781 slot
= (struct rdg_vertex_info
**) htab_find_slot (rdg
->indices
, rvi
, INSERT
);
4788 v
->data
= XNEW (struct rdg_vertex
);
4789 RDG_STMT (rdg
, i
) = stmt
;
4791 RDG_MEM_WRITE_STMT (rdg
, i
) = false;
4792 RDG_MEM_READS_STMT (rdg
, i
) = false;
4793 if (gimple_code (stmt
) == GIMPLE_PHI
)
4796 get_references_in_stmt (stmt
, &references
);
4797 FOR_EACH_VEC_ELT (data_ref_loc
, references
, j
, ref
)
4799 RDG_MEM_WRITE_STMT (rdg
, i
) = true;
4801 RDG_MEM_READS_STMT (rdg
, i
) = true;
4803 VEC_free (data_ref_loc
, heap
, references
);
4807 /* Initialize STMTS with all the statements of LOOP. When
4808 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4809 which we discover statements is important as
4810 generate_loops_for_partition is using the same traversal for
4811 identifying statements. */
4814 stmts_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4817 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4819 for (i
= 0; i
< loop
->num_nodes
; i
++)
4821 basic_block bb
= bbs
[i
];
4822 gimple_stmt_iterator bsi
;
4825 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4826 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4828 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4830 stmt
= gsi_stmt (bsi
);
4831 if (gimple_code (stmt
) != GIMPLE_LABEL
)
4832 VEC_safe_push (gimple
, heap
, *stmts
, stmt
);
4839 /* Returns true when all the dependences are computable. */
4842 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
4847 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4848 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4854 /* Computes a hash function for element ELT. */
4857 hash_stmt_vertex_info (const void *elt
)
4859 const struct rdg_vertex_info
*const rvi
=
4860 (const struct rdg_vertex_info
*) elt
;
4861 gimple stmt
= rvi
->stmt
;
4863 return htab_hash_pointer (stmt
);
4866 /* Compares database elements E1 and E2. */
4869 eq_stmt_vertex_info (const void *e1
, const void *e2
)
4871 const struct rdg_vertex_info
*elt1
= (const struct rdg_vertex_info
*) e1
;
4872 const struct rdg_vertex_info
*elt2
= (const struct rdg_vertex_info
*) e2
;
4874 return elt1
->stmt
== elt2
->stmt
;
4877 /* Free the element E. */
4880 hash_stmt_vertex_del (void *e
)
4885 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4886 statement of the loop nest, and one edge per data dependence or
4887 scalar dependence. */
4890 build_empty_rdg (int n_stmts
)
4892 int nb_data_refs
= 10;
4893 struct graph
*rdg
= new_graph (n_stmts
);
4895 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4896 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4900 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4901 statement of the loop nest, and one edge per data dependence or
4902 scalar dependence. */
4905 build_rdg (struct loop
*loop
)
4907 int nb_data_refs
= 10;
4908 struct graph
*rdg
= NULL
;
4909 VEC (ddr_p
, heap
) *dependence_relations
;
4910 VEC (data_reference_p
, heap
) *datarefs
;
4911 VEC (gimple
, heap
) *stmts
= VEC_alloc (gimple
, heap
, nb_data_refs
);
4913 dependence_relations
= VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
) ;
4914 datarefs
= VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4915 compute_data_dependences_for_loop (loop
,
4918 &dependence_relations
);
4920 if (!known_dependences_p (dependence_relations
))
4922 free_dependence_relations (dependence_relations
);
4923 free_data_refs (datarefs
);
4924 VEC_free (gimple
, heap
, stmts
);
4929 stmts_from_loop (loop
, &stmts
);
4930 rdg
= build_empty_rdg (VEC_length (gimple
, stmts
));
4932 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4933 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4934 create_rdg_vertices (rdg
, stmts
);
4935 create_rdg_edges (rdg
, dependence_relations
);
4937 VEC_free (gimple
, heap
, stmts
);
4941 /* Free the reduced dependence graph RDG. */
4944 free_rdg (struct graph
*rdg
)
4948 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4949 free (rdg
->vertices
[i
].data
);
4951 htab_delete (rdg
->indices
);
4955 /* Initialize STMTS with all the statements of LOOP that contain a
4959 stores_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4962 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4964 for (i
= 0; i
< loop
->num_nodes
; i
++)
4966 basic_block bb
= bbs
[i
];
4967 gimple_stmt_iterator bsi
;
4969 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4970 if (gimple_vdef (gsi_stmt (bsi
)))
4971 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4977 /* Returns true when STMT is an assignment that contains a data
4978 reference on its LHS with a stride of the same size as its unit
4982 mem_write_stride_of_same_size_as_unit_type_p (gimple stmt
)
4984 struct data_reference
*dr
= XCNEW (struct data_reference
);
4985 tree op0
= gimple_assign_lhs (stmt
);
4988 DR_STMT (dr
) = stmt
;
4991 res
= dr_analyze_innermost (dr
)
4992 && stride_of_unit_type_p (DR_STEP (dr
), TREE_TYPE (op0
));
4998 /* Initialize STMTS with all the statements of LOOP that contain a
4999 store to memory of the form "A[i] = 0". */
5002 stores_zero_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
5006 gimple_stmt_iterator si
;
5009 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
5011 for (i
= 0; i
< loop
->num_nodes
; i
++)
5012 for (bb
= bbs
[i
], si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
5013 if ((stmt
= gsi_stmt (si
))
5014 && gimple_vdef (stmt
)
5015 && is_gimple_assign (stmt
)
5016 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
5017 && (op
= gimple_assign_rhs1 (stmt
))
5018 && (integer_zerop (op
) || real_zerop (op
))
5019 && mem_write_stride_of_same_size_as_unit_type_p (stmt
))
5020 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (si
));
5025 /* For a data reference REF, return the declaration of its base
5026 address or NULL_TREE if the base is not determined. */
5029 ref_base_address (gimple stmt
, data_ref_loc
*ref
)
5031 tree base
= NULL_TREE
;
5033 struct data_reference
*dr
= XCNEW (struct data_reference
);
5035 DR_STMT (dr
) = stmt
;
5036 DR_REF (dr
) = *ref
->pos
;
5037 dr_analyze_innermost (dr
);
5038 base_address
= DR_BASE_ADDRESS (dr
);
5043 switch (TREE_CODE (base_address
))
5046 base
= TREE_OPERAND (base_address
, 0);
5050 base
= base_address
;
5059 /* Determines whether the statement from vertex V of the RDG has a
5060 definition used outside the loop that contains this statement. */
5063 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
5065 gimple stmt
= RDG_STMT (rdg
, v
);
5066 struct loop
*loop
= loop_containing_stmt (stmt
);
5067 use_operand_p imm_use_p
;
5068 imm_use_iterator iterator
;
5070 def_operand_p def_p
;
5075 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
5077 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
5079 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)
5087 /* Determines whether statements S1 and S2 access to similar memory
5088 locations. Two memory accesses are considered similar when they
5089 have the same base address declaration, i.e. when their
5090 ref_base_address is the same. */
5093 have_similar_memory_accesses (gimple s1
, gimple s2
)
5097 VEC (data_ref_loc
, heap
) *refs1
, *refs2
;
5098 data_ref_loc
*ref1
, *ref2
;
5100 get_references_in_stmt (s1
, &refs1
);
5101 get_references_in_stmt (s2
, &refs2
);
5103 FOR_EACH_VEC_ELT (data_ref_loc
, refs1
, i
, ref1
)
5105 tree base1
= ref_base_address (s1
, ref1
);
5108 FOR_EACH_VEC_ELT (data_ref_loc
, refs2
, j
, ref2
)
5109 if (base1
== ref_base_address (s2
, ref2
))
5117 VEC_free (data_ref_loc
, heap
, refs1
);
5118 VEC_free (data_ref_loc
, heap
, refs2
);
5122 /* Helper function for the hashtab. */
5125 have_similar_memory_accesses_1 (const void *s1
, const void *s2
)
5127 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple
) s1
),
5128 CONST_CAST_GIMPLE ((const_gimple
) s2
));
5131 /* Helper function for the hashtab. */
5134 ref_base_address_1 (const void *s
)
5136 gimple stmt
= CONST_CAST_GIMPLE ((const_gimple
) s
);
5138 VEC (data_ref_loc
, heap
) *refs
;
5142 get_references_in_stmt (stmt
, &refs
);
5144 FOR_EACH_VEC_ELT (data_ref_loc
, refs
, i
, ref
)
5147 res
= htab_hash_pointer (ref_base_address (stmt
, ref
));
5151 VEC_free (data_ref_loc
, heap
, refs
);
5155 /* Try to remove duplicated write data references from STMTS. */
5158 remove_similar_memory_refs (VEC (gimple
, heap
) **stmts
)
5162 htab_t seen
= htab_create (VEC_length (gimple
, *stmts
), ref_base_address_1
,
5163 have_similar_memory_accesses_1
, NULL
);
5165 for (i
= 0; VEC_iterate (gimple
, *stmts
, i
, stmt
); )
5169 slot
= htab_find_slot (seen
, stmt
, INSERT
);
5172 VEC_ordered_remove (gimple
, *stmts
, i
);
5175 *slot
= (void *) stmt
;
5183 /* Returns the index of PARAMETER in the parameters vector of the
5184 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5187 access_matrix_get_index_for_parameter (tree parameter
,
5188 struct access_matrix
*access_matrix
)
5191 VEC (tree
,heap
) *lambda_parameters
= AM_PARAMETERS (access_matrix
);
5192 tree lambda_parameter
;
5194 FOR_EACH_VEC_ELT (tree
, lambda_parameters
, i
, lambda_parameter
)
5195 if (lambda_parameter
== parameter
)
5196 return i
+ AM_NB_INDUCTION_VARS (access_matrix
);