1 /* Data references and dependences detectors.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass walks a given loop structure searching for array
22 references. The information about the array accesses is recorded
23 in DATA_REFERENCE structures.
25 The basic test for determining the dependences is:
26 given two access functions chrec1 and chrec2 to a same array, and
27 x and y two vectors from the iteration domain, the same element of
28 the array is accessed twice at iterations x and y if and only if:
29 | chrec1 (x) == chrec2 (y).
31 The goals of this analysis are:
33 - to determine the independence: the relation between two
34 independent accesses is qualified with the chrec_known (this
35 information allows a loop parallelization),
37 - when two data references access the same data, to qualify the
38 dependence relation with classic dependence representations:
42 - loop carried level dependence
43 - polyhedron dependence
44 or with the chains of recurrences based representation,
46 - to define a knowledge base for storing the data dependence
49 - to define an interface to access this data.
54 - subscript: given two array accesses a subscript is the tuple
55 composed of the access functions for a given dimension. Example:
56 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
57 (f1, g1), (f2, g2), (f3, g3).
59 - Diophantine equation: an equation whose coefficients and
60 solutions are integer constants, for example the equation
62 has an integer solution x = 1 and y = -1.
66 - "Advanced Compilation for High Performance Computing" by Randy
67 Allen and Ken Kennedy.
68 http://citeseer.ist.psu.edu/goff91practical.html
70 - "Loop Transformations for Restructuring Compilers - The Foundations"
78 #include "coretypes.h"
79 #include "gimple-pretty-print.h"
80 #include "tree-flow.h"
82 #include "tree-data-ref.h"
83 #include "tree-scalar-evolution.h"
85 #include "langhooks.h"
86 #include "tree-affine.h"
89 static struct datadep_stats
91 int num_dependence_tests
;
92 int num_dependence_dependent
;
93 int num_dependence_independent
;
94 int num_dependence_undetermined
;
96 int num_subscript_tests
;
97 int num_subscript_undetermined
;
98 int num_same_subscript_function
;
101 int num_ziv_independent
;
102 int num_ziv_dependent
;
103 int num_ziv_unimplemented
;
106 int num_siv_independent
;
107 int num_siv_dependent
;
108 int num_siv_unimplemented
;
111 int num_miv_independent
;
112 int num_miv_dependent
;
113 int num_miv_unimplemented
;
116 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
117 struct data_reference
*,
118 struct data_reference
*,
120 /* Returns true iff A divides B. */
123 tree_fold_divides_p (const_tree a
, const_tree b
)
125 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
126 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
127 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
));
130 /* Returns true iff A divides B. */
133 int_divides_p (int a
, int b
)
135 return ((b
% a
) == 0);
140 /* Dump into FILE all the data references from DATAREFS. */
143 dump_data_references (FILE *file
, vec
<data_reference_p
> datarefs
)
146 struct data_reference
*dr
;
148 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
149 dump_data_reference (file
, dr
);
152 /* Unified dump into FILE all the data references from DATAREFS. */
155 debug (vec
<data_reference_p
> &ref
)
157 dump_data_references (stderr
, ref
);
161 debug (vec
<data_reference_p
> *ptr
)
166 fprintf (stderr
, "<nil>\n");
170 /* Dump into STDERR all the data references from DATAREFS. */
173 debug_data_references (vec
<data_reference_p
> datarefs
)
175 dump_data_references (stderr
, datarefs
);
178 /* Print to STDERR the data_reference DR. */
181 debug_data_reference (struct data_reference
*dr
)
183 dump_data_reference (stderr
, dr
);
186 /* Dump function for a DATA_REFERENCE structure. */
189 dump_data_reference (FILE *outf
,
190 struct data_reference
*dr
)
194 fprintf (outf
, "#(Data Ref: \n");
195 fprintf (outf
, "# bb: %d \n", gimple_bb (DR_STMT (dr
))->index
);
196 fprintf (outf
, "# stmt: ");
197 print_gimple_stmt (outf
, DR_STMT (dr
), 0, 0);
198 fprintf (outf
, "# ref: ");
199 print_generic_stmt (outf
, DR_REF (dr
), 0);
200 fprintf (outf
, "# base_object: ");
201 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
203 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
205 fprintf (outf
, "# Access function %d: ", i
);
206 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
208 fprintf (outf
, "#)\n");
211 /* Unified dump function for a DATA_REFERENCE structure. */
214 debug (data_reference
&ref
)
216 dump_data_reference (stderr
, &ref
);
220 debug (data_reference
*ptr
)
225 fprintf (stderr
, "<nil>\n");
229 /* Dumps the affine function described by FN to the file OUTF. */
232 dump_affine_function (FILE *outf
, affine_fn fn
)
237 print_generic_expr (outf
, fn
[0], TDF_SLIM
);
238 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
240 fprintf (outf
, " + ");
241 print_generic_expr (outf
, coef
, TDF_SLIM
);
242 fprintf (outf
, " * x_%u", i
);
246 /* Dumps the conflict function CF to the file OUTF. */
249 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
253 if (cf
->n
== NO_DEPENDENCE
)
254 fprintf (outf
, "no dependence");
255 else if (cf
->n
== NOT_KNOWN
)
256 fprintf (outf
, "not known");
259 for (i
= 0; i
< cf
->n
; i
++)
264 dump_affine_function (outf
, cf
->fns
[i
]);
270 /* Dump function for a SUBSCRIPT structure. */
273 dump_subscript (FILE *outf
, struct subscript
*subscript
)
275 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
277 fprintf (outf
, "\n (subscript \n");
278 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
279 dump_conflict_function (outf
, cf
);
280 if (CF_NONTRIVIAL_P (cf
))
282 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
283 fprintf (outf
, "\n last_conflict: ");
284 print_generic_expr (outf
, last_iteration
, 0);
287 cf
= SUB_CONFLICTS_IN_B (subscript
);
288 fprintf (outf
, "\n iterations_that_access_an_element_twice_in_B: ");
289 dump_conflict_function (outf
, cf
);
290 if (CF_NONTRIVIAL_P (cf
))
292 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
293 fprintf (outf
, "\n last_conflict: ");
294 print_generic_expr (outf
, last_iteration
, 0);
297 fprintf (outf
, "\n (Subscript distance: ");
298 print_generic_expr (outf
, SUB_DISTANCE (subscript
), 0);
299 fprintf (outf
, " ))\n");
302 /* Print the classic direction vector DIRV to OUTF. */
305 print_direction_vector (FILE *outf
,
311 for (eq
= 0; eq
< length
; eq
++)
313 enum data_dependence_direction dir
= ((enum data_dependence_direction
)
319 fprintf (outf
, " +");
322 fprintf (outf
, " -");
325 fprintf (outf
, " =");
327 case dir_positive_or_equal
:
328 fprintf (outf
, " +=");
330 case dir_positive_or_negative
:
331 fprintf (outf
, " +-");
333 case dir_negative_or_equal
:
334 fprintf (outf
, " -=");
337 fprintf (outf
, " *");
340 fprintf (outf
, "indep");
344 fprintf (outf
, "\n");
347 /* Print a vector of direction vectors. */
350 print_dir_vectors (FILE *outf
, vec
<lambda_vector
> dir_vects
,
356 FOR_EACH_VEC_ELT (dir_vects
, j
, v
)
357 print_direction_vector (outf
, v
, length
);
360 /* Print out a vector VEC of length N to OUTFILE. */
363 print_lambda_vector (FILE * outfile
, lambda_vector vector
, int n
)
367 for (i
= 0; i
< n
; i
++)
368 fprintf (outfile
, "%3d ", vector
[i
]);
369 fprintf (outfile
, "\n");
372 /* Print a vector of distance vectors. */
375 print_dist_vectors (FILE *outf
, vec
<lambda_vector
> dist_vects
,
381 FOR_EACH_VEC_ELT (dist_vects
, j
, v
)
382 print_lambda_vector (outf
, v
, length
);
385 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
388 dump_data_dependence_relation (FILE *outf
,
389 struct data_dependence_relation
*ddr
)
391 struct data_reference
*dra
, *drb
;
393 fprintf (outf
, "(Data Dep: \n");
395 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
402 dump_data_reference (outf
, dra
);
404 fprintf (outf
, " (nil)\n");
406 dump_data_reference (outf
, drb
);
408 fprintf (outf
, " (nil)\n");
410 fprintf (outf
, " (don't know)\n)\n");
416 dump_data_reference (outf
, dra
);
417 dump_data_reference (outf
, drb
);
419 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
420 fprintf (outf
, " (no dependence)\n");
422 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
427 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
429 fprintf (outf
, " access_fn_A: ");
430 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
431 fprintf (outf
, " access_fn_B: ");
432 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
433 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
436 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
437 fprintf (outf
, " loop nest: (");
438 FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr
), i
, loopi
)
439 fprintf (outf
, "%d ", loopi
->num
);
440 fprintf (outf
, ")\n");
442 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
444 fprintf (outf
, " distance_vector: ");
445 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
449 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
451 fprintf (outf
, " direction_vector: ");
452 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
457 fprintf (outf
, ")\n");
463 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
465 dump_data_dependence_relation (stderr
, ddr
);
468 /* Dump into FILE all the dependence relations from DDRS. */
471 dump_data_dependence_relations (FILE *file
,
475 struct data_dependence_relation
*ddr
;
477 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
478 dump_data_dependence_relation (file
, ddr
);
482 debug (vec
<ddr_p
> &ref
)
484 dump_data_dependence_relations (stderr
, ref
);
488 debug (vec
<ddr_p
> *ptr
)
493 fprintf (stderr
, "<nil>\n");
497 /* Dump to STDERR all the dependence relations from DDRS. */
500 debug_data_dependence_relations (vec
<ddr_p
> ddrs
)
502 dump_data_dependence_relations (stderr
, ddrs
);
505 /* Dumps the distance and direction vectors in FILE. DDRS contains
506 the dependence relations, and VECT_SIZE is the size of the
507 dependence vectors, or in other words the number of loops in the
511 dump_dist_dir_vectors (FILE *file
, vec
<ddr_p
> ddrs
)
514 struct data_dependence_relation
*ddr
;
517 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
518 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
520 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), j
, v
)
522 fprintf (file
, "DISTANCE_V (");
523 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
524 fprintf (file
, ")\n");
527 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), j
, v
)
529 fprintf (file
, "DIRECTION_V (");
530 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
531 fprintf (file
, ")\n");
535 fprintf (file
, "\n\n");
538 /* Dumps the data dependence relations DDRS in FILE. */
541 dump_ddrs (FILE *file
, vec
<ddr_p
> ddrs
)
544 struct data_dependence_relation
*ddr
;
546 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
547 dump_data_dependence_relation (file
, ddr
);
549 fprintf (file
, "\n\n");
553 debug_ddrs (vec
<ddr_p
> ddrs
)
555 dump_ddrs (stderr
, ddrs
);
558 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
559 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
560 constant of type ssizetype, and returns true. If we cannot do this
561 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
565 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
566 tree
*var
, tree
*off
)
570 enum tree_code ocode
= code
;
578 *var
= build_int_cst (type
, 0);
579 *off
= fold_convert (ssizetype
, op0
);
582 case POINTER_PLUS_EXPR
:
587 split_constant_offset (op0
, &var0
, &off0
);
588 split_constant_offset (op1
, &var1
, &off1
);
589 *var
= fold_build2 (code
, type
, var0
, var1
);
590 *off
= size_binop (ocode
, off0
, off1
);
594 if (TREE_CODE (op1
) != INTEGER_CST
)
597 split_constant_offset (op0
, &var0
, &off0
);
598 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
599 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
605 HOST_WIDE_INT pbitsize
, pbitpos
;
606 enum machine_mode pmode
;
607 int punsignedp
, pvolatilep
;
609 op0
= TREE_OPERAND (op0
, 0);
610 base
= get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
,
611 &pmode
, &punsignedp
, &pvolatilep
, false);
613 if (pbitpos
% BITS_PER_UNIT
!= 0)
615 base
= build_fold_addr_expr (base
);
616 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
620 split_constant_offset (poffset
, &poffset
, &off1
);
621 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
622 if (POINTER_TYPE_P (TREE_TYPE (base
)))
623 base
= fold_build_pointer_plus (base
, poffset
);
625 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
626 fold_convert (TREE_TYPE (base
), poffset
));
629 var0
= fold_convert (type
, base
);
631 /* If variable length types are involved, punt, otherwise casts
632 might be converted into ARRAY_REFs in gimplify_conversion.
633 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
634 possibly no longer appears in current GIMPLE, might resurface.
635 This perhaps could run
636 if (CONVERT_EXPR_P (var0))
638 gimplify_conversion (&var0);
639 // Attempt to fill in any within var0 found ARRAY_REF's
640 // element size from corresponding op embedded ARRAY_REF,
641 // if unsuccessful, just punt.
643 while (POINTER_TYPE_P (type
))
644 type
= TREE_TYPE (type
);
645 if (int_size_in_bytes (type
) < 0)
655 gimple def_stmt
= SSA_NAME_DEF_STMT (op0
);
656 enum tree_code subcode
;
658 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
661 var0
= gimple_assign_rhs1 (def_stmt
);
662 subcode
= gimple_assign_rhs_code (def_stmt
);
663 var1
= gimple_assign_rhs2 (def_stmt
);
665 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
669 /* We must not introduce undefined overflow, and we must not change the value.
670 Hence we're okay if the inner type doesn't overflow to start with
671 (pointer or signed), the outer type also is an integer or pointer
672 and the outer precision is at least as large as the inner. */
673 tree itype
= TREE_TYPE (op0
);
674 if ((POINTER_TYPE_P (itype
)
675 || (INTEGRAL_TYPE_P (itype
) && TYPE_OVERFLOW_UNDEFINED (itype
)))
676 && TYPE_PRECISION (type
) >= TYPE_PRECISION (itype
)
677 && (POINTER_TYPE_P (type
) || INTEGRAL_TYPE_P (type
)))
679 split_constant_offset (op0
, &var0
, off
);
680 *var
= fold_convert (type
, var0
);
691 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
692 will be ssizetype. */
695 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
697 tree type
= TREE_TYPE (exp
), otype
, op0
, op1
, e
, o
;
701 *off
= ssize_int (0);
704 if (tree_is_chrec (exp
)
705 || get_gimple_rhs_class (TREE_CODE (exp
)) == GIMPLE_TERNARY_RHS
)
708 otype
= TREE_TYPE (exp
);
709 code
= TREE_CODE (exp
);
710 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
711 if (split_constant_offset_1 (otype
, op0
, code
, op1
, &e
, &o
))
713 *var
= fold_convert (type
, e
);
718 /* Returns the address ADDR of an object in a canonical shape (without nop
719 casts, and with type of pointer to the object). */
722 canonicalize_base_object_address (tree addr
)
728 /* The base address may be obtained by casting from integer, in that case
730 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
733 if (TREE_CODE (addr
) != ADDR_EXPR
)
736 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
739 /* Analyzes the behavior of the memory reference DR in the innermost loop or
740 basic block that contains it. Returns true if analysis succeed or false
744 dr_analyze_innermost (struct data_reference
*dr
, struct loop
*nest
)
746 gimple stmt
= DR_STMT (dr
);
747 struct loop
*loop
= loop_containing_stmt (stmt
);
748 tree ref
= DR_REF (dr
);
749 HOST_WIDE_INT pbitsize
, pbitpos
;
751 enum machine_mode pmode
;
752 int punsignedp
, pvolatilep
;
753 affine_iv base_iv
, offset_iv
;
754 tree init
, dinit
, step
;
755 bool in_loop
= (loop
&& loop
->num
);
757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
758 fprintf (dump_file
, "analyze_innermost: ");
760 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
761 &pmode
, &punsignedp
, &pvolatilep
, false);
762 gcc_assert (base
!= NULL_TREE
);
764 if (pbitpos
% BITS_PER_UNIT
!= 0)
766 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
767 fprintf (dump_file
, "failed: bit offset alignment.\n");
771 if (TREE_CODE (base
) == MEM_REF
)
773 if (!integer_zerop (TREE_OPERAND (base
, 1)))
775 double_int moff
= mem_ref_offset (base
);
776 tree mofft
= double_int_to_tree (sizetype
, moff
);
780 poffset
= size_binop (PLUS_EXPR
, poffset
, mofft
);
782 base
= TREE_OPERAND (base
, 0);
785 base
= build_fold_addr_expr (base
);
789 if (!simple_iv (loop
, loop_containing_stmt (stmt
), base
, &base_iv
,
790 nest
? true : false))
794 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
795 fprintf (dump_file
, "failed: evolution of base is not"
802 base_iv
.step
= ssize_int (0);
803 base_iv
.no_overflow
= true;
810 base_iv
.step
= ssize_int (0);
811 base_iv
.no_overflow
= true;
816 offset_iv
.base
= ssize_int (0);
817 offset_iv
.step
= ssize_int (0);
823 offset_iv
.base
= poffset
;
824 offset_iv
.step
= ssize_int (0);
826 else if (!simple_iv (loop
, loop_containing_stmt (stmt
),
828 nest
? true : false))
832 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
833 fprintf (dump_file
, "failed: evolution of offset is not"
839 offset_iv
.base
= poffset
;
840 offset_iv
.step
= ssize_int (0);
845 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
846 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
847 init
= size_binop (PLUS_EXPR
, init
, dinit
);
848 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
849 init
= size_binop (PLUS_EXPR
, init
, dinit
);
851 step
= size_binop (PLUS_EXPR
,
852 fold_convert (ssizetype
, base_iv
.step
),
853 fold_convert (ssizetype
, offset_iv
.step
));
855 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
857 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
861 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
864 fprintf (dump_file
, "success.\n");
869 /* Determines the base object and the list of indices of memory reference
870 DR, analyzed in LOOP and instantiated in loop nest NEST. */
873 dr_analyze_indices (struct data_reference
*dr
, loop_p nest
, loop_p loop
)
875 vec
<tree
> access_fns
= vNULL
;
877 tree base
, off
, access_fn
;
878 basic_block before_loop
;
880 /* If analyzing a basic-block there are no indices to analyze
881 and thus no access functions. */
884 DR_BASE_OBJECT (dr
) = DR_REF (dr
);
885 DR_ACCESS_FNS (dr
).create (0);
890 before_loop
= block_before_loop (nest
);
892 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
893 into a two element array with a constant index. The base is
894 then just the immediate underlying object. */
895 if (TREE_CODE (ref
) == REALPART_EXPR
)
897 ref
= TREE_OPERAND (ref
, 0);
898 access_fns
.safe_push (integer_zero_node
);
900 else if (TREE_CODE (ref
) == IMAGPART_EXPR
)
902 ref
= TREE_OPERAND (ref
, 0);
903 access_fns
.safe_push (integer_one_node
);
906 /* Analyze access functions of dimensions we know to be independent. */
907 while (handled_component_p (ref
))
909 if (TREE_CODE (ref
) == ARRAY_REF
)
911 op
= TREE_OPERAND (ref
, 1);
912 access_fn
= analyze_scalar_evolution (loop
, op
);
913 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
914 access_fns
.safe_push (access_fn
);
916 else if (TREE_CODE (ref
) == COMPONENT_REF
917 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref
, 0))) == RECORD_TYPE
)
919 /* For COMPONENT_REFs of records (but not unions!) use the
920 FIELD_DECL offset as constant access function so we can
921 disambiguate a[i].f1 and a[i].f2. */
922 tree off
= component_ref_field_offset (ref
);
923 off
= size_binop (PLUS_EXPR
,
924 size_binop (MULT_EXPR
,
925 fold_convert (bitsizetype
, off
),
926 bitsize_int (BITS_PER_UNIT
)),
927 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1)));
928 access_fns
.safe_push (off
);
931 /* If we have an unhandled component we could not translate
932 to an access function stop analyzing. We have determined
933 our base object in this case. */
936 ref
= TREE_OPERAND (ref
, 0);
939 /* If the address operand of a MEM_REF base has an evolution in the
940 analyzed nest, add it as an additional independent access-function. */
941 if (TREE_CODE (ref
) == MEM_REF
)
943 op
= TREE_OPERAND (ref
, 0);
944 access_fn
= analyze_scalar_evolution (loop
, op
);
945 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
946 if (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
949 tree memoff
= TREE_OPERAND (ref
, 1);
950 base
= initial_condition (access_fn
);
951 orig_type
= TREE_TYPE (base
);
952 STRIP_USELESS_TYPE_CONVERSION (base
);
953 split_constant_offset (base
, &base
, &off
);
954 /* Fold the MEM_REF offset into the evolutions initial
955 value to make more bases comparable. */
956 if (!integer_zerop (memoff
))
958 off
= size_binop (PLUS_EXPR
, off
,
959 fold_convert (ssizetype
, memoff
));
960 memoff
= build_int_cst (TREE_TYPE (memoff
), 0);
962 access_fn
= chrec_replace_initial_condition
963 (access_fn
, fold_convert (orig_type
, off
));
964 /* ??? This is still not a suitable base object for
965 dr_may_alias_p - the base object needs to be an
966 access that covers the object as whole. With
967 an evolution in the pointer this cannot be
969 As a band-aid, mark the access so we can special-case
970 it in dr_may_alias_p. */
971 ref
= fold_build2_loc (EXPR_LOCATION (ref
),
972 MEM_REF
, TREE_TYPE (ref
),
974 DR_UNCONSTRAINED_BASE (dr
) = true;
975 access_fns
.safe_push (access_fn
);
978 else if (DECL_P (ref
))
980 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
981 ref
= build2 (MEM_REF
, TREE_TYPE (ref
),
982 build_fold_addr_expr (ref
),
983 build_int_cst (reference_alias_ptr_type (ref
), 0));
986 DR_BASE_OBJECT (dr
) = ref
;
987 DR_ACCESS_FNS (dr
) = access_fns
;
990 /* Extracts the alias analysis information from the memory reference DR. */
993 dr_analyze_alias (struct data_reference
*dr
)
995 tree ref
= DR_REF (dr
);
996 tree base
= get_base_address (ref
), addr
;
998 if (INDIRECT_REF_P (base
)
999 || TREE_CODE (base
) == MEM_REF
)
1001 addr
= TREE_OPERAND (base
, 0);
1002 if (TREE_CODE (addr
) == SSA_NAME
)
1003 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
1007 /* Frees data reference DR. */
1010 free_data_ref (data_reference_p dr
)
1012 DR_ACCESS_FNS (dr
).release ();
1016 /* Analyzes memory reference MEMREF accessed in STMT. The reference
1017 is read if IS_READ is true, write otherwise. Returns the
1018 data_reference description of MEMREF. NEST is the outermost loop
1019 in which the reference should be instantiated, LOOP is the loop in
1020 which the data reference should be analyzed. */
1022 struct data_reference
*
1023 create_data_ref (loop_p nest
, loop_p loop
, tree memref
, gimple stmt
,
1026 struct data_reference
*dr
;
1028 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1030 fprintf (dump_file
, "Creating dr for ");
1031 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1032 fprintf (dump_file
, "\n");
1035 dr
= XCNEW (struct data_reference
);
1036 DR_STMT (dr
) = stmt
;
1037 DR_REF (dr
) = memref
;
1038 DR_IS_READ (dr
) = is_read
;
1040 dr_analyze_innermost (dr
, nest
);
1041 dr_analyze_indices (dr
, nest
, loop
);
1042 dr_analyze_alias (dr
);
1044 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1047 fprintf (dump_file
, "\tbase_address: ");
1048 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
1049 fprintf (dump_file
, "\n\toffset from base address: ");
1050 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
1051 fprintf (dump_file
, "\n\tconstant offset from base address: ");
1052 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
1053 fprintf (dump_file
, "\n\tstep: ");
1054 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
1055 fprintf (dump_file
, "\n\taligned to: ");
1056 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
1057 fprintf (dump_file
, "\n\tbase_object: ");
1058 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
1059 fprintf (dump_file
, "\n");
1060 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
1062 fprintf (dump_file
, "\tAccess function %d: ", i
);
1063 print_generic_stmt (dump_file
, DR_ACCESS_FN (dr
, i
), TDF_SLIM
);
1070 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1073 dr_equal_offsets_p1 (tree offset1
, tree offset2
)
1077 STRIP_NOPS (offset1
);
1078 STRIP_NOPS (offset2
);
1080 if (offset1
== offset2
)
1083 if (TREE_CODE (offset1
) != TREE_CODE (offset2
)
1084 || (!BINARY_CLASS_P (offset1
) && !UNARY_CLASS_P (offset1
)))
1087 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 0),
1088 TREE_OPERAND (offset2
, 0));
1090 if (!res
|| !BINARY_CLASS_P (offset1
))
1093 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 1),
1094 TREE_OPERAND (offset2
, 1));
1099 /* Check if DRA and DRB have equal offsets. */
1101 dr_equal_offsets_p (struct data_reference
*dra
,
1102 struct data_reference
*drb
)
1104 tree offset1
, offset2
;
1106 offset1
= DR_OFFSET (dra
);
1107 offset2
= DR_OFFSET (drb
);
1109 return dr_equal_offsets_p1 (offset1
, offset2
);
1112 /* Returns true if FNA == FNB. */
1115 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
1117 unsigned i
, n
= fna
.length ();
1119 if (n
!= fnb
.length ())
1122 for (i
= 0; i
< n
; i
++)
1123 if (!operand_equal_p (fna
[i
], fnb
[i
], 0))
1129 /* If all the functions in CF are the same, returns one of them,
1130 otherwise returns NULL. */
1133 common_affine_function (conflict_function
*cf
)
1138 if (!CF_NONTRIVIAL_P (cf
))
1143 for (i
= 1; i
< cf
->n
; i
++)
1144 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
1150 /* Returns the base of the affine function FN. */
1153 affine_function_base (affine_fn fn
)
1158 /* Returns true if FN is a constant. */
1161 affine_function_constant_p (affine_fn fn
)
1166 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
1167 if (!integer_zerop (coef
))
1173 /* Returns true if FN is the zero constant function. */
1176 affine_function_zero_p (affine_fn fn
)
1178 return (integer_zerop (affine_function_base (fn
))
1179 && affine_function_constant_p (fn
));
1182 /* Returns a signed integer type with the largest precision from TA
1186 signed_type_for_types (tree ta
, tree tb
)
1188 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
1189 return signed_type_for (ta
);
1191 return signed_type_for (tb
);
1194 /* Applies operation OP on affine functions FNA and FNB, and returns the
1198 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
1204 if (fnb
.length () > fna
.length ())
1216 for (i
= 0; i
< n
; i
++)
1218 tree type
= signed_type_for_types (TREE_TYPE (fna
[i
]),
1219 TREE_TYPE (fnb
[i
]));
1220 ret
.quick_push (fold_build2 (op
, type
, fna
[i
], fnb
[i
]));
1223 for (; fna
.iterate (i
, &coef
); i
++)
1224 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1225 coef
, integer_zero_node
));
1226 for (; fnb
.iterate (i
, &coef
); i
++)
1227 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1228 integer_zero_node
, coef
));
1233 /* Returns the sum of affine functions FNA and FNB. */
1236 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1238 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1241 /* Returns the difference of affine functions FNA and FNB. */
1244 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1246 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1249 /* Frees affine function FN. */
1252 affine_fn_free (affine_fn fn
)
1257 /* Determine for each subscript in the data dependence relation DDR
1261 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1263 conflict_function
*cf_a
, *cf_b
;
1264 affine_fn fn_a
, fn_b
, diff
;
1266 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1270 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1272 struct subscript
*subscript
;
1274 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1275 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1276 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1278 fn_a
= common_affine_function (cf_a
);
1279 fn_b
= common_affine_function (cf_b
);
1280 if (!fn_a
.exists () || !fn_b
.exists ())
1282 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1285 diff
= affine_fn_minus (fn_a
, fn_b
);
1287 if (affine_function_constant_p (diff
))
1288 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1290 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1292 affine_fn_free (diff
);
1297 /* Returns the conflict function for "unknown". */
1299 static conflict_function
*
1300 conflict_fn_not_known (void)
1302 conflict_function
*fn
= XCNEW (conflict_function
);
1308 /* Returns the conflict function for "independent". */
1310 static conflict_function
*
1311 conflict_fn_no_dependence (void)
1313 conflict_function
*fn
= XCNEW (conflict_function
);
1314 fn
->n
= NO_DEPENDENCE
;
1319 /* Returns true if the address of OBJ is invariant in LOOP. */
1322 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1324 while (handled_component_p (obj
))
1326 if (TREE_CODE (obj
) == ARRAY_REF
)
1328 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1329 need to check the stride and the lower bound of the reference. */
1330 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1332 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1336 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1338 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1342 obj
= TREE_OPERAND (obj
, 0);
1345 if (!INDIRECT_REF_P (obj
)
1346 && TREE_CODE (obj
) != MEM_REF
)
1349 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1353 /* Returns false if we can prove that data references A and B do not alias,
1354 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1358 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
,
1361 tree addr_a
= DR_BASE_OBJECT (a
);
1362 tree addr_b
= DR_BASE_OBJECT (b
);
1364 /* If we are not processing a loop nest but scalar code we
1365 do not need to care about possible cross-iteration dependences
1366 and thus can process the full original reference. Do so,
1367 similar to how loop invariant motion applies extra offset-based
1371 aff_tree off1
, off2
;
1372 double_int size1
, size2
;
1373 get_inner_reference_aff (DR_REF (a
), &off1
, &size1
);
1374 get_inner_reference_aff (DR_REF (b
), &off2
, &size2
);
1375 aff_combination_scale (&off1
, double_int_minus_one
);
1376 aff_combination_add (&off2
, &off1
);
1377 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1381 /* If we had an evolution in a MEM_REF BASE_OBJECT we do not know
1382 the size of the base-object. So we cannot do any offset/overlap
1383 based analysis but have to rely on points-to information only. */
1384 if (TREE_CODE (addr_a
) == MEM_REF
1385 && DR_UNCONSTRAINED_BASE (a
))
1387 if (TREE_CODE (addr_b
) == MEM_REF
1388 && DR_UNCONSTRAINED_BASE (b
))
1389 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1390 TREE_OPERAND (addr_b
, 0));
1392 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1393 build_fold_addr_expr (addr_b
));
1395 else if (TREE_CODE (addr_b
) == MEM_REF
1396 && DR_UNCONSTRAINED_BASE (b
))
1397 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a
),
1398 TREE_OPERAND (addr_b
, 0));
1400 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
1401 that is being subsetted in the loop nest. */
1402 if (DR_IS_WRITE (a
) && DR_IS_WRITE (b
))
1403 return refs_output_dependent_p (addr_a
, addr_b
);
1404 else if (DR_IS_READ (a
) && DR_IS_WRITE (b
))
1405 return refs_anti_dependent_p (addr_a
, addr_b
);
1406 return refs_may_alias_p (addr_a
, addr_b
);
1409 /* Initialize a data dependence relation between data accesses A and
1410 B. NB_LOOPS is the number of loops surrounding the references: the
1411 size of the classic distance/direction vectors. */
1413 struct data_dependence_relation
*
1414 initialize_data_dependence_relation (struct data_reference
*a
,
1415 struct data_reference
*b
,
1416 vec
<loop_p
> loop_nest
)
1418 struct data_dependence_relation
*res
;
1421 res
= XNEW (struct data_dependence_relation
);
1424 DDR_LOOP_NEST (res
).create (0);
1425 DDR_REVERSED_P (res
) = false;
1426 DDR_SUBSCRIPTS (res
).create (0);
1427 DDR_DIR_VECTS (res
).create (0);
1428 DDR_DIST_VECTS (res
).create (0);
1430 if (a
== NULL
|| b
== NULL
)
1432 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1436 /* If the data references do not alias, then they are independent. */
1437 if (!dr_may_alias_p (a
, b
, loop_nest
.exists ()))
1439 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1443 /* The case where the references are exactly the same. */
1444 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1446 if (loop_nest
.exists ()
1447 && !object_address_invariant_in_loop_p (loop_nest
[0],
1448 DR_BASE_OBJECT (a
)))
1450 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1453 DDR_AFFINE_P (res
) = true;
1454 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1455 DDR_SUBSCRIPTS (res
).create (DR_NUM_DIMENSIONS (a
));
1456 DDR_LOOP_NEST (res
) = loop_nest
;
1457 DDR_INNER_LOOP (res
) = 0;
1458 DDR_SELF_REFERENCE (res
) = true;
1459 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1461 struct subscript
*subscript
;
1463 subscript
= XNEW (struct subscript
);
1464 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1465 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1466 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1467 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1468 DDR_SUBSCRIPTS (res
).safe_push (subscript
);
1473 /* If the references do not access the same object, we do not know
1474 whether they alias or not. */
1475 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1477 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1481 /* If the base of the object is not invariant in the loop nest, we cannot
1482 analyze it. TODO -- in fact, it would suffice to record that there may
1483 be arbitrary dependences in the loops where the base object varies. */
1484 if (loop_nest
.exists ()
1485 && !object_address_invariant_in_loop_p (loop_nest
[0],
1486 DR_BASE_OBJECT (a
)))
1488 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1492 /* If the number of dimensions of the access to not agree we can have
1493 a pointer access to a component of the array element type and an
1494 array access while the base-objects are still the same. Punt. */
1495 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
1497 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1501 DDR_AFFINE_P (res
) = true;
1502 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1503 DDR_SUBSCRIPTS (res
).create (DR_NUM_DIMENSIONS (a
));
1504 DDR_LOOP_NEST (res
) = loop_nest
;
1505 DDR_INNER_LOOP (res
) = 0;
1506 DDR_SELF_REFERENCE (res
) = false;
1508 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1510 struct subscript
*subscript
;
1512 subscript
= XNEW (struct subscript
);
1513 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1514 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1515 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1516 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1517 DDR_SUBSCRIPTS (res
).safe_push (subscript
);
1523 /* Frees memory used by the conflict function F. */
1526 free_conflict_function (conflict_function
*f
)
1530 if (CF_NONTRIVIAL_P (f
))
1532 for (i
= 0; i
< f
->n
; i
++)
1533 affine_fn_free (f
->fns
[i
]);
1538 /* Frees memory used by SUBSCRIPTS. */
1541 free_subscripts (vec
<subscript_p
> subscripts
)
1546 FOR_EACH_VEC_ELT (subscripts
, i
, s
)
1548 free_conflict_function (s
->conflicting_iterations_in_a
);
1549 free_conflict_function (s
->conflicting_iterations_in_b
);
1552 subscripts
.release ();
1555 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1559 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1562 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1563 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1564 DDR_SUBSCRIPTS (ddr
).create (0);
1567 /* The dependence relation DDR cannot be represented by a distance
1571 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1573 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1574 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1576 DDR_AFFINE_P (ddr
) = false;
1581 /* This section contains the classic Banerjee tests. */
1583 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1584 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1587 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1589 return (evolution_function_is_constant_p (chrec_a
)
1590 && evolution_function_is_constant_p (chrec_b
));
1593 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1594 variable, i.e., if the SIV (Single Index Variable) test is true. */
1597 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1599 if ((evolution_function_is_constant_p (chrec_a
)
1600 && evolution_function_is_univariate_p (chrec_b
))
1601 || (evolution_function_is_constant_p (chrec_b
)
1602 && evolution_function_is_univariate_p (chrec_a
)))
1605 if (evolution_function_is_univariate_p (chrec_a
)
1606 && evolution_function_is_univariate_p (chrec_b
))
1608 switch (TREE_CODE (chrec_a
))
1610 case POLYNOMIAL_CHREC
:
1611 switch (TREE_CODE (chrec_b
))
1613 case POLYNOMIAL_CHREC
:
1614 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1629 /* Creates a conflict function with N dimensions. The affine functions
1630 in each dimension follow. */
1632 static conflict_function
*
1633 conflict_fn (unsigned n
, ...)
1636 conflict_function
*ret
= XCNEW (conflict_function
);
1639 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1643 for (i
= 0; i
< n
; i
++)
1644 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1650 /* Returns constant affine function with value CST. */
1653 affine_fn_cst (tree cst
)
1657 fn
.quick_push (cst
);
1661 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1664 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1667 fn
.create (dim
+ 1);
1670 gcc_assert (dim
> 0);
1671 fn
.quick_push (cst
);
1672 for (i
= 1; i
< dim
; i
++)
1673 fn
.quick_push (integer_zero_node
);
1674 fn
.quick_push (coef
);
1678 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1679 *OVERLAPS_B are initialized to the functions that describe the
1680 relation between the elements accessed twice by CHREC_A and
1681 CHREC_B. For k >= 0, the following property is verified:
1683 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1686 analyze_ziv_subscript (tree chrec_a
,
1688 conflict_function
**overlaps_a
,
1689 conflict_function
**overlaps_b
,
1690 tree
*last_conflicts
)
1692 tree type
, difference
;
1693 dependence_stats
.num_ziv
++;
1695 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1696 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1698 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1699 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1700 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1701 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1703 switch (TREE_CODE (difference
))
1706 if (integer_zerop (difference
))
1708 /* The difference is equal to zero: the accessed index
1709 overlaps for each iteration in the loop. */
1710 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1711 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1712 *last_conflicts
= chrec_dont_know
;
1713 dependence_stats
.num_ziv_dependent
++;
1717 /* The accesses do not overlap. */
1718 *overlaps_a
= conflict_fn_no_dependence ();
1719 *overlaps_b
= conflict_fn_no_dependence ();
1720 *last_conflicts
= integer_zero_node
;
1721 dependence_stats
.num_ziv_independent
++;
1726 /* We're not sure whether the indexes overlap. For the moment,
1727 conservatively answer "don't know". */
1728 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1729 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1731 *overlaps_a
= conflict_fn_not_known ();
1732 *overlaps_b
= conflict_fn_not_known ();
1733 *last_conflicts
= chrec_dont_know
;
1734 dependence_stats
.num_ziv_unimplemented
++;
1738 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1739 fprintf (dump_file
, ")\n");
1742 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1743 and only if it fits to the int type. If this is not the case, or the
1744 bound on the number of iterations of LOOP could not be derived, returns
1748 max_stmt_executions_tree (struct loop
*loop
)
1752 if (!max_stmt_executions (loop
, &nit
))
1753 return chrec_dont_know
;
1755 if (!double_int_fits_to_tree_p (unsigned_type_node
, nit
))
1756 return chrec_dont_know
;
1758 return double_int_to_tree (unsigned_type_node
, nit
);
1761 /* Determine whether the CHREC is always positive/negative. If the expression
1762 cannot be statically analyzed, return false, otherwise set the answer into
1766 chrec_is_positive (tree chrec
, bool *value
)
1768 bool value0
, value1
, value2
;
1769 tree end_value
, nb_iter
;
1771 switch (TREE_CODE (chrec
))
1773 case POLYNOMIAL_CHREC
:
1774 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
1775 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
1778 /* FIXME -- overflows. */
1779 if (value0
== value1
)
1785 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
1786 and the proof consists in showing that the sign never
1787 changes during the execution of the loop, from 0 to
1788 loop->nb_iterations. */
1789 if (!evolution_function_is_affine_p (chrec
))
1792 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
1793 if (chrec_contains_undetermined (nb_iter
))
1797 /* TODO -- If the test is after the exit, we may decrease the number of
1798 iterations by one. */
1800 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
1803 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
1805 if (!chrec_is_positive (end_value
, &value2
))
1809 return value0
== value1
;
1812 switch (tree_int_cst_sgn (chrec
))
1831 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1832 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1833 *OVERLAPS_B are initialized to the functions that describe the
1834 relation between the elements accessed twice by CHREC_A and
1835 CHREC_B. For k >= 0, the following property is verified:
1837 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1840 analyze_siv_subscript_cst_affine (tree chrec_a
,
1842 conflict_function
**overlaps_a
,
1843 conflict_function
**overlaps_b
,
1844 tree
*last_conflicts
)
1846 bool value0
, value1
, value2
;
1847 tree type
, difference
, tmp
;
1849 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1850 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1851 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1852 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1854 /* Special case overlap in the first iteration. */
1855 if (integer_zerop (difference
))
1857 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1858 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1859 *last_conflicts
= integer_one_node
;
1863 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1865 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1866 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1868 dependence_stats
.num_siv_unimplemented
++;
1869 *overlaps_a
= conflict_fn_not_known ();
1870 *overlaps_b
= conflict_fn_not_known ();
1871 *last_conflicts
= chrec_dont_know
;
1876 if (value0
== false)
1878 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1880 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1881 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1883 *overlaps_a
= conflict_fn_not_known ();
1884 *overlaps_b
= conflict_fn_not_known ();
1885 *last_conflicts
= chrec_dont_know
;
1886 dependence_stats
.num_siv_unimplemented
++;
1895 chrec_b = {10, +, 1}
1898 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1900 HOST_WIDE_INT numiter
;
1901 struct loop
*loop
= get_chrec_loop (chrec_b
);
1903 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1904 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1905 fold_build1 (ABS_EXPR
, type
, difference
),
1906 CHREC_RIGHT (chrec_b
));
1907 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1908 *last_conflicts
= integer_one_node
;
1911 /* Perform weak-zero siv test to see if overlap is
1912 outside the loop bounds. */
1913 numiter
= max_stmt_executions_int (loop
);
1916 && compare_tree_int (tmp
, numiter
) > 0)
1918 free_conflict_function (*overlaps_a
);
1919 free_conflict_function (*overlaps_b
);
1920 *overlaps_a
= conflict_fn_no_dependence ();
1921 *overlaps_b
= conflict_fn_no_dependence ();
1922 *last_conflicts
= integer_zero_node
;
1923 dependence_stats
.num_siv_independent
++;
1926 dependence_stats
.num_siv_dependent
++;
1930 /* When the step does not divide the difference, there are
1934 *overlaps_a
= conflict_fn_no_dependence ();
1935 *overlaps_b
= conflict_fn_no_dependence ();
1936 *last_conflicts
= integer_zero_node
;
1937 dependence_stats
.num_siv_independent
++;
1946 chrec_b = {10, +, -1}
1948 In this case, chrec_a will not overlap with chrec_b. */
1949 *overlaps_a
= conflict_fn_no_dependence ();
1950 *overlaps_b
= conflict_fn_no_dependence ();
1951 *last_conflicts
= integer_zero_node
;
1952 dependence_stats
.num_siv_independent
++;
1959 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1961 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1962 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1964 *overlaps_a
= conflict_fn_not_known ();
1965 *overlaps_b
= conflict_fn_not_known ();
1966 *last_conflicts
= chrec_dont_know
;
1967 dependence_stats
.num_siv_unimplemented
++;
1972 if (value2
== false)
1976 chrec_b = {10, +, -1}
1978 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1980 HOST_WIDE_INT numiter
;
1981 struct loop
*loop
= get_chrec_loop (chrec_b
);
1983 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1984 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1985 CHREC_RIGHT (chrec_b
));
1986 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1987 *last_conflicts
= integer_one_node
;
1989 /* Perform weak-zero siv test to see if overlap is
1990 outside the loop bounds. */
1991 numiter
= max_stmt_executions_int (loop
);
1994 && compare_tree_int (tmp
, numiter
) > 0)
1996 free_conflict_function (*overlaps_a
);
1997 free_conflict_function (*overlaps_b
);
1998 *overlaps_a
= conflict_fn_no_dependence ();
1999 *overlaps_b
= conflict_fn_no_dependence ();
2000 *last_conflicts
= integer_zero_node
;
2001 dependence_stats
.num_siv_independent
++;
2004 dependence_stats
.num_siv_dependent
++;
2008 /* When the step does not divide the difference, there
2012 *overlaps_a
= conflict_fn_no_dependence ();
2013 *overlaps_b
= conflict_fn_no_dependence ();
2014 *last_conflicts
= integer_zero_node
;
2015 dependence_stats
.num_siv_independent
++;
2025 In this case, chrec_a will not overlap with chrec_b. */
2026 *overlaps_a
= conflict_fn_no_dependence ();
2027 *overlaps_b
= conflict_fn_no_dependence ();
2028 *last_conflicts
= integer_zero_node
;
2029 dependence_stats
.num_siv_independent
++;
2037 /* Helper recursive function for initializing the matrix A. Returns
2038 the initial value of CHREC. */
2041 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
2045 switch (TREE_CODE (chrec
))
2047 case POLYNOMIAL_CHREC
:
2048 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
2050 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
2051 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
2057 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2058 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
2060 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
2065 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2066 return chrec_convert (chrec_type (chrec
), op
, NULL
);
2071 /* Handle ~X as -1 - X. */
2072 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2073 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
2074 build_int_cst (TREE_TYPE (chrec
), -1), op
);
2086 #define FLOOR_DIV(x,y) ((x) / (y))
2088 /* Solves the special case of the Diophantine equation:
2089 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2091 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2092 number of iterations that loops X and Y run. The overlaps will be
2093 constructed as evolutions in dimension DIM. */
2096 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
2097 affine_fn
*overlaps_a
,
2098 affine_fn
*overlaps_b
,
2099 tree
*last_conflicts
, int dim
)
2101 if (((step_a
> 0 && step_b
> 0)
2102 || (step_a
< 0 && step_b
< 0)))
2104 int step_overlaps_a
, step_overlaps_b
;
2105 int gcd_steps_a_b
, last_conflict
, tau2
;
2107 gcd_steps_a_b
= gcd (step_a
, step_b
);
2108 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2109 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2113 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2114 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2115 last_conflict
= tau2
;
2116 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2119 *last_conflicts
= chrec_dont_know
;
2121 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
2122 build_int_cst (NULL_TREE
,
2124 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
2125 build_int_cst (NULL_TREE
,
2131 *overlaps_a
= affine_fn_cst (integer_zero_node
);
2132 *overlaps_b
= affine_fn_cst (integer_zero_node
);
2133 *last_conflicts
= integer_zero_node
;
2137 /* Solves the special case of a Diophantine equation where CHREC_A is
2138 an affine bivariate function, and CHREC_B is an affine univariate
2139 function. For example,
2141 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2143 has the following overlapping functions:
2145 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2146 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2147 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2149 FORNOW: This is a specialized implementation for a case occurring in
2150 a common benchmark. Implement the general algorithm. */
2153 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2154 conflict_function
**overlaps_a
,
2155 conflict_function
**overlaps_b
,
2156 tree
*last_conflicts
)
2158 bool xz_p
, yz_p
, xyz_p
;
2159 int step_x
, step_y
, step_z
;
2160 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
2161 affine_fn overlaps_a_xz
, overlaps_b_xz
;
2162 affine_fn overlaps_a_yz
, overlaps_b_yz
;
2163 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
2164 affine_fn ova1
, ova2
, ovb
;
2165 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
2167 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2168 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2169 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2171 niter_x
= max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a
)));
2172 niter_y
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
2173 niter_z
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
2175 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2177 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2178 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2180 *overlaps_a
= conflict_fn_not_known ();
2181 *overlaps_b
= conflict_fn_not_known ();
2182 *last_conflicts
= chrec_dont_know
;
2186 niter
= MIN (niter_x
, niter_z
);
2187 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2190 &last_conflicts_xz
, 1);
2191 niter
= MIN (niter_y
, niter_z
);
2192 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2195 &last_conflicts_yz
, 2);
2196 niter
= MIN (niter_x
, niter_z
);
2197 niter
= MIN (niter_y
, niter
);
2198 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2201 &last_conflicts_xyz
, 3);
2203 xz_p
= !integer_zerop (last_conflicts_xz
);
2204 yz_p
= !integer_zerop (last_conflicts_yz
);
2205 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2207 if (xz_p
|| yz_p
|| xyz_p
)
2209 ova1
= affine_fn_cst (integer_zero_node
);
2210 ova2
= affine_fn_cst (integer_zero_node
);
2211 ovb
= affine_fn_cst (integer_zero_node
);
2214 affine_fn t0
= ova1
;
2217 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2218 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2219 affine_fn_free (t0
);
2220 affine_fn_free (t2
);
2221 *last_conflicts
= last_conflicts_xz
;
2225 affine_fn t0
= ova2
;
2228 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2229 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2230 affine_fn_free (t0
);
2231 affine_fn_free (t2
);
2232 *last_conflicts
= last_conflicts_yz
;
2236 affine_fn t0
= ova1
;
2237 affine_fn t2
= ova2
;
2240 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2241 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2242 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2243 affine_fn_free (t0
);
2244 affine_fn_free (t2
);
2245 affine_fn_free (t4
);
2246 *last_conflicts
= last_conflicts_xyz
;
2248 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2249 *overlaps_b
= conflict_fn (1, ovb
);
2253 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2254 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2255 *last_conflicts
= integer_zero_node
;
2258 affine_fn_free (overlaps_a_xz
);
2259 affine_fn_free (overlaps_b_xz
);
2260 affine_fn_free (overlaps_a_yz
);
2261 affine_fn_free (overlaps_b_yz
);
2262 affine_fn_free (overlaps_a_xyz
);
2263 affine_fn_free (overlaps_b_xyz
);
2266 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2269 lambda_vector_copy (lambda_vector vec1
, lambda_vector vec2
,
2272 memcpy (vec2
, vec1
, size
* sizeof (*vec1
));
2275 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2278 lambda_matrix_copy (lambda_matrix mat1
, lambda_matrix mat2
,
2283 for (i
= 0; i
< m
; i
++)
2284 lambda_vector_copy (mat1
[i
], mat2
[i
], n
);
2287 /* Store the N x N identity matrix in MAT. */
2290 lambda_matrix_id (lambda_matrix mat
, int size
)
2294 for (i
= 0; i
< size
; i
++)
2295 for (j
= 0; j
< size
; j
++)
2296 mat
[i
][j
] = (i
== j
) ? 1 : 0;
2299 /* Return the first nonzero element of vector VEC1 between START and N.
2300 We must have START <= N. Returns N if VEC1 is the zero vector. */
2303 lambda_vector_first_nz (lambda_vector vec1
, int n
, int start
)
2306 while (j
< n
&& vec1
[j
] == 0)
2311 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2312 R2 = R2 + CONST1 * R1. */
2315 lambda_matrix_row_add (lambda_matrix mat
, int n
, int r1
, int r2
, int const1
)
2322 for (i
= 0; i
< n
; i
++)
2323 mat
[r2
][i
] += const1
* mat
[r1
][i
];
2326 /* Swap rows R1 and R2 in matrix MAT. */
2329 lambda_matrix_row_exchange (lambda_matrix mat
, int r1
, int r2
)
2338 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2339 and store the result in VEC2. */
2342 lambda_vector_mult_const (lambda_vector vec1
, lambda_vector vec2
,
2343 int size
, int const1
)
2348 lambda_vector_clear (vec2
, size
);
2350 for (i
= 0; i
< size
; i
++)
2351 vec2
[i
] = const1
* vec1
[i
];
2354 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2357 lambda_vector_negate (lambda_vector vec1
, lambda_vector vec2
,
2360 lambda_vector_mult_const (vec1
, vec2
, size
, -1);
2363 /* Negate row R1 of matrix MAT which has N columns. */
2366 lambda_matrix_row_negate (lambda_matrix mat
, int n
, int r1
)
2368 lambda_vector_negate (mat
[r1
], mat
[r1
], n
);
2371 /* Return true if two vectors are equal. */
2374 lambda_vector_equal (lambda_vector vec1
, lambda_vector vec2
, int size
)
2377 for (i
= 0; i
< size
; i
++)
2378 if (vec1
[i
] != vec2
[i
])
2383 /* Given an M x N integer matrix A, this function determines an M x
2384 M unimodular matrix U, and an M x N echelon matrix S such that
2385 "U.A = S". This decomposition is also known as "right Hermite".
2387 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2388 Restructuring Compilers" Utpal Banerjee. */
2391 lambda_matrix_right_hermite (lambda_matrix A
, int m
, int n
,
2392 lambda_matrix S
, lambda_matrix U
)
2396 lambda_matrix_copy (A
, S
, m
, n
);
2397 lambda_matrix_id (U
, m
);
2399 for (j
= 0; j
< n
; j
++)
2401 if (lambda_vector_first_nz (S
[j
], m
, i0
) < m
)
2404 for (i
= m
- 1; i
>= i0
; i
--)
2406 while (S
[i
][j
] != 0)
2408 int sigma
, factor
, a
, b
;
2412 sigma
= (a
* b
< 0) ? -1: 1;
2415 factor
= sigma
* (a
/ b
);
2417 lambda_matrix_row_add (S
, n
, i
, i
-1, -factor
);
2418 lambda_matrix_row_exchange (S
, i
, i
-1);
2420 lambda_matrix_row_add (U
, m
, i
, i
-1, -factor
);
2421 lambda_matrix_row_exchange (U
, i
, i
-1);
2428 /* Determines the overlapping elements due to accesses CHREC_A and
2429 CHREC_B, that are affine functions. This function cannot handle
2430 symbolic evolution functions, ie. when initial conditions are
2431 parameters, because it uses lambda matrices of integers. */
2434 analyze_subscript_affine_affine (tree chrec_a
,
2436 conflict_function
**overlaps_a
,
2437 conflict_function
**overlaps_b
,
2438 tree
*last_conflicts
)
2440 unsigned nb_vars_a
, nb_vars_b
, dim
;
2441 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2442 lambda_matrix A
, U
, S
;
2443 struct obstack scratch_obstack
;
2445 if (eq_evolutions_p (chrec_a
, chrec_b
))
2447 /* The accessed index overlaps for each iteration in the
2449 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2450 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2451 *last_conflicts
= chrec_dont_know
;
2454 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2455 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2457 /* For determining the initial intersection, we have to solve a
2458 Diophantine equation. This is the most time consuming part.
2460 For answering to the question: "Is there a dependence?" we have
2461 to prove that there exists a solution to the Diophantine
2462 equation, and that the solution is in the iteration domain,
2463 i.e. the solution is positive or zero, and that the solution
2464 happens before the upper bound loop.nb_iterations. Otherwise
2465 there is no dependence. This function outputs a description of
2466 the iterations that hold the intersections. */
2468 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2469 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2471 gcc_obstack_init (&scratch_obstack
);
2473 dim
= nb_vars_a
+ nb_vars_b
;
2474 U
= lambda_matrix_new (dim
, dim
, &scratch_obstack
);
2475 A
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2476 S
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2478 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2479 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2480 gamma
= init_b
- init_a
;
2482 /* Don't do all the hard work of solving the Diophantine equation
2483 when we already know the solution: for example,
2486 | gamma = 3 - 3 = 0.
2487 Then the first overlap occurs during the first iterations:
2488 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2492 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2494 HOST_WIDE_INT step_a
, step_b
;
2495 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2498 niter_a
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
2499 niter_b
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
2500 niter
= MIN (niter_a
, niter_b
);
2501 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2502 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2504 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2507 *overlaps_a
= conflict_fn (1, ova
);
2508 *overlaps_b
= conflict_fn (1, ovb
);
2511 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2512 compute_overlap_steps_for_affine_1_2
2513 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2515 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2516 compute_overlap_steps_for_affine_1_2
2517 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2521 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2522 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2523 *overlaps_a
= conflict_fn_not_known ();
2524 *overlaps_b
= conflict_fn_not_known ();
2525 *last_conflicts
= chrec_dont_know
;
2527 goto end_analyze_subs_aa
;
2531 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2536 lambda_matrix_row_negate (U
, dim
, 0);
2538 gcd_alpha_beta
= S
[0][0];
2540 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2541 but that is a quite strange case. Instead of ICEing, answer
2543 if (gcd_alpha_beta
== 0)
2545 *overlaps_a
= conflict_fn_not_known ();
2546 *overlaps_b
= conflict_fn_not_known ();
2547 *last_conflicts
= chrec_dont_know
;
2548 goto end_analyze_subs_aa
;
2551 /* The classic "gcd-test". */
2552 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2554 /* The "gcd-test" has determined that there is no integer
2555 solution, i.e. there is no dependence. */
2556 *overlaps_a
= conflict_fn_no_dependence ();
2557 *overlaps_b
= conflict_fn_no_dependence ();
2558 *last_conflicts
= integer_zero_node
;
2561 /* Both access functions are univariate. This includes SIV and MIV cases. */
2562 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2564 /* Both functions should have the same evolution sign. */
2565 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2566 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2568 /* The solutions are given by:
2570 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2573 For a given integer t. Using the following variables,
2575 | i0 = u11 * gamma / gcd_alpha_beta
2576 | j0 = u12 * gamma / gcd_alpha_beta
2583 | y0 = j0 + j1 * t. */
2584 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2586 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2587 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2591 if ((i1
== 0 && i0
< 0)
2592 || (j1
== 0 && j0
< 0))
2594 /* There is no solution.
2595 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2596 falls in here, but for the moment we don't look at the
2597 upper bound of the iteration domain. */
2598 *overlaps_a
= conflict_fn_no_dependence ();
2599 *overlaps_b
= conflict_fn_no_dependence ();
2600 *last_conflicts
= integer_zero_node
;
2601 goto end_analyze_subs_aa
;
2604 if (i1
> 0 && j1
> 0)
2606 HOST_WIDE_INT niter_a
2607 = max_stmt_executions_int (get_chrec_loop (chrec_a
));
2608 HOST_WIDE_INT niter_b
2609 = max_stmt_executions_int (get_chrec_loop (chrec_b
));
2610 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2612 /* (X0, Y0) is a solution of the Diophantine equation:
2613 "chrec_a (X0) = chrec_b (Y0)". */
2614 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2616 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2617 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2619 /* (X1, Y1) is the smallest positive solution of the eq
2620 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2621 first conflict occurs. */
2622 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2623 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2624 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2628 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2629 FLOOR_DIV (niter
- j0
, j1
));
2630 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2632 /* If the overlap occurs outside of the bounds of the
2633 loop, there is no dependence. */
2634 if (x1
>= niter
|| y1
>= niter
)
2636 *overlaps_a
= conflict_fn_no_dependence ();
2637 *overlaps_b
= conflict_fn_no_dependence ();
2638 *last_conflicts
= integer_zero_node
;
2639 goto end_analyze_subs_aa
;
2642 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2645 *last_conflicts
= chrec_dont_know
;
2649 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2651 build_int_cst (NULL_TREE
, i1
)));
2654 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2656 build_int_cst (NULL_TREE
, j1
)));
2660 /* FIXME: For the moment, the upper bound of the
2661 iteration domain for i and j is not checked. */
2662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2663 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2664 *overlaps_a
= conflict_fn_not_known ();
2665 *overlaps_b
= conflict_fn_not_known ();
2666 *last_conflicts
= chrec_dont_know
;
2671 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2672 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2673 *overlaps_a
= conflict_fn_not_known ();
2674 *overlaps_b
= conflict_fn_not_known ();
2675 *last_conflicts
= chrec_dont_know
;
2680 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2681 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2682 *overlaps_a
= conflict_fn_not_known ();
2683 *overlaps_b
= conflict_fn_not_known ();
2684 *last_conflicts
= chrec_dont_know
;
2687 end_analyze_subs_aa
:
2688 obstack_free (&scratch_obstack
, NULL
);
2689 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2691 fprintf (dump_file
, " (overlaps_a = ");
2692 dump_conflict_function (dump_file
, *overlaps_a
);
2693 fprintf (dump_file
, ")\n (overlaps_b = ");
2694 dump_conflict_function (dump_file
, *overlaps_b
);
2695 fprintf (dump_file
, "))\n");
2699 /* Returns true when analyze_subscript_affine_affine can be used for
2700 determining the dependence relation between chrec_a and chrec_b,
2701 that contain symbols. This function modifies chrec_a and chrec_b
2702 such that the analysis result is the same, and such that they don't
2703 contain symbols, and then can safely be passed to the analyzer.
2705 Example: The analysis of the following tuples of evolutions produce
2706 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2709 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2710 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2714 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2716 tree diff
, type
, left_a
, left_b
, right_b
;
2718 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2719 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2720 /* FIXME: For the moment not handled. Might be refined later. */
2723 type
= chrec_type (*chrec_a
);
2724 left_a
= CHREC_LEFT (*chrec_a
);
2725 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2726 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2728 if (!evolution_function_is_constant_p (diff
))
2731 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2732 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2734 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2735 diff
, CHREC_RIGHT (*chrec_a
));
2736 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2737 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2738 build_int_cst (type
, 0),
2743 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2744 *OVERLAPS_B are initialized to the functions that describe the
2745 relation between the elements accessed twice by CHREC_A and
2746 CHREC_B. For k >= 0, the following property is verified:
2748 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2751 analyze_siv_subscript (tree chrec_a
,
2753 conflict_function
**overlaps_a
,
2754 conflict_function
**overlaps_b
,
2755 tree
*last_conflicts
,
2758 dependence_stats
.num_siv
++;
2760 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2761 fprintf (dump_file
, "(analyze_siv_subscript \n");
2763 if (evolution_function_is_constant_p (chrec_a
)
2764 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2765 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2766 overlaps_a
, overlaps_b
, last_conflicts
);
2768 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2769 && evolution_function_is_constant_p (chrec_b
))
2770 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2771 overlaps_b
, overlaps_a
, last_conflicts
);
2773 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2774 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2776 if (!chrec_contains_symbols (chrec_a
)
2777 && !chrec_contains_symbols (chrec_b
))
2779 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2780 overlaps_a
, overlaps_b
,
2783 if (CF_NOT_KNOWN_P (*overlaps_a
)
2784 || CF_NOT_KNOWN_P (*overlaps_b
))
2785 dependence_stats
.num_siv_unimplemented
++;
2786 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2787 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2788 dependence_stats
.num_siv_independent
++;
2790 dependence_stats
.num_siv_dependent
++;
2792 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2795 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2796 overlaps_a
, overlaps_b
,
2799 if (CF_NOT_KNOWN_P (*overlaps_a
)
2800 || CF_NOT_KNOWN_P (*overlaps_b
))
2801 dependence_stats
.num_siv_unimplemented
++;
2802 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2803 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2804 dependence_stats
.num_siv_independent
++;
2806 dependence_stats
.num_siv_dependent
++;
2809 goto siv_subscript_dontknow
;
2814 siv_subscript_dontknow
:;
2815 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2816 fprintf (dump_file
, " siv test failed: unimplemented");
2817 *overlaps_a
= conflict_fn_not_known ();
2818 *overlaps_b
= conflict_fn_not_known ();
2819 *last_conflicts
= chrec_dont_know
;
2820 dependence_stats
.num_siv_unimplemented
++;
2823 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2824 fprintf (dump_file
, ")\n");
2827 /* Returns false if we can prove that the greatest common divisor of the steps
2828 of CHREC does not divide CST, false otherwise. */
2831 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2833 HOST_WIDE_INT cd
= 0, val
;
2836 if (!host_integerp (cst
, 0))
2838 val
= tree_low_cst (cst
, 0);
2840 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2842 step
= CHREC_RIGHT (chrec
);
2843 if (!host_integerp (step
, 0))
2845 cd
= gcd (cd
, tree_low_cst (step
, 0));
2846 chrec
= CHREC_LEFT (chrec
);
2849 return val
% cd
== 0;
2852 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2853 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2854 functions that describe the relation between the elements accessed
2855 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2858 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2861 analyze_miv_subscript (tree chrec_a
,
2863 conflict_function
**overlaps_a
,
2864 conflict_function
**overlaps_b
,
2865 tree
*last_conflicts
,
2866 struct loop
*loop_nest
)
2868 tree type
, difference
;
2870 dependence_stats
.num_miv
++;
2871 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2872 fprintf (dump_file
, "(analyze_miv_subscript \n");
2874 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2875 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2876 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2877 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2879 if (eq_evolutions_p (chrec_a
, chrec_b
))
2881 /* Access functions are the same: all the elements are accessed
2882 in the same order. */
2883 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2884 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2885 *last_conflicts
= max_stmt_executions_tree (get_chrec_loop (chrec_a
));
2886 dependence_stats
.num_miv_dependent
++;
2889 else if (evolution_function_is_constant_p (difference
)
2890 /* For the moment, the following is verified:
2891 evolution_function_is_affine_multivariate_p (chrec_a,
2893 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2895 /* testsuite/.../ssa-chrec-33.c
2896 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2898 The difference is 1, and all the evolution steps are multiples
2899 of 2, consequently there are no overlapping elements. */
2900 *overlaps_a
= conflict_fn_no_dependence ();
2901 *overlaps_b
= conflict_fn_no_dependence ();
2902 *last_conflicts
= integer_zero_node
;
2903 dependence_stats
.num_miv_independent
++;
2906 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2907 && !chrec_contains_symbols (chrec_a
)
2908 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2909 && !chrec_contains_symbols (chrec_b
))
2911 /* testsuite/.../ssa-chrec-35.c
2912 {0, +, 1}_2 vs. {0, +, 1}_3
2913 the overlapping elements are respectively located at iterations:
2914 {0, +, 1}_x and {0, +, 1}_x,
2915 in other words, we have the equality:
2916 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2919 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2920 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2922 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2923 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2925 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2926 overlaps_a
, overlaps_b
, last_conflicts
);
2928 if (CF_NOT_KNOWN_P (*overlaps_a
)
2929 || CF_NOT_KNOWN_P (*overlaps_b
))
2930 dependence_stats
.num_miv_unimplemented
++;
2931 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2932 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2933 dependence_stats
.num_miv_independent
++;
2935 dependence_stats
.num_miv_dependent
++;
2940 /* When the analysis is too difficult, answer "don't know". */
2941 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2942 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2944 *overlaps_a
= conflict_fn_not_known ();
2945 *overlaps_b
= conflict_fn_not_known ();
2946 *last_conflicts
= chrec_dont_know
;
2947 dependence_stats
.num_miv_unimplemented
++;
2950 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2951 fprintf (dump_file
, ")\n");
2954 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2955 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2956 OVERLAP_ITERATIONS_B are initialized with two functions that
2957 describe the iterations that contain conflicting elements.
2959 Remark: For an integer k >= 0, the following equality is true:
2961 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2965 analyze_overlapping_iterations (tree chrec_a
,
2967 conflict_function
**overlap_iterations_a
,
2968 conflict_function
**overlap_iterations_b
,
2969 tree
*last_conflicts
, struct loop
*loop_nest
)
2971 unsigned int lnn
= loop_nest
->num
;
2973 dependence_stats
.num_subscript_tests
++;
2975 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2977 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2978 fprintf (dump_file
, " (chrec_a = ");
2979 print_generic_expr (dump_file
, chrec_a
, 0);
2980 fprintf (dump_file
, ")\n (chrec_b = ");
2981 print_generic_expr (dump_file
, chrec_b
, 0);
2982 fprintf (dump_file
, ")\n");
2985 if (chrec_a
== NULL_TREE
2986 || chrec_b
== NULL_TREE
2987 || chrec_contains_undetermined (chrec_a
)
2988 || chrec_contains_undetermined (chrec_b
))
2990 dependence_stats
.num_subscript_undetermined
++;
2992 *overlap_iterations_a
= conflict_fn_not_known ();
2993 *overlap_iterations_b
= conflict_fn_not_known ();
2996 /* If they are the same chrec, and are affine, they overlap
2997 on every iteration. */
2998 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2999 && (evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
3000 || operand_equal_p (chrec_a
, chrec_b
, 0)))
3002 dependence_stats
.num_same_subscript_function
++;
3003 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3004 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3005 *last_conflicts
= chrec_dont_know
;
3008 /* If they aren't the same, and aren't affine, we can't do anything
3010 else if ((chrec_contains_symbols (chrec_a
)
3011 || chrec_contains_symbols (chrec_b
))
3012 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
3013 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
3015 dependence_stats
.num_subscript_undetermined
++;
3016 *overlap_iterations_a
= conflict_fn_not_known ();
3017 *overlap_iterations_b
= conflict_fn_not_known ();
3020 else if (ziv_subscript_p (chrec_a
, chrec_b
))
3021 analyze_ziv_subscript (chrec_a
, chrec_b
,
3022 overlap_iterations_a
, overlap_iterations_b
,
3025 else if (siv_subscript_p (chrec_a
, chrec_b
))
3026 analyze_siv_subscript (chrec_a
, chrec_b
,
3027 overlap_iterations_a
, overlap_iterations_b
,
3028 last_conflicts
, lnn
);
3031 analyze_miv_subscript (chrec_a
, chrec_b
,
3032 overlap_iterations_a
, overlap_iterations_b
,
3033 last_conflicts
, loop_nest
);
3035 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3037 fprintf (dump_file
, " (overlap_iterations_a = ");
3038 dump_conflict_function (dump_file
, *overlap_iterations_a
);
3039 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
3040 dump_conflict_function (dump_file
, *overlap_iterations_b
);
3041 fprintf (dump_file
, "))\n");
3045 /* Helper function for uniquely inserting distance vectors. */
3048 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
3053 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, v
)
3054 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
3057 DDR_DIST_VECTS (ddr
).safe_push (dist_v
);
3060 /* Helper function for uniquely inserting direction vectors. */
3063 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
3068 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), i
, v
)
3069 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
3072 DDR_DIR_VECTS (ddr
).safe_push (dir_v
);
3075 /* Add a distance of 1 on all the loops outer than INDEX. If we
3076 haven't yet determined a distance for this outer loop, push a new
3077 distance vector composed of the previous distance, and a distance
3078 of 1 for this outer loop. Example:
3086 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3087 save (0, 1), then we have to save (1, 0). */
3090 add_outer_distances (struct data_dependence_relation
*ddr
,
3091 lambda_vector dist_v
, int index
)
3093 /* For each outer loop where init_v is not set, the accesses are
3094 in dependence of distance 1 in the loop. */
3095 while (--index
>= 0)
3097 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3098 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3100 save_dist_v (ddr
, save_v
);
3104 /* Return false when fail to represent the data dependence as a
3105 distance vector. INIT_B is set to true when a component has been
3106 added to the distance vector DIST_V. INDEX_CARRY is then set to
3107 the index in DIST_V that carries the dependence. */
3110 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
3111 struct data_reference
*ddr_a
,
3112 struct data_reference
*ddr_b
,
3113 lambda_vector dist_v
, bool *init_b
,
3117 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3119 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3121 tree access_fn_a
, access_fn_b
;
3122 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
3124 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3126 non_affine_dependence_relation (ddr
);
3130 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
3131 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
3133 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
3134 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
3137 int var_a
= CHREC_VARIABLE (access_fn_a
);
3138 int var_b
= CHREC_VARIABLE (access_fn_b
);
3141 || chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3143 non_affine_dependence_relation (ddr
);
3147 dist
= int_cst_value (SUB_DISTANCE (subscript
));
3148 index
= index_in_loop_nest (var_a
, DDR_LOOP_NEST (ddr
));
3149 *index_carry
= MIN (index
, *index_carry
);
3151 /* This is the subscript coupling test. If we have already
3152 recorded a distance for this loop (a distance coming from
3153 another subscript), it should be the same. For example,
3154 in the following code, there is no dependence:
3161 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
3163 finalize_ddr_dependent (ddr
, chrec_known
);
3167 dist_v
[index
] = dist
;
3171 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
3173 /* This can be for example an affine vs. constant dependence
3174 (T[i] vs. T[3]) that is not an affine dependence and is
3175 not representable as a distance vector. */
3176 non_affine_dependence_relation (ddr
);
3184 /* Return true when the DDR contains only constant access functions. */
3187 constant_access_functions (const struct data_dependence_relation
*ddr
)
3191 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3192 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
3193 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
3199 /* Helper function for the case where DDR_A and DDR_B are the same
3200 multivariate access function with a constant step. For an example
3204 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
3207 tree c_1
= CHREC_LEFT (c_2
);
3208 tree c_0
= CHREC_LEFT (c_1
);
3209 lambda_vector dist_v
;
3212 /* Polynomials with more than 2 variables are not handled yet. When
3213 the evolution steps are parameters, it is not possible to
3214 represent the dependence using classical distance vectors. */
3215 if (TREE_CODE (c_0
) != INTEGER_CST
3216 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
3217 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
3219 DDR_AFFINE_P (ddr
) = false;
3223 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
3224 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
3226 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3227 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3228 v1
= int_cst_value (CHREC_RIGHT (c_1
));
3229 v2
= int_cst_value (CHREC_RIGHT (c_2
));
3242 save_dist_v (ddr
, dist_v
);
3244 add_outer_distances (ddr
, dist_v
, x_1
);
3247 /* Helper function for the case where DDR_A and DDR_B are the same
3248 access functions. */
3251 add_other_self_distances (struct data_dependence_relation
*ddr
)
3253 lambda_vector dist_v
;
3255 int index_carry
= DDR_NB_LOOPS (ddr
);
3257 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3259 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3261 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3263 if (!evolution_function_is_univariate_p (access_fun
))
3265 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3267 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3271 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
3273 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
3274 add_multivariate_self_dist (ddr
, access_fun
);
3276 /* The evolution step is not constant: it varies in
3277 the outer loop, so this cannot be represented by a
3278 distance vector. For example in pr34635.c the
3279 evolution is {0, +, {0, +, 4}_1}_2. */
3280 DDR_AFFINE_P (ddr
) = false;
3285 index_carry
= MIN (index_carry
,
3286 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3287 DDR_LOOP_NEST (ddr
)));
3291 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3292 add_outer_distances (ddr
, dist_v
, index_carry
);
3296 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
3298 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3300 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
3301 save_dist_v (ddr
, dist_v
);
3304 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3305 is the case for example when access functions are the same and
3306 equal to a constant, as in:
3313 in which case the distance vectors are (0) and (1). */
3316 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
3320 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3322 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
3323 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
3324 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
3326 for (j
= 0; j
< ca
->n
; j
++)
3327 if (affine_function_zero_p (ca
->fns
[j
]))
3329 insert_innermost_unit_dist_vector (ddr
);
3333 for (j
= 0; j
< cb
->n
; j
++)
3334 if (affine_function_zero_p (cb
->fns
[j
]))
3336 insert_innermost_unit_dist_vector (ddr
);
3342 /* Compute the classic per loop distance vector. DDR is the data
3343 dependence relation to build a vector from. Return false when fail
3344 to represent the data dependence as a distance vector. */
3347 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3348 struct loop
*loop_nest
)
3350 bool init_b
= false;
3351 int index_carry
= DDR_NB_LOOPS (ddr
);
3352 lambda_vector dist_v
;
3354 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3357 if (same_access_functions (ddr
))
3359 /* Save the 0 vector. */
3360 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3361 save_dist_v (ddr
, dist_v
);
3363 if (constant_access_functions (ddr
))
3364 add_distance_for_zero_overlaps (ddr
);
3366 if (DDR_NB_LOOPS (ddr
) > 1)
3367 add_other_self_distances (ddr
);
3372 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3373 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3374 dist_v
, &init_b
, &index_carry
))
3377 /* Save the distance vector if we initialized one. */
3380 /* Verify a basic constraint: classic distance vectors should
3381 always be lexicographically positive.
3383 Data references are collected in the order of execution of
3384 the program, thus for the following loop
3386 | for (i = 1; i < 100; i++)
3387 | for (j = 1; j < 100; j++)
3389 | t = T[j+1][i-1]; // A
3390 | T[j][i] = t + 2; // B
3393 references are collected following the direction of the wind:
3394 A then B. The data dependence tests are performed also
3395 following this order, such that we're looking at the distance
3396 separating the elements accessed by A from the elements later
3397 accessed by B. But in this example, the distance returned by
3398 test_dep (A, B) is lexicographically negative (-1, 1), that
3399 means that the access A occurs later than B with respect to
3400 the outer loop, ie. we're actually looking upwind. In this
3401 case we solve test_dep (B, A) looking downwind to the
3402 lexicographically positive solution, that returns the
3403 distance vector (1, -1). */
3404 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3406 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3407 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3410 compute_subscript_distance (ddr
);
3411 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3412 save_v
, &init_b
, &index_carry
))
3414 save_dist_v (ddr
, save_v
);
3415 DDR_REVERSED_P (ddr
) = true;
3417 /* In this case there is a dependence forward for all the
3420 | for (k = 1; k < 100; k++)
3421 | for (i = 1; i < 100; i++)
3422 | for (j = 1; j < 100; j++)
3424 | t = T[j+1][i-1]; // A
3425 | T[j][i] = t + 2; // B
3433 if (DDR_NB_LOOPS (ddr
) > 1)
3435 add_outer_distances (ddr
, save_v
, index_carry
);
3436 add_outer_distances (ddr
, dist_v
, index_carry
);
3441 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3442 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3444 if (DDR_NB_LOOPS (ddr
) > 1)
3446 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3448 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3449 DDR_A (ddr
), loop_nest
))
3451 compute_subscript_distance (ddr
);
3452 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3453 opposite_v
, &init_b
,
3457 save_dist_v (ddr
, save_v
);
3458 add_outer_distances (ddr
, dist_v
, index_carry
);
3459 add_outer_distances (ddr
, opposite_v
, index_carry
);
3462 save_dist_v (ddr
, save_v
);
3467 /* There is a distance of 1 on all the outer loops: Example:
3468 there is a dependence of distance 1 on loop_1 for the array A.
3474 add_outer_distances (ddr
, dist_v
,
3475 lambda_vector_first_nz (dist_v
,
3476 DDR_NB_LOOPS (ddr
), 0));
3479 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3483 fprintf (dump_file
, "(build_classic_dist_vector\n");
3484 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3486 fprintf (dump_file
, " dist_vector = (");
3487 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3488 DDR_NB_LOOPS (ddr
));
3489 fprintf (dump_file
, " )\n");
3491 fprintf (dump_file
, ")\n");
3497 /* Return the direction for a given distance.
3498 FIXME: Computing dir this way is suboptimal, since dir can catch
3499 cases that dist is unable to represent. */
3501 static inline enum data_dependence_direction
3502 dir_from_dist (int dist
)
3505 return dir_positive
;
3507 return dir_negative
;
3512 /* Compute the classic per loop direction vector. DDR is the data
3513 dependence relation to build a vector from. */
3516 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3519 lambda_vector dist_v
;
3521 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
3523 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3525 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3526 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3528 save_dir_v (ddr
, dir_v
);
3532 /* Helper function. Returns true when there is a dependence between
3533 data references DRA and DRB. */
3536 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3537 struct data_reference
*dra
,
3538 struct data_reference
*drb
,
3539 struct loop
*loop_nest
)
3542 tree last_conflicts
;
3543 struct subscript
*subscript
;
3544 tree res
= NULL_TREE
;
3546 for (i
= 0; DDR_SUBSCRIPTS (ddr
).iterate (i
, &subscript
); i
++)
3548 conflict_function
*overlaps_a
, *overlaps_b
;
3550 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3551 DR_ACCESS_FN (drb
, i
),
3552 &overlaps_a
, &overlaps_b
,
3553 &last_conflicts
, loop_nest
);
3555 if (SUB_CONFLICTS_IN_A (subscript
))
3556 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3557 if (SUB_CONFLICTS_IN_B (subscript
))
3558 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3560 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3561 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3562 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3564 /* If there is any undetermined conflict function we have to
3565 give a conservative answer in case we cannot prove that
3566 no dependence exists when analyzing another subscript. */
3567 if (CF_NOT_KNOWN_P (overlaps_a
)
3568 || CF_NOT_KNOWN_P (overlaps_b
))
3570 res
= chrec_dont_know
;
3574 /* When there is a subscript with no dependence we can stop. */
3575 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3576 || CF_NO_DEPENDENCE_P (overlaps_b
))
3583 if (res
== NULL_TREE
)
3586 if (res
== chrec_known
)
3587 dependence_stats
.num_dependence_independent
++;
3589 dependence_stats
.num_dependence_undetermined
++;
3590 finalize_ddr_dependent (ddr
, res
);
3594 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3597 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3598 struct loop
*loop_nest
)
3600 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3601 dependence_stats
.num_dependence_dependent
++;
3603 compute_subscript_distance (ddr
);
3604 if (build_classic_dist_vector (ddr
, loop_nest
))
3605 build_classic_dir_vector (ddr
);
3608 /* Returns true when all the access functions of A are affine or
3609 constant with respect to LOOP_NEST. */
3612 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3613 const struct loop
*loop_nest
)
3616 vec
<tree
> fns
= DR_ACCESS_FNS (a
);
3619 FOR_EACH_VEC_ELT (fns
, i
, t
)
3620 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3621 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3627 /* Initializes an equation for an OMEGA problem using the information
3628 contained in the ACCESS_FUN. Returns true when the operation
3631 PB is the omega constraint system.
3632 EQ is the number of the equation to be initialized.
3633 OFFSET is used for shifting the variables names in the constraints:
3634 a constrain is composed of 2 * the number of variables surrounding
3635 dependence accesses. OFFSET is set either to 0 for the first n variables,
3636 then it is set to n.
3637 ACCESS_FUN is expected to be an affine chrec. */
3640 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3641 unsigned int offset
, tree access_fun
,
3642 struct data_dependence_relation
*ddr
)
3644 switch (TREE_CODE (access_fun
))
3646 case POLYNOMIAL_CHREC
:
3648 tree left
= CHREC_LEFT (access_fun
);
3649 tree right
= CHREC_RIGHT (access_fun
);
3650 int var
= CHREC_VARIABLE (access_fun
);
3653 if (TREE_CODE (right
) != INTEGER_CST
)
3656 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3657 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3659 /* Compute the innermost loop index. */
3660 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3663 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3664 += int_cst_value (right
);
3666 switch (TREE_CODE (left
))
3668 case POLYNOMIAL_CHREC
:
3669 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3672 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3681 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3689 /* As explained in the comments preceding init_omega_for_ddr, we have
3690 to set up a system for each loop level, setting outer loops
3691 variation to zero, and current loop variation to positive or zero.
3692 Save each lexico positive distance vector. */
3695 omega_extract_distance_vectors (omega_pb pb
,
3696 struct data_dependence_relation
*ddr
)
3700 struct loop
*loopi
, *loopj
;
3701 enum omega_result res
;
3703 /* Set a new problem for each loop in the nest. The basis is the
3704 problem that we have initialized until now. On top of this we
3705 add new constraints. */
3706 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3707 && DDR_LOOP_NEST (ddr
).iterate (i
, &loopi
); i
++)
3710 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3711 DDR_NB_LOOPS (ddr
));
3713 omega_copy_problem (copy
, pb
);
3715 /* For all the outer loops "loop_j", add "dj = 0". */
3716 for (j
= 0; j
< i
&& DDR_LOOP_NEST (ddr
).iterate (j
, &loopj
); j
++)
3718 eq
= omega_add_zero_eq (copy
, omega_black
);
3719 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3722 /* For "loop_i", add "0 <= di". */
3723 geq
= omega_add_zero_geq (copy
, omega_black
);
3724 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3726 /* Reduce the constraint system, and test that the current
3727 problem is feasible. */
3728 res
= omega_simplify_problem (copy
);
3729 if (res
== omega_false
3730 || res
== omega_unknown
3731 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3734 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3735 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3737 dist
= copy
->subs
[eq
].coef
[0];
3743 /* Reinitialize problem... */
3744 omega_copy_problem (copy
, pb
);
3745 for (j
= 0; j
< i
&& DDR_LOOP_NEST (ddr
).iterate (j
, &loopj
); j
++)
3747 eq
= omega_add_zero_eq (copy
, omega_black
);
3748 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3751 /* ..., but this time "di = 1". */
3752 eq
= omega_add_zero_eq (copy
, omega_black
);
3753 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3754 copy
->eqs
[eq
].coef
[0] = -1;
3756 res
= omega_simplify_problem (copy
);
3757 if (res
== omega_false
3758 || res
== omega_unknown
3759 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3762 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3763 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3765 dist
= copy
->subs
[eq
].coef
[0];
3771 /* Save the lexicographically positive distance vector. */
3774 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3775 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3779 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3780 if (copy
->subs
[eq
].key
> 0)
3782 dist
= copy
->subs
[eq
].coef
[0];
3783 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3786 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3787 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3789 save_dist_v (ddr
, dist_v
);
3790 save_dir_v (ddr
, dir_v
);
3794 omega_free_problem (copy
);
3798 /* This is called for each subscript of a tuple of data references:
3799 insert an equality for representing the conflicts. */
3802 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3803 struct data_dependence_relation
*ddr
,
3804 omega_pb pb
, bool *maybe_dependent
)
3807 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3808 TREE_TYPE (access_fun_b
));
3809 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3810 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3811 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3814 /* When the fun_a - fun_b is not constant, the dependence is not
3815 captured by the classic distance vector representation. */
3816 if (TREE_CODE (difference
) != INTEGER_CST
)
3820 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3822 /* There is no dependence. */
3823 *maybe_dependent
= false;
3827 minus_one
= build_int_cst (type
, -1);
3828 fun_b
= chrec_fold_multiply (type
, fun_b
, minus_one
);
3830 eq
= omega_add_zero_eq (pb
, omega_black
);
3831 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3832 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3833 /* There is probably a dependence, but the system of
3834 constraints cannot be built: answer "don't know". */
3838 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3839 && !int_divides_p (lambda_vector_gcd
3840 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3841 2 * DDR_NB_LOOPS (ddr
)),
3842 pb
->eqs
[eq
].coef
[0]))
3844 /* There is no dependence. */
3845 *maybe_dependent
= false;
3852 /* Helper function, same as init_omega_for_ddr but specialized for
3853 data references A and B. */
3856 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3857 struct data_dependence_relation
*ddr
,
3858 omega_pb pb
, bool *maybe_dependent
)
3863 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3865 /* Insert an equality per subscript. */
3866 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3868 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3869 ddr
, pb
, maybe_dependent
))
3871 else if (*maybe_dependent
== false)
3873 /* There is no dependence. */
3874 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3879 /* Insert inequalities: constraints corresponding to the iteration
3880 domain, i.e. the loops surrounding the references "loop_x" and
3881 the distance variables "dx". The layout of the OMEGA
3882 representation is as follows:
3883 - coef[0] is the constant
3884 - coef[1..nb_loops] are the protected variables that will not be
3885 removed by the solver: the "dx"
3886 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3888 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3889 && DDR_LOOP_NEST (ddr
).iterate (i
, &loopi
); i
++)
3891 HOST_WIDE_INT nbi
= max_stmt_executions_int (loopi
);
3894 ineq
= omega_add_zero_geq (pb
, omega_black
);
3895 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3897 /* 0 <= loop_x + dx */
3898 ineq
= omega_add_zero_geq (pb
, omega_black
);
3899 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3900 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3904 /* loop_x <= nb_iters */
3905 ineq
= omega_add_zero_geq (pb
, omega_black
);
3906 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3907 pb
->geqs
[ineq
].coef
[0] = nbi
;
3909 /* loop_x + dx <= nb_iters */
3910 ineq
= omega_add_zero_geq (pb
, omega_black
);
3911 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3912 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3913 pb
->geqs
[ineq
].coef
[0] = nbi
;
3915 /* A step "dx" bigger than nb_iters is not feasible, so
3916 add "0 <= nb_iters + dx", */
3917 ineq
= omega_add_zero_geq (pb
, omega_black
);
3918 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3919 pb
->geqs
[ineq
].coef
[0] = nbi
;
3920 /* and "dx <= nb_iters". */
3921 ineq
= omega_add_zero_geq (pb
, omega_black
);
3922 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3923 pb
->geqs
[ineq
].coef
[0] = nbi
;
3927 omega_extract_distance_vectors (pb
, ddr
);
3932 /* Sets up the Omega dependence problem for the data dependence
3933 relation DDR. Returns false when the constraint system cannot be
3934 built, ie. when the test answers "don't know". Returns true
3935 otherwise, and when independence has been proved (using one of the
3936 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3937 set MAYBE_DEPENDENT to true.
3939 Example: for setting up the dependence system corresponding to the
3940 conflicting accesses
3945 | ... A[2*j, 2*(i + j)]
3949 the following constraints come from the iteration domain:
3956 where di, dj are the distance variables. The constraints
3957 representing the conflicting elements are:
3960 i + 1 = 2 * (i + di + j + dj)
3962 For asking that the resulting distance vector (di, dj) be
3963 lexicographically positive, we insert the constraint "di >= 0". If
3964 "di = 0" in the solution, we fix that component to zero, and we
3965 look at the inner loops: we set a new problem where all the outer
3966 loop distances are zero, and fix this inner component to be
3967 positive. When one of the components is positive, we save that
3968 distance, and set a new problem where the distance on this loop is
3969 zero, searching for other distances in the inner loops. Here is
3970 the classic example that illustrates that we have to set for each
3971 inner loop a new problem:
3979 we have to save two distances (1, 0) and (0, 1).
3981 Given two array references, refA and refB, we have to set the
3982 dependence problem twice, refA vs. refB and refB vs. refA, and we
3983 cannot do a single test, as refB might occur before refA in the
3984 inner loops, and the contrary when considering outer loops: ex.
3989 | T[{1,+,1}_2][{1,+,1}_1] // refA
3990 | T[{2,+,1}_2][{0,+,1}_1] // refB
3995 refB touches the elements in T before refA, and thus for the same
3996 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3997 but for successive loop_0 iterations, we have (1, -1, 1)
3999 The Omega solver expects the distance variables ("di" in the
4000 previous example) to come first in the constraint system (as
4001 variables to be protected, or "safe" variables), the constraint
4002 system is built using the following layout:
4004 "cst | distance vars | index vars".
4008 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
4009 bool *maybe_dependent
)
4014 *maybe_dependent
= true;
4016 if (same_access_functions (ddr
))
4019 lambda_vector dir_v
;
4021 /* Save the 0 vector. */
4022 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4023 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4024 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
4025 dir_v
[j
] = dir_equal
;
4026 save_dir_v (ddr
, dir_v
);
4028 /* Save the dependences carried by outer loops. */
4029 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4030 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
4032 omega_free_problem (pb
);
4036 /* Omega expects the protected variables (those that have to be kept
4037 after elimination) to appear first in the constraint system.
4038 These variables are the distance variables. In the following
4039 initialization we declare NB_LOOPS safe variables, and the total
4040 number of variables for the constraint system is 2*NB_LOOPS. */
4041 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4042 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
4044 omega_free_problem (pb
);
4046 /* Stop computation if not decidable, or no dependence. */
4047 if (res
== false || *maybe_dependent
== false)
4050 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4051 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
4053 omega_free_problem (pb
);
4058 /* Return true when DDR contains the same information as that stored
4059 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4062 ddr_consistent_p (FILE *file
,
4063 struct data_dependence_relation
*ddr
,
4064 vec
<lambda_vector
> dist_vects
,
4065 vec
<lambda_vector
> dir_vects
)
4069 /* If dump_file is set, output there. */
4070 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4073 if (dist_vects
.length () != DDR_NUM_DIST_VECTS (ddr
))
4075 lambda_vector b_dist_v
;
4076 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4077 dist_vects
.length (),
4078 DDR_NUM_DIST_VECTS (ddr
));
4080 fprintf (file
, "Banerjee dist vectors:\n");
4081 FOR_EACH_VEC_ELT (dist_vects
, i
, b_dist_v
)
4082 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
4084 fprintf (file
, "Omega dist vectors:\n");
4085 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4086 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
4088 fprintf (file
, "data dependence relation:\n");
4089 dump_data_dependence_relation (file
, ddr
);
4091 fprintf (file
, ")\n");
4095 if (dir_vects
.length () != DDR_NUM_DIR_VECTS (ddr
))
4097 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4098 dir_vects
.length (),
4099 DDR_NUM_DIR_VECTS (ddr
));
4103 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4105 lambda_vector a_dist_v
;
4106 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
4108 /* Distance vectors are not ordered in the same way in the DDR
4109 and in the DIST_VECTS: search for a matching vector. */
4110 FOR_EACH_VEC_ELT (dist_vects
, j
, a_dist_v
)
4111 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
4114 if (j
== dist_vects
.length ())
4116 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
4117 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
4118 fprintf (file
, "not found in Omega dist vectors:\n");
4119 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4120 fprintf (file
, "data dependence relation:\n");
4121 dump_data_dependence_relation (file
, ddr
);
4122 fprintf (file
, ")\n");
4126 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
4128 lambda_vector a_dir_v
;
4129 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
4131 /* Direction vectors are not ordered in the same way in the DDR
4132 and in the DIR_VECTS: search for a matching vector. */
4133 FOR_EACH_VEC_ELT (dir_vects
, j
, a_dir_v
)
4134 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
4137 if (j
== dist_vects
.length ())
4139 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
4140 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
4141 fprintf (file
, "not found in Omega dir vectors:\n");
4142 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4143 fprintf (file
, "data dependence relation:\n");
4144 dump_data_dependence_relation (file
, ddr
);
4145 fprintf (file
, ")\n");
4152 /* This computes the affine dependence relation between A and B with
4153 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4154 independence between two accesses, while CHREC_DONT_KNOW is used
4155 for representing the unknown relation.
4157 Note that it is possible to stop the computation of the dependence
4158 relation the first time we detect a CHREC_KNOWN element for a given
4162 compute_affine_dependence (struct data_dependence_relation
*ddr
,
4163 struct loop
*loop_nest
)
4165 struct data_reference
*dra
= DDR_A (ddr
);
4166 struct data_reference
*drb
= DDR_B (ddr
);
4168 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4170 fprintf (dump_file
, "(compute_affine_dependence\n");
4171 fprintf (dump_file
, " stmt_a: ");
4172 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, TDF_SLIM
);
4173 fprintf (dump_file
, " stmt_b: ");
4174 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, TDF_SLIM
);
4177 /* Analyze only when the dependence relation is not yet known. */
4178 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4180 dependence_stats
.num_dependence_tests
++;
4182 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
4183 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
4185 subscript_dependence_tester (ddr
, loop_nest
);
4187 if (flag_check_data_deps
)
4189 /* Dump the dependences from the first algorithm. */
4190 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4192 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
4193 dump_data_dependence_relation (dump_file
, ddr
);
4196 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4198 bool maybe_dependent
;
4199 vec
<lambda_vector
> dir_vects
, dist_vects
;
4201 /* Save the result of the first DD analyzer. */
4202 dist_vects
= DDR_DIST_VECTS (ddr
);
4203 dir_vects
= DDR_DIR_VECTS (ddr
);
4205 /* Reset the information. */
4206 DDR_DIST_VECTS (ddr
).create (0);
4207 DDR_DIR_VECTS (ddr
).create (0);
4209 /* Compute the same information using Omega. */
4210 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
4211 goto csys_dont_know
;
4213 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4215 fprintf (dump_file
, "Omega Analyzer\n");
4216 dump_data_dependence_relation (dump_file
, ddr
);
4219 /* Check that we get the same information. */
4220 if (maybe_dependent
)
4221 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
4227 /* As a last case, if the dependence cannot be determined, or if
4228 the dependence is considered too difficult to determine, answer
4233 dependence_stats
.num_dependence_undetermined
++;
4235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4237 fprintf (dump_file
, "Data ref a:\n");
4238 dump_data_reference (dump_file
, dra
);
4239 fprintf (dump_file
, "Data ref b:\n");
4240 dump_data_reference (dump_file
, drb
);
4241 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
4243 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4247 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4249 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4250 fprintf (dump_file
, ") -> no dependence\n");
4251 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4252 fprintf (dump_file
, ") -> dependence analysis failed\n");
4254 fprintf (dump_file
, ")\n");
4258 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4259 the data references in DATAREFS, in the LOOP_NEST. When
4260 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4261 relations. Return true when successful, i.e. data references number
4262 is small enough to be handled. */
4265 compute_all_dependences (vec
<data_reference_p
> datarefs
,
4266 vec
<ddr_p
> *dependence_relations
,
4267 vec
<loop_p
> loop_nest
,
4268 bool compute_self_and_rr
)
4270 struct data_dependence_relation
*ddr
;
4271 struct data_reference
*a
, *b
;
4274 if ((int) datarefs
.length ()
4275 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS
))
4277 struct data_dependence_relation
*ddr
;
4279 /* Insert a single relation into dependence_relations:
4281 ddr
= initialize_data_dependence_relation (NULL
, NULL
, loop_nest
);
4282 dependence_relations
->safe_push (ddr
);
4286 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4287 for (j
= i
+ 1; datarefs
.iterate (j
, &b
); j
++)
4288 if (DR_IS_WRITE (a
) || DR_IS_WRITE (b
) || compute_self_and_rr
)
4290 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4291 dependence_relations
->safe_push (ddr
);
4292 if (loop_nest
.exists ())
4293 compute_affine_dependence (ddr
, loop_nest
[0]);
4296 if (compute_self_and_rr
)
4297 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4299 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4300 dependence_relations
->safe_push (ddr
);
4301 if (loop_nest
.exists ())
4302 compute_affine_dependence (ddr
, loop_nest
[0]);
4308 /* Describes a location of a memory reference. */
4310 typedef struct data_ref_loc_d
4312 /* Position of the memory reference. */
4315 /* True if the memory reference is read. */
4320 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4321 true if STMT clobbers memory, false otherwise. */
4324 get_references_in_stmt (gimple stmt
, vec
<data_ref_loc
, va_stack
> *references
)
4326 bool clobbers_memory
= false;
4329 enum gimple_code stmt_code
= gimple_code (stmt
);
4331 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4332 As we cannot model data-references to not spelled out
4333 accesses give up if they may occur. */
4334 if (stmt_code
== GIMPLE_CALL
4335 && !(gimple_call_flags (stmt
) & ECF_CONST
))
4337 /* Allow IFN_GOMP_SIMD_LANE in their own loops. */
4338 if (gimple_call_internal_p (stmt
)
4339 && gimple_call_internal_fn (stmt
) == IFN_GOMP_SIMD_LANE
)
4341 struct loop
*loop
= gimple_bb (stmt
)->loop_father
;
4342 tree uid
= gimple_call_arg (stmt
, 0);
4343 gcc_assert (TREE_CODE (uid
) == SSA_NAME
);
4345 || loop
->simduid
!= SSA_NAME_VAR (uid
))
4346 clobbers_memory
= true;
4349 clobbers_memory
= true;
4351 else if (stmt_code
== GIMPLE_ASM
4352 && (gimple_asm_volatile_p (stmt
) || gimple_vuse (stmt
)))
4353 clobbers_memory
= true;
4355 if (!gimple_vuse (stmt
))
4356 return clobbers_memory
;
4358 if (stmt_code
== GIMPLE_ASSIGN
)
4361 op0
= gimple_assign_lhs_ptr (stmt
);
4362 op1
= gimple_assign_rhs1_ptr (stmt
);
4365 || (REFERENCE_CLASS_P (*op1
)
4366 && (base
= get_base_address (*op1
))
4367 && TREE_CODE (base
) != SSA_NAME
))
4371 references
->safe_push (ref
);
4374 else if (stmt_code
== GIMPLE_CALL
)
4378 op0
= gimple_call_lhs_ptr (stmt
);
4379 n
= gimple_call_num_args (stmt
);
4380 for (i
= 0; i
< n
; i
++)
4382 op1
= gimple_call_arg_ptr (stmt
, i
);
4385 || (REFERENCE_CLASS_P (*op1
) && get_base_address (*op1
)))
4389 references
->safe_push (ref
);
4394 return clobbers_memory
;
4398 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
))))
4401 ref
.is_read
= false;
4402 references
->safe_push (ref
);
4404 return clobbers_memory
;
4407 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4408 reference, returns false, otherwise returns true. NEST is the outermost
4409 loop of the loop nest in which the references should be analyzed. */
4412 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4413 vec
<data_reference_p
> *datarefs
)
4416 vec
<data_ref_loc
, va_stack
> references
;
4419 data_reference_p dr
;
4421 vec_stack_alloc (data_ref_loc
, references
, 2);
4422 if (get_references_in_stmt (stmt
, &references
))
4424 references
.release ();
4428 FOR_EACH_VEC_ELT (references
, i
, ref
)
4430 dr
= create_data_ref (nest
, loop_containing_stmt (stmt
),
4431 *ref
->pos
, stmt
, ref
->is_read
);
4432 gcc_assert (dr
!= NULL
);
4433 datarefs
->safe_push (dr
);
4435 references
.release ();
4439 /* Stores the data references in STMT to DATAREFS. If there is an
4440 unanalyzable reference, returns false, otherwise returns true.
4441 NEST is the outermost loop of the loop nest in which the references
4442 should be instantiated, LOOP is the loop in which the references
4443 should be analyzed. */
4446 graphite_find_data_references_in_stmt (loop_p nest
, loop_p loop
, gimple stmt
,
4447 vec
<data_reference_p
> *datarefs
)
4450 vec
<data_ref_loc
, va_stack
> references
;
4453 data_reference_p dr
;
4455 vec_stack_alloc (data_ref_loc
, references
, 2);
4456 if (get_references_in_stmt (stmt
, &references
))
4458 references
.release ();
4462 FOR_EACH_VEC_ELT (references
, i
, ref
)
4464 dr
= create_data_ref (nest
, loop
, *ref
->pos
, stmt
, ref
->is_read
);
4465 gcc_assert (dr
!= NULL
);
4466 datarefs
->safe_push (dr
);
4469 references
.release ();
4473 /* Search the data references in LOOP, and record the information into
4474 DATAREFS. Returns chrec_dont_know when failing to analyze a
4475 difficult case, returns NULL_TREE otherwise. */
4478 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4479 vec
<data_reference_p
> *datarefs
)
4481 gimple_stmt_iterator bsi
;
4483 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4485 gimple stmt
= gsi_stmt (bsi
);
4487 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4489 struct data_reference
*res
;
4490 res
= XCNEW (struct data_reference
);
4491 datarefs
->safe_push (res
);
4493 return chrec_dont_know
;
4500 /* Search the data references in LOOP, and record the information into
4501 DATAREFS. Returns chrec_dont_know when failing to analyze a
4502 difficult case, returns NULL_TREE otherwise.
4504 TODO: This function should be made smarter so that it can handle address
4505 arithmetic as if they were array accesses, etc. */
4508 find_data_references_in_loop (struct loop
*loop
,
4509 vec
<data_reference_p
> *datarefs
)
4511 basic_block bb
, *bbs
;
4514 bbs
= get_loop_body_in_dom_order (loop
);
4516 for (i
= 0; i
< loop
->num_nodes
; i
++)
4520 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4523 return chrec_dont_know
;
4531 /* Recursive helper function. */
4534 find_loop_nest_1 (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
4536 /* Inner loops of the nest should not contain siblings. Example:
4537 when there are two consecutive loops,
4548 the dependence relation cannot be captured by the distance
4553 loop_nest
->safe_push (loop
);
4555 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4559 /* Return false when the LOOP is not well nested. Otherwise return
4560 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4561 contain the loops from the outermost to the innermost, as they will
4562 appear in the classic distance vector. */
4565 find_loop_nest (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
4567 loop_nest
->safe_push (loop
);
4569 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4573 /* Returns true when the data dependences have been computed, false otherwise.
4574 Given a loop nest LOOP, the following vectors are returned:
4575 DATAREFS is initialized to all the array elements contained in this loop,
4576 DEPENDENCE_RELATIONS contains the relations between the data references.
4577 Compute read-read and self relations if
4578 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4581 compute_data_dependences_for_loop (struct loop
*loop
,
4582 bool compute_self_and_read_read_dependences
,
4583 vec
<loop_p
> *loop_nest
,
4584 vec
<data_reference_p
> *datarefs
,
4585 vec
<ddr_p
> *dependence_relations
)
4589 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4591 /* If the loop nest is not well formed, or one of the data references
4592 is not computable, give up without spending time to compute other
4595 || !find_loop_nest (loop
, loop_nest
)
4596 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
4597 || !compute_all_dependences (*datarefs
, dependence_relations
, *loop_nest
,
4598 compute_self_and_read_read_dependences
))
4601 if (dump_file
&& (dump_flags
& TDF_STATS
))
4603 fprintf (dump_file
, "Dependence tester statistics:\n");
4605 fprintf (dump_file
, "Number of dependence tests: %d\n",
4606 dependence_stats
.num_dependence_tests
);
4607 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4608 dependence_stats
.num_dependence_dependent
);
4609 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4610 dependence_stats
.num_dependence_independent
);
4611 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4612 dependence_stats
.num_dependence_undetermined
);
4614 fprintf (dump_file
, "Number of subscript tests: %d\n",
4615 dependence_stats
.num_subscript_tests
);
4616 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4617 dependence_stats
.num_subscript_undetermined
);
4618 fprintf (dump_file
, "Number of same subscript function: %d\n",
4619 dependence_stats
.num_same_subscript_function
);
4621 fprintf (dump_file
, "Number of ziv tests: %d\n",
4622 dependence_stats
.num_ziv
);
4623 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4624 dependence_stats
.num_ziv_dependent
);
4625 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4626 dependence_stats
.num_ziv_independent
);
4627 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4628 dependence_stats
.num_ziv_unimplemented
);
4630 fprintf (dump_file
, "Number of siv tests: %d\n",
4631 dependence_stats
.num_siv
);
4632 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4633 dependence_stats
.num_siv_dependent
);
4634 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4635 dependence_stats
.num_siv_independent
);
4636 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4637 dependence_stats
.num_siv_unimplemented
);
4639 fprintf (dump_file
, "Number of miv tests: %d\n",
4640 dependence_stats
.num_miv
);
4641 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4642 dependence_stats
.num_miv_dependent
);
4643 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4644 dependence_stats
.num_miv_independent
);
4645 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4646 dependence_stats
.num_miv_unimplemented
);
4652 /* Returns true when the data dependences for the basic block BB have been
4653 computed, false otherwise.
4654 DATAREFS is initialized to all the array elements contained in this basic
4655 block, DEPENDENCE_RELATIONS contains the relations between the data
4656 references. Compute read-read and self relations if
4657 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4659 compute_data_dependences_for_bb (basic_block bb
,
4660 bool compute_self_and_read_read_dependences
,
4661 vec
<data_reference_p
> *datarefs
,
4662 vec
<ddr_p
> *dependence_relations
)
4664 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4667 return compute_all_dependences (*datarefs
, dependence_relations
, vNULL
,
4668 compute_self_and_read_read_dependences
);
4671 /* Entry point (for testing only). Analyze all the data references
4672 and the dependence relations in LOOP.
4674 The data references are computed first.
4676 A relation on these nodes is represented by a complete graph. Some
4677 of the relations could be of no interest, thus the relations can be
4680 In the following function we compute all the relations. This is
4681 just a first implementation that is here for:
4682 - for showing how to ask for the dependence relations,
4683 - for the debugging the whole dependence graph,
4684 - for the dejagnu testcases and maintenance.
4686 It is possible to ask only for a part of the graph, avoiding to
4687 compute the whole dependence graph. The computed dependences are
4688 stored in a knowledge base (KB) such that later queries don't
4689 recompute the same information. The implementation of this KB is
4690 transparent to the optimizer, and thus the KB can be changed with a
4691 more efficient implementation, or the KB could be disabled. */
4693 analyze_all_data_dependences (struct loop
*loop
)
4696 int nb_data_refs
= 10;
4697 vec
<data_reference_p
> datarefs
;
4698 datarefs
.create (nb_data_refs
);
4699 vec
<ddr_p
> dependence_relations
;
4700 dependence_relations
.create (nb_data_refs
* nb_data_refs
);
4701 vec
<loop_p
> loop_nest
;
4702 loop_nest
.create (3);
4704 /* Compute DDs on the whole function. */
4705 compute_data_dependences_for_loop (loop
, false, &loop_nest
, &datarefs
,
4706 &dependence_relations
);
4710 dump_data_dependence_relations (dump_file
, dependence_relations
);
4711 fprintf (dump_file
, "\n\n");
4713 if (dump_flags
& TDF_DETAILS
)
4714 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4716 if (dump_flags
& TDF_STATS
)
4718 unsigned nb_top_relations
= 0;
4719 unsigned nb_bot_relations
= 0;
4720 unsigned nb_chrec_relations
= 0;
4721 struct data_dependence_relation
*ddr
;
4723 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
4725 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4728 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4732 nb_chrec_relations
++;
4735 gather_stats_on_scev_database ();
4739 loop_nest
.release ();
4740 free_dependence_relations (dependence_relations
);
4741 free_data_refs (datarefs
);
4744 /* Computes all the data dependences and check that the results of
4745 several analyzers are the same. */
4748 tree_check_data_deps (void)
4751 struct loop
*loop_nest
;
4753 FOR_EACH_LOOP (li
, loop_nest
, 0)
4754 analyze_all_data_dependences (loop_nest
);
4757 /* Free the memory used by a data dependence relation DDR. */
4760 free_dependence_relation (struct data_dependence_relation
*ddr
)
4765 if (DDR_SUBSCRIPTS (ddr
).exists ())
4766 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4767 DDR_DIST_VECTS (ddr
).release ();
4768 DDR_DIR_VECTS (ddr
).release ();
4773 /* Free the memory used by the data dependence relations from
4774 DEPENDENCE_RELATIONS. */
4777 free_dependence_relations (vec
<ddr_p
> dependence_relations
)
4780 struct data_dependence_relation
*ddr
;
4782 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
4784 free_dependence_relation (ddr
);
4786 dependence_relations
.release ();
4789 /* Free the memory used by the data references from DATAREFS. */
4792 free_data_refs (vec
<data_reference_p
> datarefs
)
4795 struct data_reference
*dr
;
4797 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
4799 datarefs
.release ();
4804 /* Dump vertex I in RDG to FILE. */
4807 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4809 struct vertex
*v
= &(rdg
->vertices
[i
]);
4810 struct graph_edge
*e
;
4812 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4813 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4814 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4817 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4818 fprintf (file
, " %d", e
->src
);
4820 fprintf (file
, ") (out:");
4823 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4824 fprintf (file
, " %d", e
->dest
);
4826 fprintf (file
, ")\n");
4827 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4828 fprintf (file
, ")\n");
4831 /* Call dump_rdg_vertex on stderr. */
4834 debug_rdg_vertex (struct graph
*rdg
, int i
)
4836 dump_rdg_vertex (stderr
, rdg
, i
);
4839 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4840 dumped vertices to that bitmap. */
4843 dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4847 fprintf (file
, "(%d\n", c
);
4849 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4850 if (rdg
->vertices
[i
].component
== c
)
4853 bitmap_set_bit (dumped
, i
);
4855 dump_rdg_vertex (file
, rdg
, i
);
4858 fprintf (file
, ")\n");
4861 /* Call dump_rdg_vertex on stderr. */
4864 debug_rdg_component (struct graph
*rdg
, int c
)
4866 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4869 /* Dump the reduced dependence graph RDG to FILE. */
4872 dump_rdg (FILE *file
, struct graph
*rdg
)
4875 bitmap dumped
= BITMAP_ALLOC (NULL
);
4877 fprintf (file
, "(rdg\n");
4879 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4880 if (!bitmap_bit_p (dumped
, i
))
4881 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4883 fprintf (file
, ")\n");
4884 BITMAP_FREE (dumped
);
4887 /* Call dump_rdg on stderr. */
4890 debug_rdg (struct graph
*rdg
)
4892 dump_rdg (stderr
, rdg
);
4896 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
4900 fprintf (file
, "digraph RDG {\n");
4902 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4904 struct vertex
*v
= &(rdg
->vertices
[i
]);
4905 struct graph_edge
*e
;
4907 /* Highlight reads from memory. */
4908 if (RDG_MEM_READS_STMT (rdg
, i
))
4909 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
4911 /* Highlight stores to memory. */
4912 if (RDG_MEM_WRITE_STMT (rdg
, i
))
4913 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
4916 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4917 switch (RDGE_TYPE (e
))
4920 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
4924 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
4928 /* These are the most common dependences: don't print these. */
4929 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
4933 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
4941 fprintf (file
, "}\n\n");
4944 /* Display the Reduced Dependence Graph using dotty. */
4945 extern void dot_rdg (struct graph
*);
4948 dot_rdg (struct graph
*rdg
)
4950 /* When debugging, enable the following code. This cannot be used
4951 in production compilers because it calls "system". */
4953 FILE *file
= fopen ("/tmp/rdg.dot", "w");
4954 gcc_assert (file
!= NULL
);
4956 dot_rdg_1 (file
, rdg
);
4959 system ("dotty /tmp/rdg.dot &");
4961 dot_rdg_1 (stderr
, rdg
);
4965 /* Returns the index of STMT in RDG. */
4968 rdg_vertex_for_stmt (struct graph
*rdg ATTRIBUTE_UNUSED
, gimple stmt
)
4970 int index
= gimple_uid (stmt
);
4971 gcc_checking_assert (index
== -1 || RDG_STMT (rdg
, index
) == stmt
);
4975 /* Creates an edge in RDG for each distance vector from DDR. The
4976 order that we keep track of in the RDG is the order in which
4977 statements have to be executed. */
4980 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4982 struct graph_edge
*e
;
4984 data_reference_p dra
= DDR_A (ddr
);
4985 data_reference_p drb
= DDR_B (ddr
);
4986 unsigned level
= ddr_dependence_level (ddr
);
4988 /* For non scalar dependences, when the dependence is REVERSED,
4989 statement B has to be executed before statement A. */
4991 && !DDR_REVERSED_P (ddr
))
4993 data_reference_p tmp
= dra
;
4998 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4999 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
5001 if (va
< 0 || vb
< 0)
5004 e
= add_edge (rdg
, va
, vb
);
5005 e
->data
= XNEW (struct rdg_edge
);
5007 RDGE_LEVEL (e
) = level
;
5008 RDGE_RELATION (e
) = ddr
;
5010 /* Determines the type of the data dependence. */
5011 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
5012 RDGE_TYPE (e
) = input_dd
;
5013 else if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
5014 RDGE_TYPE (e
) = output_dd
;
5015 else if (DR_IS_WRITE (dra
) && DR_IS_READ (drb
))
5016 RDGE_TYPE (e
) = flow_dd
;
5017 else if (DR_IS_READ (dra
) && DR_IS_WRITE (drb
))
5018 RDGE_TYPE (e
) = anti_dd
;
5021 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
5022 the index of DEF in RDG. */
5025 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
5027 use_operand_p imm_use_p
;
5028 imm_use_iterator iterator
;
5030 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
5032 struct graph_edge
*e
;
5033 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
5038 e
= add_edge (rdg
, idef
, use
);
5039 e
->data
= XNEW (struct rdg_edge
);
5040 RDGE_TYPE (e
) = flow_dd
;
5041 RDGE_RELATION (e
) = NULL
;
5045 /* Creates the edges of the reduced dependence graph RDG. */
5048 create_rdg_edges (struct graph
*rdg
, vec
<ddr_p
> ddrs
)
5051 struct data_dependence_relation
*ddr
;
5052 def_operand_p def_p
;
5055 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
5056 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
5057 create_rdg_edge_for_ddr (rdg
, ddr
);
5059 for (i
= 0; i
< rdg
->n_vertices
; i
++)
5060 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
5062 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
5065 /* Build the vertices of the reduced dependence graph RDG. Return false
5069 create_rdg_vertices (struct graph
*rdg
, vec
<gimple
> stmts
, loop_p loop
,
5070 vec
<data_reference_p
> *datarefs
)
5075 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
5077 struct vertex
*v
= &(rdg
->vertices
[i
]);
5079 /* Record statement to vertex mapping. */
5080 gimple_set_uid (stmt
, i
);
5082 v
->data
= XNEW (struct rdg_vertex
);
5083 RDGV_STMT (v
) = stmt
;
5084 RDGV_DATAREFS (v
).create (0);
5085 RDGV_HAS_MEM_WRITE (v
) = false;
5086 RDGV_HAS_MEM_READS (v
) = false;
5087 if (gimple_code (stmt
) == GIMPLE_PHI
)
5090 unsigned drp
= datarefs
->length ();
5091 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
5093 for (unsigned j
= drp
; j
< datarefs
->length (); ++j
)
5095 data_reference_p dr
= (*datarefs
)[j
];
5096 if (DR_IS_READ (dr
))
5097 RDGV_HAS_MEM_READS (v
) = true;
5099 RDGV_HAS_MEM_WRITE (v
) = true;
5100 RDGV_DATAREFS (v
).safe_push (dr
);
5106 /* Initialize STMTS with all the statements of LOOP. When
5107 INCLUDE_PHIS is true, include also the PHI nodes. The order in
5108 which we discover statements is important as
5109 generate_loops_for_partition is using the same traversal for
5110 identifying statements. */
5113 stmts_from_loop (struct loop
*loop
, vec
<gimple
> *stmts
)
5116 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
5118 for (i
= 0; i
< loop
->num_nodes
; i
++)
5120 basic_block bb
= bbs
[i
];
5121 gimple_stmt_iterator bsi
;
5124 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
5125 stmts
->safe_push (gsi_stmt (bsi
));
5127 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
5129 stmt
= gsi_stmt (bsi
);
5130 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
5131 stmts
->safe_push (stmt
);
5138 /* Returns true when all the dependences are computable. */
5141 known_dependences_p (vec
<ddr_p
> dependence_relations
)
5146 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
5147 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
5153 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5154 statement of the loop nest, and one edge per data dependence or
5155 scalar dependence. */
5158 build_empty_rdg (int n_stmts
)
5160 struct graph
*rdg
= new_graph (n_stmts
);
5164 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5165 statement of the loop nest, and one edge per data dependence or
5166 scalar dependence. */
5169 build_rdg (struct loop
*loop
)
5172 vec
<loop_p
> loop_nest
;
5174 vec
<data_reference_p
> datarefs
;
5175 vec
<ddr_p
> dependence_relations
;
5177 loop_nest
.create (3);
5178 if (!find_loop_nest (loop
, &loop_nest
))
5180 loop_nest
.release ();
5185 stmts_from_loop (loop
, &stmts
);
5186 rdg
= build_empty_rdg (stmts
.length ());
5187 datarefs
.create (10);
5188 if (!create_rdg_vertices (rdg
, stmts
, loop
, &datarefs
))
5195 dependence_relations
.create (100);
5196 if (!compute_all_dependences (datarefs
, &dependence_relations
, loop_nest
,
5198 || !known_dependences_p (dependence_relations
))
5200 loop_nest
.release ();
5201 datarefs
.release ();
5202 dependence_relations
.release ();
5206 loop_nest
.release ();
5207 create_rdg_edges (rdg
, dependence_relations
);
5208 dependence_relations
.release ();
5213 /* Free the reduced dependence graph RDG. */
5216 free_rdg (struct graph
*rdg
)
5220 for (i
= 0; i
< rdg
->n_vertices
; i
++)
5222 struct vertex
*v
= &(rdg
->vertices
[i
]);
5223 struct graph_edge
*e
;
5225 for (e
= v
->succ
; e
; e
= e
->succ_next
)
5227 free_dependence_relation (RDGE_RELATION (e
));
5233 gimple_set_uid (RDGV_STMT (v
), -1);
5234 free_data_refs (RDGV_DATAREFS (v
));
5242 /* Determines whether the statement from vertex V of the RDG has a
5243 definition used outside the loop that contains this statement. */
5246 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
5248 gimple stmt
= RDG_STMT (rdg
, v
);
5249 struct loop
*loop
= loop_containing_stmt (stmt
);
5250 use_operand_p imm_use_p
;
5251 imm_use_iterator iterator
;
5253 def_operand_p def_p
;
5258 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
5260 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
5262 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)