1 /* Data references and dependences detectors.
2 Copyright (C) 2003-2015 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"
84 #include "fold-const.h"
86 #include "hard-reg-set.h"
90 #include "insn-config.h"
99 #include "gimple-pretty-print.h"
101 #include "dominance.h"
103 #include "basic-block.h"
104 #include "tree-ssa-alias.h"
105 #include "internal-fn.h"
106 #include "gimple-expr.h"
109 #include "gimple-iterator.h"
110 #include "tree-ssa-loop-niter.h"
111 #include "tree-ssa-loop.h"
112 #include "tree-ssa.h"
114 #include "tree-data-ref.h"
115 #include "tree-scalar-evolution.h"
116 #include "dumpfile.h"
117 #include "langhooks.h"
118 #include "tree-affine.h"
121 static struct datadep_stats
123 int num_dependence_tests
;
124 int num_dependence_dependent
;
125 int num_dependence_independent
;
126 int num_dependence_undetermined
;
128 int num_subscript_tests
;
129 int num_subscript_undetermined
;
130 int num_same_subscript_function
;
133 int num_ziv_independent
;
134 int num_ziv_dependent
;
135 int num_ziv_unimplemented
;
138 int num_siv_independent
;
139 int num_siv_dependent
;
140 int num_siv_unimplemented
;
143 int num_miv_independent
;
144 int num_miv_dependent
;
145 int num_miv_unimplemented
;
148 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
149 struct data_reference
*,
150 struct data_reference
*,
152 /* Returns true iff A divides B. */
155 tree_fold_divides_p (const_tree a
, const_tree b
)
157 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
158 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
159 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
));
162 /* Returns true iff A divides B. */
165 int_divides_p (int a
, int b
)
167 return ((b
% a
) == 0);
172 /* Dump into FILE all the data references from DATAREFS. */
175 dump_data_references (FILE *file
, vec
<data_reference_p
> datarefs
)
178 struct data_reference
*dr
;
180 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
181 dump_data_reference (file
, dr
);
184 /* Unified dump into FILE all the data references from DATAREFS. */
187 debug (vec
<data_reference_p
> &ref
)
189 dump_data_references (stderr
, ref
);
193 debug (vec
<data_reference_p
> *ptr
)
198 fprintf (stderr
, "<nil>\n");
202 /* Dump into STDERR all the data references from DATAREFS. */
205 debug_data_references (vec
<data_reference_p
> datarefs
)
207 dump_data_references (stderr
, datarefs
);
210 /* Print to STDERR the data_reference DR. */
213 debug_data_reference (struct data_reference
*dr
)
215 dump_data_reference (stderr
, dr
);
218 /* Dump function for a DATA_REFERENCE structure. */
221 dump_data_reference (FILE *outf
,
222 struct data_reference
*dr
)
226 fprintf (outf
, "#(Data Ref: \n");
227 fprintf (outf
, "# bb: %d \n", gimple_bb (DR_STMT (dr
))->index
);
228 fprintf (outf
, "# stmt: ");
229 print_gimple_stmt (outf
, DR_STMT (dr
), 0, 0);
230 fprintf (outf
, "# ref: ");
231 print_generic_stmt (outf
, DR_REF (dr
), 0);
232 fprintf (outf
, "# base_object: ");
233 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
235 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
237 fprintf (outf
, "# Access function %d: ", i
);
238 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
240 fprintf (outf
, "#)\n");
243 /* Unified dump function for a DATA_REFERENCE structure. */
246 debug (data_reference
&ref
)
248 dump_data_reference (stderr
, &ref
);
252 debug (data_reference
*ptr
)
257 fprintf (stderr
, "<nil>\n");
261 /* Dumps the affine function described by FN to the file OUTF. */
264 dump_affine_function (FILE *outf
, affine_fn fn
)
269 print_generic_expr (outf
, fn
[0], TDF_SLIM
);
270 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
272 fprintf (outf
, " + ");
273 print_generic_expr (outf
, coef
, TDF_SLIM
);
274 fprintf (outf
, " * x_%u", i
);
278 /* Dumps the conflict function CF to the file OUTF. */
281 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
285 if (cf
->n
== NO_DEPENDENCE
)
286 fprintf (outf
, "no dependence");
287 else if (cf
->n
== NOT_KNOWN
)
288 fprintf (outf
, "not known");
291 for (i
= 0; i
< cf
->n
; i
++)
296 dump_affine_function (outf
, cf
->fns
[i
]);
302 /* Dump function for a SUBSCRIPT structure. */
305 dump_subscript (FILE *outf
, struct subscript
*subscript
)
307 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
309 fprintf (outf
, "\n (subscript \n");
310 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
311 dump_conflict_function (outf
, cf
);
312 if (CF_NONTRIVIAL_P (cf
))
314 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
315 fprintf (outf
, "\n last_conflict: ");
316 print_generic_expr (outf
, last_iteration
, 0);
319 cf
= SUB_CONFLICTS_IN_B (subscript
);
320 fprintf (outf
, "\n iterations_that_access_an_element_twice_in_B: ");
321 dump_conflict_function (outf
, cf
);
322 if (CF_NONTRIVIAL_P (cf
))
324 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
325 fprintf (outf
, "\n last_conflict: ");
326 print_generic_expr (outf
, last_iteration
, 0);
329 fprintf (outf
, "\n (Subscript distance: ");
330 print_generic_expr (outf
, SUB_DISTANCE (subscript
), 0);
331 fprintf (outf
, " ))\n");
334 /* Print the classic direction vector DIRV to OUTF. */
337 print_direction_vector (FILE *outf
,
343 for (eq
= 0; eq
< length
; eq
++)
345 enum data_dependence_direction dir
= ((enum data_dependence_direction
)
351 fprintf (outf
, " +");
354 fprintf (outf
, " -");
357 fprintf (outf
, " =");
359 case dir_positive_or_equal
:
360 fprintf (outf
, " +=");
362 case dir_positive_or_negative
:
363 fprintf (outf
, " +-");
365 case dir_negative_or_equal
:
366 fprintf (outf
, " -=");
369 fprintf (outf
, " *");
372 fprintf (outf
, "indep");
376 fprintf (outf
, "\n");
379 /* Print a vector of direction vectors. */
382 print_dir_vectors (FILE *outf
, vec
<lambda_vector
> dir_vects
,
388 FOR_EACH_VEC_ELT (dir_vects
, j
, v
)
389 print_direction_vector (outf
, v
, length
);
392 /* Print out a vector VEC of length N to OUTFILE. */
395 print_lambda_vector (FILE * outfile
, lambda_vector vector
, int n
)
399 for (i
= 0; i
< n
; i
++)
400 fprintf (outfile
, "%3d ", vector
[i
]);
401 fprintf (outfile
, "\n");
404 /* Print a vector of distance vectors. */
407 print_dist_vectors (FILE *outf
, vec
<lambda_vector
> dist_vects
,
413 FOR_EACH_VEC_ELT (dist_vects
, j
, v
)
414 print_lambda_vector (outf
, v
, length
);
417 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
420 dump_data_dependence_relation (FILE *outf
,
421 struct data_dependence_relation
*ddr
)
423 struct data_reference
*dra
, *drb
;
425 fprintf (outf
, "(Data Dep: \n");
427 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
434 dump_data_reference (outf
, dra
);
436 fprintf (outf
, " (nil)\n");
438 dump_data_reference (outf
, drb
);
440 fprintf (outf
, " (nil)\n");
442 fprintf (outf
, " (don't know)\n)\n");
448 dump_data_reference (outf
, dra
);
449 dump_data_reference (outf
, drb
);
451 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
452 fprintf (outf
, " (no dependence)\n");
454 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
459 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
461 fprintf (outf
, " access_fn_A: ");
462 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
463 fprintf (outf
, " access_fn_B: ");
464 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
465 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
468 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
469 fprintf (outf
, " loop nest: (");
470 FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr
), i
, loopi
)
471 fprintf (outf
, "%d ", loopi
->num
);
472 fprintf (outf
, ")\n");
474 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
476 fprintf (outf
, " distance_vector: ");
477 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
481 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
483 fprintf (outf
, " direction_vector: ");
484 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
489 fprintf (outf
, ")\n");
495 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
497 dump_data_dependence_relation (stderr
, ddr
);
500 /* Dump into FILE all the dependence relations from DDRS. */
503 dump_data_dependence_relations (FILE *file
,
507 struct data_dependence_relation
*ddr
;
509 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
510 dump_data_dependence_relation (file
, ddr
);
514 debug (vec
<ddr_p
> &ref
)
516 dump_data_dependence_relations (stderr
, ref
);
520 debug (vec
<ddr_p
> *ptr
)
525 fprintf (stderr
, "<nil>\n");
529 /* Dump to STDERR all the dependence relations from DDRS. */
532 debug_data_dependence_relations (vec
<ddr_p
> ddrs
)
534 dump_data_dependence_relations (stderr
, ddrs
);
537 /* Dumps the distance and direction vectors in FILE. DDRS contains
538 the dependence relations, and VECT_SIZE is the size of the
539 dependence vectors, or in other words the number of loops in the
543 dump_dist_dir_vectors (FILE *file
, vec
<ddr_p
> ddrs
)
546 struct data_dependence_relation
*ddr
;
549 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
550 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
552 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), j
, v
)
554 fprintf (file
, "DISTANCE_V (");
555 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
556 fprintf (file
, ")\n");
559 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), j
, v
)
561 fprintf (file
, "DIRECTION_V (");
562 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
563 fprintf (file
, ")\n");
567 fprintf (file
, "\n\n");
570 /* Dumps the data dependence relations DDRS in FILE. */
573 dump_ddrs (FILE *file
, vec
<ddr_p
> ddrs
)
576 struct data_dependence_relation
*ddr
;
578 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
579 dump_data_dependence_relation (file
, ddr
);
581 fprintf (file
, "\n\n");
585 debug_ddrs (vec
<ddr_p
> ddrs
)
587 dump_ddrs (stderr
, ddrs
);
590 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
591 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
592 constant of type ssizetype, and returns true. If we cannot do this
593 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
597 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
598 tree
*var
, tree
*off
)
602 enum tree_code ocode
= code
;
610 *var
= build_int_cst (type
, 0);
611 *off
= fold_convert (ssizetype
, op0
);
614 case POINTER_PLUS_EXPR
:
619 split_constant_offset (op0
, &var0
, &off0
);
620 split_constant_offset (op1
, &var1
, &off1
);
621 *var
= fold_build2 (code
, type
, var0
, var1
);
622 *off
= size_binop (ocode
, off0
, off1
);
626 if (TREE_CODE (op1
) != INTEGER_CST
)
629 split_constant_offset (op0
, &var0
, &off0
);
630 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
631 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
637 HOST_WIDE_INT pbitsize
, pbitpos
;
639 int punsignedp
, preversep
, pvolatilep
;
641 op0
= TREE_OPERAND (op0
, 0);
643 = get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
, &pmode
,
644 &punsignedp
, &preversep
, &pvolatilep
, false);
646 if (pbitpos
% BITS_PER_UNIT
!= 0)
648 base
= build_fold_addr_expr (base
);
649 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
653 split_constant_offset (poffset
, &poffset
, &off1
);
654 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
655 if (POINTER_TYPE_P (TREE_TYPE (base
)))
656 base
= fold_build_pointer_plus (base
, poffset
);
658 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
659 fold_convert (TREE_TYPE (base
), poffset
));
662 var0
= fold_convert (type
, base
);
664 /* If variable length types are involved, punt, otherwise casts
665 might be converted into ARRAY_REFs in gimplify_conversion.
666 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
667 possibly no longer appears in current GIMPLE, might resurface.
668 This perhaps could run
669 if (CONVERT_EXPR_P (var0))
671 gimplify_conversion (&var0);
672 // Attempt to fill in any within var0 found ARRAY_REF's
673 // element size from corresponding op embedded ARRAY_REF,
674 // if unsuccessful, just punt.
676 while (POINTER_TYPE_P (type
))
677 type
= TREE_TYPE (type
);
678 if (int_size_in_bytes (type
) < 0)
688 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
))
691 gimple def_stmt
= SSA_NAME_DEF_STMT (op0
);
692 enum tree_code subcode
;
694 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
697 var0
= gimple_assign_rhs1 (def_stmt
);
698 subcode
= gimple_assign_rhs_code (def_stmt
);
699 var1
= gimple_assign_rhs2 (def_stmt
);
701 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
705 /* We must not introduce undefined overflow, and we must not change the value.
706 Hence we're okay if the inner type doesn't overflow to start with
707 (pointer or signed), the outer type also is an integer or pointer
708 and the outer precision is at least as large as the inner. */
709 tree itype
= TREE_TYPE (op0
);
710 if ((POINTER_TYPE_P (itype
)
711 || (INTEGRAL_TYPE_P (itype
) && TYPE_OVERFLOW_UNDEFINED (itype
)))
712 && TYPE_PRECISION (type
) >= TYPE_PRECISION (itype
)
713 && (POINTER_TYPE_P (type
) || INTEGRAL_TYPE_P (type
)))
715 split_constant_offset (op0
, &var0
, off
);
716 *var
= fold_convert (type
, var0
);
727 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
728 will be ssizetype. */
731 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
733 tree type
= TREE_TYPE (exp
), otype
, op0
, op1
, e
, o
;
737 *off
= ssize_int (0);
740 if (tree_is_chrec (exp
)
741 || get_gimple_rhs_class (TREE_CODE (exp
)) == GIMPLE_TERNARY_RHS
)
744 otype
= TREE_TYPE (exp
);
745 code
= TREE_CODE (exp
);
746 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
747 if (split_constant_offset_1 (otype
, op0
, code
, op1
, &e
, &o
))
749 *var
= fold_convert (type
, e
);
754 /* Returns the address ADDR of an object in a canonical shape (without nop
755 casts, and with type of pointer to the object). */
758 canonicalize_base_object_address (tree addr
)
764 /* The base address may be obtained by casting from integer, in that case
766 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
769 if (TREE_CODE (addr
) != ADDR_EXPR
)
772 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
775 /* Analyzes the behavior of the memory reference DR in the innermost loop or
776 basic block that contains it. Returns true if analysis succeed or false
780 dr_analyze_innermost (struct data_reference
*dr
, struct loop
*nest
)
782 gimple stmt
= DR_STMT (dr
);
783 struct loop
*loop
= loop_containing_stmt (stmt
);
784 tree ref
= DR_REF (dr
);
785 HOST_WIDE_INT pbitsize
, pbitpos
;
788 int punsignedp
, preversep
, pvolatilep
;
789 affine_iv base_iv
, offset_iv
;
790 tree init
, dinit
, step
;
791 bool in_loop
= (loop
&& loop
->num
);
793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
794 fprintf (dump_file
, "analyze_innermost: ");
796 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
, &pmode
,
797 &punsignedp
, &preversep
, &pvolatilep
, false);
798 gcc_assert (base
!= NULL_TREE
);
800 if (pbitpos
% BITS_PER_UNIT
!= 0)
802 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
803 fprintf (dump_file
, "failed: bit offset alignment.\n");
809 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
810 fprintf (dump_file
, "failed: reverse storage order.\n");
814 if (TREE_CODE (base
) == MEM_REF
)
816 if (!integer_zerop (TREE_OPERAND (base
, 1)))
818 offset_int moff
= mem_ref_offset (base
);
819 tree mofft
= wide_int_to_tree (sizetype
, moff
);
823 poffset
= size_binop (PLUS_EXPR
, poffset
, mofft
);
825 base
= TREE_OPERAND (base
, 0);
828 base
= build_fold_addr_expr (base
);
832 if (!simple_iv (loop
, loop_containing_stmt (stmt
), base
, &base_iv
,
833 nest
? true : false))
837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
838 fprintf (dump_file
, "failed: evolution of base is not"
845 base_iv
.step
= ssize_int (0);
846 base_iv
.no_overflow
= true;
853 base_iv
.step
= ssize_int (0);
854 base_iv
.no_overflow
= true;
859 offset_iv
.base
= ssize_int (0);
860 offset_iv
.step
= ssize_int (0);
866 offset_iv
.base
= poffset
;
867 offset_iv
.step
= ssize_int (0);
869 else if (!simple_iv (loop
, loop_containing_stmt (stmt
),
871 nest
? true : false))
875 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 fprintf (dump_file
, "failed: evolution of offset is not"
882 offset_iv
.base
= poffset
;
883 offset_iv
.step
= ssize_int (0);
888 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
889 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
890 init
= size_binop (PLUS_EXPR
, init
, dinit
);
891 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
892 init
= size_binop (PLUS_EXPR
, init
, dinit
);
894 step
= size_binop (PLUS_EXPR
,
895 fold_convert (ssizetype
, base_iv
.step
),
896 fold_convert (ssizetype
, offset_iv
.step
));
898 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
900 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
904 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
906 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
907 fprintf (dump_file
, "success.\n");
912 /* Determines the base object and the list of indices of memory reference
913 DR, analyzed in LOOP and instantiated in loop nest NEST. */
916 dr_analyze_indices (struct data_reference
*dr
, loop_p nest
, loop_p loop
)
918 vec
<tree
> access_fns
= vNULL
;
920 tree base
, off
, access_fn
;
921 basic_block before_loop
;
923 /* If analyzing a basic-block there are no indices to analyze
924 and thus no access functions. */
927 DR_BASE_OBJECT (dr
) = DR_REF (dr
);
928 DR_ACCESS_FNS (dr
).create (0);
933 before_loop
= block_before_loop (nest
);
935 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
936 into a two element array with a constant index. The base is
937 then just the immediate underlying object. */
938 if (TREE_CODE (ref
) == REALPART_EXPR
)
940 ref
= TREE_OPERAND (ref
, 0);
941 access_fns
.safe_push (integer_zero_node
);
943 else if (TREE_CODE (ref
) == IMAGPART_EXPR
)
945 ref
= TREE_OPERAND (ref
, 0);
946 access_fns
.safe_push (integer_one_node
);
949 /* Analyze access functions of dimensions we know to be independent. */
950 while (handled_component_p (ref
))
952 if (TREE_CODE (ref
) == ARRAY_REF
)
954 op
= TREE_OPERAND (ref
, 1);
955 access_fn
= analyze_scalar_evolution (loop
, op
);
956 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
957 access_fns
.safe_push (access_fn
);
959 else if (TREE_CODE (ref
) == COMPONENT_REF
960 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref
, 0))) == RECORD_TYPE
)
962 /* For COMPONENT_REFs of records (but not unions!) use the
963 FIELD_DECL offset as constant access function so we can
964 disambiguate a[i].f1 and a[i].f2. */
965 tree off
= component_ref_field_offset (ref
);
966 off
= size_binop (PLUS_EXPR
,
967 size_binop (MULT_EXPR
,
968 fold_convert (bitsizetype
, off
),
969 bitsize_int (BITS_PER_UNIT
)),
970 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1)));
971 access_fns
.safe_push (off
);
974 /* If we have an unhandled component we could not translate
975 to an access function stop analyzing. We have determined
976 our base object in this case. */
979 ref
= TREE_OPERAND (ref
, 0);
982 /* If the address operand of a MEM_REF base has an evolution in the
983 analyzed nest, add it as an additional independent access-function. */
984 if (TREE_CODE (ref
) == MEM_REF
)
986 op
= TREE_OPERAND (ref
, 0);
987 access_fn
= analyze_scalar_evolution (loop
, op
);
988 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
989 if (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
992 tree memoff
= TREE_OPERAND (ref
, 1);
993 base
= initial_condition (access_fn
);
994 orig_type
= TREE_TYPE (base
);
995 STRIP_USELESS_TYPE_CONVERSION (base
);
996 split_constant_offset (base
, &base
, &off
);
997 STRIP_USELESS_TYPE_CONVERSION (base
);
998 /* Fold the MEM_REF offset into the evolutions initial
999 value to make more bases comparable. */
1000 if (!integer_zerop (memoff
))
1002 off
= size_binop (PLUS_EXPR
, off
,
1003 fold_convert (ssizetype
, memoff
));
1004 memoff
= build_int_cst (TREE_TYPE (memoff
), 0);
1006 /* Adjust the offset so it is a multiple of the access type
1007 size and thus we separate bases that can possibly be used
1008 to produce partial overlaps (which the access_fn machinery
1011 if (TYPE_SIZE_UNIT (TREE_TYPE (ref
))
1012 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref
))) == INTEGER_CST
1013 && !integer_zerop (TYPE_SIZE_UNIT (TREE_TYPE (ref
))))
1014 rem
= wi::mod_trunc (off
, TYPE_SIZE_UNIT (TREE_TYPE (ref
)), SIGNED
);
1016 /* If we can't compute the remainder simply force the initial
1017 condition to zero. */
1019 off
= wide_int_to_tree (ssizetype
, wi::sub (off
, rem
));
1020 memoff
= wide_int_to_tree (TREE_TYPE (memoff
), rem
);
1021 /* And finally replace the initial condition. */
1022 access_fn
= chrec_replace_initial_condition
1023 (access_fn
, fold_convert (orig_type
, off
));
1024 /* ??? This is still not a suitable base object for
1025 dr_may_alias_p - the base object needs to be an
1026 access that covers the object as whole. With
1027 an evolution in the pointer this cannot be
1029 As a band-aid, mark the access so we can special-case
1030 it in dr_may_alias_p. */
1032 ref
= fold_build2_loc (EXPR_LOCATION (ref
),
1033 MEM_REF
, TREE_TYPE (ref
),
1035 MR_DEPENDENCE_CLIQUE (ref
) = MR_DEPENDENCE_CLIQUE (old
);
1036 MR_DEPENDENCE_BASE (ref
) = MR_DEPENDENCE_BASE (old
);
1037 DR_UNCONSTRAINED_BASE (dr
) = true;
1038 access_fns
.safe_push (access_fn
);
1041 else if (DECL_P (ref
))
1043 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
1044 ref
= build2 (MEM_REF
, TREE_TYPE (ref
),
1045 build_fold_addr_expr (ref
),
1046 build_int_cst (reference_alias_ptr_type (ref
), 0));
1049 DR_BASE_OBJECT (dr
) = ref
;
1050 DR_ACCESS_FNS (dr
) = access_fns
;
1053 /* Extracts the alias analysis information from the memory reference DR. */
1056 dr_analyze_alias (struct data_reference
*dr
)
1058 tree ref
= DR_REF (dr
);
1059 tree base
= get_base_address (ref
), addr
;
1061 if (INDIRECT_REF_P (base
)
1062 || TREE_CODE (base
) == MEM_REF
)
1064 addr
= TREE_OPERAND (base
, 0);
1065 if (TREE_CODE (addr
) == SSA_NAME
)
1066 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
1070 /* Frees data reference DR. */
1073 free_data_ref (data_reference_p dr
)
1075 DR_ACCESS_FNS (dr
).release ();
1079 /* Analyzes memory reference MEMREF accessed in STMT. The reference
1080 is read if IS_READ is true, write otherwise. Returns the
1081 data_reference description of MEMREF. NEST is the outermost loop
1082 in which the reference should be instantiated, LOOP is the loop in
1083 which the data reference should be analyzed. */
1085 struct data_reference
*
1086 create_data_ref (loop_p nest
, loop_p loop
, tree memref
, gimple stmt
,
1089 struct data_reference
*dr
;
1091 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1093 fprintf (dump_file
, "Creating dr for ");
1094 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1095 fprintf (dump_file
, "\n");
1098 dr
= XCNEW (struct data_reference
);
1099 DR_STMT (dr
) = stmt
;
1100 DR_REF (dr
) = memref
;
1101 DR_IS_READ (dr
) = is_read
;
1103 dr_analyze_innermost (dr
, nest
);
1104 dr_analyze_indices (dr
, nest
, loop
);
1105 dr_analyze_alias (dr
);
1107 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1110 fprintf (dump_file
, "\tbase_address: ");
1111 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
1112 fprintf (dump_file
, "\n\toffset from base address: ");
1113 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
1114 fprintf (dump_file
, "\n\tconstant offset from base address: ");
1115 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
1116 fprintf (dump_file
, "\n\tstep: ");
1117 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
1118 fprintf (dump_file
, "\n\taligned to: ");
1119 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
1120 fprintf (dump_file
, "\n\tbase_object: ");
1121 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
1122 fprintf (dump_file
, "\n");
1123 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
1125 fprintf (dump_file
, "\tAccess function %d: ", i
);
1126 print_generic_stmt (dump_file
, DR_ACCESS_FN (dr
, i
), TDF_SLIM
);
1133 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1136 dr_equal_offsets_p1 (tree offset1
, tree offset2
)
1140 STRIP_NOPS (offset1
);
1141 STRIP_NOPS (offset2
);
1143 if (offset1
== offset2
)
1146 if (TREE_CODE (offset1
) != TREE_CODE (offset2
)
1147 || (!BINARY_CLASS_P (offset1
) && !UNARY_CLASS_P (offset1
)))
1150 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 0),
1151 TREE_OPERAND (offset2
, 0));
1153 if (!res
|| !BINARY_CLASS_P (offset1
))
1156 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 1),
1157 TREE_OPERAND (offset2
, 1));
1162 /* Check if DRA and DRB have equal offsets. */
1164 dr_equal_offsets_p (struct data_reference
*dra
,
1165 struct data_reference
*drb
)
1167 tree offset1
, offset2
;
1169 offset1
= DR_OFFSET (dra
);
1170 offset2
= DR_OFFSET (drb
);
1172 return dr_equal_offsets_p1 (offset1
, offset2
);
1175 /* Returns true if FNA == FNB. */
1178 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
1180 unsigned i
, n
= fna
.length ();
1182 if (n
!= fnb
.length ())
1185 for (i
= 0; i
< n
; i
++)
1186 if (!operand_equal_p (fna
[i
], fnb
[i
], 0))
1192 /* If all the functions in CF are the same, returns one of them,
1193 otherwise returns NULL. */
1196 common_affine_function (conflict_function
*cf
)
1201 if (!CF_NONTRIVIAL_P (cf
))
1202 return affine_fn ();
1206 for (i
= 1; i
< cf
->n
; i
++)
1207 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
1208 return affine_fn ();
1213 /* Returns the base of the affine function FN. */
1216 affine_function_base (affine_fn fn
)
1221 /* Returns true if FN is a constant. */
1224 affine_function_constant_p (affine_fn fn
)
1229 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
1230 if (!integer_zerop (coef
))
1236 /* Returns true if FN is the zero constant function. */
1239 affine_function_zero_p (affine_fn fn
)
1241 return (integer_zerop (affine_function_base (fn
))
1242 && affine_function_constant_p (fn
));
1245 /* Returns a signed integer type with the largest precision from TA
1249 signed_type_for_types (tree ta
, tree tb
)
1251 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
1252 return signed_type_for (ta
);
1254 return signed_type_for (tb
);
1257 /* Applies operation OP on affine functions FNA and FNB, and returns the
1261 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
1267 if (fnb
.length () > fna
.length ())
1279 for (i
= 0; i
< n
; i
++)
1281 tree type
= signed_type_for_types (TREE_TYPE (fna
[i
]),
1282 TREE_TYPE (fnb
[i
]));
1283 ret
.quick_push (fold_build2 (op
, type
, fna
[i
], fnb
[i
]));
1286 for (; fna
.iterate (i
, &coef
); i
++)
1287 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1288 coef
, integer_zero_node
));
1289 for (; fnb
.iterate (i
, &coef
); i
++)
1290 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1291 integer_zero_node
, coef
));
1296 /* Returns the sum of affine functions FNA and FNB. */
1299 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1301 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1304 /* Returns the difference of affine functions FNA and FNB. */
1307 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1309 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1312 /* Frees affine function FN. */
1315 affine_fn_free (affine_fn fn
)
1320 /* Determine for each subscript in the data dependence relation DDR
1324 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1326 conflict_function
*cf_a
, *cf_b
;
1327 affine_fn fn_a
, fn_b
, diff
;
1329 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1333 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1335 struct subscript
*subscript
;
1337 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1338 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1339 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1341 fn_a
= common_affine_function (cf_a
);
1342 fn_b
= common_affine_function (cf_b
);
1343 if (!fn_a
.exists () || !fn_b
.exists ())
1345 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1348 diff
= affine_fn_minus (fn_a
, fn_b
);
1350 if (affine_function_constant_p (diff
))
1351 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1353 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1355 affine_fn_free (diff
);
1360 /* Returns the conflict function for "unknown". */
1362 static conflict_function
*
1363 conflict_fn_not_known (void)
1365 conflict_function
*fn
= XCNEW (conflict_function
);
1371 /* Returns the conflict function for "independent". */
1373 static conflict_function
*
1374 conflict_fn_no_dependence (void)
1376 conflict_function
*fn
= XCNEW (conflict_function
);
1377 fn
->n
= NO_DEPENDENCE
;
1382 /* Returns true if the address of OBJ is invariant in LOOP. */
1385 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1387 while (handled_component_p (obj
))
1389 if (TREE_CODE (obj
) == ARRAY_REF
)
1391 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1392 need to check the stride and the lower bound of the reference. */
1393 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1395 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1399 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1401 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1405 obj
= TREE_OPERAND (obj
, 0);
1408 if (!INDIRECT_REF_P (obj
)
1409 && TREE_CODE (obj
) != MEM_REF
)
1412 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1416 /* Returns false if we can prove that data references A and B do not alias,
1417 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1421 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
,
1424 tree addr_a
= DR_BASE_OBJECT (a
);
1425 tree addr_b
= DR_BASE_OBJECT (b
);
1427 /* If we are not processing a loop nest but scalar code we
1428 do not need to care about possible cross-iteration dependences
1429 and thus can process the full original reference. Do so,
1430 similar to how loop invariant motion applies extra offset-based
1434 aff_tree off1
, off2
;
1435 widest_int size1
, size2
;
1436 get_inner_reference_aff (DR_REF (a
), &off1
, &size1
);
1437 get_inner_reference_aff (DR_REF (b
), &off2
, &size2
);
1438 aff_combination_scale (&off1
, -1);
1439 aff_combination_add (&off2
, &off1
);
1440 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1444 if ((TREE_CODE (addr_a
) == MEM_REF
|| TREE_CODE (addr_a
) == TARGET_MEM_REF
)
1445 && (TREE_CODE (addr_b
) == MEM_REF
|| TREE_CODE (addr_b
) == TARGET_MEM_REF
)
1446 && MR_DEPENDENCE_CLIQUE (addr_a
) == MR_DEPENDENCE_CLIQUE (addr_b
)
1447 && MR_DEPENDENCE_BASE (addr_a
) != MR_DEPENDENCE_BASE (addr_b
))
1450 /* If we had an evolution in a pointer-based MEM_REF BASE_OBJECT we
1451 do not know the size of the base-object. So we cannot do any
1452 offset/overlap based analysis but have to rely on points-to
1453 information only. */
1454 if (TREE_CODE (addr_a
) == MEM_REF
1455 && (DR_UNCONSTRAINED_BASE (a
)
1456 || TREE_CODE (TREE_OPERAND (addr_a
, 0)) == SSA_NAME
))
1458 /* For true dependences we can apply TBAA. */
1459 if (flag_strict_aliasing
1460 && DR_IS_WRITE (a
) && DR_IS_READ (b
)
1461 && !alias_sets_conflict_p (get_alias_set (DR_REF (a
)),
1462 get_alias_set (DR_REF (b
))))
1464 if (TREE_CODE (addr_b
) == MEM_REF
)
1465 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1466 TREE_OPERAND (addr_b
, 0));
1468 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1469 build_fold_addr_expr (addr_b
));
1471 else if (TREE_CODE (addr_b
) == MEM_REF
1472 && (DR_UNCONSTRAINED_BASE (b
)
1473 || TREE_CODE (TREE_OPERAND (addr_b
, 0)) == SSA_NAME
))
1475 /* For true dependences we can apply TBAA. */
1476 if (flag_strict_aliasing
1477 && DR_IS_WRITE (a
) && DR_IS_READ (b
)
1478 && !alias_sets_conflict_p (get_alias_set (DR_REF (a
)),
1479 get_alias_set (DR_REF (b
))))
1481 if (TREE_CODE (addr_a
) == MEM_REF
)
1482 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1483 TREE_OPERAND (addr_b
, 0));
1485 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a
),
1486 TREE_OPERAND (addr_b
, 0));
1489 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
1490 that is being subsetted in the loop nest. */
1491 if (DR_IS_WRITE (a
) && DR_IS_WRITE (b
))
1492 return refs_output_dependent_p (addr_a
, addr_b
);
1493 else if (DR_IS_READ (a
) && DR_IS_WRITE (b
))
1494 return refs_anti_dependent_p (addr_a
, addr_b
);
1495 return refs_may_alias_p (addr_a
, addr_b
);
1498 /* Initialize a data dependence relation between data accesses A and
1499 B. NB_LOOPS is the number of loops surrounding the references: the
1500 size of the classic distance/direction vectors. */
1502 struct data_dependence_relation
*
1503 initialize_data_dependence_relation (struct data_reference
*a
,
1504 struct data_reference
*b
,
1505 vec
<loop_p
> loop_nest
)
1507 struct data_dependence_relation
*res
;
1510 res
= XNEW (struct data_dependence_relation
);
1513 DDR_LOOP_NEST (res
).create (0);
1514 DDR_REVERSED_P (res
) = false;
1515 DDR_SUBSCRIPTS (res
).create (0);
1516 DDR_DIR_VECTS (res
).create (0);
1517 DDR_DIST_VECTS (res
).create (0);
1519 if (a
== NULL
|| b
== NULL
)
1521 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1525 /* If the data references do not alias, then they are independent. */
1526 if (!dr_may_alias_p (a
, b
, loop_nest
.exists ()))
1528 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1532 /* The case where the references are exactly the same. */
1533 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1535 if (loop_nest
.exists ()
1536 && !object_address_invariant_in_loop_p (loop_nest
[0],
1537 DR_BASE_OBJECT (a
)))
1539 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1542 DDR_AFFINE_P (res
) = true;
1543 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1544 DDR_SUBSCRIPTS (res
).create (DR_NUM_DIMENSIONS (a
));
1545 DDR_LOOP_NEST (res
) = loop_nest
;
1546 DDR_INNER_LOOP (res
) = 0;
1547 DDR_SELF_REFERENCE (res
) = true;
1548 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1550 struct subscript
*subscript
;
1552 subscript
= XNEW (struct subscript
);
1553 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1554 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1555 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1556 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1557 DDR_SUBSCRIPTS (res
).safe_push (subscript
);
1562 /* If the references do not access the same object, we do not know
1563 whether they alias or not. */
1564 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1566 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1570 /* If the base of the object is not invariant in the loop nest, we cannot
1571 analyze it. TODO -- in fact, it would suffice to record that there may
1572 be arbitrary dependences in the loops where the base object varies. */
1573 if (loop_nest
.exists ()
1574 && !object_address_invariant_in_loop_p (loop_nest
[0],
1575 DR_BASE_OBJECT (a
)))
1577 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1581 /* If the number of dimensions of the access to not agree we can have
1582 a pointer access to a component of the array element type and an
1583 array access while the base-objects are still the same. Punt. */
1584 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
1586 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1590 DDR_AFFINE_P (res
) = true;
1591 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1592 DDR_SUBSCRIPTS (res
).create (DR_NUM_DIMENSIONS (a
));
1593 DDR_LOOP_NEST (res
) = loop_nest
;
1594 DDR_INNER_LOOP (res
) = 0;
1595 DDR_SELF_REFERENCE (res
) = false;
1597 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1599 struct subscript
*subscript
;
1601 subscript
= XNEW (struct subscript
);
1602 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1603 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1604 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1605 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1606 DDR_SUBSCRIPTS (res
).safe_push (subscript
);
1612 /* Frees memory used by the conflict function F. */
1615 free_conflict_function (conflict_function
*f
)
1619 if (CF_NONTRIVIAL_P (f
))
1621 for (i
= 0; i
< f
->n
; i
++)
1622 affine_fn_free (f
->fns
[i
]);
1627 /* Frees memory used by SUBSCRIPTS. */
1630 free_subscripts (vec
<subscript_p
> subscripts
)
1635 FOR_EACH_VEC_ELT (subscripts
, i
, s
)
1637 free_conflict_function (s
->conflicting_iterations_in_a
);
1638 free_conflict_function (s
->conflicting_iterations_in_b
);
1641 subscripts
.release ();
1644 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1648 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1651 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1652 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1653 DDR_SUBSCRIPTS (ddr
).create (0);
1656 /* The dependence relation DDR cannot be represented by a distance
1660 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1663 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1665 DDR_AFFINE_P (ddr
) = false;
1670 /* This section contains the classic Banerjee tests. */
1672 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1673 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1676 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1678 return (evolution_function_is_constant_p (chrec_a
)
1679 && evolution_function_is_constant_p (chrec_b
));
1682 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1683 variable, i.e., if the SIV (Single Index Variable) test is true. */
1686 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1688 if ((evolution_function_is_constant_p (chrec_a
)
1689 && evolution_function_is_univariate_p (chrec_b
))
1690 || (evolution_function_is_constant_p (chrec_b
)
1691 && evolution_function_is_univariate_p (chrec_a
)))
1694 if (evolution_function_is_univariate_p (chrec_a
)
1695 && evolution_function_is_univariate_p (chrec_b
))
1697 switch (TREE_CODE (chrec_a
))
1699 case POLYNOMIAL_CHREC
:
1700 switch (TREE_CODE (chrec_b
))
1702 case POLYNOMIAL_CHREC
:
1703 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1718 /* Creates a conflict function with N dimensions. The affine functions
1719 in each dimension follow. */
1721 static conflict_function
*
1722 conflict_fn (unsigned n
, ...)
1725 conflict_function
*ret
= XCNEW (conflict_function
);
1728 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1732 for (i
= 0; i
< n
; i
++)
1733 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1739 /* Returns constant affine function with value CST. */
1742 affine_fn_cst (tree cst
)
1746 fn
.quick_push (cst
);
1750 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1753 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1756 fn
.create (dim
+ 1);
1759 gcc_assert (dim
> 0);
1760 fn
.quick_push (cst
);
1761 for (i
= 1; i
< dim
; i
++)
1762 fn
.quick_push (integer_zero_node
);
1763 fn
.quick_push (coef
);
1767 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1768 *OVERLAPS_B are initialized to the functions that describe the
1769 relation between the elements accessed twice by CHREC_A and
1770 CHREC_B. For k >= 0, the following property is verified:
1772 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1775 analyze_ziv_subscript (tree chrec_a
,
1777 conflict_function
**overlaps_a
,
1778 conflict_function
**overlaps_b
,
1779 tree
*last_conflicts
)
1781 tree type
, difference
;
1782 dependence_stats
.num_ziv
++;
1784 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1785 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1787 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1788 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1789 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1790 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1792 switch (TREE_CODE (difference
))
1795 if (integer_zerop (difference
))
1797 /* The difference is equal to zero: the accessed index
1798 overlaps for each iteration in the loop. */
1799 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1800 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1801 *last_conflicts
= chrec_dont_know
;
1802 dependence_stats
.num_ziv_dependent
++;
1806 /* The accesses do not overlap. */
1807 *overlaps_a
= conflict_fn_no_dependence ();
1808 *overlaps_b
= conflict_fn_no_dependence ();
1809 *last_conflicts
= integer_zero_node
;
1810 dependence_stats
.num_ziv_independent
++;
1815 /* We're not sure whether the indexes overlap. For the moment,
1816 conservatively answer "don't know". */
1817 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1818 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1820 *overlaps_a
= conflict_fn_not_known ();
1821 *overlaps_b
= conflict_fn_not_known ();
1822 *last_conflicts
= chrec_dont_know
;
1823 dependence_stats
.num_ziv_unimplemented
++;
1827 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1828 fprintf (dump_file
, ")\n");
1831 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1832 and only if it fits to the int type. If this is not the case, or the
1833 bound on the number of iterations of LOOP could not be derived, returns
1837 max_stmt_executions_tree (struct loop
*loop
)
1841 if (!max_stmt_executions (loop
, &nit
))
1842 return chrec_dont_know
;
1844 if (!wi::fits_to_tree_p (nit
, unsigned_type_node
))
1845 return chrec_dont_know
;
1847 return wide_int_to_tree (unsigned_type_node
, nit
);
1850 /* Determine whether the CHREC is always positive/negative. If the expression
1851 cannot be statically analyzed, return false, otherwise set the answer into
1855 chrec_is_positive (tree chrec
, bool *value
)
1857 bool value0
, value1
, value2
;
1858 tree end_value
, nb_iter
;
1860 switch (TREE_CODE (chrec
))
1862 case POLYNOMIAL_CHREC
:
1863 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
1864 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
1867 /* FIXME -- overflows. */
1868 if (value0
== value1
)
1874 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
1875 and the proof consists in showing that the sign never
1876 changes during the execution of the loop, from 0 to
1877 loop->nb_iterations. */
1878 if (!evolution_function_is_affine_p (chrec
))
1881 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
1882 if (chrec_contains_undetermined (nb_iter
))
1886 /* TODO -- If the test is after the exit, we may decrease the number of
1887 iterations by one. */
1889 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
1892 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
1894 if (!chrec_is_positive (end_value
, &value2
))
1898 return value0
== value1
;
1901 switch (tree_int_cst_sgn (chrec
))
1920 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1921 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1922 *OVERLAPS_B are initialized to the functions that describe the
1923 relation between the elements accessed twice by CHREC_A and
1924 CHREC_B. For k >= 0, the following property is verified:
1926 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1929 analyze_siv_subscript_cst_affine (tree chrec_a
,
1931 conflict_function
**overlaps_a
,
1932 conflict_function
**overlaps_b
,
1933 tree
*last_conflicts
)
1935 bool value0
, value1
, value2
;
1936 tree type
, difference
, tmp
;
1938 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1939 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1940 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1941 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1943 /* Special case overlap in the first iteration. */
1944 if (integer_zerop (difference
))
1946 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1947 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1948 *last_conflicts
= integer_one_node
;
1952 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1954 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1955 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1957 dependence_stats
.num_siv_unimplemented
++;
1958 *overlaps_a
= conflict_fn_not_known ();
1959 *overlaps_b
= conflict_fn_not_known ();
1960 *last_conflicts
= chrec_dont_know
;
1965 if (value0
== false)
1967 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1969 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1970 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1972 *overlaps_a
= conflict_fn_not_known ();
1973 *overlaps_b
= conflict_fn_not_known ();
1974 *last_conflicts
= chrec_dont_know
;
1975 dependence_stats
.num_siv_unimplemented
++;
1984 chrec_b = {10, +, 1}
1987 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1989 HOST_WIDE_INT numiter
;
1990 struct loop
*loop
= get_chrec_loop (chrec_b
);
1992 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1993 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1994 fold_build1 (ABS_EXPR
, type
, difference
),
1995 CHREC_RIGHT (chrec_b
));
1996 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1997 *last_conflicts
= integer_one_node
;
2000 /* Perform weak-zero siv test to see if overlap is
2001 outside the loop bounds. */
2002 numiter
= max_stmt_executions_int (loop
);
2005 && compare_tree_int (tmp
, numiter
) > 0)
2007 free_conflict_function (*overlaps_a
);
2008 free_conflict_function (*overlaps_b
);
2009 *overlaps_a
= conflict_fn_no_dependence ();
2010 *overlaps_b
= conflict_fn_no_dependence ();
2011 *last_conflicts
= integer_zero_node
;
2012 dependence_stats
.num_siv_independent
++;
2015 dependence_stats
.num_siv_dependent
++;
2019 /* When the step does not divide the difference, there are
2023 *overlaps_a
= conflict_fn_no_dependence ();
2024 *overlaps_b
= conflict_fn_no_dependence ();
2025 *last_conflicts
= integer_zero_node
;
2026 dependence_stats
.num_siv_independent
++;
2035 chrec_b = {10, +, -1}
2037 In this case, chrec_a will not overlap with chrec_b. */
2038 *overlaps_a
= conflict_fn_no_dependence ();
2039 *overlaps_b
= conflict_fn_no_dependence ();
2040 *last_conflicts
= integer_zero_node
;
2041 dependence_stats
.num_siv_independent
++;
2048 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
2050 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2051 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
2053 *overlaps_a
= conflict_fn_not_known ();
2054 *overlaps_b
= conflict_fn_not_known ();
2055 *last_conflicts
= chrec_dont_know
;
2056 dependence_stats
.num_siv_unimplemented
++;
2061 if (value2
== false)
2065 chrec_b = {10, +, -1}
2067 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
2069 HOST_WIDE_INT numiter
;
2070 struct loop
*loop
= get_chrec_loop (chrec_b
);
2072 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2073 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
2074 CHREC_RIGHT (chrec_b
));
2075 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
2076 *last_conflicts
= integer_one_node
;
2078 /* Perform weak-zero siv test to see if overlap is
2079 outside the loop bounds. */
2080 numiter
= max_stmt_executions_int (loop
);
2083 && compare_tree_int (tmp
, numiter
) > 0)
2085 free_conflict_function (*overlaps_a
);
2086 free_conflict_function (*overlaps_b
);
2087 *overlaps_a
= conflict_fn_no_dependence ();
2088 *overlaps_b
= conflict_fn_no_dependence ();
2089 *last_conflicts
= integer_zero_node
;
2090 dependence_stats
.num_siv_independent
++;
2093 dependence_stats
.num_siv_dependent
++;
2097 /* When the step does not divide the difference, there
2101 *overlaps_a
= conflict_fn_no_dependence ();
2102 *overlaps_b
= conflict_fn_no_dependence ();
2103 *last_conflicts
= integer_zero_node
;
2104 dependence_stats
.num_siv_independent
++;
2114 In this case, chrec_a will not overlap with chrec_b. */
2115 *overlaps_a
= conflict_fn_no_dependence ();
2116 *overlaps_b
= conflict_fn_no_dependence ();
2117 *last_conflicts
= integer_zero_node
;
2118 dependence_stats
.num_siv_independent
++;
2126 /* Helper recursive function for initializing the matrix A. Returns
2127 the initial value of CHREC. */
2130 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
2134 switch (TREE_CODE (chrec
))
2136 case POLYNOMIAL_CHREC
:
2137 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
2139 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
2140 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
2146 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2147 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
2149 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
2154 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2155 return chrec_convert (chrec_type (chrec
), op
, NULL
);
2160 /* Handle ~X as -1 - X. */
2161 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2162 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
2163 build_int_cst (TREE_TYPE (chrec
), -1), op
);
2175 #define FLOOR_DIV(x,y) ((x) / (y))
2177 /* Solves the special case of the Diophantine equation:
2178 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2180 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2181 number of iterations that loops X and Y run. The overlaps will be
2182 constructed as evolutions in dimension DIM. */
2185 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
2186 affine_fn
*overlaps_a
,
2187 affine_fn
*overlaps_b
,
2188 tree
*last_conflicts
, int dim
)
2190 if (((step_a
> 0 && step_b
> 0)
2191 || (step_a
< 0 && step_b
< 0)))
2193 int step_overlaps_a
, step_overlaps_b
;
2194 int gcd_steps_a_b
, last_conflict
, tau2
;
2196 gcd_steps_a_b
= gcd (step_a
, step_b
);
2197 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2198 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2202 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2203 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2204 last_conflict
= tau2
;
2205 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2208 *last_conflicts
= chrec_dont_know
;
2210 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
2211 build_int_cst (NULL_TREE
,
2213 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
2214 build_int_cst (NULL_TREE
,
2220 *overlaps_a
= affine_fn_cst (integer_zero_node
);
2221 *overlaps_b
= affine_fn_cst (integer_zero_node
);
2222 *last_conflicts
= integer_zero_node
;
2226 /* Solves the special case of a Diophantine equation where CHREC_A is
2227 an affine bivariate function, and CHREC_B is an affine univariate
2228 function. For example,
2230 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2232 has the following overlapping functions:
2234 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2235 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2236 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2238 FORNOW: This is a specialized implementation for a case occurring in
2239 a common benchmark. Implement the general algorithm. */
2242 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2243 conflict_function
**overlaps_a
,
2244 conflict_function
**overlaps_b
,
2245 tree
*last_conflicts
)
2247 bool xz_p
, yz_p
, xyz_p
;
2248 int step_x
, step_y
, step_z
;
2249 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
2250 affine_fn overlaps_a_xz
, overlaps_b_xz
;
2251 affine_fn overlaps_a_yz
, overlaps_b_yz
;
2252 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
2253 affine_fn ova1
, ova2
, ovb
;
2254 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
2256 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2257 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2258 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2260 niter_x
= max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a
)));
2261 niter_y
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
2262 niter_z
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
2264 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2267 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2269 *overlaps_a
= conflict_fn_not_known ();
2270 *overlaps_b
= conflict_fn_not_known ();
2271 *last_conflicts
= chrec_dont_know
;
2275 niter
= MIN (niter_x
, niter_z
);
2276 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2279 &last_conflicts_xz
, 1);
2280 niter
= MIN (niter_y
, niter_z
);
2281 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2284 &last_conflicts_yz
, 2);
2285 niter
= MIN (niter_x
, niter_z
);
2286 niter
= MIN (niter_y
, niter
);
2287 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2290 &last_conflicts_xyz
, 3);
2292 xz_p
= !integer_zerop (last_conflicts_xz
);
2293 yz_p
= !integer_zerop (last_conflicts_yz
);
2294 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2296 if (xz_p
|| yz_p
|| xyz_p
)
2298 ova1
= affine_fn_cst (integer_zero_node
);
2299 ova2
= affine_fn_cst (integer_zero_node
);
2300 ovb
= affine_fn_cst (integer_zero_node
);
2303 affine_fn t0
= ova1
;
2306 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2307 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2308 affine_fn_free (t0
);
2309 affine_fn_free (t2
);
2310 *last_conflicts
= last_conflicts_xz
;
2314 affine_fn t0
= ova2
;
2317 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2318 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2319 affine_fn_free (t0
);
2320 affine_fn_free (t2
);
2321 *last_conflicts
= last_conflicts_yz
;
2325 affine_fn t0
= ova1
;
2326 affine_fn t2
= ova2
;
2329 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2330 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2331 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2332 affine_fn_free (t0
);
2333 affine_fn_free (t2
);
2334 affine_fn_free (t4
);
2335 *last_conflicts
= last_conflicts_xyz
;
2337 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2338 *overlaps_b
= conflict_fn (1, ovb
);
2342 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2343 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2344 *last_conflicts
= integer_zero_node
;
2347 affine_fn_free (overlaps_a_xz
);
2348 affine_fn_free (overlaps_b_xz
);
2349 affine_fn_free (overlaps_a_yz
);
2350 affine_fn_free (overlaps_b_yz
);
2351 affine_fn_free (overlaps_a_xyz
);
2352 affine_fn_free (overlaps_b_xyz
);
2355 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2358 lambda_vector_copy (lambda_vector vec1
, lambda_vector vec2
,
2361 memcpy (vec2
, vec1
, size
* sizeof (*vec1
));
2364 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2367 lambda_matrix_copy (lambda_matrix mat1
, lambda_matrix mat2
,
2372 for (i
= 0; i
< m
; i
++)
2373 lambda_vector_copy (mat1
[i
], mat2
[i
], n
);
2376 /* Store the N x N identity matrix in MAT. */
2379 lambda_matrix_id (lambda_matrix mat
, int size
)
2383 for (i
= 0; i
< size
; i
++)
2384 for (j
= 0; j
< size
; j
++)
2385 mat
[i
][j
] = (i
== j
) ? 1 : 0;
2388 /* Return the first nonzero element of vector VEC1 between START and N.
2389 We must have START <= N. Returns N if VEC1 is the zero vector. */
2392 lambda_vector_first_nz (lambda_vector vec1
, int n
, int start
)
2395 while (j
< n
&& vec1
[j
] == 0)
2400 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2401 R2 = R2 + CONST1 * R1. */
2404 lambda_matrix_row_add (lambda_matrix mat
, int n
, int r1
, int r2
, int const1
)
2411 for (i
= 0; i
< n
; i
++)
2412 mat
[r2
][i
] += const1
* mat
[r1
][i
];
2415 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2416 and store the result in VEC2. */
2419 lambda_vector_mult_const (lambda_vector vec1
, lambda_vector vec2
,
2420 int size
, int const1
)
2425 lambda_vector_clear (vec2
, size
);
2427 for (i
= 0; i
< size
; i
++)
2428 vec2
[i
] = const1
* vec1
[i
];
2431 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2434 lambda_vector_negate (lambda_vector vec1
, lambda_vector vec2
,
2437 lambda_vector_mult_const (vec1
, vec2
, size
, -1);
2440 /* Negate row R1 of matrix MAT which has N columns. */
2443 lambda_matrix_row_negate (lambda_matrix mat
, int n
, int r1
)
2445 lambda_vector_negate (mat
[r1
], mat
[r1
], n
);
2448 /* Return true if two vectors are equal. */
2451 lambda_vector_equal (lambda_vector vec1
, lambda_vector vec2
, int size
)
2454 for (i
= 0; i
< size
; i
++)
2455 if (vec1
[i
] != vec2
[i
])
2460 /* Given an M x N integer matrix A, this function determines an M x
2461 M unimodular matrix U, and an M x N echelon matrix S such that
2462 "U.A = S". This decomposition is also known as "right Hermite".
2464 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2465 Restructuring Compilers" Utpal Banerjee. */
2468 lambda_matrix_right_hermite (lambda_matrix A
, int m
, int n
,
2469 lambda_matrix S
, lambda_matrix U
)
2473 lambda_matrix_copy (A
, S
, m
, n
);
2474 lambda_matrix_id (U
, m
);
2476 for (j
= 0; j
< n
; j
++)
2478 if (lambda_vector_first_nz (S
[j
], m
, i0
) < m
)
2481 for (i
= m
- 1; i
>= i0
; i
--)
2483 while (S
[i
][j
] != 0)
2485 int sigma
, factor
, a
, b
;
2489 sigma
= (a
* b
< 0) ? -1: 1;
2492 factor
= sigma
* (a
/ b
);
2494 lambda_matrix_row_add (S
, n
, i
, i
-1, -factor
);
2495 std::swap (S
[i
], S
[i
-1]);
2497 lambda_matrix_row_add (U
, m
, i
, i
-1, -factor
);
2498 std::swap (U
[i
], U
[i
-1]);
2505 /* Determines the overlapping elements due to accesses CHREC_A and
2506 CHREC_B, that are affine functions. This function cannot handle
2507 symbolic evolution functions, ie. when initial conditions are
2508 parameters, because it uses lambda matrices of integers. */
2511 analyze_subscript_affine_affine (tree chrec_a
,
2513 conflict_function
**overlaps_a
,
2514 conflict_function
**overlaps_b
,
2515 tree
*last_conflicts
)
2517 unsigned nb_vars_a
, nb_vars_b
, dim
;
2518 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2519 lambda_matrix A
, U
, S
;
2520 struct obstack scratch_obstack
;
2522 if (eq_evolutions_p (chrec_a
, chrec_b
))
2524 /* The accessed index overlaps for each iteration in the
2526 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2527 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2528 *last_conflicts
= chrec_dont_know
;
2531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2532 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2534 /* For determining the initial intersection, we have to solve a
2535 Diophantine equation. This is the most time consuming part.
2537 For answering to the question: "Is there a dependence?" we have
2538 to prove that there exists a solution to the Diophantine
2539 equation, and that the solution is in the iteration domain,
2540 i.e. the solution is positive or zero, and that the solution
2541 happens before the upper bound loop.nb_iterations. Otherwise
2542 there is no dependence. This function outputs a description of
2543 the iterations that hold the intersections. */
2545 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2546 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2548 gcc_obstack_init (&scratch_obstack
);
2550 dim
= nb_vars_a
+ nb_vars_b
;
2551 U
= lambda_matrix_new (dim
, dim
, &scratch_obstack
);
2552 A
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2553 S
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2555 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2556 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2557 gamma
= init_b
- init_a
;
2559 /* Don't do all the hard work of solving the Diophantine equation
2560 when we already know the solution: for example,
2563 | gamma = 3 - 3 = 0.
2564 Then the first overlap occurs during the first iterations:
2565 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2569 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2571 HOST_WIDE_INT step_a
, step_b
;
2572 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2575 niter_a
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
2576 niter_b
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
2577 niter
= MIN (niter_a
, niter_b
);
2578 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2579 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2581 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2584 *overlaps_a
= conflict_fn (1, ova
);
2585 *overlaps_b
= conflict_fn (1, ovb
);
2588 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2589 compute_overlap_steps_for_affine_1_2
2590 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2592 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2593 compute_overlap_steps_for_affine_1_2
2594 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2598 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2599 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2600 *overlaps_a
= conflict_fn_not_known ();
2601 *overlaps_b
= conflict_fn_not_known ();
2602 *last_conflicts
= chrec_dont_know
;
2604 goto end_analyze_subs_aa
;
2608 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2613 lambda_matrix_row_negate (U
, dim
, 0);
2615 gcd_alpha_beta
= S
[0][0];
2617 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2618 but that is a quite strange case. Instead of ICEing, answer
2620 if (gcd_alpha_beta
== 0)
2622 *overlaps_a
= conflict_fn_not_known ();
2623 *overlaps_b
= conflict_fn_not_known ();
2624 *last_conflicts
= chrec_dont_know
;
2625 goto end_analyze_subs_aa
;
2628 /* The classic "gcd-test". */
2629 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2631 /* The "gcd-test" has determined that there is no integer
2632 solution, i.e. there is no dependence. */
2633 *overlaps_a
= conflict_fn_no_dependence ();
2634 *overlaps_b
= conflict_fn_no_dependence ();
2635 *last_conflicts
= integer_zero_node
;
2638 /* Both access functions are univariate. This includes SIV and MIV cases. */
2639 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2641 /* Both functions should have the same evolution sign. */
2642 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2643 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2645 /* The solutions are given by:
2647 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2650 For a given integer t. Using the following variables,
2652 | i0 = u11 * gamma / gcd_alpha_beta
2653 | j0 = u12 * gamma / gcd_alpha_beta
2660 | y0 = j0 + j1 * t. */
2661 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2663 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2664 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2668 if ((i1
== 0 && i0
< 0)
2669 || (j1
== 0 && j0
< 0))
2671 /* There is no solution.
2672 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2673 falls in here, but for the moment we don't look at the
2674 upper bound of the iteration domain. */
2675 *overlaps_a
= conflict_fn_no_dependence ();
2676 *overlaps_b
= conflict_fn_no_dependence ();
2677 *last_conflicts
= integer_zero_node
;
2678 goto end_analyze_subs_aa
;
2681 if (i1
> 0 && j1
> 0)
2683 HOST_WIDE_INT niter_a
2684 = max_stmt_executions_int (get_chrec_loop (chrec_a
));
2685 HOST_WIDE_INT niter_b
2686 = max_stmt_executions_int (get_chrec_loop (chrec_b
));
2687 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2689 /* (X0, Y0) is a solution of the Diophantine equation:
2690 "chrec_a (X0) = chrec_b (Y0)". */
2691 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2693 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2694 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2696 /* (X1, Y1) is the smallest positive solution of the eq
2697 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2698 first conflict occurs. */
2699 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2700 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2701 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2705 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2706 FLOOR_DIV (niter
- j0
, j1
));
2707 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2709 /* If the overlap occurs outside of the bounds of the
2710 loop, there is no dependence. */
2711 if (x1
>= niter
|| y1
>= niter
)
2713 *overlaps_a
= conflict_fn_no_dependence ();
2714 *overlaps_b
= conflict_fn_no_dependence ();
2715 *last_conflicts
= integer_zero_node
;
2716 goto end_analyze_subs_aa
;
2719 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2722 *last_conflicts
= chrec_dont_know
;
2726 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2728 build_int_cst (NULL_TREE
, i1
)));
2731 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2733 build_int_cst (NULL_TREE
, j1
)));
2737 /* FIXME: For the moment, the upper bound of the
2738 iteration domain for i and j is not checked. */
2739 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2740 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2741 *overlaps_a
= conflict_fn_not_known ();
2742 *overlaps_b
= conflict_fn_not_known ();
2743 *last_conflicts
= chrec_dont_know
;
2748 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2749 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2750 *overlaps_a
= conflict_fn_not_known ();
2751 *overlaps_b
= conflict_fn_not_known ();
2752 *last_conflicts
= chrec_dont_know
;
2757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2758 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2759 *overlaps_a
= conflict_fn_not_known ();
2760 *overlaps_b
= conflict_fn_not_known ();
2761 *last_conflicts
= chrec_dont_know
;
2764 end_analyze_subs_aa
:
2765 obstack_free (&scratch_obstack
, NULL
);
2766 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2768 fprintf (dump_file
, " (overlaps_a = ");
2769 dump_conflict_function (dump_file
, *overlaps_a
);
2770 fprintf (dump_file
, ")\n (overlaps_b = ");
2771 dump_conflict_function (dump_file
, *overlaps_b
);
2772 fprintf (dump_file
, "))\n");
2776 /* Returns true when analyze_subscript_affine_affine can be used for
2777 determining the dependence relation between chrec_a and chrec_b,
2778 that contain symbols. This function modifies chrec_a and chrec_b
2779 such that the analysis result is the same, and such that they don't
2780 contain symbols, and then can safely be passed to the analyzer.
2782 Example: The analysis of the following tuples of evolutions produce
2783 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2786 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2787 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2791 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2793 tree diff
, type
, left_a
, left_b
, right_b
;
2795 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2796 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2797 /* FIXME: For the moment not handled. Might be refined later. */
2800 type
= chrec_type (*chrec_a
);
2801 left_a
= CHREC_LEFT (*chrec_a
);
2802 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2803 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2805 if (!evolution_function_is_constant_p (diff
))
2808 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2809 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2811 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2812 diff
, CHREC_RIGHT (*chrec_a
));
2813 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2814 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2815 build_int_cst (type
, 0),
2820 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2821 *OVERLAPS_B are initialized to the functions that describe the
2822 relation between the elements accessed twice by CHREC_A and
2823 CHREC_B. For k >= 0, the following property is verified:
2825 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2828 analyze_siv_subscript (tree chrec_a
,
2830 conflict_function
**overlaps_a
,
2831 conflict_function
**overlaps_b
,
2832 tree
*last_conflicts
,
2835 dependence_stats
.num_siv
++;
2837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2838 fprintf (dump_file
, "(analyze_siv_subscript \n");
2840 if (evolution_function_is_constant_p (chrec_a
)
2841 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2842 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2843 overlaps_a
, overlaps_b
, last_conflicts
);
2845 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2846 && evolution_function_is_constant_p (chrec_b
))
2847 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2848 overlaps_b
, overlaps_a
, last_conflicts
);
2850 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2851 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2853 if (!chrec_contains_symbols (chrec_a
)
2854 && !chrec_contains_symbols (chrec_b
))
2856 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2857 overlaps_a
, overlaps_b
,
2860 if (CF_NOT_KNOWN_P (*overlaps_a
)
2861 || CF_NOT_KNOWN_P (*overlaps_b
))
2862 dependence_stats
.num_siv_unimplemented
++;
2863 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2864 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2865 dependence_stats
.num_siv_independent
++;
2867 dependence_stats
.num_siv_dependent
++;
2869 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2872 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2873 overlaps_a
, overlaps_b
,
2876 if (CF_NOT_KNOWN_P (*overlaps_a
)
2877 || CF_NOT_KNOWN_P (*overlaps_b
))
2878 dependence_stats
.num_siv_unimplemented
++;
2879 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2880 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2881 dependence_stats
.num_siv_independent
++;
2883 dependence_stats
.num_siv_dependent
++;
2886 goto siv_subscript_dontknow
;
2891 siv_subscript_dontknow
:;
2892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2893 fprintf (dump_file
, " siv test failed: unimplemented");
2894 *overlaps_a
= conflict_fn_not_known ();
2895 *overlaps_b
= conflict_fn_not_known ();
2896 *last_conflicts
= chrec_dont_know
;
2897 dependence_stats
.num_siv_unimplemented
++;
2900 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2901 fprintf (dump_file
, ")\n");
2904 /* Returns false if we can prove that the greatest common divisor of the steps
2905 of CHREC does not divide CST, false otherwise. */
2908 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2910 HOST_WIDE_INT cd
= 0, val
;
2913 if (!tree_fits_shwi_p (cst
))
2915 val
= tree_to_shwi (cst
);
2917 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2919 step
= CHREC_RIGHT (chrec
);
2920 if (!tree_fits_shwi_p (step
))
2922 cd
= gcd (cd
, tree_to_shwi (step
));
2923 chrec
= CHREC_LEFT (chrec
);
2926 return val
% cd
== 0;
2929 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2930 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2931 functions that describe the relation between the elements accessed
2932 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2935 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2938 analyze_miv_subscript (tree chrec_a
,
2940 conflict_function
**overlaps_a
,
2941 conflict_function
**overlaps_b
,
2942 tree
*last_conflicts
,
2943 struct loop
*loop_nest
)
2945 tree type
, difference
;
2947 dependence_stats
.num_miv
++;
2948 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2949 fprintf (dump_file
, "(analyze_miv_subscript \n");
2951 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2952 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2953 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2954 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2956 if (eq_evolutions_p (chrec_a
, chrec_b
))
2958 /* Access functions are the same: all the elements are accessed
2959 in the same order. */
2960 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2961 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2962 *last_conflicts
= max_stmt_executions_tree (get_chrec_loop (chrec_a
));
2963 dependence_stats
.num_miv_dependent
++;
2966 else if (evolution_function_is_constant_p (difference
)
2967 /* For the moment, the following is verified:
2968 evolution_function_is_affine_multivariate_p (chrec_a,
2970 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2972 /* testsuite/.../ssa-chrec-33.c
2973 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2975 The difference is 1, and all the evolution steps are multiples
2976 of 2, consequently there are no overlapping elements. */
2977 *overlaps_a
= conflict_fn_no_dependence ();
2978 *overlaps_b
= conflict_fn_no_dependence ();
2979 *last_conflicts
= integer_zero_node
;
2980 dependence_stats
.num_miv_independent
++;
2983 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2984 && !chrec_contains_symbols (chrec_a
)
2985 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2986 && !chrec_contains_symbols (chrec_b
))
2988 /* testsuite/.../ssa-chrec-35.c
2989 {0, +, 1}_2 vs. {0, +, 1}_3
2990 the overlapping elements are respectively located at iterations:
2991 {0, +, 1}_x and {0, +, 1}_x,
2992 in other words, we have the equality:
2993 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2996 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2997 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2999 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3000 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3002 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3003 overlaps_a
, overlaps_b
, last_conflicts
);
3005 if (CF_NOT_KNOWN_P (*overlaps_a
)
3006 || CF_NOT_KNOWN_P (*overlaps_b
))
3007 dependence_stats
.num_miv_unimplemented
++;
3008 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
3009 || CF_NO_DEPENDENCE_P (*overlaps_b
))
3010 dependence_stats
.num_miv_independent
++;
3012 dependence_stats
.num_miv_dependent
++;
3017 /* When the analysis is too difficult, answer "don't know". */
3018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3019 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
3021 *overlaps_a
= conflict_fn_not_known ();
3022 *overlaps_b
= conflict_fn_not_known ();
3023 *last_conflicts
= chrec_dont_know
;
3024 dependence_stats
.num_miv_unimplemented
++;
3027 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3028 fprintf (dump_file
, ")\n");
3031 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
3032 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
3033 OVERLAP_ITERATIONS_B are initialized with two functions that
3034 describe the iterations that contain conflicting elements.
3036 Remark: For an integer k >= 0, the following equality is true:
3038 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3042 analyze_overlapping_iterations (tree chrec_a
,
3044 conflict_function
**overlap_iterations_a
,
3045 conflict_function
**overlap_iterations_b
,
3046 tree
*last_conflicts
, struct loop
*loop_nest
)
3048 unsigned int lnn
= loop_nest
->num
;
3050 dependence_stats
.num_subscript_tests
++;
3052 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3054 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
3055 fprintf (dump_file
, " (chrec_a = ");
3056 print_generic_expr (dump_file
, chrec_a
, 0);
3057 fprintf (dump_file
, ")\n (chrec_b = ");
3058 print_generic_expr (dump_file
, chrec_b
, 0);
3059 fprintf (dump_file
, ")\n");
3062 if (chrec_a
== NULL_TREE
3063 || chrec_b
== NULL_TREE
3064 || chrec_contains_undetermined (chrec_a
)
3065 || chrec_contains_undetermined (chrec_b
))
3067 dependence_stats
.num_subscript_undetermined
++;
3069 *overlap_iterations_a
= conflict_fn_not_known ();
3070 *overlap_iterations_b
= conflict_fn_not_known ();
3073 /* If they are the same chrec, and are affine, they overlap
3074 on every iteration. */
3075 else if (eq_evolutions_p (chrec_a
, chrec_b
)
3076 && (evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
3077 || operand_equal_p (chrec_a
, chrec_b
, 0)))
3079 dependence_stats
.num_same_subscript_function
++;
3080 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3081 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3082 *last_conflicts
= chrec_dont_know
;
3085 /* If they aren't the same, and aren't affine, we can't do anything
3087 else if ((chrec_contains_symbols (chrec_a
)
3088 || chrec_contains_symbols (chrec_b
))
3089 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
3090 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
3092 dependence_stats
.num_subscript_undetermined
++;
3093 *overlap_iterations_a
= conflict_fn_not_known ();
3094 *overlap_iterations_b
= conflict_fn_not_known ();
3097 else if (ziv_subscript_p (chrec_a
, chrec_b
))
3098 analyze_ziv_subscript (chrec_a
, chrec_b
,
3099 overlap_iterations_a
, overlap_iterations_b
,
3102 else if (siv_subscript_p (chrec_a
, chrec_b
))
3103 analyze_siv_subscript (chrec_a
, chrec_b
,
3104 overlap_iterations_a
, overlap_iterations_b
,
3105 last_conflicts
, lnn
);
3108 analyze_miv_subscript (chrec_a
, chrec_b
,
3109 overlap_iterations_a
, overlap_iterations_b
,
3110 last_conflicts
, loop_nest
);
3112 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3114 fprintf (dump_file
, " (overlap_iterations_a = ");
3115 dump_conflict_function (dump_file
, *overlap_iterations_a
);
3116 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
3117 dump_conflict_function (dump_file
, *overlap_iterations_b
);
3118 fprintf (dump_file
, "))\n");
3122 /* Helper function for uniquely inserting distance vectors. */
3125 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
3130 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, v
)
3131 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
3134 DDR_DIST_VECTS (ddr
).safe_push (dist_v
);
3137 /* Helper function for uniquely inserting direction vectors. */
3140 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
3145 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), i
, v
)
3146 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
3149 DDR_DIR_VECTS (ddr
).safe_push (dir_v
);
3152 /* Add a distance of 1 on all the loops outer than INDEX. If we
3153 haven't yet determined a distance for this outer loop, push a new
3154 distance vector composed of the previous distance, and a distance
3155 of 1 for this outer loop. Example:
3163 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3164 save (0, 1), then we have to save (1, 0). */
3167 add_outer_distances (struct data_dependence_relation
*ddr
,
3168 lambda_vector dist_v
, int index
)
3170 /* For each outer loop where init_v is not set, the accesses are
3171 in dependence of distance 1 in the loop. */
3172 while (--index
>= 0)
3174 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3175 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3177 save_dist_v (ddr
, save_v
);
3181 /* Return false when fail to represent the data dependence as a
3182 distance vector. INIT_B is set to true when a component has been
3183 added to the distance vector DIST_V. INDEX_CARRY is then set to
3184 the index in DIST_V that carries the dependence. */
3187 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
3188 struct data_reference
*ddr_a
,
3189 struct data_reference
*ddr_b
,
3190 lambda_vector dist_v
, bool *init_b
,
3194 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3196 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3198 tree access_fn_a
, access_fn_b
;
3199 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
3201 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3203 non_affine_dependence_relation (ddr
);
3207 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
3208 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
3210 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
3211 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
3214 int var_a
= CHREC_VARIABLE (access_fn_a
);
3215 int var_b
= CHREC_VARIABLE (access_fn_b
);
3218 || chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3220 non_affine_dependence_relation (ddr
);
3224 dist
= int_cst_value (SUB_DISTANCE (subscript
));
3225 index
= index_in_loop_nest (var_a
, DDR_LOOP_NEST (ddr
));
3226 *index_carry
= MIN (index
, *index_carry
);
3228 /* This is the subscript coupling test. If we have already
3229 recorded a distance for this loop (a distance coming from
3230 another subscript), it should be the same. For example,
3231 in the following code, there is no dependence:
3238 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
3240 finalize_ddr_dependent (ddr
, chrec_known
);
3244 dist_v
[index
] = dist
;
3248 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
3250 /* This can be for example an affine vs. constant dependence
3251 (T[i] vs. T[3]) that is not an affine dependence and is
3252 not representable as a distance vector. */
3253 non_affine_dependence_relation (ddr
);
3261 /* Return true when the DDR contains only constant access functions. */
3264 constant_access_functions (const struct data_dependence_relation
*ddr
)
3268 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3269 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
3270 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
3276 /* Helper function for the case where DDR_A and DDR_B are the same
3277 multivariate access function with a constant step. For an example
3281 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
3284 tree c_1
= CHREC_LEFT (c_2
);
3285 tree c_0
= CHREC_LEFT (c_1
);
3286 lambda_vector dist_v
;
3289 /* Polynomials with more than 2 variables are not handled yet. When
3290 the evolution steps are parameters, it is not possible to
3291 represent the dependence using classical distance vectors. */
3292 if (TREE_CODE (c_0
) != INTEGER_CST
3293 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
3294 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
3296 DDR_AFFINE_P (ddr
) = false;
3300 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
3301 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
3303 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3304 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3305 v1
= int_cst_value (CHREC_RIGHT (c_1
));
3306 v2
= int_cst_value (CHREC_RIGHT (c_2
));
3319 save_dist_v (ddr
, dist_v
);
3321 add_outer_distances (ddr
, dist_v
, x_1
);
3324 /* Helper function for the case where DDR_A and DDR_B are the same
3325 access functions. */
3328 add_other_self_distances (struct data_dependence_relation
*ddr
)
3330 lambda_vector dist_v
;
3332 int index_carry
= DDR_NB_LOOPS (ddr
);
3334 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3336 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3338 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3340 if (!evolution_function_is_univariate_p (access_fun
))
3342 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3344 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3348 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
3350 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
3351 add_multivariate_self_dist (ddr
, access_fun
);
3353 /* The evolution step is not constant: it varies in
3354 the outer loop, so this cannot be represented by a
3355 distance vector. For example in pr34635.c the
3356 evolution is {0, +, {0, +, 4}_1}_2. */
3357 DDR_AFFINE_P (ddr
) = false;
3362 index_carry
= MIN (index_carry
,
3363 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3364 DDR_LOOP_NEST (ddr
)));
3368 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3369 add_outer_distances (ddr
, dist_v
, index_carry
);
3373 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
3375 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3377 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
3378 save_dist_v (ddr
, dist_v
);
3381 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3382 is the case for example when access functions are the same and
3383 equal to a constant, as in:
3390 in which case the distance vectors are (0) and (1). */
3393 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
3397 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3399 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
3400 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
3401 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
3403 for (j
= 0; j
< ca
->n
; j
++)
3404 if (affine_function_zero_p (ca
->fns
[j
]))
3406 insert_innermost_unit_dist_vector (ddr
);
3410 for (j
= 0; j
< cb
->n
; j
++)
3411 if (affine_function_zero_p (cb
->fns
[j
]))
3413 insert_innermost_unit_dist_vector (ddr
);
3419 /* Compute the classic per loop distance vector. DDR is the data
3420 dependence relation to build a vector from. Return false when fail
3421 to represent the data dependence as a distance vector. */
3424 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3425 struct loop
*loop_nest
)
3427 bool init_b
= false;
3428 int index_carry
= DDR_NB_LOOPS (ddr
);
3429 lambda_vector dist_v
;
3431 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3434 if (same_access_functions (ddr
))
3436 /* Save the 0 vector. */
3437 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3438 save_dist_v (ddr
, dist_v
);
3440 if (constant_access_functions (ddr
))
3441 add_distance_for_zero_overlaps (ddr
);
3443 if (DDR_NB_LOOPS (ddr
) > 1)
3444 add_other_self_distances (ddr
);
3449 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3450 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3451 dist_v
, &init_b
, &index_carry
))
3454 /* Save the distance vector if we initialized one. */
3457 /* Verify a basic constraint: classic distance vectors should
3458 always be lexicographically positive.
3460 Data references are collected in the order of execution of
3461 the program, thus for the following loop
3463 | for (i = 1; i < 100; i++)
3464 | for (j = 1; j < 100; j++)
3466 | t = T[j+1][i-1]; // A
3467 | T[j][i] = t + 2; // B
3470 references are collected following the direction of the wind:
3471 A then B. The data dependence tests are performed also
3472 following this order, such that we're looking at the distance
3473 separating the elements accessed by A from the elements later
3474 accessed by B. But in this example, the distance returned by
3475 test_dep (A, B) is lexicographically negative (-1, 1), that
3476 means that the access A occurs later than B with respect to
3477 the outer loop, ie. we're actually looking upwind. In this
3478 case we solve test_dep (B, A) looking downwind to the
3479 lexicographically positive solution, that returns the
3480 distance vector (1, -1). */
3481 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3483 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3484 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3487 compute_subscript_distance (ddr
);
3488 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3489 save_v
, &init_b
, &index_carry
))
3491 save_dist_v (ddr
, save_v
);
3492 DDR_REVERSED_P (ddr
) = true;
3494 /* In this case there is a dependence forward for all the
3497 | for (k = 1; k < 100; k++)
3498 | for (i = 1; i < 100; i++)
3499 | for (j = 1; j < 100; j++)
3501 | t = T[j+1][i-1]; // A
3502 | T[j][i] = t + 2; // B
3510 if (DDR_NB_LOOPS (ddr
) > 1)
3512 add_outer_distances (ddr
, save_v
, index_carry
);
3513 add_outer_distances (ddr
, dist_v
, index_carry
);
3518 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3519 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3521 if (DDR_NB_LOOPS (ddr
) > 1)
3523 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3525 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3526 DDR_A (ddr
), loop_nest
))
3528 compute_subscript_distance (ddr
);
3529 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3530 opposite_v
, &init_b
,
3534 save_dist_v (ddr
, save_v
);
3535 add_outer_distances (ddr
, dist_v
, index_carry
);
3536 add_outer_distances (ddr
, opposite_v
, index_carry
);
3539 save_dist_v (ddr
, save_v
);
3544 /* There is a distance of 1 on all the outer loops: Example:
3545 there is a dependence of distance 1 on loop_1 for the array A.
3551 add_outer_distances (ddr
, dist_v
,
3552 lambda_vector_first_nz (dist_v
,
3553 DDR_NB_LOOPS (ddr
), 0));
3556 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3560 fprintf (dump_file
, "(build_classic_dist_vector\n");
3561 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3563 fprintf (dump_file
, " dist_vector = (");
3564 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3565 DDR_NB_LOOPS (ddr
));
3566 fprintf (dump_file
, " )\n");
3568 fprintf (dump_file
, ")\n");
3574 /* Return the direction for a given distance.
3575 FIXME: Computing dir this way is suboptimal, since dir can catch
3576 cases that dist is unable to represent. */
3578 static inline enum data_dependence_direction
3579 dir_from_dist (int dist
)
3582 return dir_positive
;
3584 return dir_negative
;
3589 /* Compute the classic per loop direction vector. DDR is the data
3590 dependence relation to build a vector from. */
3593 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3596 lambda_vector dist_v
;
3598 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
3600 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3602 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3603 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3605 save_dir_v (ddr
, dir_v
);
3609 /* Helper function. Returns true when there is a dependence between
3610 data references DRA and DRB. */
3613 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3614 struct data_reference
*dra
,
3615 struct data_reference
*drb
,
3616 struct loop
*loop_nest
)
3619 tree last_conflicts
;
3620 struct subscript
*subscript
;
3621 tree res
= NULL_TREE
;
3623 for (i
= 0; DDR_SUBSCRIPTS (ddr
).iterate (i
, &subscript
); i
++)
3625 conflict_function
*overlaps_a
, *overlaps_b
;
3627 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3628 DR_ACCESS_FN (drb
, i
),
3629 &overlaps_a
, &overlaps_b
,
3630 &last_conflicts
, loop_nest
);
3632 if (SUB_CONFLICTS_IN_A (subscript
))
3633 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3634 if (SUB_CONFLICTS_IN_B (subscript
))
3635 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3637 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3638 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3639 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3641 /* If there is any undetermined conflict function we have to
3642 give a conservative answer in case we cannot prove that
3643 no dependence exists when analyzing another subscript. */
3644 if (CF_NOT_KNOWN_P (overlaps_a
)
3645 || CF_NOT_KNOWN_P (overlaps_b
))
3647 res
= chrec_dont_know
;
3651 /* When there is a subscript with no dependence we can stop. */
3652 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3653 || CF_NO_DEPENDENCE_P (overlaps_b
))
3660 if (res
== NULL_TREE
)
3663 if (res
== chrec_known
)
3664 dependence_stats
.num_dependence_independent
++;
3666 dependence_stats
.num_dependence_undetermined
++;
3667 finalize_ddr_dependent (ddr
, res
);
3671 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3674 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3675 struct loop
*loop_nest
)
3677 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3678 dependence_stats
.num_dependence_dependent
++;
3680 compute_subscript_distance (ddr
);
3681 if (build_classic_dist_vector (ddr
, loop_nest
))
3682 build_classic_dir_vector (ddr
);
3685 /* Returns true when all the access functions of A are affine or
3686 constant with respect to LOOP_NEST. */
3689 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3690 const struct loop
*loop_nest
)
3693 vec
<tree
> fns
= DR_ACCESS_FNS (a
);
3696 FOR_EACH_VEC_ELT (fns
, i
, t
)
3697 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3698 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3704 /* Initializes an equation for an OMEGA problem using the information
3705 contained in the ACCESS_FUN. Returns true when the operation
3708 PB is the omega constraint system.
3709 EQ is the number of the equation to be initialized.
3710 OFFSET is used for shifting the variables names in the constraints:
3711 a constrain is composed of 2 * the number of variables surrounding
3712 dependence accesses. OFFSET is set either to 0 for the first n variables,
3713 then it is set to n.
3714 ACCESS_FUN is expected to be an affine chrec. */
3717 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3718 unsigned int offset
, tree access_fun
,
3719 struct data_dependence_relation
*ddr
)
3721 switch (TREE_CODE (access_fun
))
3723 case POLYNOMIAL_CHREC
:
3725 tree left
= CHREC_LEFT (access_fun
);
3726 tree right
= CHREC_RIGHT (access_fun
);
3727 int var
= CHREC_VARIABLE (access_fun
);
3730 if (TREE_CODE (right
) != INTEGER_CST
)
3733 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3734 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3736 /* Compute the innermost loop index. */
3737 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3740 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3741 += int_cst_value (right
);
3743 switch (TREE_CODE (left
))
3745 case POLYNOMIAL_CHREC
:
3746 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3749 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3758 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3766 /* As explained in the comments preceding init_omega_for_ddr, we have
3767 to set up a system for each loop level, setting outer loops
3768 variation to zero, and current loop variation to positive or zero.
3769 Save each lexico positive distance vector. */
3772 omega_extract_distance_vectors (omega_pb pb
,
3773 struct data_dependence_relation
*ddr
)
3777 struct loop
*loopi
, *loopj
;
3778 enum omega_result res
;
3780 /* Set a new problem for each loop in the nest. The basis is the
3781 problem that we have initialized until now. On top of this we
3782 add new constraints. */
3783 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3784 && DDR_LOOP_NEST (ddr
).iterate (i
, &loopi
); i
++)
3787 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3788 DDR_NB_LOOPS (ddr
));
3790 omega_copy_problem (copy
, pb
);
3792 /* For all the outer loops "loop_j", add "dj = 0". */
3793 for (j
= 0; j
< i
&& DDR_LOOP_NEST (ddr
).iterate (j
, &loopj
); j
++)
3795 eq
= omega_add_zero_eq (copy
, omega_black
);
3796 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3799 /* For "loop_i", add "0 <= di". */
3800 geq
= omega_add_zero_geq (copy
, omega_black
);
3801 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3803 /* Reduce the constraint system, and test that the current
3804 problem is feasible. */
3805 res
= omega_simplify_problem (copy
);
3806 if (res
== omega_false
3807 || res
== omega_unknown
3808 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3811 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3812 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3814 dist
= copy
->subs
[eq
].coef
[0];
3820 /* Reinitialize problem... */
3821 omega_copy_problem (copy
, pb
);
3822 for (j
= 0; j
< i
&& DDR_LOOP_NEST (ddr
).iterate (j
, &loopj
); j
++)
3824 eq
= omega_add_zero_eq (copy
, omega_black
);
3825 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3828 /* ..., but this time "di = 1". */
3829 eq
= omega_add_zero_eq (copy
, omega_black
);
3830 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3831 copy
->eqs
[eq
].coef
[0] = -1;
3833 res
= omega_simplify_problem (copy
);
3834 if (res
== omega_false
3835 || res
== omega_unknown
3836 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3839 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3840 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3842 dist
= copy
->subs
[eq
].coef
[0];
3848 /* Save the lexicographically positive distance vector. */
3851 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3852 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3856 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3857 if (copy
->subs
[eq
].key
> 0)
3859 dist
= copy
->subs
[eq
].coef
[0];
3860 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3863 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3864 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3866 save_dist_v (ddr
, dist_v
);
3867 save_dir_v (ddr
, dir_v
);
3871 omega_free_problem (copy
);
3875 /* This is called for each subscript of a tuple of data references:
3876 insert an equality for representing the conflicts. */
3879 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3880 struct data_dependence_relation
*ddr
,
3881 omega_pb pb
, bool *maybe_dependent
)
3884 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3885 TREE_TYPE (access_fun_b
));
3886 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3887 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3888 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3891 /* When the fun_a - fun_b is not constant, the dependence is not
3892 captured by the classic distance vector representation. */
3893 if (TREE_CODE (difference
) != INTEGER_CST
)
3897 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3899 /* There is no dependence. */
3900 *maybe_dependent
= false;
3904 minus_one
= build_int_cst (type
, -1);
3905 fun_b
= chrec_fold_multiply (type
, fun_b
, minus_one
);
3907 eq
= omega_add_zero_eq (pb
, omega_black
);
3908 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3909 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3910 /* There is probably a dependence, but the system of
3911 constraints cannot be built: answer "don't know". */
3915 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3916 && !int_divides_p (lambda_vector_gcd
3917 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3918 2 * DDR_NB_LOOPS (ddr
)),
3919 pb
->eqs
[eq
].coef
[0]))
3921 /* There is no dependence. */
3922 *maybe_dependent
= false;
3929 /* Helper function, same as init_omega_for_ddr but specialized for
3930 data references A and B. */
3933 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3934 struct data_dependence_relation
*ddr
,
3935 omega_pb pb
, bool *maybe_dependent
)
3940 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3942 /* Insert an equality per subscript. */
3943 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3945 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3946 ddr
, pb
, maybe_dependent
))
3948 else if (*maybe_dependent
== false)
3950 /* There is no dependence. */
3951 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3956 /* Insert inequalities: constraints corresponding to the iteration
3957 domain, i.e. the loops surrounding the references "loop_x" and
3958 the distance variables "dx". The layout of the OMEGA
3959 representation is as follows:
3960 - coef[0] is the constant
3961 - coef[1..nb_loops] are the protected variables that will not be
3962 removed by the solver: the "dx"
3963 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3965 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3966 && DDR_LOOP_NEST (ddr
).iterate (i
, &loopi
); i
++)
3968 HOST_WIDE_INT nbi
= max_stmt_executions_int (loopi
);
3971 ineq
= omega_add_zero_geq (pb
, omega_black
);
3972 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3974 /* 0 <= loop_x + dx */
3975 ineq
= omega_add_zero_geq (pb
, omega_black
);
3976 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3977 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3981 /* loop_x <= nb_iters */
3982 ineq
= omega_add_zero_geq (pb
, omega_black
);
3983 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3984 pb
->geqs
[ineq
].coef
[0] = nbi
;
3986 /* loop_x + dx <= nb_iters */
3987 ineq
= omega_add_zero_geq (pb
, omega_black
);
3988 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3989 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3990 pb
->geqs
[ineq
].coef
[0] = nbi
;
3992 /* A step "dx" bigger than nb_iters is not feasible, so
3993 add "0 <= nb_iters + dx", */
3994 ineq
= omega_add_zero_geq (pb
, omega_black
);
3995 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3996 pb
->geqs
[ineq
].coef
[0] = nbi
;
3997 /* and "dx <= nb_iters". */
3998 ineq
= omega_add_zero_geq (pb
, omega_black
);
3999 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
4000 pb
->geqs
[ineq
].coef
[0] = nbi
;
4004 omega_extract_distance_vectors (pb
, ddr
);
4009 /* Sets up the Omega dependence problem for the data dependence
4010 relation DDR. Returns false when the constraint system cannot be
4011 built, ie. when the test answers "don't know". Returns true
4012 otherwise, and when independence has been proved (using one of the
4013 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
4014 set MAYBE_DEPENDENT to true.
4016 Example: for setting up the dependence system corresponding to the
4017 conflicting accesses
4022 | ... A[2*j, 2*(i + j)]
4026 the following constraints come from the iteration domain:
4033 where di, dj are the distance variables. The constraints
4034 representing the conflicting elements are:
4037 i + 1 = 2 * (i + di + j + dj)
4039 For asking that the resulting distance vector (di, dj) be
4040 lexicographically positive, we insert the constraint "di >= 0". If
4041 "di = 0" in the solution, we fix that component to zero, and we
4042 look at the inner loops: we set a new problem where all the outer
4043 loop distances are zero, and fix this inner component to be
4044 positive. When one of the components is positive, we save that
4045 distance, and set a new problem where the distance on this loop is
4046 zero, searching for other distances in the inner loops. Here is
4047 the classic example that illustrates that we have to set for each
4048 inner loop a new problem:
4056 we have to save two distances (1, 0) and (0, 1).
4058 Given two array references, refA and refB, we have to set the
4059 dependence problem twice, refA vs. refB and refB vs. refA, and we
4060 cannot do a single test, as refB might occur before refA in the
4061 inner loops, and the contrary when considering outer loops: ex.
4066 | T[{1,+,1}_2][{1,+,1}_1] // refA
4067 | T[{2,+,1}_2][{0,+,1}_1] // refB
4072 refB touches the elements in T before refA, and thus for the same
4073 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
4074 but for successive loop_0 iterations, we have (1, -1, 1)
4076 The Omega solver expects the distance variables ("di" in the
4077 previous example) to come first in the constraint system (as
4078 variables to be protected, or "safe" variables), the constraint
4079 system is built using the following layout:
4081 "cst | distance vars | index vars".
4085 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
4086 bool *maybe_dependent
)
4091 *maybe_dependent
= true;
4093 if (same_access_functions (ddr
))
4096 lambda_vector dir_v
;
4098 /* Save the 0 vector. */
4099 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4100 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4101 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
4102 dir_v
[j
] = dir_equal
;
4103 save_dir_v (ddr
, dir_v
);
4105 /* Save the dependences carried by outer loops. */
4106 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4107 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
4109 omega_free_problem (pb
);
4113 /* Omega expects the protected variables (those that have to be kept
4114 after elimination) to appear first in the constraint system.
4115 These variables are the distance variables. In the following
4116 initialization we declare NB_LOOPS safe variables, and the total
4117 number of variables for the constraint system is 2*NB_LOOPS. */
4118 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4119 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
4121 omega_free_problem (pb
);
4123 /* Stop computation if not decidable, or no dependence. */
4124 if (res
== false || *maybe_dependent
== false)
4127 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4128 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
4130 omega_free_problem (pb
);
4135 /* Return true when DDR contains the same information as that stored
4136 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4139 ddr_consistent_p (FILE *file
,
4140 struct data_dependence_relation
*ddr
,
4141 vec
<lambda_vector
> dist_vects
,
4142 vec
<lambda_vector
> dir_vects
)
4146 /* If dump_file is set, output there. */
4147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4150 if (dist_vects
.length () != DDR_NUM_DIST_VECTS (ddr
))
4152 lambda_vector b_dist_v
;
4153 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4154 dist_vects
.length (),
4155 DDR_NUM_DIST_VECTS (ddr
));
4157 fprintf (file
, "Banerjee dist vectors:\n");
4158 FOR_EACH_VEC_ELT (dist_vects
, i
, b_dist_v
)
4159 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
4161 fprintf (file
, "Omega dist vectors:\n");
4162 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4163 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
4165 fprintf (file
, "data dependence relation:\n");
4166 dump_data_dependence_relation (file
, ddr
);
4168 fprintf (file
, ")\n");
4172 if (dir_vects
.length () != DDR_NUM_DIR_VECTS (ddr
))
4174 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4175 dir_vects
.length (),
4176 DDR_NUM_DIR_VECTS (ddr
));
4180 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4182 lambda_vector a_dist_v
;
4183 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
4185 /* Distance vectors are not ordered in the same way in the DDR
4186 and in the DIST_VECTS: search for a matching vector. */
4187 FOR_EACH_VEC_ELT (dist_vects
, j
, a_dist_v
)
4188 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
4191 if (j
== dist_vects
.length ())
4193 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
4194 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
4195 fprintf (file
, "not found in Omega dist vectors:\n");
4196 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4197 fprintf (file
, "data dependence relation:\n");
4198 dump_data_dependence_relation (file
, ddr
);
4199 fprintf (file
, ")\n");
4203 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
4205 lambda_vector a_dir_v
;
4206 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
4208 /* Direction vectors are not ordered in the same way in the DDR
4209 and in the DIR_VECTS: search for a matching vector. */
4210 FOR_EACH_VEC_ELT (dir_vects
, j
, a_dir_v
)
4211 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
4214 if (j
== dist_vects
.length ())
4216 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
4217 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
4218 fprintf (file
, "not found in Omega dir vectors:\n");
4219 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4220 fprintf (file
, "data dependence relation:\n");
4221 dump_data_dependence_relation (file
, ddr
);
4222 fprintf (file
, ")\n");
4229 /* This computes the affine dependence relation between A and B with
4230 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4231 independence between two accesses, while CHREC_DONT_KNOW is used
4232 for representing the unknown relation.
4234 Note that it is possible to stop the computation of the dependence
4235 relation the first time we detect a CHREC_KNOWN element for a given
4239 compute_affine_dependence (struct data_dependence_relation
*ddr
,
4240 struct loop
*loop_nest
)
4242 struct data_reference
*dra
= DDR_A (ddr
);
4243 struct data_reference
*drb
= DDR_B (ddr
);
4245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4247 fprintf (dump_file
, "(compute_affine_dependence\n");
4248 fprintf (dump_file
, " stmt_a: ");
4249 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, TDF_SLIM
);
4250 fprintf (dump_file
, " stmt_b: ");
4251 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, TDF_SLIM
);
4254 /* Analyze only when the dependence relation is not yet known. */
4255 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4257 dependence_stats
.num_dependence_tests
++;
4259 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
4260 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
4262 subscript_dependence_tester (ddr
, loop_nest
);
4264 if (flag_check_data_deps
)
4266 /* Dump the dependences from the first algorithm. */
4267 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4269 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
4270 dump_data_dependence_relation (dump_file
, ddr
);
4273 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4275 bool maybe_dependent
;
4276 vec
<lambda_vector
> dir_vects
, dist_vects
;
4278 /* Save the result of the first DD analyzer. */
4279 dist_vects
= DDR_DIST_VECTS (ddr
);
4280 dir_vects
= DDR_DIR_VECTS (ddr
);
4282 /* Reset the information. */
4283 DDR_DIST_VECTS (ddr
).create (0);
4284 DDR_DIR_VECTS (ddr
).create (0);
4286 /* Compute the same information using Omega. */
4287 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
4288 goto csys_dont_know
;
4290 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4292 fprintf (dump_file
, "Omega Analyzer\n");
4293 dump_data_dependence_relation (dump_file
, ddr
);
4296 /* Check that we get the same information. */
4297 if (maybe_dependent
)
4298 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
4304 /* As a last case, if the dependence cannot be determined, or if
4305 the dependence is considered too difficult to determine, answer
4310 dependence_stats
.num_dependence_undetermined
++;
4312 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4314 fprintf (dump_file
, "Data ref a:\n");
4315 dump_data_reference (dump_file
, dra
);
4316 fprintf (dump_file
, "Data ref b:\n");
4317 dump_data_reference (dump_file
, drb
);
4318 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
4320 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4324 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4326 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4327 fprintf (dump_file
, ") -> no dependence\n");
4328 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4329 fprintf (dump_file
, ") -> dependence analysis failed\n");
4331 fprintf (dump_file
, ")\n");
4335 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4336 the data references in DATAREFS, in the LOOP_NEST. When
4337 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4338 relations. Return true when successful, i.e. data references number
4339 is small enough to be handled. */
4342 compute_all_dependences (vec
<data_reference_p
> datarefs
,
4343 vec
<ddr_p
> *dependence_relations
,
4344 vec
<loop_p
> loop_nest
,
4345 bool compute_self_and_rr
)
4347 struct data_dependence_relation
*ddr
;
4348 struct data_reference
*a
, *b
;
4351 if ((int) datarefs
.length ()
4352 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS
))
4354 struct data_dependence_relation
*ddr
;
4356 /* Insert a single relation into dependence_relations:
4358 ddr
= initialize_data_dependence_relation (NULL
, NULL
, loop_nest
);
4359 dependence_relations
->safe_push (ddr
);
4363 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4364 for (j
= i
+ 1; datarefs
.iterate (j
, &b
); j
++)
4365 if (DR_IS_WRITE (a
) || DR_IS_WRITE (b
) || compute_self_and_rr
)
4367 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4368 dependence_relations
->safe_push (ddr
);
4369 if (loop_nest
.exists ())
4370 compute_affine_dependence (ddr
, loop_nest
[0]);
4373 if (compute_self_and_rr
)
4374 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4376 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4377 dependence_relations
->safe_push (ddr
);
4378 if (loop_nest
.exists ())
4379 compute_affine_dependence (ddr
, loop_nest
[0]);
4385 /* Describes a location of a memory reference. */
4387 typedef struct data_ref_loc_d
4389 /* The memory reference. */
4392 /* True if the memory reference is read. */
4397 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4398 true if STMT clobbers memory, false otherwise. */
4401 get_references_in_stmt (gimple stmt
, vec
<data_ref_loc
, va_heap
> *references
)
4403 bool clobbers_memory
= false;
4406 enum gimple_code stmt_code
= gimple_code (stmt
);
4408 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4409 As we cannot model data-references to not spelled out
4410 accesses give up if they may occur. */
4411 if (stmt_code
== GIMPLE_CALL
4412 && !(gimple_call_flags (stmt
) & ECF_CONST
))
4414 /* Allow IFN_GOMP_SIMD_LANE in their own loops. */
4415 if (gimple_call_internal_p (stmt
))
4416 switch (gimple_call_internal_fn (stmt
))
4418 case IFN_GOMP_SIMD_LANE
:
4420 struct loop
*loop
= gimple_bb (stmt
)->loop_father
;
4421 tree uid
= gimple_call_arg (stmt
, 0);
4422 gcc_assert (TREE_CODE (uid
) == SSA_NAME
);
4424 || loop
->simduid
!= SSA_NAME_VAR (uid
))
4425 clobbers_memory
= true;
4429 case IFN_MASK_STORE
:
4432 clobbers_memory
= true;
4436 clobbers_memory
= true;
4438 else if (stmt_code
== GIMPLE_ASM
4439 && (gimple_asm_volatile_p (as_a
<gasm
*> (stmt
))
4440 || gimple_vuse (stmt
)))
4441 clobbers_memory
= true;
4443 if (!gimple_vuse (stmt
))
4444 return clobbers_memory
;
4446 if (stmt_code
== GIMPLE_ASSIGN
)
4449 op0
= gimple_assign_lhs (stmt
);
4450 op1
= gimple_assign_rhs1 (stmt
);
4453 || (REFERENCE_CLASS_P (op1
)
4454 && (base
= get_base_address (op1
))
4455 && TREE_CODE (base
) != SSA_NAME
))
4459 references
->safe_push (ref
);
4462 else if (stmt_code
== GIMPLE_CALL
)
4466 ref
.is_read
= false;
4467 if (gimple_call_internal_p (stmt
))
4468 switch (gimple_call_internal_fn (stmt
))
4471 if (gimple_call_lhs (stmt
) == NULL_TREE
)
4474 case IFN_MASK_STORE
:
4475 ref
.ref
= fold_build2 (MEM_REF
,
4477 ? TREE_TYPE (gimple_call_lhs (stmt
))
4478 : TREE_TYPE (gimple_call_arg (stmt
, 3)),
4479 gimple_call_arg (stmt
, 0),
4480 gimple_call_arg (stmt
, 1));
4481 references
->safe_push (ref
);
4487 op0
= gimple_call_lhs (stmt
);
4488 n
= gimple_call_num_args (stmt
);
4489 for (i
= 0; i
< n
; i
++)
4491 op1
= gimple_call_arg (stmt
, i
);
4494 || (REFERENCE_CLASS_P (op1
) && get_base_address (op1
)))
4498 references
->safe_push (ref
);
4503 return clobbers_memory
;
4507 || (REFERENCE_CLASS_P (op0
) && get_base_address (op0
))))
4510 ref
.is_read
= false;
4511 references
->safe_push (ref
);
4513 return clobbers_memory
;
4516 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4517 reference, returns false, otherwise returns true. NEST is the outermost
4518 loop of the loop nest in which the references should be analyzed. */
4521 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4522 vec
<data_reference_p
> *datarefs
)
4525 auto_vec
<data_ref_loc
, 2> references
;
4528 data_reference_p dr
;
4530 if (get_references_in_stmt (stmt
, &references
))
4533 FOR_EACH_VEC_ELT (references
, i
, ref
)
4535 dr
= create_data_ref (nest
, loop_containing_stmt (stmt
),
4536 ref
->ref
, stmt
, ref
->is_read
);
4537 gcc_assert (dr
!= NULL
);
4538 datarefs
->safe_push (dr
);
4540 references
.release ();
4544 /* Stores the data references in STMT to DATAREFS. If there is an
4545 unanalyzable reference, returns false, otherwise returns true.
4546 NEST is the outermost loop of the loop nest in which the references
4547 should be instantiated, LOOP is the loop in which the references
4548 should be analyzed. */
4551 graphite_find_data_references_in_stmt (loop_p nest
, loop_p loop
, gimple stmt
,
4552 vec
<data_reference_p
> *datarefs
)
4555 auto_vec
<data_ref_loc
, 2> references
;
4558 data_reference_p dr
;
4560 if (get_references_in_stmt (stmt
, &references
))
4563 FOR_EACH_VEC_ELT (references
, i
, ref
)
4565 dr
= create_data_ref (nest
, loop
, ref
->ref
, stmt
, ref
->is_read
);
4566 gcc_assert (dr
!= NULL
);
4567 datarefs
->safe_push (dr
);
4570 references
.release ();
4574 /* Search the data references in LOOP, and record the information into
4575 DATAREFS. Returns chrec_dont_know when failing to analyze a
4576 difficult case, returns NULL_TREE otherwise. */
4579 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4580 vec
<data_reference_p
> *datarefs
)
4582 gimple_stmt_iterator bsi
;
4584 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4586 gimple stmt
= gsi_stmt (bsi
);
4588 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4590 struct data_reference
*res
;
4591 res
= XCNEW (struct data_reference
);
4592 datarefs
->safe_push (res
);
4594 return chrec_dont_know
;
4601 /* Search the data references in LOOP, and record the information into
4602 DATAREFS. Returns chrec_dont_know when failing to analyze a
4603 difficult case, returns NULL_TREE otherwise.
4605 TODO: This function should be made smarter so that it can handle address
4606 arithmetic as if they were array accesses, etc. */
4609 find_data_references_in_loop (struct loop
*loop
,
4610 vec
<data_reference_p
> *datarefs
)
4612 basic_block bb
, *bbs
;
4615 bbs
= get_loop_body_in_dom_order (loop
);
4617 for (i
= 0; i
< loop
->num_nodes
; i
++)
4621 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4624 return chrec_dont_know
;
4632 /* Recursive helper function. */
4635 find_loop_nest_1 (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
4637 /* Inner loops of the nest should not contain siblings. Example:
4638 when there are two consecutive loops,
4649 the dependence relation cannot be captured by the distance
4654 loop_nest
->safe_push (loop
);
4656 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4660 /* Return false when the LOOP is not well nested. Otherwise return
4661 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4662 contain the loops from the outermost to the innermost, as they will
4663 appear in the classic distance vector. */
4666 find_loop_nest (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
4668 loop_nest
->safe_push (loop
);
4670 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4674 /* Returns true when the data dependences have been computed, false otherwise.
4675 Given a loop nest LOOP, the following vectors are returned:
4676 DATAREFS is initialized to all the array elements contained in this loop,
4677 DEPENDENCE_RELATIONS contains the relations between the data references.
4678 Compute read-read and self relations if
4679 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4682 compute_data_dependences_for_loop (struct loop
*loop
,
4683 bool compute_self_and_read_read_dependences
,
4684 vec
<loop_p
> *loop_nest
,
4685 vec
<data_reference_p
> *datarefs
,
4686 vec
<ddr_p
> *dependence_relations
)
4690 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4692 /* If the loop nest is not well formed, or one of the data references
4693 is not computable, give up without spending time to compute other
4696 || !find_loop_nest (loop
, loop_nest
)
4697 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
4698 || !compute_all_dependences (*datarefs
, dependence_relations
, *loop_nest
,
4699 compute_self_and_read_read_dependences
))
4702 if (dump_file
&& (dump_flags
& TDF_STATS
))
4704 fprintf (dump_file
, "Dependence tester statistics:\n");
4706 fprintf (dump_file
, "Number of dependence tests: %d\n",
4707 dependence_stats
.num_dependence_tests
);
4708 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4709 dependence_stats
.num_dependence_dependent
);
4710 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4711 dependence_stats
.num_dependence_independent
);
4712 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4713 dependence_stats
.num_dependence_undetermined
);
4715 fprintf (dump_file
, "Number of subscript tests: %d\n",
4716 dependence_stats
.num_subscript_tests
);
4717 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4718 dependence_stats
.num_subscript_undetermined
);
4719 fprintf (dump_file
, "Number of same subscript function: %d\n",
4720 dependence_stats
.num_same_subscript_function
);
4722 fprintf (dump_file
, "Number of ziv tests: %d\n",
4723 dependence_stats
.num_ziv
);
4724 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4725 dependence_stats
.num_ziv_dependent
);
4726 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4727 dependence_stats
.num_ziv_independent
);
4728 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4729 dependence_stats
.num_ziv_unimplemented
);
4731 fprintf (dump_file
, "Number of siv tests: %d\n",
4732 dependence_stats
.num_siv
);
4733 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4734 dependence_stats
.num_siv_dependent
);
4735 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4736 dependence_stats
.num_siv_independent
);
4737 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4738 dependence_stats
.num_siv_unimplemented
);
4740 fprintf (dump_file
, "Number of miv tests: %d\n",
4741 dependence_stats
.num_miv
);
4742 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4743 dependence_stats
.num_miv_dependent
);
4744 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4745 dependence_stats
.num_miv_independent
);
4746 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4747 dependence_stats
.num_miv_unimplemented
);
4753 /* Returns true when the data dependences for the basic block BB have been
4754 computed, false otherwise.
4755 DATAREFS is initialized to all the array elements contained in this basic
4756 block, DEPENDENCE_RELATIONS contains the relations between the data
4757 references. Compute read-read and self relations if
4758 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4760 compute_data_dependences_for_bb (basic_block bb
,
4761 bool compute_self_and_read_read_dependences
,
4762 vec
<data_reference_p
> *datarefs
,
4763 vec
<ddr_p
> *dependence_relations
)
4765 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4768 return compute_all_dependences (*datarefs
, dependence_relations
, vNULL
,
4769 compute_self_and_read_read_dependences
);
4772 /* Entry point (for testing only). Analyze all the data references
4773 and the dependence relations in LOOP.
4775 The data references are computed first.
4777 A relation on these nodes is represented by a complete graph. Some
4778 of the relations could be of no interest, thus the relations can be
4781 In the following function we compute all the relations. This is
4782 just a first implementation that is here for:
4783 - for showing how to ask for the dependence relations,
4784 - for the debugging the whole dependence graph,
4785 - for the dejagnu testcases and maintenance.
4787 It is possible to ask only for a part of the graph, avoiding to
4788 compute the whole dependence graph. The computed dependences are
4789 stored in a knowledge base (KB) such that later queries don't
4790 recompute the same information. The implementation of this KB is
4791 transparent to the optimizer, and thus the KB can be changed with a
4792 more efficient implementation, or the KB could be disabled. */
4794 analyze_all_data_dependences (struct loop
*loop
)
4797 int nb_data_refs
= 10;
4798 vec
<data_reference_p
> datarefs
;
4799 datarefs
.create (nb_data_refs
);
4800 vec
<ddr_p
> dependence_relations
;
4801 dependence_relations
.create (nb_data_refs
* nb_data_refs
);
4802 vec
<loop_p
> loop_nest
;
4803 loop_nest
.create (3);
4805 /* Compute DDs on the whole function. */
4806 compute_data_dependences_for_loop (loop
, false, &loop_nest
, &datarefs
,
4807 &dependence_relations
);
4811 dump_data_dependence_relations (dump_file
, dependence_relations
);
4812 fprintf (dump_file
, "\n\n");
4814 if (dump_flags
& TDF_DETAILS
)
4815 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4817 if (dump_flags
& TDF_STATS
)
4819 unsigned nb_top_relations
= 0;
4820 unsigned nb_bot_relations
= 0;
4821 unsigned nb_chrec_relations
= 0;
4822 struct data_dependence_relation
*ddr
;
4824 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
4826 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4829 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4833 nb_chrec_relations
++;
4836 gather_stats_on_scev_database ();
4840 loop_nest
.release ();
4841 free_dependence_relations (dependence_relations
);
4842 free_data_refs (datarefs
);
4845 /* Computes all the data dependences and check that the results of
4846 several analyzers are the same. */
4849 tree_check_data_deps (void)
4851 struct loop
*loop_nest
;
4853 FOR_EACH_LOOP (loop_nest
, 0)
4854 analyze_all_data_dependences (loop_nest
);
4857 /* Free the memory used by a data dependence relation DDR. */
4860 free_dependence_relation (struct data_dependence_relation
*ddr
)
4865 if (DDR_SUBSCRIPTS (ddr
).exists ())
4866 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4867 DDR_DIST_VECTS (ddr
).release ();
4868 DDR_DIR_VECTS (ddr
).release ();
4873 /* Free the memory used by the data dependence relations from
4874 DEPENDENCE_RELATIONS. */
4877 free_dependence_relations (vec
<ddr_p
> dependence_relations
)
4880 struct data_dependence_relation
*ddr
;
4882 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
4884 free_dependence_relation (ddr
);
4886 dependence_relations
.release ();
4889 /* Free the memory used by the data references from DATAREFS. */
4892 free_data_refs (vec
<data_reference_p
> datarefs
)
4895 struct data_reference
*dr
;
4897 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
4899 datarefs
.release ();