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
);
3487 /* When the fun_a - fun_b is not constant, the dependence is not
3488 captured by the classic distance vector representation. */
3489 if (TREE_CODE (difference
) != INTEGER_CST
)
3493 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3495 /* There is no dependence. */
3496 *maybe_dependent
= false;
3500 minus_one
= build_int_cst (type
, -1);
3501 fun_b
= chrec_fold_multiply (type
, fun_b
, minus_one
);
3503 eq
= omega_add_zero_eq (pb
, omega_black
);
3504 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3505 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3506 /* There is probably a dependence, but the system of
3507 constraints cannot be built: answer "don't know". */
3511 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3512 && !int_divides_p (lambda_vector_gcd
3513 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3514 2 * DDR_NB_LOOPS (ddr
)),
3515 pb
->eqs
[eq
].coef
[0]))
3517 /* There is no dependence. */
3518 *maybe_dependent
= false;
3525 /* Helper function, same as init_omega_for_ddr but specialized for
3526 data references A and B. */
3529 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3530 struct data_dependence_relation
*ddr
,
3531 omega_pb pb
, bool *maybe_dependent
)
3536 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3538 /* Insert an equality per subscript. */
3539 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3541 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3542 ddr
, pb
, maybe_dependent
))
3544 else if (*maybe_dependent
== false)
3546 /* There is no dependence. */
3547 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3552 /* Insert inequalities: constraints corresponding to the iteration
3553 domain, i.e. the loops surrounding the references "loop_x" and
3554 the distance variables "dx". The layout of the OMEGA
3555 representation is as follows:
3556 - coef[0] is the constant
3557 - coef[1..nb_loops] are the protected variables that will not be
3558 removed by the solver: the "dx"
3559 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3561 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3562 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3564 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, false);
3567 ineq
= omega_add_zero_geq (pb
, omega_black
);
3568 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3570 /* 0 <= loop_x + dx */
3571 ineq
= omega_add_zero_geq (pb
, omega_black
);
3572 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3573 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3577 /* loop_x <= nb_iters */
3578 ineq
= omega_add_zero_geq (pb
, omega_black
);
3579 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3580 pb
->geqs
[ineq
].coef
[0] = nbi
;
3582 /* loop_x + dx <= nb_iters */
3583 ineq
= omega_add_zero_geq (pb
, omega_black
);
3584 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3585 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3586 pb
->geqs
[ineq
].coef
[0] = nbi
;
3588 /* A step "dx" bigger than nb_iters is not feasible, so
3589 add "0 <= nb_iters + dx", */
3590 ineq
= omega_add_zero_geq (pb
, omega_black
);
3591 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3592 pb
->geqs
[ineq
].coef
[0] = nbi
;
3593 /* and "dx <= nb_iters". */
3594 ineq
= omega_add_zero_geq (pb
, omega_black
);
3595 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3596 pb
->geqs
[ineq
].coef
[0] = nbi
;
3600 omega_extract_distance_vectors (pb
, ddr
);
3605 /* Sets up the Omega dependence problem for the data dependence
3606 relation DDR. Returns false when the constraint system cannot be
3607 built, ie. when the test answers "don't know". Returns true
3608 otherwise, and when independence has been proved (using one of the
3609 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3610 set MAYBE_DEPENDENT to true.
3612 Example: for setting up the dependence system corresponding to the
3613 conflicting accesses
3618 | ... A[2*j, 2*(i + j)]
3622 the following constraints come from the iteration domain:
3629 where di, dj are the distance variables. The constraints
3630 representing the conflicting elements are:
3633 i + 1 = 2 * (i + di + j + dj)
3635 For asking that the resulting distance vector (di, dj) be
3636 lexicographically positive, we insert the constraint "di >= 0". If
3637 "di = 0" in the solution, we fix that component to zero, and we
3638 look at the inner loops: we set a new problem where all the outer
3639 loop distances are zero, and fix this inner component to be
3640 positive. When one of the components is positive, we save that
3641 distance, and set a new problem where the distance on this loop is
3642 zero, searching for other distances in the inner loops. Here is
3643 the classic example that illustrates that we have to set for each
3644 inner loop a new problem:
3652 we have to save two distances (1, 0) and (0, 1).
3654 Given two array references, refA and refB, we have to set the
3655 dependence problem twice, refA vs. refB and refB vs. refA, and we
3656 cannot do a single test, as refB might occur before refA in the
3657 inner loops, and the contrary when considering outer loops: ex.
3662 | T[{1,+,1}_2][{1,+,1}_1] // refA
3663 | T[{2,+,1}_2][{0,+,1}_1] // refB
3668 refB touches the elements in T before refA, and thus for the same
3669 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3670 but for successive loop_0 iterations, we have (1, -1, 1)
3672 The Omega solver expects the distance variables ("di" in the
3673 previous example) to come first in the constraint system (as
3674 variables to be protected, or "safe" variables), the constraint
3675 system is built using the following layout:
3677 "cst | distance vars | index vars".
3681 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3682 bool *maybe_dependent
)
3687 *maybe_dependent
= true;
3689 if (same_access_functions (ddr
))
3692 lambda_vector dir_v
;
3694 /* Save the 0 vector. */
3695 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3696 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3697 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3698 dir_v
[j
] = dir_equal
;
3699 save_dir_v (ddr
, dir_v
);
3701 /* Save the dependences carried by outer loops. */
3702 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3703 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3705 omega_free_problem (pb
);
3709 /* Omega expects the protected variables (those that have to be kept
3710 after elimination) to appear first in the constraint system.
3711 These variables are the distance variables. In the following
3712 initialization we declare NB_LOOPS safe variables, and the total
3713 number of variables for the constraint system is 2*NB_LOOPS. */
3714 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3715 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3717 omega_free_problem (pb
);
3719 /* Stop computation if not decidable, or no dependence. */
3720 if (res
== false || *maybe_dependent
== false)
3723 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3724 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3726 omega_free_problem (pb
);
3731 /* Return true when DDR contains the same information as that stored
3732 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3735 ddr_consistent_p (FILE *file
,
3736 struct data_dependence_relation
*ddr
,
3737 VEC (lambda_vector
, heap
) *dist_vects
,
3738 VEC (lambda_vector
, heap
) *dir_vects
)
3742 /* If dump_file is set, output there. */
3743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3746 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
3748 lambda_vector b_dist_v
;
3749 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3750 VEC_length (lambda_vector
, dist_vects
),
3751 DDR_NUM_DIST_VECTS (ddr
));
3753 fprintf (file
, "Banerjee dist vectors:\n");
3754 FOR_EACH_VEC_ELT (lambda_vector
, dist_vects
, i
, b_dist_v
)
3755 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
3757 fprintf (file
, "Omega dist vectors:\n");
3758 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3759 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
3761 fprintf (file
, "data dependence relation:\n");
3762 dump_data_dependence_relation (file
, ddr
);
3764 fprintf (file
, ")\n");
3768 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
3770 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3771 VEC_length (lambda_vector
, dir_vects
),
3772 DDR_NUM_DIR_VECTS (ddr
));
3776 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3778 lambda_vector a_dist_v
;
3779 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
3781 /* Distance vectors are not ordered in the same way in the DDR
3782 and in the DIST_VECTS: search for a matching vector. */
3783 FOR_EACH_VEC_ELT (lambda_vector
, dist_vects
, j
, a_dist_v
)
3784 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
3787 if (j
== VEC_length (lambda_vector
, dist_vects
))
3789 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
3790 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
3791 fprintf (file
, "not found in Omega dist vectors:\n");
3792 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3793 fprintf (file
, "data dependence relation:\n");
3794 dump_data_dependence_relation (file
, ddr
);
3795 fprintf (file
, ")\n");
3799 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
3801 lambda_vector a_dir_v
;
3802 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
3804 /* Direction vectors are not ordered in the same way in the DDR
3805 and in the DIR_VECTS: search for a matching vector. */
3806 FOR_EACH_VEC_ELT (lambda_vector
, dir_vects
, j
, a_dir_v
)
3807 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
3810 if (j
== VEC_length (lambda_vector
, dist_vects
))
3812 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
3813 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
3814 fprintf (file
, "not found in Omega dir vectors:\n");
3815 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
3816 fprintf (file
, "data dependence relation:\n");
3817 dump_data_dependence_relation (file
, ddr
);
3818 fprintf (file
, ")\n");
3825 /* This computes the affine dependence relation between A and B with
3826 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3827 independence between two accesses, while CHREC_DONT_KNOW is used
3828 for representing the unknown relation.
3830 Note that it is possible to stop the computation of the dependence
3831 relation the first time we detect a CHREC_KNOWN element for a given
3835 compute_affine_dependence (struct data_dependence_relation
*ddr
,
3836 struct loop
*loop_nest
)
3838 struct data_reference
*dra
= DDR_A (ddr
);
3839 struct data_reference
*drb
= DDR_B (ddr
);
3841 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3843 fprintf (dump_file
, "(compute_affine_dependence\n");
3844 fprintf (dump_file
, " (stmt_a = \n");
3845 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, 0);
3846 fprintf (dump_file
, ")\n (stmt_b = \n");
3847 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, 0);
3848 fprintf (dump_file
, ")\n");
3851 /* Analyze only when the dependence relation is not yet known. */
3852 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
3853 && !DDR_SELF_REFERENCE (ddr
))
3855 dependence_stats
.num_dependence_tests
++;
3857 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
3858 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
3860 if (flag_check_data_deps
)
3862 /* Compute the dependences using the first algorithm. */
3863 subscript_dependence_tester (ddr
, loop_nest
);
3865 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3867 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
3868 dump_data_dependence_relation (dump_file
, ddr
);
3871 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3873 bool maybe_dependent
;
3874 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
3876 /* Save the result of the first DD analyzer. */
3877 dist_vects
= DDR_DIST_VECTS (ddr
);
3878 dir_vects
= DDR_DIR_VECTS (ddr
);
3880 /* Reset the information. */
3881 DDR_DIST_VECTS (ddr
) = NULL
;
3882 DDR_DIR_VECTS (ddr
) = NULL
;
3884 /* Compute the same information using Omega. */
3885 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
3886 goto csys_dont_know
;
3888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3890 fprintf (dump_file
, "Omega Analyzer\n");
3891 dump_data_dependence_relation (dump_file
, ddr
);
3894 /* Check that we get the same information. */
3895 if (maybe_dependent
)
3896 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
3901 subscript_dependence_tester (ddr
, loop_nest
);
3904 /* As a last case, if the dependence cannot be determined, or if
3905 the dependence is considered too difficult to determine, answer
3910 dependence_stats
.num_dependence_undetermined
++;
3912 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3914 fprintf (dump_file
, "Data ref a:\n");
3915 dump_data_reference (dump_file
, dra
);
3916 fprintf (dump_file
, "Data ref b:\n");
3917 dump_data_reference (dump_file
, drb
);
3918 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3920 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3925 fprintf (dump_file
, ")\n");
3928 /* This computes the dependence relation for the same data
3929 reference into DDR. */
3932 compute_self_dependence (struct data_dependence_relation
*ddr
)
3935 struct subscript
*subscript
;
3937 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3940 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3943 if (SUB_CONFLICTS_IN_A (subscript
))
3944 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3945 if (SUB_CONFLICTS_IN_B (subscript
))
3946 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3948 /* The accessed index overlaps for each iteration. */
3949 SUB_CONFLICTS_IN_A (subscript
)
3950 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3951 SUB_CONFLICTS_IN_B (subscript
)
3952 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
3953 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3956 /* The distance vector is the zero vector. */
3957 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3958 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3961 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3962 the data references in DATAREFS, in the LOOP_NEST. When
3963 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3967 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
3968 VEC (ddr_p
, heap
) **dependence_relations
,
3969 VEC (loop_p
, heap
) *loop_nest
,
3970 bool compute_self_and_rr
)
3972 struct data_dependence_relation
*ddr
;
3973 struct data_reference
*a
, *b
;
3976 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, a
)
3977 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
3978 if (DR_IS_WRITE (a
) || DR_IS_WRITE (b
) || compute_self_and_rr
)
3980 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
3981 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3983 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
3986 if (compute_self_and_rr
)
3987 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, a
)
3989 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
3990 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3991 compute_self_dependence (ddr
);
3995 /* Stores the locations of memory references in STMT to REFERENCES. Returns
3996 true if STMT clobbers memory, false otherwise. */
3999 get_references_in_stmt (gimple stmt
, VEC (data_ref_loc
, heap
) **references
)
4001 bool clobbers_memory
= false;
4004 enum gimple_code stmt_code
= gimple_code (stmt
);
4008 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4009 Calls have side-effects, except those to const or pure
4011 if ((stmt_code
== GIMPLE_CALL
4012 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4013 || (stmt_code
== GIMPLE_ASM
4014 && gimple_asm_volatile_p (stmt
)))
4015 clobbers_memory
= true;
4017 if (!gimple_vuse (stmt
))
4018 return clobbers_memory
;
4020 if (stmt_code
== GIMPLE_ASSIGN
)
4023 op0
= gimple_assign_lhs_ptr (stmt
);
4024 op1
= gimple_assign_rhs1_ptr (stmt
);
4027 || (REFERENCE_CLASS_P (*op1
)
4028 && (base
= get_base_address (*op1
))
4029 && TREE_CODE (base
) != SSA_NAME
))
4031 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4033 ref
->is_read
= true;
4037 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4039 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4041 ref
->is_read
= false;
4044 else if (stmt_code
== GIMPLE_CALL
)
4046 unsigned i
, n
= gimple_call_num_args (stmt
);
4048 for (i
= 0; i
< n
; i
++)
4050 op0
= gimple_call_arg_ptr (stmt
, i
);
4053 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
)))
4055 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4057 ref
->is_read
= true;
4062 return clobbers_memory
;
4065 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4066 reference, returns false, otherwise returns true. NEST is the outermost
4067 loop of the loop nest in which the references should be analyzed. */
4070 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4071 VEC (data_reference_p
, heap
) **datarefs
)
4074 VEC (data_ref_loc
, heap
) *references
;
4077 data_reference_p dr
;
4079 if (get_references_in_stmt (stmt
, &references
))
4081 VEC_free (data_ref_loc
, heap
, references
);
4085 FOR_EACH_VEC_ELT (data_ref_loc
, references
, i
, ref
)
4087 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4088 gcc_assert (dr
!= NULL
);
4090 /* FIXME -- data dependence analysis does not work correctly for objects
4091 with invariant addresses in loop nests. Let us fail here until the
4092 problem is fixed. */
4093 if (dr_address_invariant_p (dr
) && nest
)
4096 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4097 fprintf (dump_file
, "\tFAILED as dr address is invariant\n");
4102 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4104 VEC_free (data_ref_loc
, heap
, references
);
4108 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4109 reference, returns false, otherwise returns true. NEST is the outermost
4110 loop of the loop nest in which the references should be analyzed. */
4113 graphite_find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4114 VEC (data_reference_p
, heap
) **datarefs
)
4117 VEC (data_ref_loc
, heap
) *references
;
4120 data_reference_p dr
;
4122 if (get_references_in_stmt (stmt
, &references
))
4124 VEC_free (data_ref_loc
, heap
, references
);
4128 FOR_EACH_VEC_ELT (data_ref_loc
, references
, i
, ref
)
4130 dr
= create_data_ref (nest
, *ref
->pos
, stmt
, ref
->is_read
);
4131 gcc_assert (dr
!= NULL
);
4132 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4135 VEC_free (data_ref_loc
, heap
, references
);
4139 /* Search the data references in LOOP, and record the information into
4140 DATAREFS. Returns chrec_dont_know when failing to analyze a
4141 difficult case, returns NULL_TREE otherwise. */
4144 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4145 VEC (data_reference_p
, heap
) **datarefs
)
4147 gimple_stmt_iterator bsi
;
4149 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4151 gimple stmt
= gsi_stmt (bsi
);
4153 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4155 struct data_reference
*res
;
4156 res
= XCNEW (struct data_reference
);
4157 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4159 return chrec_dont_know
;
4166 /* Search the data references in LOOP, and record the information into
4167 DATAREFS. Returns chrec_dont_know when failing to analyze a
4168 difficult case, returns NULL_TREE otherwise.
4170 TODO: This function should be made smarter so that it can handle address
4171 arithmetic as if they were array accesses, etc. */
4174 find_data_references_in_loop (struct loop
*loop
,
4175 VEC (data_reference_p
, heap
) **datarefs
)
4177 basic_block bb
, *bbs
;
4180 bbs
= get_loop_body_in_dom_order (loop
);
4182 for (i
= 0; i
< loop
->num_nodes
; i
++)
4186 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4189 return chrec_dont_know
;
4197 /* Recursive helper function. */
4200 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4202 /* Inner loops of the nest should not contain siblings. Example:
4203 when there are two consecutive loops,
4214 the dependence relation cannot be captured by the distance
4219 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4221 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4225 /* Return false when the LOOP is not well nested. Otherwise return
4226 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4227 contain the loops from the outermost to the innermost, as they will
4228 appear in the classic distance vector. */
4231 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4233 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4235 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4239 /* Returns true when the data dependences have been computed, false otherwise.
4240 Given a loop nest LOOP, the following vectors are returned:
4241 DATAREFS is initialized to all the array elements contained in this loop,
4242 DEPENDENCE_RELATIONS contains the relations between the data references.
4243 Compute read-read and self relations if
4244 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4247 compute_data_dependences_for_loop (struct loop
*loop
,
4248 bool compute_self_and_read_read_dependences
,
4249 VEC (data_reference_p
, heap
) **datarefs
,
4250 VEC (ddr_p
, heap
) **dependence_relations
)
4253 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4255 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4257 /* If the loop nest is not well formed, or one of the data references
4258 is not computable, give up without spending time to compute other
4261 || !find_loop_nest (loop
, &vloops
)
4262 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4264 struct data_dependence_relation
*ddr
;
4266 /* Insert a single relation into dependence_relations:
4268 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4269 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4273 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4274 compute_self_and_read_read_dependences
);
4276 if (dump_file
&& (dump_flags
& TDF_STATS
))
4278 fprintf (dump_file
, "Dependence tester statistics:\n");
4280 fprintf (dump_file
, "Number of dependence tests: %d\n",
4281 dependence_stats
.num_dependence_tests
);
4282 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4283 dependence_stats
.num_dependence_dependent
);
4284 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4285 dependence_stats
.num_dependence_independent
);
4286 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4287 dependence_stats
.num_dependence_undetermined
);
4289 fprintf (dump_file
, "Number of subscript tests: %d\n",
4290 dependence_stats
.num_subscript_tests
);
4291 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4292 dependence_stats
.num_subscript_undetermined
);
4293 fprintf (dump_file
, "Number of same subscript function: %d\n",
4294 dependence_stats
.num_same_subscript_function
);
4296 fprintf (dump_file
, "Number of ziv tests: %d\n",
4297 dependence_stats
.num_ziv
);
4298 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4299 dependence_stats
.num_ziv_dependent
);
4300 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4301 dependence_stats
.num_ziv_independent
);
4302 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4303 dependence_stats
.num_ziv_unimplemented
);
4305 fprintf (dump_file
, "Number of siv tests: %d\n",
4306 dependence_stats
.num_siv
);
4307 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4308 dependence_stats
.num_siv_dependent
);
4309 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4310 dependence_stats
.num_siv_independent
);
4311 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4312 dependence_stats
.num_siv_unimplemented
);
4314 fprintf (dump_file
, "Number of miv tests: %d\n",
4315 dependence_stats
.num_miv
);
4316 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4317 dependence_stats
.num_miv_dependent
);
4318 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4319 dependence_stats
.num_miv_independent
);
4320 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4321 dependence_stats
.num_miv_unimplemented
);
4327 /* Returns true when the data dependences for the basic block BB have been
4328 computed, false otherwise.
4329 DATAREFS is initialized to all the array elements contained in this basic
4330 block, DEPENDENCE_RELATIONS contains the relations between the data
4331 references. Compute read-read and self relations if
4332 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4334 compute_data_dependences_for_bb (basic_block bb
,
4335 bool compute_self_and_read_read_dependences
,
4336 VEC (data_reference_p
, heap
) **datarefs
,
4337 VEC (ddr_p
, heap
) **dependence_relations
)
4339 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4342 compute_all_dependences (*datarefs
, dependence_relations
, NULL
,
4343 compute_self_and_read_read_dependences
);
4347 /* Entry point (for testing only). Analyze all the data references
4348 and the dependence relations in LOOP.
4350 The data references are computed first.
4352 A relation on these nodes is represented by a complete graph. Some
4353 of the relations could be of no interest, thus the relations can be
4356 In the following function we compute all the relations. This is
4357 just a first implementation that is here for:
4358 - for showing how to ask for the dependence relations,
4359 - for the debugging the whole dependence graph,
4360 - for the dejagnu testcases and maintenance.
4362 It is possible to ask only for a part of the graph, avoiding to
4363 compute the whole dependence graph. The computed dependences are
4364 stored in a knowledge base (KB) such that later queries don't
4365 recompute the same information. The implementation of this KB is
4366 transparent to the optimizer, and thus the KB can be changed with a
4367 more efficient implementation, or the KB could be disabled. */
4369 analyze_all_data_dependences (struct loop
*loop
)
4372 int nb_data_refs
= 10;
4373 VEC (data_reference_p
, heap
) *datarefs
=
4374 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4375 VEC (ddr_p
, heap
) *dependence_relations
=
4376 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4378 /* Compute DDs on the whole function. */
4379 compute_data_dependences_for_loop (loop
, false, &datarefs
,
4380 &dependence_relations
);
4384 dump_data_dependence_relations (dump_file
, dependence_relations
);
4385 fprintf (dump_file
, "\n\n");
4387 if (dump_flags
& TDF_DETAILS
)
4388 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4390 if (dump_flags
& TDF_STATS
)
4392 unsigned nb_top_relations
= 0;
4393 unsigned nb_bot_relations
= 0;
4394 unsigned nb_chrec_relations
= 0;
4395 struct data_dependence_relation
*ddr
;
4397 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4399 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4402 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4406 nb_chrec_relations
++;
4409 gather_stats_on_scev_database ();
4413 free_dependence_relations (dependence_relations
);
4414 free_data_refs (datarefs
);
4417 /* Computes all the data dependences and check that the results of
4418 several analyzers are the same. */
4421 tree_check_data_deps (void)
4424 struct loop
*loop_nest
;
4426 FOR_EACH_LOOP (li
, loop_nest
, 0)
4427 analyze_all_data_dependences (loop_nest
);
4430 /* Free the memory used by a data dependence relation DDR. */
4433 free_dependence_relation (struct data_dependence_relation
*ddr
)
4438 if (DDR_SUBSCRIPTS (ddr
))
4439 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4440 if (DDR_DIST_VECTS (ddr
))
4441 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4442 if (DDR_DIR_VECTS (ddr
))
4443 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4448 /* Free the memory used by the data dependence relations from
4449 DEPENDENCE_RELATIONS. */
4452 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4455 struct data_dependence_relation
*ddr
;
4456 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4458 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4462 if (loop_nest
== NULL
)
4463 loop_nest
= DDR_LOOP_NEST (ddr
);
4465 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4466 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4467 free_dependence_relation (ddr
);
4471 VEC_free (loop_p
, heap
, loop_nest
);
4472 VEC_free (ddr_p
, heap
, dependence_relations
);
4475 /* Free the memory used by the data references from DATAREFS. */
4478 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4481 struct data_reference
*dr
;
4483 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
4485 VEC_free (data_reference_p
, heap
, datarefs
);
4490 /* Dump vertex I in RDG to FILE. */
4493 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4495 struct vertex
*v
= &(rdg
->vertices
[i
]);
4496 struct graph_edge
*e
;
4498 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4499 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4500 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4503 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4504 fprintf (file
, " %d", e
->src
);
4506 fprintf (file
, ") (out:");
4509 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4510 fprintf (file
, " %d", e
->dest
);
4512 fprintf (file
, ") \n");
4513 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4514 fprintf (file
, ")\n");
4517 /* Call dump_rdg_vertex on stderr. */
4520 debug_rdg_vertex (struct graph
*rdg
, int i
)
4522 dump_rdg_vertex (stderr
, rdg
, i
);
4525 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4526 dumped vertices to that bitmap. */
4528 void dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4532 fprintf (file
, "(%d\n", c
);
4534 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4535 if (rdg
->vertices
[i
].component
== c
)
4538 bitmap_set_bit (dumped
, i
);
4540 dump_rdg_vertex (file
, rdg
, i
);
4543 fprintf (file
, ")\n");
4546 /* Call dump_rdg_vertex on stderr. */
4549 debug_rdg_component (struct graph
*rdg
, int c
)
4551 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4554 /* Dump the reduced dependence graph RDG to FILE. */
4557 dump_rdg (FILE *file
, struct graph
*rdg
)
4560 bitmap dumped
= BITMAP_ALLOC (NULL
);
4562 fprintf (file
, "(rdg\n");
4564 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4565 if (!bitmap_bit_p (dumped
, i
))
4566 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4568 fprintf (file
, ")\n");
4569 BITMAP_FREE (dumped
);
4572 /* Call dump_rdg on stderr. */
4575 debug_rdg (struct graph
*rdg
)
4577 dump_rdg (stderr
, rdg
);
4581 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
4585 fprintf (file
, "digraph RDG {\n");
4587 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4589 struct vertex
*v
= &(rdg
->vertices
[i
]);
4590 struct graph_edge
*e
;
4592 /* Highlight reads from memory. */
4593 if (RDG_MEM_READS_STMT (rdg
, i
))
4594 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
4596 /* Highlight stores to memory. */
4597 if (RDG_MEM_WRITE_STMT (rdg
, i
))
4598 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
4601 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4602 switch (RDGE_TYPE (e
))
4605 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
4609 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
4613 /* These are the most common dependences: don't print these. */
4614 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
4618 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
4626 fprintf (file
, "}\n\n");
4629 /* Display the Reduced Dependence Graph using dotty. */
4630 extern void dot_rdg (struct graph
*);
4633 dot_rdg (struct graph
*rdg
)
4635 /* When debugging, enable the following code. This cannot be used
4636 in production compilers because it calls "system". */
4638 FILE *file
= fopen ("/tmp/rdg.dot", "w");
4639 gcc_assert (file
!= NULL
);
4641 dot_rdg_1 (file
, rdg
);
4644 system ("dotty /tmp/rdg.dot &");
4646 dot_rdg_1 (stderr
, rdg
);
4650 /* This structure is used for recording the mapping statement index in
4653 struct GTY(()) rdg_vertex_info
4659 /* Returns the index of STMT in RDG. */
4662 rdg_vertex_for_stmt (struct graph
*rdg
, gimple stmt
)
4664 struct rdg_vertex_info rvi
, *slot
;
4667 slot
= (struct rdg_vertex_info
*) htab_find (rdg
->indices
, &rvi
);
4675 /* Creates an edge in RDG for each distance vector from DDR. The
4676 order that we keep track of in the RDG is the order in which
4677 statements have to be executed. */
4680 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4682 struct graph_edge
*e
;
4684 data_reference_p dra
= DDR_A (ddr
);
4685 data_reference_p drb
= DDR_B (ddr
);
4686 unsigned level
= ddr_dependence_level (ddr
);
4688 /* For non scalar dependences, when the dependence is REVERSED,
4689 statement B has to be executed before statement A. */
4691 && !DDR_REVERSED_P (ddr
))
4693 data_reference_p tmp
= dra
;
4698 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4699 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4701 if (va
< 0 || vb
< 0)
4704 e
= add_edge (rdg
, va
, vb
);
4705 e
->data
= XNEW (struct rdg_edge
);
4707 RDGE_LEVEL (e
) = level
;
4708 RDGE_RELATION (e
) = ddr
;
4710 /* Determines the type of the data dependence. */
4711 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4712 RDGE_TYPE (e
) = input_dd
;
4713 else if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
4714 RDGE_TYPE (e
) = output_dd
;
4715 else if (DR_IS_WRITE (dra
) && DR_IS_READ (drb
))
4716 RDGE_TYPE (e
) = flow_dd
;
4717 else if (DR_IS_READ (dra
) && DR_IS_WRITE (drb
))
4718 RDGE_TYPE (e
) = anti_dd
;
4721 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4722 the index of DEF in RDG. */
4725 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4727 use_operand_p imm_use_p
;
4728 imm_use_iterator iterator
;
4730 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4732 struct graph_edge
*e
;
4733 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4738 e
= add_edge (rdg
, idef
, use
);
4739 e
->data
= XNEW (struct rdg_edge
);
4740 RDGE_TYPE (e
) = flow_dd
;
4741 RDGE_RELATION (e
) = NULL
;
4745 /* Creates the edges of the reduced dependence graph RDG. */
4748 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4751 struct data_dependence_relation
*ddr
;
4752 def_operand_p def_p
;
4755 FOR_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
4756 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4757 create_rdg_edge_for_ddr (rdg
, ddr
);
4759 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4760 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4762 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4765 /* Build the vertices of the reduced dependence graph RDG. */
4768 create_rdg_vertices (struct graph
*rdg
, VEC (gimple
, heap
) *stmts
)
4773 FOR_EACH_VEC_ELT (gimple
, stmts
, i
, stmt
)
4775 VEC (data_ref_loc
, heap
) *references
;
4777 struct vertex
*v
= &(rdg
->vertices
[i
]);
4778 struct rdg_vertex_info
*rvi
= XNEW (struct rdg_vertex_info
);
4779 struct rdg_vertex_info
**slot
;
4783 slot
= (struct rdg_vertex_info
**) htab_find_slot (rdg
->indices
, rvi
, INSERT
);
4790 v
->data
= XNEW (struct rdg_vertex
);
4791 RDG_STMT (rdg
, i
) = stmt
;
4793 RDG_MEM_WRITE_STMT (rdg
, i
) = false;
4794 RDG_MEM_READS_STMT (rdg
, i
) = false;
4795 if (gimple_code (stmt
) == GIMPLE_PHI
)
4798 get_references_in_stmt (stmt
, &references
);
4799 FOR_EACH_VEC_ELT (data_ref_loc
, references
, j
, ref
)
4801 RDG_MEM_WRITE_STMT (rdg
, i
) = true;
4803 RDG_MEM_READS_STMT (rdg
, i
) = true;
4805 VEC_free (data_ref_loc
, heap
, references
);
4809 /* Initialize STMTS with all the statements of LOOP. When
4810 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4811 which we discover statements is important as
4812 generate_loops_for_partition is using the same traversal for
4813 identifying statements. */
4816 stmts_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4819 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4821 for (i
= 0; i
< loop
->num_nodes
; i
++)
4823 basic_block bb
= bbs
[i
];
4824 gimple_stmt_iterator bsi
;
4827 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4828 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4830 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4832 stmt
= gsi_stmt (bsi
);
4833 if (gimple_code (stmt
) != GIMPLE_LABEL
)
4834 VEC_safe_push (gimple
, heap
, *stmts
, stmt
);
4841 /* Returns true when all the dependences are computable. */
4844 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
4849 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4850 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4856 /* Computes a hash function for element ELT. */
4859 hash_stmt_vertex_info (const void *elt
)
4861 const struct rdg_vertex_info
*const rvi
=
4862 (const struct rdg_vertex_info
*) elt
;
4863 gimple stmt
= rvi
->stmt
;
4865 return htab_hash_pointer (stmt
);
4868 /* Compares database elements E1 and E2. */
4871 eq_stmt_vertex_info (const void *e1
, const void *e2
)
4873 const struct rdg_vertex_info
*elt1
= (const struct rdg_vertex_info
*) e1
;
4874 const struct rdg_vertex_info
*elt2
= (const struct rdg_vertex_info
*) e2
;
4876 return elt1
->stmt
== elt2
->stmt
;
4879 /* Free the element E. */
4882 hash_stmt_vertex_del (void *e
)
4887 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4888 statement of the loop nest, and one edge per data dependence or
4889 scalar dependence. */
4892 build_empty_rdg (int n_stmts
)
4894 int nb_data_refs
= 10;
4895 struct graph
*rdg
= new_graph (n_stmts
);
4897 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4898 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4902 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4903 statement of the loop nest, and one edge per data dependence or
4904 scalar dependence. */
4907 build_rdg (struct loop
*loop
)
4909 int nb_data_refs
= 10;
4910 struct graph
*rdg
= NULL
;
4911 VEC (ddr_p
, heap
) *dependence_relations
;
4912 VEC (data_reference_p
, heap
) *datarefs
;
4913 VEC (gimple
, heap
) *stmts
= VEC_alloc (gimple
, heap
, nb_data_refs
);
4915 dependence_relations
= VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
) ;
4916 datarefs
= VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4917 compute_data_dependences_for_loop (loop
,
4920 &dependence_relations
);
4922 if (!known_dependences_p (dependence_relations
))
4924 free_dependence_relations (dependence_relations
);
4925 free_data_refs (datarefs
);
4926 VEC_free (gimple
, heap
, stmts
);
4931 stmts_from_loop (loop
, &stmts
);
4932 rdg
= build_empty_rdg (VEC_length (gimple
, stmts
));
4934 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
4935 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
4936 create_rdg_vertices (rdg
, stmts
);
4937 create_rdg_edges (rdg
, dependence_relations
);
4939 VEC_free (gimple
, heap
, stmts
);
4943 /* Free the reduced dependence graph RDG. */
4946 free_rdg (struct graph
*rdg
)
4950 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4951 free (rdg
->vertices
[i
].data
);
4953 htab_delete (rdg
->indices
);
4957 /* Initialize STMTS with all the statements of LOOP that contain a
4961 stores_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
4964 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
4966 for (i
= 0; i
< loop
->num_nodes
; i
++)
4968 basic_block bb
= bbs
[i
];
4969 gimple_stmt_iterator bsi
;
4971 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4972 if (gimple_vdef (gsi_stmt (bsi
)))
4973 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
4979 /* Returns true when STMT is an assignment that contains a data
4980 reference on its LHS with a stride of the same size as its unit
4984 mem_write_stride_of_same_size_as_unit_type_p (gimple stmt
)
4986 struct data_reference
*dr
= XCNEW (struct data_reference
);
4987 tree op0
= gimple_assign_lhs (stmt
);
4990 DR_STMT (dr
) = stmt
;
4993 res
= dr_analyze_innermost (dr
)
4994 && stride_of_unit_type_p (DR_STEP (dr
), TREE_TYPE (op0
));
5000 /* Initialize STMTS with all the statements of LOOP that contain a
5001 store to memory of the form "A[i] = 0". */
5004 stores_zero_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
5008 gimple_stmt_iterator si
;
5011 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
5013 for (i
= 0; i
< loop
->num_nodes
; i
++)
5014 for (bb
= bbs
[i
], si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
5015 if ((stmt
= gsi_stmt (si
))
5016 && gimple_vdef (stmt
)
5017 && is_gimple_assign (stmt
)
5018 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
5019 && (op
= gimple_assign_rhs1 (stmt
))
5020 && (integer_zerop (op
) || real_zerop (op
))
5021 && mem_write_stride_of_same_size_as_unit_type_p (stmt
))
5022 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (si
));
5027 /* For a data reference REF, return the declaration of its base
5028 address or NULL_TREE if the base is not determined. */
5031 ref_base_address (gimple stmt
, data_ref_loc
*ref
)
5033 tree base
= NULL_TREE
;
5035 struct data_reference
*dr
= XCNEW (struct data_reference
);
5037 DR_STMT (dr
) = stmt
;
5038 DR_REF (dr
) = *ref
->pos
;
5039 dr_analyze_innermost (dr
);
5040 base_address
= DR_BASE_ADDRESS (dr
);
5045 switch (TREE_CODE (base_address
))
5048 base
= TREE_OPERAND (base_address
, 0);
5052 base
= base_address
;
5061 /* Determines whether the statement from vertex V of the RDG has a
5062 definition used outside the loop that contains this statement. */
5065 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
5067 gimple stmt
= RDG_STMT (rdg
, v
);
5068 struct loop
*loop
= loop_containing_stmt (stmt
);
5069 use_operand_p imm_use_p
;
5070 imm_use_iterator iterator
;
5072 def_operand_p def_p
;
5077 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
5079 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
5081 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)
5089 /* Determines whether statements S1 and S2 access to similar memory
5090 locations. Two memory accesses are considered similar when they
5091 have the same base address declaration, i.e. when their
5092 ref_base_address is the same. */
5095 have_similar_memory_accesses (gimple s1
, gimple s2
)
5099 VEC (data_ref_loc
, heap
) *refs1
, *refs2
;
5100 data_ref_loc
*ref1
, *ref2
;
5102 get_references_in_stmt (s1
, &refs1
);
5103 get_references_in_stmt (s2
, &refs2
);
5105 FOR_EACH_VEC_ELT (data_ref_loc
, refs1
, i
, ref1
)
5107 tree base1
= ref_base_address (s1
, ref1
);
5110 FOR_EACH_VEC_ELT (data_ref_loc
, refs2
, j
, ref2
)
5111 if (base1
== ref_base_address (s2
, ref2
))
5119 VEC_free (data_ref_loc
, heap
, refs1
);
5120 VEC_free (data_ref_loc
, heap
, refs2
);
5124 /* Helper function for the hashtab. */
5127 have_similar_memory_accesses_1 (const void *s1
, const void *s2
)
5129 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple
) s1
),
5130 CONST_CAST_GIMPLE ((const_gimple
) s2
));
5133 /* Helper function for the hashtab. */
5136 ref_base_address_1 (const void *s
)
5138 gimple stmt
= CONST_CAST_GIMPLE ((const_gimple
) s
);
5140 VEC (data_ref_loc
, heap
) *refs
;
5144 get_references_in_stmt (stmt
, &refs
);
5146 FOR_EACH_VEC_ELT (data_ref_loc
, refs
, i
, ref
)
5149 res
= htab_hash_pointer (ref_base_address (stmt
, ref
));
5153 VEC_free (data_ref_loc
, heap
, refs
);
5157 /* Try to remove duplicated write data references from STMTS. */
5160 remove_similar_memory_refs (VEC (gimple
, heap
) **stmts
)
5164 htab_t seen
= htab_create (VEC_length (gimple
, *stmts
), ref_base_address_1
,
5165 have_similar_memory_accesses_1
, NULL
);
5167 for (i
= 0; VEC_iterate (gimple
, *stmts
, i
, stmt
); )
5171 slot
= htab_find_slot (seen
, stmt
, INSERT
);
5174 VEC_ordered_remove (gimple
, *stmts
, i
);
5177 *slot
= (void *) stmt
;
5185 /* Returns the index of PARAMETER in the parameters vector of the
5186 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5189 access_matrix_get_index_for_parameter (tree parameter
,
5190 struct access_matrix
*access_matrix
)
5193 VEC (tree
,heap
) *lambda_parameters
= AM_PARAMETERS (access_matrix
);
5194 tree lambda_parameter
;
5196 FOR_EACH_VEC_ELT (tree
, lambda_parameters
, i
, lambda_parameter
)
5197 if (lambda_parameter
== parameter
)
5198 return i
+ AM_NB_INDUCTION_VARS (access_matrix
);