GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This pass walks a given loop structure searching for array
references. The information about the array accesses is recorded
/* Returns true iff A divides B. */
static inline bool
-tree_fold_divides_p (tree a, tree b)
+tree_fold_divides_p (const_tree a, const_tree b)
{
gcc_assert (TREE_CODE (a) == INTEGER_CST);
gcc_assert (TREE_CODE (b) == INTEGER_CST);
/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
will be ssizetype. */
-static void
+void
split_constant_offset (tree exp, tree *var, tree *off)
{
tree type = TREE_TYPE (exp), otype;
{
split_constant_offset (poffset, &poffset, &off1);
off0 = size_binop (PLUS_EXPR, off0, off1);
- base = fold_build2 (PLUS_EXPR, TREE_TYPE (base),
- base,
- fold_convert (TREE_TYPE (base), poffset));
+ if (POINTER_TYPE_P (TREE_TYPE (base)))
+ base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base),
+ base, fold_convert (sizetype, poffset));
+ else
+ base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
+ fold_convert (TREE_TYPE (base), poffset));
}
- *var = fold_convert (type, base);
+ var0 = fold_convert (type, base);
+
+ /* If variable length types are involved, punt, otherwise casts
+ might be converted into ARRAY_REFs in gimplify_conversion.
+ To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
+ possibly no longer appears in current GIMPLE, might resurface.
+ This perhaps could run
+ if (TREE_CODE (var0) == NOP_EXPR
+ || TREE_CODE (var0) == CONVERT_EXPR)
+ {
+ gimplify_conversion (&var0);
+ // Attempt to fill in any within var0 found ARRAY_REF's
+ // element size from corresponding op embedded ARRAY_REF,
+ // if unsuccessful, just punt.
+ } */
+ while (POINTER_TYPE_P (type))
+ type = TREE_TYPE (type);
+ if (int_size_in_bytes (type) < 0)
+ break;
+
+ *var = var0;
*off = off0;
return;
}
+ case SSA_NAME:
+ {
+ tree def_stmt = SSA_NAME_DEF_STMT (exp);
+ if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT)
+ {
+ tree def_stmt_rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
+
+ if (!TREE_SIDE_EFFECTS (def_stmt_rhs)
+ && EXPR_P (def_stmt_rhs)
+ && !REFERENCE_CLASS_P (def_stmt_rhs)
+ && !get_call_expr_in (def_stmt_rhs))
+ {
+ split_constant_offset (def_stmt_rhs, &var0, &off0);
+ var0 = fold_convert (type, var0);
+ *var = var0;
+ *off = off0;
+ return;
+ }
+ }
+ break;
+ }
+
default:
break;
}
&& affine_function_constant_p (fn));
}
+/* Returns a signed integer type with the largest precision from TA
+ and TB. */
+
+static tree
+signed_type_for_types (tree ta, tree tb)
+{
+ if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
+ return signed_type_for (ta);
+ else
+ return signed_type_for (tb);
+}
+
/* Applies operation OP on affine functions FNA and FNB, and returns the
result. */
ret = VEC_alloc (tree, heap, m);
for (i = 0; i < n; i++)
- VEC_quick_push (tree, ret,
- fold_build2 (op, integer_type_node,
- VEC_index (tree, fna, i),
- VEC_index (tree, fnb, i)));
+ {
+ tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)),
+ TREE_TYPE (VEC_index (tree, fnb, i)));
+
+ VEC_quick_push (tree, ret,
+ fold_build2 (op, type,
+ VEC_index (tree, fna, i),
+ VEC_index (tree, fnb, i)));
+ }
for (; VEC_iterate (tree, fna, i, coef); i++)
VEC_quick_push (tree, ret,
- fold_build2 (op, integer_type_node,
+ fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
coef, integer_zero_node));
for (; VEC_iterate (tree, fnb, i, coef); i++)
VEC_quick_push (tree, ret,
- fold_build2 (op, integer_type_node,
+ fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
integer_zero_node, coef));
return ret;
/* Returns true if the address of OBJ is invariant in LOOP. */
static bool
-object_address_invariant_in_loop_p (struct loop *loop, tree obj)
+object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
{
while (handled_component_p (obj))
{
true otherwise. */
static bool
-dr_may_alias_p (struct data_reference *a, struct data_reference *b)
+dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
{
- tree addr_a = DR_BASE_ADDRESS (a);
- tree addr_b = DR_BASE_ADDRESS (b);
- tree type_a, type_b;
- tree decl_a = NULL_TREE, decl_b = NULL_TREE;
+ const_tree addr_a = DR_BASE_ADDRESS (a);
+ const_tree addr_b = DR_BASE_ADDRESS (b);
+ const_tree type_a, type_b;
+ const_tree decl_a = NULL_TREE, decl_b = NULL_TREE;
/* If the sets of virtual operands are disjoint, the memory references do not
alias. */
DDR_A (res) = a;
DDR_B (res) = b;
DDR_LOOP_NEST (res) = NULL;
+ DDR_REVERSED_P (res) = false;
+ DDR_SUBSCRIPTS (res) = NULL;
+ DDR_DIR_VECTS (res) = NULL;
+ DDR_DIST_VECTS (res) = NULL;
if (a == NULL || b == NULL)
{
DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
DDR_LOOP_NEST (res) = loop_nest;
DDR_INNER_LOOP (res) = 0;
- DDR_DIR_VECTS (res) = NULL;
- DDR_DIST_VECTS (res) = NULL;
for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
{
DDR_ARE_DEPENDENT (ddr) = chrec;
free_subscripts (DDR_SUBSCRIPTS (ddr));
+ DDR_SUBSCRIPTS (ddr) = NULL;
}
/* The dependence relation DDR cannot be represented by a distance
variables, i.e., if the ZIV (Zero Index Variable) test is true. */
static inline bool
-ziv_subscript_p (tree chrec_a,
- tree chrec_b)
+ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
{
return (evolution_function_is_constant_p (chrec_a)
&& evolution_function_is_constant_p (chrec_b));
variable, i.e., if the SIV (Single Index Variable) test is true. */
static bool
-siv_subscript_p (tree chrec_a,
- tree chrec_b)
+siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
{
if ((evolution_function_is_constant_p (chrec_a)
&& evolution_function_is_univariate_p (chrec_b))
conflict_function **overlaps_b,
tree *last_conflicts)
{
- tree difference;
+ tree type, difference;
dependence_stats.num_ziv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_ziv_subscript \n");
-
- chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
- chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
- difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
+
+ type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+ chrec_a = chrec_convert (type, chrec_a, NULL_TREE);
+ chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
+ difference = chrec_fold_minus (type, chrec_a, chrec_b);
switch (TREE_CODE (difference))
{
tree *last_conflicts)
{
bool value0, value1, value2;
- tree difference, tmp;
+ tree type, difference, tmp;
- chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
- chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
- difference = chrec_fold_minus
- (integer_type_node, initial_condition (chrec_b), chrec_a);
+ type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+ chrec_a = chrec_convert (type, chrec_a, NULL_TREE);
+ chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
+ difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
if (!chrec_is_positive (initial_condition (difference), &value0))
{
struct loop *loop = get_chrec_loop (chrec_b);
*overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
- fold_build1 (ABS_EXPR,
- integer_type_node,
- difference),
+ tmp = fold_build2 (EXACT_DIV_EXPR, type,
+ fold_build1 (ABS_EXPR, type, difference),
CHREC_RIGHT (chrec_b));
*overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
*last_conflicts = integer_one_node;
/* Perform weak-zero siv test to see if overlap is
outside the loop bounds. */
- numiter = estimated_loop_iterations_int (loop, true);
+ numiter = estimated_loop_iterations_int (loop, false);
if (numiter >= 0
&& compare_tree_int (tmp, numiter) > 0)
struct loop *loop = get_chrec_loop (chrec_b);
*overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- tmp = fold_build2 (EXACT_DIV_EXPR,
- integer_type_node, difference,
+ tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
CHREC_RIGHT (chrec_b));
*overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
*last_conflicts = integer_one_node;
/* Perform weak-zero siv test to see if overlap is
outside the loop bounds. */
- numiter = estimated_loop_iterations_int (loop, true);
+ numiter = estimated_loop_iterations_int (loop, false);
if (numiter >= 0
&& compare_tree_int (tmp, numiter) > 0)
/* Helper recursive function for initializing the matrix A. Returns
the initial value of CHREC. */
-static int
+static HOST_WIDE_INT
initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
{
+ tree type;
+
gcc_assert (chrec);
+ type = TREE_TYPE (chrec);
if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
- return int_cst_value (chrec);
-
- A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
+ return tree_low_cst (chrec, TYPE_UNSIGNED (type)
+ && !(TREE_CODE (type) == INTEGER_TYPE
+ && TYPE_IS_SIZETYPE (type)));
+
+ type = TREE_TYPE (CHREC_RIGHT (chrec));
+ A[index][0] = mult * tree_low_cst (CHREC_RIGHT (chrec),
+ TYPE_UNSIGNED (type)
+ && !(TREE_CODE (type) == INTEGER_TYPE
+ && TYPE_IS_SIZETYPE (type)));
return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
}
step_overlaps_a = step_b / gcd_steps_a_b;
step_overlaps_b = step_a / gcd_steps_a_b;
- tau2 = FLOOR_DIV (niter, step_overlaps_a);
- tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
- last_conflict = tau2;
+ if (niter > 0)
+ {
+ tau2 = FLOOR_DIV (niter, step_overlaps_a);
+ tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
+ last_conflict = tau2;
+ *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+ }
+ else
+ *last_conflicts = chrec_dont_know;
*overlaps_a = affine_fn_univar (integer_zero_node, dim,
build_int_cst (NULL_TREE,
*overlaps_b = affine_fn_univar (integer_zero_node, dim,
build_int_cst (NULL_TREE,
step_overlaps_b));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
}
else
step_y = int_cst_value (CHREC_RIGHT (chrec_a));
step_z = int_cst_value (CHREC_RIGHT (chrec_b));
- niter_x = estimated_loop_iterations_int
- (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
- niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true);
- niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true);
+ niter_x =
+ estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)),
+ false);
+ niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false);
+ niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false);
if (niter_x < 0 || niter_y < 0 || niter_z < 0)
{
tree *last_conflicts)
{
unsigned nb_vars_a, nb_vars_b, dim;
- int init_a, init_b, gamma, gcd_alpha_beta;
- int tau1, tau2;
+ HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
lambda_matrix A, U, S;
if (eq_evolutions_p (chrec_a, chrec_b))
{
if (nb_vars_a == 1 && nb_vars_b == 1)
{
- int step_a, step_b;
+ HOST_WIDE_INT step_a, step_b;
HOST_WIDE_INT niter, niter_a, niter_b;
affine_fn ova, ovb;
- niter_a = estimated_loop_iterations_int
- (get_chrec_loop (chrec_a), true);
- niter_b = estimated_loop_iterations_int
- (get_chrec_loop (chrec_b), true);
- if (niter_a < 0 || niter_b < 0)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- goto end_analyze_subs_aa;
- }
-
+ niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
+ false);
+ niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
+ false);
niter = MIN (niter_a, niter_b);
-
step_a = int_cst_value (CHREC_RIGHT (chrec_a));
step_b = int_cst_value (CHREC_RIGHT (chrec_b));
| x0 = i0 + i1 * t,
| y0 = j0 + j1 * t. */
-
- int i0, j0, i1, j1;
-
- /* X0 and Y0 are the first iterations for which there is a
- dependence. X0, Y0 are two solutions of the Diophantine
- equation: chrec_a (X0) = chrec_b (Y0). */
- int x0, y0;
- int niter, niter_a, niter_b;
-
- niter_a = estimated_loop_iterations_int
- (get_chrec_loop (chrec_a), true);
- niter_b = estimated_loop_iterations_int
- (get_chrec_loop (chrec_b), true);
-
- if (niter_a < 0 || niter_b < 0)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- goto end_analyze_subs_aa;
- }
-
- niter = MIN (niter_a, niter_b);
+ HOST_WIDE_INT i0, j0, i1, j1;
i0 = U[0][0] * gamma / gcd_alpha_beta;
j0 = U[0][1] * gamma / gcd_alpha_beta;
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
+ goto end_analyze_subs_aa;
}
- else
+ if (i1 > 0 && j1 > 0)
{
- if (i1 > 0)
+ HOST_WIDE_INT niter_a = estimated_loop_iterations_int
+ (get_chrec_loop (chrec_a), false);
+ HOST_WIDE_INT niter_b = estimated_loop_iterations_int
+ (get_chrec_loop (chrec_b), false);
+ HOST_WIDE_INT niter = MIN (niter_a, niter_b);
+
+ /* (X0, Y0) is a solution of the Diophantine equation:
+ "chrec_a (X0) = chrec_b (Y0)". */
+ HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
+ CEIL (-j0, j1));
+ HOST_WIDE_INT x0 = i1 * tau1 + i0;
+ HOST_WIDE_INT y0 = j1 * tau1 + j0;
+
+ /* (X1, Y1) is the smallest positive solution of the eq
+ "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
+ first conflict occurs. */
+ HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
+ HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
+ HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
+
+ if (niter > 0)
{
- tau1 = CEIL (-i0, i1);
- tau2 = FLOOR_DIV (niter - i0, i1);
+ HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
+ FLOOR_DIV (niter - j0, j1));
+ HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
- if (j1 > 0)
+ /* If the overlap occurs outside of the bounds of the
+ loop, there is no dependence. */
+ if (x1 > niter || y1 > niter)
{
- int last_conflict, min_multiple;
- tau1 = MAX (tau1, CEIL (-j0, j1));
- tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
-
- x0 = i1 * tau1 + i0;
- y0 = j1 * tau1 + j0;
-
- /* At this point (x0, y0) is one of the
- solutions to the Diophantine equation. The
- next step has to compute the smallest
- positive solution: the first conflicts. */
- min_multiple = MIN (x0 / i1, y0 / j1);
- x0 -= i1 * min_multiple;
- y0 -= j1 * min_multiple;
-
- tau1 = (x0 - i0)/i1;
- last_conflict = tau2 - tau1;
-
- /* If the overlap occurs outside of the bounds of the
- loop, there is no dependence. */
- if (x0 > niter || y0 > niter)
- {
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- }
- else
- {
- *overlaps_a
- = conflict_fn (1,
- affine_fn_univar (build_int_cst (NULL_TREE, x0),
- 1,
- build_int_cst (NULL_TREE, i1)));
- *overlaps_b
- = conflict_fn (1,
- affine_fn_univar (build_int_cst (NULL_TREE, y0),
- 1,
- build_int_cst (NULL_TREE, j1)));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
- }
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ goto end_analyze_subs_aa;
}
else
- {
- /* FIXME: For the moment, the upper bound of the
- iteration domain for j is not checked. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- }
+ *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
}
-
else
- {
- /* FIXME: For the moment, the upper bound of the
- iteration domain for i is not checked. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- }
+ *last_conflicts = chrec_dont_know;
+
+ *overlaps_a
+ = conflict_fn (1,
+ affine_fn_univar (build_int_cst (NULL_TREE, x1),
+ 1,
+ build_int_cst (NULL_TREE, i1)));
+ *overlaps_b
+ = conflict_fn (1,
+ affine_fn_univar (build_int_cst (NULL_TREE, y1),
+ 1,
+ build_int_cst (NULL_TREE, j1)));
+ }
+ else
+ {
+ /* FIXME: For the moment, the upper bound of the
+ iteration domain for i and j is not checked. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
}
}
else
*last_conflicts = chrec_dont_know;
}
}
-
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
analyze_subscript_affine_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b,
last_conflicts);
- /* FIXME: The number of iterations is a symbolic expression.
- Compute it properly. */
- *last_conflicts = chrec_dont_know;
if (CF_NOT_KNOWN_P (*overlaps_a)
|| CF_NOT_KNOWN_P (*overlaps_b))
of CHREC does not divide CST, false otherwise. */
static bool
-gcd_of_steps_may_divide_p (tree chrec, tree cst)
+gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
{
HOST_WIDE_INT cd = 0, val;
tree step;
variables. In the MIV case we have to solve a Diophantine
equation with 2*n variables (if the subscript uses n IVs).
*/
- tree difference;
+ tree type, difference;
+
dependence_stats.num_miv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_miv_subscript \n");
- chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
- chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
- difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
+ type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+ chrec_a = chrec_convert (type, chrec_a, NULL_TREE);
+ chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
+ difference = chrec_fold_minus (type, chrec_a, chrec_b);
if (eq_evolutions_p (chrec_a, chrec_b))
{
same access functions. */
static bool
-same_access_functions (struct data_dependence_relation *ddr)
+same_access_functions (const struct data_dependence_relation *ddr)
{
unsigned i;
/* Return true when the DDR contains only constant access functions. */
static bool
-constant_access_functions (struct data_dependence_relation *ddr)
+constant_access_functions (const struct data_dependence_relation *ddr)
{
unsigned i;
return true;
}
-
/* Helper function for the case where DDR_A and DDR_B are the same
- multivariate access function. */
+ multivariate access function with a constant step. For an example
+ see pr34635-1.c. */
static void
add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
lambda_vector dist_v;
int v1, v2, cd;
- /* Polynomials with more than 2 variables are not handled yet. */
- if (TREE_CODE (c_0) != INTEGER_CST)
+ /* Polynomials with more than 2 variables are not handled yet. When
+ the evolution steps are parameters, it is not possible to
+ represent the dependence using classical distance vectors. */
+ if (TREE_CODE (c_0) != INTEGER_CST
+ || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
+ || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
{
- DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+ DDR_AFFINE_P (ddr) = false;
return;
}
return;
}
- add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
+ access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
+
+ if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
+ add_multivariate_self_dist (ddr, access_fun);
+ else
+ /* The evolution step is not constant: it varies in
+ the outer loop, so this cannot be represented by a
+ distance vector. For example in pr34635.c the
+ evolution is {0, +, {0, +, 4}_1}_2. */
+ DDR_AFFINE_P (ddr) = false;
+
return;
}
lambda_vector dist_v;
if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return true;
+ return false;
if (same_access_functions (ddr))
{
if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
{
lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- loop_nest);
+ if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ loop_nest))
+ return false;
compute_subscript_distance (ddr);
- build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- save_v, &init_b, &index_carry);
+ if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ save_v, &init_b, &index_carry))
+ return false;
save_dist_v (ddr, save_v);
+ DDR_REVERSED_P (ddr) = true;
/* In this case there is a dependence forward for all the
outer loops:
{
lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
- save_dist_v (ddr, save_v);
if (DDR_NB_LOOPS (ddr) > 1)
{
lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- loop_nest);
+ if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
+ DDR_A (ddr), loop_nest))
+ return false;
compute_subscript_distance (ddr);
- build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- opposite_v, &init_b, &index_carry);
+ if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ opposite_v, &init_b,
+ &index_carry))
+ return false;
+ save_dist_v (ddr, save_v);
add_outer_distances (ddr, dist_v, index_carry);
add_outer_distances (ddr, opposite_v, index_carry);
}
+ else
+ save_dist_v (ddr, save_v);
}
}
else
else
{
+ if (SUB_CONFLICTS_IN_A (subscript))
+ free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
+ if (SUB_CONFLICTS_IN_B (subscript))
+ free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
+
SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
SUB_LAST_CONFLICT (subscript) = last_conflicts;
constant with respect to LOOP_NEST. */
static bool
-access_functions_are_affine_or_constant_p (struct data_reference *a,
- struct loop *loop_nest)
+access_functions_are_affine_or_constant_p (const struct data_reference *a,
+ const struct loop *loop_nest)
{
unsigned int i;
VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
omega_pb pb, bool *maybe_dependent)
{
int eq;
- tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE);
- tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE);
- tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b);
+ tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
+ TREE_TYPE (access_fun_b));
+ tree fun_a = chrec_convert (type, access_fun_a, NULL_TREE);
+ tree fun_b = chrec_convert (type, access_fun_b, NULL_TREE);
+ tree difference = chrec_fold_minus (type, fun_a, fun_b);
/* When the fun_a - fun_b is not constant, the dependence is not
captured by the classic distance vector representation. */
return true;
}
- fun_b = chrec_fold_multiply (integer_type_node, fun_b,
- integer_minus_one_node);
+ fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
eq = omega_add_zero_eq (pb, omega_black);
if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
for (i = 0; i <= DDR_INNER_LOOP (ddr)
&& VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
{
- HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, true);
+ HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
/* 0 <= loop_x */
ineq = omega_add_zero_geq (pb, omega_black);
for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
i++)
{
+ if (SUB_CONFLICTS_IN_A (subscript))
+ free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
+ if (SUB_CONFLICTS_IN_B (subscript))
+ free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
+
/* The accessed index overlaps for each iteration. */
SUB_CONFLICTS_IN_A (subscript)
- = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ = conflict_fn (1, affine_fn_cst (integer_zero_node));
SUB_CONFLICTS_IN_B (subscript)
- = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ = conflict_fn (1, affine_fn_cst (integer_zero_node));
SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
}
op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
if (DECL_P (*op1)
- || REFERENCE_CLASS_P (*op1))
+ || (REFERENCE_CLASS_P (*op1) && get_base_address (*op1)))
{
ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
ref->pos = op1;
}
if (DECL_P (*op0)
- || REFERENCE_CLASS_P (*op0))
+ || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
{
ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
ref->pos = op0;
op0 = &CALL_EXPR_ARG (call, i);
if (DECL_P (*op0)
- || REFERENCE_CLASS_P (*op0))
+ || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
{
ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
ref->pos = op0;
if (ddr == NULL)
return;
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
+ if (DDR_SUBSCRIPTS (ddr))
free_subscripts (DDR_SUBSCRIPTS (ddr));
+ if (DDR_DIST_VECTS (ddr))
+ VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
+ if (DDR_DIR_VECTS (ddr))
+ VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
free (ddr);
}
VEC_free (data_reference_p, heap, datarefs);
}
+\f
+
+/* Returns the index of STMT in RDG. */
+
+static int
+find_vertex_for_stmt (const struct graph *rdg, const_tree stmt)
+{
+ int i;
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ if (RDGV_STMT (&(rdg->vertices[i])) == stmt)
+ return i;
+
+ gcc_unreachable ();
+ return 0;
+}
+
+/* Creates an edge in RDG for each distance vector from DDR. */
+
+static void
+create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
+{
+ int va, vb;
+ data_reference_p dra;
+ data_reference_p drb;
+ struct graph_edge *e;
+
+ if (DDR_REVERSED_P (ddr))
+ {
+ dra = DDR_B (ddr);
+ drb = DDR_A (ddr);
+ }
+ else
+ {
+ dra = DDR_A (ddr);
+ drb = DDR_B (ddr);
+ }
+
+ va = find_vertex_for_stmt (rdg, DR_STMT (dra));
+ vb = find_vertex_for_stmt (rdg, DR_STMT (drb));
+
+ e = add_edge (rdg, va, vb);
+ e->data = XNEW (struct rdg_edge);
+
+ /* Determines the type of the data dependence. */
+ if (DR_IS_READ (dra) && DR_IS_READ (drb))
+ RDGE_TYPE (e) = input_dd;
+ else if (!DR_IS_READ (dra) && !DR_IS_READ (drb))
+ RDGE_TYPE (e) = output_dd;
+ else if (!DR_IS_READ (dra) && DR_IS_READ (drb))
+ RDGE_TYPE (e) = flow_dd;
+ else if (DR_IS_READ (dra) && !DR_IS_READ (drb))
+ RDGE_TYPE (e) = anti_dd;
+}
+
+/* Creates dependence edges in RDG for all the uses of DEF. IDEF is
+ the index of DEF in RDG. */
+
+static void
+create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
+{
+ use_operand_p imm_use_p;
+ imm_use_iterator iterator;
+
+ FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
+ {
+ int use = find_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
+ struct graph_edge *e = add_edge (rdg, idef, use);
+
+ e->data = XNEW (struct rdg_edge);
+ RDGE_TYPE (e) = flow_dd;
+ }
+}
+
+/* Creates the edges of the reduced dependence graph RDG. */
+
+static void
+create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
+{
+ int i;
+ struct data_dependence_relation *ddr;
+ def_operand_p def_p;
+ ssa_op_iter iter;
+
+ for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ create_rdg_edge_for_ddr (rdg, ddr);
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ FOR_EACH_PHI_OR_STMT_DEF (def_p, RDGV_STMT (&(rdg->vertices[i])),
+ iter, SSA_OP_ALL_DEFS)
+ create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
+}
+
+/* Build the vertices of the reduced dependence graph RDG. */
+
+static void
+create_rdg_vertices (struct graph *rdg, VEC (tree, heap) *stmts)
+{
+ int i;
+ tree s;
+
+ for (i = 0; VEC_iterate (tree, stmts, i, s); i++)
+ {
+ struct vertex *v = &(rdg->vertices[i]);
+
+ v->data = XNEW (struct rdg_vertex);
+ RDGV_STMT (v) = s;
+ }
+}
+
+/* Initialize STMTS with all the statements and PHI nodes of LOOP. */
+
+static void
+stmts_from_loop (struct loop *loop, VEC (tree, heap) **stmts)
+{
+ unsigned int i;
+ basic_block *bbs = get_loop_body_in_dom_order (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ tree phi;
+ basic_block bb = bbs[i];
+ block_stmt_iterator bsi;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ VEC_safe_push (tree, heap, *stmts, phi);
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ VEC_safe_push (tree, heap, *stmts, bsi_stmt (bsi));
+ }
+
+ free (bbs);
+}
+
+/* Returns true when all the dependences are computable. */
+
+static bool
+known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
+{
+ ddr_p ddr;
+ unsigned int i;
+
+ for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ return false;
+
+ return true;
+}
+
+/* Build a Reduced Dependence Graph with one vertex per statement of the
+ loop nest and one edge per data dependence or scalar dependence. */
+
+struct graph *
+build_rdg (struct loop *loop)
+{
+ int nb_data_refs = 10;
+ struct graph *rdg = NULL;
+ VEC (ddr_p, heap) *dependence_relations;
+ VEC (data_reference_p, heap) *datarefs;
+ VEC (tree, heap) *stmts = VEC_alloc (tree, heap, 10);
+
+ dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
+ datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
+ compute_data_dependences_for_loop (loop,
+ false,
+ &datarefs,
+ &dependence_relations);
+
+ if (!known_dependences_p (dependence_relations))
+ goto end_rdg;
+
+ stmts_from_loop (loop, &stmts);
+ rdg = new_graph (VEC_length (tree, stmts));
+ create_rdg_vertices (rdg, stmts);
+ create_rdg_edges (rdg, dependence_relations);
+
+ end_rdg:
+ free_dependence_relations (dependence_relations);
+ free_data_refs (datarefs);
+ VEC_free (tree, heap, stmts);
+
+ return rdg;
+}
OSDN Git Service
