1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
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"
80 #include "gimple-pretty-print.h"
81 #include "tree-flow.h"
83 #include "tree-data-ref.h"
84 #include "tree-scalar-evolution.h"
85 #include "tree-pass.h"
86 #include "langhooks.h"
87 #include "tree-affine.h"
90 static struct datadep_stats
92 int num_dependence_tests
;
93 int num_dependence_dependent
;
94 int num_dependence_independent
;
95 int num_dependence_undetermined
;
97 int num_subscript_tests
;
98 int num_subscript_undetermined
;
99 int num_same_subscript_function
;
102 int num_ziv_independent
;
103 int num_ziv_dependent
;
104 int num_ziv_unimplemented
;
107 int num_siv_independent
;
108 int num_siv_dependent
;
109 int num_siv_unimplemented
;
112 int num_miv_independent
;
113 int num_miv_dependent
;
114 int num_miv_unimplemented
;
117 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
118 struct data_reference
*,
119 struct data_reference
*,
121 /* Returns true iff A divides B. */
124 tree_fold_divides_p (const_tree a
, const_tree b
)
126 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
127 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
128 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
));
131 /* Returns true iff A divides B. */
134 int_divides_p (int a
, int b
)
136 return ((b
% a
) == 0);
141 /* Dump into FILE all the data references from DATAREFS. */
144 dump_data_references (FILE *file
, VEC (data_reference_p
, heap
) *datarefs
)
147 struct data_reference
*dr
;
149 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
150 dump_data_reference (file
, dr
);
153 /* Dump into STDERR all the data references from DATAREFS. */
156 debug_data_references (VEC (data_reference_p
, heap
) *datarefs
)
158 dump_data_references (stderr
, datarefs
);
161 /* Dump to STDERR all the dependence relations from DDRS. */
164 debug_data_dependence_relations (VEC (ddr_p
, heap
) *ddrs
)
166 dump_data_dependence_relations (stderr
, ddrs
);
169 /* Dump into FILE all the dependence relations from DDRS. */
172 dump_data_dependence_relations (FILE *file
,
173 VEC (ddr_p
, heap
) *ddrs
)
176 struct data_dependence_relation
*ddr
;
178 FOR_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
179 dump_data_dependence_relation (file
, ddr
);
182 /* Print to STDERR the data_reference DR. */
185 debug_data_reference (struct data_reference
*dr
)
187 dump_data_reference (stderr
, dr
);
190 /* Dump function for a DATA_REFERENCE structure. */
193 dump_data_reference (FILE *outf
,
194 struct data_reference
*dr
)
198 fprintf (outf
, "#(Data Ref: \n");
199 fprintf (outf
, "# bb: %d \n", gimple_bb (DR_STMT (dr
))->index
);
200 fprintf (outf
, "# stmt: ");
201 print_gimple_stmt (outf
, DR_STMT (dr
), 0, 0);
202 fprintf (outf
, "# ref: ");
203 print_generic_stmt (outf
, DR_REF (dr
), 0);
204 fprintf (outf
, "# base_object: ");
205 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
207 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
209 fprintf (outf
, "# Access function %d: ", i
);
210 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
212 fprintf (outf
, "#)\n");
215 /* Dumps the affine function described by FN to the file OUTF. */
218 dump_affine_function (FILE *outf
, affine_fn fn
)
223 print_generic_expr (outf
, VEC_index (tree
, fn
, 0), TDF_SLIM
);
224 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
226 fprintf (outf
, " + ");
227 print_generic_expr (outf
, coef
, TDF_SLIM
);
228 fprintf (outf
, " * x_%u", i
);
232 /* Dumps the conflict function CF to the file OUTF. */
235 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
239 if (cf
->n
== NO_DEPENDENCE
)
240 fprintf (outf
, "no dependence\n");
241 else if (cf
->n
== NOT_KNOWN
)
242 fprintf (outf
, "not known\n");
245 for (i
= 0; i
< cf
->n
; i
++)
248 dump_affine_function (outf
, cf
->fns
[i
]);
249 fprintf (outf
, "]\n");
254 /* Dump function for a SUBSCRIPT structure. */
257 dump_subscript (FILE *outf
, struct subscript
*subscript
)
259 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
261 fprintf (outf
, "\n (subscript \n");
262 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
263 dump_conflict_function (outf
, cf
);
264 if (CF_NONTRIVIAL_P (cf
))
266 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
267 fprintf (outf
, " last_conflict: ");
268 print_generic_stmt (outf
, last_iteration
, 0);
271 cf
= SUB_CONFLICTS_IN_B (subscript
);
272 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
273 dump_conflict_function (outf
, cf
);
274 if (CF_NONTRIVIAL_P (cf
))
276 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
277 fprintf (outf
, " last_conflict: ");
278 print_generic_stmt (outf
, last_iteration
, 0);
281 fprintf (outf
, " (Subscript distance: ");
282 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
283 fprintf (outf
, " )\n");
284 fprintf (outf
, " )\n");
287 /* Print the classic direction vector DIRV to OUTF. */
290 print_direction_vector (FILE *outf
,
296 for (eq
= 0; eq
< length
; eq
++)
298 enum data_dependence_direction dir
= ((enum data_dependence_direction
)
304 fprintf (outf
, " +");
307 fprintf (outf
, " -");
310 fprintf (outf
, " =");
312 case dir_positive_or_equal
:
313 fprintf (outf
, " +=");
315 case dir_positive_or_negative
:
316 fprintf (outf
, " +-");
318 case dir_negative_or_equal
:
319 fprintf (outf
, " -=");
322 fprintf (outf
, " *");
325 fprintf (outf
, "indep");
329 fprintf (outf
, "\n");
332 /* Print a vector of direction vectors. */
335 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
341 FOR_EACH_VEC_ELT (lambda_vector
, dir_vects
, j
, v
)
342 print_direction_vector (outf
, v
, length
);
345 /* Print out a vector VEC of length N to OUTFILE. */
348 print_lambda_vector (FILE * outfile
, lambda_vector vector
, int n
)
352 for (i
= 0; i
< n
; i
++)
353 fprintf (outfile
, "%3d ", vector
[i
]);
354 fprintf (outfile
, "\n");
357 /* Print a vector of distance vectors. */
360 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
366 FOR_EACH_VEC_ELT (lambda_vector
, dist_vects
, j
, v
)
367 print_lambda_vector (outf
, v
, length
);
373 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
375 dump_data_dependence_relation (stderr
, ddr
);
378 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
381 dump_data_dependence_relation (FILE *outf
,
382 struct data_dependence_relation
*ddr
)
384 struct data_reference
*dra
, *drb
;
386 fprintf (outf
, "(Data Dep: \n");
388 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
395 dump_data_reference (outf
, dra
);
397 fprintf (outf
, " (nil)\n");
399 dump_data_reference (outf
, drb
);
401 fprintf (outf
, " (nil)\n");
403 fprintf (outf
, " (don't know)\n)\n");
409 dump_data_reference (outf
, dra
);
410 dump_data_reference (outf
, drb
);
412 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
413 fprintf (outf
, " (no dependence)\n");
415 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
420 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
422 fprintf (outf
, " access_fn_A: ");
423 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
424 fprintf (outf
, " access_fn_B: ");
425 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
426 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
429 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
430 fprintf (outf
, " loop nest: (");
431 FOR_EACH_VEC_ELT (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
)
432 fprintf (outf
, "%d ", loopi
->num
);
433 fprintf (outf
, ")\n");
435 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
437 fprintf (outf
, " distance_vector: ");
438 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
442 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
444 fprintf (outf
, " direction_vector: ");
445 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
450 fprintf (outf
, ")\n");
453 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
456 dump_data_dependence_direction (FILE *file
,
457 enum data_dependence_direction dir
)
473 case dir_positive_or_negative
:
474 fprintf (file
, "+-");
477 case dir_positive_or_equal
:
478 fprintf (file
, "+=");
481 case dir_negative_or_equal
:
482 fprintf (file
, "-=");
494 /* Dumps the distance and direction vectors in FILE. DDRS contains
495 the dependence relations, and VECT_SIZE is the size of the
496 dependence vectors, or in other words the number of loops in the
500 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
503 struct data_dependence_relation
*ddr
;
506 FOR_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
507 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
509 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
)
511 fprintf (file
, "DISTANCE_V (");
512 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
513 fprintf (file
, ")\n");
516 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
)
518 fprintf (file
, "DIRECTION_V (");
519 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
520 fprintf (file
, ")\n");
524 fprintf (file
, "\n\n");
527 /* Dumps the data dependence relations DDRS in FILE. */
530 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
533 struct data_dependence_relation
*ddr
;
535 FOR_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
536 dump_data_dependence_relation (file
, ddr
);
538 fprintf (file
, "\n\n");
541 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
542 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
543 constant of type ssizetype, and returns true. If we cannot do this
544 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
548 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
549 tree
*var
, tree
*off
)
553 enum tree_code ocode
= code
;
561 *var
= build_int_cst (type
, 0);
562 *off
= fold_convert (ssizetype
, op0
);
565 case POINTER_PLUS_EXPR
:
570 split_constant_offset (op0
, &var0
, &off0
);
571 split_constant_offset (op1
, &var1
, &off1
);
572 *var
= fold_build2 (code
, type
, var0
, var1
);
573 *off
= size_binop (ocode
, off0
, off1
);
577 if (TREE_CODE (op1
) != INTEGER_CST
)
580 split_constant_offset (op0
, &var0
, &off0
);
581 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
582 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
588 HOST_WIDE_INT pbitsize
, pbitpos
;
589 enum machine_mode pmode
;
590 int punsignedp
, pvolatilep
;
592 op0
= TREE_OPERAND (op0
, 0);
593 base
= get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
,
594 &pmode
, &punsignedp
, &pvolatilep
, false);
596 if (pbitpos
% BITS_PER_UNIT
!= 0)
598 base
= build_fold_addr_expr (base
);
599 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
603 split_constant_offset (poffset
, &poffset
, &off1
);
604 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
605 if (POINTER_TYPE_P (TREE_TYPE (base
)))
606 base
= fold_build_pointer_plus (base
, poffset
);
608 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
609 fold_convert (TREE_TYPE (base
), poffset
));
612 var0
= fold_convert (type
, base
);
614 /* If variable length types are involved, punt, otherwise casts
615 might be converted into ARRAY_REFs in gimplify_conversion.
616 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
617 possibly no longer appears in current GIMPLE, might resurface.
618 This perhaps could run
619 if (CONVERT_EXPR_P (var0))
621 gimplify_conversion (&var0);
622 // Attempt to fill in any within var0 found ARRAY_REF's
623 // element size from corresponding op embedded ARRAY_REF,
624 // if unsuccessful, just punt.
626 while (POINTER_TYPE_P (type
))
627 type
= TREE_TYPE (type
);
628 if (int_size_in_bytes (type
) < 0)
638 gimple def_stmt
= SSA_NAME_DEF_STMT (op0
);
639 enum tree_code subcode
;
641 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
644 var0
= gimple_assign_rhs1 (def_stmt
);
645 subcode
= gimple_assign_rhs_code (def_stmt
);
646 var1
= gimple_assign_rhs2 (def_stmt
);
648 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
652 /* We must not introduce undefined overflow, and we must not change the value.
653 Hence we're okay if the inner type doesn't overflow to start with
654 (pointer or signed), the outer type also is an integer or pointer
655 and the outer precision is at least as large as the inner. */
656 tree itype
= TREE_TYPE (op0
);
657 if ((POINTER_TYPE_P (itype
)
658 || (INTEGRAL_TYPE_P (itype
) && TYPE_OVERFLOW_UNDEFINED (itype
)))
659 && TYPE_PRECISION (type
) >= TYPE_PRECISION (itype
)
660 && (POINTER_TYPE_P (type
) || INTEGRAL_TYPE_P (type
)))
662 split_constant_offset (op0
, &var0
, off
);
663 *var
= fold_convert (type
, var0
);
674 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
675 will be ssizetype. */
678 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
680 tree type
= TREE_TYPE (exp
), otype
, op0
, op1
, e
, o
;
684 *off
= ssize_int (0);
687 if (tree_is_chrec (exp
)
688 || get_gimple_rhs_class (TREE_CODE (exp
)) == GIMPLE_TERNARY_RHS
)
691 otype
= TREE_TYPE (exp
);
692 code
= TREE_CODE (exp
);
693 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
694 if (split_constant_offset_1 (otype
, op0
, code
, op1
, &e
, &o
))
696 *var
= fold_convert (type
, e
);
701 /* Returns the address ADDR of an object in a canonical shape (without nop
702 casts, and with type of pointer to the object). */
705 canonicalize_base_object_address (tree addr
)
711 /* The base address may be obtained by casting from integer, in that case
713 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
716 if (TREE_CODE (addr
) != ADDR_EXPR
)
719 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
722 /* Analyzes the behavior of the memory reference DR in the innermost loop or
723 basic block that contains it. Returns true if analysis succeed or false
727 dr_analyze_innermost (struct data_reference
*dr
, struct loop
*nest
)
729 gimple stmt
= DR_STMT (dr
);
730 struct loop
*loop
= loop_containing_stmt (stmt
);
731 tree ref
= DR_REF (dr
);
732 HOST_WIDE_INT pbitsize
, pbitpos
;
734 enum machine_mode pmode
;
735 int punsignedp
, pvolatilep
;
736 affine_iv base_iv
, offset_iv
;
737 tree init
, dinit
, step
;
738 bool in_loop
= (loop
&& loop
->num
);
740 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
741 fprintf (dump_file
, "analyze_innermost: ");
743 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
744 &pmode
, &punsignedp
, &pvolatilep
, false);
745 gcc_assert (base
!= NULL_TREE
);
747 if (pbitpos
% BITS_PER_UNIT
!= 0)
749 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
750 fprintf (dump_file
, "failed: bit offset alignment.\n");
754 if (TREE_CODE (base
) == MEM_REF
)
756 if (!integer_zerop (TREE_OPERAND (base
, 1)))
760 double_int moff
= mem_ref_offset (base
);
761 poffset
= double_int_to_tree (sizetype
, moff
);
764 poffset
= size_binop (PLUS_EXPR
, poffset
, TREE_OPERAND (base
, 1));
766 base
= TREE_OPERAND (base
, 0);
769 base
= build_fold_addr_expr (base
);
773 if (!simple_iv (loop
, loop_containing_stmt (stmt
), base
, &base_iv
,
778 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
779 fprintf (dump_file
, "failed: evolution of base is not"
786 base_iv
.step
= ssize_int (0);
787 base_iv
.no_overflow
= true;
794 base_iv
.step
= ssize_int (0);
795 base_iv
.no_overflow
= true;
800 offset_iv
.base
= ssize_int (0);
801 offset_iv
.step
= ssize_int (0);
807 offset_iv
.base
= poffset
;
808 offset_iv
.step
= ssize_int (0);
810 else if (!simple_iv (loop
, loop_containing_stmt (stmt
),
811 poffset
, &offset_iv
, false))
815 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
816 fprintf (dump_file
, "failed: evolution of offset is not"
822 offset_iv
.base
= poffset
;
823 offset_iv
.step
= ssize_int (0);
828 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
829 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
830 init
= size_binop (PLUS_EXPR
, init
, dinit
);
831 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
832 init
= size_binop (PLUS_EXPR
, init
, dinit
);
834 step
= size_binop (PLUS_EXPR
,
835 fold_convert (ssizetype
, base_iv
.step
),
836 fold_convert (ssizetype
, offset_iv
.step
));
838 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
840 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
844 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
846 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
847 fprintf (dump_file
, "success.\n");
852 /* Determines the base object and the list of indices of memory reference
853 DR, analyzed in LOOP and instantiated in loop nest NEST. */
856 dr_analyze_indices (struct data_reference
*dr
, loop_p nest
, loop_p loop
)
858 VEC (tree
, heap
) *access_fns
= NULL
;
860 tree base
, off
, access_fn
;
861 basic_block before_loop
;
863 /* If analyzing a basic-block there are no indices to analyze
864 and thus no access functions. */
867 DR_BASE_OBJECT (dr
) = DR_REF (dr
);
868 DR_ACCESS_FNS (dr
) = NULL
;
873 before_loop
= block_before_loop (nest
);
875 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
876 into a two element array with a constant index. The base is
877 then just the immediate underlying object. */
878 if (TREE_CODE (ref
) == REALPART_EXPR
)
880 ref
= TREE_OPERAND (ref
, 0);
881 VEC_safe_push (tree
, heap
, access_fns
, integer_zero_node
);
883 else if (TREE_CODE (ref
) == IMAGPART_EXPR
)
885 ref
= TREE_OPERAND (ref
, 0);
886 VEC_safe_push (tree
, heap
, access_fns
, integer_one_node
);
889 /* Analyze access functions of dimensions we know to be independent. */
890 while (handled_component_p (ref
))
892 if (TREE_CODE (ref
) == ARRAY_REF
)
894 op
= TREE_OPERAND (ref
, 1);
895 access_fn
= analyze_scalar_evolution (loop
, op
);
896 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
897 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
899 else if (TREE_CODE (ref
) == COMPONENT_REF
900 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref
, 0))) == RECORD_TYPE
)
902 /* For COMPONENT_REFs of records (but not unions!) use the
903 FIELD_DECL offset as constant access function so we can
904 disambiguate a[i].f1 and a[i].f2. */
905 tree off
= component_ref_field_offset (ref
);
906 off
= size_binop (PLUS_EXPR
,
907 size_binop (MULT_EXPR
,
908 fold_convert (bitsizetype
, off
),
909 bitsize_int (BITS_PER_UNIT
)),
910 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1)));
911 VEC_safe_push (tree
, heap
, access_fns
, off
);
914 /* If we have an unhandled component we could not translate
915 to an access function stop analyzing. We have determined
916 our base object in this case. */
919 ref
= TREE_OPERAND (ref
, 0);
922 /* If the address operand of a MEM_REF base has an evolution in the
923 analyzed nest, add it as an additional independent access-function. */
924 if (TREE_CODE (ref
) == MEM_REF
)
926 op
= TREE_OPERAND (ref
, 0);
927 access_fn
= analyze_scalar_evolution (loop
, op
);
928 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
929 if (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
932 tree memoff
= TREE_OPERAND (ref
, 1);
933 base
= initial_condition (access_fn
);
934 orig_type
= TREE_TYPE (base
);
935 STRIP_USELESS_TYPE_CONVERSION (base
);
936 split_constant_offset (base
, &base
, &off
);
937 /* Fold the MEM_REF offset into the evolutions initial
938 value to make more bases comparable. */
939 if (!integer_zerop (memoff
))
941 off
= size_binop (PLUS_EXPR
, off
,
942 fold_convert (ssizetype
, memoff
));
943 memoff
= build_int_cst (TREE_TYPE (memoff
), 0);
945 access_fn
= chrec_replace_initial_condition
946 (access_fn
, fold_convert (orig_type
, off
));
947 /* ??? This is still not a suitable base object for
948 dr_may_alias_p - the base object needs to be an
949 access that covers the object as whole. With
950 an evolution in the pointer this cannot be
952 As a band-aid, mark the access so we can special-case
953 it in dr_may_alias_p. */
954 ref
= fold_build2_loc (EXPR_LOCATION (ref
),
955 MEM_REF
, TREE_TYPE (ref
),
957 DR_UNCONSTRAINED_BASE (dr
) = true;
958 VEC_safe_push (tree
, heap
, access_fns
, access_fn
);
961 else if (DECL_P (ref
))
963 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
964 ref
= build2 (MEM_REF
, TREE_TYPE (ref
),
965 build_fold_addr_expr (ref
),
966 build_int_cst (reference_alias_ptr_type (ref
), 0));
969 DR_BASE_OBJECT (dr
) = ref
;
970 DR_ACCESS_FNS (dr
) = access_fns
;
973 /* Extracts the alias analysis information from the memory reference DR. */
976 dr_analyze_alias (struct data_reference
*dr
)
978 tree ref
= DR_REF (dr
);
979 tree base
= get_base_address (ref
), addr
;
981 if (INDIRECT_REF_P (base
)
982 || TREE_CODE (base
) == MEM_REF
)
984 addr
= TREE_OPERAND (base
, 0);
985 if (TREE_CODE (addr
) == SSA_NAME
)
986 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
990 /* Frees data reference DR. */
993 free_data_ref (data_reference_p dr
)
995 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
999 /* Analyzes memory reference MEMREF accessed in STMT. The reference
1000 is read if IS_READ is true, write otherwise. Returns the
1001 data_reference description of MEMREF. NEST is the outermost loop
1002 in which the reference should be instantiated, LOOP is the loop in
1003 which the data reference should be analyzed. */
1005 struct data_reference
*
1006 create_data_ref (loop_p nest
, loop_p loop
, tree memref
, gimple stmt
,
1009 struct data_reference
*dr
;
1011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1013 fprintf (dump_file
, "Creating dr for ");
1014 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1015 fprintf (dump_file
, "\n");
1018 dr
= XCNEW (struct data_reference
);
1019 DR_STMT (dr
) = stmt
;
1020 DR_REF (dr
) = memref
;
1021 DR_IS_READ (dr
) = is_read
;
1023 dr_analyze_innermost (dr
, nest
);
1024 dr_analyze_indices (dr
, nest
, loop
);
1025 dr_analyze_alias (dr
);
1027 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1030 fprintf (dump_file
, "\tbase_address: ");
1031 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
1032 fprintf (dump_file
, "\n\toffset from base address: ");
1033 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
1034 fprintf (dump_file
, "\n\tconstant offset from base address: ");
1035 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
1036 fprintf (dump_file
, "\n\tstep: ");
1037 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
1038 fprintf (dump_file
, "\n\taligned to: ");
1039 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
1040 fprintf (dump_file
, "\n\tbase_object: ");
1041 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
1042 fprintf (dump_file
, "\n");
1043 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
1045 fprintf (dump_file
, "\tAccess function %d: ", i
);
1046 print_generic_stmt (dump_file
, DR_ACCESS_FN (dr
, i
), TDF_SLIM
);
1053 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1056 dr_equal_offsets_p1 (tree offset1
, tree offset2
)
1060 STRIP_NOPS (offset1
);
1061 STRIP_NOPS (offset2
);
1063 if (offset1
== offset2
)
1066 if (TREE_CODE (offset1
) != TREE_CODE (offset2
)
1067 || (!BINARY_CLASS_P (offset1
) && !UNARY_CLASS_P (offset1
)))
1070 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 0),
1071 TREE_OPERAND (offset2
, 0));
1073 if (!res
|| !BINARY_CLASS_P (offset1
))
1076 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 1),
1077 TREE_OPERAND (offset2
, 1));
1082 /* Check if DRA and DRB have equal offsets. */
1084 dr_equal_offsets_p (struct data_reference
*dra
,
1085 struct data_reference
*drb
)
1087 tree offset1
, offset2
;
1089 offset1
= DR_OFFSET (dra
);
1090 offset2
= DR_OFFSET (drb
);
1092 return dr_equal_offsets_p1 (offset1
, offset2
);
1095 /* Returns true if FNA == FNB. */
1098 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
1100 unsigned i
, n
= VEC_length (tree
, fna
);
1102 if (n
!= VEC_length (tree
, fnb
))
1105 for (i
= 0; i
< n
; i
++)
1106 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
1107 VEC_index (tree
, fnb
, i
), 0))
1113 /* If all the functions in CF are the same, returns one of them,
1114 otherwise returns NULL. */
1117 common_affine_function (conflict_function
*cf
)
1122 if (!CF_NONTRIVIAL_P (cf
))
1127 for (i
= 1; i
< cf
->n
; i
++)
1128 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
1134 /* Returns the base of the affine function FN. */
1137 affine_function_base (affine_fn fn
)
1139 return VEC_index (tree
, fn
, 0);
1142 /* Returns true if FN is a constant. */
1145 affine_function_constant_p (affine_fn fn
)
1150 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
1151 if (!integer_zerop (coef
))
1157 /* Returns true if FN is the zero constant function. */
1160 affine_function_zero_p (affine_fn fn
)
1162 return (integer_zerop (affine_function_base (fn
))
1163 && affine_function_constant_p (fn
));
1166 /* Returns a signed integer type with the largest precision from TA
1170 signed_type_for_types (tree ta
, tree tb
)
1172 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
1173 return signed_type_for (ta
);
1175 return signed_type_for (tb
);
1178 /* Applies operation OP on affine functions FNA and FNB, and returns the
1182 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
1188 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
1190 n
= VEC_length (tree
, fna
);
1191 m
= VEC_length (tree
, fnb
);
1195 n
= VEC_length (tree
, fnb
);
1196 m
= VEC_length (tree
, fna
);
1199 ret
= VEC_alloc (tree
, heap
, m
);
1200 for (i
= 0; i
< n
; i
++)
1202 tree type
= signed_type_for_types (TREE_TYPE (VEC_index (tree
, fna
, i
)),
1203 TREE_TYPE (VEC_index (tree
, fnb
, i
)));
1205 VEC_quick_push (tree
, ret
,
1206 fold_build2 (op
, type
,
1207 VEC_index (tree
, fna
, i
),
1208 VEC_index (tree
, fnb
, i
)));
1211 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
1212 VEC_quick_push (tree
, ret
,
1213 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1214 coef
, integer_zero_node
));
1215 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
1216 VEC_quick_push (tree
, ret
,
1217 fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1218 integer_zero_node
, coef
));
1223 /* Returns the sum of affine functions FNA and FNB. */
1226 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1228 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1231 /* Returns the difference of affine functions FNA and FNB. */
1234 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1236 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1239 /* Frees affine function FN. */
1242 affine_fn_free (affine_fn fn
)
1244 VEC_free (tree
, heap
, fn
);
1247 /* Determine for each subscript in the data dependence relation DDR
1251 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1253 conflict_function
*cf_a
, *cf_b
;
1254 affine_fn fn_a
, fn_b
, diff
;
1256 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1260 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1262 struct subscript
*subscript
;
1264 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1265 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1266 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1268 fn_a
= common_affine_function (cf_a
);
1269 fn_b
= common_affine_function (cf_b
);
1272 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1275 diff
= affine_fn_minus (fn_a
, fn_b
);
1277 if (affine_function_constant_p (diff
))
1278 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1280 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1282 affine_fn_free (diff
);
1287 /* Returns the conflict function for "unknown". */
1289 static conflict_function
*
1290 conflict_fn_not_known (void)
1292 conflict_function
*fn
= XCNEW (conflict_function
);
1298 /* Returns the conflict function for "independent". */
1300 static conflict_function
*
1301 conflict_fn_no_dependence (void)
1303 conflict_function
*fn
= XCNEW (conflict_function
);
1304 fn
->n
= NO_DEPENDENCE
;
1309 /* Returns true if the address of OBJ is invariant in LOOP. */
1312 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1314 while (handled_component_p (obj
))
1316 if (TREE_CODE (obj
) == ARRAY_REF
)
1318 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1319 need to check the stride and the lower bound of the reference. */
1320 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1322 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1326 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1328 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1332 obj
= TREE_OPERAND (obj
, 0);
1335 if (!INDIRECT_REF_P (obj
)
1336 && TREE_CODE (obj
) != MEM_REF
)
1339 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1343 /* Returns false if we can prove that data references A and B do not alias,
1344 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1348 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
,
1351 tree addr_a
= DR_BASE_OBJECT (a
);
1352 tree addr_b
= DR_BASE_OBJECT (b
);
1354 /* If we are not processing a loop nest but scalar code we
1355 do not need to care about possible cross-iteration dependences
1356 and thus can process the full original reference. Do so,
1357 similar to how loop invariant motion applies extra offset-based
1361 aff_tree off1
, off2
;
1362 double_int size1
, size2
;
1363 get_inner_reference_aff (DR_REF (a
), &off1
, &size1
);
1364 get_inner_reference_aff (DR_REF (b
), &off2
, &size2
);
1365 aff_combination_scale (&off1
, double_int_minus_one
);
1366 aff_combination_add (&off2
, &off1
);
1367 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1371 /* If we had an evolution in a MEM_REF BASE_OBJECT we do not know
1372 the size of the base-object. So we cannot do any offset/overlap
1373 based analysis but have to rely on points-to information only. */
1374 if (TREE_CODE (addr_a
) == MEM_REF
1375 && DR_UNCONSTRAINED_BASE (a
))
1377 if (TREE_CODE (addr_b
) == MEM_REF
1378 && DR_UNCONSTRAINED_BASE (b
))
1379 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1380 TREE_OPERAND (addr_b
, 0));
1382 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1383 build_fold_addr_expr (addr_b
));
1385 else if (TREE_CODE (addr_b
) == MEM_REF
1386 && DR_UNCONSTRAINED_BASE (b
))
1387 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a
),
1388 TREE_OPERAND (addr_b
, 0));
1390 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
1391 that is being subsetted in the loop nest. */
1392 if (DR_IS_WRITE (a
) && DR_IS_WRITE (b
))
1393 return refs_output_dependent_p (addr_a
, addr_b
);
1394 else if (DR_IS_READ (a
) && DR_IS_WRITE (b
))
1395 return refs_anti_dependent_p (addr_a
, addr_b
);
1396 return refs_may_alias_p (addr_a
, addr_b
);
1399 /* Initialize a data dependence relation between data accesses A and
1400 B. NB_LOOPS is the number of loops surrounding the references: the
1401 size of the classic distance/direction vectors. */
1403 struct data_dependence_relation
*
1404 initialize_data_dependence_relation (struct data_reference
*a
,
1405 struct data_reference
*b
,
1406 VEC (loop_p
, heap
) *loop_nest
)
1408 struct data_dependence_relation
*res
;
1411 res
= XNEW (struct data_dependence_relation
);
1414 DDR_LOOP_NEST (res
) = NULL
;
1415 DDR_REVERSED_P (res
) = false;
1416 DDR_SUBSCRIPTS (res
) = NULL
;
1417 DDR_DIR_VECTS (res
) = NULL
;
1418 DDR_DIST_VECTS (res
) = NULL
;
1420 if (a
== NULL
|| b
== NULL
)
1422 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1426 /* If the data references do not alias, then they are independent. */
1427 if (!dr_may_alias_p (a
, b
, loop_nest
!= NULL
))
1429 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1433 /* The case where the references are exactly the same. */
1434 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1437 && !object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1438 DR_BASE_OBJECT (a
)))
1440 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1443 DDR_AFFINE_P (res
) = true;
1444 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1445 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1446 DDR_LOOP_NEST (res
) = loop_nest
;
1447 DDR_INNER_LOOP (res
) = 0;
1448 DDR_SELF_REFERENCE (res
) = true;
1449 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1451 struct subscript
*subscript
;
1453 subscript
= XNEW (struct subscript
);
1454 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1455 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1456 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1457 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1458 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1463 /* If the references do not access the same object, we do not know
1464 whether they alias or not. */
1465 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1467 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1471 /* If the base of the object is not invariant in the loop nest, we cannot
1472 analyze it. TODO -- in fact, it would suffice to record that there may
1473 be arbitrary dependences in the loops where the base object varies. */
1475 && !object_address_invariant_in_loop_p (VEC_index (loop_p
, loop_nest
, 0),
1476 DR_BASE_OBJECT (a
)))
1478 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1482 /* If the number of dimensions of the access to not agree we can have
1483 a pointer access to a component of the array element type and an
1484 array access while the base-objects are still the same. Punt. */
1485 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
1487 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1491 DDR_AFFINE_P (res
) = true;
1492 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1493 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
1494 DDR_LOOP_NEST (res
) = loop_nest
;
1495 DDR_INNER_LOOP (res
) = 0;
1496 DDR_SELF_REFERENCE (res
) = false;
1498 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1500 struct subscript
*subscript
;
1502 subscript
= XNEW (struct subscript
);
1503 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1504 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1505 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1506 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1507 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
1513 /* Frees memory used by the conflict function F. */
1516 free_conflict_function (conflict_function
*f
)
1520 if (CF_NONTRIVIAL_P (f
))
1522 for (i
= 0; i
< f
->n
; i
++)
1523 affine_fn_free (f
->fns
[i
]);
1528 /* Frees memory used by SUBSCRIPTS. */
1531 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
1536 FOR_EACH_VEC_ELT (subscript_p
, subscripts
, i
, s
)
1538 free_conflict_function (s
->conflicting_iterations_in_a
);
1539 free_conflict_function (s
->conflicting_iterations_in_b
);
1542 VEC_free (subscript_p
, heap
, subscripts
);
1545 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1549 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1552 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1554 fprintf (dump_file
, "(dependence classified: ");
1555 print_generic_expr (dump_file
, chrec
, 0);
1556 fprintf (dump_file
, ")\n");
1559 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1560 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1561 DDR_SUBSCRIPTS (ddr
) = NULL
;
1564 /* The dependence relation DDR cannot be represented by a distance
1568 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1570 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1571 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1573 DDR_AFFINE_P (ddr
) = false;
1578 /* This section contains the classic Banerjee tests. */
1580 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1581 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1584 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1586 return (evolution_function_is_constant_p (chrec_a
)
1587 && evolution_function_is_constant_p (chrec_b
));
1590 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1591 variable, i.e., if the SIV (Single Index Variable) test is true. */
1594 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1596 if ((evolution_function_is_constant_p (chrec_a
)
1597 && evolution_function_is_univariate_p (chrec_b
))
1598 || (evolution_function_is_constant_p (chrec_b
)
1599 && evolution_function_is_univariate_p (chrec_a
)))
1602 if (evolution_function_is_univariate_p (chrec_a
)
1603 && evolution_function_is_univariate_p (chrec_b
))
1605 switch (TREE_CODE (chrec_a
))
1607 case POLYNOMIAL_CHREC
:
1608 switch (TREE_CODE (chrec_b
))
1610 case POLYNOMIAL_CHREC
:
1611 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1626 /* Creates a conflict function with N dimensions. The affine functions
1627 in each dimension follow. */
1629 static conflict_function
*
1630 conflict_fn (unsigned n
, ...)
1633 conflict_function
*ret
= XCNEW (conflict_function
);
1636 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1640 for (i
= 0; i
< n
; i
++)
1641 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1647 /* Returns constant affine function with value CST. */
1650 affine_fn_cst (tree cst
)
1652 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
1653 VEC_quick_push (tree
, fn
, cst
);
1657 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1660 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1662 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
1665 gcc_assert (dim
> 0);
1666 VEC_quick_push (tree
, fn
, cst
);
1667 for (i
= 1; i
< dim
; i
++)
1668 VEC_quick_push (tree
, fn
, integer_zero_node
);
1669 VEC_quick_push (tree
, fn
, coef
);
1673 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1674 *OVERLAPS_B are initialized to the functions that describe the
1675 relation between the elements accessed twice by CHREC_A and
1676 CHREC_B. For k >= 0, the following property is verified:
1678 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1681 analyze_ziv_subscript (tree chrec_a
,
1683 conflict_function
**overlaps_a
,
1684 conflict_function
**overlaps_b
,
1685 tree
*last_conflicts
)
1687 tree type
, difference
;
1688 dependence_stats
.num_ziv
++;
1690 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1691 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1693 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1694 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1695 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1696 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1698 switch (TREE_CODE (difference
))
1701 if (integer_zerop (difference
))
1703 /* The difference is equal to zero: the accessed index
1704 overlaps for each iteration in the loop. */
1705 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1706 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1707 *last_conflicts
= chrec_dont_know
;
1708 dependence_stats
.num_ziv_dependent
++;
1712 /* The accesses do not overlap. */
1713 *overlaps_a
= conflict_fn_no_dependence ();
1714 *overlaps_b
= conflict_fn_no_dependence ();
1715 *last_conflicts
= integer_zero_node
;
1716 dependence_stats
.num_ziv_independent
++;
1721 /* We're not sure whether the indexes overlap. For the moment,
1722 conservatively answer "don't know". */
1723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1724 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1726 *overlaps_a
= conflict_fn_not_known ();
1727 *overlaps_b
= conflict_fn_not_known ();
1728 *last_conflicts
= chrec_dont_know
;
1729 dependence_stats
.num_ziv_unimplemented
++;
1733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1734 fprintf (dump_file
, ")\n");
1737 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1738 and only if it fits to the int type. If this is not the case, or the
1739 bound on the number of iterations of LOOP could not be derived, returns
1743 max_stmt_executions_tree (struct loop
*loop
)
1747 if (!max_stmt_executions (loop
, true, &nit
))
1748 return chrec_dont_know
;
1750 if (!double_int_fits_to_tree_p (unsigned_type_node
, nit
))
1751 return chrec_dont_know
;
1753 return double_int_to_tree (unsigned_type_node
, nit
);
1756 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1757 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1758 *OVERLAPS_B are initialized to the functions that describe the
1759 relation between the elements accessed twice by CHREC_A and
1760 CHREC_B. For k >= 0, the following property is verified:
1762 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1765 analyze_siv_subscript_cst_affine (tree chrec_a
,
1767 conflict_function
**overlaps_a
,
1768 conflict_function
**overlaps_b
,
1769 tree
*last_conflicts
)
1771 bool value0
, value1
, value2
;
1772 tree type
, difference
, tmp
;
1774 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1775 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1776 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1777 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1779 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1781 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1782 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1784 dependence_stats
.num_siv_unimplemented
++;
1785 *overlaps_a
= conflict_fn_not_known ();
1786 *overlaps_b
= conflict_fn_not_known ();
1787 *last_conflicts
= chrec_dont_know
;
1792 if (value0
== false)
1794 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1797 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1799 *overlaps_a
= conflict_fn_not_known ();
1800 *overlaps_b
= conflict_fn_not_known ();
1801 *last_conflicts
= chrec_dont_know
;
1802 dependence_stats
.num_siv_unimplemented
++;
1811 chrec_b = {10, +, 1}
1814 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1816 HOST_WIDE_INT numiter
;
1817 struct loop
*loop
= get_chrec_loop (chrec_b
);
1819 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1820 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1821 fold_build1 (ABS_EXPR
, type
, difference
),
1822 CHREC_RIGHT (chrec_b
));
1823 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1824 *last_conflicts
= integer_one_node
;
1827 /* Perform weak-zero siv test to see if overlap is
1828 outside the loop bounds. */
1829 numiter
= max_stmt_executions_int (loop
, true);
1832 && compare_tree_int (tmp
, numiter
) > 0)
1834 free_conflict_function (*overlaps_a
);
1835 free_conflict_function (*overlaps_b
);
1836 *overlaps_a
= conflict_fn_no_dependence ();
1837 *overlaps_b
= conflict_fn_no_dependence ();
1838 *last_conflicts
= integer_zero_node
;
1839 dependence_stats
.num_siv_independent
++;
1842 dependence_stats
.num_siv_dependent
++;
1846 /* When the step does not divide the difference, there are
1850 *overlaps_a
= conflict_fn_no_dependence ();
1851 *overlaps_b
= conflict_fn_no_dependence ();
1852 *last_conflicts
= integer_zero_node
;
1853 dependence_stats
.num_siv_independent
++;
1862 chrec_b = {10, +, -1}
1864 In this case, chrec_a will not overlap with chrec_b. */
1865 *overlaps_a
= conflict_fn_no_dependence ();
1866 *overlaps_b
= conflict_fn_no_dependence ();
1867 *last_conflicts
= integer_zero_node
;
1868 dependence_stats
.num_siv_independent
++;
1875 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1877 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1878 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1880 *overlaps_a
= conflict_fn_not_known ();
1881 *overlaps_b
= conflict_fn_not_known ();
1882 *last_conflicts
= chrec_dont_know
;
1883 dependence_stats
.num_siv_unimplemented
++;
1888 if (value2
== false)
1892 chrec_b = {10, +, -1}
1894 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1896 HOST_WIDE_INT numiter
;
1897 struct loop
*loop
= get_chrec_loop (chrec_b
);
1899 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1900 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1901 CHREC_RIGHT (chrec_b
));
1902 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1903 *last_conflicts
= integer_one_node
;
1905 /* Perform weak-zero siv test to see if overlap is
1906 outside the loop bounds. */
1907 numiter
= max_stmt_executions_int (loop
, true);
1910 && compare_tree_int (tmp
, numiter
) > 0)
1912 free_conflict_function (*overlaps_a
);
1913 free_conflict_function (*overlaps_b
);
1914 *overlaps_a
= conflict_fn_no_dependence ();
1915 *overlaps_b
= conflict_fn_no_dependence ();
1916 *last_conflicts
= integer_zero_node
;
1917 dependence_stats
.num_siv_independent
++;
1920 dependence_stats
.num_siv_dependent
++;
1924 /* When the step does not divide the difference, there
1928 *overlaps_a
= conflict_fn_no_dependence ();
1929 *overlaps_b
= conflict_fn_no_dependence ();
1930 *last_conflicts
= integer_zero_node
;
1931 dependence_stats
.num_siv_independent
++;
1941 In this case, chrec_a will not overlap with chrec_b. */
1942 *overlaps_a
= conflict_fn_no_dependence ();
1943 *overlaps_b
= conflict_fn_no_dependence ();
1944 *last_conflicts
= integer_zero_node
;
1945 dependence_stats
.num_siv_independent
++;
1953 /* Helper recursive function for initializing the matrix A. Returns
1954 the initial value of CHREC. */
1957 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1961 switch (TREE_CODE (chrec
))
1963 case POLYNOMIAL_CHREC
:
1964 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
1966 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1967 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1973 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1974 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
1976 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
1981 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1982 return chrec_convert (chrec_type (chrec
), op
, NULL
);
1987 /* Handle ~X as -1 - X. */
1988 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
1989 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
1990 build_int_cst (TREE_TYPE (chrec
), -1), op
);
2002 #define FLOOR_DIV(x,y) ((x) / (y))
2004 /* Solves the special case of the Diophantine equation:
2005 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2007 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2008 number of iterations that loops X and Y run. The overlaps will be
2009 constructed as evolutions in dimension DIM. */
2012 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
2013 affine_fn
*overlaps_a
,
2014 affine_fn
*overlaps_b
,
2015 tree
*last_conflicts
, int dim
)
2017 if (((step_a
> 0 && step_b
> 0)
2018 || (step_a
< 0 && step_b
< 0)))
2020 int step_overlaps_a
, step_overlaps_b
;
2021 int gcd_steps_a_b
, last_conflict
, tau2
;
2023 gcd_steps_a_b
= gcd (step_a
, step_b
);
2024 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2025 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2029 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2030 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2031 last_conflict
= tau2
;
2032 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2035 *last_conflicts
= chrec_dont_know
;
2037 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
2038 build_int_cst (NULL_TREE
,
2040 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
2041 build_int_cst (NULL_TREE
,
2047 *overlaps_a
= affine_fn_cst (integer_zero_node
);
2048 *overlaps_b
= affine_fn_cst (integer_zero_node
);
2049 *last_conflicts
= integer_zero_node
;
2053 /* Solves the special case of a Diophantine equation where CHREC_A is
2054 an affine bivariate function, and CHREC_B is an affine univariate
2055 function. For example,
2057 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2059 has the following overlapping functions:
2061 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2062 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2063 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2065 FORNOW: This is a specialized implementation for a case occurring in
2066 a common benchmark. Implement the general algorithm. */
2069 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2070 conflict_function
**overlaps_a
,
2071 conflict_function
**overlaps_b
,
2072 tree
*last_conflicts
)
2074 bool xz_p
, yz_p
, xyz_p
;
2075 int step_x
, step_y
, step_z
;
2076 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
2077 affine_fn overlaps_a_xz
, overlaps_b_xz
;
2078 affine_fn overlaps_a_yz
, overlaps_b_yz
;
2079 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
2080 affine_fn ova1
, ova2
, ovb
;
2081 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
2083 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2084 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2085 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2088 max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a
)), true);
2089 niter_y
= max_stmt_executions_int (get_chrec_loop (chrec_a
), true);
2090 niter_z
= max_stmt_executions_int (get_chrec_loop (chrec_b
), true);
2092 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2094 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2095 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2097 *overlaps_a
= conflict_fn_not_known ();
2098 *overlaps_b
= conflict_fn_not_known ();
2099 *last_conflicts
= chrec_dont_know
;
2103 niter
= MIN (niter_x
, niter_z
);
2104 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2107 &last_conflicts_xz
, 1);
2108 niter
= MIN (niter_y
, niter_z
);
2109 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2112 &last_conflicts_yz
, 2);
2113 niter
= MIN (niter_x
, niter_z
);
2114 niter
= MIN (niter_y
, niter
);
2115 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2118 &last_conflicts_xyz
, 3);
2120 xz_p
= !integer_zerop (last_conflicts_xz
);
2121 yz_p
= !integer_zerop (last_conflicts_yz
);
2122 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2124 if (xz_p
|| yz_p
|| xyz_p
)
2126 ova1
= affine_fn_cst (integer_zero_node
);
2127 ova2
= affine_fn_cst (integer_zero_node
);
2128 ovb
= affine_fn_cst (integer_zero_node
);
2131 affine_fn t0
= ova1
;
2134 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2135 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2136 affine_fn_free (t0
);
2137 affine_fn_free (t2
);
2138 *last_conflicts
= last_conflicts_xz
;
2142 affine_fn t0
= ova2
;
2145 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2146 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2147 affine_fn_free (t0
);
2148 affine_fn_free (t2
);
2149 *last_conflicts
= last_conflicts_yz
;
2153 affine_fn t0
= ova1
;
2154 affine_fn t2
= ova2
;
2157 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2158 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2159 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2160 affine_fn_free (t0
);
2161 affine_fn_free (t2
);
2162 affine_fn_free (t4
);
2163 *last_conflicts
= last_conflicts_xyz
;
2165 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2166 *overlaps_b
= conflict_fn (1, ovb
);
2170 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2171 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2172 *last_conflicts
= integer_zero_node
;
2175 affine_fn_free (overlaps_a_xz
);
2176 affine_fn_free (overlaps_b_xz
);
2177 affine_fn_free (overlaps_a_yz
);
2178 affine_fn_free (overlaps_b_yz
);
2179 affine_fn_free (overlaps_a_xyz
);
2180 affine_fn_free (overlaps_b_xyz
);
2183 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2186 lambda_vector_copy (lambda_vector vec1
, lambda_vector vec2
,
2189 memcpy (vec2
, vec1
, size
* sizeof (*vec1
));
2192 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2195 lambda_matrix_copy (lambda_matrix mat1
, lambda_matrix mat2
,
2200 for (i
= 0; i
< m
; i
++)
2201 lambda_vector_copy (mat1
[i
], mat2
[i
], n
);
2204 /* Store the N x N identity matrix in MAT. */
2207 lambda_matrix_id (lambda_matrix mat
, int size
)
2211 for (i
= 0; i
< size
; i
++)
2212 for (j
= 0; j
< size
; j
++)
2213 mat
[i
][j
] = (i
== j
) ? 1 : 0;
2216 /* Return the first nonzero element of vector VEC1 between START and N.
2217 We must have START <= N. Returns N if VEC1 is the zero vector. */
2220 lambda_vector_first_nz (lambda_vector vec1
, int n
, int start
)
2223 while (j
< n
&& vec1
[j
] == 0)
2228 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2229 R2 = R2 + CONST1 * R1. */
2232 lambda_matrix_row_add (lambda_matrix mat
, int n
, int r1
, int r2
, int const1
)
2239 for (i
= 0; i
< n
; i
++)
2240 mat
[r2
][i
] += const1
* mat
[r1
][i
];
2243 /* Swap rows R1 and R2 in matrix MAT. */
2246 lambda_matrix_row_exchange (lambda_matrix mat
, int r1
, int r2
)
2255 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2256 and store the result in VEC2. */
2259 lambda_vector_mult_const (lambda_vector vec1
, lambda_vector vec2
,
2260 int size
, int const1
)
2265 lambda_vector_clear (vec2
, size
);
2267 for (i
= 0; i
< size
; i
++)
2268 vec2
[i
] = const1
* vec1
[i
];
2271 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2274 lambda_vector_negate (lambda_vector vec1
, lambda_vector vec2
,
2277 lambda_vector_mult_const (vec1
, vec2
, size
, -1);
2280 /* Negate row R1 of matrix MAT which has N columns. */
2283 lambda_matrix_row_negate (lambda_matrix mat
, int n
, int r1
)
2285 lambda_vector_negate (mat
[r1
], mat
[r1
], n
);
2288 /* Return true if two vectors are equal. */
2291 lambda_vector_equal (lambda_vector vec1
, lambda_vector vec2
, int size
)
2294 for (i
= 0; i
< size
; i
++)
2295 if (vec1
[i
] != vec2
[i
])
2300 /* Given an M x N integer matrix A, this function determines an M x
2301 M unimodular matrix U, and an M x N echelon matrix S such that
2302 "U.A = S". This decomposition is also known as "right Hermite".
2304 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2305 Restructuring Compilers" Utpal Banerjee. */
2308 lambda_matrix_right_hermite (lambda_matrix A
, int m
, int n
,
2309 lambda_matrix S
, lambda_matrix U
)
2313 lambda_matrix_copy (A
, S
, m
, n
);
2314 lambda_matrix_id (U
, m
);
2316 for (j
= 0; j
< n
; j
++)
2318 if (lambda_vector_first_nz (S
[j
], m
, i0
) < m
)
2321 for (i
= m
- 1; i
>= i0
; i
--)
2323 while (S
[i
][j
] != 0)
2325 int sigma
, factor
, a
, b
;
2329 sigma
= (a
* b
< 0) ? -1: 1;
2332 factor
= sigma
* (a
/ b
);
2334 lambda_matrix_row_add (S
, n
, i
, i
-1, -factor
);
2335 lambda_matrix_row_exchange (S
, i
, i
-1);
2337 lambda_matrix_row_add (U
, m
, i
, i
-1, -factor
);
2338 lambda_matrix_row_exchange (U
, i
, i
-1);
2345 /* Determines the overlapping elements due to accesses CHREC_A and
2346 CHREC_B, that are affine functions. This function cannot handle
2347 symbolic evolution functions, ie. when initial conditions are
2348 parameters, because it uses lambda matrices of integers. */
2351 analyze_subscript_affine_affine (tree chrec_a
,
2353 conflict_function
**overlaps_a
,
2354 conflict_function
**overlaps_b
,
2355 tree
*last_conflicts
)
2357 unsigned nb_vars_a
, nb_vars_b
, dim
;
2358 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2359 lambda_matrix A
, U
, S
;
2360 struct obstack scratch_obstack
;
2362 if (eq_evolutions_p (chrec_a
, chrec_b
))
2364 /* The accessed index overlaps for each iteration in the
2366 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2367 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2368 *last_conflicts
= chrec_dont_know
;
2371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2372 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2374 /* For determining the initial intersection, we have to solve a
2375 Diophantine equation. This is the most time consuming part.
2377 For answering to the question: "Is there a dependence?" we have
2378 to prove that there exists a solution to the Diophantine
2379 equation, and that the solution is in the iteration domain,
2380 i.e. the solution is positive or zero, and that the solution
2381 happens before the upper bound loop.nb_iterations. Otherwise
2382 there is no dependence. This function outputs a description of
2383 the iterations that hold the intersections. */
2385 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2386 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2388 gcc_obstack_init (&scratch_obstack
);
2390 dim
= nb_vars_a
+ nb_vars_b
;
2391 U
= lambda_matrix_new (dim
, dim
, &scratch_obstack
);
2392 A
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2393 S
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2395 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2396 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2397 gamma
= init_b
- init_a
;
2399 /* Don't do all the hard work of solving the Diophantine equation
2400 when we already know the solution: for example,
2403 | gamma = 3 - 3 = 0.
2404 Then the first overlap occurs during the first iterations:
2405 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2409 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2411 HOST_WIDE_INT step_a
, step_b
;
2412 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2415 niter_a
= max_stmt_executions_int (get_chrec_loop (chrec_a
), true);
2416 niter_b
= max_stmt_executions_int (get_chrec_loop (chrec_b
), true);
2417 niter
= MIN (niter_a
, niter_b
);
2418 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2419 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2421 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2424 *overlaps_a
= conflict_fn (1, ova
);
2425 *overlaps_b
= conflict_fn (1, ovb
);
2428 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2429 compute_overlap_steps_for_affine_1_2
2430 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2432 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2433 compute_overlap_steps_for_affine_1_2
2434 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2439 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2440 *overlaps_a
= conflict_fn_not_known ();
2441 *overlaps_b
= conflict_fn_not_known ();
2442 *last_conflicts
= chrec_dont_know
;
2444 goto end_analyze_subs_aa
;
2448 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2453 lambda_matrix_row_negate (U
, dim
, 0);
2455 gcd_alpha_beta
= S
[0][0];
2457 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2458 but that is a quite strange case. Instead of ICEing, answer
2460 if (gcd_alpha_beta
== 0)
2462 *overlaps_a
= conflict_fn_not_known ();
2463 *overlaps_b
= conflict_fn_not_known ();
2464 *last_conflicts
= chrec_dont_know
;
2465 goto end_analyze_subs_aa
;
2468 /* The classic "gcd-test". */
2469 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2471 /* The "gcd-test" has determined that there is no integer
2472 solution, i.e. there is no dependence. */
2473 *overlaps_a
= conflict_fn_no_dependence ();
2474 *overlaps_b
= conflict_fn_no_dependence ();
2475 *last_conflicts
= integer_zero_node
;
2478 /* Both access functions are univariate. This includes SIV and MIV cases. */
2479 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2481 /* Both functions should have the same evolution sign. */
2482 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2483 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2485 /* The solutions are given by:
2487 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2490 For a given integer t. Using the following variables,
2492 | i0 = u11 * gamma / gcd_alpha_beta
2493 | j0 = u12 * gamma / gcd_alpha_beta
2500 | y0 = j0 + j1 * t. */
2501 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2503 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2504 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2508 if ((i1
== 0 && i0
< 0)
2509 || (j1
== 0 && j0
< 0))
2511 /* There is no solution.
2512 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2513 falls in here, but for the moment we don't look at the
2514 upper bound of the iteration domain. */
2515 *overlaps_a
= conflict_fn_no_dependence ();
2516 *overlaps_b
= conflict_fn_no_dependence ();
2517 *last_conflicts
= integer_zero_node
;
2518 goto end_analyze_subs_aa
;
2521 if (i1
> 0 && j1
> 0)
2523 HOST_WIDE_INT niter_a
= max_stmt_executions_int
2524 (get_chrec_loop (chrec_a
), true);
2525 HOST_WIDE_INT niter_b
= max_stmt_executions_int
2526 (get_chrec_loop (chrec_b
), true);
2527 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2529 /* (X0, Y0) is a solution of the Diophantine equation:
2530 "chrec_a (X0) = chrec_b (Y0)". */
2531 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2533 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2534 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2536 /* (X1, Y1) is the smallest positive solution of the eq
2537 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2538 first conflict occurs. */
2539 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2540 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2541 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2545 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2546 FLOOR_DIV (niter
- j0
, j1
));
2547 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2549 /* If the overlap occurs outside of the bounds of the
2550 loop, there is no dependence. */
2551 if (x1
>= niter
|| y1
>= niter
)
2553 *overlaps_a
= conflict_fn_no_dependence ();
2554 *overlaps_b
= conflict_fn_no_dependence ();
2555 *last_conflicts
= integer_zero_node
;
2556 goto end_analyze_subs_aa
;
2559 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2562 *last_conflicts
= chrec_dont_know
;
2566 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2568 build_int_cst (NULL_TREE
, i1
)));
2571 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2573 build_int_cst (NULL_TREE
, j1
)));
2577 /* FIXME: For the moment, the upper bound of the
2578 iteration domain for i and j is not checked. */
2579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2580 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2581 *overlaps_a
= conflict_fn_not_known ();
2582 *overlaps_b
= conflict_fn_not_known ();
2583 *last_conflicts
= chrec_dont_know
;
2588 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2589 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2590 *overlaps_a
= conflict_fn_not_known ();
2591 *overlaps_b
= conflict_fn_not_known ();
2592 *last_conflicts
= chrec_dont_know
;
2597 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2598 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2599 *overlaps_a
= conflict_fn_not_known ();
2600 *overlaps_b
= conflict_fn_not_known ();
2601 *last_conflicts
= chrec_dont_know
;
2604 end_analyze_subs_aa
:
2605 obstack_free (&scratch_obstack
, NULL
);
2606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2608 fprintf (dump_file
, " (overlaps_a = ");
2609 dump_conflict_function (dump_file
, *overlaps_a
);
2610 fprintf (dump_file
, ")\n (overlaps_b = ");
2611 dump_conflict_function (dump_file
, *overlaps_b
);
2612 fprintf (dump_file
, ")\n");
2613 fprintf (dump_file
, ")\n");
2617 /* Returns true when analyze_subscript_affine_affine can be used for
2618 determining the dependence relation between chrec_a and chrec_b,
2619 that contain symbols. This function modifies chrec_a and chrec_b
2620 such that the analysis result is the same, and such that they don't
2621 contain symbols, and then can safely be passed to the analyzer.
2623 Example: The analysis of the following tuples of evolutions produce
2624 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2627 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2628 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2632 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2634 tree diff
, type
, left_a
, left_b
, right_b
;
2636 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2637 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2638 /* FIXME: For the moment not handled. Might be refined later. */
2641 type
= chrec_type (*chrec_a
);
2642 left_a
= CHREC_LEFT (*chrec_a
);
2643 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2644 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2646 if (!evolution_function_is_constant_p (diff
))
2649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2650 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2652 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2653 diff
, CHREC_RIGHT (*chrec_a
));
2654 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2655 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2656 build_int_cst (type
, 0),
2661 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2662 *OVERLAPS_B are initialized to the functions that describe the
2663 relation between the elements accessed twice by CHREC_A and
2664 CHREC_B. For k >= 0, the following property is verified:
2666 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2669 analyze_siv_subscript (tree chrec_a
,
2671 conflict_function
**overlaps_a
,
2672 conflict_function
**overlaps_b
,
2673 tree
*last_conflicts
,
2676 dependence_stats
.num_siv
++;
2678 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2679 fprintf (dump_file
, "(analyze_siv_subscript \n");
2681 if (evolution_function_is_constant_p (chrec_a
)
2682 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2683 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2684 overlaps_a
, overlaps_b
, last_conflicts
);
2686 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2687 && evolution_function_is_constant_p (chrec_b
))
2688 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2689 overlaps_b
, overlaps_a
, last_conflicts
);
2691 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2692 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2694 if (!chrec_contains_symbols (chrec_a
)
2695 && !chrec_contains_symbols (chrec_b
))
2697 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2698 overlaps_a
, overlaps_b
,
2701 if (CF_NOT_KNOWN_P (*overlaps_a
)
2702 || CF_NOT_KNOWN_P (*overlaps_b
))
2703 dependence_stats
.num_siv_unimplemented
++;
2704 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2705 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2706 dependence_stats
.num_siv_independent
++;
2708 dependence_stats
.num_siv_dependent
++;
2710 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2713 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2714 overlaps_a
, overlaps_b
,
2717 if (CF_NOT_KNOWN_P (*overlaps_a
)
2718 || CF_NOT_KNOWN_P (*overlaps_b
))
2719 dependence_stats
.num_siv_unimplemented
++;
2720 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2721 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2722 dependence_stats
.num_siv_independent
++;
2724 dependence_stats
.num_siv_dependent
++;
2727 goto siv_subscript_dontknow
;
2732 siv_subscript_dontknow
:;
2733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2734 fprintf (dump_file
, "siv test failed: unimplemented.\n");
2735 *overlaps_a
= conflict_fn_not_known ();
2736 *overlaps_b
= conflict_fn_not_known ();
2737 *last_conflicts
= chrec_dont_know
;
2738 dependence_stats
.num_siv_unimplemented
++;
2741 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2742 fprintf (dump_file
, ")\n");
2745 /* Returns false if we can prove that the greatest common divisor of the steps
2746 of CHREC does not divide CST, false otherwise. */
2749 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2751 HOST_WIDE_INT cd
= 0, val
;
2754 if (!host_integerp (cst
, 0))
2756 val
= tree_low_cst (cst
, 0);
2758 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2760 step
= CHREC_RIGHT (chrec
);
2761 if (!host_integerp (step
, 0))
2763 cd
= gcd (cd
, tree_low_cst (step
, 0));
2764 chrec
= CHREC_LEFT (chrec
);
2767 return val
% cd
== 0;
2770 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2771 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2772 functions that describe the relation between the elements accessed
2773 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2776 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2779 analyze_miv_subscript (tree chrec_a
,
2781 conflict_function
**overlaps_a
,
2782 conflict_function
**overlaps_b
,
2783 tree
*last_conflicts
,
2784 struct loop
*loop_nest
)
2786 tree type
, difference
;
2788 dependence_stats
.num_miv
++;
2789 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2790 fprintf (dump_file
, "(analyze_miv_subscript \n");
2792 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2793 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2794 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2795 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2797 if (eq_evolutions_p (chrec_a
, chrec_b
))
2799 /* Access functions are the same: all the elements are accessed
2800 in the same order. */
2801 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2802 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2803 *last_conflicts
= max_stmt_executions_tree (get_chrec_loop (chrec_a
));
2804 dependence_stats
.num_miv_dependent
++;
2807 else if (evolution_function_is_constant_p (difference
)
2808 /* For the moment, the following is verified:
2809 evolution_function_is_affine_multivariate_p (chrec_a,
2811 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2813 /* testsuite/.../ssa-chrec-33.c
2814 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2816 The difference is 1, and all the evolution steps are multiples
2817 of 2, consequently there are no overlapping elements. */
2818 *overlaps_a
= conflict_fn_no_dependence ();
2819 *overlaps_b
= conflict_fn_no_dependence ();
2820 *last_conflicts
= integer_zero_node
;
2821 dependence_stats
.num_miv_independent
++;
2824 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2825 && !chrec_contains_symbols (chrec_a
)
2826 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2827 && !chrec_contains_symbols (chrec_b
))
2829 /* testsuite/.../ssa-chrec-35.c
2830 {0, +, 1}_2 vs. {0, +, 1}_3
2831 the overlapping elements are respectively located at iterations:
2832 {0, +, 1}_x and {0, +, 1}_x,
2833 in other words, we have the equality:
2834 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2837 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2838 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2840 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2841 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2843 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2844 overlaps_a
, overlaps_b
, last_conflicts
);
2846 if (CF_NOT_KNOWN_P (*overlaps_a
)
2847 || CF_NOT_KNOWN_P (*overlaps_b
))
2848 dependence_stats
.num_miv_unimplemented
++;
2849 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2850 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2851 dependence_stats
.num_miv_independent
++;
2853 dependence_stats
.num_miv_dependent
++;
2858 /* When the analysis is too difficult, answer "don't know". */
2859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2860 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2862 *overlaps_a
= conflict_fn_not_known ();
2863 *overlaps_b
= conflict_fn_not_known ();
2864 *last_conflicts
= chrec_dont_know
;
2865 dependence_stats
.num_miv_unimplemented
++;
2868 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2869 fprintf (dump_file
, ")\n");
2872 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2873 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2874 OVERLAP_ITERATIONS_B are initialized with two functions that
2875 describe the iterations that contain conflicting elements.
2877 Remark: For an integer k >= 0, the following equality is true:
2879 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2883 analyze_overlapping_iterations (tree chrec_a
,
2885 conflict_function
**overlap_iterations_a
,
2886 conflict_function
**overlap_iterations_b
,
2887 tree
*last_conflicts
, struct loop
*loop_nest
)
2889 unsigned int lnn
= loop_nest
->num
;
2891 dependence_stats
.num_subscript_tests
++;
2893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2895 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2896 fprintf (dump_file
, " (chrec_a = ");
2897 print_generic_expr (dump_file
, chrec_a
, 0);
2898 fprintf (dump_file
, ")\n (chrec_b = ");
2899 print_generic_expr (dump_file
, chrec_b
, 0);
2900 fprintf (dump_file
, ")\n");
2903 if (chrec_a
== NULL_TREE
2904 || chrec_b
== NULL_TREE
2905 || chrec_contains_undetermined (chrec_a
)
2906 || chrec_contains_undetermined (chrec_b
))
2908 dependence_stats
.num_subscript_undetermined
++;
2910 *overlap_iterations_a
= conflict_fn_not_known ();
2911 *overlap_iterations_b
= conflict_fn_not_known ();
2914 /* If they are the same chrec, and are affine, they overlap
2915 on every iteration. */
2916 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2917 && (evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2918 || operand_equal_p (chrec_a
, chrec_b
, 0)))
2920 dependence_stats
.num_same_subscript_function
++;
2921 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2922 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2923 *last_conflicts
= chrec_dont_know
;
2926 /* If they aren't the same, and aren't affine, we can't do anything
2928 else if ((chrec_contains_symbols (chrec_a
)
2929 || chrec_contains_symbols (chrec_b
))
2930 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2931 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2933 dependence_stats
.num_subscript_undetermined
++;
2934 *overlap_iterations_a
= conflict_fn_not_known ();
2935 *overlap_iterations_b
= conflict_fn_not_known ();
2938 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2939 analyze_ziv_subscript (chrec_a
, chrec_b
,
2940 overlap_iterations_a
, overlap_iterations_b
,
2943 else if (siv_subscript_p (chrec_a
, chrec_b
))
2944 analyze_siv_subscript (chrec_a
, chrec_b
,
2945 overlap_iterations_a
, overlap_iterations_b
,
2946 last_conflicts
, lnn
);
2949 analyze_miv_subscript (chrec_a
, chrec_b
,
2950 overlap_iterations_a
, overlap_iterations_b
,
2951 last_conflicts
, loop_nest
);
2953 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2955 fprintf (dump_file
, " (overlap_iterations_a = ");
2956 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2957 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2958 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2959 fprintf (dump_file
, ")\n");
2960 fprintf (dump_file
, ")\n");
2964 /* Helper function for uniquely inserting distance vectors. */
2967 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
2972 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
)
2973 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
2976 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
2979 /* Helper function for uniquely inserting direction vectors. */
2982 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
2987 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
)
2988 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
2991 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
2994 /* Add a distance of 1 on all the loops outer than INDEX. If we
2995 haven't yet determined a distance for this outer loop, push a new
2996 distance vector composed of the previous distance, and a distance
2997 of 1 for this outer loop. Example:
3005 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3006 save (0, 1), then we have to save (1, 0). */
3009 add_outer_distances (struct data_dependence_relation
*ddr
,
3010 lambda_vector dist_v
, int index
)
3012 /* For each outer loop where init_v is not set, the accesses are
3013 in dependence of distance 1 in the loop. */
3014 while (--index
>= 0)
3016 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3017 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3019 save_dist_v (ddr
, save_v
);
3023 /* Return false when fail to represent the data dependence as a
3024 distance vector. INIT_B is set to true when a component has been
3025 added to the distance vector DIST_V. INDEX_CARRY is then set to
3026 the index in DIST_V that carries the dependence. */
3029 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
3030 struct data_reference
*ddr_a
,
3031 struct data_reference
*ddr_b
,
3032 lambda_vector dist_v
, bool *init_b
,
3036 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3038 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3040 tree access_fn_a
, access_fn_b
;
3041 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
3043 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3045 non_affine_dependence_relation (ddr
);
3049 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
3050 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
3052 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
3053 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
3056 int var_a
= CHREC_VARIABLE (access_fn_a
);
3057 int var_b
= CHREC_VARIABLE (access_fn_b
);
3060 || chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3062 non_affine_dependence_relation (ddr
);
3066 dist
= int_cst_value (SUB_DISTANCE (subscript
));
3067 index
= index_in_loop_nest (var_a
, DDR_LOOP_NEST (ddr
));
3068 *index_carry
= MIN (index
, *index_carry
);
3070 /* This is the subscript coupling test. If we have already
3071 recorded a distance for this loop (a distance coming from
3072 another subscript), it should be the same. For example,
3073 in the following code, there is no dependence:
3080 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
3082 finalize_ddr_dependent (ddr
, chrec_known
);
3086 dist_v
[index
] = dist
;
3090 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
3092 /* This can be for example an affine vs. constant dependence
3093 (T[i] vs. T[3]) that is not an affine dependence and is
3094 not representable as a distance vector. */
3095 non_affine_dependence_relation (ddr
);
3103 /* Return true when the DDR contains only constant access functions. */
3106 constant_access_functions (const struct data_dependence_relation
*ddr
)
3110 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3111 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
3112 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
3118 /* Helper function for the case where DDR_A and DDR_B are the same
3119 multivariate access function with a constant step. For an example
3123 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
3126 tree c_1
= CHREC_LEFT (c_2
);
3127 tree c_0
= CHREC_LEFT (c_1
);
3128 lambda_vector dist_v
;
3131 /* Polynomials with more than 2 variables are not handled yet. When
3132 the evolution steps are parameters, it is not possible to
3133 represent the dependence using classical distance vectors. */
3134 if (TREE_CODE (c_0
) != INTEGER_CST
3135 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
3136 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
3138 DDR_AFFINE_P (ddr
) = false;
3142 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
3143 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
3145 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3146 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3147 v1
= int_cst_value (CHREC_RIGHT (c_1
));
3148 v2
= int_cst_value (CHREC_RIGHT (c_2
));
3161 save_dist_v (ddr
, dist_v
);
3163 add_outer_distances (ddr
, dist_v
, x_1
);
3166 /* Helper function for the case where DDR_A and DDR_B are the same
3167 access functions. */
3170 add_other_self_distances (struct data_dependence_relation
*ddr
)
3172 lambda_vector dist_v
;
3174 int index_carry
= DDR_NB_LOOPS (ddr
);
3176 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3178 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3180 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3182 if (!evolution_function_is_univariate_p (access_fun
))
3184 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3186 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3190 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
3192 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
3193 add_multivariate_self_dist (ddr
, access_fun
);
3195 /* The evolution step is not constant: it varies in
3196 the outer loop, so this cannot be represented by a
3197 distance vector. For example in pr34635.c the
3198 evolution is {0, +, {0, +, 4}_1}_2. */
3199 DDR_AFFINE_P (ddr
) = false;
3204 index_carry
= MIN (index_carry
,
3205 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3206 DDR_LOOP_NEST (ddr
)));
3210 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3211 add_outer_distances (ddr
, dist_v
, index_carry
);
3215 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
3217 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3219 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
3220 save_dist_v (ddr
, dist_v
);
3223 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3224 is the case for example when access functions are the same and
3225 equal to a constant, as in:
3232 in which case the distance vectors are (0) and (1). */
3235 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
3239 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3241 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
3242 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
3243 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
3245 for (j
= 0; j
< ca
->n
; j
++)
3246 if (affine_function_zero_p (ca
->fns
[j
]))
3248 insert_innermost_unit_dist_vector (ddr
);
3252 for (j
= 0; j
< cb
->n
; j
++)
3253 if (affine_function_zero_p (cb
->fns
[j
]))
3255 insert_innermost_unit_dist_vector (ddr
);
3261 /* Compute the classic per loop distance vector. DDR is the data
3262 dependence relation to build a vector from. Return false when fail
3263 to represent the data dependence as a distance vector. */
3266 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3267 struct loop
*loop_nest
)
3269 bool init_b
= false;
3270 int index_carry
= DDR_NB_LOOPS (ddr
);
3271 lambda_vector dist_v
;
3273 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3276 if (same_access_functions (ddr
))
3278 /* Save the 0 vector. */
3279 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3280 save_dist_v (ddr
, dist_v
);
3282 if (constant_access_functions (ddr
))
3283 add_distance_for_zero_overlaps (ddr
);
3285 if (DDR_NB_LOOPS (ddr
) > 1)
3286 add_other_self_distances (ddr
);
3291 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3292 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3293 dist_v
, &init_b
, &index_carry
))
3296 /* Save the distance vector if we initialized one. */
3299 /* Verify a basic constraint: classic distance vectors should
3300 always be lexicographically positive.
3302 Data references are collected in the order of execution of
3303 the program, thus for the following loop
3305 | for (i = 1; i < 100; i++)
3306 | for (j = 1; j < 100; j++)
3308 | t = T[j+1][i-1]; // A
3309 | T[j][i] = t + 2; // B
3312 references are collected following the direction of the wind:
3313 A then B. The data dependence tests are performed also
3314 following this order, such that we're looking at the distance
3315 separating the elements accessed by A from the elements later
3316 accessed by B. But in this example, the distance returned by
3317 test_dep (A, B) is lexicographically negative (-1, 1), that
3318 means that the access A occurs later than B with respect to
3319 the outer loop, ie. we're actually looking upwind. In this
3320 case we solve test_dep (B, A) looking downwind to the
3321 lexicographically positive solution, that returns the
3322 distance vector (1, -1). */
3323 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3325 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3326 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3329 compute_subscript_distance (ddr
);
3330 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3331 save_v
, &init_b
, &index_carry
))
3333 save_dist_v (ddr
, save_v
);
3334 DDR_REVERSED_P (ddr
) = true;
3336 /* In this case there is a dependence forward for all the
3339 | for (k = 1; k < 100; k++)
3340 | for (i = 1; i < 100; i++)
3341 | for (j = 1; j < 100; j++)
3343 | t = T[j+1][i-1]; // A
3344 | T[j][i] = t + 2; // B
3352 if (DDR_NB_LOOPS (ddr
) > 1)
3354 add_outer_distances (ddr
, save_v
, index_carry
);
3355 add_outer_distances (ddr
, dist_v
, index_carry
);
3360 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3361 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3363 if (DDR_NB_LOOPS (ddr
) > 1)
3365 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3367 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3368 DDR_A (ddr
), loop_nest
))
3370 compute_subscript_distance (ddr
);
3371 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3372 opposite_v
, &init_b
,
3376 save_dist_v (ddr
, save_v
);
3377 add_outer_distances (ddr
, dist_v
, index_carry
);
3378 add_outer_distances (ddr
, opposite_v
, index_carry
);
3381 save_dist_v (ddr
, save_v
);
3386 /* There is a distance of 1 on all the outer loops: Example:
3387 there is a dependence of distance 1 on loop_1 for the array A.
3393 add_outer_distances (ddr
, dist_v
,
3394 lambda_vector_first_nz (dist_v
,
3395 DDR_NB_LOOPS (ddr
), 0));
3398 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3402 fprintf (dump_file
, "(build_classic_dist_vector\n");
3403 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3405 fprintf (dump_file
, " dist_vector = (");
3406 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3407 DDR_NB_LOOPS (ddr
));
3408 fprintf (dump_file
, " )\n");
3410 fprintf (dump_file
, ")\n");
3416 /* Return the direction for a given distance.
3417 FIXME: Computing dir this way is suboptimal, since dir can catch
3418 cases that dist is unable to represent. */
3420 static inline enum data_dependence_direction
3421 dir_from_dist (int dist
)
3424 return dir_positive
;
3426 return dir_negative
;
3431 /* Compute the classic per loop direction vector. DDR is the data
3432 dependence relation to build a vector from. */
3435 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3438 lambda_vector dist_v
;
3440 FOR_EACH_VEC_ELT (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
)
3442 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3444 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3445 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3447 save_dir_v (ddr
, dir_v
);
3451 /* Helper function. Returns true when there is a dependence between
3452 data references DRA and DRB. */
3455 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3456 struct data_reference
*dra
,
3457 struct data_reference
*drb
,
3458 struct loop
*loop_nest
)
3461 tree last_conflicts
;
3462 struct subscript
*subscript
;
3464 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3467 conflict_function
*overlaps_a
, *overlaps_b
;
3469 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3470 DR_ACCESS_FN (drb
, i
),
3471 &overlaps_a
, &overlaps_b
,
3472 &last_conflicts
, loop_nest
);
3474 if (CF_NOT_KNOWN_P (overlaps_a
)
3475 || CF_NOT_KNOWN_P (overlaps_b
))
3477 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3478 dependence_stats
.num_dependence_undetermined
++;
3479 free_conflict_function (overlaps_a
);
3480 free_conflict_function (overlaps_b
);
3484 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3485 || CF_NO_DEPENDENCE_P (overlaps_b
))
3487 finalize_ddr_dependent (ddr
, chrec_known
);
3488 dependence_stats
.num_dependence_independent
++;
3489 free_conflict_function (overlaps_a
);
3490 free_conflict_function (overlaps_b
);
3496 if (SUB_CONFLICTS_IN_A (subscript
))
3497 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3498 if (SUB_CONFLICTS_IN_B (subscript
))
3499 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3501 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3502 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3503 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3510 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3513 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3514 struct loop
*loop_nest
)
3517 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3518 fprintf (dump_file
, "(subscript_dependence_tester \n");
3520 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3521 dependence_stats
.num_dependence_dependent
++;
3523 compute_subscript_distance (ddr
);
3524 if (build_classic_dist_vector (ddr
, loop_nest
))
3525 build_classic_dir_vector (ddr
);
3527 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3528 fprintf (dump_file
, ")\n");
3531 /* Returns true when all the access functions of A are affine or
3532 constant with respect to LOOP_NEST. */
3535 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3536 const struct loop
*loop_nest
)
3539 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
3542 FOR_EACH_VEC_ELT (tree
, fns
, i
, t
)
3543 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3544 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3550 /* Initializes an equation for an OMEGA problem using the information
3551 contained in the ACCESS_FUN. Returns true when the operation
3554 PB is the omega constraint system.
3555 EQ is the number of the equation to be initialized.
3556 OFFSET is used for shifting the variables names in the constraints:
3557 a constrain is composed of 2 * the number of variables surrounding
3558 dependence accesses. OFFSET is set either to 0 for the first n variables,
3559 then it is set to n.
3560 ACCESS_FUN is expected to be an affine chrec. */
3563 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3564 unsigned int offset
, tree access_fun
,
3565 struct data_dependence_relation
*ddr
)
3567 switch (TREE_CODE (access_fun
))
3569 case POLYNOMIAL_CHREC
:
3571 tree left
= CHREC_LEFT (access_fun
);
3572 tree right
= CHREC_RIGHT (access_fun
);
3573 int var
= CHREC_VARIABLE (access_fun
);
3576 if (TREE_CODE (right
) != INTEGER_CST
)
3579 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3580 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3582 /* Compute the innermost loop index. */
3583 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3586 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3587 += int_cst_value (right
);
3589 switch (TREE_CODE (left
))
3591 case POLYNOMIAL_CHREC
:
3592 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3595 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3604 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3612 /* As explained in the comments preceding init_omega_for_ddr, we have
3613 to set up a system for each loop level, setting outer loops
3614 variation to zero, and current loop variation to positive or zero.
3615 Save each lexico positive distance vector. */
3618 omega_extract_distance_vectors (omega_pb pb
,
3619 struct data_dependence_relation
*ddr
)
3623 struct loop
*loopi
, *loopj
;
3624 enum omega_result res
;
3626 /* Set a new problem for each loop in the nest. The basis is the
3627 problem that we have initialized until now. On top of this we
3628 add new constraints. */
3629 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3630 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3633 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3634 DDR_NB_LOOPS (ddr
));
3636 omega_copy_problem (copy
, pb
);
3638 /* For all the outer loops "loop_j", add "dj = 0". */
3640 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3642 eq
= omega_add_zero_eq (copy
, omega_black
);
3643 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3646 /* For "loop_i", add "0 <= di". */
3647 geq
= omega_add_zero_geq (copy
, omega_black
);
3648 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3650 /* Reduce the constraint system, and test that the current
3651 problem is feasible. */
3652 res
= omega_simplify_problem (copy
);
3653 if (res
== omega_false
3654 || res
== omega_unknown
3655 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3658 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3659 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3661 dist
= copy
->subs
[eq
].coef
[0];
3667 /* Reinitialize problem... */
3668 omega_copy_problem (copy
, pb
);
3670 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
3672 eq
= omega_add_zero_eq (copy
, omega_black
);
3673 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3676 /* ..., but this time "di = 1". */
3677 eq
= omega_add_zero_eq (copy
, omega_black
);
3678 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3679 copy
->eqs
[eq
].coef
[0] = -1;
3681 res
= omega_simplify_problem (copy
);
3682 if (res
== omega_false
3683 || res
== omega_unknown
3684 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3687 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3688 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3690 dist
= copy
->subs
[eq
].coef
[0];
3696 /* Save the lexicographically positive distance vector. */
3699 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3700 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3704 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3705 if (copy
->subs
[eq
].key
> 0)
3707 dist
= copy
->subs
[eq
].coef
[0];
3708 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3711 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3712 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3714 save_dist_v (ddr
, dist_v
);
3715 save_dir_v (ddr
, dir_v
);
3719 omega_free_problem (copy
);
3723 /* This is called for each subscript of a tuple of data references:
3724 insert an equality for representing the conflicts. */
3727 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3728 struct data_dependence_relation
*ddr
,
3729 omega_pb pb
, bool *maybe_dependent
)
3732 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3733 TREE_TYPE (access_fun_b
));
3734 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3735 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3736 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3739 /* When the fun_a - fun_b is not constant, the dependence is not
3740 captured by the classic distance vector representation. */
3741 if (TREE_CODE (difference
) != INTEGER_CST
)
3745 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3747 /* There is no dependence. */
3748 *maybe_dependent
= false;
3752 minus_one
= build_int_cst (type
, -1);
3753 fun_b
= chrec_fold_multiply (type
, fun_b
, minus_one
);
3755 eq
= omega_add_zero_eq (pb
, omega_black
);
3756 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3757 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3758 /* There is probably a dependence, but the system of
3759 constraints cannot be built: answer "don't know". */
3763 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3764 && !int_divides_p (lambda_vector_gcd
3765 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3766 2 * DDR_NB_LOOPS (ddr
)),
3767 pb
->eqs
[eq
].coef
[0]))
3769 /* There is no dependence. */
3770 *maybe_dependent
= false;
3777 /* Helper function, same as init_omega_for_ddr but specialized for
3778 data references A and B. */
3781 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3782 struct data_dependence_relation
*ddr
,
3783 omega_pb pb
, bool *maybe_dependent
)
3788 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3790 /* Insert an equality per subscript. */
3791 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3793 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3794 ddr
, pb
, maybe_dependent
))
3796 else if (*maybe_dependent
== false)
3798 /* There is no dependence. */
3799 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3804 /* Insert inequalities: constraints corresponding to the iteration
3805 domain, i.e. the loops surrounding the references "loop_x" and
3806 the distance variables "dx". The layout of the OMEGA
3807 representation is as follows:
3808 - coef[0] is the constant
3809 - coef[1..nb_loops] are the protected variables that will not be
3810 removed by the solver: the "dx"
3811 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3813 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3814 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
3816 HOST_WIDE_INT nbi
= max_stmt_executions_int (loopi
, true);
3819 ineq
= omega_add_zero_geq (pb
, omega_black
);
3820 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3822 /* 0 <= loop_x + dx */
3823 ineq
= omega_add_zero_geq (pb
, omega_black
);
3824 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3825 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3829 /* loop_x <= nb_iters */
3830 ineq
= omega_add_zero_geq (pb
, omega_black
);
3831 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3832 pb
->geqs
[ineq
].coef
[0] = nbi
;
3834 /* loop_x + dx <= nb_iters */
3835 ineq
= omega_add_zero_geq (pb
, omega_black
);
3836 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3837 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3838 pb
->geqs
[ineq
].coef
[0] = nbi
;
3840 /* A step "dx" bigger than nb_iters is not feasible, so
3841 add "0 <= nb_iters + dx", */
3842 ineq
= omega_add_zero_geq (pb
, omega_black
);
3843 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3844 pb
->geqs
[ineq
].coef
[0] = nbi
;
3845 /* and "dx <= nb_iters". */
3846 ineq
= omega_add_zero_geq (pb
, omega_black
);
3847 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3848 pb
->geqs
[ineq
].coef
[0] = nbi
;
3852 omega_extract_distance_vectors (pb
, ddr
);
3857 /* Sets up the Omega dependence problem for the data dependence
3858 relation DDR. Returns false when the constraint system cannot be
3859 built, ie. when the test answers "don't know". Returns true
3860 otherwise, and when independence has been proved (using one of the
3861 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3862 set MAYBE_DEPENDENT to true.
3864 Example: for setting up the dependence system corresponding to the
3865 conflicting accesses
3870 | ... A[2*j, 2*(i + j)]
3874 the following constraints come from the iteration domain:
3881 where di, dj are the distance variables. The constraints
3882 representing the conflicting elements are:
3885 i + 1 = 2 * (i + di + j + dj)
3887 For asking that the resulting distance vector (di, dj) be
3888 lexicographically positive, we insert the constraint "di >= 0". If
3889 "di = 0" in the solution, we fix that component to zero, and we
3890 look at the inner loops: we set a new problem where all the outer
3891 loop distances are zero, and fix this inner component to be
3892 positive. When one of the components is positive, we save that
3893 distance, and set a new problem where the distance on this loop is
3894 zero, searching for other distances in the inner loops. Here is
3895 the classic example that illustrates that we have to set for each
3896 inner loop a new problem:
3904 we have to save two distances (1, 0) and (0, 1).
3906 Given two array references, refA and refB, we have to set the
3907 dependence problem twice, refA vs. refB and refB vs. refA, and we
3908 cannot do a single test, as refB might occur before refA in the
3909 inner loops, and the contrary when considering outer loops: ex.
3914 | T[{1,+,1}_2][{1,+,1}_1] // refA
3915 | T[{2,+,1}_2][{0,+,1}_1] // refB
3920 refB touches the elements in T before refA, and thus for the same
3921 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3922 but for successive loop_0 iterations, we have (1, -1, 1)
3924 The Omega solver expects the distance variables ("di" in the
3925 previous example) to come first in the constraint system (as
3926 variables to be protected, or "safe" variables), the constraint
3927 system is built using the following layout:
3929 "cst | distance vars | index vars".
3933 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3934 bool *maybe_dependent
)
3939 *maybe_dependent
= true;
3941 if (same_access_functions (ddr
))
3944 lambda_vector dir_v
;
3946 /* Save the 0 vector. */
3947 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3948 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3949 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3950 dir_v
[j
] = dir_equal
;
3951 save_dir_v (ddr
, dir_v
);
3953 /* Save the dependences carried by outer loops. */
3954 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3955 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3957 omega_free_problem (pb
);
3961 /* Omega expects the protected variables (those that have to be kept
3962 after elimination) to appear first in the constraint system.
3963 These variables are the distance variables. In the following
3964 initialization we declare NB_LOOPS safe variables, and the total
3965 number of variables for the constraint system is 2*NB_LOOPS. */
3966 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3967 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3969 omega_free_problem (pb
);
3971 /* Stop computation if not decidable, or no dependence. */
3972 if (res
== false || *maybe_dependent
== false)
3975 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3976 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
3978 omega_free_problem (pb
);
3983 /* Return true when DDR contains the same information as that stored
3984 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3987 ddr_consistent_p (FILE *file
,
3988 struct data_dependence_relation
*ddr
,
3989 VEC (lambda_vector
, heap
) *dist_vects
,
3990 VEC (lambda_vector
, heap
) *dir_vects
)
3994 /* If dump_file is set, output there. */
3995 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3998 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
4000 lambda_vector b_dist_v
;
4001 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4002 VEC_length (lambda_vector
, dist_vects
),
4003 DDR_NUM_DIST_VECTS (ddr
));
4005 fprintf (file
, "Banerjee dist vectors:\n");
4006 FOR_EACH_VEC_ELT (lambda_vector
, dist_vects
, i
, b_dist_v
)
4007 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
4009 fprintf (file
, "Omega dist vectors:\n");
4010 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4011 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
4013 fprintf (file
, "data dependence relation:\n");
4014 dump_data_dependence_relation (file
, ddr
);
4016 fprintf (file
, ")\n");
4020 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
4022 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4023 VEC_length (lambda_vector
, dir_vects
),
4024 DDR_NUM_DIR_VECTS (ddr
));
4028 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4030 lambda_vector a_dist_v
;
4031 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
4033 /* Distance vectors are not ordered in the same way in the DDR
4034 and in the DIST_VECTS: search for a matching vector. */
4035 FOR_EACH_VEC_ELT (lambda_vector
, dist_vects
, j
, a_dist_v
)
4036 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
4039 if (j
== VEC_length (lambda_vector
, dist_vects
))
4041 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
4042 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
4043 fprintf (file
, "not found in Omega dist vectors:\n");
4044 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4045 fprintf (file
, "data dependence relation:\n");
4046 dump_data_dependence_relation (file
, ddr
);
4047 fprintf (file
, ")\n");
4051 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
4053 lambda_vector a_dir_v
;
4054 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
4056 /* Direction vectors are not ordered in the same way in the DDR
4057 and in the DIR_VECTS: search for a matching vector. */
4058 FOR_EACH_VEC_ELT (lambda_vector
, dir_vects
, j
, a_dir_v
)
4059 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
4062 if (j
== VEC_length (lambda_vector
, dist_vects
))
4064 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
4065 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
4066 fprintf (file
, "not found in Omega dir vectors:\n");
4067 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4068 fprintf (file
, "data dependence relation:\n");
4069 dump_data_dependence_relation (file
, ddr
);
4070 fprintf (file
, ")\n");
4077 /* This computes the affine dependence relation between A and B with
4078 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4079 independence between two accesses, while CHREC_DONT_KNOW is used
4080 for representing the unknown relation.
4082 Note that it is possible to stop the computation of the dependence
4083 relation the first time we detect a CHREC_KNOWN element for a given
4087 compute_affine_dependence (struct data_dependence_relation
*ddr
,
4088 struct loop
*loop_nest
)
4090 struct data_reference
*dra
= DDR_A (ddr
);
4091 struct data_reference
*drb
= DDR_B (ddr
);
4093 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4095 fprintf (dump_file
, "(compute_affine_dependence\n");
4096 fprintf (dump_file
, " stmt_a: ");
4097 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, TDF_SLIM
);
4098 fprintf (dump_file
, " stmt_b: ");
4099 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, TDF_SLIM
);
4102 /* Analyze only when the dependence relation is not yet known. */
4103 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4105 dependence_stats
.num_dependence_tests
++;
4107 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
4108 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
4110 if (flag_check_data_deps
)
4112 /* Compute the dependences using the first algorithm. */
4113 subscript_dependence_tester (ddr
, loop_nest
);
4115 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4117 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
4118 dump_data_dependence_relation (dump_file
, ddr
);
4121 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4123 bool maybe_dependent
;
4124 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
4126 /* Save the result of the first DD analyzer. */
4127 dist_vects
= DDR_DIST_VECTS (ddr
);
4128 dir_vects
= DDR_DIR_VECTS (ddr
);
4130 /* Reset the information. */
4131 DDR_DIST_VECTS (ddr
) = NULL
;
4132 DDR_DIR_VECTS (ddr
) = NULL
;
4134 /* Compute the same information using Omega. */
4135 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
4136 goto csys_dont_know
;
4138 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4140 fprintf (dump_file
, "Omega Analyzer\n");
4141 dump_data_dependence_relation (dump_file
, ddr
);
4144 /* Check that we get the same information. */
4145 if (maybe_dependent
)
4146 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
4151 subscript_dependence_tester (ddr
, loop_nest
);
4154 /* As a last case, if the dependence cannot be determined, or if
4155 the dependence is considered too difficult to determine, answer
4160 dependence_stats
.num_dependence_undetermined
++;
4162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4164 fprintf (dump_file
, "Data ref a:\n");
4165 dump_data_reference (dump_file
, dra
);
4166 fprintf (dump_file
, "Data ref b:\n");
4167 dump_data_reference (dump_file
, drb
);
4168 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
4170 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4174 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4176 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4177 fprintf (dump_file
, ") -> no dependence\n");
4178 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4179 fprintf (dump_file
, ") -> dependence analysis failed\n");
4181 fprintf (dump_file
, ")\n");
4185 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4186 the data references in DATAREFS, in the LOOP_NEST. When
4187 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4188 relations. Return true when successful, i.e. data references number
4189 is small enough to be handled. */
4192 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
4193 VEC (ddr_p
, heap
) **dependence_relations
,
4194 VEC (loop_p
, heap
) *loop_nest
,
4195 bool compute_self_and_rr
)
4197 struct data_dependence_relation
*ddr
;
4198 struct data_reference
*a
, *b
;
4201 if ((int) VEC_length (data_reference_p
, datarefs
)
4202 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS
))
4204 struct data_dependence_relation
*ddr
;
4206 /* Insert a single relation into dependence_relations:
4208 ddr
= initialize_data_dependence_relation (NULL
, NULL
, loop_nest
);
4209 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4213 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, a
)
4214 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
4215 if (DR_IS_WRITE (a
) || DR_IS_WRITE (b
) || compute_self_and_rr
)
4217 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4218 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4220 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
4223 if (compute_self_and_rr
)
4224 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, a
)
4226 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4227 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4229 compute_affine_dependence (ddr
, VEC_index (loop_p
, loop_nest
, 0));
4235 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4236 true if STMT clobbers memory, false otherwise. */
4239 get_references_in_stmt (gimple stmt
, VEC (data_ref_loc
, heap
) **references
)
4241 bool clobbers_memory
= false;
4244 enum gimple_code stmt_code
= gimple_code (stmt
);
4248 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4249 Calls have side-effects, except those to const or pure
4251 if ((stmt_code
== GIMPLE_CALL
4252 && !(gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4253 || (stmt_code
== GIMPLE_ASM
4254 && (gimple_asm_volatile_p (stmt
) || gimple_vuse (stmt
))))
4255 clobbers_memory
= true;
4257 if (!gimple_vuse (stmt
))
4258 return clobbers_memory
;
4260 if (stmt_code
== GIMPLE_ASSIGN
)
4263 op0
= gimple_assign_lhs_ptr (stmt
);
4264 op1
= gimple_assign_rhs1_ptr (stmt
);
4267 || (REFERENCE_CLASS_P (*op1
)
4268 && (base
= get_base_address (*op1
))
4269 && TREE_CODE (base
) != SSA_NAME
))
4271 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4273 ref
->is_read
= true;
4276 else if (stmt_code
== GIMPLE_CALL
)
4280 op0
= gimple_call_lhs_ptr (stmt
);
4281 n
= gimple_call_num_args (stmt
);
4282 for (i
= 0; i
< n
; i
++)
4284 op1
= gimple_call_arg_ptr (stmt
, i
);
4287 || (REFERENCE_CLASS_P (*op1
) && get_base_address (*op1
)))
4289 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4291 ref
->is_read
= true;
4296 return clobbers_memory
;
4300 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
))))
4302 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4304 ref
->is_read
= false;
4306 return clobbers_memory
;
4309 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4310 reference, returns false, otherwise returns true. NEST is the outermost
4311 loop of the loop nest in which the references should be analyzed. */
4314 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4315 VEC (data_reference_p
, heap
) **datarefs
)
4318 VEC (data_ref_loc
, heap
) *references
;
4321 data_reference_p dr
;
4323 if (get_references_in_stmt (stmt
, &references
))
4325 VEC_free (data_ref_loc
, heap
, references
);
4329 FOR_EACH_VEC_ELT (data_ref_loc
, references
, i
, ref
)
4331 dr
= create_data_ref (nest
, loop_containing_stmt (stmt
),
4332 *ref
->pos
, stmt
, ref
->is_read
);
4333 gcc_assert (dr
!= NULL
);
4334 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4336 VEC_free (data_ref_loc
, heap
, references
);
4340 /* Stores the data references in STMT to DATAREFS. If there is an
4341 unanalyzable reference, returns false, otherwise returns true.
4342 NEST is the outermost loop of the loop nest in which the references
4343 should be instantiated, LOOP is the loop in which the references
4344 should be analyzed. */
4347 graphite_find_data_references_in_stmt (loop_p nest
, loop_p loop
, gimple stmt
,
4348 VEC (data_reference_p
, heap
) **datarefs
)
4351 VEC (data_ref_loc
, heap
) *references
;
4354 data_reference_p dr
;
4356 if (get_references_in_stmt (stmt
, &references
))
4358 VEC_free (data_ref_loc
, heap
, references
);
4362 FOR_EACH_VEC_ELT (data_ref_loc
, references
, i
, ref
)
4364 dr
= create_data_ref (nest
, loop
, *ref
->pos
, stmt
, ref
->is_read
);
4365 gcc_assert (dr
!= NULL
);
4366 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4369 VEC_free (data_ref_loc
, heap
, references
);
4373 /* Search the data references in LOOP, and record the information into
4374 DATAREFS. Returns chrec_dont_know when failing to analyze a
4375 difficult case, returns NULL_TREE otherwise. */
4378 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4379 VEC (data_reference_p
, heap
) **datarefs
)
4381 gimple_stmt_iterator bsi
;
4383 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4385 gimple stmt
= gsi_stmt (bsi
);
4387 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4389 struct data_reference
*res
;
4390 res
= XCNEW (struct data_reference
);
4391 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4393 return chrec_dont_know
;
4400 /* Search the data references in LOOP, and record the information into
4401 DATAREFS. Returns chrec_dont_know when failing to analyze a
4402 difficult case, returns NULL_TREE otherwise.
4404 TODO: This function should be made smarter so that it can handle address
4405 arithmetic as if they were array accesses, etc. */
4408 find_data_references_in_loop (struct loop
*loop
,
4409 VEC (data_reference_p
, heap
) **datarefs
)
4411 basic_block bb
, *bbs
;
4414 bbs
= get_loop_body_in_dom_order (loop
);
4416 for (i
= 0; i
< loop
->num_nodes
; i
++)
4420 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4423 return chrec_dont_know
;
4431 /* Recursive helper function. */
4434 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4436 /* Inner loops of the nest should not contain siblings. Example:
4437 when there are two consecutive loops,
4448 the dependence relation cannot be captured by the distance
4453 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4455 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4459 /* Return false when the LOOP is not well nested. Otherwise return
4460 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4461 contain the loops from the outermost to the innermost, as they will
4462 appear in the classic distance vector. */
4465 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4467 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4469 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4473 /* Returns true when the data dependences have been computed, false otherwise.
4474 Given a loop nest LOOP, the following vectors are returned:
4475 DATAREFS is initialized to all the array elements contained in this loop,
4476 DEPENDENCE_RELATIONS contains the relations between the data references.
4477 Compute read-read and self relations if
4478 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4481 compute_data_dependences_for_loop (struct loop
*loop
,
4482 bool compute_self_and_read_read_dependences
,
4483 VEC (loop_p
, heap
) **loop_nest
,
4484 VEC (data_reference_p
, heap
) **datarefs
,
4485 VEC (ddr_p
, heap
) **dependence_relations
)
4489 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4491 /* If the loop nest is not well formed, or one of the data references
4492 is not computable, give up without spending time to compute other
4495 || !find_loop_nest (loop
, loop_nest
)
4496 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
4497 || !compute_all_dependences (*datarefs
, dependence_relations
, *loop_nest
,
4498 compute_self_and_read_read_dependences
))
4501 if (dump_file
&& (dump_flags
& TDF_STATS
))
4503 fprintf (dump_file
, "Dependence tester statistics:\n");
4505 fprintf (dump_file
, "Number of dependence tests: %d\n",
4506 dependence_stats
.num_dependence_tests
);
4507 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4508 dependence_stats
.num_dependence_dependent
);
4509 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4510 dependence_stats
.num_dependence_independent
);
4511 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4512 dependence_stats
.num_dependence_undetermined
);
4514 fprintf (dump_file
, "Number of subscript tests: %d\n",
4515 dependence_stats
.num_subscript_tests
);
4516 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4517 dependence_stats
.num_subscript_undetermined
);
4518 fprintf (dump_file
, "Number of same subscript function: %d\n",
4519 dependence_stats
.num_same_subscript_function
);
4521 fprintf (dump_file
, "Number of ziv tests: %d\n",
4522 dependence_stats
.num_ziv
);
4523 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4524 dependence_stats
.num_ziv_dependent
);
4525 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4526 dependence_stats
.num_ziv_independent
);
4527 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4528 dependence_stats
.num_ziv_unimplemented
);
4530 fprintf (dump_file
, "Number of siv tests: %d\n",
4531 dependence_stats
.num_siv
);
4532 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4533 dependence_stats
.num_siv_dependent
);
4534 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4535 dependence_stats
.num_siv_independent
);
4536 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4537 dependence_stats
.num_siv_unimplemented
);
4539 fprintf (dump_file
, "Number of miv tests: %d\n",
4540 dependence_stats
.num_miv
);
4541 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4542 dependence_stats
.num_miv_dependent
);
4543 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4544 dependence_stats
.num_miv_independent
);
4545 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4546 dependence_stats
.num_miv_unimplemented
);
4552 /* Returns true when the data dependences for the basic block BB have been
4553 computed, false otherwise.
4554 DATAREFS is initialized to all the array elements contained in this basic
4555 block, DEPENDENCE_RELATIONS contains the relations between the data
4556 references. Compute read-read and self relations if
4557 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4559 compute_data_dependences_for_bb (basic_block bb
,
4560 bool compute_self_and_read_read_dependences
,
4561 VEC (data_reference_p
, heap
) **datarefs
,
4562 VEC (ddr_p
, heap
) **dependence_relations
)
4564 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4567 return compute_all_dependences (*datarefs
, dependence_relations
, NULL
,
4568 compute_self_and_read_read_dependences
);
4571 /* Entry point (for testing only). Analyze all the data references
4572 and the dependence relations in LOOP.
4574 The data references are computed first.
4576 A relation on these nodes is represented by a complete graph. Some
4577 of the relations could be of no interest, thus the relations can be
4580 In the following function we compute all the relations. This is
4581 just a first implementation that is here for:
4582 - for showing how to ask for the dependence relations,
4583 - for the debugging the whole dependence graph,
4584 - for the dejagnu testcases and maintenance.
4586 It is possible to ask only for a part of the graph, avoiding to
4587 compute the whole dependence graph. The computed dependences are
4588 stored in a knowledge base (KB) such that later queries don't
4589 recompute the same information. The implementation of this KB is
4590 transparent to the optimizer, and thus the KB can be changed with a
4591 more efficient implementation, or the KB could be disabled. */
4593 analyze_all_data_dependences (struct loop
*loop
)
4596 int nb_data_refs
= 10;
4597 VEC (data_reference_p
, heap
) *datarefs
=
4598 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4599 VEC (ddr_p
, heap
) *dependence_relations
=
4600 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4601 VEC (loop_p
, heap
) *loop_nest
= VEC_alloc (loop_p
, heap
, 3);
4603 /* Compute DDs on the whole function. */
4604 compute_data_dependences_for_loop (loop
, false, &loop_nest
, &datarefs
,
4605 &dependence_relations
);
4609 dump_data_dependence_relations (dump_file
, dependence_relations
);
4610 fprintf (dump_file
, "\n\n");
4612 if (dump_flags
& TDF_DETAILS
)
4613 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4615 if (dump_flags
& TDF_STATS
)
4617 unsigned nb_top_relations
= 0;
4618 unsigned nb_bot_relations
= 0;
4619 unsigned nb_chrec_relations
= 0;
4620 struct data_dependence_relation
*ddr
;
4622 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4624 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4627 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4631 nb_chrec_relations
++;
4634 gather_stats_on_scev_database ();
4638 VEC_free (loop_p
, heap
, loop_nest
);
4639 free_dependence_relations (dependence_relations
);
4640 free_data_refs (datarefs
);
4643 /* Computes all the data dependences and check that the results of
4644 several analyzers are the same. */
4647 tree_check_data_deps (void)
4650 struct loop
*loop_nest
;
4652 FOR_EACH_LOOP (li
, loop_nest
, 0)
4653 analyze_all_data_dependences (loop_nest
);
4656 /* Free the memory used by a data dependence relation DDR. */
4659 free_dependence_relation (struct data_dependence_relation
*ddr
)
4664 if (DDR_SUBSCRIPTS (ddr
))
4665 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4666 if (DDR_DIST_VECTS (ddr
))
4667 VEC_free (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
));
4668 if (DDR_DIR_VECTS (ddr
))
4669 VEC_free (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
));
4674 /* Free the memory used by the data dependence relations from
4675 DEPENDENCE_RELATIONS. */
4678 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4681 struct data_dependence_relation
*ddr
;
4683 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
4685 free_dependence_relation (ddr
);
4687 VEC_free (ddr_p
, heap
, dependence_relations
);
4690 /* Free the memory used by the data references from DATAREFS. */
4693 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4696 struct data_reference
*dr
;
4698 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
4700 VEC_free (data_reference_p
, heap
, datarefs
);
4705 /* Dump vertex I in RDG to FILE. */
4708 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4710 struct vertex
*v
= &(rdg
->vertices
[i
]);
4711 struct graph_edge
*e
;
4713 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4714 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4715 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4718 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4719 fprintf (file
, " %d", e
->src
);
4721 fprintf (file
, ") (out:");
4724 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4725 fprintf (file
, " %d", e
->dest
);
4727 fprintf (file
, ")\n");
4728 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4729 fprintf (file
, ")\n");
4732 /* Call dump_rdg_vertex on stderr. */
4735 debug_rdg_vertex (struct graph
*rdg
, int i
)
4737 dump_rdg_vertex (stderr
, rdg
, i
);
4740 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4741 dumped vertices to that bitmap. */
4743 void dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4747 fprintf (file
, "(%d\n", c
);
4749 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4750 if (rdg
->vertices
[i
].component
== c
)
4753 bitmap_set_bit (dumped
, i
);
4755 dump_rdg_vertex (file
, rdg
, i
);
4758 fprintf (file
, ")\n");
4761 /* Call dump_rdg_vertex on stderr. */
4764 debug_rdg_component (struct graph
*rdg
, int c
)
4766 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4769 /* Dump the reduced dependence graph RDG to FILE. */
4772 dump_rdg (FILE *file
, struct graph
*rdg
)
4775 bitmap dumped
= BITMAP_ALLOC (NULL
);
4777 fprintf (file
, "(rdg\n");
4779 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4780 if (!bitmap_bit_p (dumped
, i
))
4781 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4783 fprintf (file
, ")\n");
4784 BITMAP_FREE (dumped
);
4787 /* Call dump_rdg on stderr. */
4790 debug_rdg (struct graph
*rdg
)
4792 dump_rdg (stderr
, rdg
);
4796 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
4800 fprintf (file
, "digraph RDG {\n");
4802 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4804 struct vertex
*v
= &(rdg
->vertices
[i
]);
4805 struct graph_edge
*e
;
4807 /* Highlight reads from memory. */
4808 if (RDG_MEM_READS_STMT (rdg
, i
))
4809 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
4811 /* Highlight stores to memory. */
4812 if (RDG_MEM_WRITE_STMT (rdg
, i
))
4813 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
4816 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4817 switch (RDGE_TYPE (e
))
4820 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
4824 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
4828 /* These are the most common dependences: don't print these. */
4829 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
4833 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
4841 fprintf (file
, "}\n\n");
4844 /* Display the Reduced Dependence Graph using dotty. */
4845 extern void dot_rdg (struct graph
*);
4848 dot_rdg (struct graph
*rdg
)
4850 /* When debugging, enable the following code. This cannot be used
4851 in production compilers because it calls "system". */
4853 FILE *file
= fopen ("/tmp/rdg.dot", "w");
4854 gcc_assert (file
!= NULL
);
4856 dot_rdg_1 (file
, rdg
);
4859 system ("dotty /tmp/rdg.dot &");
4861 dot_rdg_1 (stderr
, rdg
);
4865 /* This structure is used for recording the mapping statement index in
4868 struct GTY(()) rdg_vertex_info
4874 /* Returns the index of STMT in RDG. */
4877 rdg_vertex_for_stmt (struct graph
*rdg
, gimple stmt
)
4879 struct rdg_vertex_info rvi
, *slot
;
4882 slot
= (struct rdg_vertex_info
*) htab_find (rdg
->indices
, &rvi
);
4890 /* Creates an edge in RDG for each distance vector from DDR. The
4891 order that we keep track of in the RDG is the order in which
4892 statements have to be executed. */
4895 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4897 struct graph_edge
*e
;
4899 data_reference_p dra
= DDR_A (ddr
);
4900 data_reference_p drb
= DDR_B (ddr
);
4901 unsigned level
= ddr_dependence_level (ddr
);
4903 /* For non scalar dependences, when the dependence is REVERSED,
4904 statement B has to be executed before statement A. */
4906 && !DDR_REVERSED_P (ddr
))
4908 data_reference_p tmp
= dra
;
4913 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4914 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4916 if (va
< 0 || vb
< 0)
4919 e
= add_edge (rdg
, va
, vb
);
4920 e
->data
= XNEW (struct rdg_edge
);
4922 RDGE_LEVEL (e
) = level
;
4923 RDGE_RELATION (e
) = ddr
;
4925 /* Determines the type of the data dependence. */
4926 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4927 RDGE_TYPE (e
) = input_dd
;
4928 else if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
4929 RDGE_TYPE (e
) = output_dd
;
4930 else if (DR_IS_WRITE (dra
) && DR_IS_READ (drb
))
4931 RDGE_TYPE (e
) = flow_dd
;
4932 else if (DR_IS_READ (dra
) && DR_IS_WRITE (drb
))
4933 RDGE_TYPE (e
) = anti_dd
;
4936 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4937 the index of DEF in RDG. */
4940 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4942 use_operand_p imm_use_p
;
4943 imm_use_iterator iterator
;
4945 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4947 struct graph_edge
*e
;
4948 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4953 e
= add_edge (rdg
, idef
, use
);
4954 e
->data
= XNEW (struct rdg_edge
);
4955 RDGE_TYPE (e
) = flow_dd
;
4956 RDGE_RELATION (e
) = NULL
;
4960 /* Creates the edges of the reduced dependence graph RDG. */
4963 create_rdg_edges (struct graph
*rdg
, VEC (ddr_p
, heap
) *ddrs
)
4966 struct data_dependence_relation
*ddr
;
4967 def_operand_p def_p
;
4970 FOR_EACH_VEC_ELT (ddr_p
, ddrs
, i
, ddr
)
4971 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4972 create_rdg_edge_for_ddr (rdg
, ddr
);
4974 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4975 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4977 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4980 /* Build the vertices of the reduced dependence graph RDG. */
4983 create_rdg_vertices (struct graph
*rdg
, VEC (gimple
, heap
) *stmts
)
4988 FOR_EACH_VEC_ELT (gimple
, stmts
, i
, stmt
)
4990 VEC (data_ref_loc
, heap
) *references
;
4992 struct vertex
*v
= &(rdg
->vertices
[i
]);
4993 struct rdg_vertex_info
*rvi
= XNEW (struct rdg_vertex_info
);
4994 struct rdg_vertex_info
**slot
;
4998 slot
= (struct rdg_vertex_info
**) htab_find_slot (rdg
->indices
, rvi
, INSERT
);
5005 v
->data
= XNEW (struct rdg_vertex
);
5006 RDG_STMT (rdg
, i
) = stmt
;
5008 RDG_MEM_WRITE_STMT (rdg
, i
) = false;
5009 RDG_MEM_READS_STMT (rdg
, i
) = false;
5010 if (gimple_code (stmt
) == GIMPLE_PHI
)
5013 get_references_in_stmt (stmt
, &references
);
5014 FOR_EACH_VEC_ELT (data_ref_loc
, references
, j
, ref
)
5016 RDG_MEM_WRITE_STMT (rdg
, i
) = true;
5018 RDG_MEM_READS_STMT (rdg
, i
) = true;
5020 VEC_free (data_ref_loc
, heap
, references
);
5024 /* Initialize STMTS with all the statements of LOOP. When
5025 INCLUDE_PHIS is true, include also the PHI nodes. The order in
5026 which we discover statements is important as
5027 generate_loops_for_partition is using the same traversal for
5028 identifying statements. */
5031 stmts_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
5034 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
5036 for (i
= 0; i
< loop
->num_nodes
; i
++)
5038 basic_block bb
= bbs
[i
];
5039 gimple_stmt_iterator bsi
;
5042 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
5043 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
5045 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
5047 stmt
= gsi_stmt (bsi
);
5048 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
5049 VEC_safe_push (gimple
, heap
, *stmts
, stmt
);
5056 /* Returns true when all the dependences are computable. */
5059 known_dependences_p (VEC (ddr_p
, heap
) *dependence_relations
)
5064 FOR_EACH_VEC_ELT (ddr_p
, dependence_relations
, i
, ddr
)
5065 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
5071 /* Computes a hash function for element ELT. */
5074 hash_stmt_vertex_info (const void *elt
)
5076 const struct rdg_vertex_info
*const rvi
=
5077 (const struct rdg_vertex_info
*) elt
;
5078 gimple stmt
= rvi
->stmt
;
5080 return htab_hash_pointer (stmt
);
5083 /* Compares database elements E1 and E2. */
5086 eq_stmt_vertex_info (const void *e1
, const void *e2
)
5088 const struct rdg_vertex_info
*elt1
= (const struct rdg_vertex_info
*) e1
;
5089 const struct rdg_vertex_info
*elt2
= (const struct rdg_vertex_info
*) e2
;
5091 return elt1
->stmt
== elt2
->stmt
;
5094 /* Free the element E. */
5097 hash_stmt_vertex_del (void *e
)
5102 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5103 statement of the loop nest, and one edge per data dependence or
5104 scalar dependence. */
5107 build_empty_rdg (int n_stmts
)
5109 int nb_data_refs
= 10;
5110 struct graph
*rdg
= new_graph (n_stmts
);
5112 rdg
->indices
= htab_create (nb_data_refs
, hash_stmt_vertex_info
,
5113 eq_stmt_vertex_info
, hash_stmt_vertex_del
);
5117 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5118 statement of the loop nest, and one edge per data dependence or
5119 scalar dependence. */
5122 build_rdg (struct loop
*loop
,
5123 VEC (loop_p
, heap
) **loop_nest
,
5124 VEC (ddr_p
, heap
) **dependence_relations
,
5125 VEC (data_reference_p
, heap
) **datarefs
)
5127 struct graph
*rdg
= NULL
;
5128 VEC (gimple
, heap
) *stmts
= VEC_alloc (gimple
, heap
, 10);
5130 compute_data_dependences_for_loop (loop
, false, loop_nest
, datarefs
,
5131 dependence_relations
);
5133 if (known_dependences_p (*dependence_relations
))
5135 stmts_from_loop (loop
, &stmts
);
5136 rdg
= build_empty_rdg (VEC_length (gimple
, stmts
));
5137 create_rdg_vertices (rdg
, stmts
);
5138 create_rdg_edges (rdg
, *dependence_relations
);
5141 VEC_free (gimple
, heap
, stmts
);
5145 /* Free the reduced dependence graph RDG. */
5148 free_rdg (struct graph
*rdg
)
5152 for (i
= 0; i
< rdg
->n_vertices
; i
++)
5154 struct vertex
*v
= &(rdg
->vertices
[i
]);
5155 struct graph_edge
*e
;
5157 for (e
= v
->succ
; e
; e
= e
->succ_next
)
5163 htab_delete (rdg
->indices
);
5167 /* Initialize STMTS with all the statements of LOOP that contain a
5171 stores_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
5174 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
5176 for (i
= 0; i
< loop
->num_nodes
; i
++)
5178 basic_block bb
= bbs
[i
];
5179 gimple_stmt_iterator bsi
;
5181 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
5182 if (gimple_vdef (gsi_stmt (bsi
)))
5183 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (bsi
));
5189 /* Returns true when the statement at STMT is of the form "A[i] = 0"
5190 that contains a data reference on its LHS with a stride of the same
5191 size as its unit type. */
5194 stmt_with_adjacent_zero_store_dr_p (gimple stmt
)
5198 struct data_reference
*dr
;
5201 || !gimple_vdef (stmt
)
5202 || !is_gimple_assign (stmt
)
5203 || !gimple_assign_single_p (stmt
)
5204 || !(op1
= gimple_assign_rhs1 (stmt
))
5205 || !(integer_zerop (op1
) || real_zerop (op1
)))
5208 dr
= XCNEW (struct data_reference
);
5209 op0
= gimple_assign_lhs (stmt
);
5211 DR_STMT (dr
) = stmt
;
5214 res
= dr_analyze_innermost (dr
, loop_containing_stmt (stmt
))
5215 && stride_of_unit_type_p (DR_STEP (dr
), TREE_TYPE (op0
));
5221 /* Initialize STMTS with all the statements of LOOP that contain a
5222 store to memory of the form "A[i] = 0". */
5225 stores_zero_from_loop (struct loop
*loop
, VEC (gimple
, heap
) **stmts
)
5229 gimple_stmt_iterator si
;
5231 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
5233 for (i
= 0; i
< loop
->num_nodes
; i
++)
5234 for (bb
= bbs
[i
], si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
5235 if ((stmt
= gsi_stmt (si
))
5236 && stmt_with_adjacent_zero_store_dr_p (stmt
))
5237 VEC_safe_push (gimple
, heap
, *stmts
, gsi_stmt (si
));
5242 /* For a data reference REF, return the declaration of its base
5243 address or NULL_TREE if the base is not determined. */
5246 ref_base_address (gimple stmt
, data_ref_loc
*ref
)
5248 tree base
= NULL_TREE
;
5250 struct data_reference
*dr
= XCNEW (struct data_reference
);
5252 DR_STMT (dr
) = stmt
;
5253 DR_REF (dr
) = *ref
->pos
;
5254 dr_analyze_innermost (dr
, loop_containing_stmt (stmt
));
5255 base_address
= DR_BASE_ADDRESS (dr
);
5260 switch (TREE_CODE (base_address
))
5263 base
= TREE_OPERAND (base_address
, 0);
5267 base
= base_address
;
5276 /* Determines whether the statement from vertex V of the RDG has a
5277 definition used outside the loop that contains this statement. */
5280 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
5282 gimple stmt
= RDG_STMT (rdg
, v
);
5283 struct loop
*loop
= loop_containing_stmt (stmt
);
5284 use_operand_p imm_use_p
;
5285 imm_use_iterator iterator
;
5287 def_operand_p def_p
;
5292 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
5294 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
5296 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)
5304 /* Determines whether statements S1 and S2 access to similar memory
5305 locations. Two memory accesses are considered similar when they
5306 have the same base address declaration, i.e. when their
5307 ref_base_address is the same. */
5310 have_similar_memory_accesses (gimple s1
, gimple s2
)
5314 VEC (data_ref_loc
, heap
) *refs1
, *refs2
;
5315 data_ref_loc
*ref1
, *ref2
;
5317 get_references_in_stmt (s1
, &refs1
);
5318 get_references_in_stmt (s2
, &refs2
);
5320 FOR_EACH_VEC_ELT (data_ref_loc
, refs1
, i
, ref1
)
5322 tree base1
= ref_base_address (s1
, ref1
);
5325 FOR_EACH_VEC_ELT (data_ref_loc
, refs2
, j
, ref2
)
5326 if (base1
== ref_base_address (s2
, ref2
))
5334 VEC_free (data_ref_loc
, heap
, refs1
);
5335 VEC_free (data_ref_loc
, heap
, refs2
);
5339 /* Helper function for the hashtab. */
5342 have_similar_memory_accesses_1 (const void *s1
, const void *s2
)
5344 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple
) s1
),
5345 CONST_CAST_GIMPLE ((const_gimple
) s2
));
5348 /* Helper function for the hashtab. */
5351 ref_base_address_1 (const void *s
)
5353 gimple stmt
= CONST_CAST_GIMPLE ((const_gimple
) s
);
5355 VEC (data_ref_loc
, heap
) *refs
;
5359 get_references_in_stmt (stmt
, &refs
);
5361 FOR_EACH_VEC_ELT (data_ref_loc
, refs
, i
, ref
)
5364 res
= htab_hash_pointer (ref_base_address (stmt
, ref
));
5368 VEC_free (data_ref_loc
, heap
, refs
);
5372 /* Try to remove duplicated write data references from STMTS. */
5375 remove_similar_memory_refs (VEC (gimple
, heap
) **stmts
)
5379 htab_t seen
= htab_create (VEC_length (gimple
, *stmts
), ref_base_address_1
,
5380 have_similar_memory_accesses_1
, NULL
);
5382 for (i
= 0; VEC_iterate (gimple
, *stmts
, i
, stmt
); )
5386 slot
= htab_find_slot (seen
, stmt
, INSERT
);
5389 VEC_ordered_remove (gimple
, *stmts
, i
);
5392 *slot
= (void *) stmt
;
5400 /* Returns the index of PARAMETER in the parameters vector of the
5401 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5404 access_matrix_get_index_for_parameter (tree parameter
,
5405 struct access_matrix
*access_matrix
)
5408 VEC (tree
,heap
) *lambda_parameters
= AM_PARAMETERS (access_matrix
);
5409 tree lambda_parameter
;
5411 FOR_EACH_VEC_ELT (tree
, lambda_parameters
, i
, lambda_parameter
)
5412 if (lambda_parameter
== parameter
)
5413 return i
+ AM_NB_INDUCTION_VARS (access_matrix
);