1 /* Data references and dependences detectors.
2 Copyright (C) 2003-2014 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"
81 #include "gimple-pretty-print.h"
82 #include "basic-block.h"
83 #include "tree-ssa-alias.h"
84 #include "internal-fn.h"
85 #include "gimple-expr.h"
88 #include "gimple-iterator.h"
89 #include "tree-ssa-loop-niter.h"
90 #include "tree-ssa-loop.h"
93 #include "tree-data-ref.h"
94 #include "tree-scalar-evolution.h"
96 #include "langhooks.h"
97 #include "tree-affine.h"
100 static struct datadep_stats
102 int num_dependence_tests
;
103 int num_dependence_dependent
;
104 int num_dependence_independent
;
105 int num_dependence_undetermined
;
107 int num_subscript_tests
;
108 int num_subscript_undetermined
;
109 int num_same_subscript_function
;
112 int num_ziv_independent
;
113 int num_ziv_dependent
;
114 int num_ziv_unimplemented
;
117 int num_siv_independent
;
118 int num_siv_dependent
;
119 int num_siv_unimplemented
;
122 int num_miv_independent
;
123 int num_miv_dependent
;
124 int num_miv_unimplemented
;
127 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
128 struct data_reference
*,
129 struct data_reference
*,
131 /* Returns true iff A divides B. */
134 tree_fold_divides_p (const_tree a
, const_tree b
)
136 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
137 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
138 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
));
141 /* Returns true iff A divides B. */
144 int_divides_p (int a
, int b
)
146 return ((b
% a
) == 0);
151 /* Dump into FILE all the data references from DATAREFS. */
154 dump_data_references (FILE *file
, vec
<data_reference_p
> datarefs
)
157 struct data_reference
*dr
;
159 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
160 dump_data_reference (file
, dr
);
163 /* Unified dump into FILE all the data references from DATAREFS. */
166 debug (vec
<data_reference_p
> &ref
)
168 dump_data_references (stderr
, ref
);
172 debug (vec
<data_reference_p
> *ptr
)
177 fprintf (stderr
, "<nil>\n");
181 /* Dump into STDERR all the data references from DATAREFS. */
184 debug_data_references (vec
<data_reference_p
> datarefs
)
186 dump_data_references (stderr
, datarefs
);
189 /* Print to STDERR the data_reference DR. */
192 debug_data_reference (struct data_reference
*dr
)
194 dump_data_reference (stderr
, dr
);
197 /* Dump function for a DATA_REFERENCE structure. */
200 dump_data_reference (FILE *outf
,
201 struct data_reference
*dr
)
205 fprintf (outf
, "#(Data Ref: \n");
206 fprintf (outf
, "# bb: %d \n", gimple_bb (DR_STMT (dr
))->index
);
207 fprintf (outf
, "# stmt: ");
208 print_gimple_stmt (outf
, DR_STMT (dr
), 0, 0);
209 fprintf (outf
, "# ref: ");
210 print_generic_stmt (outf
, DR_REF (dr
), 0);
211 fprintf (outf
, "# base_object: ");
212 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
214 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
216 fprintf (outf
, "# Access function %d: ", i
);
217 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
219 fprintf (outf
, "#)\n");
222 /* Unified dump function for a DATA_REFERENCE structure. */
225 debug (data_reference
&ref
)
227 dump_data_reference (stderr
, &ref
);
231 debug (data_reference
*ptr
)
236 fprintf (stderr
, "<nil>\n");
240 /* Dumps the affine function described by FN to the file OUTF. */
243 dump_affine_function (FILE *outf
, affine_fn fn
)
248 print_generic_expr (outf
, fn
[0], TDF_SLIM
);
249 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
251 fprintf (outf
, " + ");
252 print_generic_expr (outf
, coef
, TDF_SLIM
);
253 fprintf (outf
, " * x_%u", i
);
257 /* Dumps the conflict function CF to the file OUTF. */
260 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
264 if (cf
->n
== NO_DEPENDENCE
)
265 fprintf (outf
, "no dependence");
266 else if (cf
->n
== NOT_KNOWN
)
267 fprintf (outf
, "not known");
270 for (i
= 0; i
< cf
->n
; i
++)
275 dump_affine_function (outf
, cf
->fns
[i
]);
281 /* Dump function for a SUBSCRIPT structure. */
284 dump_subscript (FILE *outf
, struct subscript
*subscript
)
286 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
288 fprintf (outf
, "\n (subscript \n");
289 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
290 dump_conflict_function (outf
, cf
);
291 if (CF_NONTRIVIAL_P (cf
))
293 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
294 fprintf (outf
, "\n last_conflict: ");
295 print_generic_expr (outf
, last_iteration
, 0);
298 cf
= SUB_CONFLICTS_IN_B (subscript
);
299 fprintf (outf
, "\n iterations_that_access_an_element_twice_in_B: ");
300 dump_conflict_function (outf
, cf
);
301 if (CF_NONTRIVIAL_P (cf
))
303 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
304 fprintf (outf
, "\n last_conflict: ");
305 print_generic_expr (outf
, last_iteration
, 0);
308 fprintf (outf
, "\n (Subscript distance: ");
309 print_generic_expr (outf
, SUB_DISTANCE (subscript
), 0);
310 fprintf (outf
, " ))\n");
313 /* Print the classic direction vector DIRV to OUTF. */
316 print_direction_vector (FILE *outf
,
322 for (eq
= 0; eq
< length
; eq
++)
324 enum data_dependence_direction dir
= ((enum data_dependence_direction
)
330 fprintf (outf
, " +");
333 fprintf (outf
, " -");
336 fprintf (outf
, " =");
338 case dir_positive_or_equal
:
339 fprintf (outf
, " +=");
341 case dir_positive_or_negative
:
342 fprintf (outf
, " +-");
344 case dir_negative_or_equal
:
345 fprintf (outf
, " -=");
348 fprintf (outf
, " *");
351 fprintf (outf
, "indep");
355 fprintf (outf
, "\n");
358 /* Print a vector of direction vectors. */
361 print_dir_vectors (FILE *outf
, vec
<lambda_vector
> dir_vects
,
367 FOR_EACH_VEC_ELT (dir_vects
, j
, v
)
368 print_direction_vector (outf
, v
, length
);
371 /* Print out a vector VEC of length N to OUTFILE. */
374 print_lambda_vector (FILE * outfile
, lambda_vector vector
, int n
)
378 for (i
= 0; i
< n
; i
++)
379 fprintf (outfile
, "%3d ", vector
[i
]);
380 fprintf (outfile
, "\n");
383 /* Print a vector of distance vectors. */
386 print_dist_vectors (FILE *outf
, vec
<lambda_vector
> dist_vects
,
392 FOR_EACH_VEC_ELT (dist_vects
, j
, v
)
393 print_lambda_vector (outf
, v
, length
);
396 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
399 dump_data_dependence_relation (FILE *outf
,
400 struct data_dependence_relation
*ddr
)
402 struct data_reference
*dra
, *drb
;
404 fprintf (outf
, "(Data Dep: \n");
406 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
413 dump_data_reference (outf
, dra
);
415 fprintf (outf
, " (nil)\n");
417 dump_data_reference (outf
, drb
);
419 fprintf (outf
, " (nil)\n");
421 fprintf (outf
, " (don't know)\n)\n");
427 dump_data_reference (outf
, dra
);
428 dump_data_reference (outf
, drb
);
430 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
431 fprintf (outf
, " (no dependence)\n");
433 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
438 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
440 fprintf (outf
, " access_fn_A: ");
441 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
442 fprintf (outf
, " access_fn_B: ");
443 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
444 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
447 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
448 fprintf (outf
, " loop nest: (");
449 FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr
), i
, loopi
)
450 fprintf (outf
, "%d ", loopi
->num
);
451 fprintf (outf
, ")\n");
453 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
455 fprintf (outf
, " distance_vector: ");
456 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
460 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
462 fprintf (outf
, " direction_vector: ");
463 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
468 fprintf (outf
, ")\n");
474 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
476 dump_data_dependence_relation (stderr
, ddr
);
479 /* Dump into FILE all the dependence relations from DDRS. */
482 dump_data_dependence_relations (FILE *file
,
486 struct data_dependence_relation
*ddr
;
488 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
489 dump_data_dependence_relation (file
, ddr
);
493 debug (vec
<ddr_p
> &ref
)
495 dump_data_dependence_relations (stderr
, ref
);
499 debug (vec
<ddr_p
> *ptr
)
504 fprintf (stderr
, "<nil>\n");
508 /* Dump to STDERR all the dependence relations from DDRS. */
511 debug_data_dependence_relations (vec
<ddr_p
> ddrs
)
513 dump_data_dependence_relations (stderr
, ddrs
);
516 /* Dumps the distance and direction vectors in FILE. DDRS contains
517 the dependence relations, and VECT_SIZE is the size of the
518 dependence vectors, or in other words the number of loops in the
522 dump_dist_dir_vectors (FILE *file
, vec
<ddr_p
> ddrs
)
525 struct data_dependence_relation
*ddr
;
528 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
529 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
531 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), j
, v
)
533 fprintf (file
, "DISTANCE_V (");
534 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
535 fprintf (file
, ")\n");
538 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), j
, v
)
540 fprintf (file
, "DIRECTION_V (");
541 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
542 fprintf (file
, ")\n");
546 fprintf (file
, "\n\n");
549 /* Dumps the data dependence relations DDRS in FILE. */
552 dump_ddrs (FILE *file
, vec
<ddr_p
> ddrs
)
555 struct data_dependence_relation
*ddr
;
557 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
558 dump_data_dependence_relation (file
, ddr
);
560 fprintf (file
, "\n\n");
564 debug_ddrs (vec
<ddr_p
> ddrs
)
566 dump_ddrs (stderr
, ddrs
);
569 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
570 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
571 constant of type ssizetype, and returns true. If we cannot do this
572 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
576 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
577 tree
*var
, tree
*off
)
581 enum tree_code ocode
= code
;
589 *var
= build_int_cst (type
, 0);
590 *off
= fold_convert (ssizetype
, op0
);
593 case POINTER_PLUS_EXPR
:
598 split_constant_offset (op0
, &var0
, &off0
);
599 split_constant_offset (op1
, &var1
, &off1
);
600 *var
= fold_build2 (code
, type
, var0
, var1
);
601 *off
= size_binop (ocode
, off0
, off1
);
605 if (TREE_CODE (op1
) != INTEGER_CST
)
608 split_constant_offset (op0
, &var0
, &off0
);
609 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
610 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
616 HOST_WIDE_INT pbitsize
, pbitpos
;
617 enum machine_mode pmode
;
618 int punsignedp
, pvolatilep
;
620 op0
= TREE_OPERAND (op0
, 0);
621 base
= get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
,
622 &pmode
, &punsignedp
, &pvolatilep
, false);
624 if (pbitpos
% BITS_PER_UNIT
!= 0)
626 base
= build_fold_addr_expr (base
);
627 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
631 split_constant_offset (poffset
, &poffset
, &off1
);
632 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
633 if (POINTER_TYPE_P (TREE_TYPE (base
)))
634 base
= fold_build_pointer_plus (base
, poffset
);
636 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
637 fold_convert (TREE_TYPE (base
), poffset
));
640 var0
= fold_convert (type
, base
);
642 /* If variable length types are involved, punt, otherwise casts
643 might be converted into ARRAY_REFs in gimplify_conversion.
644 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
645 possibly no longer appears in current GIMPLE, might resurface.
646 This perhaps could run
647 if (CONVERT_EXPR_P (var0))
649 gimplify_conversion (&var0);
650 // Attempt to fill in any within var0 found ARRAY_REF's
651 // element size from corresponding op embedded ARRAY_REF,
652 // if unsuccessful, just punt.
654 while (POINTER_TYPE_P (type
))
655 type
= TREE_TYPE (type
);
656 if (int_size_in_bytes (type
) < 0)
666 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
))
669 gimple def_stmt
= SSA_NAME_DEF_STMT (op0
);
670 enum tree_code subcode
;
672 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
675 var0
= gimple_assign_rhs1 (def_stmt
);
676 subcode
= gimple_assign_rhs_code (def_stmt
);
677 var1
= gimple_assign_rhs2 (def_stmt
);
679 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
683 /* We must not introduce undefined overflow, and we must not change the value.
684 Hence we're okay if the inner type doesn't overflow to start with
685 (pointer or signed), the outer type also is an integer or pointer
686 and the outer precision is at least as large as the inner. */
687 tree itype
= TREE_TYPE (op0
);
688 if ((POINTER_TYPE_P (itype
)
689 || (INTEGRAL_TYPE_P (itype
) && TYPE_OVERFLOW_UNDEFINED (itype
)))
690 && TYPE_PRECISION (type
) >= TYPE_PRECISION (itype
)
691 && (POINTER_TYPE_P (type
) || INTEGRAL_TYPE_P (type
)))
693 split_constant_offset (op0
, &var0
, off
);
694 *var
= fold_convert (type
, var0
);
705 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
706 will be ssizetype. */
709 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
711 tree type
= TREE_TYPE (exp
), otype
, op0
, op1
, e
, o
;
715 *off
= ssize_int (0);
718 if (tree_is_chrec (exp
)
719 || get_gimple_rhs_class (TREE_CODE (exp
)) == GIMPLE_TERNARY_RHS
)
722 otype
= TREE_TYPE (exp
);
723 code
= TREE_CODE (exp
);
724 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
725 if (split_constant_offset_1 (otype
, op0
, code
, op1
, &e
, &o
))
727 *var
= fold_convert (type
, e
);
732 /* Returns the address ADDR of an object in a canonical shape (without nop
733 casts, and with type of pointer to the object). */
736 canonicalize_base_object_address (tree addr
)
742 /* The base address may be obtained by casting from integer, in that case
744 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
747 if (TREE_CODE (addr
) != ADDR_EXPR
)
750 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
753 /* Analyzes the behavior of the memory reference DR in the innermost loop or
754 basic block that contains it. Returns true if analysis succeed or false
758 dr_analyze_innermost (struct data_reference
*dr
, struct loop
*nest
)
760 gimple stmt
= DR_STMT (dr
);
761 struct loop
*loop
= loop_containing_stmt (stmt
);
762 tree ref
= DR_REF (dr
);
763 HOST_WIDE_INT pbitsize
, pbitpos
;
765 enum machine_mode pmode
;
766 int punsignedp
, pvolatilep
;
767 affine_iv base_iv
, offset_iv
;
768 tree init
, dinit
, step
;
769 bool in_loop
= (loop
&& loop
->num
);
771 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
772 fprintf (dump_file
, "analyze_innermost: ");
774 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
775 &pmode
, &punsignedp
, &pvolatilep
, false);
776 gcc_assert (base
!= NULL_TREE
);
778 if (pbitpos
% BITS_PER_UNIT
!= 0)
780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
781 fprintf (dump_file
, "failed: bit offset alignment.\n");
785 if (TREE_CODE (base
) == MEM_REF
)
787 if (!integer_zerop (TREE_OPERAND (base
, 1)))
789 double_int moff
= mem_ref_offset (base
);
790 tree mofft
= double_int_to_tree (sizetype
, moff
);
794 poffset
= size_binop (PLUS_EXPR
, poffset
, mofft
);
796 base
= TREE_OPERAND (base
, 0);
799 base
= build_fold_addr_expr (base
);
803 if (!simple_iv (loop
, loop_containing_stmt (stmt
), base
, &base_iv
,
804 nest
? true : false))
808 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
809 fprintf (dump_file
, "failed: evolution of base is not"
816 base_iv
.step
= ssize_int (0);
817 base_iv
.no_overflow
= true;
824 base_iv
.step
= ssize_int (0);
825 base_iv
.no_overflow
= true;
830 offset_iv
.base
= ssize_int (0);
831 offset_iv
.step
= ssize_int (0);
837 offset_iv
.base
= poffset
;
838 offset_iv
.step
= ssize_int (0);
840 else if (!simple_iv (loop
, loop_containing_stmt (stmt
),
842 nest
? true : false))
846 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
847 fprintf (dump_file
, "failed: evolution of offset is not"
853 offset_iv
.base
= poffset
;
854 offset_iv
.step
= ssize_int (0);
859 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
860 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
861 init
= size_binop (PLUS_EXPR
, init
, dinit
);
862 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
863 init
= size_binop (PLUS_EXPR
, init
, dinit
);
865 step
= size_binop (PLUS_EXPR
,
866 fold_convert (ssizetype
, base_iv
.step
),
867 fold_convert (ssizetype
, offset_iv
.step
));
869 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
871 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
875 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
877 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
878 fprintf (dump_file
, "success.\n");
883 /* Determines the base object and the list of indices of memory reference
884 DR, analyzed in LOOP and instantiated in loop nest NEST. */
887 dr_analyze_indices (struct data_reference
*dr
, loop_p nest
, loop_p loop
)
889 vec
<tree
> access_fns
= vNULL
;
891 tree base
, off
, access_fn
;
892 basic_block before_loop
;
894 /* If analyzing a basic-block there are no indices to analyze
895 and thus no access functions. */
898 DR_BASE_OBJECT (dr
) = DR_REF (dr
);
899 DR_ACCESS_FNS (dr
).create (0);
904 before_loop
= block_before_loop (nest
);
906 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
907 into a two element array with a constant index. The base is
908 then just the immediate underlying object. */
909 if (TREE_CODE (ref
) == REALPART_EXPR
)
911 ref
= TREE_OPERAND (ref
, 0);
912 access_fns
.safe_push (integer_zero_node
);
914 else if (TREE_CODE (ref
) == IMAGPART_EXPR
)
916 ref
= TREE_OPERAND (ref
, 0);
917 access_fns
.safe_push (integer_one_node
);
920 /* Analyze access functions of dimensions we know to be independent. */
921 while (handled_component_p (ref
))
923 if (TREE_CODE (ref
) == ARRAY_REF
)
925 op
= TREE_OPERAND (ref
, 1);
926 access_fn
= analyze_scalar_evolution (loop
, op
);
927 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
928 access_fns
.safe_push (access_fn
);
930 else if (TREE_CODE (ref
) == COMPONENT_REF
931 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref
, 0))) == RECORD_TYPE
)
933 /* For COMPONENT_REFs of records (but not unions!) use the
934 FIELD_DECL offset as constant access function so we can
935 disambiguate a[i].f1 and a[i].f2. */
936 tree off
= component_ref_field_offset (ref
);
937 off
= size_binop (PLUS_EXPR
,
938 size_binop (MULT_EXPR
,
939 fold_convert (bitsizetype
, off
),
940 bitsize_int (BITS_PER_UNIT
)),
941 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1)));
942 access_fns
.safe_push (off
);
945 /* If we have an unhandled component we could not translate
946 to an access function stop analyzing. We have determined
947 our base object in this case. */
950 ref
= TREE_OPERAND (ref
, 0);
953 /* If the address operand of a MEM_REF base has an evolution in the
954 analyzed nest, add it as an additional independent access-function. */
955 if (TREE_CODE (ref
) == MEM_REF
)
957 op
= TREE_OPERAND (ref
, 0);
958 access_fn
= analyze_scalar_evolution (loop
, op
);
959 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
960 if (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
963 tree memoff
= TREE_OPERAND (ref
, 1);
964 base
= initial_condition (access_fn
);
965 orig_type
= TREE_TYPE (base
);
966 STRIP_USELESS_TYPE_CONVERSION (base
);
967 split_constant_offset (base
, &base
, &off
);
968 /* Fold the MEM_REF offset into the evolutions initial
969 value to make more bases comparable. */
970 if (!integer_zerop (memoff
))
972 off
= size_binop (PLUS_EXPR
, off
,
973 fold_convert (ssizetype
, memoff
));
974 memoff
= build_int_cst (TREE_TYPE (memoff
), 0);
976 /* Adjust the offset so it is a multiple of the access type
977 size and thus we separate bases that can possibly be used
978 to produce partial overlaps (which the access_fn machinery
981 if (TYPE_SIZE_UNIT (TREE_TYPE (ref
))
982 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref
))) == INTEGER_CST
983 && !integer_zerop (TYPE_SIZE_UNIT (TREE_TYPE (ref
))))
984 rem
= tree_to_double_int (off
).mod
985 (tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (ref
))), false,
988 /* If we can't compute the remainder simply force the initial
989 condition to zero. */
990 rem
= tree_to_double_int (off
);
991 off
= double_int_to_tree (ssizetype
, tree_to_double_int (off
) - rem
);
992 memoff
= double_int_to_tree (TREE_TYPE (memoff
), rem
);
993 /* And finally replace the initial condition. */
994 access_fn
= chrec_replace_initial_condition
995 (access_fn
, fold_convert (orig_type
, off
));
996 /* ??? This is still not a suitable base object for
997 dr_may_alias_p - the base object needs to be an
998 access that covers the object as whole. With
999 an evolution in the pointer this cannot be
1001 As a band-aid, mark the access so we can special-case
1002 it in dr_may_alias_p. */
1004 ref
= fold_build2_loc (EXPR_LOCATION (ref
),
1005 MEM_REF
, TREE_TYPE (ref
),
1007 MR_DEPENDENCE_CLIQUE (ref
) = MR_DEPENDENCE_CLIQUE (old
);
1008 MR_DEPENDENCE_BASE (ref
) = MR_DEPENDENCE_BASE (old
);
1009 access_fns
.safe_push (access_fn
);
1012 else if (DECL_P (ref
))
1014 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
1015 ref
= build2 (MEM_REF
, TREE_TYPE (ref
),
1016 build_fold_addr_expr (ref
),
1017 build_int_cst (reference_alias_ptr_type (ref
), 0));
1020 DR_BASE_OBJECT (dr
) = ref
;
1021 DR_ACCESS_FNS (dr
) = access_fns
;
1024 /* Extracts the alias analysis information from the memory reference DR. */
1027 dr_analyze_alias (struct data_reference
*dr
)
1029 tree ref
= DR_REF (dr
);
1030 tree base
= get_base_address (ref
), addr
;
1032 if (INDIRECT_REF_P (base
)
1033 || TREE_CODE (base
) == MEM_REF
)
1035 addr
= TREE_OPERAND (base
, 0);
1036 if (TREE_CODE (addr
) == SSA_NAME
)
1037 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
1041 /* Frees data reference DR. */
1044 free_data_ref (data_reference_p dr
)
1046 DR_ACCESS_FNS (dr
).release ();
1050 /* Analyzes memory reference MEMREF accessed in STMT. The reference
1051 is read if IS_READ is true, write otherwise. Returns the
1052 data_reference description of MEMREF. NEST is the outermost loop
1053 in which the reference should be instantiated, LOOP is the loop in
1054 which the data reference should be analyzed. */
1056 struct data_reference
*
1057 create_data_ref (loop_p nest
, loop_p loop
, tree memref
, gimple stmt
,
1060 struct data_reference
*dr
;
1062 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1064 fprintf (dump_file
, "Creating dr for ");
1065 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1066 fprintf (dump_file
, "\n");
1069 dr
= XCNEW (struct data_reference
);
1070 DR_STMT (dr
) = stmt
;
1071 DR_REF (dr
) = memref
;
1072 DR_IS_READ (dr
) = is_read
;
1074 dr_analyze_innermost (dr
, nest
);
1075 dr_analyze_indices (dr
, nest
, loop
);
1076 dr_analyze_alias (dr
);
1078 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1081 fprintf (dump_file
, "\tbase_address: ");
1082 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
1083 fprintf (dump_file
, "\n\toffset from base address: ");
1084 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
1085 fprintf (dump_file
, "\n\tconstant offset from base address: ");
1086 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
1087 fprintf (dump_file
, "\n\tstep: ");
1088 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
1089 fprintf (dump_file
, "\n\taligned to: ");
1090 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
1091 fprintf (dump_file
, "\n\tbase_object: ");
1092 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
1093 fprintf (dump_file
, "\n");
1094 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
1096 fprintf (dump_file
, "\tAccess function %d: ", i
);
1097 print_generic_stmt (dump_file
, DR_ACCESS_FN (dr
, i
), TDF_SLIM
);
1104 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1107 dr_equal_offsets_p1 (tree offset1
, tree offset2
)
1111 STRIP_NOPS (offset1
);
1112 STRIP_NOPS (offset2
);
1114 if (offset1
== offset2
)
1117 if (TREE_CODE (offset1
) != TREE_CODE (offset2
)
1118 || (!BINARY_CLASS_P (offset1
) && !UNARY_CLASS_P (offset1
)))
1121 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 0),
1122 TREE_OPERAND (offset2
, 0));
1124 if (!res
|| !BINARY_CLASS_P (offset1
))
1127 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 1),
1128 TREE_OPERAND (offset2
, 1));
1133 /* Check if DRA and DRB have equal offsets. */
1135 dr_equal_offsets_p (struct data_reference
*dra
,
1136 struct data_reference
*drb
)
1138 tree offset1
, offset2
;
1140 offset1
= DR_OFFSET (dra
);
1141 offset2
= DR_OFFSET (drb
);
1143 return dr_equal_offsets_p1 (offset1
, offset2
);
1146 /* Returns true if FNA == FNB. */
1149 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
1151 unsigned i
, n
= fna
.length ();
1153 if (n
!= fnb
.length ())
1156 for (i
= 0; i
< n
; i
++)
1157 if (!operand_equal_p (fna
[i
], fnb
[i
], 0))
1163 /* If all the functions in CF are the same, returns one of them,
1164 otherwise returns NULL. */
1167 common_affine_function (conflict_function
*cf
)
1172 if (!CF_NONTRIVIAL_P (cf
))
1173 return affine_fn ();
1177 for (i
= 1; i
< cf
->n
; i
++)
1178 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
1179 return affine_fn ();
1184 /* Returns the base of the affine function FN. */
1187 affine_function_base (affine_fn fn
)
1192 /* Returns true if FN is a constant. */
1195 affine_function_constant_p (affine_fn fn
)
1200 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
1201 if (!integer_zerop (coef
))
1207 /* Returns true if FN is the zero constant function. */
1210 affine_function_zero_p (affine_fn fn
)
1212 return (integer_zerop (affine_function_base (fn
))
1213 && affine_function_constant_p (fn
));
1216 /* Returns a signed integer type with the largest precision from TA
1220 signed_type_for_types (tree ta
, tree tb
)
1222 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
1223 return signed_type_for (ta
);
1225 return signed_type_for (tb
);
1228 /* Applies operation OP on affine functions FNA and FNB, and returns the
1232 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
1238 if (fnb
.length () > fna
.length ())
1250 for (i
= 0; i
< n
; i
++)
1252 tree type
= signed_type_for_types (TREE_TYPE (fna
[i
]),
1253 TREE_TYPE (fnb
[i
]));
1254 ret
.quick_push (fold_build2 (op
, type
, fna
[i
], fnb
[i
]));
1257 for (; fna
.iterate (i
, &coef
); i
++)
1258 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1259 coef
, integer_zero_node
));
1260 for (; fnb
.iterate (i
, &coef
); i
++)
1261 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1262 integer_zero_node
, coef
));
1267 /* Returns the sum of affine functions FNA and FNB. */
1270 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1272 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1275 /* Returns the difference of affine functions FNA and FNB. */
1278 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1280 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1283 /* Frees affine function FN. */
1286 affine_fn_free (affine_fn fn
)
1291 /* Determine for each subscript in the data dependence relation DDR
1295 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1297 conflict_function
*cf_a
, *cf_b
;
1298 affine_fn fn_a
, fn_b
, diff
;
1300 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1304 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1306 struct subscript
*subscript
;
1308 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1309 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1310 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1312 fn_a
= common_affine_function (cf_a
);
1313 fn_b
= common_affine_function (cf_b
);
1314 if (!fn_a
.exists () || !fn_b
.exists ())
1316 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1319 diff
= affine_fn_minus (fn_a
, fn_b
);
1321 if (affine_function_constant_p (diff
))
1322 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1324 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1326 affine_fn_free (diff
);
1331 /* Returns the conflict function for "unknown". */
1333 static conflict_function
*
1334 conflict_fn_not_known (void)
1336 conflict_function
*fn
= XCNEW (conflict_function
);
1342 /* Returns the conflict function for "independent". */
1344 static conflict_function
*
1345 conflict_fn_no_dependence (void)
1347 conflict_function
*fn
= XCNEW (conflict_function
);
1348 fn
->n
= NO_DEPENDENCE
;
1353 /* Returns true if the address of OBJ is invariant in LOOP. */
1356 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1358 while (handled_component_p (obj
))
1360 if (TREE_CODE (obj
) == ARRAY_REF
)
1362 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1363 need to check the stride and the lower bound of the reference. */
1364 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1366 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1370 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1372 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1376 obj
= TREE_OPERAND (obj
, 0);
1379 if (!INDIRECT_REF_P (obj
)
1380 && TREE_CODE (obj
) != MEM_REF
)
1383 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1387 /* Returns false if we can prove that data references A and B do not alias,
1388 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1392 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
,
1395 tree addr_a
= DR_BASE_OBJECT (a
);
1396 tree addr_b
= DR_BASE_OBJECT (b
);
1398 /* If we are not processing a loop nest but scalar code we
1399 do not need to care about possible cross-iteration dependences
1400 and thus can process the full original reference. Do so,
1401 similar to how loop invariant motion applies extra offset-based
1405 aff_tree off1
, off2
;
1406 double_int size1
, size2
;
1407 get_inner_reference_aff (DR_REF (a
), &off1
, &size1
);
1408 get_inner_reference_aff (DR_REF (b
), &off2
, &size2
);
1409 aff_combination_scale (&off1
, double_int_minus_one
);
1410 aff_combination_add (&off2
, &off1
);
1411 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1415 if ((TREE_CODE (addr_a
) == MEM_REF
|| TREE_CODE (addr_a
) == TARGET_MEM_REF
)
1416 && (TREE_CODE (addr_b
) == MEM_REF
|| TREE_CODE (addr_b
) == TARGET_MEM_REF
)
1417 && MR_DEPENDENCE_CLIQUE (addr_a
) == MR_DEPENDENCE_CLIQUE (addr_b
)
1418 && MR_DEPENDENCE_BASE (addr_a
) != MR_DEPENDENCE_BASE (addr_b
))
1421 /* If we had an evolution in a pointer-based MEM_REF BASE_OBJECT we
1422 do not know the size of the base-object. So we cannot do any
1423 offset/overlap based analysis but have to rely on points-to
1424 information only. */
1425 if (TREE_CODE (addr_a
) == MEM_REF
1426 && TREE_CODE (TREE_OPERAND (addr_a
, 0)) == SSA_NAME
)
1428 /* For true dependences we can apply TBAA. */
1429 if (flag_strict_aliasing
1430 && DR_IS_WRITE (a
) && DR_IS_READ (b
)
1431 && !alias_sets_conflict_p (get_alias_set (DR_REF (a
)),
1432 get_alias_set (DR_REF (b
))))
1434 if (TREE_CODE (addr_b
) == MEM_REF
)
1435 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1436 TREE_OPERAND (addr_b
, 0));
1438 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1439 build_fold_addr_expr (addr_b
));
1441 else if (TREE_CODE (addr_b
) == MEM_REF
1442 && TREE_CODE (TREE_OPERAND (addr_b
, 0)) == SSA_NAME
)
1444 /* For true dependences we can apply TBAA. */
1445 if (flag_strict_aliasing
1446 && DR_IS_WRITE (a
) && DR_IS_READ (b
)
1447 && !alias_sets_conflict_p (get_alias_set (DR_REF (a
)),
1448 get_alias_set (DR_REF (b
))))
1450 if (TREE_CODE (addr_a
) == MEM_REF
)
1451 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1452 TREE_OPERAND (addr_b
, 0));
1454 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a
),
1455 TREE_OPERAND (addr_b
, 0));
1458 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
1459 that is being subsetted in the loop nest. */
1460 if (DR_IS_WRITE (a
) && DR_IS_WRITE (b
))
1461 return refs_output_dependent_p (addr_a
, addr_b
);
1462 else if (DR_IS_READ (a
) && DR_IS_WRITE (b
))
1463 return refs_anti_dependent_p (addr_a
, addr_b
);
1464 return refs_may_alias_p (addr_a
, addr_b
);
1467 /* Initialize a data dependence relation between data accesses A and
1468 B. NB_LOOPS is the number of loops surrounding the references: the
1469 size of the classic distance/direction vectors. */
1471 struct data_dependence_relation
*
1472 initialize_data_dependence_relation (struct data_reference
*a
,
1473 struct data_reference
*b
,
1474 vec
<loop_p
> loop_nest
)
1476 struct data_dependence_relation
*res
;
1479 res
= XNEW (struct data_dependence_relation
);
1482 DDR_LOOP_NEST (res
).create (0);
1483 DDR_REVERSED_P (res
) = false;
1484 DDR_SUBSCRIPTS (res
).create (0);
1485 DDR_DIR_VECTS (res
).create (0);
1486 DDR_DIST_VECTS (res
).create (0);
1488 if (a
== NULL
|| b
== NULL
)
1490 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1494 /* If the data references do not alias, then they are independent. */
1495 if (!dr_may_alias_p (a
, b
, loop_nest
.exists ()))
1497 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1501 /* The case where the references are exactly the same. */
1502 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1504 if (loop_nest
.exists ()
1505 && !object_address_invariant_in_loop_p (loop_nest
[0],
1506 DR_BASE_OBJECT (a
)))
1508 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1511 DDR_AFFINE_P (res
) = true;
1512 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1513 DDR_SUBSCRIPTS (res
).create (DR_NUM_DIMENSIONS (a
));
1514 DDR_LOOP_NEST (res
) = loop_nest
;
1515 DDR_INNER_LOOP (res
) = 0;
1516 DDR_SELF_REFERENCE (res
) = true;
1517 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1519 struct subscript
*subscript
;
1521 subscript
= XNEW (struct subscript
);
1522 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1523 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1524 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1525 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1526 DDR_SUBSCRIPTS (res
).safe_push (subscript
);
1531 /* If the references do not access the same object, we do not know
1532 whether they alias or not. */
1533 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1535 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1539 /* If the base of the object is not invariant in the loop nest, we cannot
1540 analyze it. TODO -- in fact, it would suffice to record that there may
1541 be arbitrary dependences in the loops where the base object varies. */
1542 if (loop_nest
.exists ()
1543 && !object_address_invariant_in_loop_p (loop_nest
[0],
1544 DR_BASE_OBJECT (a
)))
1546 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1550 /* If the number of dimensions of the access to not agree we can have
1551 a pointer access to a component of the array element type and an
1552 array access while the base-objects are still the same. Punt. */
1553 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
1555 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1559 DDR_AFFINE_P (res
) = true;
1560 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1561 DDR_SUBSCRIPTS (res
).create (DR_NUM_DIMENSIONS (a
));
1562 DDR_LOOP_NEST (res
) = loop_nest
;
1563 DDR_INNER_LOOP (res
) = 0;
1564 DDR_SELF_REFERENCE (res
) = false;
1566 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1568 struct subscript
*subscript
;
1570 subscript
= XNEW (struct subscript
);
1571 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1572 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1573 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1574 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1575 DDR_SUBSCRIPTS (res
).safe_push (subscript
);
1581 /* Frees memory used by the conflict function F. */
1584 free_conflict_function (conflict_function
*f
)
1588 if (CF_NONTRIVIAL_P (f
))
1590 for (i
= 0; i
< f
->n
; i
++)
1591 affine_fn_free (f
->fns
[i
]);
1596 /* Frees memory used by SUBSCRIPTS. */
1599 free_subscripts (vec
<subscript_p
> subscripts
)
1604 FOR_EACH_VEC_ELT (subscripts
, i
, s
)
1606 free_conflict_function (s
->conflicting_iterations_in_a
);
1607 free_conflict_function (s
->conflicting_iterations_in_b
);
1610 subscripts
.release ();
1613 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1617 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1620 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1621 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1622 DDR_SUBSCRIPTS (ddr
).create (0);
1625 /* The dependence relation DDR cannot be represented by a distance
1629 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1632 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1634 DDR_AFFINE_P (ddr
) = false;
1639 /* This section contains the classic Banerjee tests. */
1641 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1642 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1645 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1647 return (evolution_function_is_constant_p (chrec_a
)
1648 && evolution_function_is_constant_p (chrec_b
));
1651 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1652 variable, i.e., if the SIV (Single Index Variable) test is true. */
1655 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1657 if ((evolution_function_is_constant_p (chrec_a
)
1658 && evolution_function_is_univariate_p (chrec_b
))
1659 || (evolution_function_is_constant_p (chrec_b
)
1660 && evolution_function_is_univariate_p (chrec_a
)))
1663 if (evolution_function_is_univariate_p (chrec_a
)
1664 && evolution_function_is_univariate_p (chrec_b
))
1666 switch (TREE_CODE (chrec_a
))
1668 case POLYNOMIAL_CHREC
:
1669 switch (TREE_CODE (chrec_b
))
1671 case POLYNOMIAL_CHREC
:
1672 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1687 /* Creates a conflict function with N dimensions. The affine functions
1688 in each dimension follow. */
1690 static conflict_function
*
1691 conflict_fn (unsigned n
, ...)
1694 conflict_function
*ret
= XCNEW (conflict_function
);
1697 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1701 for (i
= 0; i
< n
; i
++)
1702 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1708 /* Returns constant affine function with value CST. */
1711 affine_fn_cst (tree cst
)
1715 fn
.quick_push (cst
);
1719 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1722 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1725 fn
.create (dim
+ 1);
1728 gcc_assert (dim
> 0);
1729 fn
.quick_push (cst
);
1730 for (i
= 1; i
< dim
; i
++)
1731 fn
.quick_push (integer_zero_node
);
1732 fn
.quick_push (coef
);
1736 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1737 *OVERLAPS_B are initialized to the functions that describe the
1738 relation between the elements accessed twice by CHREC_A and
1739 CHREC_B. For k >= 0, the following property is verified:
1741 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1744 analyze_ziv_subscript (tree chrec_a
,
1746 conflict_function
**overlaps_a
,
1747 conflict_function
**overlaps_b
,
1748 tree
*last_conflicts
)
1750 tree type
, difference
;
1751 dependence_stats
.num_ziv
++;
1753 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1754 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1756 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1757 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1758 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1759 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1761 switch (TREE_CODE (difference
))
1764 if (integer_zerop (difference
))
1766 /* The difference is equal to zero: the accessed index
1767 overlaps for each iteration in the loop. */
1768 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1769 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1770 *last_conflicts
= chrec_dont_know
;
1771 dependence_stats
.num_ziv_dependent
++;
1775 /* The accesses do not overlap. */
1776 *overlaps_a
= conflict_fn_no_dependence ();
1777 *overlaps_b
= conflict_fn_no_dependence ();
1778 *last_conflicts
= integer_zero_node
;
1779 dependence_stats
.num_ziv_independent
++;
1784 /* We're not sure whether the indexes overlap. For the moment,
1785 conservatively answer "don't know". */
1786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1787 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1789 *overlaps_a
= conflict_fn_not_known ();
1790 *overlaps_b
= conflict_fn_not_known ();
1791 *last_conflicts
= chrec_dont_know
;
1792 dependence_stats
.num_ziv_unimplemented
++;
1796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1797 fprintf (dump_file
, ")\n");
1800 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1801 and only if it fits to the int type. If this is not the case, or the
1802 bound on the number of iterations of LOOP could not be derived, returns
1806 max_stmt_executions_tree (struct loop
*loop
)
1810 if (!max_stmt_executions (loop
, &nit
))
1811 return chrec_dont_know
;
1813 if (!double_int_fits_to_tree_p (unsigned_type_node
, nit
))
1814 return chrec_dont_know
;
1816 return double_int_to_tree (unsigned_type_node
, nit
);
1819 /* Determine whether the CHREC is always positive/negative. If the expression
1820 cannot be statically analyzed, return false, otherwise set the answer into
1824 chrec_is_positive (tree chrec
, bool *value
)
1826 bool value0
, value1
, value2
;
1827 tree end_value
, nb_iter
;
1829 switch (TREE_CODE (chrec
))
1831 case POLYNOMIAL_CHREC
:
1832 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
1833 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
1836 /* FIXME -- overflows. */
1837 if (value0
== value1
)
1843 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
1844 and the proof consists in showing that the sign never
1845 changes during the execution of the loop, from 0 to
1846 loop->nb_iterations. */
1847 if (!evolution_function_is_affine_p (chrec
))
1850 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
1851 if (chrec_contains_undetermined (nb_iter
))
1855 /* TODO -- If the test is after the exit, we may decrease the number of
1856 iterations by one. */
1858 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
1861 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
1863 if (!chrec_is_positive (end_value
, &value2
))
1867 return value0
== value1
;
1870 switch (tree_int_cst_sgn (chrec
))
1889 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1890 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1891 *OVERLAPS_B are initialized to the functions that describe the
1892 relation between the elements accessed twice by CHREC_A and
1893 CHREC_B. For k >= 0, the following property is verified:
1895 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1898 analyze_siv_subscript_cst_affine (tree chrec_a
,
1900 conflict_function
**overlaps_a
,
1901 conflict_function
**overlaps_b
,
1902 tree
*last_conflicts
)
1904 bool value0
, value1
, value2
;
1905 tree type
, difference
, tmp
;
1907 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1908 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1909 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1910 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1912 /* Special case overlap in the first iteration. */
1913 if (integer_zerop (difference
))
1915 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1916 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1917 *last_conflicts
= integer_one_node
;
1921 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1923 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1924 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1926 dependence_stats
.num_siv_unimplemented
++;
1927 *overlaps_a
= conflict_fn_not_known ();
1928 *overlaps_b
= conflict_fn_not_known ();
1929 *last_conflicts
= chrec_dont_know
;
1934 if (value0
== false)
1936 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1938 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1939 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1941 *overlaps_a
= conflict_fn_not_known ();
1942 *overlaps_b
= conflict_fn_not_known ();
1943 *last_conflicts
= chrec_dont_know
;
1944 dependence_stats
.num_siv_unimplemented
++;
1953 chrec_b = {10, +, 1}
1956 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1958 HOST_WIDE_INT numiter
;
1959 struct loop
*loop
= get_chrec_loop (chrec_b
);
1961 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1962 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1963 fold_build1 (ABS_EXPR
, type
, difference
),
1964 CHREC_RIGHT (chrec_b
));
1965 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1966 *last_conflicts
= integer_one_node
;
1969 /* Perform weak-zero siv test to see if overlap is
1970 outside the loop bounds. */
1971 numiter
= max_stmt_executions_int (loop
);
1974 && compare_tree_int (tmp
, numiter
) > 0)
1976 free_conflict_function (*overlaps_a
);
1977 free_conflict_function (*overlaps_b
);
1978 *overlaps_a
= conflict_fn_no_dependence ();
1979 *overlaps_b
= conflict_fn_no_dependence ();
1980 *last_conflicts
= integer_zero_node
;
1981 dependence_stats
.num_siv_independent
++;
1984 dependence_stats
.num_siv_dependent
++;
1988 /* When the step does not divide the difference, there are
1992 *overlaps_a
= conflict_fn_no_dependence ();
1993 *overlaps_b
= conflict_fn_no_dependence ();
1994 *last_conflicts
= integer_zero_node
;
1995 dependence_stats
.num_siv_independent
++;
2004 chrec_b = {10, +, -1}
2006 In this case, chrec_a will not overlap with chrec_b. */
2007 *overlaps_a
= conflict_fn_no_dependence ();
2008 *overlaps_b
= conflict_fn_no_dependence ();
2009 *last_conflicts
= integer_zero_node
;
2010 dependence_stats
.num_siv_independent
++;
2017 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
2019 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2020 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
2022 *overlaps_a
= conflict_fn_not_known ();
2023 *overlaps_b
= conflict_fn_not_known ();
2024 *last_conflicts
= chrec_dont_know
;
2025 dependence_stats
.num_siv_unimplemented
++;
2030 if (value2
== false)
2034 chrec_b = {10, +, -1}
2036 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
2038 HOST_WIDE_INT numiter
;
2039 struct loop
*loop
= get_chrec_loop (chrec_b
);
2041 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2042 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
2043 CHREC_RIGHT (chrec_b
));
2044 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
2045 *last_conflicts
= integer_one_node
;
2047 /* Perform weak-zero siv test to see if overlap is
2048 outside the loop bounds. */
2049 numiter
= max_stmt_executions_int (loop
);
2052 && compare_tree_int (tmp
, numiter
) > 0)
2054 free_conflict_function (*overlaps_a
);
2055 free_conflict_function (*overlaps_b
);
2056 *overlaps_a
= conflict_fn_no_dependence ();
2057 *overlaps_b
= conflict_fn_no_dependence ();
2058 *last_conflicts
= integer_zero_node
;
2059 dependence_stats
.num_siv_independent
++;
2062 dependence_stats
.num_siv_dependent
++;
2066 /* When the step does not divide the difference, there
2070 *overlaps_a
= conflict_fn_no_dependence ();
2071 *overlaps_b
= conflict_fn_no_dependence ();
2072 *last_conflicts
= integer_zero_node
;
2073 dependence_stats
.num_siv_independent
++;
2083 In this case, chrec_a will not overlap with chrec_b. */
2084 *overlaps_a
= conflict_fn_no_dependence ();
2085 *overlaps_b
= conflict_fn_no_dependence ();
2086 *last_conflicts
= integer_zero_node
;
2087 dependence_stats
.num_siv_independent
++;
2095 /* Helper recursive function for initializing the matrix A. Returns
2096 the initial value of CHREC. */
2099 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
2103 switch (TREE_CODE (chrec
))
2105 case POLYNOMIAL_CHREC
:
2106 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
2108 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
2109 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
2115 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2116 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
2118 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
2123 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2124 return chrec_convert (chrec_type (chrec
), op
, NULL
);
2129 /* Handle ~X as -1 - X. */
2130 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2131 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
2132 build_int_cst (TREE_TYPE (chrec
), -1), op
);
2144 #define FLOOR_DIV(x,y) ((x) / (y))
2146 /* Solves the special case of the Diophantine equation:
2147 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2149 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2150 number of iterations that loops X and Y run. The overlaps will be
2151 constructed as evolutions in dimension DIM. */
2154 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
2155 affine_fn
*overlaps_a
,
2156 affine_fn
*overlaps_b
,
2157 tree
*last_conflicts
, int dim
)
2159 if (((step_a
> 0 && step_b
> 0)
2160 || (step_a
< 0 && step_b
< 0)))
2162 int step_overlaps_a
, step_overlaps_b
;
2163 int gcd_steps_a_b
, last_conflict
, tau2
;
2165 gcd_steps_a_b
= gcd (step_a
, step_b
);
2166 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2167 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2171 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2172 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2173 last_conflict
= tau2
;
2174 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2177 *last_conflicts
= chrec_dont_know
;
2179 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
2180 build_int_cst (NULL_TREE
,
2182 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
2183 build_int_cst (NULL_TREE
,
2189 *overlaps_a
= affine_fn_cst (integer_zero_node
);
2190 *overlaps_b
= affine_fn_cst (integer_zero_node
);
2191 *last_conflicts
= integer_zero_node
;
2195 /* Solves the special case of a Diophantine equation where CHREC_A is
2196 an affine bivariate function, and CHREC_B is an affine univariate
2197 function. For example,
2199 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2201 has the following overlapping functions:
2203 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2204 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2205 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2207 FORNOW: This is a specialized implementation for a case occurring in
2208 a common benchmark. Implement the general algorithm. */
2211 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2212 conflict_function
**overlaps_a
,
2213 conflict_function
**overlaps_b
,
2214 tree
*last_conflicts
)
2216 bool xz_p
, yz_p
, xyz_p
;
2217 int step_x
, step_y
, step_z
;
2218 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
2219 affine_fn overlaps_a_xz
, overlaps_b_xz
;
2220 affine_fn overlaps_a_yz
, overlaps_b_yz
;
2221 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
2222 affine_fn ova1
, ova2
, ovb
;
2223 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
2225 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2226 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2227 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2229 niter_x
= max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a
)));
2230 niter_y
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
2231 niter_z
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
2233 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2236 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2238 *overlaps_a
= conflict_fn_not_known ();
2239 *overlaps_b
= conflict_fn_not_known ();
2240 *last_conflicts
= chrec_dont_know
;
2244 niter
= MIN (niter_x
, niter_z
);
2245 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2248 &last_conflicts_xz
, 1);
2249 niter
= MIN (niter_y
, niter_z
);
2250 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2253 &last_conflicts_yz
, 2);
2254 niter
= MIN (niter_x
, niter_z
);
2255 niter
= MIN (niter_y
, niter
);
2256 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2259 &last_conflicts_xyz
, 3);
2261 xz_p
= !integer_zerop (last_conflicts_xz
);
2262 yz_p
= !integer_zerop (last_conflicts_yz
);
2263 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2265 if (xz_p
|| yz_p
|| xyz_p
)
2267 ova1
= affine_fn_cst (integer_zero_node
);
2268 ova2
= affine_fn_cst (integer_zero_node
);
2269 ovb
= affine_fn_cst (integer_zero_node
);
2272 affine_fn t0
= ova1
;
2275 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2276 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2277 affine_fn_free (t0
);
2278 affine_fn_free (t2
);
2279 *last_conflicts
= last_conflicts_xz
;
2283 affine_fn t0
= ova2
;
2286 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2287 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2288 affine_fn_free (t0
);
2289 affine_fn_free (t2
);
2290 *last_conflicts
= last_conflicts_yz
;
2294 affine_fn t0
= ova1
;
2295 affine_fn t2
= ova2
;
2298 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2299 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2300 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2301 affine_fn_free (t0
);
2302 affine_fn_free (t2
);
2303 affine_fn_free (t4
);
2304 *last_conflicts
= last_conflicts_xyz
;
2306 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2307 *overlaps_b
= conflict_fn (1, ovb
);
2311 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2312 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2313 *last_conflicts
= integer_zero_node
;
2316 affine_fn_free (overlaps_a_xz
);
2317 affine_fn_free (overlaps_b_xz
);
2318 affine_fn_free (overlaps_a_yz
);
2319 affine_fn_free (overlaps_b_yz
);
2320 affine_fn_free (overlaps_a_xyz
);
2321 affine_fn_free (overlaps_b_xyz
);
2324 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2327 lambda_vector_copy (lambda_vector vec1
, lambda_vector vec2
,
2330 memcpy (vec2
, vec1
, size
* sizeof (*vec1
));
2333 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2336 lambda_matrix_copy (lambda_matrix mat1
, lambda_matrix mat2
,
2341 for (i
= 0; i
< m
; i
++)
2342 lambda_vector_copy (mat1
[i
], mat2
[i
], n
);
2345 /* Store the N x N identity matrix in MAT. */
2348 lambda_matrix_id (lambda_matrix mat
, int size
)
2352 for (i
= 0; i
< size
; i
++)
2353 for (j
= 0; j
< size
; j
++)
2354 mat
[i
][j
] = (i
== j
) ? 1 : 0;
2357 /* Return the first nonzero element of vector VEC1 between START and N.
2358 We must have START <= N. Returns N if VEC1 is the zero vector. */
2361 lambda_vector_first_nz (lambda_vector vec1
, int n
, int start
)
2364 while (j
< n
&& vec1
[j
] == 0)
2369 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2370 R2 = R2 + CONST1 * R1. */
2373 lambda_matrix_row_add (lambda_matrix mat
, int n
, int r1
, int r2
, int const1
)
2380 for (i
= 0; i
< n
; i
++)
2381 mat
[r2
][i
] += const1
* mat
[r1
][i
];
2384 /* Swap rows R1 and R2 in matrix MAT. */
2387 lambda_matrix_row_exchange (lambda_matrix mat
, int r1
, int r2
)
2396 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2397 and store the result in VEC2. */
2400 lambda_vector_mult_const (lambda_vector vec1
, lambda_vector vec2
,
2401 int size
, int const1
)
2406 lambda_vector_clear (vec2
, size
);
2408 for (i
= 0; i
< size
; i
++)
2409 vec2
[i
] = const1
* vec1
[i
];
2412 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2415 lambda_vector_negate (lambda_vector vec1
, lambda_vector vec2
,
2418 lambda_vector_mult_const (vec1
, vec2
, size
, -1);
2421 /* Negate row R1 of matrix MAT which has N columns. */
2424 lambda_matrix_row_negate (lambda_matrix mat
, int n
, int r1
)
2426 lambda_vector_negate (mat
[r1
], mat
[r1
], n
);
2429 /* Return true if two vectors are equal. */
2432 lambda_vector_equal (lambda_vector vec1
, lambda_vector vec2
, int size
)
2435 for (i
= 0; i
< size
; i
++)
2436 if (vec1
[i
] != vec2
[i
])
2441 /* Given an M x N integer matrix A, this function determines an M x
2442 M unimodular matrix U, and an M x N echelon matrix S such that
2443 "U.A = S". This decomposition is also known as "right Hermite".
2445 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2446 Restructuring Compilers" Utpal Banerjee. */
2449 lambda_matrix_right_hermite (lambda_matrix A
, int m
, int n
,
2450 lambda_matrix S
, lambda_matrix U
)
2454 lambda_matrix_copy (A
, S
, m
, n
);
2455 lambda_matrix_id (U
, m
);
2457 for (j
= 0; j
< n
; j
++)
2459 if (lambda_vector_first_nz (S
[j
], m
, i0
) < m
)
2462 for (i
= m
- 1; i
>= i0
; i
--)
2464 while (S
[i
][j
] != 0)
2466 int sigma
, factor
, a
, b
;
2470 sigma
= (a
* b
< 0) ? -1: 1;
2473 factor
= sigma
* (a
/ b
);
2475 lambda_matrix_row_add (S
, n
, i
, i
-1, -factor
);
2476 lambda_matrix_row_exchange (S
, i
, i
-1);
2478 lambda_matrix_row_add (U
, m
, i
, i
-1, -factor
);
2479 lambda_matrix_row_exchange (U
, i
, i
-1);
2486 /* Determines the overlapping elements due to accesses CHREC_A and
2487 CHREC_B, that are affine functions. This function cannot handle
2488 symbolic evolution functions, ie. when initial conditions are
2489 parameters, because it uses lambda matrices of integers. */
2492 analyze_subscript_affine_affine (tree chrec_a
,
2494 conflict_function
**overlaps_a
,
2495 conflict_function
**overlaps_b
,
2496 tree
*last_conflicts
)
2498 unsigned nb_vars_a
, nb_vars_b
, dim
;
2499 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2500 lambda_matrix A
, U
, S
;
2501 struct obstack scratch_obstack
;
2503 if (eq_evolutions_p (chrec_a
, chrec_b
))
2505 /* The accessed index overlaps for each iteration in the
2507 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2508 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2509 *last_conflicts
= chrec_dont_know
;
2512 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2513 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2515 /* For determining the initial intersection, we have to solve a
2516 Diophantine equation. This is the most time consuming part.
2518 For answering to the question: "Is there a dependence?" we have
2519 to prove that there exists a solution to the Diophantine
2520 equation, and that the solution is in the iteration domain,
2521 i.e. the solution is positive or zero, and that the solution
2522 happens before the upper bound loop.nb_iterations. Otherwise
2523 there is no dependence. This function outputs a description of
2524 the iterations that hold the intersections. */
2526 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2527 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2529 gcc_obstack_init (&scratch_obstack
);
2531 dim
= nb_vars_a
+ nb_vars_b
;
2532 U
= lambda_matrix_new (dim
, dim
, &scratch_obstack
);
2533 A
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2534 S
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2536 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2537 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2538 gamma
= init_b
- init_a
;
2540 /* Don't do all the hard work of solving the Diophantine equation
2541 when we already know the solution: for example,
2544 | gamma = 3 - 3 = 0.
2545 Then the first overlap occurs during the first iterations:
2546 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2550 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2552 HOST_WIDE_INT step_a
, step_b
;
2553 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2556 niter_a
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
2557 niter_b
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
2558 niter
= MIN (niter_a
, niter_b
);
2559 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2560 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2562 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2565 *overlaps_a
= conflict_fn (1, ova
);
2566 *overlaps_b
= conflict_fn (1, ovb
);
2569 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2570 compute_overlap_steps_for_affine_1_2
2571 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2573 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2574 compute_overlap_steps_for_affine_1_2
2575 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2580 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2581 *overlaps_a
= conflict_fn_not_known ();
2582 *overlaps_b
= conflict_fn_not_known ();
2583 *last_conflicts
= chrec_dont_know
;
2585 goto end_analyze_subs_aa
;
2589 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2594 lambda_matrix_row_negate (U
, dim
, 0);
2596 gcd_alpha_beta
= S
[0][0];
2598 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2599 but that is a quite strange case. Instead of ICEing, answer
2601 if (gcd_alpha_beta
== 0)
2603 *overlaps_a
= conflict_fn_not_known ();
2604 *overlaps_b
= conflict_fn_not_known ();
2605 *last_conflicts
= chrec_dont_know
;
2606 goto end_analyze_subs_aa
;
2609 /* The classic "gcd-test". */
2610 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2612 /* The "gcd-test" has determined that there is no integer
2613 solution, i.e. there is no dependence. */
2614 *overlaps_a
= conflict_fn_no_dependence ();
2615 *overlaps_b
= conflict_fn_no_dependence ();
2616 *last_conflicts
= integer_zero_node
;
2619 /* Both access functions are univariate. This includes SIV and MIV cases. */
2620 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2622 /* Both functions should have the same evolution sign. */
2623 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2624 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2626 /* The solutions are given by:
2628 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2631 For a given integer t. Using the following variables,
2633 | i0 = u11 * gamma / gcd_alpha_beta
2634 | j0 = u12 * gamma / gcd_alpha_beta
2641 | y0 = j0 + j1 * t. */
2642 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2644 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2645 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2649 if ((i1
== 0 && i0
< 0)
2650 || (j1
== 0 && j0
< 0))
2652 /* There is no solution.
2653 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2654 falls in here, but for the moment we don't look at the
2655 upper bound of the iteration domain. */
2656 *overlaps_a
= conflict_fn_no_dependence ();
2657 *overlaps_b
= conflict_fn_no_dependence ();
2658 *last_conflicts
= integer_zero_node
;
2659 goto end_analyze_subs_aa
;
2662 if (i1
> 0 && j1
> 0)
2664 HOST_WIDE_INT niter_a
2665 = max_stmt_executions_int (get_chrec_loop (chrec_a
));
2666 HOST_WIDE_INT niter_b
2667 = max_stmt_executions_int (get_chrec_loop (chrec_b
));
2668 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2670 /* (X0, Y0) is a solution of the Diophantine equation:
2671 "chrec_a (X0) = chrec_b (Y0)". */
2672 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2674 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2675 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2677 /* (X1, Y1) is the smallest positive solution of the eq
2678 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2679 first conflict occurs. */
2680 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2681 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2682 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2686 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2687 FLOOR_DIV (niter
- j0
, j1
));
2688 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2690 /* If the overlap occurs outside of the bounds of the
2691 loop, there is no dependence. */
2692 if (x1
>= niter
|| y1
>= niter
)
2694 *overlaps_a
= conflict_fn_no_dependence ();
2695 *overlaps_b
= conflict_fn_no_dependence ();
2696 *last_conflicts
= integer_zero_node
;
2697 goto end_analyze_subs_aa
;
2700 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2703 *last_conflicts
= chrec_dont_know
;
2707 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2709 build_int_cst (NULL_TREE
, i1
)));
2712 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2714 build_int_cst (NULL_TREE
, j1
)));
2718 /* FIXME: For the moment, the upper bound of the
2719 iteration domain for i and j is not checked. */
2720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2721 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2722 *overlaps_a
= conflict_fn_not_known ();
2723 *overlaps_b
= conflict_fn_not_known ();
2724 *last_conflicts
= chrec_dont_know
;
2729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2730 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2731 *overlaps_a
= conflict_fn_not_known ();
2732 *overlaps_b
= conflict_fn_not_known ();
2733 *last_conflicts
= chrec_dont_know
;
2738 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2739 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2740 *overlaps_a
= conflict_fn_not_known ();
2741 *overlaps_b
= conflict_fn_not_known ();
2742 *last_conflicts
= chrec_dont_know
;
2745 end_analyze_subs_aa
:
2746 obstack_free (&scratch_obstack
, NULL
);
2747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2749 fprintf (dump_file
, " (overlaps_a = ");
2750 dump_conflict_function (dump_file
, *overlaps_a
);
2751 fprintf (dump_file
, ")\n (overlaps_b = ");
2752 dump_conflict_function (dump_file
, *overlaps_b
);
2753 fprintf (dump_file
, "))\n");
2757 /* Returns true when analyze_subscript_affine_affine can be used for
2758 determining the dependence relation between chrec_a and chrec_b,
2759 that contain symbols. This function modifies chrec_a and chrec_b
2760 such that the analysis result is the same, and such that they don't
2761 contain symbols, and then can safely be passed to the analyzer.
2763 Example: The analysis of the following tuples of evolutions produce
2764 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2767 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2768 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2772 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2774 tree diff
, type
, left_a
, left_b
, right_b
;
2776 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2777 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2778 /* FIXME: For the moment not handled. Might be refined later. */
2781 type
= chrec_type (*chrec_a
);
2782 left_a
= CHREC_LEFT (*chrec_a
);
2783 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2784 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2786 if (!evolution_function_is_constant_p (diff
))
2789 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2790 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2792 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2793 diff
, CHREC_RIGHT (*chrec_a
));
2794 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2795 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2796 build_int_cst (type
, 0),
2801 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2802 *OVERLAPS_B are initialized to the functions that describe the
2803 relation between the elements accessed twice by CHREC_A and
2804 CHREC_B. For k >= 0, the following property is verified:
2806 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2809 analyze_siv_subscript (tree chrec_a
,
2811 conflict_function
**overlaps_a
,
2812 conflict_function
**overlaps_b
,
2813 tree
*last_conflicts
,
2816 dependence_stats
.num_siv
++;
2818 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2819 fprintf (dump_file
, "(analyze_siv_subscript \n");
2821 if (evolution_function_is_constant_p (chrec_a
)
2822 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2823 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2824 overlaps_a
, overlaps_b
, last_conflicts
);
2826 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2827 && evolution_function_is_constant_p (chrec_b
))
2828 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2829 overlaps_b
, overlaps_a
, last_conflicts
);
2831 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2832 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2834 if (!chrec_contains_symbols (chrec_a
)
2835 && !chrec_contains_symbols (chrec_b
))
2837 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2838 overlaps_a
, overlaps_b
,
2841 if (CF_NOT_KNOWN_P (*overlaps_a
)
2842 || CF_NOT_KNOWN_P (*overlaps_b
))
2843 dependence_stats
.num_siv_unimplemented
++;
2844 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2845 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2846 dependence_stats
.num_siv_independent
++;
2848 dependence_stats
.num_siv_dependent
++;
2850 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2853 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2854 overlaps_a
, overlaps_b
,
2857 if (CF_NOT_KNOWN_P (*overlaps_a
)
2858 || CF_NOT_KNOWN_P (*overlaps_b
))
2859 dependence_stats
.num_siv_unimplemented
++;
2860 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2861 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2862 dependence_stats
.num_siv_independent
++;
2864 dependence_stats
.num_siv_dependent
++;
2867 goto siv_subscript_dontknow
;
2872 siv_subscript_dontknow
:;
2873 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2874 fprintf (dump_file
, " siv test failed: unimplemented");
2875 *overlaps_a
= conflict_fn_not_known ();
2876 *overlaps_b
= conflict_fn_not_known ();
2877 *last_conflicts
= chrec_dont_know
;
2878 dependence_stats
.num_siv_unimplemented
++;
2881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2882 fprintf (dump_file
, ")\n");
2885 /* Returns false if we can prove that the greatest common divisor of the steps
2886 of CHREC does not divide CST, false otherwise. */
2889 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2891 HOST_WIDE_INT cd
= 0, val
;
2894 if (!tree_fits_shwi_p (cst
))
2896 val
= tree_to_shwi (cst
);
2898 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2900 step
= CHREC_RIGHT (chrec
);
2901 if (!tree_fits_shwi_p (step
))
2903 cd
= gcd (cd
, tree_to_shwi (step
));
2904 chrec
= CHREC_LEFT (chrec
);
2907 return val
% cd
== 0;
2910 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2911 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2912 functions that describe the relation between the elements accessed
2913 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2916 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2919 analyze_miv_subscript (tree chrec_a
,
2921 conflict_function
**overlaps_a
,
2922 conflict_function
**overlaps_b
,
2923 tree
*last_conflicts
,
2924 struct loop
*loop_nest
)
2926 tree type
, difference
;
2928 dependence_stats
.num_miv
++;
2929 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2930 fprintf (dump_file
, "(analyze_miv_subscript \n");
2932 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2933 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2934 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2935 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2937 if (eq_evolutions_p (chrec_a
, chrec_b
))
2939 /* Access functions are the same: all the elements are accessed
2940 in the same order. */
2941 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2942 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2943 *last_conflicts
= max_stmt_executions_tree (get_chrec_loop (chrec_a
));
2944 dependence_stats
.num_miv_dependent
++;
2947 else if (evolution_function_is_constant_p (difference
)
2948 /* For the moment, the following is verified:
2949 evolution_function_is_affine_multivariate_p (chrec_a,
2951 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2953 /* testsuite/.../ssa-chrec-33.c
2954 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2956 The difference is 1, and all the evolution steps are multiples
2957 of 2, consequently there are no overlapping elements. */
2958 *overlaps_a
= conflict_fn_no_dependence ();
2959 *overlaps_b
= conflict_fn_no_dependence ();
2960 *last_conflicts
= integer_zero_node
;
2961 dependence_stats
.num_miv_independent
++;
2964 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2965 && !chrec_contains_symbols (chrec_a
)
2966 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2967 && !chrec_contains_symbols (chrec_b
))
2969 /* testsuite/.../ssa-chrec-35.c
2970 {0, +, 1}_2 vs. {0, +, 1}_3
2971 the overlapping elements are respectively located at iterations:
2972 {0, +, 1}_x and {0, +, 1}_x,
2973 in other words, we have the equality:
2974 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2977 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2978 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2980 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2981 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2983 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2984 overlaps_a
, overlaps_b
, last_conflicts
);
2986 if (CF_NOT_KNOWN_P (*overlaps_a
)
2987 || CF_NOT_KNOWN_P (*overlaps_b
))
2988 dependence_stats
.num_miv_unimplemented
++;
2989 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2990 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2991 dependence_stats
.num_miv_independent
++;
2993 dependence_stats
.num_miv_dependent
++;
2998 /* When the analysis is too difficult, answer "don't know". */
2999 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3000 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
3002 *overlaps_a
= conflict_fn_not_known ();
3003 *overlaps_b
= conflict_fn_not_known ();
3004 *last_conflicts
= chrec_dont_know
;
3005 dependence_stats
.num_miv_unimplemented
++;
3008 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3009 fprintf (dump_file
, ")\n");
3012 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
3013 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
3014 OVERLAP_ITERATIONS_B are initialized with two functions that
3015 describe the iterations that contain conflicting elements.
3017 Remark: For an integer k >= 0, the following equality is true:
3019 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3023 analyze_overlapping_iterations (tree chrec_a
,
3025 conflict_function
**overlap_iterations_a
,
3026 conflict_function
**overlap_iterations_b
,
3027 tree
*last_conflicts
, struct loop
*loop_nest
)
3029 unsigned int lnn
= loop_nest
->num
;
3031 dependence_stats
.num_subscript_tests
++;
3033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3035 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
3036 fprintf (dump_file
, " (chrec_a = ");
3037 print_generic_expr (dump_file
, chrec_a
, 0);
3038 fprintf (dump_file
, ")\n (chrec_b = ");
3039 print_generic_expr (dump_file
, chrec_b
, 0);
3040 fprintf (dump_file
, ")\n");
3043 if (chrec_a
== NULL_TREE
3044 || chrec_b
== NULL_TREE
3045 || chrec_contains_undetermined (chrec_a
)
3046 || chrec_contains_undetermined (chrec_b
))
3048 dependence_stats
.num_subscript_undetermined
++;
3050 *overlap_iterations_a
= conflict_fn_not_known ();
3051 *overlap_iterations_b
= conflict_fn_not_known ();
3054 /* If they are the same chrec, and are affine, they overlap
3055 on every iteration. */
3056 else if (eq_evolutions_p (chrec_a
, chrec_b
)
3057 && (evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
3058 || operand_equal_p (chrec_a
, chrec_b
, 0)))
3060 dependence_stats
.num_same_subscript_function
++;
3061 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3062 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3063 *last_conflicts
= chrec_dont_know
;
3066 /* If they aren't the same, and aren't affine, we can't do anything
3068 else if ((chrec_contains_symbols (chrec_a
)
3069 || chrec_contains_symbols (chrec_b
))
3070 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
3071 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
3073 dependence_stats
.num_subscript_undetermined
++;
3074 *overlap_iterations_a
= conflict_fn_not_known ();
3075 *overlap_iterations_b
= conflict_fn_not_known ();
3078 else if (ziv_subscript_p (chrec_a
, chrec_b
))
3079 analyze_ziv_subscript (chrec_a
, chrec_b
,
3080 overlap_iterations_a
, overlap_iterations_b
,
3083 else if (siv_subscript_p (chrec_a
, chrec_b
))
3084 analyze_siv_subscript (chrec_a
, chrec_b
,
3085 overlap_iterations_a
, overlap_iterations_b
,
3086 last_conflicts
, lnn
);
3089 analyze_miv_subscript (chrec_a
, chrec_b
,
3090 overlap_iterations_a
, overlap_iterations_b
,
3091 last_conflicts
, loop_nest
);
3093 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3095 fprintf (dump_file
, " (overlap_iterations_a = ");
3096 dump_conflict_function (dump_file
, *overlap_iterations_a
);
3097 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
3098 dump_conflict_function (dump_file
, *overlap_iterations_b
);
3099 fprintf (dump_file
, "))\n");
3103 /* Helper function for uniquely inserting distance vectors. */
3106 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
3111 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, v
)
3112 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
3115 DDR_DIST_VECTS (ddr
).safe_push (dist_v
);
3118 /* Helper function for uniquely inserting direction vectors. */
3121 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
3126 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), i
, v
)
3127 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
3130 DDR_DIR_VECTS (ddr
).safe_push (dir_v
);
3133 /* Add a distance of 1 on all the loops outer than INDEX. If we
3134 haven't yet determined a distance for this outer loop, push a new
3135 distance vector composed of the previous distance, and a distance
3136 of 1 for this outer loop. Example:
3144 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3145 save (0, 1), then we have to save (1, 0). */
3148 add_outer_distances (struct data_dependence_relation
*ddr
,
3149 lambda_vector dist_v
, int index
)
3151 /* For each outer loop where init_v is not set, the accesses are
3152 in dependence of distance 1 in the loop. */
3153 while (--index
>= 0)
3155 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3156 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3158 save_dist_v (ddr
, save_v
);
3162 /* Return false when fail to represent the data dependence as a
3163 distance vector. INIT_B is set to true when a component has been
3164 added to the distance vector DIST_V. INDEX_CARRY is then set to
3165 the index in DIST_V that carries the dependence. */
3168 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
3169 struct data_reference
*ddr_a
,
3170 struct data_reference
*ddr_b
,
3171 lambda_vector dist_v
, bool *init_b
,
3175 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3177 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3179 tree access_fn_a
, access_fn_b
;
3180 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
3182 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3184 non_affine_dependence_relation (ddr
);
3188 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
3189 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
3191 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
3192 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
3195 int var_a
= CHREC_VARIABLE (access_fn_a
);
3196 int var_b
= CHREC_VARIABLE (access_fn_b
);
3199 || chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3201 non_affine_dependence_relation (ddr
);
3205 dist
= int_cst_value (SUB_DISTANCE (subscript
));
3206 index
= index_in_loop_nest (var_a
, DDR_LOOP_NEST (ddr
));
3207 *index_carry
= MIN (index
, *index_carry
);
3209 /* This is the subscript coupling test. If we have already
3210 recorded a distance for this loop (a distance coming from
3211 another subscript), it should be the same. For example,
3212 in the following code, there is no dependence:
3219 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
3221 finalize_ddr_dependent (ddr
, chrec_known
);
3225 dist_v
[index
] = dist
;
3229 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
3231 /* This can be for example an affine vs. constant dependence
3232 (T[i] vs. T[3]) that is not an affine dependence and is
3233 not representable as a distance vector. */
3234 non_affine_dependence_relation (ddr
);
3242 /* Return true when the DDR contains only constant access functions. */
3245 constant_access_functions (const struct data_dependence_relation
*ddr
)
3249 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3250 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
3251 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
3257 /* Helper function for the case where DDR_A and DDR_B are the same
3258 multivariate access function with a constant step. For an example
3262 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
3265 tree c_1
= CHREC_LEFT (c_2
);
3266 tree c_0
= CHREC_LEFT (c_1
);
3267 lambda_vector dist_v
;
3270 /* Polynomials with more than 2 variables are not handled yet. When
3271 the evolution steps are parameters, it is not possible to
3272 represent the dependence using classical distance vectors. */
3273 if (TREE_CODE (c_0
) != INTEGER_CST
3274 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
3275 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
3277 DDR_AFFINE_P (ddr
) = false;
3281 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
3282 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
3284 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3285 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3286 v1
= int_cst_value (CHREC_RIGHT (c_1
));
3287 v2
= int_cst_value (CHREC_RIGHT (c_2
));
3300 save_dist_v (ddr
, dist_v
);
3302 add_outer_distances (ddr
, dist_v
, x_1
);
3305 /* Helper function for the case where DDR_A and DDR_B are the same
3306 access functions. */
3309 add_other_self_distances (struct data_dependence_relation
*ddr
)
3311 lambda_vector dist_v
;
3313 int index_carry
= DDR_NB_LOOPS (ddr
);
3315 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3317 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3319 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3321 if (!evolution_function_is_univariate_p (access_fun
))
3323 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3325 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3329 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
3331 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
3332 add_multivariate_self_dist (ddr
, access_fun
);
3334 /* The evolution step is not constant: it varies in
3335 the outer loop, so this cannot be represented by a
3336 distance vector. For example in pr34635.c the
3337 evolution is {0, +, {0, +, 4}_1}_2. */
3338 DDR_AFFINE_P (ddr
) = false;
3343 index_carry
= MIN (index_carry
,
3344 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3345 DDR_LOOP_NEST (ddr
)));
3349 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3350 add_outer_distances (ddr
, dist_v
, index_carry
);
3354 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
3356 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3358 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
3359 save_dist_v (ddr
, dist_v
);
3362 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3363 is the case for example when access functions are the same and
3364 equal to a constant, as in:
3371 in which case the distance vectors are (0) and (1). */
3374 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
3378 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3380 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
3381 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
3382 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
3384 for (j
= 0; j
< ca
->n
; j
++)
3385 if (affine_function_zero_p (ca
->fns
[j
]))
3387 insert_innermost_unit_dist_vector (ddr
);
3391 for (j
= 0; j
< cb
->n
; j
++)
3392 if (affine_function_zero_p (cb
->fns
[j
]))
3394 insert_innermost_unit_dist_vector (ddr
);
3400 /* Compute the classic per loop distance vector. DDR is the data
3401 dependence relation to build a vector from. Return false when fail
3402 to represent the data dependence as a distance vector. */
3405 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3406 struct loop
*loop_nest
)
3408 bool init_b
= false;
3409 int index_carry
= DDR_NB_LOOPS (ddr
);
3410 lambda_vector dist_v
;
3412 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3415 if (same_access_functions (ddr
))
3417 /* Save the 0 vector. */
3418 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3419 save_dist_v (ddr
, dist_v
);
3421 if (constant_access_functions (ddr
))
3422 add_distance_for_zero_overlaps (ddr
);
3424 if (DDR_NB_LOOPS (ddr
) > 1)
3425 add_other_self_distances (ddr
);
3430 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3431 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3432 dist_v
, &init_b
, &index_carry
))
3435 /* Save the distance vector if we initialized one. */
3438 /* Verify a basic constraint: classic distance vectors should
3439 always be lexicographically positive.
3441 Data references are collected in the order of execution of
3442 the program, thus for the following loop
3444 | for (i = 1; i < 100; i++)
3445 | for (j = 1; j < 100; j++)
3447 | t = T[j+1][i-1]; // A
3448 | T[j][i] = t + 2; // B
3451 references are collected following the direction of the wind:
3452 A then B. The data dependence tests are performed also
3453 following this order, such that we're looking at the distance
3454 separating the elements accessed by A from the elements later
3455 accessed by B. But in this example, the distance returned by
3456 test_dep (A, B) is lexicographically negative (-1, 1), that
3457 means that the access A occurs later than B with respect to
3458 the outer loop, ie. we're actually looking upwind. In this
3459 case we solve test_dep (B, A) looking downwind to the
3460 lexicographically positive solution, that returns the
3461 distance vector (1, -1). */
3462 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3464 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3465 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3468 compute_subscript_distance (ddr
);
3469 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3470 save_v
, &init_b
, &index_carry
))
3472 save_dist_v (ddr
, save_v
);
3473 DDR_REVERSED_P (ddr
) = true;
3475 /* In this case there is a dependence forward for all the
3478 | for (k = 1; k < 100; k++)
3479 | for (i = 1; i < 100; i++)
3480 | for (j = 1; j < 100; j++)
3482 | t = T[j+1][i-1]; // A
3483 | T[j][i] = t + 2; // B
3491 if (DDR_NB_LOOPS (ddr
) > 1)
3493 add_outer_distances (ddr
, save_v
, index_carry
);
3494 add_outer_distances (ddr
, dist_v
, index_carry
);
3499 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3500 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3502 if (DDR_NB_LOOPS (ddr
) > 1)
3504 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3506 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3507 DDR_A (ddr
), loop_nest
))
3509 compute_subscript_distance (ddr
);
3510 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3511 opposite_v
, &init_b
,
3515 save_dist_v (ddr
, save_v
);
3516 add_outer_distances (ddr
, dist_v
, index_carry
);
3517 add_outer_distances (ddr
, opposite_v
, index_carry
);
3520 save_dist_v (ddr
, save_v
);
3525 /* There is a distance of 1 on all the outer loops: Example:
3526 there is a dependence of distance 1 on loop_1 for the array A.
3532 add_outer_distances (ddr
, dist_v
,
3533 lambda_vector_first_nz (dist_v
,
3534 DDR_NB_LOOPS (ddr
), 0));
3537 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3541 fprintf (dump_file
, "(build_classic_dist_vector\n");
3542 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3544 fprintf (dump_file
, " dist_vector = (");
3545 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3546 DDR_NB_LOOPS (ddr
));
3547 fprintf (dump_file
, " )\n");
3549 fprintf (dump_file
, ")\n");
3555 /* Return the direction for a given distance.
3556 FIXME: Computing dir this way is suboptimal, since dir can catch
3557 cases that dist is unable to represent. */
3559 static inline enum data_dependence_direction
3560 dir_from_dist (int dist
)
3563 return dir_positive
;
3565 return dir_negative
;
3570 /* Compute the classic per loop direction vector. DDR is the data
3571 dependence relation to build a vector from. */
3574 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3577 lambda_vector dist_v
;
3579 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
3581 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3583 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3584 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3586 save_dir_v (ddr
, dir_v
);
3590 /* Helper function. Returns true when there is a dependence between
3591 data references DRA and DRB. */
3594 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3595 struct data_reference
*dra
,
3596 struct data_reference
*drb
,
3597 struct loop
*loop_nest
)
3600 tree last_conflicts
;
3601 struct subscript
*subscript
;
3602 tree res
= NULL_TREE
;
3604 for (i
= 0; DDR_SUBSCRIPTS (ddr
).iterate (i
, &subscript
); i
++)
3606 conflict_function
*overlaps_a
, *overlaps_b
;
3608 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3609 DR_ACCESS_FN (drb
, i
),
3610 &overlaps_a
, &overlaps_b
,
3611 &last_conflicts
, loop_nest
);
3613 if (SUB_CONFLICTS_IN_A (subscript
))
3614 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3615 if (SUB_CONFLICTS_IN_B (subscript
))
3616 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3618 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3619 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3620 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3622 /* If there is any undetermined conflict function we have to
3623 give a conservative answer in case we cannot prove that
3624 no dependence exists when analyzing another subscript. */
3625 if (CF_NOT_KNOWN_P (overlaps_a
)
3626 || CF_NOT_KNOWN_P (overlaps_b
))
3628 res
= chrec_dont_know
;
3632 /* When there is a subscript with no dependence we can stop. */
3633 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3634 || CF_NO_DEPENDENCE_P (overlaps_b
))
3641 if (res
== NULL_TREE
)
3644 if (res
== chrec_known
)
3645 dependence_stats
.num_dependence_independent
++;
3647 dependence_stats
.num_dependence_undetermined
++;
3648 finalize_ddr_dependent (ddr
, res
);
3652 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3655 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3656 struct loop
*loop_nest
)
3658 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3659 dependence_stats
.num_dependence_dependent
++;
3661 compute_subscript_distance (ddr
);
3662 if (build_classic_dist_vector (ddr
, loop_nest
))
3663 build_classic_dir_vector (ddr
);
3666 /* Returns true when all the access functions of A are affine or
3667 constant with respect to LOOP_NEST. */
3670 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3671 const struct loop
*loop_nest
)
3674 vec
<tree
> fns
= DR_ACCESS_FNS (a
);
3677 FOR_EACH_VEC_ELT (fns
, i
, t
)
3678 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3679 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3685 /* Initializes an equation for an OMEGA problem using the information
3686 contained in the ACCESS_FUN. Returns true when the operation
3689 PB is the omega constraint system.
3690 EQ is the number of the equation to be initialized.
3691 OFFSET is used for shifting the variables names in the constraints:
3692 a constrain is composed of 2 * the number of variables surrounding
3693 dependence accesses. OFFSET is set either to 0 for the first n variables,
3694 then it is set to n.
3695 ACCESS_FUN is expected to be an affine chrec. */
3698 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3699 unsigned int offset
, tree access_fun
,
3700 struct data_dependence_relation
*ddr
)
3702 switch (TREE_CODE (access_fun
))
3704 case POLYNOMIAL_CHREC
:
3706 tree left
= CHREC_LEFT (access_fun
);
3707 tree right
= CHREC_RIGHT (access_fun
);
3708 int var
= CHREC_VARIABLE (access_fun
);
3711 if (TREE_CODE (right
) != INTEGER_CST
)
3714 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3715 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3717 /* Compute the innermost loop index. */
3718 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3721 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3722 += int_cst_value (right
);
3724 switch (TREE_CODE (left
))
3726 case POLYNOMIAL_CHREC
:
3727 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3730 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3739 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3747 /* As explained in the comments preceding init_omega_for_ddr, we have
3748 to set up a system for each loop level, setting outer loops
3749 variation to zero, and current loop variation to positive or zero.
3750 Save each lexico positive distance vector. */
3753 omega_extract_distance_vectors (omega_pb pb
,
3754 struct data_dependence_relation
*ddr
)
3758 struct loop
*loopi
, *loopj
;
3759 enum omega_result res
;
3761 /* Set a new problem for each loop in the nest. The basis is the
3762 problem that we have initialized until now. On top of this we
3763 add new constraints. */
3764 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3765 && DDR_LOOP_NEST (ddr
).iterate (i
, &loopi
); i
++)
3768 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3769 DDR_NB_LOOPS (ddr
));
3771 omega_copy_problem (copy
, pb
);
3773 /* For all the outer loops "loop_j", add "dj = 0". */
3774 for (j
= 0; j
< i
&& DDR_LOOP_NEST (ddr
).iterate (j
, &loopj
); j
++)
3776 eq
= omega_add_zero_eq (copy
, omega_black
);
3777 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3780 /* For "loop_i", add "0 <= di". */
3781 geq
= omega_add_zero_geq (copy
, omega_black
);
3782 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3784 /* Reduce the constraint system, and test that the current
3785 problem is feasible. */
3786 res
= omega_simplify_problem (copy
);
3787 if (res
== omega_false
3788 || res
== omega_unknown
3789 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3792 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3793 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3795 dist
= copy
->subs
[eq
].coef
[0];
3801 /* Reinitialize problem... */
3802 omega_copy_problem (copy
, pb
);
3803 for (j
= 0; j
< i
&& DDR_LOOP_NEST (ddr
).iterate (j
, &loopj
); j
++)
3805 eq
= omega_add_zero_eq (copy
, omega_black
);
3806 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3809 /* ..., but this time "di = 1". */
3810 eq
= omega_add_zero_eq (copy
, omega_black
);
3811 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3812 copy
->eqs
[eq
].coef
[0] = -1;
3814 res
= omega_simplify_problem (copy
);
3815 if (res
== omega_false
3816 || res
== omega_unknown
3817 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3820 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3821 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3823 dist
= copy
->subs
[eq
].coef
[0];
3829 /* Save the lexicographically positive distance vector. */
3832 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3833 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3837 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3838 if (copy
->subs
[eq
].key
> 0)
3840 dist
= copy
->subs
[eq
].coef
[0];
3841 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3844 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3845 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3847 save_dist_v (ddr
, dist_v
);
3848 save_dir_v (ddr
, dir_v
);
3852 omega_free_problem (copy
);
3856 /* This is called for each subscript of a tuple of data references:
3857 insert an equality for representing the conflicts. */
3860 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3861 struct data_dependence_relation
*ddr
,
3862 omega_pb pb
, bool *maybe_dependent
)
3865 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3866 TREE_TYPE (access_fun_b
));
3867 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3868 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3869 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3872 /* When the fun_a - fun_b is not constant, the dependence is not
3873 captured by the classic distance vector representation. */
3874 if (TREE_CODE (difference
) != INTEGER_CST
)
3878 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3880 /* There is no dependence. */
3881 *maybe_dependent
= false;
3885 minus_one
= build_int_cst (type
, -1);
3886 fun_b
= chrec_fold_multiply (type
, fun_b
, minus_one
);
3888 eq
= omega_add_zero_eq (pb
, omega_black
);
3889 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3890 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3891 /* There is probably a dependence, but the system of
3892 constraints cannot be built: answer "don't know". */
3896 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3897 && !int_divides_p (lambda_vector_gcd
3898 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3899 2 * DDR_NB_LOOPS (ddr
)),
3900 pb
->eqs
[eq
].coef
[0]))
3902 /* There is no dependence. */
3903 *maybe_dependent
= false;
3910 /* Helper function, same as init_omega_for_ddr but specialized for
3911 data references A and B. */
3914 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3915 struct data_dependence_relation
*ddr
,
3916 omega_pb pb
, bool *maybe_dependent
)
3921 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3923 /* Insert an equality per subscript. */
3924 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3926 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3927 ddr
, pb
, maybe_dependent
))
3929 else if (*maybe_dependent
== false)
3931 /* There is no dependence. */
3932 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3937 /* Insert inequalities: constraints corresponding to the iteration
3938 domain, i.e. the loops surrounding the references "loop_x" and
3939 the distance variables "dx". The layout of the OMEGA
3940 representation is as follows:
3941 - coef[0] is the constant
3942 - coef[1..nb_loops] are the protected variables that will not be
3943 removed by the solver: the "dx"
3944 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3946 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3947 && DDR_LOOP_NEST (ddr
).iterate (i
, &loopi
); i
++)
3949 HOST_WIDE_INT nbi
= max_stmt_executions_int (loopi
);
3952 ineq
= omega_add_zero_geq (pb
, omega_black
);
3953 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3955 /* 0 <= loop_x + dx */
3956 ineq
= omega_add_zero_geq (pb
, omega_black
);
3957 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3958 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3962 /* loop_x <= nb_iters */
3963 ineq
= omega_add_zero_geq (pb
, omega_black
);
3964 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3965 pb
->geqs
[ineq
].coef
[0] = nbi
;
3967 /* loop_x + dx <= nb_iters */
3968 ineq
= omega_add_zero_geq (pb
, omega_black
);
3969 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3970 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3971 pb
->geqs
[ineq
].coef
[0] = nbi
;
3973 /* A step "dx" bigger than nb_iters is not feasible, so
3974 add "0 <= nb_iters + dx", */
3975 ineq
= omega_add_zero_geq (pb
, omega_black
);
3976 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3977 pb
->geqs
[ineq
].coef
[0] = nbi
;
3978 /* and "dx <= nb_iters". */
3979 ineq
= omega_add_zero_geq (pb
, omega_black
);
3980 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3981 pb
->geqs
[ineq
].coef
[0] = nbi
;
3985 omega_extract_distance_vectors (pb
, ddr
);
3990 /* Sets up the Omega dependence problem for the data dependence
3991 relation DDR. Returns false when the constraint system cannot be
3992 built, ie. when the test answers "don't know". Returns true
3993 otherwise, and when independence has been proved (using one of the
3994 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3995 set MAYBE_DEPENDENT to true.
3997 Example: for setting up the dependence system corresponding to the
3998 conflicting accesses
4003 | ... A[2*j, 2*(i + j)]
4007 the following constraints come from the iteration domain:
4014 where di, dj are the distance variables. The constraints
4015 representing the conflicting elements are:
4018 i + 1 = 2 * (i + di + j + dj)
4020 For asking that the resulting distance vector (di, dj) be
4021 lexicographically positive, we insert the constraint "di >= 0". If
4022 "di = 0" in the solution, we fix that component to zero, and we
4023 look at the inner loops: we set a new problem where all the outer
4024 loop distances are zero, and fix this inner component to be
4025 positive. When one of the components is positive, we save that
4026 distance, and set a new problem where the distance on this loop is
4027 zero, searching for other distances in the inner loops. Here is
4028 the classic example that illustrates that we have to set for each
4029 inner loop a new problem:
4037 we have to save two distances (1, 0) and (0, 1).
4039 Given two array references, refA and refB, we have to set the
4040 dependence problem twice, refA vs. refB and refB vs. refA, and we
4041 cannot do a single test, as refB might occur before refA in the
4042 inner loops, and the contrary when considering outer loops: ex.
4047 | T[{1,+,1}_2][{1,+,1}_1] // refA
4048 | T[{2,+,1}_2][{0,+,1}_1] // refB
4053 refB touches the elements in T before refA, and thus for the same
4054 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
4055 but for successive loop_0 iterations, we have (1, -1, 1)
4057 The Omega solver expects the distance variables ("di" in the
4058 previous example) to come first in the constraint system (as
4059 variables to be protected, or "safe" variables), the constraint
4060 system is built using the following layout:
4062 "cst | distance vars | index vars".
4066 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
4067 bool *maybe_dependent
)
4072 *maybe_dependent
= true;
4074 if (same_access_functions (ddr
))
4077 lambda_vector dir_v
;
4079 /* Save the 0 vector. */
4080 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4081 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4082 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
4083 dir_v
[j
] = dir_equal
;
4084 save_dir_v (ddr
, dir_v
);
4086 /* Save the dependences carried by outer loops. */
4087 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4088 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
4090 omega_free_problem (pb
);
4094 /* Omega expects the protected variables (those that have to be kept
4095 after elimination) to appear first in the constraint system.
4096 These variables are the distance variables. In the following
4097 initialization we declare NB_LOOPS safe variables, and the total
4098 number of variables for the constraint system is 2*NB_LOOPS. */
4099 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4100 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
4102 omega_free_problem (pb
);
4104 /* Stop computation if not decidable, or no dependence. */
4105 if (res
== false || *maybe_dependent
== false)
4108 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4109 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
4111 omega_free_problem (pb
);
4116 /* Return true when DDR contains the same information as that stored
4117 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4120 ddr_consistent_p (FILE *file
,
4121 struct data_dependence_relation
*ddr
,
4122 vec
<lambda_vector
> dist_vects
,
4123 vec
<lambda_vector
> dir_vects
)
4127 /* If dump_file is set, output there. */
4128 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4131 if (dist_vects
.length () != DDR_NUM_DIST_VECTS (ddr
))
4133 lambda_vector b_dist_v
;
4134 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4135 dist_vects
.length (),
4136 DDR_NUM_DIST_VECTS (ddr
));
4138 fprintf (file
, "Banerjee dist vectors:\n");
4139 FOR_EACH_VEC_ELT (dist_vects
, i
, b_dist_v
)
4140 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
4142 fprintf (file
, "Omega dist vectors:\n");
4143 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4144 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
4146 fprintf (file
, "data dependence relation:\n");
4147 dump_data_dependence_relation (file
, ddr
);
4149 fprintf (file
, ")\n");
4153 if (dir_vects
.length () != DDR_NUM_DIR_VECTS (ddr
))
4155 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4156 dir_vects
.length (),
4157 DDR_NUM_DIR_VECTS (ddr
));
4161 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4163 lambda_vector a_dist_v
;
4164 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
4166 /* Distance vectors are not ordered in the same way in the DDR
4167 and in the DIST_VECTS: search for a matching vector. */
4168 FOR_EACH_VEC_ELT (dist_vects
, j
, a_dist_v
)
4169 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
4172 if (j
== dist_vects
.length ())
4174 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
4175 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
4176 fprintf (file
, "not found in Omega dist vectors:\n");
4177 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4178 fprintf (file
, "data dependence relation:\n");
4179 dump_data_dependence_relation (file
, ddr
);
4180 fprintf (file
, ")\n");
4184 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
4186 lambda_vector a_dir_v
;
4187 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
4189 /* Direction vectors are not ordered in the same way in the DDR
4190 and in the DIR_VECTS: search for a matching vector. */
4191 FOR_EACH_VEC_ELT (dir_vects
, j
, a_dir_v
)
4192 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
4195 if (j
== dist_vects
.length ())
4197 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
4198 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
4199 fprintf (file
, "not found in Omega dir vectors:\n");
4200 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4201 fprintf (file
, "data dependence relation:\n");
4202 dump_data_dependence_relation (file
, ddr
);
4203 fprintf (file
, ")\n");
4210 /* This computes the affine dependence relation between A and B with
4211 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4212 independence between two accesses, while CHREC_DONT_KNOW is used
4213 for representing the unknown relation.
4215 Note that it is possible to stop the computation of the dependence
4216 relation the first time we detect a CHREC_KNOWN element for a given
4220 compute_affine_dependence (struct data_dependence_relation
*ddr
,
4221 struct loop
*loop_nest
)
4223 struct data_reference
*dra
= DDR_A (ddr
);
4224 struct data_reference
*drb
= DDR_B (ddr
);
4226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4228 fprintf (dump_file
, "(compute_affine_dependence\n");
4229 fprintf (dump_file
, " stmt_a: ");
4230 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, TDF_SLIM
);
4231 fprintf (dump_file
, " stmt_b: ");
4232 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, TDF_SLIM
);
4235 /* Analyze only when the dependence relation is not yet known. */
4236 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4238 dependence_stats
.num_dependence_tests
++;
4240 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
4241 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
4243 subscript_dependence_tester (ddr
, loop_nest
);
4245 if (flag_check_data_deps
)
4247 /* Dump the dependences from the first algorithm. */
4248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4250 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
4251 dump_data_dependence_relation (dump_file
, ddr
);
4254 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4256 bool maybe_dependent
;
4257 vec
<lambda_vector
> dir_vects
, dist_vects
;
4259 /* Save the result of the first DD analyzer. */
4260 dist_vects
= DDR_DIST_VECTS (ddr
);
4261 dir_vects
= DDR_DIR_VECTS (ddr
);
4263 /* Reset the information. */
4264 DDR_DIST_VECTS (ddr
).create (0);
4265 DDR_DIR_VECTS (ddr
).create (0);
4267 /* Compute the same information using Omega. */
4268 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
4269 goto csys_dont_know
;
4271 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4273 fprintf (dump_file
, "Omega Analyzer\n");
4274 dump_data_dependence_relation (dump_file
, ddr
);
4277 /* Check that we get the same information. */
4278 if (maybe_dependent
)
4279 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
4285 /* As a last case, if the dependence cannot be determined, or if
4286 the dependence is considered too difficult to determine, answer
4291 dependence_stats
.num_dependence_undetermined
++;
4293 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4295 fprintf (dump_file
, "Data ref a:\n");
4296 dump_data_reference (dump_file
, dra
);
4297 fprintf (dump_file
, "Data ref b:\n");
4298 dump_data_reference (dump_file
, drb
);
4299 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
4301 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4305 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4307 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4308 fprintf (dump_file
, ") -> no dependence\n");
4309 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4310 fprintf (dump_file
, ") -> dependence analysis failed\n");
4312 fprintf (dump_file
, ")\n");
4316 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4317 the data references in DATAREFS, in the LOOP_NEST. When
4318 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4319 relations. Return true when successful, i.e. data references number
4320 is small enough to be handled. */
4323 compute_all_dependences (vec
<data_reference_p
> datarefs
,
4324 vec
<ddr_p
> *dependence_relations
,
4325 vec
<loop_p
> loop_nest
,
4326 bool compute_self_and_rr
)
4328 struct data_dependence_relation
*ddr
;
4329 struct data_reference
*a
, *b
;
4332 if ((int) datarefs
.length ()
4333 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS
))
4335 struct data_dependence_relation
*ddr
;
4337 /* Insert a single relation into dependence_relations:
4339 ddr
= initialize_data_dependence_relation (NULL
, NULL
, loop_nest
);
4340 dependence_relations
->safe_push (ddr
);
4344 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4345 for (j
= i
+ 1; datarefs
.iterate (j
, &b
); j
++)
4346 if (DR_IS_WRITE (a
) || DR_IS_WRITE (b
) || compute_self_and_rr
)
4348 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4349 dependence_relations
->safe_push (ddr
);
4350 if (loop_nest
.exists ())
4351 compute_affine_dependence (ddr
, loop_nest
[0]);
4354 if (compute_self_and_rr
)
4355 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4357 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4358 dependence_relations
->safe_push (ddr
);
4359 if (loop_nest
.exists ())
4360 compute_affine_dependence (ddr
, loop_nest
[0]);
4366 /* Describes a location of a memory reference. */
4368 typedef struct data_ref_loc_d
4370 /* The memory reference. */
4373 /* True if the memory reference is read. */
4378 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4379 true if STMT clobbers memory, false otherwise. */
4382 get_references_in_stmt (gimple stmt
, vec
<data_ref_loc
, va_heap
> *references
)
4384 bool clobbers_memory
= false;
4387 enum gimple_code stmt_code
= gimple_code (stmt
);
4389 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4390 As we cannot model data-references to not spelled out
4391 accesses give up if they may occur. */
4392 if (stmt_code
== GIMPLE_CALL
4393 && !(gimple_call_flags (stmt
) & ECF_CONST
))
4395 /* Allow IFN_GOMP_SIMD_LANE in their own loops. */
4396 if (gimple_call_internal_p (stmt
))
4397 switch (gimple_call_internal_fn (stmt
))
4399 case IFN_GOMP_SIMD_LANE
:
4401 struct loop
*loop
= gimple_bb (stmt
)->loop_father
;
4402 tree uid
= gimple_call_arg (stmt
, 0);
4403 gcc_assert (TREE_CODE (uid
) == SSA_NAME
);
4405 || loop
->simduid
!= SSA_NAME_VAR (uid
))
4406 clobbers_memory
= true;
4410 case IFN_MASK_STORE
:
4413 clobbers_memory
= true;
4417 clobbers_memory
= true;
4419 else if (stmt_code
== GIMPLE_ASM
4420 && (gimple_asm_volatile_p (stmt
) || gimple_vuse (stmt
)))
4421 clobbers_memory
= true;
4423 if (!gimple_vuse (stmt
))
4424 return clobbers_memory
;
4426 if (stmt_code
== GIMPLE_ASSIGN
)
4429 op0
= gimple_assign_lhs (stmt
);
4430 op1
= gimple_assign_rhs1 (stmt
);
4433 || (REFERENCE_CLASS_P (op1
)
4434 && (base
= get_base_address (op1
))
4435 && TREE_CODE (base
) != SSA_NAME
))
4439 references
->safe_push (ref
);
4442 else if (stmt_code
== GIMPLE_CALL
)
4446 ref
.is_read
= false;
4447 if (gimple_call_internal_p (stmt
))
4448 switch (gimple_call_internal_fn (stmt
))
4451 if (gimple_call_lhs (stmt
) == NULL_TREE
)
4454 case IFN_MASK_STORE
:
4455 ref
.ref
= fold_build2 (MEM_REF
,
4457 ? TREE_TYPE (gimple_call_lhs (stmt
))
4458 : TREE_TYPE (gimple_call_arg (stmt
, 3)),
4459 gimple_call_arg (stmt
, 0),
4460 gimple_call_arg (stmt
, 1));
4461 references
->safe_push (ref
);
4467 op0
= gimple_call_lhs (stmt
);
4468 n
= gimple_call_num_args (stmt
);
4469 for (i
= 0; i
< n
; i
++)
4471 op1
= gimple_call_arg (stmt
, i
);
4474 || (REFERENCE_CLASS_P (op1
) && get_base_address (op1
)))
4478 references
->safe_push (ref
);
4483 return clobbers_memory
;
4487 || (REFERENCE_CLASS_P (op0
) && get_base_address (op0
))))
4490 ref
.is_read
= false;
4491 references
->safe_push (ref
);
4493 return clobbers_memory
;
4496 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4497 reference, returns false, otherwise returns true. NEST is the outermost
4498 loop of the loop nest in which the references should be analyzed. */
4501 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4502 vec
<data_reference_p
> *datarefs
)
4505 auto_vec
<data_ref_loc
, 2> references
;
4508 data_reference_p dr
;
4510 if (get_references_in_stmt (stmt
, &references
))
4513 FOR_EACH_VEC_ELT (references
, i
, ref
)
4515 dr
= create_data_ref (nest
, loop_containing_stmt (stmt
),
4516 ref
->ref
, stmt
, ref
->is_read
);
4517 gcc_assert (dr
!= NULL
);
4518 datarefs
->safe_push (dr
);
4520 references
.release ();
4524 /* Stores the data references in STMT to DATAREFS. If there is an
4525 unanalyzable reference, returns false, otherwise returns true.
4526 NEST is the outermost loop of the loop nest in which the references
4527 should be instantiated, LOOP is the loop in which the references
4528 should be analyzed. */
4531 graphite_find_data_references_in_stmt (loop_p nest
, loop_p loop
, gimple stmt
,
4532 vec
<data_reference_p
> *datarefs
)
4535 auto_vec
<data_ref_loc
, 2> references
;
4538 data_reference_p dr
;
4540 if (get_references_in_stmt (stmt
, &references
))
4543 FOR_EACH_VEC_ELT (references
, i
, ref
)
4545 dr
= create_data_ref (nest
, loop
, ref
->ref
, stmt
, ref
->is_read
);
4546 gcc_assert (dr
!= NULL
);
4547 datarefs
->safe_push (dr
);
4550 references
.release ();
4554 /* Search the data references in LOOP, and record the information into
4555 DATAREFS. Returns chrec_dont_know when failing to analyze a
4556 difficult case, returns NULL_TREE otherwise. */
4559 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4560 vec
<data_reference_p
> *datarefs
)
4562 gimple_stmt_iterator bsi
;
4564 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4566 gimple stmt
= gsi_stmt (bsi
);
4568 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4570 struct data_reference
*res
;
4571 res
= XCNEW (struct data_reference
);
4572 datarefs
->safe_push (res
);
4574 return chrec_dont_know
;
4581 /* Search the data references in LOOP, and record the information into
4582 DATAREFS. Returns chrec_dont_know when failing to analyze a
4583 difficult case, returns NULL_TREE otherwise.
4585 TODO: This function should be made smarter so that it can handle address
4586 arithmetic as if they were array accesses, etc. */
4589 find_data_references_in_loop (struct loop
*loop
,
4590 vec
<data_reference_p
> *datarefs
)
4592 basic_block bb
, *bbs
;
4595 bbs
= get_loop_body_in_dom_order (loop
);
4597 for (i
= 0; i
< loop
->num_nodes
; i
++)
4601 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4604 return chrec_dont_know
;
4612 /* Recursive helper function. */
4615 find_loop_nest_1 (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
4617 /* Inner loops of the nest should not contain siblings. Example:
4618 when there are two consecutive loops,
4629 the dependence relation cannot be captured by the distance
4634 loop_nest
->safe_push (loop
);
4636 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4640 /* Return false when the LOOP is not well nested. Otherwise return
4641 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4642 contain the loops from the outermost to the innermost, as they will
4643 appear in the classic distance vector. */
4646 find_loop_nest (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
4648 loop_nest
->safe_push (loop
);
4650 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4654 /* Returns true when the data dependences have been computed, false otherwise.
4655 Given a loop nest LOOP, the following vectors are returned:
4656 DATAREFS is initialized to all the array elements contained in this loop,
4657 DEPENDENCE_RELATIONS contains the relations between the data references.
4658 Compute read-read and self relations if
4659 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4662 compute_data_dependences_for_loop (struct loop
*loop
,
4663 bool compute_self_and_read_read_dependences
,
4664 vec
<loop_p
> *loop_nest
,
4665 vec
<data_reference_p
> *datarefs
,
4666 vec
<ddr_p
> *dependence_relations
)
4670 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4672 /* If the loop nest is not well formed, or one of the data references
4673 is not computable, give up without spending time to compute other
4676 || !find_loop_nest (loop
, loop_nest
)
4677 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
4678 || !compute_all_dependences (*datarefs
, dependence_relations
, *loop_nest
,
4679 compute_self_and_read_read_dependences
))
4682 if (dump_file
&& (dump_flags
& TDF_STATS
))
4684 fprintf (dump_file
, "Dependence tester statistics:\n");
4686 fprintf (dump_file
, "Number of dependence tests: %d\n",
4687 dependence_stats
.num_dependence_tests
);
4688 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4689 dependence_stats
.num_dependence_dependent
);
4690 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4691 dependence_stats
.num_dependence_independent
);
4692 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4693 dependence_stats
.num_dependence_undetermined
);
4695 fprintf (dump_file
, "Number of subscript tests: %d\n",
4696 dependence_stats
.num_subscript_tests
);
4697 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4698 dependence_stats
.num_subscript_undetermined
);
4699 fprintf (dump_file
, "Number of same subscript function: %d\n",
4700 dependence_stats
.num_same_subscript_function
);
4702 fprintf (dump_file
, "Number of ziv tests: %d\n",
4703 dependence_stats
.num_ziv
);
4704 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4705 dependence_stats
.num_ziv_dependent
);
4706 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4707 dependence_stats
.num_ziv_independent
);
4708 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4709 dependence_stats
.num_ziv_unimplemented
);
4711 fprintf (dump_file
, "Number of siv tests: %d\n",
4712 dependence_stats
.num_siv
);
4713 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4714 dependence_stats
.num_siv_dependent
);
4715 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4716 dependence_stats
.num_siv_independent
);
4717 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4718 dependence_stats
.num_siv_unimplemented
);
4720 fprintf (dump_file
, "Number of miv tests: %d\n",
4721 dependence_stats
.num_miv
);
4722 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4723 dependence_stats
.num_miv_dependent
);
4724 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4725 dependence_stats
.num_miv_independent
);
4726 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4727 dependence_stats
.num_miv_unimplemented
);
4733 /* Returns true when the data dependences for the basic block BB have been
4734 computed, false otherwise.
4735 DATAREFS is initialized to all the array elements contained in this basic
4736 block, DEPENDENCE_RELATIONS contains the relations between the data
4737 references. Compute read-read and self relations if
4738 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4740 compute_data_dependences_for_bb (basic_block bb
,
4741 bool compute_self_and_read_read_dependences
,
4742 vec
<data_reference_p
> *datarefs
,
4743 vec
<ddr_p
> *dependence_relations
)
4745 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4748 return compute_all_dependences (*datarefs
, dependence_relations
, vNULL
,
4749 compute_self_and_read_read_dependences
);
4752 /* Entry point (for testing only). Analyze all the data references
4753 and the dependence relations in LOOP.
4755 The data references are computed first.
4757 A relation on these nodes is represented by a complete graph. Some
4758 of the relations could be of no interest, thus the relations can be
4761 In the following function we compute all the relations. This is
4762 just a first implementation that is here for:
4763 - for showing how to ask for the dependence relations,
4764 - for the debugging the whole dependence graph,
4765 - for the dejagnu testcases and maintenance.
4767 It is possible to ask only for a part of the graph, avoiding to
4768 compute the whole dependence graph. The computed dependences are
4769 stored in a knowledge base (KB) such that later queries don't
4770 recompute the same information. The implementation of this KB is
4771 transparent to the optimizer, and thus the KB can be changed with a
4772 more efficient implementation, or the KB could be disabled. */
4774 analyze_all_data_dependences (struct loop
*loop
)
4777 int nb_data_refs
= 10;
4778 vec
<data_reference_p
> datarefs
;
4779 datarefs
.create (nb_data_refs
);
4780 vec
<ddr_p
> dependence_relations
;
4781 dependence_relations
.create (nb_data_refs
* nb_data_refs
);
4782 vec
<loop_p
> loop_nest
;
4783 loop_nest
.create (3);
4785 /* Compute DDs on the whole function. */
4786 compute_data_dependences_for_loop (loop
, false, &loop_nest
, &datarefs
,
4787 &dependence_relations
);
4791 dump_data_dependence_relations (dump_file
, dependence_relations
);
4792 fprintf (dump_file
, "\n\n");
4794 if (dump_flags
& TDF_DETAILS
)
4795 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4797 if (dump_flags
& TDF_STATS
)
4799 unsigned nb_top_relations
= 0;
4800 unsigned nb_bot_relations
= 0;
4801 unsigned nb_chrec_relations
= 0;
4802 struct data_dependence_relation
*ddr
;
4804 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
4806 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4809 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4813 nb_chrec_relations
++;
4816 gather_stats_on_scev_database ();
4820 loop_nest
.release ();
4821 free_dependence_relations (dependence_relations
);
4822 free_data_refs (datarefs
);
4825 /* Computes all the data dependences and check that the results of
4826 several analyzers are the same. */
4829 tree_check_data_deps (void)
4831 struct loop
*loop_nest
;
4833 FOR_EACH_LOOP (loop_nest
, 0)
4834 analyze_all_data_dependences (loop_nest
);
4837 /* Free the memory used by a data dependence relation DDR. */
4840 free_dependence_relation (struct data_dependence_relation
*ddr
)
4845 if (DDR_SUBSCRIPTS (ddr
).exists ())
4846 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4847 DDR_DIST_VECTS (ddr
).release ();
4848 DDR_DIR_VECTS (ddr
).release ();
4853 /* Free the memory used by the data dependence relations from
4854 DEPENDENCE_RELATIONS. */
4857 free_dependence_relations (vec
<ddr_p
> dependence_relations
)
4860 struct data_dependence_relation
*ddr
;
4862 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
4864 free_dependence_relation (ddr
);
4866 dependence_relations
.release ();
4869 /* Free the memory used by the data references from DATAREFS. */
4872 free_data_refs (vec
<data_reference_p
> datarefs
)
4875 struct data_reference
*dr
;
4877 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
4879 datarefs
.release ();