1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
80 #include "gimple-pretty-print.h"
81 #include "tree-flow.h"
83 #include "tree-data-ref.h"
84 #include "tree-scalar-evolution.h"
86 #include "langhooks.h"
87 #include "tree-affine.h"
90 static struct datadep_stats
92 int num_dependence_tests
;
93 int num_dependence_dependent
;
94 int num_dependence_independent
;
95 int num_dependence_undetermined
;
97 int num_subscript_tests
;
98 int num_subscript_undetermined
;
99 int num_same_subscript_function
;
102 int num_ziv_independent
;
103 int num_ziv_dependent
;
104 int num_ziv_unimplemented
;
107 int num_siv_independent
;
108 int num_siv_dependent
;
109 int num_siv_unimplemented
;
112 int num_miv_independent
;
113 int num_miv_dependent
;
114 int num_miv_unimplemented
;
117 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
118 struct data_reference
*,
119 struct data_reference
*,
121 /* Returns true iff A divides B. */
124 tree_fold_divides_p (const_tree a
, const_tree b
)
126 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
127 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
128 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
));
131 /* Returns true iff A divides B. */
134 int_divides_p (int a
, int b
)
136 return ((b
% a
) == 0);
141 /* Dump into FILE all the data references from DATAREFS. */
144 dump_data_references (FILE *file
, vec
<data_reference_p
> datarefs
)
147 struct data_reference
*dr
;
149 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
150 dump_data_reference (file
, dr
);
153 /* Dump into STDERR all the data references from DATAREFS. */
156 debug_data_references (vec
<data_reference_p
> datarefs
)
158 dump_data_references (stderr
, datarefs
);
161 /* Print to STDERR the data_reference DR. */
164 debug_data_reference (struct data_reference
*dr
)
166 dump_data_reference (stderr
, dr
);
169 /* Dump function for a DATA_REFERENCE structure. */
172 dump_data_reference (FILE *outf
,
173 struct data_reference
*dr
)
177 fprintf (outf
, "#(Data Ref: \n");
178 fprintf (outf
, "# bb: %d \n", gimple_bb (DR_STMT (dr
))->index
);
179 fprintf (outf
, "# stmt: ");
180 print_gimple_stmt (outf
, DR_STMT (dr
), 0, 0);
181 fprintf (outf
, "# ref: ");
182 print_generic_stmt (outf
, DR_REF (dr
), 0);
183 fprintf (outf
, "# base_object: ");
184 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
186 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
188 fprintf (outf
, "# Access function %d: ", i
);
189 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
191 fprintf (outf
, "#)\n");
194 /* Dumps the affine function described by FN to the file OUTF. */
197 dump_affine_function (FILE *outf
, affine_fn fn
)
202 print_generic_expr (outf
, fn
[0], TDF_SLIM
);
203 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
205 fprintf (outf
, " + ");
206 print_generic_expr (outf
, coef
, TDF_SLIM
);
207 fprintf (outf
, " * x_%u", i
);
211 /* Dumps the conflict function CF to the file OUTF. */
214 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
218 if (cf
->n
== NO_DEPENDENCE
)
219 fprintf (outf
, "no dependence");
220 else if (cf
->n
== NOT_KNOWN
)
221 fprintf (outf
, "not known");
224 for (i
= 0; i
< cf
->n
; i
++)
229 dump_affine_function (outf
, cf
->fns
[i
]);
235 /* Dump function for a SUBSCRIPT structure. */
238 dump_subscript (FILE *outf
, struct subscript
*subscript
)
240 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
242 fprintf (outf
, "\n (subscript \n");
243 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
244 dump_conflict_function (outf
, cf
);
245 if (CF_NONTRIVIAL_P (cf
))
247 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
248 fprintf (outf
, "\n last_conflict: ");
249 print_generic_expr (outf
, last_iteration
, 0);
252 cf
= SUB_CONFLICTS_IN_B (subscript
);
253 fprintf (outf
, "\n iterations_that_access_an_element_twice_in_B: ");
254 dump_conflict_function (outf
, cf
);
255 if (CF_NONTRIVIAL_P (cf
))
257 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
258 fprintf (outf
, "\n last_conflict: ");
259 print_generic_expr (outf
, last_iteration
, 0);
262 fprintf (outf
, "\n (Subscript distance: ");
263 print_generic_expr (outf
, SUB_DISTANCE (subscript
), 0);
264 fprintf (outf
, " ))\n");
267 /* Print the classic direction vector DIRV to OUTF. */
270 print_direction_vector (FILE *outf
,
276 for (eq
= 0; eq
< length
; eq
++)
278 enum data_dependence_direction dir
= ((enum data_dependence_direction
)
284 fprintf (outf
, " +");
287 fprintf (outf
, " -");
290 fprintf (outf
, " =");
292 case dir_positive_or_equal
:
293 fprintf (outf
, " +=");
295 case dir_positive_or_negative
:
296 fprintf (outf
, " +-");
298 case dir_negative_or_equal
:
299 fprintf (outf
, " -=");
302 fprintf (outf
, " *");
305 fprintf (outf
, "indep");
309 fprintf (outf
, "\n");
312 /* Print a vector of direction vectors. */
315 print_dir_vectors (FILE *outf
, vec
<lambda_vector
> dir_vects
,
321 FOR_EACH_VEC_ELT (dir_vects
, j
, v
)
322 print_direction_vector (outf
, v
, length
);
325 /* Print out a vector VEC of length N to OUTFILE. */
328 print_lambda_vector (FILE * outfile
, lambda_vector vector
, int n
)
332 for (i
= 0; i
< n
; i
++)
333 fprintf (outfile
, "%3d ", vector
[i
]);
334 fprintf (outfile
, "\n");
337 /* Print a vector of distance vectors. */
340 print_dist_vectors (FILE *outf
, vec
<lambda_vector
> dist_vects
,
346 FOR_EACH_VEC_ELT (dist_vects
, j
, v
)
347 print_lambda_vector (outf
, v
, length
);
350 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
353 dump_data_dependence_relation (FILE *outf
,
354 struct data_dependence_relation
*ddr
)
356 struct data_reference
*dra
, *drb
;
358 fprintf (outf
, "(Data Dep: \n");
360 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
367 dump_data_reference (outf
, dra
);
369 fprintf (outf
, " (nil)\n");
371 dump_data_reference (outf
, drb
);
373 fprintf (outf
, " (nil)\n");
375 fprintf (outf
, " (don't know)\n)\n");
381 dump_data_reference (outf
, dra
);
382 dump_data_reference (outf
, drb
);
384 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
385 fprintf (outf
, " (no dependence)\n");
387 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
392 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
394 fprintf (outf
, " access_fn_A: ");
395 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
396 fprintf (outf
, " access_fn_B: ");
397 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
398 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
401 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
402 fprintf (outf
, " loop nest: (");
403 FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr
), i
, loopi
)
404 fprintf (outf
, "%d ", loopi
->num
);
405 fprintf (outf
, ")\n");
407 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
409 fprintf (outf
, " distance_vector: ");
410 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
414 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
416 fprintf (outf
, " direction_vector: ");
417 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
422 fprintf (outf
, ")\n");
428 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
430 dump_data_dependence_relation (stderr
, ddr
);
433 /* Dump into FILE all the dependence relations from DDRS. */
436 dump_data_dependence_relations (FILE *file
,
440 struct data_dependence_relation
*ddr
;
442 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
443 dump_data_dependence_relation (file
, ddr
);
446 /* Dump to STDERR all the dependence relations from DDRS. */
449 debug_data_dependence_relations (vec
<ddr_p
> ddrs
)
451 dump_data_dependence_relations (stderr
, ddrs
);
454 /* Dumps the distance and direction vectors in FILE. DDRS contains
455 the dependence relations, and VECT_SIZE is the size of the
456 dependence vectors, or in other words the number of loops in the
460 dump_dist_dir_vectors (FILE *file
, vec
<ddr_p
> ddrs
)
463 struct data_dependence_relation
*ddr
;
466 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
467 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
469 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), j
, v
)
471 fprintf (file
, "DISTANCE_V (");
472 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
473 fprintf (file
, ")\n");
476 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), j
, v
)
478 fprintf (file
, "DIRECTION_V (");
479 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
480 fprintf (file
, ")\n");
484 fprintf (file
, "\n\n");
487 /* Dumps the data dependence relations DDRS in FILE. */
490 dump_ddrs (FILE *file
, vec
<ddr_p
> ddrs
)
493 struct data_dependence_relation
*ddr
;
495 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
496 dump_data_dependence_relation (file
, ddr
);
498 fprintf (file
, "\n\n");
502 debug_ddrs (vec
<ddr_p
> ddrs
)
504 dump_ddrs (stderr
, ddrs
);
507 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
508 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
509 constant of type ssizetype, and returns true. If we cannot do this
510 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
514 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
515 tree
*var
, tree
*off
)
519 enum tree_code ocode
= code
;
527 *var
= build_int_cst (type
, 0);
528 *off
= fold_convert (ssizetype
, op0
);
531 case POINTER_PLUS_EXPR
:
536 split_constant_offset (op0
, &var0
, &off0
);
537 split_constant_offset (op1
, &var1
, &off1
);
538 *var
= fold_build2 (code
, type
, var0
, var1
);
539 *off
= size_binop (ocode
, off0
, off1
);
543 if (TREE_CODE (op1
) != INTEGER_CST
)
546 split_constant_offset (op0
, &var0
, &off0
);
547 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
548 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
554 HOST_WIDE_INT pbitsize
, pbitpos
;
555 enum machine_mode pmode
;
556 int punsignedp
, pvolatilep
;
558 op0
= TREE_OPERAND (op0
, 0);
559 base
= get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
,
560 &pmode
, &punsignedp
, &pvolatilep
, false);
562 if (pbitpos
% BITS_PER_UNIT
!= 0)
564 base
= build_fold_addr_expr (base
);
565 off0
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
569 split_constant_offset (poffset
, &poffset
, &off1
);
570 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
571 if (POINTER_TYPE_P (TREE_TYPE (base
)))
572 base
= fold_build_pointer_plus (base
, poffset
);
574 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
575 fold_convert (TREE_TYPE (base
), poffset
));
578 var0
= fold_convert (type
, base
);
580 /* If variable length types are involved, punt, otherwise casts
581 might be converted into ARRAY_REFs in gimplify_conversion.
582 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
583 possibly no longer appears in current GIMPLE, might resurface.
584 This perhaps could run
585 if (CONVERT_EXPR_P (var0))
587 gimplify_conversion (&var0);
588 // Attempt to fill in any within var0 found ARRAY_REF's
589 // element size from corresponding op embedded ARRAY_REF,
590 // if unsuccessful, just punt.
592 while (POINTER_TYPE_P (type
))
593 type
= TREE_TYPE (type
);
594 if (int_size_in_bytes (type
) < 0)
604 gimple def_stmt
= SSA_NAME_DEF_STMT (op0
);
605 enum tree_code subcode
;
607 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
610 var0
= gimple_assign_rhs1 (def_stmt
);
611 subcode
= gimple_assign_rhs_code (def_stmt
);
612 var1
= gimple_assign_rhs2 (def_stmt
);
614 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
618 /* We must not introduce undefined overflow, and we must not change the value.
619 Hence we're okay if the inner type doesn't overflow to start with
620 (pointer or signed), the outer type also is an integer or pointer
621 and the outer precision is at least as large as the inner. */
622 tree itype
= TREE_TYPE (op0
);
623 if ((POINTER_TYPE_P (itype
)
624 || (INTEGRAL_TYPE_P (itype
) && TYPE_OVERFLOW_UNDEFINED (itype
)))
625 && TYPE_PRECISION (type
) >= TYPE_PRECISION (itype
)
626 && (POINTER_TYPE_P (type
) || INTEGRAL_TYPE_P (type
)))
628 split_constant_offset (op0
, &var0
, off
);
629 *var
= fold_convert (type
, var0
);
640 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
641 will be ssizetype. */
644 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
646 tree type
= TREE_TYPE (exp
), otype
, op0
, op1
, e
, o
;
650 *off
= ssize_int (0);
653 if (tree_is_chrec (exp
)
654 || get_gimple_rhs_class (TREE_CODE (exp
)) == GIMPLE_TERNARY_RHS
)
657 otype
= TREE_TYPE (exp
);
658 code
= TREE_CODE (exp
);
659 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
660 if (split_constant_offset_1 (otype
, op0
, code
, op1
, &e
, &o
))
662 *var
= fold_convert (type
, e
);
667 /* Returns the address ADDR of an object in a canonical shape (without nop
668 casts, and with type of pointer to the object). */
671 canonicalize_base_object_address (tree addr
)
677 /* The base address may be obtained by casting from integer, in that case
679 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
682 if (TREE_CODE (addr
) != ADDR_EXPR
)
685 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
688 /* Analyzes the behavior of the memory reference DR in the innermost loop or
689 basic block that contains it. Returns true if analysis succeed or false
693 dr_analyze_innermost (struct data_reference
*dr
, struct loop
*nest
)
695 gimple stmt
= DR_STMT (dr
);
696 struct loop
*loop
= loop_containing_stmt (stmt
);
697 tree ref
= DR_REF (dr
);
698 HOST_WIDE_INT pbitsize
, pbitpos
;
700 enum machine_mode pmode
;
701 int punsignedp
, pvolatilep
;
702 affine_iv base_iv
, offset_iv
;
703 tree init
, dinit
, step
;
704 bool in_loop
= (loop
&& loop
->num
);
706 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
707 fprintf (dump_file
, "analyze_innermost: ");
709 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
,
710 &pmode
, &punsignedp
, &pvolatilep
, false);
711 gcc_assert (base
!= NULL_TREE
);
713 if (pbitpos
% BITS_PER_UNIT
!= 0)
715 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
716 fprintf (dump_file
, "failed: bit offset alignment.\n");
720 if (TREE_CODE (base
) == MEM_REF
)
722 if (!integer_zerop (TREE_OPERAND (base
, 1)))
724 double_int moff
= mem_ref_offset (base
);
725 tree mofft
= double_int_to_tree (sizetype
, moff
);
729 poffset
= size_binop (PLUS_EXPR
, poffset
, mofft
);
731 base
= TREE_OPERAND (base
, 0);
734 base
= build_fold_addr_expr (base
);
738 if (!simple_iv (loop
, loop_containing_stmt (stmt
), base
, &base_iv
,
739 nest
? true : false))
743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
744 fprintf (dump_file
, "failed: evolution of base is not"
751 base_iv
.step
= ssize_int (0);
752 base_iv
.no_overflow
= true;
759 base_iv
.step
= ssize_int (0);
760 base_iv
.no_overflow
= true;
765 offset_iv
.base
= ssize_int (0);
766 offset_iv
.step
= ssize_int (0);
772 offset_iv
.base
= poffset
;
773 offset_iv
.step
= ssize_int (0);
775 else if (!simple_iv (loop
, loop_containing_stmt (stmt
),
777 nest
? true : false))
781 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
782 fprintf (dump_file
, "failed: evolution of offset is not"
788 offset_iv
.base
= poffset
;
789 offset_iv
.step
= ssize_int (0);
794 init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
795 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
796 init
= size_binop (PLUS_EXPR
, init
, dinit
);
797 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
798 init
= size_binop (PLUS_EXPR
, init
, dinit
);
800 step
= size_binop (PLUS_EXPR
,
801 fold_convert (ssizetype
, base_iv
.step
),
802 fold_convert (ssizetype
, offset_iv
.step
));
804 DR_BASE_ADDRESS (dr
) = canonicalize_base_object_address (base_iv
.base
);
806 DR_OFFSET (dr
) = fold_convert (ssizetype
, offset_iv
.base
);
810 DR_ALIGNED_TO (dr
) = size_int (highest_pow2_factor (offset_iv
.base
));
812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
813 fprintf (dump_file
, "success.\n");
818 /* Determines the base object and the list of indices of memory reference
819 DR, analyzed in LOOP and instantiated in loop nest NEST. */
822 dr_analyze_indices (struct data_reference
*dr
, loop_p nest
, loop_p loop
)
824 vec
<tree
> access_fns
= vNULL
;
826 tree base
, off
, access_fn
;
827 basic_block before_loop
;
829 /* If analyzing a basic-block there are no indices to analyze
830 and thus no access functions. */
833 DR_BASE_OBJECT (dr
) = DR_REF (dr
);
834 DR_ACCESS_FNS (dr
).create (0);
839 before_loop
= block_before_loop (nest
);
841 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
842 into a two element array with a constant index. The base is
843 then just the immediate underlying object. */
844 if (TREE_CODE (ref
) == REALPART_EXPR
)
846 ref
= TREE_OPERAND (ref
, 0);
847 access_fns
.safe_push (integer_zero_node
);
849 else if (TREE_CODE (ref
) == IMAGPART_EXPR
)
851 ref
= TREE_OPERAND (ref
, 0);
852 access_fns
.safe_push (integer_one_node
);
855 /* Analyze access functions of dimensions we know to be independent. */
856 while (handled_component_p (ref
))
858 if (TREE_CODE (ref
) == ARRAY_REF
)
860 op
= TREE_OPERAND (ref
, 1);
861 access_fn
= analyze_scalar_evolution (loop
, op
);
862 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
863 access_fns
.safe_push (access_fn
);
865 else if (TREE_CODE (ref
) == COMPONENT_REF
866 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref
, 0))) == RECORD_TYPE
)
868 /* For COMPONENT_REFs of records (but not unions!) use the
869 FIELD_DECL offset as constant access function so we can
870 disambiguate a[i].f1 and a[i].f2. */
871 tree off
= component_ref_field_offset (ref
);
872 off
= size_binop (PLUS_EXPR
,
873 size_binop (MULT_EXPR
,
874 fold_convert (bitsizetype
, off
),
875 bitsize_int (BITS_PER_UNIT
)),
876 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1)));
877 access_fns
.safe_push (off
);
880 /* If we have an unhandled component we could not translate
881 to an access function stop analyzing. We have determined
882 our base object in this case. */
885 ref
= TREE_OPERAND (ref
, 0);
888 /* If the address operand of a MEM_REF base has an evolution in the
889 analyzed nest, add it as an additional independent access-function. */
890 if (TREE_CODE (ref
) == MEM_REF
)
892 op
= TREE_OPERAND (ref
, 0);
893 access_fn
= analyze_scalar_evolution (loop
, op
);
894 access_fn
= instantiate_scev (before_loop
, loop
, access_fn
);
895 if (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
898 tree memoff
= TREE_OPERAND (ref
, 1);
899 base
= initial_condition (access_fn
);
900 orig_type
= TREE_TYPE (base
);
901 STRIP_USELESS_TYPE_CONVERSION (base
);
902 split_constant_offset (base
, &base
, &off
);
903 /* Fold the MEM_REF offset into the evolutions initial
904 value to make more bases comparable. */
905 if (!integer_zerop (memoff
))
907 off
= size_binop (PLUS_EXPR
, off
,
908 fold_convert (ssizetype
, memoff
));
909 memoff
= build_int_cst (TREE_TYPE (memoff
), 0);
911 access_fn
= chrec_replace_initial_condition
912 (access_fn
, fold_convert (orig_type
, off
));
913 /* ??? This is still not a suitable base object for
914 dr_may_alias_p - the base object needs to be an
915 access that covers the object as whole. With
916 an evolution in the pointer this cannot be
918 As a band-aid, mark the access so we can special-case
919 it in dr_may_alias_p. */
920 ref
= fold_build2_loc (EXPR_LOCATION (ref
),
921 MEM_REF
, TREE_TYPE (ref
),
923 DR_UNCONSTRAINED_BASE (dr
) = true;
924 access_fns
.safe_push (access_fn
);
927 else if (DECL_P (ref
))
929 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
930 ref
= build2 (MEM_REF
, TREE_TYPE (ref
),
931 build_fold_addr_expr (ref
),
932 build_int_cst (reference_alias_ptr_type (ref
), 0));
935 DR_BASE_OBJECT (dr
) = ref
;
936 DR_ACCESS_FNS (dr
) = access_fns
;
939 /* Extracts the alias analysis information from the memory reference DR. */
942 dr_analyze_alias (struct data_reference
*dr
)
944 tree ref
= DR_REF (dr
);
945 tree base
= get_base_address (ref
), addr
;
947 if (INDIRECT_REF_P (base
)
948 || TREE_CODE (base
) == MEM_REF
)
950 addr
= TREE_OPERAND (base
, 0);
951 if (TREE_CODE (addr
) == SSA_NAME
)
952 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
956 /* Frees data reference DR. */
959 free_data_ref (data_reference_p dr
)
961 DR_ACCESS_FNS (dr
).release ();
965 /* Analyzes memory reference MEMREF accessed in STMT. The reference
966 is read if IS_READ is true, write otherwise. Returns the
967 data_reference description of MEMREF. NEST is the outermost loop
968 in which the reference should be instantiated, LOOP is the loop in
969 which the data reference should be analyzed. */
971 struct data_reference
*
972 create_data_ref (loop_p nest
, loop_p loop
, tree memref
, gimple stmt
,
975 struct data_reference
*dr
;
977 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
979 fprintf (dump_file
, "Creating dr for ");
980 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
981 fprintf (dump_file
, "\n");
984 dr
= XCNEW (struct data_reference
);
986 DR_REF (dr
) = memref
;
987 DR_IS_READ (dr
) = is_read
;
989 dr_analyze_innermost (dr
, nest
);
990 dr_analyze_indices (dr
, nest
, loop
);
991 dr_analyze_alias (dr
);
993 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
996 fprintf (dump_file
, "\tbase_address: ");
997 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
998 fprintf (dump_file
, "\n\toffset from base address: ");
999 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
1000 fprintf (dump_file
, "\n\tconstant offset from base address: ");
1001 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
1002 fprintf (dump_file
, "\n\tstep: ");
1003 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
1004 fprintf (dump_file
, "\n\taligned to: ");
1005 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
1006 fprintf (dump_file
, "\n\tbase_object: ");
1007 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
1008 fprintf (dump_file
, "\n");
1009 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
1011 fprintf (dump_file
, "\tAccess function %d: ", i
);
1012 print_generic_stmt (dump_file
, DR_ACCESS_FN (dr
, i
), TDF_SLIM
);
1019 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1022 dr_equal_offsets_p1 (tree offset1
, tree offset2
)
1026 STRIP_NOPS (offset1
);
1027 STRIP_NOPS (offset2
);
1029 if (offset1
== offset2
)
1032 if (TREE_CODE (offset1
) != TREE_CODE (offset2
)
1033 || (!BINARY_CLASS_P (offset1
) && !UNARY_CLASS_P (offset1
)))
1036 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 0),
1037 TREE_OPERAND (offset2
, 0));
1039 if (!res
|| !BINARY_CLASS_P (offset1
))
1042 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 1),
1043 TREE_OPERAND (offset2
, 1));
1048 /* Check if DRA and DRB have equal offsets. */
1050 dr_equal_offsets_p (struct data_reference
*dra
,
1051 struct data_reference
*drb
)
1053 tree offset1
, offset2
;
1055 offset1
= DR_OFFSET (dra
);
1056 offset2
= DR_OFFSET (drb
);
1058 return dr_equal_offsets_p1 (offset1
, offset2
);
1061 /* Returns true if FNA == FNB. */
1064 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
1066 unsigned i
, n
= fna
.length ();
1068 if (n
!= fnb
.length ())
1071 for (i
= 0; i
< n
; i
++)
1072 if (!operand_equal_p (fna
[i
], fnb
[i
], 0))
1078 /* If all the functions in CF are the same, returns one of them,
1079 otherwise returns NULL. */
1082 common_affine_function (conflict_function
*cf
)
1087 if (!CF_NONTRIVIAL_P (cf
))
1092 for (i
= 1; i
< cf
->n
; i
++)
1093 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
1099 /* Returns the base of the affine function FN. */
1102 affine_function_base (affine_fn fn
)
1107 /* Returns true if FN is a constant. */
1110 affine_function_constant_p (affine_fn fn
)
1115 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
1116 if (!integer_zerop (coef
))
1122 /* Returns true if FN is the zero constant function. */
1125 affine_function_zero_p (affine_fn fn
)
1127 return (integer_zerop (affine_function_base (fn
))
1128 && affine_function_constant_p (fn
));
1131 /* Returns a signed integer type with the largest precision from TA
1135 signed_type_for_types (tree ta
, tree tb
)
1137 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
1138 return signed_type_for (ta
);
1140 return signed_type_for (tb
);
1143 /* Applies operation OP on affine functions FNA and FNB, and returns the
1147 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
1153 if (fnb
.length () > fna
.length ())
1165 for (i
= 0; i
< n
; i
++)
1167 tree type
= signed_type_for_types (TREE_TYPE (fna
[i
]),
1168 TREE_TYPE (fnb
[i
]));
1169 ret
.quick_push (fold_build2 (op
, type
, fna
[i
], fnb
[i
]));
1172 for (; fna
.iterate (i
, &coef
); i
++)
1173 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1174 coef
, integer_zero_node
));
1175 for (; fnb
.iterate (i
, &coef
); i
++)
1176 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
1177 integer_zero_node
, coef
));
1182 /* Returns the sum of affine functions FNA and FNB. */
1185 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
1187 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
1190 /* Returns the difference of affine functions FNA and FNB. */
1193 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
1195 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
1198 /* Frees affine function FN. */
1201 affine_fn_free (affine_fn fn
)
1206 /* Determine for each subscript in the data dependence relation DDR
1210 compute_subscript_distance (struct data_dependence_relation
*ddr
)
1212 conflict_function
*cf_a
, *cf_b
;
1213 affine_fn fn_a
, fn_b
, diff
;
1215 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1219 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1221 struct subscript
*subscript
;
1223 subscript
= DDR_SUBSCRIPT (ddr
, i
);
1224 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
1225 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
1227 fn_a
= common_affine_function (cf_a
);
1228 fn_b
= common_affine_function (cf_b
);
1229 if (!fn_a
.exists () || !fn_b
.exists ())
1231 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1234 diff
= affine_fn_minus (fn_a
, fn_b
);
1236 if (affine_function_constant_p (diff
))
1237 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
1239 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1241 affine_fn_free (diff
);
1246 /* Returns the conflict function for "unknown". */
1248 static conflict_function
*
1249 conflict_fn_not_known (void)
1251 conflict_function
*fn
= XCNEW (conflict_function
);
1257 /* Returns the conflict function for "independent". */
1259 static conflict_function
*
1260 conflict_fn_no_dependence (void)
1262 conflict_function
*fn
= XCNEW (conflict_function
);
1263 fn
->n
= NO_DEPENDENCE
;
1268 /* Returns true if the address of OBJ is invariant in LOOP. */
1271 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
1273 while (handled_component_p (obj
))
1275 if (TREE_CODE (obj
) == ARRAY_REF
)
1277 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1278 need to check the stride and the lower bound of the reference. */
1279 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1281 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 3),
1285 else if (TREE_CODE (obj
) == COMPONENT_REF
)
1287 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
1291 obj
= TREE_OPERAND (obj
, 0);
1294 if (!INDIRECT_REF_P (obj
)
1295 && TREE_CODE (obj
) != MEM_REF
)
1298 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
1302 /* Returns false if we can prove that data references A and B do not alias,
1303 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1307 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
,
1310 tree addr_a
= DR_BASE_OBJECT (a
);
1311 tree addr_b
= DR_BASE_OBJECT (b
);
1313 /* If we are not processing a loop nest but scalar code we
1314 do not need to care about possible cross-iteration dependences
1315 and thus can process the full original reference. Do so,
1316 similar to how loop invariant motion applies extra offset-based
1320 aff_tree off1
, off2
;
1321 double_int size1
, size2
;
1322 get_inner_reference_aff (DR_REF (a
), &off1
, &size1
);
1323 get_inner_reference_aff (DR_REF (b
), &off2
, &size2
);
1324 aff_combination_scale (&off1
, double_int_minus_one
);
1325 aff_combination_add (&off2
, &off1
);
1326 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1330 /* If we had an evolution in a MEM_REF BASE_OBJECT we do not know
1331 the size of the base-object. So we cannot do any offset/overlap
1332 based analysis but have to rely on points-to information only. */
1333 if (TREE_CODE (addr_a
) == MEM_REF
1334 && DR_UNCONSTRAINED_BASE (a
))
1336 if (TREE_CODE (addr_b
) == MEM_REF
1337 && DR_UNCONSTRAINED_BASE (b
))
1338 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1339 TREE_OPERAND (addr_b
, 0));
1341 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
1342 build_fold_addr_expr (addr_b
));
1344 else if (TREE_CODE (addr_b
) == MEM_REF
1345 && DR_UNCONSTRAINED_BASE (b
))
1346 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a
),
1347 TREE_OPERAND (addr_b
, 0));
1349 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
1350 that is being subsetted in the loop nest. */
1351 if (DR_IS_WRITE (a
) && DR_IS_WRITE (b
))
1352 return refs_output_dependent_p (addr_a
, addr_b
);
1353 else if (DR_IS_READ (a
) && DR_IS_WRITE (b
))
1354 return refs_anti_dependent_p (addr_a
, addr_b
);
1355 return refs_may_alias_p (addr_a
, addr_b
);
1358 /* Initialize a data dependence relation between data accesses A and
1359 B. NB_LOOPS is the number of loops surrounding the references: the
1360 size of the classic distance/direction vectors. */
1362 struct data_dependence_relation
*
1363 initialize_data_dependence_relation (struct data_reference
*a
,
1364 struct data_reference
*b
,
1365 vec
<loop_p
> loop_nest
)
1367 struct data_dependence_relation
*res
;
1370 res
= XNEW (struct data_dependence_relation
);
1373 DDR_LOOP_NEST (res
).create (0);
1374 DDR_REVERSED_P (res
) = false;
1375 DDR_SUBSCRIPTS (res
).create (0);
1376 DDR_DIR_VECTS (res
).create (0);
1377 DDR_DIST_VECTS (res
).create (0);
1379 if (a
== NULL
|| b
== NULL
)
1381 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1385 /* If the data references do not alias, then they are independent. */
1386 if (!dr_may_alias_p (a
, b
, loop_nest
.exists ()))
1388 DDR_ARE_DEPENDENT (res
) = chrec_known
;
1392 /* The case where the references are exactly the same. */
1393 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
1395 if (loop_nest
.exists ()
1396 && !object_address_invariant_in_loop_p (loop_nest
[0],
1397 DR_BASE_OBJECT (a
)))
1399 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1402 DDR_AFFINE_P (res
) = true;
1403 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1404 DDR_SUBSCRIPTS (res
).create (DR_NUM_DIMENSIONS (a
));
1405 DDR_LOOP_NEST (res
) = loop_nest
;
1406 DDR_INNER_LOOP (res
) = 0;
1407 DDR_SELF_REFERENCE (res
) = true;
1408 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1410 struct subscript
*subscript
;
1412 subscript
= XNEW (struct subscript
);
1413 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1414 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1415 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1416 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1417 DDR_SUBSCRIPTS (res
).safe_push (subscript
);
1422 /* If the references do not access the same object, we do not know
1423 whether they alias or not. */
1424 if (!operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0))
1426 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1430 /* If the base of the object is not invariant in the loop nest, we cannot
1431 analyze it. TODO -- in fact, it would suffice to record that there may
1432 be arbitrary dependences in the loops where the base object varies. */
1433 if (loop_nest
.exists ()
1434 && !object_address_invariant_in_loop_p (loop_nest
[0],
1435 DR_BASE_OBJECT (a
)))
1437 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1441 /* If the number of dimensions of the access to not agree we can have
1442 a pointer access to a component of the array element type and an
1443 array access while the base-objects are still the same. Punt. */
1444 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
1446 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
1450 DDR_AFFINE_P (res
) = true;
1451 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
1452 DDR_SUBSCRIPTS (res
).create (DR_NUM_DIMENSIONS (a
));
1453 DDR_LOOP_NEST (res
) = loop_nest
;
1454 DDR_INNER_LOOP (res
) = 0;
1455 DDR_SELF_REFERENCE (res
) = false;
1457 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
1459 struct subscript
*subscript
;
1461 subscript
= XNEW (struct subscript
);
1462 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
1463 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
1464 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
1465 SUB_DISTANCE (subscript
) = chrec_dont_know
;
1466 DDR_SUBSCRIPTS (res
).safe_push (subscript
);
1472 /* Frees memory used by the conflict function F. */
1475 free_conflict_function (conflict_function
*f
)
1479 if (CF_NONTRIVIAL_P (f
))
1481 for (i
= 0; i
< f
->n
; i
++)
1482 affine_fn_free (f
->fns
[i
]);
1487 /* Frees memory used by SUBSCRIPTS. */
1490 free_subscripts (vec
<subscript_p
> subscripts
)
1495 FOR_EACH_VEC_ELT (subscripts
, i
, s
)
1497 free_conflict_function (s
->conflicting_iterations_in_a
);
1498 free_conflict_function (s
->conflicting_iterations_in_b
);
1501 subscripts
.release ();
1504 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1508 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
1511 DDR_ARE_DEPENDENT (ddr
) = chrec
;
1512 free_subscripts (DDR_SUBSCRIPTS (ddr
));
1513 DDR_SUBSCRIPTS (ddr
).create (0);
1516 /* The dependence relation DDR cannot be represented by a distance
1520 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
1522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1523 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
1525 DDR_AFFINE_P (ddr
) = false;
1530 /* This section contains the classic Banerjee tests. */
1532 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1533 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1536 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1538 return (evolution_function_is_constant_p (chrec_a
)
1539 && evolution_function_is_constant_p (chrec_b
));
1542 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1543 variable, i.e., if the SIV (Single Index Variable) test is true. */
1546 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
1548 if ((evolution_function_is_constant_p (chrec_a
)
1549 && evolution_function_is_univariate_p (chrec_b
))
1550 || (evolution_function_is_constant_p (chrec_b
)
1551 && evolution_function_is_univariate_p (chrec_a
)))
1554 if (evolution_function_is_univariate_p (chrec_a
)
1555 && evolution_function_is_univariate_p (chrec_b
))
1557 switch (TREE_CODE (chrec_a
))
1559 case POLYNOMIAL_CHREC
:
1560 switch (TREE_CODE (chrec_b
))
1562 case POLYNOMIAL_CHREC
:
1563 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
1578 /* Creates a conflict function with N dimensions. The affine functions
1579 in each dimension follow. */
1581 static conflict_function
*
1582 conflict_fn (unsigned n
, ...)
1585 conflict_function
*ret
= XCNEW (conflict_function
);
1588 gcc_assert (0 < n
&& n
<= MAX_DIM
);
1592 for (i
= 0; i
< n
; i
++)
1593 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
1599 /* Returns constant affine function with value CST. */
1602 affine_fn_cst (tree cst
)
1606 fn
.quick_push (cst
);
1610 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1613 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
1616 fn
.create (dim
+ 1);
1619 gcc_assert (dim
> 0);
1620 fn
.quick_push (cst
);
1621 for (i
= 1; i
< dim
; i
++)
1622 fn
.quick_push (integer_zero_node
);
1623 fn
.quick_push (coef
);
1627 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1628 *OVERLAPS_B are initialized to the functions that describe the
1629 relation between the elements accessed twice by CHREC_A and
1630 CHREC_B. For k >= 0, the following property is verified:
1632 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1635 analyze_ziv_subscript (tree chrec_a
,
1637 conflict_function
**overlaps_a
,
1638 conflict_function
**overlaps_b
,
1639 tree
*last_conflicts
)
1641 tree type
, difference
;
1642 dependence_stats
.num_ziv
++;
1644 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1645 fprintf (dump_file
, "(analyze_ziv_subscript \n");
1647 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1648 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1649 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1650 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
1652 switch (TREE_CODE (difference
))
1655 if (integer_zerop (difference
))
1657 /* The difference is equal to zero: the accessed index
1658 overlaps for each iteration in the loop. */
1659 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1660 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1661 *last_conflicts
= chrec_dont_know
;
1662 dependence_stats
.num_ziv_dependent
++;
1666 /* The accesses do not overlap. */
1667 *overlaps_a
= conflict_fn_no_dependence ();
1668 *overlaps_b
= conflict_fn_no_dependence ();
1669 *last_conflicts
= integer_zero_node
;
1670 dependence_stats
.num_ziv_independent
++;
1675 /* We're not sure whether the indexes overlap. For the moment,
1676 conservatively answer "don't know". */
1677 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1678 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
1680 *overlaps_a
= conflict_fn_not_known ();
1681 *overlaps_b
= conflict_fn_not_known ();
1682 *last_conflicts
= chrec_dont_know
;
1683 dependence_stats
.num_ziv_unimplemented
++;
1687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1688 fprintf (dump_file
, ")\n");
1691 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1692 and only if it fits to the int type. If this is not the case, or the
1693 bound on the number of iterations of LOOP could not be derived, returns
1697 max_stmt_executions_tree (struct loop
*loop
)
1701 if (!max_stmt_executions (loop
, &nit
))
1702 return chrec_dont_know
;
1704 if (!double_int_fits_to_tree_p (unsigned_type_node
, nit
))
1705 return chrec_dont_know
;
1707 return double_int_to_tree (unsigned_type_node
, nit
);
1710 /* Determine whether the CHREC is always positive/negative. If the expression
1711 cannot be statically analyzed, return false, otherwise set the answer into
1715 chrec_is_positive (tree chrec
, bool *value
)
1717 bool value0
, value1
, value2
;
1718 tree end_value
, nb_iter
;
1720 switch (TREE_CODE (chrec
))
1722 case POLYNOMIAL_CHREC
:
1723 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
1724 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
1727 /* FIXME -- overflows. */
1728 if (value0
== value1
)
1734 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
1735 and the proof consists in showing that the sign never
1736 changes during the execution of the loop, from 0 to
1737 loop->nb_iterations. */
1738 if (!evolution_function_is_affine_p (chrec
))
1741 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
1742 if (chrec_contains_undetermined (nb_iter
))
1746 /* TODO -- If the test is after the exit, we may decrease the number of
1747 iterations by one. */
1749 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
1752 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
1754 if (!chrec_is_positive (end_value
, &value2
))
1758 return value0
== value1
;
1761 switch (tree_int_cst_sgn (chrec
))
1780 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1781 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1782 *OVERLAPS_B are initialized to the functions that describe the
1783 relation between the elements accessed twice by CHREC_A and
1784 CHREC_B. For k >= 0, the following property is verified:
1786 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1789 analyze_siv_subscript_cst_affine (tree chrec_a
,
1791 conflict_function
**overlaps_a
,
1792 conflict_function
**overlaps_b
,
1793 tree
*last_conflicts
)
1795 bool value0
, value1
, value2
;
1796 tree type
, difference
, tmp
;
1798 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
1799 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
1800 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
1801 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
1803 /* Special case overlap in the first iteration. */
1804 if (integer_zerop (difference
))
1806 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1807 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1808 *last_conflicts
= integer_one_node
;
1812 if (!chrec_is_positive (initial_condition (difference
), &value0
))
1814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1815 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
1817 dependence_stats
.num_siv_unimplemented
++;
1818 *overlaps_a
= conflict_fn_not_known ();
1819 *overlaps_b
= conflict_fn_not_known ();
1820 *last_conflicts
= chrec_dont_know
;
1825 if (value0
== false)
1827 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
1829 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1830 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1832 *overlaps_a
= conflict_fn_not_known ();
1833 *overlaps_b
= conflict_fn_not_known ();
1834 *last_conflicts
= chrec_dont_know
;
1835 dependence_stats
.num_siv_unimplemented
++;
1844 chrec_b = {10, +, 1}
1847 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1849 HOST_WIDE_INT numiter
;
1850 struct loop
*loop
= get_chrec_loop (chrec_b
);
1852 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1853 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
1854 fold_build1 (ABS_EXPR
, type
, difference
),
1855 CHREC_RIGHT (chrec_b
));
1856 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1857 *last_conflicts
= integer_one_node
;
1860 /* Perform weak-zero siv test to see if overlap is
1861 outside the loop bounds. */
1862 numiter
= max_stmt_executions_int (loop
);
1865 && compare_tree_int (tmp
, numiter
) > 0)
1867 free_conflict_function (*overlaps_a
);
1868 free_conflict_function (*overlaps_b
);
1869 *overlaps_a
= conflict_fn_no_dependence ();
1870 *overlaps_b
= conflict_fn_no_dependence ();
1871 *last_conflicts
= integer_zero_node
;
1872 dependence_stats
.num_siv_independent
++;
1875 dependence_stats
.num_siv_dependent
++;
1879 /* When the step does not divide the difference, there are
1883 *overlaps_a
= conflict_fn_no_dependence ();
1884 *overlaps_b
= conflict_fn_no_dependence ();
1885 *last_conflicts
= integer_zero_node
;
1886 dependence_stats
.num_siv_independent
++;
1895 chrec_b = {10, +, -1}
1897 In this case, chrec_a will not overlap with chrec_b. */
1898 *overlaps_a
= conflict_fn_no_dependence ();
1899 *overlaps_b
= conflict_fn_no_dependence ();
1900 *last_conflicts
= integer_zero_node
;
1901 dependence_stats
.num_siv_independent
++;
1908 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
1910 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1911 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
1913 *overlaps_a
= conflict_fn_not_known ();
1914 *overlaps_b
= conflict_fn_not_known ();
1915 *last_conflicts
= chrec_dont_know
;
1916 dependence_stats
.num_siv_unimplemented
++;
1921 if (value2
== false)
1925 chrec_b = {10, +, -1}
1927 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
1929 HOST_WIDE_INT numiter
;
1930 struct loop
*loop
= get_chrec_loop (chrec_b
);
1932 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
1933 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
1934 CHREC_RIGHT (chrec_b
));
1935 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
1936 *last_conflicts
= integer_one_node
;
1938 /* Perform weak-zero siv test to see if overlap is
1939 outside the loop bounds. */
1940 numiter
= max_stmt_executions_int (loop
);
1943 && compare_tree_int (tmp
, numiter
) > 0)
1945 free_conflict_function (*overlaps_a
);
1946 free_conflict_function (*overlaps_b
);
1947 *overlaps_a
= conflict_fn_no_dependence ();
1948 *overlaps_b
= conflict_fn_no_dependence ();
1949 *last_conflicts
= integer_zero_node
;
1950 dependence_stats
.num_siv_independent
++;
1953 dependence_stats
.num_siv_dependent
++;
1957 /* When the step does not divide the difference, there
1961 *overlaps_a
= conflict_fn_no_dependence ();
1962 *overlaps_b
= conflict_fn_no_dependence ();
1963 *last_conflicts
= integer_zero_node
;
1964 dependence_stats
.num_siv_independent
++;
1974 In this case, chrec_a will not overlap with chrec_b. */
1975 *overlaps_a
= conflict_fn_no_dependence ();
1976 *overlaps_b
= conflict_fn_no_dependence ();
1977 *last_conflicts
= integer_zero_node
;
1978 dependence_stats
.num_siv_independent
++;
1986 /* Helper recursive function for initializing the matrix A. Returns
1987 the initial value of CHREC. */
1990 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1994 switch (TREE_CODE (chrec
))
1996 case POLYNOMIAL_CHREC
:
1997 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
);
1999 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
2000 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
2006 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2007 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
2009 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
2014 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2015 return chrec_convert (chrec_type (chrec
), op
, NULL
);
2020 /* Handle ~X as -1 - X. */
2021 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
2022 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
2023 build_int_cst (TREE_TYPE (chrec
), -1), op
);
2035 #define FLOOR_DIV(x,y) ((x) / (y))
2037 /* Solves the special case of the Diophantine equation:
2038 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2040 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2041 number of iterations that loops X and Y run. The overlaps will be
2042 constructed as evolutions in dimension DIM. */
2045 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
2046 affine_fn
*overlaps_a
,
2047 affine_fn
*overlaps_b
,
2048 tree
*last_conflicts
, int dim
)
2050 if (((step_a
> 0 && step_b
> 0)
2051 || (step_a
< 0 && step_b
< 0)))
2053 int step_overlaps_a
, step_overlaps_b
;
2054 int gcd_steps_a_b
, last_conflict
, tau2
;
2056 gcd_steps_a_b
= gcd (step_a
, step_b
);
2057 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2058 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2062 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2063 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2064 last_conflict
= tau2
;
2065 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2068 *last_conflicts
= chrec_dont_know
;
2070 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
2071 build_int_cst (NULL_TREE
,
2073 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
2074 build_int_cst (NULL_TREE
,
2080 *overlaps_a
= affine_fn_cst (integer_zero_node
);
2081 *overlaps_b
= affine_fn_cst (integer_zero_node
);
2082 *last_conflicts
= integer_zero_node
;
2086 /* Solves the special case of a Diophantine equation where CHREC_A is
2087 an affine bivariate function, and CHREC_B is an affine univariate
2088 function. For example,
2090 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2092 has the following overlapping functions:
2094 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2095 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2096 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2098 FORNOW: This is a specialized implementation for a case occurring in
2099 a common benchmark. Implement the general algorithm. */
2102 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2103 conflict_function
**overlaps_a
,
2104 conflict_function
**overlaps_b
,
2105 tree
*last_conflicts
)
2107 bool xz_p
, yz_p
, xyz_p
;
2108 int step_x
, step_y
, step_z
;
2109 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
2110 affine_fn overlaps_a_xz
, overlaps_b_xz
;
2111 affine_fn overlaps_a_yz
, overlaps_b_yz
;
2112 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
2113 affine_fn ova1
, ova2
, ovb
;
2114 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
2116 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2117 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2118 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2120 niter_x
= max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a
)));
2121 niter_y
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
2122 niter_z
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
2124 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2127 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2129 *overlaps_a
= conflict_fn_not_known ();
2130 *overlaps_b
= conflict_fn_not_known ();
2131 *last_conflicts
= chrec_dont_know
;
2135 niter
= MIN (niter_x
, niter_z
);
2136 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2139 &last_conflicts_xz
, 1);
2140 niter
= MIN (niter_y
, niter_z
);
2141 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2144 &last_conflicts_yz
, 2);
2145 niter
= MIN (niter_x
, niter_z
);
2146 niter
= MIN (niter_y
, niter
);
2147 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2150 &last_conflicts_xyz
, 3);
2152 xz_p
= !integer_zerop (last_conflicts_xz
);
2153 yz_p
= !integer_zerop (last_conflicts_yz
);
2154 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2156 if (xz_p
|| yz_p
|| xyz_p
)
2158 ova1
= affine_fn_cst (integer_zero_node
);
2159 ova2
= affine_fn_cst (integer_zero_node
);
2160 ovb
= affine_fn_cst (integer_zero_node
);
2163 affine_fn t0
= ova1
;
2166 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2167 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2168 affine_fn_free (t0
);
2169 affine_fn_free (t2
);
2170 *last_conflicts
= last_conflicts_xz
;
2174 affine_fn t0
= ova2
;
2177 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2178 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2179 affine_fn_free (t0
);
2180 affine_fn_free (t2
);
2181 *last_conflicts
= last_conflicts_yz
;
2185 affine_fn t0
= ova1
;
2186 affine_fn t2
= ova2
;
2189 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2190 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2191 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2192 affine_fn_free (t0
);
2193 affine_fn_free (t2
);
2194 affine_fn_free (t4
);
2195 *last_conflicts
= last_conflicts_xyz
;
2197 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2198 *overlaps_b
= conflict_fn (1, ovb
);
2202 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2203 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2204 *last_conflicts
= integer_zero_node
;
2207 affine_fn_free (overlaps_a_xz
);
2208 affine_fn_free (overlaps_b_xz
);
2209 affine_fn_free (overlaps_a_yz
);
2210 affine_fn_free (overlaps_b_yz
);
2211 affine_fn_free (overlaps_a_xyz
);
2212 affine_fn_free (overlaps_b_xyz
);
2215 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2218 lambda_vector_copy (lambda_vector vec1
, lambda_vector vec2
,
2221 memcpy (vec2
, vec1
, size
* sizeof (*vec1
));
2224 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2227 lambda_matrix_copy (lambda_matrix mat1
, lambda_matrix mat2
,
2232 for (i
= 0; i
< m
; i
++)
2233 lambda_vector_copy (mat1
[i
], mat2
[i
], n
);
2236 /* Store the N x N identity matrix in MAT. */
2239 lambda_matrix_id (lambda_matrix mat
, int size
)
2243 for (i
= 0; i
< size
; i
++)
2244 for (j
= 0; j
< size
; j
++)
2245 mat
[i
][j
] = (i
== j
) ? 1 : 0;
2248 /* Return the first nonzero element of vector VEC1 between START and N.
2249 We must have START <= N. Returns N if VEC1 is the zero vector. */
2252 lambda_vector_first_nz (lambda_vector vec1
, int n
, int start
)
2255 while (j
< n
&& vec1
[j
] == 0)
2260 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2261 R2 = R2 + CONST1 * R1. */
2264 lambda_matrix_row_add (lambda_matrix mat
, int n
, int r1
, int r2
, int const1
)
2271 for (i
= 0; i
< n
; i
++)
2272 mat
[r2
][i
] += const1
* mat
[r1
][i
];
2275 /* Swap rows R1 and R2 in matrix MAT. */
2278 lambda_matrix_row_exchange (lambda_matrix mat
, int r1
, int r2
)
2287 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2288 and store the result in VEC2. */
2291 lambda_vector_mult_const (lambda_vector vec1
, lambda_vector vec2
,
2292 int size
, int const1
)
2297 lambda_vector_clear (vec2
, size
);
2299 for (i
= 0; i
< size
; i
++)
2300 vec2
[i
] = const1
* vec1
[i
];
2303 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2306 lambda_vector_negate (lambda_vector vec1
, lambda_vector vec2
,
2309 lambda_vector_mult_const (vec1
, vec2
, size
, -1);
2312 /* Negate row R1 of matrix MAT which has N columns. */
2315 lambda_matrix_row_negate (lambda_matrix mat
, int n
, int r1
)
2317 lambda_vector_negate (mat
[r1
], mat
[r1
], n
);
2320 /* Return true if two vectors are equal. */
2323 lambda_vector_equal (lambda_vector vec1
, lambda_vector vec2
, int size
)
2326 for (i
= 0; i
< size
; i
++)
2327 if (vec1
[i
] != vec2
[i
])
2332 /* Given an M x N integer matrix A, this function determines an M x
2333 M unimodular matrix U, and an M x N echelon matrix S such that
2334 "U.A = S". This decomposition is also known as "right Hermite".
2336 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2337 Restructuring Compilers" Utpal Banerjee. */
2340 lambda_matrix_right_hermite (lambda_matrix A
, int m
, int n
,
2341 lambda_matrix S
, lambda_matrix U
)
2345 lambda_matrix_copy (A
, S
, m
, n
);
2346 lambda_matrix_id (U
, m
);
2348 for (j
= 0; j
< n
; j
++)
2350 if (lambda_vector_first_nz (S
[j
], m
, i0
) < m
)
2353 for (i
= m
- 1; i
>= i0
; i
--)
2355 while (S
[i
][j
] != 0)
2357 int sigma
, factor
, a
, b
;
2361 sigma
= (a
* b
< 0) ? -1: 1;
2364 factor
= sigma
* (a
/ b
);
2366 lambda_matrix_row_add (S
, n
, i
, i
-1, -factor
);
2367 lambda_matrix_row_exchange (S
, i
, i
-1);
2369 lambda_matrix_row_add (U
, m
, i
, i
-1, -factor
);
2370 lambda_matrix_row_exchange (U
, i
, i
-1);
2377 /* Determines the overlapping elements due to accesses CHREC_A and
2378 CHREC_B, that are affine functions. This function cannot handle
2379 symbolic evolution functions, ie. when initial conditions are
2380 parameters, because it uses lambda matrices of integers. */
2383 analyze_subscript_affine_affine (tree chrec_a
,
2385 conflict_function
**overlaps_a
,
2386 conflict_function
**overlaps_b
,
2387 tree
*last_conflicts
)
2389 unsigned nb_vars_a
, nb_vars_b
, dim
;
2390 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
2391 lambda_matrix A
, U
, S
;
2392 struct obstack scratch_obstack
;
2394 if (eq_evolutions_p (chrec_a
, chrec_b
))
2396 /* The accessed index overlaps for each iteration in the
2398 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2399 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2400 *last_conflicts
= chrec_dont_know
;
2403 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2404 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2406 /* For determining the initial intersection, we have to solve a
2407 Diophantine equation. This is the most time consuming part.
2409 For answering to the question: "Is there a dependence?" we have
2410 to prove that there exists a solution to the Diophantine
2411 equation, and that the solution is in the iteration domain,
2412 i.e. the solution is positive or zero, and that the solution
2413 happens before the upper bound loop.nb_iterations. Otherwise
2414 there is no dependence. This function outputs a description of
2415 the iterations that hold the intersections. */
2417 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2418 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2420 gcc_obstack_init (&scratch_obstack
);
2422 dim
= nb_vars_a
+ nb_vars_b
;
2423 U
= lambda_matrix_new (dim
, dim
, &scratch_obstack
);
2424 A
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2425 S
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
2427 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
2428 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
2429 gamma
= init_b
- init_a
;
2431 /* Don't do all the hard work of solving the Diophantine equation
2432 when we already know the solution: for example,
2435 | gamma = 3 - 3 = 0.
2436 Then the first overlap occurs during the first iterations:
2437 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2441 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2443 HOST_WIDE_INT step_a
, step_b
;
2444 HOST_WIDE_INT niter
, niter_a
, niter_b
;
2447 niter_a
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
2448 niter_b
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
2449 niter
= MIN (niter_a
, niter_b
);
2450 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2451 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2453 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2456 *overlaps_a
= conflict_fn (1, ova
);
2457 *overlaps_b
= conflict_fn (1, ovb
);
2460 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2461 compute_overlap_steps_for_affine_1_2
2462 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2464 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2465 compute_overlap_steps_for_affine_1_2
2466 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2471 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2472 *overlaps_a
= conflict_fn_not_known ();
2473 *overlaps_b
= conflict_fn_not_known ();
2474 *last_conflicts
= chrec_dont_know
;
2476 goto end_analyze_subs_aa
;
2480 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2485 lambda_matrix_row_negate (U
, dim
, 0);
2487 gcd_alpha_beta
= S
[0][0];
2489 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2490 but that is a quite strange case. Instead of ICEing, answer
2492 if (gcd_alpha_beta
== 0)
2494 *overlaps_a
= conflict_fn_not_known ();
2495 *overlaps_b
= conflict_fn_not_known ();
2496 *last_conflicts
= chrec_dont_know
;
2497 goto end_analyze_subs_aa
;
2500 /* The classic "gcd-test". */
2501 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2503 /* The "gcd-test" has determined that there is no integer
2504 solution, i.e. there is no dependence. */
2505 *overlaps_a
= conflict_fn_no_dependence ();
2506 *overlaps_b
= conflict_fn_no_dependence ();
2507 *last_conflicts
= integer_zero_node
;
2510 /* Both access functions are univariate. This includes SIV and MIV cases. */
2511 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2513 /* Both functions should have the same evolution sign. */
2514 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2515 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2517 /* The solutions are given by:
2519 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2522 For a given integer t. Using the following variables,
2524 | i0 = u11 * gamma / gcd_alpha_beta
2525 | j0 = u12 * gamma / gcd_alpha_beta
2532 | y0 = j0 + j1 * t. */
2533 HOST_WIDE_INT i0
, j0
, i1
, j1
;
2535 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2536 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2540 if ((i1
== 0 && i0
< 0)
2541 || (j1
== 0 && j0
< 0))
2543 /* There is no solution.
2544 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2545 falls in here, but for the moment we don't look at the
2546 upper bound of the iteration domain. */
2547 *overlaps_a
= conflict_fn_no_dependence ();
2548 *overlaps_b
= conflict_fn_no_dependence ();
2549 *last_conflicts
= integer_zero_node
;
2550 goto end_analyze_subs_aa
;
2553 if (i1
> 0 && j1
> 0)
2555 HOST_WIDE_INT niter_a
2556 = max_stmt_executions_int (get_chrec_loop (chrec_a
));
2557 HOST_WIDE_INT niter_b
2558 = max_stmt_executions_int (get_chrec_loop (chrec_b
));
2559 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
2561 /* (X0, Y0) is a solution of the Diophantine equation:
2562 "chrec_a (X0) = chrec_b (Y0)". */
2563 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
2565 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
2566 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
2568 /* (X1, Y1) is the smallest positive solution of the eq
2569 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2570 first conflict occurs. */
2571 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2572 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
2573 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
2577 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter
- i0
, i1
),
2578 FLOOR_DIV (niter
- j0
, j1
));
2579 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
2581 /* If the overlap occurs outside of the bounds of the
2582 loop, there is no dependence. */
2583 if (x1
>= niter
|| y1
>= niter
)
2585 *overlaps_a
= conflict_fn_no_dependence ();
2586 *overlaps_b
= conflict_fn_no_dependence ();
2587 *last_conflicts
= integer_zero_node
;
2588 goto end_analyze_subs_aa
;
2591 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2594 *last_conflicts
= chrec_dont_know
;
2598 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
2600 build_int_cst (NULL_TREE
, i1
)));
2603 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
2605 build_int_cst (NULL_TREE
, j1
)));
2609 /* FIXME: For the moment, the upper bound of the
2610 iteration domain for i and j is not checked. */
2611 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2612 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2613 *overlaps_a
= conflict_fn_not_known ();
2614 *overlaps_b
= conflict_fn_not_known ();
2615 *last_conflicts
= chrec_dont_know
;
2620 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2621 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2622 *overlaps_a
= conflict_fn_not_known ();
2623 *overlaps_b
= conflict_fn_not_known ();
2624 *last_conflicts
= chrec_dont_know
;
2629 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2630 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2631 *overlaps_a
= conflict_fn_not_known ();
2632 *overlaps_b
= conflict_fn_not_known ();
2633 *last_conflicts
= chrec_dont_know
;
2636 end_analyze_subs_aa
:
2637 obstack_free (&scratch_obstack
, NULL
);
2638 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2640 fprintf (dump_file
, " (overlaps_a = ");
2641 dump_conflict_function (dump_file
, *overlaps_a
);
2642 fprintf (dump_file
, ")\n (overlaps_b = ");
2643 dump_conflict_function (dump_file
, *overlaps_b
);
2644 fprintf (dump_file
, "))\n");
2648 /* Returns true when analyze_subscript_affine_affine can be used for
2649 determining the dependence relation between chrec_a and chrec_b,
2650 that contain symbols. This function modifies chrec_a and chrec_b
2651 such that the analysis result is the same, and such that they don't
2652 contain symbols, and then can safely be passed to the analyzer.
2654 Example: The analysis of the following tuples of evolutions produce
2655 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2658 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2659 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2663 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
2665 tree diff
, type
, left_a
, left_b
, right_b
;
2667 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
2668 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
2669 /* FIXME: For the moment not handled. Might be refined later. */
2672 type
= chrec_type (*chrec_a
);
2673 left_a
= CHREC_LEFT (*chrec_a
);
2674 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
2675 diff
= chrec_fold_minus (type
, left_a
, left_b
);
2677 if (!evolution_function_is_constant_p (diff
))
2680 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2681 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
2683 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
2684 diff
, CHREC_RIGHT (*chrec_a
));
2685 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
2686 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
2687 build_int_cst (type
, 0),
2692 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2693 *OVERLAPS_B are initialized to the functions that describe the
2694 relation between the elements accessed twice by CHREC_A and
2695 CHREC_B. For k >= 0, the following property is verified:
2697 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2700 analyze_siv_subscript (tree chrec_a
,
2702 conflict_function
**overlaps_a
,
2703 conflict_function
**overlaps_b
,
2704 tree
*last_conflicts
,
2707 dependence_stats
.num_siv
++;
2709 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2710 fprintf (dump_file
, "(analyze_siv_subscript \n");
2712 if (evolution_function_is_constant_p (chrec_a
)
2713 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2714 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
2715 overlaps_a
, overlaps_b
, last_conflicts
);
2717 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2718 && evolution_function_is_constant_p (chrec_b
))
2719 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
2720 overlaps_b
, overlaps_a
, last_conflicts
);
2722 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
2723 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
2725 if (!chrec_contains_symbols (chrec_a
)
2726 && !chrec_contains_symbols (chrec_b
))
2728 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2729 overlaps_a
, overlaps_b
,
2732 if (CF_NOT_KNOWN_P (*overlaps_a
)
2733 || CF_NOT_KNOWN_P (*overlaps_b
))
2734 dependence_stats
.num_siv_unimplemented
++;
2735 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2736 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2737 dependence_stats
.num_siv_independent
++;
2739 dependence_stats
.num_siv_dependent
++;
2741 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
2744 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2745 overlaps_a
, overlaps_b
,
2748 if (CF_NOT_KNOWN_P (*overlaps_a
)
2749 || CF_NOT_KNOWN_P (*overlaps_b
))
2750 dependence_stats
.num_siv_unimplemented
++;
2751 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2752 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2753 dependence_stats
.num_siv_independent
++;
2755 dependence_stats
.num_siv_dependent
++;
2758 goto siv_subscript_dontknow
;
2763 siv_subscript_dontknow
:;
2764 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2765 fprintf (dump_file
, " siv test failed: unimplemented");
2766 *overlaps_a
= conflict_fn_not_known ();
2767 *overlaps_b
= conflict_fn_not_known ();
2768 *last_conflicts
= chrec_dont_know
;
2769 dependence_stats
.num_siv_unimplemented
++;
2772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2773 fprintf (dump_file
, ")\n");
2776 /* Returns false if we can prove that the greatest common divisor of the steps
2777 of CHREC does not divide CST, false otherwise. */
2780 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
2782 HOST_WIDE_INT cd
= 0, val
;
2785 if (!host_integerp (cst
, 0))
2787 val
= tree_low_cst (cst
, 0);
2789 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
2791 step
= CHREC_RIGHT (chrec
);
2792 if (!host_integerp (step
, 0))
2794 cd
= gcd (cd
, tree_low_cst (step
, 0));
2795 chrec
= CHREC_LEFT (chrec
);
2798 return val
% cd
== 0;
2801 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2802 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2803 functions that describe the relation between the elements accessed
2804 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2807 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2810 analyze_miv_subscript (tree chrec_a
,
2812 conflict_function
**overlaps_a
,
2813 conflict_function
**overlaps_b
,
2814 tree
*last_conflicts
,
2815 struct loop
*loop_nest
)
2817 tree type
, difference
;
2819 dependence_stats
.num_miv
++;
2820 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2821 fprintf (dump_file
, "(analyze_miv_subscript \n");
2823 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2824 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2825 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2826 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2828 if (eq_evolutions_p (chrec_a
, chrec_b
))
2830 /* Access functions are the same: all the elements are accessed
2831 in the same order. */
2832 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2833 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2834 *last_conflicts
= max_stmt_executions_tree (get_chrec_loop (chrec_a
));
2835 dependence_stats
.num_miv_dependent
++;
2838 else if (evolution_function_is_constant_p (difference
)
2839 /* For the moment, the following is verified:
2840 evolution_function_is_affine_multivariate_p (chrec_a,
2842 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
2844 /* testsuite/.../ssa-chrec-33.c
2845 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2847 The difference is 1, and all the evolution steps are multiples
2848 of 2, consequently there are no overlapping elements. */
2849 *overlaps_a
= conflict_fn_no_dependence ();
2850 *overlaps_b
= conflict_fn_no_dependence ();
2851 *last_conflicts
= integer_zero_node
;
2852 dependence_stats
.num_miv_independent
++;
2855 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
2856 && !chrec_contains_symbols (chrec_a
)
2857 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
2858 && !chrec_contains_symbols (chrec_b
))
2860 /* testsuite/.../ssa-chrec-35.c
2861 {0, +, 1}_2 vs. {0, +, 1}_3
2862 the overlapping elements are respectively located at iterations:
2863 {0, +, 1}_x and {0, +, 1}_x,
2864 in other words, we have the equality:
2865 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2868 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2869 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2871 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2872 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2874 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
2875 overlaps_a
, overlaps_b
, last_conflicts
);
2877 if (CF_NOT_KNOWN_P (*overlaps_a
)
2878 || CF_NOT_KNOWN_P (*overlaps_b
))
2879 dependence_stats
.num_miv_unimplemented
++;
2880 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
2881 || CF_NO_DEPENDENCE_P (*overlaps_b
))
2882 dependence_stats
.num_miv_independent
++;
2884 dependence_stats
.num_miv_dependent
++;
2889 /* When the analysis is too difficult, answer "don't know". */
2890 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2891 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
2893 *overlaps_a
= conflict_fn_not_known ();
2894 *overlaps_b
= conflict_fn_not_known ();
2895 *last_conflicts
= chrec_dont_know
;
2896 dependence_stats
.num_miv_unimplemented
++;
2899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2900 fprintf (dump_file
, ")\n");
2903 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2904 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2905 OVERLAP_ITERATIONS_B are initialized with two functions that
2906 describe the iterations that contain conflicting elements.
2908 Remark: For an integer k >= 0, the following equality is true:
2910 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2914 analyze_overlapping_iterations (tree chrec_a
,
2916 conflict_function
**overlap_iterations_a
,
2917 conflict_function
**overlap_iterations_b
,
2918 tree
*last_conflicts
, struct loop
*loop_nest
)
2920 unsigned int lnn
= loop_nest
->num
;
2922 dependence_stats
.num_subscript_tests
++;
2924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2926 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
2927 fprintf (dump_file
, " (chrec_a = ");
2928 print_generic_expr (dump_file
, chrec_a
, 0);
2929 fprintf (dump_file
, ")\n (chrec_b = ");
2930 print_generic_expr (dump_file
, chrec_b
, 0);
2931 fprintf (dump_file
, ")\n");
2934 if (chrec_a
== NULL_TREE
2935 || chrec_b
== NULL_TREE
2936 || chrec_contains_undetermined (chrec_a
)
2937 || chrec_contains_undetermined (chrec_b
))
2939 dependence_stats
.num_subscript_undetermined
++;
2941 *overlap_iterations_a
= conflict_fn_not_known ();
2942 *overlap_iterations_b
= conflict_fn_not_known ();
2945 /* If they are the same chrec, and are affine, they overlap
2946 on every iteration. */
2947 else if (eq_evolutions_p (chrec_a
, chrec_b
)
2948 && (evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2949 || operand_equal_p (chrec_a
, chrec_b
, 0)))
2951 dependence_stats
.num_same_subscript_function
++;
2952 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2953 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2954 *last_conflicts
= chrec_dont_know
;
2957 /* If they aren't the same, and aren't affine, we can't do anything
2959 else if ((chrec_contains_symbols (chrec_a
)
2960 || chrec_contains_symbols (chrec_b
))
2961 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
2962 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
2964 dependence_stats
.num_subscript_undetermined
++;
2965 *overlap_iterations_a
= conflict_fn_not_known ();
2966 *overlap_iterations_b
= conflict_fn_not_known ();
2969 else if (ziv_subscript_p (chrec_a
, chrec_b
))
2970 analyze_ziv_subscript (chrec_a
, chrec_b
,
2971 overlap_iterations_a
, overlap_iterations_b
,
2974 else if (siv_subscript_p (chrec_a
, chrec_b
))
2975 analyze_siv_subscript (chrec_a
, chrec_b
,
2976 overlap_iterations_a
, overlap_iterations_b
,
2977 last_conflicts
, lnn
);
2980 analyze_miv_subscript (chrec_a
, chrec_b
,
2981 overlap_iterations_a
, overlap_iterations_b
,
2982 last_conflicts
, loop_nest
);
2984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2986 fprintf (dump_file
, " (overlap_iterations_a = ");
2987 dump_conflict_function (dump_file
, *overlap_iterations_a
);
2988 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
2989 dump_conflict_function (dump_file
, *overlap_iterations_b
);
2990 fprintf (dump_file
, "))\n");
2994 /* Helper function for uniquely inserting distance vectors. */
2997 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
3002 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, v
)
3003 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
3006 DDR_DIST_VECTS (ddr
).safe_push (dist_v
);
3009 /* Helper function for uniquely inserting direction vectors. */
3012 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
3017 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), i
, v
)
3018 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
3021 DDR_DIR_VECTS (ddr
).safe_push (dir_v
);
3024 /* Add a distance of 1 on all the loops outer than INDEX. If we
3025 haven't yet determined a distance for this outer loop, push a new
3026 distance vector composed of the previous distance, and a distance
3027 of 1 for this outer loop. Example:
3035 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3036 save (0, 1), then we have to save (1, 0). */
3039 add_outer_distances (struct data_dependence_relation
*ddr
,
3040 lambda_vector dist_v
, int index
)
3042 /* For each outer loop where init_v is not set, the accesses are
3043 in dependence of distance 1 in the loop. */
3044 while (--index
>= 0)
3046 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3047 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3049 save_dist_v (ddr
, save_v
);
3053 /* Return false when fail to represent the data dependence as a
3054 distance vector. INIT_B is set to true when a component has been
3055 added to the distance vector DIST_V. INDEX_CARRY is then set to
3056 the index in DIST_V that carries the dependence. */
3059 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
3060 struct data_reference
*ddr_a
,
3061 struct data_reference
*ddr_b
,
3062 lambda_vector dist_v
, bool *init_b
,
3066 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3068 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3070 tree access_fn_a
, access_fn_b
;
3071 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
3073 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3075 non_affine_dependence_relation (ddr
);
3079 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
3080 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
3082 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
3083 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
3086 int var_a
= CHREC_VARIABLE (access_fn_a
);
3087 int var_b
= CHREC_VARIABLE (access_fn_b
);
3090 || chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3092 non_affine_dependence_relation (ddr
);
3096 dist
= int_cst_value (SUB_DISTANCE (subscript
));
3097 index
= index_in_loop_nest (var_a
, DDR_LOOP_NEST (ddr
));
3098 *index_carry
= MIN (index
, *index_carry
);
3100 /* This is the subscript coupling test. If we have already
3101 recorded a distance for this loop (a distance coming from
3102 another subscript), it should be the same. For example,
3103 in the following code, there is no dependence:
3110 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
3112 finalize_ddr_dependent (ddr
, chrec_known
);
3116 dist_v
[index
] = dist
;
3120 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
3122 /* This can be for example an affine vs. constant dependence
3123 (T[i] vs. T[3]) that is not an affine dependence and is
3124 not representable as a distance vector. */
3125 non_affine_dependence_relation (ddr
);
3133 /* Return true when the DDR contains only constant access functions. */
3136 constant_access_functions (const struct data_dependence_relation
*ddr
)
3140 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3141 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr
), i
))
3142 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr
), i
)))
3148 /* Helper function for the case where DDR_A and DDR_B are the same
3149 multivariate access function with a constant step. For an example
3153 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
3156 tree c_1
= CHREC_LEFT (c_2
);
3157 tree c_0
= CHREC_LEFT (c_1
);
3158 lambda_vector dist_v
;
3161 /* Polynomials with more than 2 variables are not handled yet. When
3162 the evolution steps are parameters, it is not possible to
3163 represent the dependence using classical distance vectors. */
3164 if (TREE_CODE (c_0
) != INTEGER_CST
3165 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
3166 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
3168 DDR_AFFINE_P (ddr
) = false;
3172 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
3173 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
3175 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3176 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3177 v1
= int_cst_value (CHREC_RIGHT (c_1
));
3178 v2
= int_cst_value (CHREC_RIGHT (c_2
));
3191 save_dist_v (ddr
, dist_v
);
3193 add_outer_distances (ddr
, dist_v
, x_1
);
3196 /* Helper function for the case where DDR_A and DDR_B are the same
3197 access functions. */
3200 add_other_self_distances (struct data_dependence_relation
*ddr
)
3202 lambda_vector dist_v
;
3204 int index_carry
= DDR_NB_LOOPS (ddr
);
3206 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3208 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3210 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3212 if (!evolution_function_is_univariate_p (access_fun
))
3214 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3216 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3220 access_fun
= DR_ACCESS_FN (DDR_A (ddr
), 0);
3222 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
3223 add_multivariate_self_dist (ddr
, access_fun
);
3225 /* The evolution step is not constant: it varies in
3226 the outer loop, so this cannot be represented by a
3227 distance vector. For example in pr34635.c the
3228 evolution is {0, +, {0, +, 4}_1}_2. */
3229 DDR_AFFINE_P (ddr
) = false;
3234 index_carry
= MIN (index_carry
,
3235 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3236 DDR_LOOP_NEST (ddr
)));
3240 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3241 add_outer_distances (ddr
, dist_v
, index_carry
);
3245 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
3247 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3249 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
3250 save_dist_v (ddr
, dist_v
);
3253 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3254 is the case for example when access functions are the same and
3255 equal to a constant, as in:
3262 in which case the distance vectors are (0) and (1). */
3265 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
3269 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3271 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
3272 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
3273 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
3275 for (j
= 0; j
< ca
->n
; j
++)
3276 if (affine_function_zero_p (ca
->fns
[j
]))
3278 insert_innermost_unit_dist_vector (ddr
);
3282 for (j
= 0; j
< cb
->n
; j
++)
3283 if (affine_function_zero_p (cb
->fns
[j
]))
3285 insert_innermost_unit_dist_vector (ddr
);
3291 /* Compute the classic per loop distance vector. DDR is the data
3292 dependence relation to build a vector from. Return false when fail
3293 to represent the data dependence as a distance vector. */
3296 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
3297 struct loop
*loop_nest
)
3299 bool init_b
= false;
3300 int index_carry
= DDR_NB_LOOPS (ddr
);
3301 lambda_vector dist_v
;
3303 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3306 if (same_access_functions (ddr
))
3308 /* Save the 0 vector. */
3309 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3310 save_dist_v (ddr
, dist_v
);
3312 if (constant_access_functions (ddr
))
3313 add_distance_for_zero_overlaps (ddr
);
3315 if (DDR_NB_LOOPS (ddr
) > 1)
3316 add_other_self_distances (ddr
);
3321 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3322 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3323 dist_v
, &init_b
, &index_carry
))
3326 /* Save the distance vector if we initialized one. */
3329 /* Verify a basic constraint: classic distance vectors should
3330 always be lexicographically positive.
3332 Data references are collected in the order of execution of
3333 the program, thus for the following loop
3335 | for (i = 1; i < 100; i++)
3336 | for (j = 1; j < 100; j++)
3338 | t = T[j+1][i-1]; // A
3339 | T[j][i] = t + 2; // B
3342 references are collected following the direction of the wind:
3343 A then B. The data dependence tests are performed also
3344 following this order, such that we're looking at the distance
3345 separating the elements accessed by A from the elements later
3346 accessed by B. But in this example, the distance returned by
3347 test_dep (A, B) is lexicographically negative (-1, 1), that
3348 means that the access A occurs later than B with respect to
3349 the outer loop, ie. we're actually looking upwind. In this
3350 case we solve test_dep (B, A) looking downwind to the
3351 lexicographically positive solution, that returns the
3352 distance vector (1, -1). */
3353 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3355 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3356 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3359 compute_subscript_distance (ddr
);
3360 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3361 save_v
, &init_b
, &index_carry
))
3363 save_dist_v (ddr
, save_v
);
3364 DDR_REVERSED_P (ddr
) = true;
3366 /* In this case there is a dependence forward for all the
3369 | for (k = 1; k < 100; k++)
3370 | for (i = 1; i < 100; i++)
3371 | for (j = 1; j < 100; j++)
3373 | t = T[j+1][i-1]; // A
3374 | T[j][i] = t + 2; // B
3382 if (DDR_NB_LOOPS (ddr
) > 1)
3384 add_outer_distances (ddr
, save_v
, index_carry
);
3385 add_outer_distances (ddr
, dist_v
, index_carry
);
3390 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3391 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3393 if (DDR_NB_LOOPS (ddr
) > 1)
3395 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3397 if (!subscript_dependence_tester_1 (ddr
, DDR_B (ddr
),
3398 DDR_A (ddr
), loop_nest
))
3400 compute_subscript_distance (ddr
);
3401 if (!build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3402 opposite_v
, &init_b
,
3406 save_dist_v (ddr
, save_v
);
3407 add_outer_distances (ddr
, dist_v
, index_carry
);
3408 add_outer_distances (ddr
, opposite_v
, index_carry
);
3411 save_dist_v (ddr
, save_v
);
3416 /* There is a distance of 1 on all the outer loops: Example:
3417 there is a dependence of distance 1 on loop_1 for the array A.
3423 add_outer_distances (ddr
, dist_v
,
3424 lambda_vector_first_nz (dist_v
,
3425 DDR_NB_LOOPS (ddr
), 0));
3428 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3432 fprintf (dump_file
, "(build_classic_dist_vector\n");
3433 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3435 fprintf (dump_file
, " dist_vector = (");
3436 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3437 DDR_NB_LOOPS (ddr
));
3438 fprintf (dump_file
, " )\n");
3440 fprintf (dump_file
, ")\n");
3446 /* Return the direction for a given distance.
3447 FIXME: Computing dir this way is suboptimal, since dir can catch
3448 cases that dist is unable to represent. */
3450 static inline enum data_dependence_direction
3451 dir_from_dist (int dist
)
3454 return dir_positive
;
3456 return dir_negative
;
3461 /* Compute the classic per loop direction vector. DDR is the data
3462 dependence relation to build a vector from. */
3465 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3468 lambda_vector dist_v
;
3470 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
3472 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3474 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3475 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3477 save_dir_v (ddr
, dir_v
);
3481 /* Helper function. Returns true when there is a dependence between
3482 data references DRA and DRB. */
3485 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3486 struct data_reference
*dra
,
3487 struct data_reference
*drb
,
3488 struct loop
*loop_nest
)
3491 tree last_conflicts
;
3492 struct subscript
*subscript
;
3493 tree res
= NULL_TREE
;
3495 for (i
= 0; DDR_SUBSCRIPTS (ddr
).iterate (i
, &subscript
); i
++)
3497 conflict_function
*overlaps_a
, *overlaps_b
;
3499 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3500 DR_ACCESS_FN (drb
, i
),
3501 &overlaps_a
, &overlaps_b
,
3502 &last_conflicts
, loop_nest
);
3504 if (SUB_CONFLICTS_IN_A (subscript
))
3505 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
3506 if (SUB_CONFLICTS_IN_B (subscript
))
3507 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
3509 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3510 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3511 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3513 /* If there is any undetermined conflict function we have to
3514 give a conservative answer in case we cannot prove that
3515 no dependence exists when analyzing another subscript. */
3516 if (CF_NOT_KNOWN_P (overlaps_a
)
3517 || CF_NOT_KNOWN_P (overlaps_b
))
3519 res
= chrec_dont_know
;
3523 /* When there is a subscript with no dependence we can stop. */
3524 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
3525 || CF_NO_DEPENDENCE_P (overlaps_b
))
3532 if (res
== NULL_TREE
)
3535 if (res
== chrec_known
)
3536 dependence_stats
.num_dependence_independent
++;
3538 dependence_stats
.num_dependence_undetermined
++;
3539 finalize_ddr_dependent (ddr
, res
);
3543 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3546 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
3547 struct loop
*loop_nest
)
3549 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
), loop_nest
))
3550 dependence_stats
.num_dependence_dependent
++;
3552 compute_subscript_distance (ddr
);
3553 if (build_classic_dist_vector (ddr
, loop_nest
))
3554 build_classic_dir_vector (ddr
);
3557 /* Returns true when all the access functions of A are affine or
3558 constant with respect to LOOP_NEST. */
3561 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
3562 const struct loop
*loop_nest
)
3565 vec
<tree
> fns
= DR_ACCESS_FNS (a
);
3568 FOR_EACH_VEC_ELT (fns
, i
, t
)
3569 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
3570 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
3576 /* Initializes an equation for an OMEGA problem using the information
3577 contained in the ACCESS_FUN. Returns true when the operation
3580 PB is the omega constraint system.
3581 EQ is the number of the equation to be initialized.
3582 OFFSET is used for shifting the variables names in the constraints:
3583 a constrain is composed of 2 * the number of variables surrounding
3584 dependence accesses. OFFSET is set either to 0 for the first n variables,
3585 then it is set to n.
3586 ACCESS_FUN is expected to be an affine chrec. */
3589 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
3590 unsigned int offset
, tree access_fun
,
3591 struct data_dependence_relation
*ddr
)
3593 switch (TREE_CODE (access_fun
))
3595 case POLYNOMIAL_CHREC
:
3597 tree left
= CHREC_LEFT (access_fun
);
3598 tree right
= CHREC_RIGHT (access_fun
);
3599 int var
= CHREC_VARIABLE (access_fun
);
3602 if (TREE_CODE (right
) != INTEGER_CST
)
3605 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
3606 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
3608 /* Compute the innermost loop index. */
3609 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
3612 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
3613 += int_cst_value (right
);
3615 switch (TREE_CODE (left
))
3617 case POLYNOMIAL_CHREC
:
3618 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
3621 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
3630 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
3638 /* As explained in the comments preceding init_omega_for_ddr, we have
3639 to set up a system for each loop level, setting outer loops
3640 variation to zero, and current loop variation to positive or zero.
3641 Save each lexico positive distance vector. */
3644 omega_extract_distance_vectors (omega_pb pb
,
3645 struct data_dependence_relation
*ddr
)
3649 struct loop
*loopi
, *loopj
;
3650 enum omega_result res
;
3652 /* Set a new problem for each loop in the nest. The basis is the
3653 problem that we have initialized until now. On top of this we
3654 add new constraints. */
3655 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3656 && DDR_LOOP_NEST (ddr
).iterate (i
, &loopi
); i
++)
3659 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
3660 DDR_NB_LOOPS (ddr
));
3662 omega_copy_problem (copy
, pb
);
3664 /* For all the outer loops "loop_j", add "dj = 0". */
3665 for (j
= 0; j
< i
&& DDR_LOOP_NEST (ddr
).iterate (j
, &loopj
); j
++)
3667 eq
= omega_add_zero_eq (copy
, omega_black
);
3668 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3671 /* For "loop_i", add "0 <= di". */
3672 geq
= omega_add_zero_geq (copy
, omega_black
);
3673 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
3675 /* Reduce the constraint system, and test that the current
3676 problem is feasible. */
3677 res
= omega_simplify_problem (copy
);
3678 if (res
== omega_false
3679 || res
== omega_unknown
3680 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3683 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3684 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3686 dist
= copy
->subs
[eq
].coef
[0];
3692 /* Reinitialize problem... */
3693 omega_copy_problem (copy
, pb
);
3694 for (j
= 0; j
< i
&& DDR_LOOP_NEST (ddr
).iterate (j
, &loopj
); j
++)
3696 eq
= omega_add_zero_eq (copy
, omega_black
);
3697 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
3700 /* ..., but this time "di = 1". */
3701 eq
= omega_add_zero_eq (copy
, omega_black
);
3702 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
3703 copy
->eqs
[eq
].coef
[0] = -1;
3705 res
= omega_simplify_problem (copy
);
3706 if (res
== omega_false
3707 || res
== omega_unknown
3708 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
3711 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3712 if (copy
->subs
[eq
].key
== (int) i
+ 1)
3714 dist
= copy
->subs
[eq
].coef
[0];
3720 /* Save the lexicographically positive distance vector. */
3723 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3724 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3728 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
3729 if (copy
->subs
[eq
].key
> 0)
3731 dist
= copy
->subs
[eq
].coef
[0];
3732 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
3735 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3736 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3738 save_dist_v (ddr
, dist_v
);
3739 save_dir_v (ddr
, dir_v
);
3743 omega_free_problem (copy
);
3747 /* This is called for each subscript of a tuple of data references:
3748 insert an equality for representing the conflicts. */
3751 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
3752 struct data_dependence_relation
*ddr
,
3753 omega_pb pb
, bool *maybe_dependent
)
3756 tree type
= signed_type_for_types (TREE_TYPE (access_fun_a
),
3757 TREE_TYPE (access_fun_b
));
3758 tree fun_a
= chrec_convert (type
, access_fun_a
, NULL
);
3759 tree fun_b
= chrec_convert (type
, access_fun_b
, NULL
);
3760 tree difference
= chrec_fold_minus (type
, fun_a
, fun_b
);
3763 /* When the fun_a - fun_b is not constant, the dependence is not
3764 captured by the classic distance vector representation. */
3765 if (TREE_CODE (difference
) != INTEGER_CST
)
3769 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
3771 /* There is no dependence. */
3772 *maybe_dependent
= false;
3776 minus_one
= build_int_cst (type
, -1);
3777 fun_b
= chrec_fold_multiply (type
, fun_b
, minus_one
);
3779 eq
= omega_add_zero_eq (pb
, omega_black
);
3780 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
3781 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
3782 /* There is probably a dependence, but the system of
3783 constraints cannot be built: answer "don't know". */
3787 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
3788 && !int_divides_p (lambda_vector_gcd
3789 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
3790 2 * DDR_NB_LOOPS (ddr
)),
3791 pb
->eqs
[eq
].coef
[0]))
3793 /* There is no dependence. */
3794 *maybe_dependent
= false;
3801 /* Helper function, same as init_omega_for_ddr but specialized for
3802 data references A and B. */
3805 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
3806 struct data_dependence_relation
*ddr
,
3807 omega_pb pb
, bool *maybe_dependent
)
3812 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
3814 /* Insert an equality per subscript. */
3815 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3817 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
3818 ddr
, pb
, maybe_dependent
))
3820 else if (*maybe_dependent
== false)
3822 /* There is no dependence. */
3823 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
3828 /* Insert inequalities: constraints corresponding to the iteration
3829 domain, i.e. the loops surrounding the references "loop_x" and
3830 the distance variables "dx". The layout of the OMEGA
3831 representation is as follows:
3832 - coef[0] is the constant
3833 - coef[1..nb_loops] are the protected variables that will not be
3834 removed by the solver: the "dx"
3835 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3837 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
3838 && DDR_LOOP_NEST (ddr
).iterate (i
, &loopi
); i
++)
3840 HOST_WIDE_INT nbi
= max_stmt_executions_int (loopi
);
3843 ineq
= omega_add_zero_geq (pb
, omega_black
);
3844 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3846 /* 0 <= loop_x + dx */
3847 ineq
= omega_add_zero_geq (pb
, omega_black
);
3848 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
3849 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3853 /* loop_x <= nb_iters */
3854 ineq
= omega_add_zero_geq (pb
, omega_black
);
3855 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3856 pb
->geqs
[ineq
].coef
[0] = nbi
;
3858 /* loop_x + dx <= nb_iters */
3859 ineq
= omega_add_zero_geq (pb
, omega_black
);
3860 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
3861 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3862 pb
->geqs
[ineq
].coef
[0] = nbi
;
3864 /* A step "dx" bigger than nb_iters is not feasible, so
3865 add "0 <= nb_iters + dx", */
3866 ineq
= omega_add_zero_geq (pb
, omega_black
);
3867 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
3868 pb
->geqs
[ineq
].coef
[0] = nbi
;
3869 /* and "dx <= nb_iters". */
3870 ineq
= omega_add_zero_geq (pb
, omega_black
);
3871 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
3872 pb
->geqs
[ineq
].coef
[0] = nbi
;
3876 omega_extract_distance_vectors (pb
, ddr
);
3881 /* Sets up the Omega dependence problem for the data dependence
3882 relation DDR. Returns false when the constraint system cannot be
3883 built, ie. when the test answers "don't know". Returns true
3884 otherwise, and when independence has been proved (using one of the
3885 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3886 set MAYBE_DEPENDENT to true.
3888 Example: for setting up the dependence system corresponding to the
3889 conflicting accesses
3894 | ... A[2*j, 2*(i + j)]
3898 the following constraints come from the iteration domain:
3905 where di, dj are the distance variables. The constraints
3906 representing the conflicting elements are:
3909 i + 1 = 2 * (i + di + j + dj)
3911 For asking that the resulting distance vector (di, dj) be
3912 lexicographically positive, we insert the constraint "di >= 0". If
3913 "di = 0" in the solution, we fix that component to zero, and we
3914 look at the inner loops: we set a new problem where all the outer
3915 loop distances are zero, and fix this inner component to be
3916 positive. When one of the components is positive, we save that
3917 distance, and set a new problem where the distance on this loop is
3918 zero, searching for other distances in the inner loops. Here is
3919 the classic example that illustrates that we have to set for each
3920 inner loop a new problem:
3928 we have to save two distances (1, 0) and (0, 1).
3930 Given two array references, refA and refB, we have to set the
3931 dependence problem twice, refA vs. refB and refB vs. refA, and we
3932 cannot do a single test, as refB might occur before refA in the
3933 inner loops, and the contrary when considering outer loops: ex.
3938 | T[{1,+,1}_2][{1,+,1}_1] // refA
3939 | T[{2,+,1}_2][{0,+,1}_1] // refB
3944 refB touches the elements in T before refA, and thus for the same
3945 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3946 but for successive loop_0 iterations, we have (1, -1, 1)
3948 The Omega solver expects the distance variables ("di" in the
3949 previous example) to come first in the constraint system (as
3950 variables to be protected, or "safe" variables), the constraint
3951 system is built using the following layout:
3953 "cst | distance vars | index vars".
3957 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
3958 bool *maybe_dependent
)
3963 *maybe_dependent
= true;
3965 if (same_access_functions (ddr
))
3968 lambda_vector dir_v
;
3970 /* Save the 0 vector. */
3971 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3972 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3973 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3974 dir_v
[j
] = dir_equal
;
3975 save_dir_v (ddr
, dir_v
);
3977 /* Save the dependences carried by outer loops. */
3978 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3979 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3981 omega_free_problem (pb
);
3985 /* Omega expects the protected variables (those that have to be kept
3986 after elimination) to appear first in the constraint system.
3987 These variables are the distance variables. In the following
3988 initialization we declare NB_LOOPS safe variables, and the total
3989 number of variables for the constraint system is 2*NB_LOOPS. */
3990 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
3991 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
3993 omega_free_problem (pb
);
3995 /* Stop computation if not decidable, or no dependence. */
3996 if (res
== false || *maybe_dependent
== false)
3999 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4000 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
4002 omega_free_problem (pb
);
4007 /* Return true when DDR contains the same information as that stored
4008 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4011 ddr_consistent_p (FILE *file
,
4012 struct data_dependence_relation
*ddr
,
4013 vec
<lambda_vector
> dist_vects
,
4014 vec
<lambda_vector
> dir_vects
)
4018 /* If dump_file is set, output there. */
4019 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4022 if (dist_vects
.length () != DDR_NUM_DIST_VECTS (ddr
))
4024 lambda_vector b_dist_v
;
4025 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4026 dist_vects
.length (),
4027 DDR_NUM_DIST_VECTS (ddr
));
4029 fprintf (file
, "Banerjee dist vectors:\n");
4030 FOR_EACH_VEC_ELT (dist_vects
, i
, b_dist_v
)
4031 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
4033 fprintf (file
, "Omega dist vectors:\n");
4034 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4035 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
4037 fprintf (file
, "data dependence relation:\n");
4038 dump_data_dependence_relation (file
, ddr
);
4040 fprintf (file
, ")\n");
4044 if (dir_vects
.length () != DDR_NUM_DIR_VECTS (ddr
))
4046 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4047 dir_vects
.length (),
4048 DDR_NUM_DIR_VECTS (ddr
));
4052 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4054 lambda_vector a_dist_v
;
4055 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
4057 /* Distance vectors are not ordered in the same way in the DDR
4058 and in the DIST_VECTS: search for a matching vector. */
4059 FOR_EACH_VEC_ELT (dist_vects
, j
, a_dist_v
)
4060 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
4063 if (j
== dist_vects
.length ())
4065 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
4066 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
4067 fprintf (file
, "not found in Omega dist vectors:\n");
4068 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4069 fprintf (file
, "data dependence relation:\n");
4070 dump_data_dependence_relation (file
, ddr
);
4071 fprintf (file
, ")\n");
4075 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
4077 lambda_vector a_dir_v
;
4078 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
4080 /* Direction vectors are not ordered in the same way in the DDR
4081 and in the DIR_VECTS: search for a matching vector. */
4082 FOR_EACH_VEC_ELT (dir_vects
, j
, a_dir_v
)
4083 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
4086 if (j
== dist_vects
.length ())
4088 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
4089 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
4090 fprintf (file
, "not found in Omega dir vectors:\n");
4091 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4092 fprintf (file
, "data dependence relation:\n");
4093 dump_data_dependence_relation (file
, ddr
);
4094 fprintf (file
, ")\n");
4101 /* This computes the affine dependence relation between A and B with
4102 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4103 independence between two accesses, while CHREC_DONT_KNOW is used
4104 for representing the unknown relation.
4106 Note that it is possible to stop the computation of the dependence
4107 relation the first time we detect a CHREC_KNOWN element for a given
4111 compute_affine_dependence (struct data_dependence_relation
*ddr
,
4112 struct loop
*loop_nest
)
4114 struct data_reference
*dra
= DDR_A (ddr
);
4115 struct data_reference
*drb
= DDR_B (ddr
);
4117 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4119 fprintf (dump_file
, "(compute_affine_dependence\n");
4120 fprintf (dump_file
, " stmt_a: ");
4121 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, TDF_SLIM
);
4122 fprintf (dump_file
, " stmt_b: ");
4123 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, TDF_SLIM
);
4126 /* Analyze only when the dependence relation is not yet known. */
4127 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4129 dependence_stats
.num_dependence_tests
++;
4131 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
4132 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
4134 subscript_dependence_tester (ddr
, loop_nest
);
4136 if (flag_check_data_deps
)
4138 /* Dump the dependences from the first algorithm. */
4139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4141 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
4142 dump_data_dependence_relation (dump_file
, ddr
);
4145 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4147 bool maybe_dependent
;
4148 vec
<lambda_vector
> dir_vects
, dist_vects
;
4150 /* Save the result of the first DD analyzer. */
4151 dist_vects
= DDR_DIST_VECTS (ddr
);
4152 dir_vects
= DDR_DIR_VECTS (ddr
);
4154 /* Reset the information. */
4155 DDR_DIST_VECTS (ddr
).create (0);
4156 DDR_DIR_VECTS (ddr
).create (0);
4158 /* Compute the same information using Omega. */
4159 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
4160 goto csys_dont_know
;
4162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4164 fprintf (dump_file
, "Omega Analyzer\n");
4165 dump_data_dependence_relation (dump_file
, ddr
);
4168 /* Check that we get the same information. */
4169 if (maybe_dependent
)
4170 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
4176 /* As a last case, if the dependence cannot be determined, or if
4177 the dependence is considered too difficult to determine, answer
4182 dependence_stats
.num_dependence_undetermined
++;
4184 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4186 fprintf (dump_file
, "Data ref a:\n");
4187 dump_data_reference (dump_file
, dra
);
4188 fprintf (dump_file
, "Data ref b:\n");
4189 dump_data_reference (dump_file
, drb
);
4190 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
4192 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4196 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4198 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4199 fprintf (dump_file
, ") -> no dependence\n");
4200 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4201 fprintf (dump_file
, ") -> dependence analysis failed\n");
4203 fprintf (dump_file
, ")\n");
4207 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4208 the data references in DATAREFS, in the LOOP_NEST. When
4209 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4210 relations. Return true when successful, i.e. data references number
4211 is small enough to be handled. */
4214 compute_all_dependences (vec
<data_reference_p
> datarefs
,
4215 vec
<ddr_p
> *dependence_relations
,
4216 vec
<loop_p
> loop_nest
,
4217 bool compute_self_and_rr
)
4219 struct data_dependence_relation
*ddr
;
4220 struct data_reference
*a
, *b
;
4223 if ((int) datarefs
.length ()
4224 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS
))
4226 struct data_dependence_relation
*ddr
;
4228 /* Insert a single relation into dependence_relations:
4230 ddr
= initialize_data_dependence_relation (NULL
, NULL
, loop_nest
);
4231 dependence_relations
->safe_push (ddr
);
4235 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4236 for (j
= i
+ 1; datarefs
.iterate (j
, &b
); j
++)
4237 if (DR_IS_WRITE (a
) || DR_IS_WRITE (b
) || compute_self_and_rr
)
4239 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4240 dependence_relations
->safe_push (ddr
);
4241 if (loop_nest
.exists ())
4242 compute_affine_dependence (ddr
, loop_nest
[0]);
4245 if (compute_self_and_rr
)
4246 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4248 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4249 dependence_relations
->safe_push (ddr
);
4250 if (loop_nest
.exists ())
4251 compute_affine_dependence (ddr
, loop_nest
[0]);
4257 /* Describes a location of a memory reference. */
4259 typedef struct data_ref_loc_d
4261 /* Position of the memory reference. */
4264 /* True if the memory reference is read. */
4269 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4270 true if STMT clobbers memory, false otherwise. */
4273 get_references_in_stmt (gimple stmt
, vec
<data_ref_loc
> *references
)
4275 bool clobbers_memory
= false;
4278 enum gimple_code stmt_code
= gimple_code (stmt
);
4280 references
->create (0);
4282 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4283 As we cannot model data-references to not spelled out
4284 accesses give up if they may occur. */
4285 if ((stmt_code
== GIMPLE_CALL
4286 && !(gimple_call_flags (stmt
) & ECF_CONST
))
4287 || (stmt_code
== GIMPLE_ASM
4288 && (gimple_asm_volatile_p (stmt
) || gimple_vuse (stmt
))))
4289 clobbers_memory
= true;
4291 if (!gimple_vuse (stmt
))
4292 return clobbers_memory
;
4294 if (stmt_code
== GIMPLE_ASSIGN
)
4297 op0
= gimple_assign_lhs_ptr (stmt
);
4298 op1
= gimple_assign_rhs1_ptr (stmt
);
4301 || (REFERENCE_CLASS_P (*op1
)
4302 && (base
= get_base_address (*op1
))
4303 && TREE_CODE (base
) != SSA_NAME
))
4307 references
->safe_push (ref
);
4310 else if (stmt_code
== GIMPLE_CALL
)
4314 op0
= gimple_call_lhs_ptr (stmt
);
4315 n
= gimple_call_num_args (stmt
);
4316 for (i
= 0; i
< n
; i
++)
4318 op1
= gimple_call_arg_ptr (stmt
, i
);
4321 || (REFERENCE_CLASS_P (*op1
) && get_base_address (*op1
)))
4325 references
->safe_push (ref
);
4330 return clobbers_memory
;
4334 || (REFERENCE_CLASS_P (*op0
) && get_base_address (*op0
))))
4337 ref
.is_read
= false;
4338 references
->safe_push (ref
);
4340 return clobbers_memory
;
4343 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4344 reference, returns false, otherwise returns true. NEST is the outermost
4345 loop of the loop nest in which the references should be analyzed. */
4348 find_data_references_in_stmt (struct loop
*nest
, gimple stmt
,
4349 vec
<data_reference_p
> *datarefs
)
4352 vec
<data_ref_loc
> references
;
4355 data_reference_p dr
;
4357 if (get_references_in_stmt (stmt
, &references
))
4359 references
.release ();
4363 FOR_EACH_VEC_ELT (references
, i
, ref
)
4365 dr
= create_data_ref (nest
, loop_containing_stmt (stmt
),
4366 *ref
->pos
, stmt
, ref
->is_read
);
4367 gcc_assert (dr
!= NULL
);
4368 datarefs
->safe_push (dr
);
4370 references
.release ();
4374 /* Stores the data references in STMT to DATAREFS. If there is an
4375 unanalyzable reference, returns false, otherwise returns true.
4376 NEST is the outermost loop of the loop nest in which the references
4377 should be instantiated, LOOP is the loop in which the references
4378 should be analyzed. */
4381 graphite_find_data_references_in_stmt (loop_p nest
, loop_p loop
, gimple stmt
,
4382 vec
<data_reference_p
> *datarefs
)
4385 vec
<data_ref_loc
> references
;
4388 data_reference_p dr
;
4390 if (get_references_in_stmt (stmt
, &references
))
4392 references
.release ();
4396 FOR_EACH_VEC_ELT (references
, i
, ref
)
4398 dr
= create_data_ref (nest
, loop
, *ref
->pos
, stmt
, ref
->is_read
);
4399 gcc_assert (dr
!= NULL
);
4400 datarefs
->safe_push (dr
);
4403 references
.release ();
4407 /* Search the data references in LOOP, and record the information into
4408 DATAREFS. Returns chrec_dont_know when failing to analyze a
4409 difficult case, returns NULL_TREE otherwise. */
4412 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
4413 vec
<data_reference_p
> *datarefs
)
4415 gimple_stmt_iterator bsi
;
4417 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4419 gimple stmt
= gsi_stmt (bsi
);
4421 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
4423 struct data_reference
*res
;
4424 res
= XCNEW (struct data_reference
);
4425 datarefs
->safe_push (res
);
4427 return chrec_dont_know
;
4434 /* Search the data references in LOOP, and record the information into
4435 DATAREFS. Returns chrec_dont_know when failing to analyze a
4436 difficult case, returns NULL_TREE otherwise.
4438 TODO: This function should be made smarter so that it can handle address
4439 arithmetic as if they were array accesses, etc. */
4442 find_data_references_in_loop (struct loop
*loop
,
4443 vec
<data_reference_p
> *datarefs
)
4445 basic_block bb
, *bbs
;
4448 bbs
= get_loop_body_in_dom_order (loop
);
4450 for (i
= 0; i
< loop
->num_nodes
; i
++)
4454 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
4457 return chrec_dont_know
;
4465 /* Recursive helper function. */
4468 find_loop_nest_1 (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
4470 /* Inner loops of the nest should not contain siblings. Example:
4471 when there are two consecutive loops,
4482 the dependence relation cannot be captured by the distance
4487 loop_nest
->safe_push (loop
);
4489 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4493 /* Return false when the LOOP is not well nested. Otherwise return
4494 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4495 contain the loops from the outermost to the innermost, as they will
4496 appear in the classic distance vector. */
4499 find_loop_nest (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
4501 loop_nest
->safe_push (loop
);
4503 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4507 /* Returns true when the data dependences have been computed, false otherwise.
4508 Given a loop nest LOOP, the following vectors are returned:
4509 DATAREFS is initialized to all the array elements contained in this loop,
4510 DEPENDENCE_RELATIONS contains the relations between the data references.
4511 Compute read-read and self relations if
4512 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4515 compute_data_dependences_for_loop (struct loop
*loop
,
4516 bool compute_self_and_read_read_dependences
,
4517 vec
<loop_p
> *loop_nest
,
4518 vec
<data_reference_p
> *datarefs
,
4519 vec
<ddr_p
> *dependence_relations
)
4523 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4525 /* If the loop nest is not well formed, or one of the data references
4526 is not computable, give up without spending time to compute other
4529 || !find_loop_nest (loop
, loop_nest
)
4530 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
4531 || !compute_all_dependences (*datarefs
, dependence_relations
, *loop_nest
,
4532 compute_self_and_read_read_dependences
))
4535 if (dump_file
&& (dump_flags
& TDF_STATS
))
4537 fprintf (dump_file
, "Dependence tester statistics:\n");
4539 fprintf (dump_file
, "Number of dependence tests: %d\n",
4540 dependence_stats
.num_dependence_tests
);
4541 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4542 dependence_stats
.num_dependence_dependent
);
4543 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4544 dependence_stats
.num_dependence_independent
);
4545 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4546 dependence_stats
.num_dependence_undetermined
);
4548 fprintf (dump_file
, "Number of subscript tests: %d\n",
4549 dependence_stats
.num_subscript_tests
);
4550 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4551 dependence_stats
.num_subscript_undetermined
);
4552 fprintf (dump_file
, "Number of same subscript function: %d\n",
4553 dependence_stats
.num_same_subscript_function
);
4555 fprintf (dump_file
, "Number of ziv tests: %d\n",
4556 dependence_stats
.num_ziv
);
4557 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4558 dependence_stats
.num_ziv_dependent
);
4559 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4560 dependence_stats
.num_ziv_independent
);
4561 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4562 dependence_stats
.num_ziv_unimplemented
);
4564 fprintf (dump_file
, "Number of siv tests: %d\n",
4565 dependence_stats
.num_siv
);
4566 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4567 dependence_stats
.num_siv_dependent
);
4568 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4569 dependence_stats
.num_siv_independent
);
4570 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4571 dependence_stats
.num_siv_unimplemented
);
4573 fprintf (dump_file
, "Number of miv tests: %d\n",
4574 dependence_stats
.num_miv
);
4575 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4576 dependence_stats
.num_miv_dependent
);
4577 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4578 dependence_stats
.num_miv_independent
);
4579 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4580 dependence_stats
.num_miv_unimplemented
);
4586 /* Returns true when the data dependences for the basic block BB have been
4587 computed, false otherwise.
4588 DATAREFS is initialized to all the array elements contained in this basic
4589 block, DEPENDENCE_RELATIONS contains the relations between the data
4590 references. Compute read-read and self relations if
4591 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4593 compute_data_dependences_for_bb (basic_block bb
,
4594 bool compute_self_and_read_read_dependences
,
4595 vec
<data_reference_p
> *datarefs
,
4596 vec
<ddr_p
> *dependence_relations
)
4598 if (find_data_references_in_bb (NULL
, bb
, datarefs
) == chrec_dont_know
)
4601 return compute_all_dependences (*datarefs
, dependence_relations
, vNULL
,
4602 compute_self_and_read_read_dependences
);
4605 /* Entry point (for testing only). Analyze all the data references
4606 and the dependence relations in LOOP.
4608 The data references are computed first.
4610 A relation on these nodes is represented by a complete graph. Some
4611 of the relations could be of no interest, thus the relations can be
4614 In the following function we compute all the relations. This is
4615 just a first implementation that is here for:
4616 - for showing how to ask for the dependence relations,
4617 - for the debugging the whole dependence graph,
4618 - for the dejagnu testcases and maintenance.
4620 It is possible to ask only for a part of the graph, avoiding to
4621 compute the whole dependence graph. The computed dependences are
4622 stored in a knowledge base (KB) such that later queries don't
4623 recompute the same information. The implementation of this KB is
4624 transparent to the optimizer, and thus the KB can be changed with a
4625 more efficient implementation, or the KB could be disabled. */
4627 analyze_all_data_dependences (struct loop
*loop
)
4630 int nb_data_refs
= 10;
4631 vec
<data_reference_p
> datarefs
;
4632 datarefs
.create (nb_data_refs
);
4633 vec
<ddr_p
> dependence_relations
;
4634 dependence_relations
.create (nb_data_refs
* nb_data_refs
);
4635 vec
<loop_p
> loop_nest
;
4636 loop_nest
.create (3);
4638 /* Compute DDs on the whole function. */
4639 compute_data_dependences_for_loop (loop
, false, &loop_nest
, &datarefs
,
4640 &dependence_relations
);
4644 dump_data_dependence_relations (dump_file
, dependence_relations
);
4645 fprintf (dump_file
, "\n\n");
4647 if (dump_flags
& TDF_DETAILS
)
4648 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4650 if (dump_flags
& TDF_STATS
)
4652 unsigned nb_top_relations
= 0;
4653 unsigned nb_bot_relations
= 0;
4654 unsigned nb_chrec_relations
= 0;
4655 struct data_dependence_relation
*ddr
;
4657 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
4659 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4662 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4666 nb_chrec_relations
++;
4669 gather_stats_on_scev_database ();
4673 loop_nest
.release ();
4674 free_dependence_relations (dependence_relations
);
4675 free_data_refs (datarefs
);
4678 /* Computes all the data dependences and check that the results of
4679 several analyzers are the same. */
4682 tree_check_data_deps (void)
4685 struct loop
*loop_nest
;
4687 FOR_EACH_LOOP (li
, loop_nest
, 0)
4688 analyze_all_data_dependences (loop_nest
);
4691 /* Free the memory used by a data dependence relation DDR. */
4694 free_dependence_relation (struct data_dependence_relation
*ddr
)
4699 if (DDR_SUBSCRIPTS (ddr
).exists ())
4700 free_subscripts (DDR_SUBSCRIPTS (ddr
));
4701 DDR_DIST_VECTS (ddr
).release ();
4702 DDR_DIR_VECTS (ddr
).release ();
4707 /* Free the memory used by the data dependence relations from
4708 DEPENDENCE_RELATIONS. */
4711 free_dependence_relations (vec
<ddr_p
> dependence_relations
)
4714 struct data_dependence_relation
*ddr
;
4716 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
4718 free_dependence_relation (ddr
);
4720 dependence_relations
.release ();
4723 /* Free the memory used by the data references from DATAREFS. */
4726 free_data_refs (vec
<data_reference_p
> datarefs
)
4729 struct data_reference
*dr
;
4731 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
4733 datarefs
.release ();
4738 /* Dump vertex I in RDG to FILE. */
4741 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
4743 struct vertex
*v
= &(rdg
->vertices
[i
]);
4744 struct graph_edge
*e
;
4746 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
4747 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
4748 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
4751 for (e
= v
->pred
; e
; e
= e
->pred_next
)
4752 fprintf (file
, " %d", e
->src
);
4754 fprintf (file
, ") (out:");
4757 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4758 fprintf (file
, " %d", e
->dest
);
4760 fprintf (file
, ")\n");
4761 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
4762 fprintf (file
, ")\n");
4765 /* Call dump_rdg_vertex on stderr. */
4768 debug_rdg_vertex (struct graph
*rdg
, int i
)
4770 dump_rdg_vertex (stderr
, rdg
, i
);
4773 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4774 dumped vertices to that bitmap. */
4777 dump_rdg_component (FILE *file
, struct graph
*rdg
, int c
, bitmap dumped
)
4781 fprintf (file
, "(%d\n", c
);
4783 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4784 if (rdg
->vertices
[i
].component
== c
)
4787 bitmap_set_bit (dumped
, i
);
4789 dump_rdg_vertex (file
, rdg
, i
);
4792 fprintf (file
, ")\n");
4795 /* Call dump_rdg_vertex on stderr. */
4798 debug_rdg_component (struct graph
*rdg
, int c
)
4800 dump_rdg_component (stderr
, rdg
, c
, NULL
);
4803 /* Dump the reduced dependence graph RDG to FILE. */
4806 dump_rdg (FILE *file
, struct graph
*rdg
)
4809 bitmap dumped
= BITMAP_ALLOC (NULL
);
4811 fprintf (file
, "(rdg\n");
4813 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4814 if (!bitmap_bit_p (dumped
, i
))
4815 dump_rdg_component (file
, rdg
, rdg
->vertices
[i
].component
, dumped
);
4817 fprintf (file
, ")\n");
4818 BITMAP_FREE (dumped
);
4821 /* Call dump_rdg on stderr. */
4824 debug_rdg (struct graph
*rdg
)
4826 dump_rdg (stderr
, rdg
);
4830 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
4834 fprintf (file
, "digraph RDG {\n");
4836 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4838 struct vertex
*v
= &(rdg
->vertices
[i
]);
4839 struct graph_edge
*e
;
4841 /* Highlight reads from memory. */
4842 if (RDG_MEM_READS_STMT (rdg
, i
))
4843 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
4845 /* Highlight stores to memory. */
4846 if (RDG_MEM_WRITE_STMT (rdg
, i
))
4847 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
4850 for (e
= v
->succ
; e
; e
= e
->succ_next
)
4851 switch (RDGE_TYPE (e
))
4854 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
4858 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
4862 /* These are the most common dependences: don't print these. */
4863 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
4867 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
4875 fprintf (file
, "}\n\n");
4878 /* Display the Reduced Dependence Graph using dotty. */
4879 extern void dot_rdg (struct graph
*);
4882 dot_rdg (struct graph
*rdg
)
4884 /* When debugging, enable the following code. This cannot be used
4885 in production compilers because it calls "system". */
4887 FILE *file
= fopen ("/tmp/rdg.dot", "w");
4888 gcc_assert (file
!= NULL
);
4890 dot_rdg_1 (file
, rdg
);
4893 system ("dotty /tmp/rdg.dot &");
4895 dot_rdg_1 (stderr
, rdg
);
4899 /* Returns the index of STMT in RDG. */
4902 rdg_vertex_for_stmt (struct graph
*rdg ATTRIBUTE_UNUSED
, gimple stmt
)
4904 int index
= gimple_uid (stmt
);
4905 gcc_checking_assert (index
== -1 || RDG_STMT (rdg
, index
) == stmt
);
4909 /* Creates an edge in RDG for each distance vector from DDR. The
4910 order that we keep track of in the RDG is the order in which
4911 statements have to be executed. */
4914 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
4916 struct graph_edge
*e
;
4918 data_reference_p dra
= DDR_A (ddr
);
4919 data_reference_p drb
= DDR_B (ddr
);
4920 unsigned level
= ddr_dependence_level (ddr
);
4922 /* For non scalar dependences, when the dependence is REVERSED,
4923 statement B has to be executed before statement A. */
4925 && !DDR_REVERSED_P (ddr
))
4927 data_reference_p tmp
= dra
;
4932 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
4933 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
4935 if (va
< 0 || vb
< 0)
4938 e
= add_edge (rdg
, va
, vb
);
4939 e
->data
= XNEW (struct rdg_edge
);
4941 RDGE_LEVEL (e
) = level
;
4942 RDGE_RELATION (e
) = ddr
;
4944 /* Determines the type of the data dependence. */
4945 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
4946 RDGE_TYPE (e
) = input_dd
;
4947 else if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
4948 RDGE_TYPE (e
) = output_dd
;
4949 else if (DR_IS_WRITE (dra
) && DR_IS_READ (drb
))
4950 RDGE_TYPE (e
) = flow_dd
;
4951 else if (DR_IS_READ (dra
) && DR_IS_WRITE (drb
))
4952 RDGE_TYPE (e
) = anti_dd
;
4955 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4956 the index of DEF in RDG. */
4959 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
4961 use_operand_p imm_use_p
;
4962 imm_use_iterator iterator
;
4964 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
4966 struct graph_edge
*e
;
4967 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
4972 e
= add_edge (rdg
, idef
, use
);
4973 e
->data
= XNEW (struct rdg_edge
);
4974 RDGE_TYPE (e
) = flow_dd
;
4975 RDGE_RELATION (e
) = NULL
;
4979 /* Creates the edges of the reduced dependence graph RDG. */
4982 create_rdg_edges (struct graph
*rdg
, vec
<ddr_p
> ddrs
)
4985 struct data_dependence_relation
*ddr
;
4986 def_operand_p def_p
;
4989 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
4990 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4991 create_rdg_edge_for_ddr (rdg
, ddr
);
4993 for (i
= 0; i
< rdg
->n_vertices
; i
++)
4994 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
4996 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
4999 /* Build the vertices of the reduced dependence graph RDG. */
5002 create_rdg_vertices (struct graph
*rdg
, vec
<gimple
> stmts
, loop_p loop
)
5007 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
5009 vec
<data_ref_loc
> references
;
5011 struct vertex
*v
= &(rdg
->vertices
[i
]);
5013 /* Record statement to vertex mapping. */
5014 gimple_set_uid (stmt
, i
);
5016 v
->data
= XNEW (struct rdg_vertex
);
5017 RDGV_STMT (v
) = stmt
;
5018 RDGV_DATAREFS (v
).create (0);
5019 RDGV_HAS_MEM_WRITE (v
) = false;
5020 RDGV_HAS_MEM_READS (v
) = false;
5021 if (gimple_code (stmt
) == GIMPLE_PHI
)
5024 get_references_in_stmt (stmt
, &references
);
5025 FOR_EACH_VEC_ELT (references
, j
, ref
)
5027 data_reference_p dr
;
5029 RDGV_HAS_MEM_WRITE (v
) = true;
5031 RDGV_HAS_MEM_READS (v
) = true;
5032 dr
= create_data_ref (loop
, loop_containing_stmt (stmt
),
5033 *ref
->pos
, stmt
, ref
->is_read
);
5035 RDGV_DATAREFS (v
).safe_push (dr
);
5037 references
.release ();
5041 /* Initialize STMTS with all the statements of LOOP. When
5042 INCLUDE_PHIS is true, include also the PHI nodes. The order in
5043 which we discover statements is important as
5044 generate_loops_for_partition is using the same traversal for
5045 identifying statements. */
5048 stmts_from_loop (struct loop
*loop
, vec
<gimple
> *stmts
)
5051 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
5053 for (i
= 0; i
< loop
->num_nodes
; i
++)
5055 basic_block bb
= bbs
[i
];
5056 gimple_stmt_iterator bsi
;
5059 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
5060 stmts
->safe_push (gsi_stmt (bsi
));
5062 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
5064 stmt
= gsi_stmt (bsi
);
5065 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
5066 stmts
->safe_push (stmt
);
5073 /* Returns true when all the dependences are computable. */
5076 known_dependences_p (vec
<ddr_p
> dependence_relations
)
5081 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
5082 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
5088 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5089 statement of the loop nest, and one edge per data dependence or
5090 scalar dependence. */
5093 build_empty_rdg (int n_stmts
)
5095 struct graph
*rdg
= new_graph (n_stmts
);
5099 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5100 statement of the loop nest, and one edge per data dependence or
5101 scalar dependence. */
5104 build_rdg (struct loop
*loop
,
5105 vec
<loop_p
> *loop_nest
,
5106 vec
<ddr_p
> *dependence_relations
,
5107 vec
<data_reference_p
> *datarefs
)
5109 struct graph
*rdg
= NULL
;
5111 if (compute_data_dependences_for_loop (loop
, false, loop_nest
, datarefs
,
5112 dependence_relations
)
5113 && known_dependences_p (*dependence_relations
))
5117 stmts_from_loop (loop
, &stmts
);
5118 rdg
= build_empty_rdg (stmts
.length ());
5119 create_rdg_vertices (rdg
, stmts
, loop
);
5120 create_rdg_edges (rdg
, *dependence_relations
);
5127 /* Free the reduced dependence graph RDG. */
5130 free_rdg (struct graph
*rdg
)
5134 for (i
= 0; i
< rdg
->n_vertices
; i
++)
5136 struct vertex
*v
= &(rdg
->vertices
[i
]);
5137 struct graph_edge
*e
;
5139 for (e
= v
->succ
; e
; e
= e
->succ_next
)
5142 gimple_set_uid (RDGV_STMT (v
), -1);
5143 free_data_refs (RDGV_DATAREFS (v
));
5150 /* Determines whether the statement from vertex V of the RDG has a
5151 definition used outside the loop that contains this statement. */
5154 rdg_defs_used_in_other_loops_p (struct graph
*rdg
, int v
)
5156 gimple stmt
= RDG_STMT (rdg
, v
);
5157 struct loop
*loop
= loop_containing_stmt (stmt
);
5158 use_operand_p imm_use_p
;
5159 imm_use_iterator iterator
;
5161 def_operand_p def_p
;
5166 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, it
, SSA_OP_DEF
)
5168 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, DEF_FROM_PTR (def_p
))
5170 if (loop_containing_stmt (USE_STMT (imm_use_p
)) != loop
)