1 /* Data references and dependences detectors.
2 Copyright (C) 2003-2018 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass walks a given loop structure searching for array
22 references. The information about the array accesses is recorded
23 in DATA_REFERENCE structures.
25 The basic test for determining the dependences is:
26 given two access functions chrec1 and chrec2 to a same array, and
27 x and y two vectors from the iteration domain, the same element of
28 the array is accessed twice at iterations x and y if and only if:
29 | chrec1 (x) == chrec2 (y).
31 The goals of this analysis are:
33 - to determine the independence: the relation between two
34 independent accesses is qualified with the chrec_known (this
35 information allows a loop parallelization),
37 - when two data references access the same data, to qualify the
38 dependence relation with classic dependence representations:
42 - loop carried level dependence
43 - polyhedron dependence
44 or with the chains of recurrences based representation,
46 - to define a knowledge base for storing the data dependence
49 - to define an interface to access this data.
54 - subscript: given two array accesses a subscript is the tuple
55 composed of the access functions for a given dimension. Example:
56 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
57 (f1, g1), (f2, g2), (f3, g3).
59 - Diophantine equation: an equation whose coefficients and
60 solutions are integer constants, for example the equation
62 has an integer solution x = 1 and y = -1.
66 - "Advanced Compilation for High Performance Computing" by Randy
67 Allen and Ken Kennedy.
68 http://citeseer.ist.psu.edu/goff91practical.html
70 - "Loop Transformations for Restructuring Compilers - The Foundations"
78 #include "coretypes.h"
83 #include "gimple-pretty-print.h"
85 #include "fold-const.h"
87 #include "gimple-iterator.h"
88 #include "tree-ssa-loop-niter.h"
89 #include "tree-ssa-loop.h"
92 #include "tree-data-ref.h"
93 #include "tree-scalar-evolution.h"
95 #include "tree-affine.h"
98 #include "stringpool.h"
100 #include "tree-ssanames.h"
103 static struct datadep_stats
105 int num_dependence_tests
;
106 int num_dependence_dependent
;
107 int num_dependence_independent
;
108 int num_dependence_undetermined
;
110 int num_subscript_tests
;
111 int num_subscript_undetermined
;
112 int num_same_subscript_function
;
115 int num_ziv_independent
;
116 int num_ziv_dependent
;
117 int num_ziv_unimplemented
;
120 int num_siv_independent
;
121 int num_siv_dependent
;
122 int num_siv_unimplemented
;
125 int num_miv_independent
;
126 int num_miv_dependent
;
127 int num_miv_unimplemented
;
130 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
131 unsigned int, unsigned int,
133 /* Returns true iff A divides B. */
136 tree_fold_divides_p (const_tree a
, const_tree b
)
138 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
139 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
140 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
));
143 /* Returns true iff A divides B. */
146 int_divides_p (int a
, int b
)
148 return ((b
% a
) == 0);
151 /* Return true if reference REF contains a union access. */
154 ref_contains_union_access_p (tree ref
)
156 while (handled_component_p (ref
))
158 ref
= TREE_OPERAND (ref
, 0);
159 if (TREE_CODE (TREE_TYPE (ref
)) == UNION_TYPE
160 || TREE_CODE (TREE_TYPE (ref
)) == QUAL_UNION_TYPE
)
168 /* Dump into FILE all the data references from DATAREFS. */
171 dump_data_references (FILE *file
, vec
<data_reference_p
> datarefs
)
174 struct data_reference
*dr
;
176 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
177 dump_data_reference (file
, dr
);
180 /* Unified dump into FILE all the data references from DATAREFS. */
183 debug (vec
<data_reference_p
> &ref
)
185 dump_data_references (stderr
, ref
);
189 debug (vec
<data_reference_p
> *ptr
)
194 fprintf (stderr
, "<nil>\n");
198 /* Dump into STDERR all the data references from DATAREFS. */
201 debug_data_references (vec
<data_reference_p
> datarefs
)
203 dump_data_references (stderr
, datarefs
);
206 /* Print to STDERR the data_reference DR. */
209 debug_data_reference (struct data_reference
*dr
)
211 dump_data_reference (stderr
, dr
);
214 /* Dump function for a DATA_REFERENCE structure. */
217 dump_data_reference (FILE *outf
,
218 struct data_reference
*dr
)
222 fprintf (outf
, "#(Data Ref: \n");
223 fprintf (outf
, "# bb: %d \n", gimple_bb (DR_STMT (dr
))->index
);
224 fprintf (outf
, "# stmt: ");
225 print_gimple_stmt (outf
, DR_STMT (dr
), 0);
226 fprintf (outf
, "# ref: ");
227 print_generic_stmt (outf
, DR_REF (dr
));
228 fprintf (outf
, "# base_object: ");
229 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
));
231 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
233 fprintf (outf
, "# Access function %d: ", i
);
234 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
));
236 fprintf (outf
, "#)\n");
239 /* Unified dump function for a DATA_REFERENCE structure. */
242 debug (data_reference
&ref
)
244 dump_data_reference (stderr
, &ref
);
248 debug (data_reference
*ptr
)
253 fprintf (stderr
, "<nil>\n");
257 /* Dumps the affine function described by FN to the file OUTF. */
260 dump_affine_function (FILE *outf
, affine_fn fn
)
265 print_generic_expr (outf
, fn
[0], TDF_SLIM
);
266 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
268 fprintf (outf
, " + ");
269 print_generic_expr (outf
, coef
, TDF_SLIM
);
270 fprintf (outf
, " * x_%u", i
);
274 /* Dumps the conflict function CF to the file OUTF. */
277 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
281 if (cf
->n
== NO_DEPENDENCE
)
282 fprintf (outf
, "no dependence");
283 else if (cf
->n
== NOT_KNOWN
)
284 fprintf (outf
, "not known");
287 for (i
= 0; i
< cf
->n
; i
++)
292 dump_affine_function (outf
, cf
->fns
[i
]);
298 /* Dump function for a SUBSCRIPT structure. */
301 dump_subscript (FILE *outf
, struct subscript
*subscript
)
303 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
305 fprintf (outf
, "\n (subscript \n");
306 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
307 dump_conflict_function (outf
, cf
);
308 if (CF_NONTRIVIAL_P (cf
))
310 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
311 fprintf (outf
, "\n last_conflict: ");
312 print_generic_expr (outf
, last_iteration
);
315 cf
= SUB_CONFLICTS_IN_B (subscript
);
316 fprintf (outf
, "\n iterations_that_access_an_element_twice_in_B: ");
317 dump_conflict_function (outf
, cf
);
318 if (CF_NONTRIVIAL_P (cf
))
320 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
321 fprintf (outf
, "\n last_conflict: ");
322 print_generic_expr (outf
, last_iteration
);
325 fprintf (outf
, "\n (Subscript distance: ");
326 print_generic_expr (outf
, SUB_DISTANCE (subscript
));
327 fprintf (outf
, " ))\n");
330 /* Print the classic direction vector DIRV to OUTF. */
333 print_direction_vector (FILE *outf
,
339 for (eq
= 0; eq
< length
; eq
++)
341 enum data_dependence_direction dir
= ((enum data_dependence_direction
)
347 fprintf (outf
, " +");
350 fprintf (outf
, " -");
353 fprintf (outf
, " =");
355 case dir_positive_or_equal
:
356 fprintf (outf
, " +=");
358 case dir_positive_or_negative
:
359 fprintf (outf
, " +-");
361 case dir_negative_or_equal
:
362 fprintf (outf
, " -=");
365 fprintf (outf
, " *");
368 fprintf (outf
, "indep");
372 fprintf (outf
, "\n");
375 /* Print a vector of direction vectors. */
378 print_dir_vectors (FILE *outf
, vec
<lambda_vector
> dir_vects
,
384 FOR_EACH_VEC_ELT (dir_vects
, j
, v
)
385 print_direction_vector (outf
, v
, length
);
388 /* Print out a vector VEC of length N to OUTFILE. */
391 print_lambda_vector (FILE * outfile
, lambda_vector vector
, int n
)
395 for (i
= 0; i
< n
; i
++)
396 fprintf (outfile
, "%3d ", vector
[i
]);
397 fprintf (outfile
, "\n");
400 /* Print a vector of distance vectors. */
403 print_dist_vectors (FILE *outf
, vec
<lambda_vector
> dist_vects
,
409 FOR_EACH_VEC_ELT (dist_vects
, j
, v
)
410 print_lambda_vector (outf
, v
, length
);
413 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
416 dump_data_dependence_relation (FILE *outf
,
417 struct data_dependence_relation
*ddr
)
419 struct data_reference
*dra
, *drb
;
421 fprintf (outf
, "(Data Dep: \n");
423 if (!ddr
|| DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
430 dump_data_reference (outf
, dra
);
432 fprintf (outf
, " (nil)\n");
434 dump_data_reference (outf
, drb
);
436 fprintf (outf
, " (nil)\n");
438 fprintf (outf
, " (don't know)\n)\n");
444 dump_data_reference (outf
, dra
);
445 dump_data_reference (outf
, drb
);
447 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
448 fprintf (outf
, " (no dependence)\n");
450 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
456 FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr
), i
, sub
)
458 fprintf (outf
, " access_fn_A: ");
459 print_generic_stmt (outf
, SUB_ACCESS_FN (sub
, 0));
460 fprintf (outf
, " access_fn_B: ");
461 print_generic_stmt (outf
, SUB_ACCESS_FN (sub
, 1));
462 dump_subscript (outf
, sub
);
465 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
466 fprintf (outf
, " loop nest: (");
467 FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr
), i
, loopi
)
468 fprintf (outf
, "%d ", loopi
->num
);
469 fprintf (outf
, ")\n");
471 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
473 fprintf (outf
, " distance_vector: ");
474 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
478 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
480 fprintf (outf
, " direction_vector: ");
481 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
486 fprintf (outf
, ")\n");
492 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
494 dump_data_dependence_relation (stderr
, ddr
);
497 /* Dump into FILE all the dependence relations from DDRS. */
500 dump_data_dependence_relations (FILE *file
,
504 struct data_dependence_relation
*ddr
;
506 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
507 dump_data_dependence_relation (file
, ddr
);
511 debug (vec
<ddr_p
> &ref
)
513 dump_data_dependence_relations (stderr
, ref
);
517 debug (vec
<ddr_p
> *ptr
)
522 fprintf (stderr
, "<nil>\n");
526 /* Dump to STDERR all the dependence relations from DDRS. */
529 debug_data_dependence_relations (vec
<ddr_p
> ddrs
)
531 dump_data_dependence_relations (stderr
, ddrs
);
534 /* Dumps the distance and direction vectors in FILE. DDRS contains
535 the dependence relations, and VECT_SIZE is the size of the
536 dependence vectors, or in other words the number of loops in the
540 dump_dist_dir_vectors (FILE *file
, vec
<ddr_p
> ddrs
)
543 struct data_dependence_relation
*ddr
;
546 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
547 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
549 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), j
, v
)
551 fprintf (file
, "DISTANCE_V (");
552 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
553 fprintf (file
, ")\n");
556 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), j
, v
)
558 fprintf (file
, "DIRECTION_V (");
559 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
560 fprintf (file
, ")\n");
564 fprintf (file
, "\n\n");
567 /* Dumps the data dependence relations DDRS in FILE. */
570 dump_ddrs (FILE *file
, vec
<ddr_p
> ddrs
)
573 struct data_dependence_relation
*ddr
;
575 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
576 dump_data_dependence_relation (file
, ddr
);
578 fprintf (file
, "\n\n");
582 debug_ddrs (vec
<ddr_p
> ddrs
)
584 dump_ddrs (stderr
, ddrs
);
587 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
588 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
589 constant of type ssizetype, and returns true. If we cannot do this
590 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
594 split_constant_offset_1 (tree type
, tree op0
, enum tree_code code
, tree op1
,
595 tree
*var
, tree
*off
)
599 enum tree_code ocode
= code
;
607 *var
= build_int_cst (type
, 0);
608 *off
= fold_convert (ssizetype
, op0
);
611 case POINTER_PLUS_EXPR
:
616 split_constant_offset (op0
, &var0
, &off0
);
617 split_constant_offset (op1
, &var1
, &off1
);
618 *var
= fold_build2 (code
, type
, var0
, var1
);
619 *off
= size_binop (ocode
, off0
, off1
);
623 if (TREE_CODE (op1
) != INTEGER_CST
)
626 split_constant_offset (op0
, &var0
, &off0
);
627 *var
= fold_build2 (MULT_EXPR
, type
, var0
, op1
);
628 *off
= size_binop (MULT_EXPR
, off0
, fold_convert (ssizetype
, op1
));
634 poly_int64 pbitsize
, pbitpos
, pbytepos
;
636 int punsignedp
, preversep
, pvolatilep
;
638 op0
= TREE_OPERAND (op0
, 0);
640 = get_inner_reference (op0
, &pbitsize
, &pbitpos
, &poffset
, &pmode
,
641 &punsignedp
, &preversep
, &pvolatilep
);
643 if (!multiple_p (pbitpos
, BITS_PER_UNIT
, &pbytepos
))
645 base
= build_fold_addr_expr (base
);
646 off0
= ssize_int (pbytepos
);
650 split_constant_offset (poffset
, &poffset
, &off1
);
651 off0
= size_binop (PLUS_EXPR
, off0
, off1
);
652 if (POINTER_TYPE_P (TREE_TYPE (base
)))
653 base
= fold_build_pointer_plus (base
, poffset
);
655 base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
,
656 fold_convert (TREE_TYPE (base
), poffset
));
659 var0
= fold_convert (type
, base
);
661 /* If variable length types are involved, punt, otherwise casts
662 might be converted into ARRAY_REFs in gimplify_conversion.
663 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
664 possibly no longer appears in current GIMPLE, might resurface.
665 This perhaps could run
666 if (CONVERT_EXPR_P (var0))
668 gimplify_conversion (&var0);
669 // Attempt to fill in any within var0 found ARRAY_REF's
670 // element size from corresponding op embedded ARRAY_REF,
671 // if unsuccessful, just punt.
673 while (POINTER_TYPE_P (type
))
674 type
= TREE_TYPE (type
);
675 if (int_size_in_bytes (type
) < 0)
685 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
))
688 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op0
);
689 enum tree_code subcode
;
691 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
694 var0
= gimple_assign_rhs1 (def_stmt
);
695 subcode
= gimple_assign_rhs_code (def_stmt
);
696 var1
= gimple_assign_rhs2 (def_stmt
);
698 return split_constant_offset_1 (type
, var0
, subcode
, var1
, var
, off
);
702 /* We must not introduce undefined overflow, and we must not change the value.
703 Hence we're okay if the inner type doesn't overflow to start with
704 (pointer or signed), the outer type also is an integer or pointer
705 and the outer precision is at least as large as the inner. */
706 tree itype
= TREE_TYPE (op0
);
707 if ((POINTER_TYPE_P (itype
)
708 || (INTEGRAL_TYPE_P (itype
) && !TYPE_OVERFLOW_TRAPS (itype
)))
709 && TYPE_PRECISION (type
) >= TYPE_PRECISION (itype
)
710 && (POINTER_TYPE_P (type
) || INTEGRAL_TYPE_P (type
)))
712 if (INTEGRAL_TYPE_P (itype
) && TYPE_OVERFLOW_WRAPS (itype
))
714 /* Split the unconverted operand and try to prove that
715 wrapping isn't a problem. */
716 tree tmp_var
, tmp_off
;
717 split_constant_offset (op0
, &tmp_var
, &tmp_off
);
719 /* See whether we have an SSA_NAME whose range is known
721 if (TREE_CODE (tmp_var
) != SSA_NAME
)
723 wide_int var_min
, var_max
;
724 value_range_type vr_type
= get_range_info (tmp_var
, &var_min
,
726 wide_int var_nonzero
= get_nonzero_bits (tmp_var
);
727 signop sgn
= TYPE_SIGN (itype
);
728 if (intersect_range_with_nonzero_bits (vr_type
, &var_min
,
729 &var_max
, var_nonzero
,
733 /* See whether the range of OP0 (i.e. TMP_VAR + TMP_OFF)
734 is known to be [A + TMP_OFF, B + TMP_OFF], with all
735 operations done in ITYPE. The addition must overflow
736 at both ends of the range or at neither. */
738 unsigned int prec
= TYPE_PRECISION (itype
);
739 wide_int woff
= wi::to_wide (tmp_off
, prec
);
740 wide_int op0_min
= wi::add (var_min
, woff
, sgn
, &overflow
[0]);
741 wi::add (var_max
, woff
, sgn
, &overflow
[1]);
742 if (overflow
[0] != overflow
[1])
745 /* Calculate (ssizetype) OP0 - (ssizetype) TMP_VAR. */
746 widest_int diff
= (widest_int::from (op0_min
, sgn
)
747 - widest_int::from (var_min
, sgn
));
749 *off
= wide_int_to_tree (ssizetype
, diff
);
752 split_constant_offset (op0
, &var0
, off
);
753 *var
= fold_convert (type
, var0
);
764 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
765 will be ssizetype. */
768 split_constant_offset (tree exp
, tree
*var
, tree
*off
)
770 tree type
= TREE_TYPE (exp
), op0
, op1
, e
, o
;
774 *off
= ssize_int (0);
776 if (tree_is_chrec (exp
)
777 || get_gimple_rhs_class (TREE_CODE (exp
)) == GIMPLE_TERNARY_RHS
)
780 code
= TREE_CODE (exp
);
781 extract_ops_from_tree (exp
, &code
, &op0
, &op1
);
782 if (split_constant_offset_1 (type
, op0
, code
, op1
, &e
, &o
))
789 /* Returns the address ADDR of an object in a canonical shape (without nop
790 casts, and with type of pointer to the object). */
793 canonicalize_base_object_address (tree addr
)
799 /* The base address may be obtained by casting from integer, in that case
801 if (!POINTER_TYPE_P (TREE_TYPE (addr
)))
804 if (TREE_CODE (addr
) != ADDR_EXPR
)
807 return build_fold_addr_expr (TREE_OPERAND (addr
, 0));
810 /* Analyze the behavior of memory reference REF. There are two modes:
812 - BB analysis. In this case we simply split the address into base,
813 init and offset components, without reference to any containing loop.
814 The resulting base and offset are general expressions and they can
815 vary arbitrarily from one iteration of the containing loop to the next.
816 The step is always zero.
818 - loop analysis. In this case we analyze the reference both wrt LOOP
819 and on the basis that the reference occurs (is "used") in LOOP;
820 see the comment above analyze_scalar_evolution_in_loop for more
821 information about this distinction. The base, init, offset and
822 step fields are all invariant in LOOP.
824 Perform BB analysis if LOOP is null, or if LOOP is the function's
825 dummy outermost loop. In other cases perform loop analysis.
827 Return true if the analysis succeeded and store the results in DRB if so.
828 BB analysis can only fail for bitfield or reversed-storage accesses. */
831 dr_analyze_innermost (innermost_loop_behavior
*drb
, tree ref
,
834 poly_int64 pbitsize
, pbitpos
;
837 int punsignedp
, preversep
, pvolatilep
;
838 affine_iv base_iv
, offset_iv
;
839 tree init
, dinit
, step
;
840 bool in_loop
= (loop
&& loop
->num
);
842 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
843 fprintf (dump_file
, "analyze_innermost: ");
845 base
= get_inner_reference (ref
, &pbitsize
, &pbitpos
, &poffset
, &pmode
,
846 &punsignedp
, &preversep
, &pvolatilep
);
847 gcc_assert (base
!= NULL_TREE
);
850 if (!multiple_p (pbitpos
, BITS_PER_UNIT
, &pbytepos
))
852 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
853 fprintf (dump_file
, "failed: bit offset alignment.\n");
859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
860 fprintf (dump_file
, "failed: reverse storage order.\n");
864 /* Calculate the alignment and misalignment for the inner reference. */
865 unsigned int HOST_WIDE_INT bit_base_misalignment
;
866 unsigned int bit_base_alignment
;
867 get_object_alignment_1 (base
, &bit_base_alignment
, &bit_base_misalignment
);
869 /* There are no bitfield references remaining in BASE, so the values
870 we got back must be whole bytes. */
871 gcc_assert (bit_base_alignment
% BITS_PER_UNIT
== 0
872 && bit_base_misalignment
% BITS_PER_UNIT
== 0);
873 unsigned int base_alignment
= bit_base_alignment
/ BITS_PER_UNIT
;
874 poly_int64 base_misalignment
= bit_base_misalignment
/ BITS_PER_UNIT
;
876 if (TREE_CODE (base
) == MEM_REF
)
878 if (!integer_zerop (TREE_OPERAND (base
, 1)))
880 /* Subtract MOFF from the base and add it to POFFSET instead.
881 Adjust the misalignment to reflect the amount we subtracted. */
882 poly_offset_int moff
= mem_ref_offset (base
);
883 base_misalignment
-= moff
.force_shwi ();
884 tree mofft
= wide_int_to_tree (sizetype
, moff
);
888 poffset
= size_binop (PLUS_EXPR
, poffset
, mofft
);
890 base
= TREE_OPERAND (base
, 0);
893 base
= build_fold_addr_expr (base
);
897 if (!simple_iv (loop
, loop
, base
, &base_iv
, true))
899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
900 fprintf (dump_file
, "failed: evolution of base is not affine.\n");
907 base_iv
.step
= ssize_int (0);
908 base_iv
.no_overflow
= true;
913 offset_iv
.base
= ssize_int (0);
914 offset_iv
.step
= ssize_int (0);
920 offset_iv
.base
= poffset
;
921 offset_iv
.step
= ssize_int (0);
923 else if (!simple_iv (loop
, loop
, poffset
, &offset_iv
, true))
925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
926 fprintf (dump_file
, "failed: evolution of offset is not affine.\n");
931 init
= ssize_int (pbytepos
);
933 /* Subtract any constant component from the base and add it to INIT instead.
934 Adjust the misalignment to reflect the amount we subtracted. */
935 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
936 init
= size_binop (PLUS_EXPR
, init
, dinit
);
937 base_misalignment
-= TREE_INT_CST_LOW (dinit
);
939 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
940 init
= size_binop (PLUS_EXPR
, init
, dinit
);
942 step
= size_binop (PLUS_EXPR
,
943 fold_convert (ssizetype
, base_iv
.step
),
944 fold_convert (ssizetype
, offset_iv
.step
));
946 base
= canonicalize_base_object_address (base_iv
.base
);
948 /* See if get_pointer_alignment can guarantee a higher alignment than
949 the one we calculated above. */
950 unsigned int HOST_WIDE_INT alt_misalignment
;
951 unsigned int alt_alignment
;
952 get_pointer_alignment_1 (base
, &alt_alignment
, &alt_misalignment
);
954 /* As above, these values must be whole bytes. */
955 gcc_assert (alt_alignment
% BITS_PER_UNIT
== 0
956 && alt_misalignment
% BITS_PER_UNIT
== 0);
957 alt_alignment
/= BITS_PER_UNIT
;
958 alt_misalignment
/= BITS_PER_UNIT
;
960 if (base_alignment
< alt_alignment
)
962 base_alignment
= alt_alignment
;
963 base_misalignment
= alt_misalignment
;
966 drb
->base_address
= base
;
967 drb
->offset
= fold_convert (ssizetype
, offset_iv
.base
);
970 if (known_misalignment (base_misalignment
, base_alignment
,
971 &drb
->base_misalignment
))
972 drb
->base_alignment
= base_alignment
;
975 drb
->base_alignment
= known_alignment (base_misalignment
);
976 drb
->base_misalignment
= 0;
978 drb
->offset_alignment
= highest_pow2_factor (offset_iv
.base
);
979 drb
->step_alignment
= highest_pow2_factor (step
);
981 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
982 fprintf (dump_file
, "success.\n");
987 /* Return true if OP is a valid component reference for a DR access
988 function. This accepts a subset of what handled_component_p accepts. */
991 access_fn_component_p (tree op
)
993 switch (TREE_CODE (op
))
1001 return TREE_CODE (TREE_TYPE (TREE_OPERAND (op
, 0))) == RECORD_TYPE
;
1008 /* Determines the base object and the list of indices of memory reference
1009 DR, analyzed in LOOP and instantiated before NEST. */
1012 dr_analyze_indices (struct data_reference
*dr
, edge nest
, loop_p loop
)
1014 vec
<tree
> access_fns
= vNULL
;
1016 tree base
, off
, access_fn
;
1018 /* If analyzing a basic-block there are no indices to analyze
1019 and thus no access functions. */
1022 DR_BASE_OBJECT (dr
) = DR_REF (dr
);
1023 DR_ACCESS_FNS (dr
).create (0);
1029 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
1030 into a two element array with a constant index. The base is
1031 then just the immediate underlying object. */
1032 if (TREE_CODE (ref
) == REALPART_EXPR
)
1034 ref
= TREE_OPERAND (ref
, 0);
1035 access_fns
.safe_push (integer_zero_node
);
1037 else if (TREE_CODE (ref
) == IMAGPART_EXPR
)
1039 ref
= TREE_OPERAND (ref
, 0);
1040 access_fns
.safe_push (integer_one_node
);
1043 /* Analyze access functions of dimensions we know to be independent.
1044 The list of component references handled here should be kept in
1045 sync with access_fn_component_p. */
1046 while (handled_component_p (ref
))
1048 if (TREE_CODE (ref
) == ARRAY_REF
)
1050 op
= TREE_OPERAND (ref
, 1);
1051 access_fn
= analyze_scalar_evolution (loop
, op
);
1052 access_fn
= instantiate_scev (nest
, loop
, access_fn
);
1053 access_fns
.safe_push (access_fn
);
1055 else if (TREE_CODE (ref
) == COMPONENT_REF
1056 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref
, 0))) == RECORD_TYPE
)
1058 /* For COMPONENT_REFs of records (but not unions!) use the
1059 FIELD_DECL offset as constant access function so we can
1060 disambiguate a[i].f1 and a[i].f2. */
1061 tree off
= component_ref_field_offset (ref
);
1062 off
= size_binop (PLUS_EXPR
,
1063 size_binop (MULT_EXPR
,
1064 fold_convert (bitsizetype
, off
),
1065 bitsize_int (BITS_PER_UNIT
)),
1066 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1)));
1067 access_fns
.safe_push (off
);
1070 /* If we have an unhandled component we could not translate
1071 to an access function stop analyzing. We have determined
1072 our base object in this case. */
1075 ref
= TREE_OPERAND (ref
, 0);
1078 /* If the address operand of a MEM_REF base has an evolution in the
1079 analyzed nest, add it as an additional independent access-function. */
1080 if (TREE_CODE (ref
) == MEM_REF
)
1082 op
= TREE_OPERAND (ref
, 0);
1083 access_fn
= analyze_scalar_evolution (loop
, op
);
1084 access_fn
= instantiate_scev (nest
, loop
, access_fn
);
1085 if (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
1088 tree memoff
= TREE_OPERAND (ref
, 1);
1089 base
= initial_condition (access_fn
);
1090 orig_type
= TREE_TYPE (base
);
1091 STRIP_USELESS_TYPE_CONVERSION (base
);
1092 split_constant_offset (base
, &base
, &off
);
1093 STRIP_USELESS_TYPE_CONVERSION (base
);
1094 /* Fold the MEM_REF offset into the evolutions initial
1095 value to make more bases comparable. */
1096 if (!integer_zerop (memoff
))
1098 off
= size_binop (PLUS_EXPR
, off
,
1099 fold_convert (ssizetype
, memoff
));
1100 memoff
= build_int_cst (TREE_TYPE (memoff
), 0);
1102 /* Adjust the offset so it is a multiple of the access type
1103 size and thus we separate bases that can possibly be used
1104 to produce partial overlaps (which the access_fn machinery
1107 if (TYPE_SIZE_UNIT (TREE_TYPE (ref
))
1108 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref
))) == INTEGER_CST
1109 && !integer_zerop (TYPE_SIZE_UNIT (TREE_TYPE (ref
))))
1112 wi::to_wide (TYPE_SIZE_UNIT (TREE_TYPE (ref
))),
1115 /* If we can't compute the remainder simply force the initial
1116 condition to zero. */
1117 rem
= wi::to_wide (off
);
1118 off
= wide_int_to_tree (ssizetype
, wi::to_wide (off
) - rem
);
1119 memoff
= wide_int_to_tree (TREE_TYPE (memoff
), rem
);
1120 /* And finally replace the initial condition. */
1121 access_fn
= chrec_replace_initial_condition
1122 (access_fn
, fold_convert (orig_type
, off
));
1123 /* ??? This is still not a suitable base object for
1124 dr_may_alias_p - the base object needs to be an
1125 access that covers the object as whole. With
1126 an evolution in the pointer this cannot be
1128 As a band-aid, mark the access so we can special-case
1129 it in dr_may_alias_p. */
1131 ref
= fold_build2_loc (EXPR_LOCATION (ref
),
1132 MEM_REF
, TREE_TYPE (ref
),
1134 MR_DEPENDENCE_CLIQUE (ref
) = MR_DEPENDENCE_CLIQUE (old
);
1135 MR_DEPENDENCE_BASE (ref
) = MR_DEPENDENCE_BASE (old
);
1136 DR_UNCONSTRAINED_BASE (dr
) = true;
1137 access_fns
.safe_push (access_fn
);
1140 else if (DECL_P (ref
))
1142 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
1143 ref
= build2 (MEM_REF
, TREE_TYPE (ref
),
1144 build_fold_addr_expr (ref
),
1145 build_int_cst (reference_alias_ptr_type (ref
), 0));
1148 DR_BASE_OBJECT (dr
) = ref
;
1149 DR_ACCESS_FNS (dr
) = access_fns
;
1152 /* Extracts the alias analysis information from the memory reference DR. */
1155 dr_analyze_alias (struct data_reference
*dr
)
1157 tree ref
= DR_REF (dr
);
1158 tree base
= get_base_address (ref
), addr
;
1160 if (INDIRECT_REF_P (base
)
1161 || TREE_CODE (base
) == MEM_REF
)
1163 addr
= TREE_OPERAND (base
, 0);
1164 if (TREE_CODE (addr
) == SSA_NAME
)
1165 DR_PTR_INFO (dr
) = SSA_NAME_PTR_INFO (addr
);
1169 /* Frees data reference DR. */
1172 free_data_ref (data_reference_p dr
)
1174 DR_ACCESS_FNS (dr
).release ();
1178 /* Analyze memory reference MEMREF, which is accessed in STMT.
1179 The reference is a read if IS_READ is true, otherwise it is a write.
1180 IS_CONDITIONAL_IN_STMT indicates that the reference is conditional
1181 within STMT, i.e. that it might not occur even if STMT is executed
1182 and runs to completion.
1184 Return the data_reference description of MEMREF. NEST is the outermost
1185 loop in which the reference should be instantiated, LOOP is the loop
1186 in which the data reference should be analyzed. */
1188 struct data_reference
*
1189 create_data_ref (edge nest
, loop_p loop
, tree memref
, gimple
*stmt
,
1190 bool is_read
, bool is_conditional_in_stmt
)
1192 struct data_reference
*dr
;
1194 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1196 fprintf (dump_file
, "Creating dr for ");
1197 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1198 fprintf (dump_file
, "\n");
1201 dr
= XCNEW (struct data_reference
);
1202 DR_STMT (dr
) = stmt
;
1203 DR_REF (dr
) = memref
;
1204 DR_IS_READ (dr
) = is_read
;
1205 DR_IS_CONDITIONAL_IN_STMT (dr
) = is_conditional_in_stmt
;
1207 dr_analyze_innermost (&DR_INNERMOST (dr
), memref
,
1208 nest
!= NULL
? loop
: NULL
);
1209 dr_analyze_indices (dr
, nest
, loop
);
1210 dr_analyze_alias (dr
);
1212 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1215 fprintf (dump_file
, "\tbase_address: ");
1216 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
1217 fprintf (dump_file
, "\n\toffset from base address: ");
1218 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
1219 fprintf (dump_file
, "\n\tconstant offset from base address: ");
1220 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
1221 fprintf (dump_file
, "\n\tstep: ");
1222 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
1223 fprintf (dump_file
, "\n\tbase alignment: %d", DR_BASE_ALIGNMENT (dr
));
1224 fprintf (dump_file
, "\n\tbase misalignment: %d",
1225 DR_BASE_MISALIGNMENT (dr
));
1226 fprintf (dump_file
, "\n\toffset alignment: %d",
1227 DR_OFFSET_ALIGNMENT (dr
));
1228 fprintf (dump_file
, "\n\tstep alignment: %d", DR_STEP_ALIGNMENT (dr
));
1229 fprintf (dump_file
, "\n\tbase_object: ");
1230 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
1231 fprintf (dump_file
, "\n");
1232 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
1234 fprintf (dump_file
, "\tAccess function %d: ", i
);
1235 print_generic_stmt (dump_file
, DR_ACCESS_FN (dr
, i
), TDF_SLIM
);
1242 /* A helper function computes order between two tree epxressions T1 and T2.
1243 This is used in comparator functions sorting objects based on the order
1244 of tree expressions. The function returns -1, 0, or 1. */
1247 data_ref_compare_tree (tree t1
, tree t2
)
1250 enum tree_code code
;
1260 STRIP_USELESS_TYPE_CONVERSION (t1
);
1261 STRIP_USELESS_TYPE_CONVERSION (t2
);
1265 if (TREE_CODE (t1
) != TREE_CODE (t2
)
1266 && ! (CONVERT_EXPR_P (t1
) && CONVERT_EXPR_P (t2
)))
1267 return TREE_CODE (t1
) < TREE_CODE (t2
) ? -1 : 1;
1269 code
= TREE_CODE (t1
);
1273 return tree_int_cst_compare (t1
, t2
);
1276 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1277 return TREE_STRING_LENGTH (t1
) < TREE_STRING_LENGTH (t2
) ? -1 : 1;
1278 return memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1279 TREE_STRING_LENGTH (t1
));
1282 if (SSA_NAME_VERSION (t1
) != SSA_NAME_VERSION (t2
))
1283 return SSA_NAME_VERSION (t1
) < SSA_NAME_VERSION (t2
) ? -1 : 1;
1287 if (POLY_INT_CST_P (t1
))
1288 return compare_sizes_for_sort (wi::to_poly_widest (t1
),
1289 wi::to_poly_widest (t2
));
1291 tclass
= TREE_CODE_CLASS (code
);
1293 /* For decls, compare their UIDs. */
1294 if (tclass
== tcc_declaration
)
1296 if (DECL_UID (t1
) != DECL_UID (t2
))
1297 return DECL_UID (t1
) < DECL_UID (t2
) ? -1 : 1;
1300 /* For expressions, compare their operands recursively. */
1301 else if (IS_EXPR_CODE_CLASS (tclass
))
1303 for (i
= TREE_OPERAND_LENGTH (t1
) - 1; i
>= 0; --i
)
1305 cmp
= data_ref_compare_tree (TREE_OPERAND (t1
, i
),
1306 TREE_OPERAND (t2
, i
));
1318 /* Return TRUE it's possible to resolve data dependence DDR by runtime alias
1322 runtime_alias_check_p (ddr_p ddr
, struct loop
*loop
, bool speed_p
)
1324 if (dump_enabled_p ())
1326 dump_printf (MSG_NOTE
, "consider run-time aliasing test between ");
1327 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (DDR_A (ddr
)));
1328 dump_printf (MSG_NOTE
, " and ");
1329 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (DDR_B (ddr
)));
1330 dump_printf (MSG_NOTE
, "\n");
1335 if (dump_enabled_p ())
1336 dump_printf (MSG_MISSED_OPTIMIZATION
,
1337 "runtime alias check not supported when optimizing "
1342 /* FORNOW: We don't support versioning with outer-loop in either
1343 vectorization or loop distribution. */
1344 if (loop
!= NULL
&& loop
->inner
!= NULL
)
1346 if (dump_enabled_p ())
1347 dump_printf (MSG_MISSED_OPTIMIZATION
,
1348 "runtime alias check not supported for outer loop.\n");
1355 /* Operator == between two dr_with_seg_len objects.
1357 This equality operator is used to make sure two data refs
1358 are the same one so that we will consider to combine the
1359 aliasing checks of those two pairs of data dependent data
1363 operator == (const dr_with_seg_len
& d1
,
1364 const dr_with_seg_len
& d2
)
1366 return (operand_equal_p (DR_BASE_ADDRESS (d1
.dr
),
1367 DR_BASE_ADDRESS (d2
.dr
), 0)
1368 && data_ref_compare_tree (DR_OFFSET (d1
.dr
), DR_OFFSET (d2
.dr
)) == 0
1369 && data_ref_compare_tree (DR_INIT (d1
.dr
), DR_INIT (d2
.dr
)) == 0
1370 && data_ref_compare_tree (d1
.seg_len
, d2
.seg_len
) == 0
1371 && known_eq (d1
.access_size
, d2
.access_size
)
1372 && d1
.align
== d2
.align
);
1375 /* Comparison function for sorting objects of dr_with_seg_len_pair_t
1376 so that we can combine aliasing checks in one scan. */
1379 comp_dr_with_seg_len_pair (const void *pa_
, const void *pb_
)
1381 const dr_with_seg_len_pair_t
* pa
= (const dr_with_seg_len_pair_t
*) pa_
;
1382 const dr_with_seg_len_pair_t
* pb
= (const dr_with_seg_len_pair_t
*) pb_
;
1383 const dr_with_seg_len
&a1
= pa
->first
, &a2
= pa
->second
;
1384 const dr_with_seg_len
&b1
= pb
->first
, &b2
= pb
->second
;
1386 /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks
1387 if a and c have the same basic address snd step, and b and d have the same
1388 address and step. Therefore, if any a&c or b&d don't have the same address
1389 and step, we don't care the order of those two pairs after sorting. */
1392 if ((comp_res
= data_ref_compare_tree (DR_BASE_ADDRESS (a1
.dr
),
1393 DR_BASE_ADDRESS (b1
.dr
))) != 0)
1395 if ((comp_res
= data_ref_compare_tree (DR_BASE_ADDRESS (a2
.dr
),
1396 DR_BASE_ADDRESS (b2
.dr
))) != 0)
1398 if ((comp_res
= data_ref_compare_tree (DR_STEP (a1
.dr
),
1399 DR_STEP (b1
.dr
))) != 0)
1401 if ((comp_res
= data_ref_compare_tree (DR_STEP (a2
.dr
),
1402 DR_STEP (b2
.dr
))) != 0)
1404 if ((comp_res
= data_ref_compare_tree (DR_OFFSET (a1
.dr
),
1405 DR_OFFSET (b1
.dr
))) != 0)
1407 if ((comp_res
= data_ref_compare_tree (DR_INIT (a1
.dr
),
1408 DR_INIT (b1
.dr
))) != 0)
1410 if ((comp_res
= data_ref_compare_tree (DR_OFFSET (a2
.dr
),
1411 DR_OFFSET (b2
.dr
))) != 0)
1413 if ((comp_res
= data_ref_compare_tree (DR_INIT (a2
.dr
),
1414 DR_INIT (b2
.dr
))) != 0)
1420 /* Merge alias checks recorded in ALIAS_PAIRS and remove redundant ones.
1421 FACTOR is number of iterations that each data reference is accessed.
1423 Basically, for each pair of dependent data refs store_ptr_0 & load_ptr_0,
1424 we create an expression:
1426 ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
1427 || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
1429 for aliasing checks. However, in some cases we can decrease the number
1430 of checks by combining two checks into one. For example, suppose we have
1431 another pair of data refs store_ptr_0 & load_ptr_1, and if the following
1432 condition is satisfied:
1434 load_ptr_0 < load_ptr_1 &&
1435 load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0
1437 (this condition means, in each iteration of vectorized loop, the accessed
1438 memory of store_ptr_0 cannot be between the memory of load_ptr_0 and
1441 we then can use only the following expression to finish the alising checks
1442 between store_ptr_0 & load_ptr_0 and store_ptr_0 & load_ptr_1:
1444 ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
1445 || (load_ptr_1 + load_segment_length_1 <= store_ptr_0))
1447 Note that we only consider that load_ptr_0 and load_ptr_1 have the same
1451 prune_runtime_alias_test_list (vec
<dr_with_seg_len_pair_t
> *alias_pairs
,
1454 /* Sort the collected data ref pairs so that we can scan them once to
1455 combine all possible aliasing checks. */
1456 alias_pairs
->qsort (comp_dr_with_seg_len_pair
);
1458 /* Scan the sorted dr pairs and check if we can combine alias checks
1459 of two neighboring dr pairs. */
1460 for (size_t i
= 1; i
< alias_pairs
->length (); ++i
)
1462 /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2). */
1463 dr_with_seg_len
*dr_a1
= &(*alias_pairs
)[i
-1].first
,
1464 *dr_b1
= &(*alias_pairs
)[i
-1].second
,
1465 *dr_a2
= &(*alias_pairs
)[i
].first
,
1466 *dr_b2
= &(*alias_pairs
)[i
].second
;
1468 /* Remove duplicate data ref pairs. */
1469 if (*dr_a1
== *dr_a2
&& *dr_b1
== *dr_b2
)
1471 if (dump_enabled_p ())
1473 dump_printf (MSG_NOTE
, "found equal ranges ");
1474 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_a1
->dr
));
1475 dump_printf (MSG_NOTE
, ", ");
1476 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_b1
->dr
));
1477 dump_printf (MSG_NOTE
, " and ");
1478 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_a2
->dr
));
1479 dump_printf (MSG_NOTE
, ", ");
1480 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_b2
->dr
));
1481 dump_printf (MSG_NOTE
, "\n");
1483 alias_pairs
->ordered_remove (i
--);
1487 if (*dr_a1
== *dr_a2
|| *dr_b1
== *dr_b2
)
1489 /* We consider the case that DR_B1 and DR_B2 are same memrefs,
1490 and DR_A1 and DR_A2 are two consecutive memrefs. */
1491 if (*dr_a1
== *dr_a2
)
1493 std::swap (dr_a1
, dr_b1
);
1494 std::swap (dr_a2
, dr_b2
);
1497 poly_int64 init_a1
, init_a2
;
1498 /* Only consider cases in which the distance between the initial
1499 DR_A1 and the initial DR_A2 is known at compile time. */
1500 if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1
->dr
),
1501 DR_BASE_ADDRESS (dr_a2
->dr
), 0)
1502 || !operand_equal_p (DR_OFFSET (dr_a1
->dr
),
1503 DR_OFFSET (dr_a2
->dr
), 0)
1504 || !poly_int_tree_p (DR_INIT (dr_a1
->dr
), &init_a1
)
1505 || !poly_int_tree_p (DR_INIT (dr_a2
->dr
), &init_a2
))
1508 /* Don't combine if we can't tell which one comes first. */
1509 if (!ordered_p (init_a1
, init_a2
))
1512 /* Make sure dr_a1 starts left of dr_a2. */
1513 if (maybe_gt (init_a1
, init_a2
))
1515 std::swap (*dr_a1
, *dr_a2
);
1516 std::swap (init_a1
, init_a2
);
1519 /* Work out what the segment length would be if we did combine
1522 - If DR_A1 and DR_A2 have equal lengths, that length is
1523 also the combined length.
1525 - If DR_A1 and DR_A2 both have negative "lengths", the combined
1526 length is the lower bound on those lengths.
1528 - If DR_A1 and DR_A2 both have positive lengths, the combined
1529 length is the upper bound on those lengths.
1531 Other cases are unlikely to give a useful combination.
1533 The lengths both have sizetype, so the sign is taken from
1534 the step instead. */
1535 if (!operand_equal_p (dr_a1
->seg_len
, dr_a2
->seg_len
, 0))
1537 poly_uint64 seg_len_a1
, seg_len_a2
;
1538 if (!poly_int_tree_p (dr_a1
->seg_len
, &seg_len_a1
)
1539 || !poly_int_tree_p (dr_a2
->seg_len
, &seg_len_a2
))
1542 tree indicator_a
= dr_direction_indicator (dr_a1
->dr
);
1543 if (TREE_CODE (indicator_a
) != INTEGER_CST
)
1546 tree indicator_b
= dr_direction_indicator (dr_a2
->dr
);
1547 if (TREE_CODE (indicator_b
) != INTEGER_CST
)
1550 int sign_a
= tree_int_cst_sgn (indicator_a
);
1551 int sign_b
= tree_int_cst_sgn (indicator_b
);
1553 poly_uint64 new_seg_len
;
1554 if (sign_a
<= 0 && sign_b
<= 0)
1555 new_seg_len
= lower_bound (seg_len_a1
, seg_len_a2
);
1556 else if (sign_a
>= 0 && sign_b
>= 0)
1557 new_seg_len
= upper_bound (seg_len_a1
, seg_len_a2
);
1561 dr_a1
->seg_len
= build_int_cst (TREE_TYPE (dr_a1
->seg_len
),
1563 dr_a1
->align
= MIN (dr_a1
->align
, known_alignment (new_seg_len
));
1566 /* This is always positive due to the swap above. */
1567 poly_uint64 diff
= init_a2
- init_a1
;
1569 /* The new check will start at DR_A1. Make sure that its access
1570 size encompasses the initial DR_A2. */
1571 if (maybe_lt (dr_a1
->access_size
, diff
+ dr_a2
->access_size
))
1573 dr_a1
->access_size
= upper_bound (dr_a1
->access_size
,
1574 diff
+ dr_a2
->access_size
);
1575 unsigned int new_align
= known_alignment (dr_a1
->access_size
);
1576 dr_a1
->align
= MIN (dr_a1
->align
, new_align
);
1578 if (dump_enabled_p ())
1580 dump_printf (MSG_NOTE
, "merging ranges for ");
1581 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_a1
->dr
));
1582 dump_printf (MSG_NOTE
, ", ");
1583 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_b1
->dr
));
1584 dump_printf (MSG_NOTE
, " and ");
1585 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_a2
->dr
));
1586 dump_printf (MSG_NOTE
, ", ");
1587 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_b2
->dr
));
1588 dump_printf (MSG_NOTE
, "\n");
1590 alias_pairs
->ordered_remove (i
);
1596 /* Given LOOP's two data references and segment lengths described by DR_A
1597 and DR_B, create expression checking if the two addresses ranges intersect
1598 with each other based on index of the two addresses. This can only be
1599 done if DR_A and DR_B referring to the same (array) object and the index
1600 is the only difference. For example:
1603 data-ref arr[i] arr[j]
1605 index {i_0, +, 1}_loop {j_0, +, 1}_loop
1607 The addresses and their index are like:
1609 |<- ADDR_A ->| |<- ADDR_B ->|
1610 ------------------------------------------------------->
1612 ------------------------------------------------------->
1613 i_0 ... i_0+4 j_0 ... j_0+4
1615 We can create expression based on index rather than address:
1617 (i_0 + 4 < j_0 || j_0 + 4 < i_0)
1619 Note evolution step of index needs to be considered in comparison. */
1622 create_intersect_range_checks_index (struct loop
*loop
, tree
*cond_expr
,
1623 const dr_with_seg_len
& dr_a
,
1624 const dr_with_seg_len
& dr_b
)
1626 if (integer_zerop (DR_STEP (dr_a
.dr
))
1627 || integer_zerop (DR_STEP (dr_b
.dr
))
1628 || DR_NUM_DIMENSIONS (dr_a
.dr
) != DR_NUM_DIMENSIONS (dr_b
.dr
))
1631 poly_uint64 seg_len1
, seg_len2
;
1632 if (!poly_int_tree_p (dr_a
.seg_len
, &seg_len1
)
1633 || !poly_int_tree_p (dr_b
.seg_len
, &seg_len2
))
1636 if (!tree_fits_shwi_p (DR_STEP (dr_a
.dr
)))
1639 if (!operand_equal_p (DR_BASE_OBJECT (dr_a
.dr
), DR_BASE_OBJECT (dr_b
.dr
), 0))
1642 if (!operand_equal_p (DR_STEP (dr_a
.dr
), DR_STEP (dr_b
.dr
), 0))
1645 gcc_assert (TREE_CODE (DR_STEP (dr_a
.dr
)) == INTEGER_CST
);
1647 bool neg_step
= tree_int_cst_compare (DR_STEP (dr_a
.dr
), size_zero_node
) < 0;
1648 unsigned HOST_WIDE_INT abs_step
= tree_to_shwi (DR_STEP (dr_a
.dr
));
1651 abs_step
= -abs_step
;
1652 seg_len1
= -seg_len1
;
1653 seg_len2
= -seg_len2
;
1657 /* Include the access size in the length, so that we only have one
1658 tree addition below. */
1659 seg_len1
+= dr_a
.access_size
;
1660 seg_len2
+= dr_b
.access_size
;
1663 /* Infer the number of iterations with which the memory segment is accessed
1664 by DR. In other words, alias is checked if memory segment accessed by
1665 DR_A in some iterations intersect with memory segment accessed by DR_B
1666 in the same amount iterations.
1667 Note segnment length is a linear function of number of iterations with
1668 DR_STEP as the coefficient. */
1669 poly_uint64 niter_len1
, niter_len2
;
1670 if (!can_div_trunc_p (seg_len1
+ abs_step
- 1, abs_step
, &niter_len1
)
1671 || !can_div_trunc_p (seg_len2
+ abs_step
- 1, abs_step
, &niter_len2
))
1674 poly_uint64 niter_access1
= 0, niter_access2
= 0;
1677 /* Divide each access size by the byte step, rounding up. */
1678 if (!can_div_trunc_p (dr_a
.access_size
- abs_step
- 1,
1679 abs_step
, &niter_access1
)
1680 || !can_div_trunc_p (dr_b
.access_size
+ abs_step
- 1,
1681 abs_step
, &niter_access2
))
1686 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr_a
.dr
); i
++)
1688 tree access1
= DR_ACCESS_FN (dr_a
.dr
, i
);
1689 tree access2
= DR_ACCESS_FN (dr_b
.dr
, i
);
1690 /* Two indices must be the same if they are not scev, or not scev wrto
1691 current loop being vecorized. */
1692 if (TREE_CODE (access1
) != POLYNOMIAL_CHREC
1693 || TREE_CODE (access2
) != POLYNOMIAL_CHREC
1694 || CHREC_VARIABLE (access1
) != (unsigned)loop
->num
1695 || CHREC_VARIABLE (access2
) != (unsigned)loop
->num
)
1697 if (operand_equal_p (access1
, access2
, 0))
1702 /* The two indices must have the same step. */
1703 if (!operand_equal_p (CHREC_RIGHT (access1
), CHREC_RIGHT (access2
), 0))
1706 tree idx_step
= CHREC_RIGHT (access1
);
1707 /* Index must have const step, otherwise DR_STEP won't be constant. */
1708 gcc_assert (TREE_CODE (idx_step
) == INTEGER_CST
);
1709 /* Index must evaluate in the same direction as DR. */
1710 gcc_assert (!neg_step
|| tree_int_cst_sign_bit (idx_step
) == 1);
1712 tree min1
= CHREC_LEFT (access1
);
1713 tree min2
= CHREC_LEFT (access2
);
1714 if (!types_compatible_p (TREE_TYPE (min1
), TREE_TYPE (min2
)))
1717 /* Ideally, alias can be checked against loop's control IV, but we
1718 need to prove linear mapping between control IV and reference
1719 index. Although that should be true, we check against (array)
1720 index of data reference. Like segment length, index length is
1721 linear function of the number of iterations with index_step as
1722 the coefficient, i.e, niter_len * idx_step. */
1723 tree idx_len1
= fold_build2 (MULT_EXPR
, TREE_TYPE (min1
), idx_step
,
1724 build_int_cst (TREE_TYPE (min1
),
1726 tree idx_len2
= fold_build2 (MULT_EXPR
, TREE_TYPE (min2
), idx_step
,
1727 build_int_cst (TREE_TYPE (min2
),
1729 tree max1
= fold_build2 (PLUS_EXPR
, TREE_TYPE (min1
), min1
, idx_len1
);
1730 tree max2
= fold_build2 (PLUS_EXPR
, TREE_TYPE (min2
), min2
, idx_len2
);
1731 /* Adjust ranges for negative step. */
1734 /* IDX_LEN1 and IDX_LEN2 are negative in this case. */
1735 std::swap (min1
, max1
);
1736 std::swap (min2
, max2
);
1738 /* As with the lengths just calculated, we've measured the access
1739 sizes in iterations, so multiply them by the index step. */
1741 = fold_build2 (MULT_EXPR
, TREE_TYPE (min1
), idx_step
,
1742 build_int_cst (TREE_TYPE (min1
), niter_access1
));
1744 = fold_build2 (MULT_EXPR
, TREE_TYPE (min2
), idx_step
,
1745 build_int_cst (TREE_TYPE (min2
), niter_access2
));
1747 /* MINUS_EXPR because the above values are negative. */
1748 max1
= fold_build2 (MINUS_EXPR
, TREE_TYPE (max1
), max1
, idx_access1
);
1749 max2
= fold_build2 (MINUS_EXPR
, TREE_TYPE (max2
), max2
, idx_access2
);
1752 = fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1753 fold_build2 (LE_EXPR
, boolean_type_node
, max1
, min2
),
1754 fold_build2 (LE_EXPR
, boolean_type_node
, max2
, min1
));
1756 *cond_expr
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1757 *cond_expr
, part_cond_expr
);
1759 *cond_expr
= part_cond_expr
;
1764 /* If ALIGN is nonzero, set up *SEQ_MIN_OUT and *SEQ_MAX_OUT so that for
1765 every address ADDR accessed by D:
1767 *SEQ_MIN_OUT <= ADDR (== ADDR & -ALIGN) <= *SEQ_MAX_OUT
1769 In this case, every element accessed by D is aligned to at least
1772 If ALIGN is zero then instead set *SEG_MAX_OUT so that:
1774 *SEQ_MIN_OUT <= ADDR < *SEQ_MAX_OUT. */
1777 get_segment_min_max (const dr_with_seg_len
&d
, tree
*seg_min_out
,
1778 tree
*seg_max_out
, HOST_WIDE_INT align
)
1780 /* Each access has the following pattern:
1783 <--- A: -ve step --->
1784 +-----+-------+-----+-------+-----+
1785 | n-1 | ,.... | 0 | ..... | n-1 |
1786 +-----+-------+-----+-------+-----+
1787 <--- B: +ve step --->
1792 where "n" is the number of scalar iterations covered by the segment.
1793 (This should be VF for a particular pair if we know that both steps
1794 are the same, otherwise it will be the full number of scalar loop
1797 A is the range of bytes accessed when the step is negative,
1798 B is the range when the step is positive.
1800 If the access size is "access_size" bytes, the lowest addressed byte is:
1802 base + (step < 0 ? seg_len : 0) [LB]
1804 and the highest addressed byte is always below:
1806 base + (step < 0 ? 0 : seg_len) + access_size [UB]
1812 If ALIGN is nonzero, all three values are aligned to at least ALIGN
1815 LB <= ADDR <= UB - ALIGN
1817 where "- ALIGN" folds naturally with the "+ access_size" and often
1820 We don't try to simplify LB and UB beyond this (e.g. by using
1821 MIN and MAX based on whether seg_len rather than the stride is
1822 negative) because it is possible for the absolute size of the
1823 segment to overflow the range of a ssize_t.
1825 Keeping the pointer_plus outside of the cond_expr should allow
1826 the cond_exprs to be shared with other alias checks. */
1827 tree indicator
= dr_direction_indicator (d
.dr
);
1828 tree neg_step
= fold_build2 (LT_EXPR
, boolean_type_node
,
1829 fold_convert (ssizetype
, indicator
),
1831 tree addr_base
= fold_build_pointer_plus (DR_BASE_ADDRESS (d
.dr
),
1833 addr_base
= fold_build_pointer_plus (addr_base
, DR_INIT (d
.dr
));
1835 = fold_convert (sizetype
, rewrite_to_non_trapping_overflow (d
.seg_len
));
1837 tree min_reach
= fold_build3 (COND_EXPR
, sizetype
, neg_step
,
1838 seg_len
, size_zero_node
);
1839 tree max_reach
= fold_build3 (COND_EXPR
, sizetype
, neg_step
,
1840 size_zero_node
, seg_len
);
1841 max_reach
= fold_build2 (PLUS_EXPR
, sizetype
, max_reach
,
1842 size_int (d
.access_size
- align
));
1844 *seg_min_out
= fold_build_pointer_plus (addr_base
, min_reach
);
1845 *seg_max_out
= fold_build_pointer_plus (addr_base
, max_reach
);
1848 /* Given two data references and segment lengths described by DR_A and DR_B,
1849 create expression checking if the two addresses ranges intersect with
1852 ((DR_A_addr_0 + DR_A_segment_length_0) <= DR_B_addr_0)
1853 || (DR_B_addr_0 + DER_B_segment_length_0) <= DR_A_addr_0)) */
1856 create_intersect_range_checks (struct loop
*loop
, tree
*cond_expr
,
1857 const dr_with_seg_len
& dr_a
,
1858 const dr_with_seg_len
& dr_b
)
1860 *cond_expr
= NULL_TREE
;
1861 if (create_intersect_range_checks_index (loop
, cond_expr
, dr_a
, dr_b
))
1864 unsigned HOST_WIDE_INT min_align
;
1866 if (TREE_CODE (DR_STEP (dr_a
.dr
)) == INTEGER_CST
1867 && TREE_CODE (DR_STEP (dr_b
.dr
)) == INTEGER_CST
)
1869 /* In this case adding access_size to seg_len is likely to give
1870 a simple X * step, where X is either the number of scalar
1871 iterations or the vectorization factor. We're better off
1872 keeping that, rather than subtracting an alignment from it.
1874 In this case the maximum values are exclusive and so there is
1875 no alias if the maximum of one segment equals the minimum
1882 /* Calculate the minimum alignment shared by all four pointers,
1883 then arrange for this alignment to be subtracted from the
1884 exclusive maximum values to get inclusive maximum values.
1885 This "- min_align" is cumulative with a "+ access_size"
1886 in the calculation of the maximum values. In the best
1887 (and common) case, the two cancel each other out, leaving
1888 us with an inclusive bound based only on seg_len. In the
1889 worst case we're simply adding a smaller number than before.
1891 Because the maximum values are inclusive, there is an alias
1892 if the maximum value of one segment is equal to the minimum
1893 value of the other. */
1894 min_align
= MIN (dr_a
.align
, dr_b
.align
);
1898 tree seg_a_min
, seg_a_max
, seg_b_min
, seg_b_max
;
1899 get_segment_min_max (dr_a
, &seg_a_min
, &seg_a_max
, min_align
);
1900 get_segment_min_max (dr_b
, &seg_b_min
, &seg_b_max
, min_align
);
1903 = fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1904 fold_build2 (cmp_code
, boolean_type_node
, seg_a_max
, seg_b_min
),
1905 fold_build2 (cmp_code
, boolean_type_node
, seg_b_max
, seg_a_min
));
1908 /* Create a conditional expression that represents the run-time checks for
1909 overlapping of address ranges represented by a list of data references
1910 pairs passed in ALIAS_PAIRS. Data references are in LOOP. The returned
1911 COND_EXPR is the conditional expression to be used in the if statement
1912 that controls which version of the loop gets executed at runtime. */
1915 create_runtime_alias_checks (struct loop
*loop
,
1916 vec
<dr_with_seg_len_pair_t
> *alias_pairs
,
1919 tree part_cond_expr
;
1921 for (size_t i
= 0, s
= alias_pairs
->length (); i
< s
; ++i
)
1923 const dr_with_seg_len
& dr_a
= (*alias_pairs
)[i
].first
;
1924 const dr_with_seg_len
& dr_b
= (*alias_pairs
)[i
].second
;
1926 if (dump_enabled_p ())
1928 dump_printf (MSG_NOTE
, "create runtime check for data references ");
1929 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_a
.dr
));
1930 dump_printf (MSG_NOTE
, " and ");
1931 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr_b
.dr
));
1932 dump_printf (MSG_NOTE
, "\n");
1935 /* Create condition expression for each pair data references. */
1936 create_intersect_range_checks (loop
, &part_cond_expr
, dr_a
, dr_b
);
1938 *cond_expr
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1939 *cond_expr
, part_cond_expr
);
1941 *cond_expr
= part_cond_expr
;
1945 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1948 dr_equal_offsets_p1 (tree offset1
, tree offset2
)
1952 STRIP_NOPS (offset1
);
1953 STRIP_NOPS (offset2
);
1955 if (offset1
== offset2
)
1958 if (TREE_CODE (offset1
) != TREE_CODE (offset2
)
1959 || (!BINARY_CLASS_P (offset1
) && !UNARY_CLASS_P (offset1
)))
1962 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 0),
1963 TREE_OPERAND (offset2
, 0));
1965 if (!res
|| !BINARY_CLASS_P (offset1
))
1968 res
= dr_equal_offsets_p1 (TREE_OPERAND (offset1
, 1),
1969 TREE_OPERAND (offset2
, 1));
1974 /* Check if DRA and DRB have equal offsets. */
1976 dr_equal_offsets_p (struct data_reference
*dra
,
1977 struct data_reference
*drb
)
1979 tree offset1
, offset2
;
1981 offset1
= DR_OFFSET (dra
);
1982 offset2
= DR_OFFSET (drb
);
1984 return dr_equal_offsets_p1 (offset1
, offset2
);
1987 /* Returns true if FNA == FNB. */
1990 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
1992 unsigned i
, n
= fna
.length ();
1994 if (n
!= fnb
.length ())
1997 for (i
= 0; i
< n
; i
++)
1998 if (!operand_equal_p (fna
[i
], fnb
[i
], 0))
2004 /* If all the functions in CF are the same, returns one of them,
2005 otherwise returns NULL. */
2008 common_affine_function (conflict_function
*cf
)
2013 if (!CF_NONTRIVIAL_P (cf
))
2014 return affine_fn ();
2018 for (i
= 1; i
< cf
->n
; i
++)
2019 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
2020 return affine_fn ();
2025 /* Returns the base of the affine function FN. */
2028 affine_function_base (affine_fn fn
)
2033 /* Returns true if FN is a constant. */
2036 affine_function_constant_p (affine_fn fn
)
2041 for (i
= 1; fn
.iterate (i
, &coef
); i
++)
2042 if (!integer_zerop (coef
))
2048 /* Returns true if FN is the zero constant function. */
2051 affine_function_zero_p (affine_fn fn
)
2053 return (integer_zerop (affine_function_base (fn
))
2054 && affine_function_constant_p (fn
));
2057 /* Returns a signed integer type with the largest precision from TA
2061 signed_type_for_types (tree ta
, tree tb
)
2063 if (TYPE_PRECISION (ta
) > TYPE_PRECISION (tb
))
2064 return signed_type_for (ta
);
2066 return signed_type_for (tb
);
2069 /* Applies operation OP on affine functions FNA and FNB, and returns the
2073 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
2079 if (fnb
.length () > fna
.length ())
2091 for (i
= 0; i
< n
; i
++)
2093 tree type
= signed_type_for_types (TREE_TYPE (fna
[i
]),
2094 TREE_TYPE (fnb
[i
]));
2095 ret
.quick_push (fold_build2 (op
, type
, fna
[i
], fnb
[i
]));
2098 for (; fna
.iterate (i
, &coef
); i
++)
2099 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
2100 coef
, integer_zero_node
));
2101 for (; fnb
.iterate (i
, &coef
); i
++)
2102 ret
.quick_push (fold_build2 (op
, signed_type_for (TREE_TYPE (coef
)),
2103 integer_zero_node
, coef
));
2108 /* Returns the sum of affine functions FNA and FNB. */
2111 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
2113 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
2116 /* Returns the difference of affine functions FNA and FNB. */
2119 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
2121 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
2124 /* Frees affine function FN. */
2127 affine_fn_free (affine_fn fn
)
2132 /* Determine for each subscript in the data dependence relation DDR
2136 compute_subscript_distance (struct data_dependence_relation
*ddr
)
2138 conflict_function
*cf_a
, *cf_b
;
2139 affine_fn fn_a
, fn_b
, diff
;
2141 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
2145 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2147 struct subscript
*subscript
;
2149 subscript
= DDR_SUBSCRIPT (ddr
, i
);
2150 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
2151 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
2153 fn_a
= common_affine_function (cf_a
);
2154 fn_b
= common_affine_function (cf_b
);
2155 if (!fn_a
.exists () || !fn_b
.exists ())
2157 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2160 diff
= affine_fn_minus (fn_a
, fn_b
);
2162 if (affine_function_constant_p (diff
))
2163 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
2165 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2167 affine_fn_free (diff
);
2172 /* Returns the conflict function for "unknown". */
2174 static conflict_function
*
2175 conflict_fn_not_known (void)
2177 conflict_function
*fn
= XCNEW (conflict_function
);
2183 /* Returns the conflict function for "independent". */
2185 static conflict_function
*
2186 conflict_fn_no_dependence (void)
2188 conflict_function
*fn
= XCNEW (conflict_function
);
2189 fn
->n
= NO_DEPENDENCE
;
2194 /* Returns true if the address of OBJ is invariant in LOOP. */
2197 object_address_invariant_in_loop_p (const struct loop
*loop
, const_tree obj
)
2199 while (handled_component_p (obj
))
2201 if (TREE_CODE (obj
) == ARRAY_REF
)
2203 for (int i
= 1; i
< 4; ++i
)
2204 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, i
),
2208 else if (TREE_CODE (obj
) == COMPONENT_REF
)
2210 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 2),
2214 obj
= TREE_OPERAND (obj
, 0);
2217 if (!INDIRECT_REF_P (obj
)
2218 && TREE_CODE (obj
) != MEM_REF
)
2221 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj
, 0),
2225 /* Returns false if we can prove that data references A and B do not alias,
2226 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
2230 dr_may_alias_p (const struct data_reference
*a
, const struct data_reference
*b
,
2233 tree addr_a
= DR_BASE_OBJECT (a
);
2234 tree addr_b
= DR_BASE_OBJECT (b
);
2236 /* If we are not processing a loop nest but scalar code we
2237 do not need to care about possible cross-iteration dependences
2238 and thus can process the full original reference. Do so,
2239 similar to how loop invariant motion applies extra offset-based
2243 aff_tree off1
, off2
;
2244 poly_widest_int size1
, size2
;
2245 get_inner_reference_aff (DR_REF (a
), &off1
, &size1
);
2246 get_inner_reference_aff (DR_REF (b
), &off2
, &size2
);
2247 aff_combination_scale (&off1
, -1);
2248 aff_combination_add (&off2
, &off1
);
2249 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
2253 if ((TREE_CODE (addr_a
) == MEM_REF
|| TREE_CODE (addr_a
) == TARGET_MEM_REF
)
2254 && (TREE_CODE (addr_b
) == MEM_REF
|| TREE_CODE (addr_b
) == TARGET_MEM_REF
)
2255 && MR_DEPENDENCE_CLIQUE (addr_a
) == MR_DEPENDENCE_CLIQUE (addr_b
)
2256 && MR_DEPENDENCE_BASE (addr_a
) != MR_DEPENDENCE_BASE (addr_b
))
2259 /* If we had an evolution in a pointer-based MEM_REF BASE_OBJECT we
2260 do not know the size of the base-object. So we cannot do any
2261 offset/overlap based analysis but have to rely on points-to
2262 information only. */
2263 if (TREE_CODE (addr_a
) == MEM_REF
2264 && (DR_UNCONSTRAINED_BASE (a
)
2265 || TREE_CODE (TREE_OPERAND (addr_a
, 0)) == SSA_NAME
))
2267 /* For true dependences we can apply TBAA. */
2268 if (flag_strict_aliasing
2269 && DR_IS_WRITE (a
) && DR_IS_READ (b
)
2270 && !alias_sets_conflict_p (get_alias_set (DR_REF (a
)),
2271 get_alias_set (DR_REF (b
))))
2273 if (TREE_CODE (addr_b
) == MEM_REF
)
2274 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
2275 TREE_OPERAND (addr_b
, 0));
2277 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
2278 build_fold_addr_expr (addr_b
));
2280 else if (TREE_CODE (addr_b
) == MEM_REF
2281 && (DR_UNCONSTRAINED_BASE (b
)
2282 || TREE_CODE (TREE_OPERAND (addr_b
, 0)) == SSA_NAME
))
2284 /* For true dependences we can apply TBAA. */
2285 if (flag_strict_aliasing
2286 && DR_IS_WRITE (a
) && DR_IS_READ (b
)
2287 && !alias_sets_conflict_p (get_alias_set (DR_REF (a
)),
2288 get_alias_set (DR_REF (b
))))
2290 if (TREE_CODE (addr_a
) == MEM_REF
)
2291 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a
, 0),
2292 TREE_OPERAND (addr_b
, 0));
2294 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a
),
2295 TREE_OPERAND (addr_b
, 0));
2298 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
2299 that is being subsetted in the loop nest. */
2300 if (DR_IS_WRITE (a
) && DR_IS_WRITE (b
))
2301 return refs_output_dependent_p (addr_a
, addr_b
);
2302 else if (DR_IS_READ (a
) && DR_IS_WRITE (b
))
2303 return refs_anti_dependent_p (addr_a
, addr_b
);
2304 return refs_may_alias_p (addr_a
, addr_b
);
2307 /* REF_A and REF_B both satisfy access_fn_component_p. Return true
2308 if it is meaningful to compare their associated access functions
2309 when checking for dependencies. */
2312 access_fn_components_comparable_p (tree ref_a
, tree ref_b
)
2314 /* Allow pairs of component refs from the following sets:
2316 { REALPART_EXPR, IMAGPART_EXPR }
2319 tree_code code_a
= TREE_CODE (ref_a
);
2320 tree_code code_b
= TREE_CODE (ref_b
);
2321 if (code_a
== IMAGPART_EXPR
)
2322 code_a
= REALPART_EXPR
;
2323 if (code_b
== IMAGPART_EXPR
)
2324 code_b
= REALPART_EXPR
;
2325 if (code_a
!= code_b
)
2328 if (TREE_CODE (ref_a
) == COMPONENT_REF
)
2329 /* ??? We cannot simply use the type of operand #0 of the refs here as
2330 the Fortran compiler smuggles type punning into COMPONENT_REFs.
2331 Use the DECL_CONTEXT of the FIELD_DECLs instead. */
2332 return (DECL_CONTEXT (TREE_OPERAND (ref_a
, 1))
2333 == DECL_CONTEXT (TREE_OPERAND (ref_b
, 1)));
2335 return types_compatible_p (TREE_TYPE (TREE_OPERAND (ref_a
, 0)),
2336 TREE_TYPE (TREE_OPERAND (ref_b
, 0)));
2339 /* Initialize a data dependence relation between data accesses A and
2340 B. NB_LOOPS is the number of loops surrounding the references: the
2341 size of the classic distance/direction vectors. */
2343 struct data_dependence_relation
*
2344 initialize_data_dependence_relation (struct data_reference
*a
,
2345 struct data_reference
*b
,
2346 vec
<loop_p
> loop_nest
)
2348 struct data_dependence_relation
*res
;
2351 res
= XCNEW (struct data_dependence_relation
);
2354 DDR_LOOP_NEST (res
).create (0);
2355 DDR_SUBSCRIPTS (res
).create (0);
2356 DDR_DIR_VECTS (res
).create (0);
2357 DDR_DIST_VECTS (res
).create (0);
2359 if (a
== NULL
|| b
== NULL
)
2361 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2365 /* If the data references do not alias, then they are independent. */
2366 if (!dr_may_alias_p (a
, b
, loop_nest
.exists ()))
2368 DDR_ARE_DEPENDENT (res
) = chrec_known
;
2372 unsigned int num_dimensions_a
= DR_NUM_DIMENSIONS (a
);
2373 unsigned int num_dimensions_b
= DR_NUM_DIMENSIONS (b
);
2374 if (num_dimensions_a
== 0 || num_dimensions_b
== 0)
2376 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2380 /* For unconstrained bases, the root (highest-indexed) subscript
2381 describes a variation in the base of the original DR_REF rather
2382 than a component access. We have no type that accurately describes
2383 the new DR_BASE_OBJECT (whose TREE_TYPE describes the type *after*
2384 applying this subscript) so limit the search to the last real
2390 f (int a[][8], int b[][8])
2392 for (int i = 0; i < 8; ++i)
2393 a[i * 2][0] = b[i][0];
2396 the a and b accesses have a single ARRAY_REF component reference [0]
2397 but have two subscripts. */
2398 if (DR_UNCONSTRAINED_BASE (a
))
2399 num_dimensions_a
-= 1;
2400 if (DR_UNCONSTRAINED_BASE (b
))
2401 num_dimensions_b
-= 1;
2403 /* These structures describe sequences of component references in
2404 DR_REF (A) and DR_REF (B). Each component reference is tied to a
2405 specific access function. */
2407 /* The sequence starts at DR_ACCESS_FN (A, START_A) of A and
2408 DR_ACCESS_FN (B, START_B) of B (inclusive) and extends to higher
2409 indices. In C notation, these are the indices of the rightmost
2410 component references; e.g. for a sequence .b.c.d, the start
2412 unsigned int start_a
;
2413 unsigned int start_b
;
2415 /* The sequence contains LENGTH consecutive access functions from
2417 unsigned int length
;
2419 /* The enclosing objects for the A and B sequences respectively,
2420 i.e. the objects to which DR_ACCESS_FN (A, START_A + LENGTH - 1)
2421 and DR_ACCESS_FN (B, START_B + LENGTH - 1) are applied. */
2424 } full_seq
= {}, struct_seq
= {};
2426 /* Before each iteration of the loop:
2428 - REF_A is what you get after applying DR_ACCESS_FN (A, INDEX_A) and
2429 - REF_B is what you get after applying DR_ACCESS_FN (B, INDEX_B). */
2430 unsigned int index_a
= 0;
2431 unsigned int index_b
= 0;
2432 tree ref_a
= DR_REF (a
);
2433 tree ref_b
= DR_REF (b
);
2435 /* Now walk the component references from the final DR_REFs back up to
2436 the enclosing base objects. Each component reference corresponds
2437 to one access function in the DR, with access function 0 being for
2438 the final DR_REF and the highest-indexed access function being the
2439 one that is applied to the base of the DR.
2441 Look for a sequence of component references whose access functions
2442 are comparable (see access_fn_components_comparable_p). If more
2443 than one such sequence exists, pick the one nearest the base
2444 (which is the leftmost sequence in C notation). Store this sequence
2447 For example, if we have:
2449 struct foo { struct bar s; ... } (*a)[10], (*b)[10];
2452 B: __real b[0][i].s.e[i].f
2454 (where d is the same type as the real component of f) then the access
2461 B: __real .f [i] .e .s [i]
2463 The A0/B2 column isn't comparable, since .d is a COMPONENT_REF
2464 and [i] is an ARRAY_REF. However, the A1/B3 column contains two
2465 COMPONENT_REF accesses for struct bar, so is comparable. Likewise
2466 the A2/B4 column contains two COMPONENT_REF accesses for struct foo,
2467 so is comparable. The A3/B5 column contains two ARRAY_REFs that
2468 index foo[10] arrays, so is again comparable. The sequence is
2471 A: [1, 3] (i.e. [i].s.c)
2472 B: [3, 5] (i.e. [i].s.e)
2474 Also look for sequences of component references whose access
2475 functions are comparable and whose enclosing objects have the same
2476 RECORD_TYPE. Store this sequence in STRUCT_SEQ. In the above
2477 example, STRUCT_SEQ would be:
2479 A: [1, 2] (i.e. s.c)
2480 B: [3, 4] (i.e. s.e) */
2481 while (index_a
< num_dimensions_a
&& index_b
< num_dimensions_b
)
2483 /* REF_A and REF_B must be one of the component access types
2484 allowed by dr_analyze_indices. */
2485 gcc_checking_assert (access_fn_component_p (ref_a
));
2486 gcc_checking_assert (access_fn_component_p (ref_b
));
2488 /* Get the immediately-enclosing objects for REF_A and REF_B,
2489 i.e. the references *before* applying DR_ACCESS_FN (A, INDEX_A)
2490 and DR_ACCESS_FN (B, INDEX_B). */
2491 tree object_a
= TREE_OPERAND (ref_a
, 0);
2492 tree object_b
= TREE_OPERAND (ref_b
, 0);
2494 tree type_a
= TREE_TYPE (object_a
);
2495 tree type_b
= TREE_TYPE (object_b
);
2496 if (access_fn_components_comparable_p (ref_a
, ref_b
))
2498 /* This pair of component accesses is comparable for dependence
2499 analysis, so we can include DR_ACCESS_FN (A, INDEX_A) and
2500 DR_ACCESS_FN (B, INDEX_B) in the sequence. */
2501 if (full_seq
.start_a
+ full_seq
.length
!= index_a
2502 || full_seq
.start_b
+ full_seq
.length
!= index_b
)
2504 /* The accesses don't extend the current sequence,
2505 so start a new one here. */
2506 full_seq
.start_a
= index_a
;
2507 full_seq
.start_b
= index_b
;
2508 full_seq
.length
= 0;
2511 /* Add this pair of references to the sequence. */
2512 full_seq
.length
+= 1;
2513 full_seq
.object_a
= object_a
;
2514 full_seq
.object_b
= object_b
;
2516 /* If the enclosing objects are structures (and thus have the
2517 same RECORD_TYPE), record the new sequence in STRUCT_SEQ. */
2518 if (TREE_CODE (type_a
) == RECORD_TYPE
)
2519 struct_seq
= full_seq
;
2521 /* Move to the next containing reference for both A and B. */
2529 /* Try to approach equal type sizes. */
2530 if (!COMPLETE_TYPE_P (type_a
)
2531 || !COMPLETE_TYPE_P (type_b
)
2532 || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_a
))
2533 || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_b
)))
2536 unsigned HOST_WIDE_INT size_a
= tree_to_uhwi (TYPE_SIZE_UNIT (type_a
));
2537 unsigned HOST_WIDE_INT size_b
= tree_to_uhwi (TYPE_SIZE_UNIT (type_b
));
2538 if (size_a
<= size_b
)
2543 if (size_b
<= size_a
)
2550 /* See whether FULL_SEQ ends at the base and whether the two bases
2551 are equal. We do not care about TBAA or alignment info so we can
2552 use OEP_ADDRESS_OF to avoid false negatives. */
2553 tree base_a
= DR_BASE_OBJECT (a
);
2554 tree base_b
= DR_BASE_OBJECT (b
);
2555 bool same_base_p
= (full_seq
.start_a
+ full_seq
.length
== num_dimensions_a
2556 && full_seq
.start_b
+ full_seq
.length
== num_dimensions_b
2557 && DR_UNCONSTRAINED_BASE (a
) == DR_UNCONSTRAINED_BASE (b
)
2558 && operand_equal_p (base_a
, base_b
, OEP_ADDRESS_OF
)
2559 && types_compatible_p (TREE_TYPE (base_a
),
2561 && (!loop_nest
.exists ()
2562 || (object_address_invariant_in_loop_p
2563 (loop_nest
[0], base_a
))));
2565 /* If the bases are the same, we can include the base variation too.
2566 E.g. the b accesses in:
2568 for (int i = 0; i < n; ++i)
2569 b[i + 4][0] = b[i][0];
2571 have a definite dependence distance of 4, while for:
2573 for (int i = 0; i < n; ++i)
2574 a[i + 4][0] = b[i][0];
2576 the dependence distance depends on the gap between a and b.
2578 If the bases are different then we can only rely on the sequence
2579 rooted at a structure access, since arrays are allowed to overlap
2580 arbitrarily and change shape arbitrarily. E.g. we treat this as
2585 ((int (*)[4][3]) &a[1])[i][0] += ((int (*)[4][3]) &a[2])[i][0];
2587 where two lvalues with the same int[4][3] type overlap, and where
2588 both lvalues are distinct from the object's declared type. */
2591 if (DR_UNCONSTRAINED_BASE (a
))
2592 full_seq
.length
+= 1;
2595 full_seq
= struct_seq
;
2597 /* Punt if we didn't find a suitable sequence. */
2598 if (full_seq
.length
== 0)
2600 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2606 /* Partial overlap is possible for different bases when strict aliasing
2607 is not in effect. It's also possible if either base involves a union
2610 struct s1 { int a[2]; };
2611 struct s2 { struct s1 b; int c; };
2612 struct s3 { int d; struct s1 e; };
2613 union u { struct s2 f; struct s3 g; } *p, *q;
2615 the s1 at "p->f.b" (base "p->f") partially overlaps the s1 at
2616 "p->g.e" (base "p->g") and might partially overlap the s1 at
2617 "q->g.e" (base "q->g"). */
2618 if (!flag_strict_aliasing
2619 || ref_contains_union_access_p (full_seq
.object_a
)
2620 || ref_contains_union_access_p (full_seq
.object_b
))
2622 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2626 DDR_COULD_BE_INDEPENDENT_P (res
) = true;
2627 if (!loop_nest
.exists ()
2628 || (object_address_invariant_in_loop_p (loop_nest
[0],
2630 && object_address_invariant_in_loop_p (loop_nest
[0],
2631 full_seq
.object_b
)))
2633 DDR_OBJECT_A (res
) = full_seq
.object_a
;
2634 DDR_OBJECT_B (res
) = full_seq
.object_b
;
2638 DDR_AFFINE_P (res
) = true;
2639 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
2640 DDR_SUBSCRIPTS (res
).create (full_seq
.length
);
2641 DDR_LOOP_NEST (res
) = loop_nest
;
2642 DDR_INNER_LOOP (res
) = 0;
2643 DDR_SELF_REFERENCE (res
) = false;
2645 for (i
= 0; i
< full_seq
.length
; ++i
)
2647 struct subscript
*subscript
;
2649 subscript
= XNEW (struct subscript
);
2650 SUB_ACCESS_FN (subscript
, 0) = DR_ACCESS_FN (a
, full_seq
.start_a
+ i
);
2651 SUB_ACCESS_FN (subscript
, 1) = DR_ACCESS_FN (b
, full_seq
.start_b
+ i
);
2652 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
2653 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
2654 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
2655 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2656 DDR_SUBSCRIPTS (res
).safe_push (subscript
);
2662 /* Frees memory used by the conflict function F. */
2665 free_conflict_function (conflict_function
*f
)
2669 if (CF_NONTRIVIAL_P (f
))
2671 for (i
= 0; i
< f
->n
; i
++)
2672 affine_fn_free (f
->fns
[i
]);
2677 /* Frees memory used by SUBSCRIPTS. */
2680 free_subscripts (vec
<subscript_p
> subscripts
)
2685 FOR_EACH_VEC_ELT (subscripts
, i
, s
)
2687 free_conflict_function (s
->conflicting_iterations_in_a
);
2688 free_conflict_function (s
->conflicting_iterations_in_b
);
2691 subscripts
.release ();
2694 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2698 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
2701 DDR_ARE_DEPENDENT (ddr
) = chrec
;
2702 free_subscripts (DDR_SUBSCRIPTS (ddr
));
2703 DDR_SUBSCRIPTS (ddr
).create (0);
2706 /* The dependence relation DDR cannot be represented by a distance
2710 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
2712 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2713 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
2715 DDR_AFFINE_P (ddr
) = false;
2720 /* This section contains the classic Banerjee tests. */
2722 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2723 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2726 ziv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
2728 return (evolution_function_is_constant_p (chrec_a
)
2729 && evolution_function_is_constant_p (chrec_b
));
2732 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2733 variable, i.e., if the SIV (Single Index Variable) test is true. */
2736 siv_subscript_p (const_tree chrec_a
, const_tree chrec_b
)
2738 if ((evolution_function_is_constant_p (chrec_a
)
2739 && evolution_function_is_univariate_p (chrec_b
))
2740 || (evolution_function_is_constant_p (chrec_b
)
2741 && evolution_function_is_univariate_p (chrec_a
)))
2744 if (evolution_function_is_univariate_p (chrec_a
)
2745 && evolution_function_is_univariate_p (chrec_b
))
2747 switch (TREE_CODE (chrec_a
))
2749 case POLYNOMIAL_CHREC
:
2750 switch (TREE_CODE (chrec_b
))
2752 case POLYNOMIAL_CHREC
:
2753 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
2769 /* Creates a conflict function with N dimensions. The affine functions
2770 in each dimension follow. */
2772 static conflict_function
*
2773 conflict_fn (unsigned n
, ...)
2776 conflict_function
*ret
= XCNEW (conflict_function
);
2779 gcc_assert (n
> 0 && n
<= MAX_DIM
);
2783 for (i
= 0; i
< n
; i
++)
2784 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
2790 /* Returns constant affine function with value CST. */
2793 affine_fn_cst (tree cst
)
2797 fn
.quick_push (cst
);
2801 /* Returns affine function with single variable, CST + COEF * x_DIM. */
2804 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
2807 fn
.create (dim
+ 1);
2810 gcc_assert (dim
> 0);
2811 fn
.quick_push (cst
);
2812 for (i
= 1; i
< dim
; i
++)
2813 fn
.quick_push (integer_zero_node
);
2814 fn
.quick_push (coef
);
2818 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2819 *OVERLAPS_B are initialized to the functions that describe the
2820 relation between the elements accessed twice by CHREC_A and
2821 CHREC_B. For k >= 0, the following property is verified:
2823 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2826 analyze_ziv_subscript (tree chrec_a
,
2828 conflict_function
**overlaps_a
,
2829 conflict_function
**overlaps_b
,
2830 tree
*last_conflicts
)
2832 tree type
, difference
;
2833 dependence_stats
.num_ziv
++;
2835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2836 fprintf (dump_file
, "(analyze_ziv_subscript \n");
2838 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2839 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2840 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2841 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
2843 switch (TREE_CODE (difference
))
2846 if (integer_zerop (difference
))
2848 /* The difference is equal to zero: the accessed index
2849 overlaps for each iteration in the loop. */
2850 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2851 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2852 *last_conflicts
= chrec_dont_know
;
2853 dependence_stats
.num_ziv_dependent
++;
2857 /* The accesses do not overlap. */
2858 *overlaps_a
= conflict_fn_no_dependence ();
2859 *overlaps_b
= conflict_fn_no_dependence ();
2860 *last_conflicts
= integer_zero_node
;
2861 dependence_stats
.num_ziv_independent
++;
2866 /* We're not sure whether the indexes overlap. For the moment,
2867 conservatively answer "don't know". */
2868 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2869 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
2871 *overlaps_a
= conflict_fn_not_known ();
2872 *overlaps_b
= conflict_fn_not_known ();
2873 *last_conflicts
= chrec_dont_know
;
2874 dependence_stats
.num_ziv_unimplemented
++;
2878 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2879 fprintf (dump_file
, ")\n");
2882 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
2883 and only if it fits to the int type. If this is not the case, or the
2884 bound on the number of iterations of LOOP could not be derived, returns
2888 max_stmt_executions_tree (struct loop
*loop
)
2892 if (!max_stmt_executions (loop
, &nit
))
2893 return chrec_dont_know
;
2895 if (!wi::fits_to_tree_p (nit
, unsigned_type_node
))
2896 return chrec_dont_know
;
2898 return wide_int_to_tree (unsigned_type_node
, nit
);
2901 /* Determine whether the CHREC is always positive/negative. If the expression
2902 cannot be statically analyzed, return false, otherwise set the answer into
2906 chrec_is_positive (tree chrec
, bool *value
)
2908 bool value0
, value1
, value2
;
2909 tree end_value
, nb_iter
;
2911 switch (TREE_CODE (chrec
))
2913 case POLYNOMIAL_CHREC
:
2914 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
2915 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
2918 /* FIXME -- overflows. */
2919 if (value0
== value1
)
2925 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
2926 and the proof consists in showing that the sign never
2927 changes during the execution of the loop, from 0 to
2928 loop->nb_iterations. */
2929 if (!evolution_function_is_affine_p (chrec
))
2932 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
2933 if (chrec_contains_undetermined (nb_iter
))
2937 /* TODO -- If the test is after the exit, we may decrease the number of
2938 iterations by one. */
2940 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
2943 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
2945 if (!chrec_is_positive (end_value
, &value2
))
2949 return value0
== value1
;
2952 switch (tree_int_cst_sgn (chrec
))
2971 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2972 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2973 *OVERLAPS_B are initialized to the functions that describe the
2974 relation between the elements accessed twice by CHREC_A and
2975 CHREC_B. For k >= 0, the following property is verified:
2977 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2980 analyze_siv_subscript_cst_affine (tree chrec_a
,
2982 conflict_function
**overlaps_a
,
2983 conflict_function
**overlaps_b
,
2984 tree
*last_conflicts
)
2986 bool value0
, value1
, value2
;
2987 tree type
, difference
, tmp
;
2989 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
2990 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
2991 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
2992 difference
= chrec_fold_minus (type
, initial_condition (chrec_b
), chrec_a
);
2994 /* Special case overlap in the first iteration. */
2995 if (integer_zerop (difference
))
2997 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2998 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2999 *last_conflicts
= integer_one_node
;
3003 if (!chrec_is_positive (initial_condition (difference
), &value0
))
3005 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3006 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
3008 dependence_stats
.num_siv_unimplemented
++;
3009 *overlaps_a
= conflict_fn_not_known ();
3010 *overlaps_b
= conflict_fn_not_known ();
3011 *last_conflicts
= chrec_dont_know
;
3016 if (value0
== false)
3018 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
3020 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3021 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
3023 *overlaps_a
= conflict_fn_not_known ();
3024 *overlaps_b
= conflict_fn_not_known ();
3025 *last_conflicts
= chrec_dont_know
;
3026 dependence_stats
.num_siv_unimplemented
++;
3035 chrec_b = {10, +, 1}
3038 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
3040 HOST_WIDE_INT numiter
;
3041 struct loop
*loop
= get_chrec_loop (chrec_b
);
3043 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3044 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
,
3045 fold_build1 (ABS_EXPR
, type
, difference
),
3046 CHREC_RIGHT (chrec_b
));
3047 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
3048 *last_conflicts
= integer_one_node
;
3051 /* Perform weak-zero siv test to see if overlap is
3052 outside the loop bounds. */
3053 numiter
= max_stmt_executions_int (loop
);
3056 && compare_tree_int (tmp
, numiter
) > 0)
3058 free_conflict_function (*overlaps_a
);
3059 free_conflict_function (*overlaps_b
);
3060 *overlaps_a
= conflict_fn_no_dependence ();
3061 *overlaps_b
= conflict_fn_no_dependence ();
3062 *last_conflicts
= integer_zero_node
;
3063 dependence_stats
.num_siv_independent
++;
3066 dependence_stats
.num_siv_dependent
++;
3070 /* When the step does not divide the difference, there are
3074 *overlaps_a
= conflict_fn_no_dependence ();
3075 *overlaps_b
= conflict_fn_no_dependence ();
3076 *last_conflicts
= integer_zero_node
;
3077 dependence_stats
.num_siv_independent
++;
3086 chrec_b = {10, +, -1}
3088 In this case, chrec_a will not overlap with chrec_b. */
3089 *overlaps_a
= conflict_fn_no_dependence ();
3090 *overlaps_b
= conflict_fn_no_dependence ();
3091 *last_conflicts
= integer_zero_node
;
3092 dependence_stats
.num_siv_independent
++;
3099 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
3101 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3102 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
3104 *overlaps_a
= conflict_fn_not_known ();
3105 *overlaps_b
= conflict_fn_not_known ();
3106 *last_conflicts
= chrec_dont_know
;
3107 dependence_stats
.num_siv_unimplemented
++;
3112 if (value2
== false)
3116 chrec_b = {10, +, -1}
3118 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
3120 HOST_WIDE_INT numiter
;
3121 struct loop
*loop
= get_chrec_loop (chrec_b
);
3123 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3124 tmp
= fold_build2 (EXACT_DIV_EXPR
, type
, difference
,
3125 CHREC_RIGHT (chrec_b
));
3126 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
3127 *last_conflicts
= integer_one_node
;
3129 /* Perform weak-zero siv test to see if overlap is
3130 outside the loop bounds. */
3131 numiter
= max_stmt_executions_int (loop
);
3134 && compare_tree_int (tmp
, numiter
) > 0)
3136 free_conflict_function (*overlaps_a
);
3137 free_conflict_function (*overlaps_b
);
3138 *overlaps_a
= conflict_fn_no_dependence ();
3139 *overlaps_b
= conflict_fn_no_dependence ();
3140 *last_conflicts
= integer_zero_node
;
3141 dependence_stats
.num_siv_independent
++;
3144 dependence_stats
.num_siv_dependent
++;
3148 /* When the step does not divide the difference, there
3152 *overlaps_a
= conflict_fn_no_dependence ();
3153 *overlaps_b
= conflict_fn_no_dependence ();
3154 *last_conflicts
= integer_zero_node
;
3155 dependence_stats
.num_siv_independent
++;
3165 In this case, chrec_a will not overlap with chrec_b. */
3166 *overlaps_a
= conflict_fn_no_dependence ();
3167 *overlaps_b
= conflict_fn_no_dependence ();
3168 *last_conflicts
= integer_zero_node
;
3169 dependence_stats
.num_siv_independent
++;
3177 /* Helper recursive function for initializing the matrix A. Returns
3178 the initial value of CHREC. */
3181 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
3185 switch (TREE_CODE (chrec
))
3187 case POLYNOMIAL_CHREC
:
3188 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
3189 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
3195 tree op0
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
3196 tree op1
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 1), index
, mult
);
3198 return chrec_fold_op (TREE_CODE (chrec
), chrec_type (chrec
), op0
, op1
);
3203 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
3204 return chrec_convert (chrec_type (chrec
), op
, NULL
);
3209 /* Handle ~X as -1 - X. */
3210 tree op
= initialize_matrix_A (A
, TREE_OPERAND (chrec
, 0), index
, mult
);
3211 return chrec_fold_op (MINUS_EXPR
, chrec_type (chrec
),
3212 build_int_cst (TREE_TYPE (chrec
), -1), op
);
3224 #define FLOOR_DIV(x,y) ((x) / (y))
3226 /* Solves the special case of the Diophantine equation:
3227 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
3229 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
3230 number of iterations that loops X and Y run. The overlaps will be
3231 constructed as evolutions in dimension DIM. */
3234 compute_overlap_steps_for_affine_univar (HOST_WIDE_INT niter
,
3235 HOST_WIDE_INT step_a
,
3236 HOST_WIDE_INT step_b
,
3237 affine_fn
*overlaps_a
,
3238 affine_fn
*overlaps_b
,
3239 tree
*last_conflicts
, int dim
)
3241 if (((step_a
> 0 && step_b
> 0)
3242 || (step_a
< 0 && step_b
< 0)))
3244 HOST_WIDE_INT step_overlaps_a
, step_overlaps_b
;
3245 HOST_WIDE_INT gcd_steps_a_b
, last_conflict
, tau2
;
3247 gcd_steps_a_b
= gcd (step_a
, step_b
);
3248 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
3249 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
3253 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
3254 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
3255 last_conflict
= tau2
;
3256 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
3259 *last_conflicts
= chrec_dont_know
;
3261 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
3262 build_int_cst (NULL_TREE
,
3264 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
3265 build_int_cst (NULL_TREE
,
3271 *overlaps_a
= affine_fn_cst (integer_zero_node
);
3272 *overlaps_b
= affine_fn_cst (integer_zero_node
);
3273 *last_conflicts
= integer_zero_node
;
3277 /* Solves the special case of a Diophantine equation where CHREC_A is
3278 an affine bivariate function, and CHREC_B is an affine univariate
3279 function. For example,
3281 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
3283 has the following overlapping functions:
3285 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
3286 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
3287 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
3289 FORNOW: This is a specialized implementation for a case occurring in
3290 a common benchmark. Implement the general algorithm. */
3293 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
3294 conflict_function
**overlaps_a
,
3295 conflict_function
**overlaps_b
,
3296 tree
*last_conflicts
)
3298 bool xz_p
, yz_p
, xyz_p
;
3299 HOST_WIDE_INT step_x
, step_y
, step_z
;
3300 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
3301 affine_fn overlaps_a_xz
, overlaps_b_xz
;
3302 affine_fn overlaps_a_yz
, overlaps_b_yz
;
3303 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
3304 affine_fn ova1
, ova2
, ovb
;
3305 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
3307 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
3308 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
3309 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
3311 niter_x
= max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a
)));
3312 niter_y
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
3313 niter_z
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
3315 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
3317 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3318 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
3320 *overlaps_a
= conflict_fn_not_known ();
3321 *overlaps_b
= conflict_fn_not_known ();
3322 *last_conflicts
= chrec_dont_know
;
3326 niter
= MIN (niter_x
, niter_z
);
3327 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
3330 &last_conflicts_xz
, 1);
3331 niter
= MIN (niter_y
, niter_z
);
3332 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
3335 &last_conflicts_yz
, 2);
3336 niter
= MIN (niter_x
, niter_z
);
3337 niter
= MIN (niter_y
, niter
);
3338 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
3341 &last_conflicts_xyz
, 3);
3343 xz_p
= !integer_zerop (last_conflicts_xz
);
3344 yz_p
= !integer_zerop (last_conflicts_yz
);
3345 xyz_p
= !integer_zerop (last_conflicts_xyz
);
3347 if (xz_p
|| yz_p
|| xyz_p
)
3349 ova1
= affine_fn_cst (integer_zero_node
);
3350 ova2
= affine_fn_cst (integer_zero_node
);
3351 ovb
= affine_fn_cst (integer_zero_node
);
3354 affine_fn t0
= ova1
;
3357 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
3358 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
3359 affine_fn_free (t0
);
3360 affine_fn_free (t2
);
3361 *last_conflicts
= last_conflicts_xz
;
3365 affine_fn t0
= ova2
;
3368 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
3369 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
3370 affine_fn_free (t0
);
3371 affine_fn_free (t2
);
3372 *last_conflicts
= last_conflicts_yz
;
3376 affine_fn t0
= ova1
;
3377 affine_fn t2
= ova2
;
3380 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
3381 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
3382 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
3383 affine_fn_free (t0
);
3384 affine_fn_free (t2
);
3385 affine_fn_free (t4
);
3386 *last_conflicts
= last_conflicts_xyz
;
3388 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
3389 *overlaps_b
= conflict_fn (1, ovb
);
3393 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3394 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3395 *last_conflicts
= integer_zero_node
;
3398 affine_fn_free (overlaps_a_xz
);
3399 affine_fn_free (overlaps_b_xz
);
3400 affine_fn_free (overlaps_a_yz
);
3401 affine_fn_free (overlaps_b_yz
);
3402 affine_fn_free (overlaps_a_xyz
);
3403 affine_fn_free (overlaps_b_xyz
);
3406 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
3409 lambda_vector_copy (lambda_vector vec1
, lambda_vector vec2
,
3412 memcpy (vec2
, vec1
, size
* sizeof (*vec1
));
3415 /* Copy the elements of M x N matrix MAT1 to MAT2. */
3418 lambda_matrix_copy (lambda_matrix mat1
, lambda_matrix mat2
,
3423 for (i
= 0; i
< m
; i
++)
3424 lambda_vector_copy (mat1
[i
], mat2
[i
], n
);
3427 /* Store the N x N identity matrix in MAT. */
3430 lambda_matrix_id (lambda_matrix mat
, int size
)
3434 for (i
= 0; i
< size
; i
++)
3435 for (j
= 0; j
< size
; j
++)
3436 mat
[i
][j
] = (i
== j
) ? 1 : 0;
3439 /* Return the first nonzero element of vector VEC1 between START and N.
3440 We must have START <= N. Returns N if VEC1 is the zero vector. */
3443 lambda_vector_first_nz (lambda_vector vec1
, int n
, int start
)
3446 while (j
< n
&& vec1
[j
] == 0)
3451 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
3452 R2 = R2 + CONST1 * R1. */
3455 lambda_matrix_row_add (lambda_matrix mat
, int n
, int r1
, int r2
, int const1
)
3462 for (i
= 0; i
< n
; i
++)
3463 mat
[r2
][i
] += const1
* mat
[r1
][i
];
3466 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
3467 and store the result in VEC2. */
3470 lambda_vector_mult_const (lambda_vector vec1
, lambda_vector vec2
,
3471 int size
, int const1
)
3476 lambda_vector_clear (vec2
, size
);
3478 for (i
= 0; i
< size
; i
++)
3479 vec2
[i
] = const1
* vec1
[i
];
3482 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
3485 lambda_vector_negate (lambda_vector vec1
, lambda_vector vec2
,
3488 lambda_vector_mult_const (vec1
, vec2
, size
, -1);
3491 /* Negate row R1 of matrix MAT which has N columns. */
3494 lambda_matrix_row_negate (lambda_matrix mat
, int n
, int r1
)
3496 lambda_vector_negate (mat
[r1
], mat
[r1
], n
);
3499 /* Return true if two vectors are equal. */
3502 lambda_vector_equal (lambda_vector vec1
, lambda_vector vec2
, int size
)
3505 for (i
= 0; i
< size
; i
++)
3506 if (vec1
[i
] != vec2
[i
])
3511 /* Given an M x N integer matrix A, this function determines an M x
3512 M unimodular matrix U, and an M x N echelon matrix S such that
3513 "U.A = S". This decomposition is also known as "right Hermite".
3515 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
3516 Restructuring Compilers" Utpal Banerjee. */
3519 lambda_matrix_right_hermite (lambda_matrix A
, int m
, int n
,
3520 lambda_matrix S
, lambda_matrix U
)
3524 lambda_matrix_copy (A
, S
, m
, n
);
3525 lambda_matrix_id (U
, m
);
3527 for (j
= 0; j
< n
; j
++)
3529 if (lambda_vector_first_nz (S
[j
], m
, i0
) < m
)
3532 for (i
= m
- 1; i
>= i0
; i
--)
3534 while (S
[i
][j
] != 0)
3536 int sigma
, factor
, a
, b
;
3540 sigma
= (a
* b
< 0) ? -1: 1;
3543 factor
= sigma
* (a
/ b
);
3545 lambda_matrix_row_add (S
, n
, i
, i
-1, -factor
);
3546 std::swap (S
[i
], S
[i
-1]);
3548 lambda_matrix_row_add (U
, m
, i
, i
-1, -factor
);
3549 std::swap (U
[i
], U
[i
-1]);
3556 /* Determines the overlapping elements due to accesses CHREC_A and
3557 CHREC_B, that are affine functions. This function cannot handle
3558 symbolic evolution functions, ie. when initial conditions are
3559 parameters, because it uses lambda matrices of integers. */
3562 analyze_subscript_affine_affine (tree chrec_a
,
3564 conflict_function
**overlaps_a
,
3565 conflict_function
**overlaps_b
,
3566 tree
*last_conflicts
)
3568 unsigned nb_vars_a
, nb_vars_b
, dim
;
3569 HOST_WIDE_INT init_a
, init_b
, gamma
, gcd_alpha_beta
;
3570 lambda_matrix A
, U
, S
;
3571 struct obstack scratch_obstack
;
3573 if (eq_evolutions_p (chrec_a
, chrec_b
))
3575 /* The accessed index overlaps for each iteration in the
3577 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3578 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3579 *last_conflicts
= chrec_dont_know
;
3582 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3583 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
3585 /* For determining the initial intersection, we have to solve a
3586 Diophantine equation. This is the most time consuming part.
3588 For answering to the question: "Is there a dependence?" we have
3589 to prove that there exists a solution to the Diophantine
3590 equation, and that the solution is in the iteration domain,
3591 i.e. the solution is positive or zero, and that the solution
3592 happens before the upper bound loop.nb_iterations. Otherwise
3593 there is no dependence. This function outputs a description of
3594 the iterations that hold the intersections. */
3596 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
3597 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
3599 gcc_obstack_init (&scratch_obstack
);
3601 dim
= nb_vars_a
+ nb_vars_b
;
3602 U
= lambda_matrix_new (dim
, dim
, &scratch_obstack
);
3603 A
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
3604 S
= lambda_matrix_new (dim
, 1, &scratch_obstack
);
3606 init_a
= int_cst_value (initialize_matrix_A (A
, chrec_a
, 0, 1));
3607 init_b
= int_cst_value (initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1));
3608 gamma
= init_b
- init_a
;
3610 /* Don't do all the hard work of solving the Diophantine equation
3611 when we already know the solution: for example,
3614 | gamma = 3 - 3 = 0.
3615 Then the first overlap occurs during the first iterations:
3616 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
3620 if (nb_vars_a
== 1 && nb_vars_b
== 1)
3622 HOST_WIDE_INT step_a
, step_b
;
3623 HOST_WIDE_INT niter
, niter_a
, niter_b
;
3626 niter_a
= max_stmt_executions_int (get_chrec_loop (chrec_a
));
3627 niter_b
= max_stmt_executions_int (get_chrec_loop (chrec_b
));
3628 niter
= MIN (niter_a
, niter_b
);
3629 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
3630 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
3632 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
3635 *overlaps_a
= conflict_fn (1, ova
);
3636 *overlaps_b
= conflict_fn (1, ovb
);
3639 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
3640 compute_overlap_steps_for_affine_1_2
3641 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
3643 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
3644 compute_overlap_steps_for_affine_1_2
3645 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
3649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3650 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
3651 *overlaps_a
= conflict_fn_not_known ();
3652 *overlaps_b
= conflict_fn_not_known ();
3653 *last_conflicts
= chrec_dont_know
;
3655 goto end_analyze_subs_aa
;
3659 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
3664 lambda_matrix_row_negate (U
, dim
, 0);
3666 gcd_alpha_beta
= S
[0][0];
3668 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
3669 but that is a quite strange case. Instead of ICEing, answer
3671 if (gcd_alpha_beta
== 0)
3673 *overlaps_a
= conflict_fn_not_known ();
3674 *overlaps_b
= conflict_fn_not_known ();
3675 *last_conflicts
= chrec_dont_know
;
3676 goto end_analyze_subs_aa
;
3679 /* The classic "gcd-test". */
3680 if (!int_divides_p (gcd_alpha_beta
, gamma
))
3682 /* The "gcd-test" has determined that there is no integer
3683 solution, i.e. there is no dependence. */
3684 *overlaps_a
= conflict_fn_no_dependence ();
3685 *overlaps_b
= conflict_fn_no_dependence ();
3686 *last_conflicts
= integer_zero_node
;
3689 /* Both access functions are univariate. This includes SIV and MIV cases. */
3690 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
3692 /* Both functions should have the same evolution sign. */
3693 if (((A
[0][0] > 0 && -A
[1][0] > 0)
3694 || (A
[0][0] < 0 && -A
[1][0] < 0)))
3696 /* The solutions are given by:
3698 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
3701 For a given integer t. Using the following variables,
3703 | i0 = u11 * gamma / gcd_alpha_beta
3704 | j0 = u12 * gamma / gcd_alpha_beta
3711 | y0 = j0 + j1 * t. */
3712 HOST_WIDE_INT i0
, j0
, i1
, j1
;
3714 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
3715 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
3719 if ((i1
== 0 && i0
< 0)
3720 || (j1
== 0 && j0
< 0))
3722 /* There is no solution.
3723 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
3724 falls in here, but for the moment we don't look at the
3725 upper bound of the iteration domain. */
3726 *overlaps_a
= conflict_fn_no_dependence ();
3727 *overlaps_b
= conflict_fn_no_dependence ();
3728 *last_conflicts
= integer_zero_node
;
3729 goto end_analyze_subs_aa
;
3732 if (i1
> 0 && j1
> 0)
3734 HOST_WIDE_INT niter_a
3735 = max_stmt_executions_int (get_chrec_loop (chrec_a
));
3736 HOST_WIDE_INT niter_b
3737 = max_stmt_executions_int (get_chrec_loop (chrec_b
));
3738 HOST_WIDE_INT niter
= MIN (niter_a
, niter_b
);
3740 /* (X0, Y0) is a solution of the Diophantine equation:
3741 "chrec_a (X0) = chrec_b (Y0)". */
3742 HOST_WIDE_INT tau1
= MAX (CEIL (-i0
, i1
),
3744 HOST_WIDE_INT x0
= i1
* tau1
+ i0
;
3745 HOST_WIDE_INT y0
= j1
* tau1
+ j0
;
3747 /* (X1, Y1) is the smallest positive solution of the eq
3748 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
3749 first conflict occurs. */
3750 HOST_WIDE_INT min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
3751 HOST_WIDE_INT x1
= x0
- i1
* min_multiple
;
3752 HOST_WIDE_INT y1
= y0
- j1
* min_multiple
;
3756 HOST_WIDE_INT tau2
= MIN (FLOOR_DIV (niter_a
- i0
, i1
),
3757 FLOOR_DIV (niter_b
- j0
, j1
));
3758 HOST_WIDE_INT last_conflict
= tau2
- (x1
- i0
)/i1
;
3760 /* If the overlap occurs outside of the bounds of the
3761 loop, there is no dependence. */
3762 if (x1
>= niter_a
|| y1
>= niter_b
)
3764 *overlaps_a
= conflict_fn_no_dependence ();
3765 *overlaps_b
= conflict_fn_no_dependence ();
3766 *last_conflicts
= integer_zero_node
;
3767 goto end_analyze_subs_aa
;
3770 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
3773 *last_conflicts
= chrec_dont_know
;
3777 affine_fn_univar (build_int_cst (NULL_TREE
, x1
),
3779 build_int_cst (NULL_TREE
, i1
)));
3782 affine_fn_univar (build_int_cst (NULL_TREE
, y1
),
3784 build_int_cst (NULL_TREE
, j1
)));
3788 /* FIXME: For the moment, the upper bound of the
3789 iteration domain for i and j is not checked. */
3790 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3791 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3792 *overlaps_a
= conflict_fn_not_known ();
3793 *overlaps_b
= conflict_fn_not_known ();
3794 *last_conflicts
= chrec_dont_know
;
3799 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3800 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3801 *overlaps_a
= conflict_fn_not_known ();
3802 *overlaps_b
= conflict_fn_not_known ();
3803 *last_conflicts
= chrec_dont_know
;
3808 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3809 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3810 *overlaps_a
= conflict_fn_not_known ();
3811 *overlaps_b
= conflict_fn_not_known ();
3812 *last_conflicts
= chrec_dont_know
;
3815 end_analyze_subs_aa
:
3816 obstack_free (&scratch_obstack
, NULL
);
3817 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3819 fprintf (dump_file
, " (overlaps_a = ");
3820 dump_conflict_function (dump_file
, *overlaps_a
);
3821 fprintf (dump_file
, ")\n (overlaps_b = ");
3822 dump_conflict_function (dump_file
, *overlaps_b
);
3823 fprintf (dump_file
, "))\n");
3827 /* Returns true when analyze_subscript_affine_affine can be used for
3828 determining the dependence relation between chrec_a and chrec_b,
3829 that contain symbols. This function modifies chrec_a and chrec_b
3830 such that the analysis result is the same, and such that they don't
3831 contain symbols, and then can safely be passed to the analyzer.
3833 Example: The analysis of the following tuples of evolutions produce
3834 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3837 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3838 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3842 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
3844 tree diff
, type
, left_a
, left_b
, right_b
;
3846 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
3847 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
3848 /* FIXME: For the moment not handled. Might be refined later. */
3851 type
= chrec_type (*chrec_a
);
3852 left_a
= CHREC_LEFT (*chrec_a
);
3853 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL
);
3854 diff
= chrec_fold_minus (type
, left_a
, left_b
);
3856 if (!evolution_function_is_constant_p (diff
))
3859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3860 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
3862 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
3863 diff
, CHREC_RIGHT (*chrec_a
));
3864 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL
);
3865 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
3866 build_int_cst (type
, 0),
3871 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
3872 *OVERLAPS_B are initialized to the functions that describe the
3873 relation between the elements accessed twice by CHREC_A and
3874 CHREC_B. For k >= 0, the following property is verified:
3876 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3879 analyze_siv_subscript (tree chrec_a
,
3881 conflict_function
**overlaps_a
,
3882 conflict_function
**overlaps_b
,
3883 tree
*last_conflicts
,
3886 dependence_stats
.num_siv
++;
3888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3889 fprintf (dump_file
, "(analyze_siv_subscript \n");
3891 if (evolution_function_is_constant_p (chrec_a
)
3892 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
3893 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
3894 overlaps_a
, overlaps_b
, last_conflicts
);
3896 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
3897 && evolution_function_is_constant_p (chrec_b
))
3898 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
3899 overlaps_b
, overlaps_a
, last_conflicts
);
3901 else if (evolution_function_is_affine_in_loop (chrec_a
, loop_nest_num
)
3902 && evolution_function_is_affine_in_loop (chrec_b
, loop_nest_num
))
3904 if (!chrec_contains_symbols (chrec_a
)
3905 && !chrec_contains_symbols (chrec_b
))
3907 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3908 overlaps_a
, overlaps_b
,
3911 if (CF_NOT_KNOWN_P (*overlaps_a
)
3912 || CF_NOT_KNOWN_P (*overlaps_b
))
3913 dependence_stats
.num_siv_unimplemented
++;
3914 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
3915 || CF_NO_DEPENDENCE_P (*overlaps_b
))
3916 dependence_stats
.num_siv_independent
++;
3918 dependence_stats
.num_siv_dependent
++;
3920 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
3923 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3924 overlaps_a
, overlaps_b
,
3927 if (CF_NOT_KNOWN_P (*overlaps_a
)
3928 || CF_NOT_KNOWN_P (*overlaps_b
))
3929 dependence_stats
.num_siv_unimplemented
++;
3930 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
3931 || CF_NO_DEPENDENCE_P (*overlaps_b
))
3932 dependence_stats
.num_siv_independent
++;
3934 dependence_stats
.num_siv_dependent
++;
3937 goto siv_subscript_dontknow
;
3942 siv_subscript_dontknow
:;
3943 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3944 fprintf (dump_file
, " siv test failed: unimplemented");
3945 *overlaps_a
= conflict_fn_not_known ();
3946 *overlaps_b
= conflict_fn_not_known ();
3947 *last_conflicts
= chrec_dont_know
;
3948 dependence_stats
.num_siv_unimplemented
++;
3951 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3952 fprintf (dump_file
, ")\n");
3955 /* Returns false if we can prove that the greatest common divisor of the steps
3956 of CHREC does not divide CST, false otherwise. */
3959 gcd_of_steps_may_divide_p (const_tree chrec
, const_tree cst
)
3961 HOST_WIDE_INT cd
= 0, val
;
3964 if (!tree_fits_shwi_p (cst
))
3966 val
= tree_to_shwi (cst
);
3968 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
3970 step
= CHREC_RIGHT (chrec
);
3971 if (!tree_fits_shwi_p (step
))
3973 cd
= gcd (cd
, tree_to_shwi (step
));
3974 chrec
= CHREC_LEFT (chrec
);
3977 return val
% cd
== 0;
3980 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
3981 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
3982 functions that describe the relation between the elements accessed
3983 twice by CHREC_A and CHREC_B. For k >= 0, the following property
3986 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3989 analyze_miv_subscript (tree chrec_a
,
3991 conflict_function
**overlaps_a
,
3992 conflict_function
**overlaps_b
,
3993 tree
*last_conflicts
,
3994 struct loop
*loop_nest
)
3996 tree type
, difference
;
3998 dependence_stats
.num_miv
++;
3999 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4000 fprintf (dump_file
, "(analyze_miv_subscript \n");
4002 type
= signed_type_for_types (TREE_TYPE (chrec_a
), TREE_TYPE (chrec_b
));
4003 chrec_a
= chrec_convert (type
, chrec_a
, NULL
);
4004 chrec_b
= chrec_convert (type
, chrec_b
, NULL
);
4005 difference
= chrec_fold_minus (type
, chrec_a
, chrec_b
);
4007 if (eq_evolutions_p (chrec_a
, chrec_b
))
4009 /* Access functions are the same: all the elements are accessed
4010 in the same order. */
4011 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
4012 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
4013 *last_conflicts
= max_stmt_executions_tree (get_chrec_loop (chrec_a
));
4014 dependence_stats
.num_miv_dependent
++;
4017 else if (evolution_function_is_constant_p (difference
)
4018 && evolution_function_is_affine_multivariate_p (chrec_a
,
4020 && !gcd_of_steps_may_divide_p (chrec_a
, difference
))
4022 /* testsuite/.../ssa-chrec-33.c
4023 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
4025 The difference is 1, and all the evolution steps are multiples
4026 of 2, consequently there are no overlapping elements. */
4027 *overlaps_a
= conflict_fn_no_dependence ();
4028 *overlaps_b
= conflict_fn_no_dependence ();
4029 *last_conflicts
= integer_zero_node
;
4030 dependence_stats
.num_miv_independent
++;
4033 else if (evolution_function_is_affine_multivariate_p (chrec_a
, loop_nest
->num
)
4034 && !chrec_contains_symbols (chrec_a
)
4035 && evolution_function_is_affine_multivariate_p (chrec_b
, loop_nest
->num
)
4036 && !chrec_contains_symbols (chrec_b
))
4038 /* testsuite/.../ssa-chrec-35.c
4039 {0, +, 1}_2 vs. {0, +, 1}_3
4040 the overlapping elements are respectively located at iterations:
4041 {0, +, 1}_x and {0, +, 1}_x,
4042 in other words, we have the equality:
4043 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
4046 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
4047 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
4049 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
4050 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
4052 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
4053 overlaps_a
, overlaps_b
, last_conflicts
);
4055 if (CF_NOT_KNOWN_P (*overlaps_a
)
4056 || CF_NOT_KNOWN_P (*overlaps_b
))
4057 dependence_stats
.num_miv_unimplemented
++;
4058 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
4059 || CF_NO_DEPENDENCE_P (*overlaps_b
))
4060 dependence_stats
.num_miv_independent
++;
4062 dependence_stats
.num_miv_dependent
++;
4067 /* When the analysis is too difficult, answer "don't know". */
4068 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4069 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
4071 *overlaps_a
= conflict_fn_not_known ();
4072 *overlaps_b
= conflict_fn_not_known ();
4073 *last_conflicts
= chrec_dont_know
;
4074 dependence_stats
.num_miv_unimplemented
++;
4077 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4078 fprintf (dump_file
, ")\n");
4081 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
4082 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
4083 OVERLAP_ITERATIONS_B are initialized with two functions that
4084 describe the iterations that contain conflicting elements.
4086 Remark: For an integer k >= 0, the following equality is true:
4088 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
4092 analyze_overlapping_iterations (tree chrec_a
,
4094 conflict_function
**overlap_iterations_a
,
4095 conflict_function
**overlap_iterations_b
,
4096 tree
*last_conflicts
, struct loop
*loop_nest
)
4098 unsigned int lnn
= loop_nest
->num
;
4100 dependence_stats
.num_subscript_tests
++;
4102 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4104 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
4105 fprintf (dump_file
, " (chrec_a = ");
4106 print_generic_expr (dump_file
, chrec_a
);
4107 fprintf (dump_file
, ")\n (chrec_b = ");
4108 print_generic_expr (dump_file
, chrec_b
);
4109 fprintf (dump_file
, ")\n");
4112 if (chrec_a
== NULL_TREE
4113 || chrec_b
== NULL_TREE
4114 || chrec_contains_undetermined (chrec_a
)
4115 || chrec_contains_undetermined (chrec_b
))
4117 dependence_stats
.num_subscript_undetermined
++;
4119 *overlap_iterations_a
= conflict_fn_not_known ();
4120 *overlap_iterations_b
= conflict_fn_not_known ();
4123 /* If they are the same chrec, and are affine, they overlap
4124 on every iteration. */
4125 else if (eq_evolutions_p (chrec_a
, chrec_b
)
4126 && (evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
4127 || operand_equal_p (chrec_a
, chrec_b
, 0)))
4129 dependence_stats
.num_same_subscript_function
++;
4130 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
4131 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
4132 *last_conflicts
= chrec_dont_know
;
4135 /* If they aren't the same, and aren't affine, we can't do anything
4137 else if ((chrec_contains_symbols (chrec_a
)
4138 || chrec_contains_symbols (chrec_b
))
4139 && (!evolution_function_is_affine_multivariate_p (chrec_a
, lnn
)
4140 || !evolution_function_is_affine_multivariate_p (chrec_b
, lnn
)))
4142 dependence_stats
.num_subscript_undetermined
++;
4143 *overlap_iterations_a
= conflict_fn_not_known ();
4144 *overlap_iterations_b
= conflict_fn_not_known ();
4147 else if (ziv_subscript_p (chrec_a
, chrec_b
))
4148 analyze_ziv_subscript (chrec_a
, chrec_b
,
4149 overlap_iterations_a
, overlap_iterations_b
,
4152 else if (siv_subscript_p (chrec_a
, chrec_b
))
4153 analyze_siv_subscript (chrec_a
, chrec_b
,
4154 overlap_iterations_a
, overlap_iterations_b
,
4155 last_conflicts
, lnn
);
4158 analyze_miv_subscript (chrec_a
, chrec_b
,
4159 overlap_iterations_a
, overlap_iterations_b
,
4160 last_conflicts
, loop_nest
);
4162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4164 fprintf (dump_file
, " (overlap_iterations_a = ");
4165 dump_conflict_function (dump_file
, *overlap_iterations_a
);
4166 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
4167 dump_conflict_function (dump_file
, *overlap_iterations_b
);
4168 fprintf (dump_file
, "))\n");
4172 /* Helper function for uniquely inserting distance vectors. */
4175 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
4180 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, v
)
4181 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
4184 DDR_DIST_VECTS (ddr
).safe_push (dist_v
);
4187 /* Helper function for uniquely inserting direction vectors. */
4190 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
4195 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr
), i
, v
)
4196 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
4199 DDR_DIR_VECTS (ddr
).safe_push (dir_v
);
4202 /* Add a distance of 1 on all the loops outer than INDEX. If we
4203 haven't yet determined a distance for this outer loop, push a new
4204 distance vector composed of the previous distance, and a distance
4205 of 1 for this outer loop. Example:
4213 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
4214 save (0, 1), then we have to save (1, 0). */
4217 add_outer_distances (struct data_dependence_relation
*ddr
,
4218 lambda_vector dist_v
, int index
)
4220 /* For each outer loop where init_v is not set, the accesses are
4221 in dependence of distance 1 in the loop. */
4222 while (--index
>= 0)
4224 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4225 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
4227 save_dist_v (ddr
, save_v
);
4231 /* Return false when fail to represent the data dependence as a
4232 distance vector. A_INDEX is the index of the first reference
4233 (0 for DDR_A, 1 for DDR_B) and B_INDEX is the index of the
4234 second reference. INIT_B is set to true when a component has been
4235 added to the distance vector DIST_V. INDEX_CARRY is then set to
4236 the index in DIST_V that carries the dependence. */
4239 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
4240 unsigned int a_index
, unsigned int b_index
,
4241 lambda_vector dist_v
, bool *init_b
,
4245 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4247 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
4249 tree access_fn_a
, access_fn_b
;
4250 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
4252 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
4254 non_affine_dependence_relation (ddr
);
4258 access_fn_a
= SUB_ACCESS_FN (subscript
, a_index
);
4259 access_fn_b
= SUB_ACCESS_FN (subscript
, b_index
);
4261 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
4262 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
4266 int var_a
= CHREC_VARIABLE (access_fn_a
);
4267 int var_b
= CHREC_VARIABLE (access_fn_b
);
4270 || chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
4272 non_affine_dependence_relation (ddr
);
4276 dist
= int_cst_value (SUB_DISTANCE (subscript
));
4277 index
= index_in_loop_nest (var_a
, DDR_LOOP_NEST (ddr
));
4278 *index_carry
= MIN (index
, *index_carry
);
4280 /* This is the subscript coupling test. If we have already
4281 recorded a distance for this loop (a distance coming from
4282 another subscript), it should be the same. For example,
4283 in the following code, there is no dependence:
4290 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
4292 finalize_ddr_dependent (ddr
, chrec_known
);
4296 dist_v
[index
] = dist
;
4300 else if (!operand_equal_p (access_fn_a
, access_fn_b
, 0))
4302 /* This can be for example an affine vs. constant dependence
4303 (T[i] vs. T[3]) that is not an affine dependence and is
4304 not representable as a distance vector. */
4305 non_affine_dependence_relation (ddr
);
4313 /* Return true when the DDR contains only constant access functions. */
4316 constant_access_functions (const struct data_dependence_relation
*ddr
)
4321 FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr
), i
, sub
)
4322 if (!evolution_function_is_constant_p (SUB_ACCESS_FN (sub
, 0))
4323 || !evolution_function_is_constant_p (SUB_ACCESS_FN (sub
, 1)))
4329 /* Helper function for the case where DDR_A and DDR_B are the same
4330 multivariate access function with a constant step. For an example
4334 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
4337 tree c_1
= CHREC_LEFT (c_2
);
4338 tree c_0
= CHREC_LEFT (c_1
);
4339 lambda_vector dist_v
;
4340 HOST_WIDE_INT v1
, v2
, cd
;
4342 /* Polynomials with more than 2 variables are not handled yet. When
4343 the evolution steps are parameters, it is not possible to
4344 represent the dependence using classical distance vectors. */
4345 if (TREE_CODE (c_0
) != INTEGER_CST
4346 || TREE_CODE (CHREC_RIGHT (c_1
)) != INTEGER_CST
4347 || TREE_CODE (CHREC_RIGHT (c_2
)) != INTEGER_CST
)
4349 DDR_AFFINE_P (ddr
) = false;
4353 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
4354 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
4356 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
4357 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4358 v1
= int_cst_value (CHREC_RIGHT (c_1
));
4359 v2
= int_cst_value (CHREC_RIGHT (c_2
));
4372 save_dist_v (ddr
, dist_v
);
4374 add_outer_distances (ddr
, dist_v
, x_1
);
4377 /* Helper function for the case where DDR_A and DDR_B are the same
4378 access functions. */
4381 add_other_self_distances (struct data_dependence_relation
*ddr
)
4383 lambda_vector dist_v
;
4385 int index_carry
= DDR_NB_LOOPS (ddr
);
4388 FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr
), i
, sub
)
4390 tree access_fun
= SUB_ACCESS_FN (sub
, 0);
4392 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
4394 if (!evolution_function_is_univariate_p (access_fun
))
4396 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
4398 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
4402 access_fun
= SUB_ACCESS_FN (DDR_SUBSCRIPT (ddr
, 0), 0);
4404 if (TREE_CODE (CHREC_LEFT (access_fun
)) == POLYNOMIAL_CHREC
)
4405 add_multivariate_self_dist (ddr
, access_fun
);
4407 /* The evolution step is not constant: it varies in
4408 the outer loop, so this cannot be represented by a
4409 distance vector. For example in pr34635.c the
4410 evolution is {0, +, {0, +, 4}_1}_2. */
4411 DDR_AFFINE_P (ddr
) = false;
4416 index_carry
= MIN (index_carry
,
4417 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
4418 DDR_LOOP_NEST (ddr
)));
4422 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4423 add_outer_distances (ddr
, dist_v
, index_carry
);
4427 insert_innermost_unit_dist_vector (struct data_dependence_relation
*ddr
)
4429 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4431 dist_v
[DDR_INNER_LOOP (ddr
)] = 1;
4432 save_dist_v (ddr
, dist_v
);
4435 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
4436 is the case for example when access functions are the same and
4437 equal to a constant, as in:
4444 in which case the distance vectors are (0) and (1). */
4447 add_distance_for_zero_overlaps (struct data_dependence_relation
*ddr
)
4451 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
4453 subscript_p sub
= DDR_SUBSCRIPT (ddr
, i
);
4454 conflict_function
*ca
= SUB_CONFLICTS_IN_A (sub
);
4455 conflict_function
*cb
= SUB_CONFLICTS_IN_B (sub
);
4457 for (j
= 0; j
< ca
->n
; j
++)
4458 if (affine_function_zero_p (ca
->fns
[j
]))
4460 insert_innermost_unit_dist_vector (ddr
);
4464 for (j
= 0; j
< cb
->n
; j
++)
4465 if (affine_function_zero_p (cb
->fns
[j
]))
4467 insert_innermost_unit_dist_vector (ddr
);
4473 /* Return true when the DDR contains two data references that have the
4474 same access functions. */
4477 same_access_functions (const struct data_dependence_relation
*ddr
)
4482 FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr
), i
, sub
)
4483 if (!eq_evolutions_p (SUB_ACCESS_FN (sub
, 0),
4484 SUB_ACCESS_FN (sub
, 1)))
4490 /* Compute the classic per loop distance vector. DDR is the data
4491 dependence relation to build a vector from. Return false when fail
4492 to represent the data dependence as a distance vector. */
4495 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
4496 struct loop
*loop_nest
)
4498 bool init_b
= false;
4499 int index_carry
= DDR_NB_LOOPS (ddr
);
4500 lambda_vector dist_v
;
4502 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
4505 if (same_access_functions (ddr
))
4507 /* Save the 0 vector. */
4508 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4509 save_dist_v (ddr
, dist_v
);
4511 if (constant_access_functions (ddr
))
4512 add_distance_for_zero_overlaps (ddr
);
4514 if (DDR_NB_LOOPS (ddr
) > 1)
4515 add_other_self_distances (ddr
);
4520 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4521 if (!build_classic_dist_vector_1 (ddr
, 0, 1, dist_v
, &init_b
, &index_carry
))
4524 /* Save the distance vector if we initialized one. */
4527 /* Verify a basic constraint: classic distance vectors should
4528 always be lexicographically positive.
4530 Data references are collected in the order of execution of
4531 the program, thus for the following loop
4533 | for (i = 1; i < 100; i++)
4534 | for (j = 1; j < 100; j++)
4536 | t = T[j+1][i-1]; // A
4537 | T[j][i] = t + 2; // B
4540 references are collected following the direction of the wind:
4541 A then B. The data dependence tests are performed also
4542 following this order, such that we're looking at the distance
4543 separating the elements accessed by A from the elements later
4544 accessed by B. But in this example, the distance returned by
4545 test_dep (A, B) is lexicographically negative (-1, 1), that
4546 means that the access A occurs later than B with respect to
4547 the outer loop, ie. we're actually looking upwind. In this
4548 case we solve test_dep (B, A) looking downwind to the
4549 lexicographically positive solution, that returns the
4550 distance vector (1, -1). */
4551 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
4553 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4554 if (!subscript_dependence_tester_1 (ddr
, 1, 0, loop_nest
))
4556 compute_subscript_distance (ddr
);
4557 if (!build_classic_dist_vector_1 (ddr
, 1, 0, save_v
, &init_b
,
4560 save_dist_v (ddr
, save_v
);
4561 DDR_REVERSED_P (ddr
) = true;
4563 /* In this case there is a dependence forward for all the
4566 | for (k = 1; k < 100; k++)
4567 | for (i = 1; i < 100; i++)
4568 | for (j = 1; j < 100; j++)
4570 | t = T[j+1][i-1]; // A
4571 | T[j][i] = t + 2; // B
4579 if (DDR_NB_LOOPS (ddr
) > 1)
4581 add_outer_distances (ddr
, save_v
, index_carry
);
4582 add_outer_distances (ddr
, dist_v
, index_carry
);
4587 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4588 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
4590 if (DDR_NB_LOOPS (ddr
) > 1)
4592 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4594 if (!subscript_dependence_tester_1 (ddr
, 1, 0, loop_nest
))
4596 compute_subscript_distance (ddr
);
4597 if (!build_classic_dist_vector_1 (ddr
, 1, 0, opposite_v
, &init_b
,
4601 save_dist_v (ddr
, save_v
);
4602 add_outer_distances (ddr
, dist_v
, index_carry
);
4603 add_outer_distances (ddr
, opposite_v
, index_carry
);
4606 save_dist_v (ddr
, save_v
);
4611 /* There is a distance of 1 on all the outer loops: Example:
4612 there is a dependence of distance 1 on loop_1 for the array A.
4618 add_outer_distances (ddr
, dist_v
,
4619 lambda_vector_first_nz (dist_v
,
4620 DDR_NB_LOOPS (ddr
), 0));
4623 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4627 fprintf (dump_file
, "(build_classic_dist_vector\n");
4628 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4630 fprintf (dump_file
, " dist_vector = (");
4631 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
4632 DDR_NB_LOOPS (ddr
));
4633 fprintf (dump_file
, " )\n");
4635 fprintf (dump_file
, ")\n");
4641 /* Return the direction for a given distance.
4642 FIXME: Computing dir this way is suboptimal, since dir can catch
4643 cases that dist is unable to represent. */
4645 static inline enum data_dependence_direction
4646 dir_from_dist (int dist
)
4649 return dir_positive
;
4651 return dir_negative
;
4656 /* Compute the classic per loop direction vector. DDR is the data
4657 dependence relation to build a vector from. */
4660 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
4663 lambda_vector dist_v
;
4665 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
4667 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4669 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
4670 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
4672 save_dir_v (ddr
, dir_v
);
4676 /* Helper function. Returns true when there is a dependence between the
4677 data references. A_INDEX is the index of the first reference (0 for
4678 DDR_A, 1 for DDR_B) and B_INDEX is the index of the second reference. */
4681 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
4682 unsigned int a_index
, unsigned int b_index
,
4683 struct loop
*loop_nest
)
4686 tree last_conflicts
;
4687 struct subscript
*subscript
;
4688 tree res
= NULL_TREE
;
4690 for (i
= 0; DDR_SUBSCRIPTS (ddr
).iterate (i
, &subscript
); i
++)
4692 conflict_function
*overlaps_a
, *overlaps_b
;
4694 analyze_overlapping_iterations (SUB_ACCESS_FN (subscript
, a_index
),
4695 SUB_ACCESS_FN (subscript
, b_index
),
4696 &overlaps_a
, &overlaps_b
,
4697 &last_conflicts
, loop_nest
);
4699 if (SUB_CONFLICTS_IN_A (subscript
))
4700 free_conflict_function (SUB_CONFLICTS_IN_A (subscript
));
4701 if (SUB_CONFLICTS_IN_B (subscript
))
4702 free_conflict_function (SUB_CONFLICTS_IN_B (subscript
));
4704 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
4705 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
4706 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
4708 /* If there is any undetermined conflict function we have to
4709 give a conservative answer in case we cannot prove that
4710 no dependence exists when analyzing another subscript. */
4711 if (CF_NOT_KNOWN_P (overlaps_a
)
4712 || CF_NOT_KNOWN_P (overlaps_b
))
4714 res
= chrec_dont_know
;
4718 /* When there is a subscript with no dependence we can stop. */
4719 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
4720 || CF_NO_DEPENDENCE_P (overlaps_b
))
4727 if (res
== NULL_TREE
)
4730 if (res
== chrec_known
)
4731 dependence_stats
.num_dependence_independent
++;
4733 dependence_stats
.num_dependence_undetermined
++;
4734 finalize_ddr_dependent (ddr
, res
);
4738 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
4741 subscript_dependence_tester (struct data_dependence_relation
*ddr
,
4742 struct loop
*loop_nest
)
4744 if (subscript_dependence_tester_1 (ddr
, 0, 1, loop_nest
))
4745 dependence_stats
.num_dependence_dependent
++;
4747 compute_subscript_distance (ddr
);
4748 if (build_classic_dist_vector (ddr
, loop_nest
))
4749 build_classic_dir_vector (ddr
);
4752 /* Returns true when all the access functions of A are affine or
4753 constant with respect to LOOP_NEST. */
4756 access_functions_are_affine_or_constant_p (const struct data_reference
*a
,
4757 const struct loop
*loop_nest
)
4760 vec
<tree
> fns
= DR_ACCESS_FNS (a
);
4763 FOR_EACH_VEC_ELT (fns
, i
, t
)
4764 if (!evolution_function_is_invariant_p (t
, loop_nest
->num
)
4765 && !evolution_function_is_affine_multivariate_p (t
, loop_nest
->num
))
4771 /* This computes the affine dependence relation between A and B with
4772 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4773 independence between two accesses, while CHREC_DONT_KNOW is used
4774 for representing the unknown relation.
4776 Note that it is possible to stop the computation of the dependence
4777 relation the first time we detect a CHREC_KNOWN element for a given
4781 compute_affine_dependence (struct data_dependence_relation
*ddr
,
4782 struct loop
*loop_nest
)
4784 struct data_reference
*dra
= DDR_A (ddr
);
4785 struct data_reference
*drb
= DDR_B (ddr
);
4787 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4789 fprintf (dump_file
, "(compute_affine_dependence\n");
4790 fprintf (dump_file
, " stmt_a: ");
4791 print_gimple_stmt (dump_file
, DR_STMT (dra
), 0, TDF_SLIM
);
4792 fprintf (dump_file
, " stmt_b: ");
4793 print_gimple_stmt (dump_file
, DR_STMT (drb
), 0, TDF_SLIM
);
4796 /* Analyze only when the dependence relation is not yet known. */
4797 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4799 dependence_stats
.num_dependence_tests
++;
4801 if (access_functions_are_affine_or_constant_p (dra
, loop_nest
)
4802 && access_functions_are_affine_or_constant_p (drb
, loop_nest
))
4803 subscript_dependence_tester (ddr
, loop_nest
);
4805 /* As a last case, if the dependence cannot be determined, or if
4806 the dependence is considered too difficult to determine, answer
4810 dependence_stats
.num_dependence_undetermined
++;
4812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4814 fprintf (dump_file
, "Data ref a:\n");
4815 dump_data_reference (dump_file
, dra
);
4816 fprintf (dump_file
, "Data ref b:\n");
4817 dump_data_reference (dump_file
, drb
);
4818 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
4820 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4824 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4826 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4827 fprintf (dump_file
, ") -> no dependence\n");
4828 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
4829 fprintf (dump_file
, ") -> dependence analysis failed\n");
4831 fprintf (dump_file
, ")\n");
4835 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4836 the data references in DATAREFS, in the LOOP_NEST. When
4837 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4838 relations. Return true when successful, i.e. data references number
4839 is small enough to be handled. */
4842 compute_all_dependences (vec
<data_reference_p
> datarefs
,
4843 vec
<ddr_p
> *dependence_relations
,
4844 vec
<loop_p
> loop_nest
,
4845 bool compute_self_and_rr
)
4847 struct data_dependence_relation
*ddr
;
4848 struct data_reference
*a
, *b
;
4851 if ((int) datarefs
.length ()
4852 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS
))
4854 struct data_dependence_relation
*ddr
;
4856 /* Insert a single relation into dependence_relations:
4858 ddr
= initialize_data_dependence_relation (NULL
, NULL
, loop_nest
);
4859 dependence_relations
->safe_push (ddr
);
4863 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4864 for (j
= i
+ 1; datarefs
.iterate (j
, &b
); j
++)
4865 if (DR_IS_WRITE (a
) || DR_IS_WRITE (b
) || compute_self_and_rr
)
4867 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4868 dependence_relations
->safe_push (ddr
);
4869 if (loop_nest
.exists ())
4870 compute_affine_dependence (ddr
, loop_nest
[0]);
4873 if (compute_self_and_rr
)
4874 FOR_EACH_VEC_ELT (datarefs
, i
, a
)
4876 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4877 dependence_relations
->safe_push (ddr
);
4878 if (loop_nest
.exists ())
4879 compute_affine_dependence (ddr
, loop_nest
[0]);
4885 /* Describes a location of a memory reference. */
4889 /* The memory reference. */
4892 /* True if the memory reference is read. */
4895 /* True if the data reference is conditional within the containing
4896 statement, i.e. if it might not occur even when the statement
4897 is executed and runs to completion. */
4898 bool is_conditional_in_stmt
;
4902 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4903 true if STMT clobbers memory, false otherwise. */
4906 get_references_in_stmt (gimple
*stmt
, vec
<data_ref_loc
, va_heap
> *references
)
4908 bool clobbers_memory
= false;
4911 enum gimple_code stmt_code
= gimple_code (stmt
);
4913 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4914 As we cannot model data-references to not spelled out
4915 accesses give up if they may occur. */
4916 if (stmt_code
== GIMPLE_CALL
4917 && !(gimple_call_flags (stmt
) & ECF_CONST
))
4919 /* Allow IFN_GOMP_SIMD_LANE in their own loops. */
4920 if (gimple_call_internal_p (stmt
))
4921 switch (gimple_call_internal_fn (stmt
))
4923 case IFN_GOMP_SIMD_LANE
:
4925 struct loop
*loop
= gimple_bb (stmt
)->loop_father
;
4926 tree uid
= gimple_call_arg (stmt
, 0);
4927 gcc_assert (TREE_CODE (uid
) == SSA_NAME
);
4929 || loop
->simduid
!= SSA_NAME_VAR (uid
))
4930 clobbers_memory
= true;
4934 case IFN_MASK_STORE
:
4937 clobbers_memory
= true;
4941 clobbers_memory
= true;
4943 else if (stmt_code
== GIMPLE_ASM
4944 && (gimple_asm_volatile_p (as_a
<gasm
*> (stmt
))
4945 || gimple_vuse (stmt
)))
4946 clobbers_memory
= true;
4948 if (!gimple_vuse (stmt
))
4949 return clobbers_memory
;
4951 if (stmt_code
== GIMPLE_ASSIGN
)
4954 op0
= gimple_assign_lhs (stmt
);
4955 op1
= gimple_assign_rhs1 (stmt
);
4958 || (REFERENCE_CLASS_P (op1
)
4959 && (base
= get_base_address (op1
))
4960 && TREE_CODE (base
) != SSA_NAME
4961 && !is_gimple_min_invariant (base
)))
4965 ref
.is_conditional_in_stmt
= false;
4966 references
->safe_push (ref
);
4969 else if (stmt_code
== GIMPLE_CALL
)
4975 ref
.is_read
= false;
4976 if (gimple_call_internal_p (stmt
))
4977 switch (gimple_call_internal_fn (stmt
))
4980 if (gimple_call_lhs (stmt
) == NULL_TREE
)
4984 case IFN_MASK_STORE
:
4985 ptr
= build_int_cst (TREE_TYPE (gimple_call_arg (stmt
, 1)), 0);
4986 align
= tree_to_shwi (gimple_call_arg (stmt
, 1));
4988 type
= TREE_TYPE (gimple_call_lhs (stmt
));
4990 type
= TREE_TYPE (gimple_call_arg (stmt
, 3));
4991 if (TYPE_ALIGN (type
) != align
)
4992 type
= build_aligned_type (type
, align
);
4993 ref
.is_conditional_in_stmt
= true;
4994 ref
.ref
= fold_build2 (MEM_REF
, type
, gimple_call_arg (stmt
, 0),
4996 references
->safe_push (ref
);
5002 op0
= gimple_call_lhs (stmt
);
5003 n
= gimple_call_num_args (stmt
);
5004 for (i
= 0; i
< n
; i
++)
5006 op1
= gimple_call_arg (stmt
, i
);
5009 || (REFERENCE_CLASS_P (op1
) && get_base_address (op1
)))
5013 ref
.is_conditional_in_stmt
= false;
5014 references
->safe_push (ref
);
5019 return clobbers_memory
;
5023 || (REFERENCE_CLASS_P (op0
) && get_base_address (op0
))))
5026 ref
.is_read
= false;
5027 ref
.is_conditional_in_stmt
= false;
5028 references
->safe_push (ref
);
5030 return clobbers_memory
;
5034 /* Returns true if the loop-nest has any data reference. */
5037 loop_nest_has_data_refs (loop_p loop
)
5039 basic_block
*bbs
= get_loop_body (loop
);
5040 auto_vec
<data_ref_loc
, 3> references
;
5042 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
5044 basic_block bb
= bbs
[i
];
5045 gimple_stmt_iterator bsi
;
5047 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
5049 gimple
*stmt
= gsi_stmt (bsi
);
5050 get_references_in_stmt (stmt
, &references
);
5051 if (references
.length ())
5062 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
5063 reference, returns false, otherwise returns true. NEST is the outermost
5064 loop of the loop nest in which the references should be analyzed. */
5067 find_data_references_in_stmt (struct loop
*nest
, gimple
*stmt
,
5068 vec
<data_reference_p
> *datarefs
)
5071 auto_vec
<data_ref_loc
, 2> references
;
5074 data_reference_p dr
;
5076 if (get_references_in_stmt (stmt
, &references
))
5079 FOR_EACH_VEC_ELT (references
, i
, ref
)
5081 dr
= create_data_ref (nest
? loop_preheader_edge (nest
) : NULL
,
5082 loop_containing_stmt (stmt
), ref
->ref
,
5083 stmt
, ref
->is_read
, ref
->is_conditional_in_stmt
);
5084 gcc_assert (dr
!= NULL
);
5085 datarefs
->safe_push (dr
);
5091 /* Stores the data references in STMT to DATAREFS. If there is an
5092 unanalyzable reference, returns false, otherwise returns true.
5093 NEST is the outermost loop of the loop nest in which the references
5094 should be instantiated, LOOP is the loop in which the references
5095 should be analyzed. */
5098 graphite_find_data_references_in_stmt (edge nest
, loop_p loop
, gimple
*stmt
,
5099 vec
<data_reference_p
> *datarefs
)
5102 auto_vec
<data_ref_loc
, 2> references
;
5105 data_reference_p dr
;
5107 if (get_references_in_stmt (stmt
, &references
))
5110 FOR_EACH_VEC_ELT (references
, i
, ref
)
5112 dr
= create_data_ref (nest
, loop
, ref
->ref
, stmt
, ref
->is_read
,
5113 ref
->is_conditional_in_stmt
);
5114 gcc_assert (dr
!= NULL
);
5115 datarefs
->safe_push (dr
);
5121 /* Search the data references in LOOP, and record the information into
5122 DATAREFS. Returns chrec_dont_know when failing to analyze a
5123 difficult case, returns NULL_TREE otherwise. */
5126 find_data_references_in_bb (struct loop
*loop
, basic_block bb
,
5127 vec
<data_reference_p
> *datarefs
)
5129 gimple_stmt_iterator bsi
;
5131 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
5133 gimple
*stmt
= gsi_stmt (bsi
);
5135 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
5137 struct data_reference
*res
;
5138 res
= XCNEW (struct data_reference
);
5139 datarefs
->safe_push (res
);
5141 return chrec_dont_know
;
5148 /* Search the data references in LOOP, and record the information into
5149 DATAREFS. Returns chrec_dont_know when failing to analyze a
5150 difficult case, returns NULL_TREE otherwise.
5152 TODO: This function should be made smarter so that it can handle address
5153 arithmetic as if they were array accesses, etc. */
5156 find_data_references_in_loop (struct loop
*loop
,
5157 vec
<data_reference_p
> *datarefs
)
5159 basic_block bb
, *bbs
;
5162 bbs
= get_loop_body_in_dom_order (loop
);
5164 for (i
= 0; i
< loop
->num_nodes
; i
++)
5168 if (find_data_references_in_bb (loop
, bb
, datarefs
) == chrec_dont_know
)
5171 return chrec_dont_know
;
5179 /* Return the alignment in bytes that DRB is guaranteed to have at all
5183 dr_alignment (innermost_loop_behavior
*drb
)
5185 /* Get the alignment of BASE_ADDRESS + INIT. */
5186 unsigned int alignment
= drb
->base_alignment
;
5187 unsigned int misalignment
= (drb
->base_misalignment
5188 + TREE_INT_CST_LOW (drb
->init
));
5189 if (misalignment
!= 0)
5190 alignment
= MIN (alignment
, misalignment
& -misalignment
);
5192 /* Cap it to the alignment of OFFSET. */
5193 if (!integer_zerop (drb
->offset
))
5194 alignment
= MIN (alignment
, drb
->offset_alignment
);
5196 /* Cap it to the alignment of STEP. */
5197 if (!integer_zerop (drb
->step
))
5198 alignment
= MIN (alignment
, drb
->step_alignment
);
5203 /* Recursive helper function. */
5206 find_loop_nest_1 (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
5208 /* Inner loops of the nest should not contain siblings. Example:
5209 when there are two consecutive loops,
5220 the dependence relation cannot be captured by the distance
5225 loop_nest
->safe_push (loop
);
5227 return find_loop_nest_1 (loop
->inner
, loop_nest
);
5231 /* Return false when the LOOP is not well nested. Otherwise return
5232 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
5233 contain the loops from the outermost to the innermost, as they will
5234 appear in the classic distance vector. */
5237 find_loop_nest (struct loop
*loop
, vec
<loop_p
> *loop_nest
)
5239 loop_nest
->safe_push (loop
);
5241 return find_loop_nest_1 (loop
->inner
, loop_nest
);
5245 /* Returns true when the data dependences have been computed, false otherwise.
5246 Given a loop nest LOOP, the following vectors are returned:
5247 DATAREFS is initialized to all the array elements contained in this loop,
5248 DEPENDENCE_RELATIONS contains the relations between the data references.
5249 Compute read-read and self relations if
5250 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
5253 compute_data_dependences_for_loop (struct loop
*loop
,
5254 bool compute_self_and_read_read_dependences
,
5255 vec
<loop_p
> *loop_nest
,
5256 vec
<data_reference_p
> *datarefs
,
5257 vec
<ddr_p
> *dependence_relations
)
5261 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
5263 /* If the loop nest is not well formed, or one of the data references
5264 is not computable, give up without spending time to compute other
5267 || !find_loop_nest (loop
, loop_nest
)
5268 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
5269 || !compute_all_dependences (*datarefs
, dependence_relations
, *loop_nest
,
5270 compute_self_and_read_read_dependences
))
5273 if (dump_file
&& (dump_flags
& TDF_STATS
))
5275 fprintf (dump_file
, "Dependence tester statistics:\n");
5277 fprintf (dump_file
, "Number of dependence tests: %d\n",
5278 dependence_stats
.num_dependence_tests
);
5279 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
5280 dependence_stats
.num_dependence_dependent
);
5281 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
5282 dependence_stats
.num_dependence_independent
);
5283 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
5284 dependence_stats
.num_dependence_undetermined
);
5286 fprintf (dump_file
, "Number of subscript tests: %d\n",
5287 dependence_stats
.num_subscript_tests
);
5288 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
5289 dependence_stats
.num_subscript_undetermined
);
5290 fprintf (dump_file
, "Number of same subscript function: %d\n",
5291 dependence_stats
.num_same_subscript_function
);
5293 fprintf (dump_file
, "Number of ziv tests: %d\n",
5294 dependence_stats
.num_ziv
);
5295 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
5296 dependence_stats
.num_ziv_dependent
);
5297 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
5298 dependence_stats
.num_ziv_independent
);
5299 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
5300 dependence_stats
.num_ziv_unimplemented
);
5302 fprintf (dump_file
, "Number of siv tests: %d\n",
5303 dependence_stats
.num_siv
);
5304 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
5305 dependence_stats
.num_siv_dependent
);
5306 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
5307 dependence_stats
.num_siv_independent
);
5308 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
5309 dependence_stats
.num_siv_unimplemented
);
5311 fprintf (dump_file
, "Number of miv tests: %d\n",
5312 dependence_stats
.num_miv
);
5313 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
5314 dependence_stats
.num_miv_dependent
);
5315 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
5316 dependence_stats
.num_miv_independent
);
5317 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
5318 dependence_stats
.num_miv_unimplemented
);
5324 /* Free the memory used by a data dependence relation DDR. */
5327 free_dependence_relation (struct data_dependence_relation
*ddr
)
5332 if (DDR_SUBSCRIPTS (ddr
).exists ())
5333 free_subscripts (DDR_SUBSCRIPTS (ddr
));
5334 DDR_DIST_VECTS (ddr
).release ();
5335 DDR_DIR_VECTS (ddr
).release ();
5340 /* Free the memory used by the data dependence relations from
5341 DEPENDENCE_RELATIONS. */
5344 free_dependence_relations (vec
<ddr_p
> dependence_relations
)
5347 struct data_dependence_relation
*ddr
;
5349 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
5351 free_dependence_relation (ddr
);
5353 dependence_relations
.release ();
5356 /* Free the memory used by the data references from DATAREFS. */
5359 free_data_refs (vec
<data_reference_p
> datarefs
)
5362 struct data_reference
*dr
;
5364 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
5366 datarefs
.release ();
5369 /* Common routine implementing both dr_direction_indicator and
5370 dr_zero_step_indicator. Return USEFUL_MIN if the indicator is known
5371 to be >= USEFUL_MIN and -1 if the indicator is known to be negative.
5372 Return the step as the indicator otherwise. */
5375 dr_step_indicator (struct data_reference
*dr
, int useful_min
)
5377 tree step
= DR_STEP (dr
);
5379 /* Look for cases where the step is scaled by a positive constant
5380 integer, which will often be the access size. If the multiplication
5381 doesn't change the sign (due to overflow effects) then we can
5382 test the unscaled value instead. */
5383 if (TREE_CODE (step
) == MULT_EXPR
5384 && TREE_CODE (TREE_OPERAND (step
, 1)) == INTEGER_CST
5385 && tree_int_cst_sgn (TREE_OPERAND (step
, 1)) > 0)
5387 tree factor
= TREE_OPERAND (step
, 1);
5388 step
= TREE_OPERAND (step
, 0);
5390 /* Strip widening and truncating conversions as well as nops. */
5391 if (CONVERT_EXPR_P (step
)
5392 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (step
, 0))))
5393 step
= TREE_OPERAND (step
, 0);
5394 tree type
= TREE_TYPE (step
);
5396 /* Get the range of step values that would not cause overflow. */
5397 widest_int minv
= (wi::to_widest (TYPE_MIN_VALUE (ssizetype
))
5398 / wi::to_widest (factor
));
5399 widest_int maxv
= (wi::to_widest (TYPE_MAX_VALUE (ssizetype
))
5400 / wi::to_widest (factor
));
5402 /* Get the range of values that the unconverted step actually has. */
5403 wide_int step_min
, step_max
;
5404 if (TREE_CODE (step
) != SSA_NAME
5405 || get_range_info (step
, &step_min
, &step_max
) != VR_RANGE
)
5407 step_min
= wi::to_wide (TYPE_MIN_VALUE (type
));
5408 step_max
= wi::to_wide (TYPE_MAX_VALUE (type
));
5411 /* Check whether the unconverted step has an acceptable range. */
5412 signop sgn
= TYPE_SIGN (type
);
5413 if (wi::les_p (minv
, widest_int::from (step_min
, sgn
))
5414 && wi::ges_p (maxv
, widest_int::from (step_max
, sgn
)))
5416 if (wi::ge_p (step_min
, useful_min
, sgn
))
5417 return ssize_int (useful_min
);
5418 else if (wi::lt_p (step_max
, 0, sgn
))
5419 return ssize_int (-1);
5421 return fold_convert (ssizetype
, step
);
5424 return DR_STEP (dr
);
5427 /* Return a value that is negative iff DR has a negative step. */
5430 dr_direction_indicator (struct data_reference
*dr
)
5432 return dr_step_indicator (dr
, 0);
5435 /* Return a value that is zero iff DR has a zero step. */
5438 dr_zero_step_indicator (struct data_reference
*dr
)
5440 return dr_step_indicator (dr
, 1);
5443 /* Return true if DR is known to have a nonnegative (but possibly zero)
5447 dr_known_forward_stride_p (struct data_reference
*dr
)
5449 tree indicator
= dr_direction_indicator (dr
);
5450 tree neg_step_val
= fold_binary (LT_EXPR
, boolean_type_node
,
5451 fold_convert (ssizetype
, indicator
),
5453 return neg_step_val
&& integer_zerop (neg_step_val
);