return true;
}
+/* Returns true if FN is the zero constant function. */
+
+static bool
+affine_function_zero_p (affine_fn fn)
+{
+ return (integer_zerop (affine_function_base (fn))
+ && affine_function_constant_p (fn));
+}
+
/* Applies operation OP on affine functions FNA and FNB, and returns the
result. */
fprintf (dump_file, ")\n");
}
-/* Return true when the property can be computed. RES should contain
- true when calling the first time this function, then it is set to
- false when one of the evolution steps of an affine CHREC does not
- divide the constant CST. */
+/* Returns false if we can prove that the greatest common divisor of the steps
+ of CHREC does not divide CST, false otherwise. */
static bool
-chrec_steps_divide_constant_p (tree chrec,
- tree cst,
- bool *res)
+gcd_of_steps_may_divide_p (tree chrec, tree cst)
{
- switch (TREE_CODE (chrec))
- {
- case POLYNOMIAL_CHREC:
- if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
- {
- if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
- /* Keep RES to true, and iterate on other dimensions. */
- return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
-
- *res = false;
- return true;
- }
- else
- /* When the step is a parameter the result is undetermined. */
- return false;
+ HOST_WIDE_INT cd = 0, val;
+ tree step;
- default:
- /* On the initial condition, return true. */
- return true;
+ if (!host_integerp (cst, 0))
+ return true;
+ val = tree_low_cst (cst, 0);
+
+ while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
+ {
+ step = CHREC_RIGHT (chrec);
+ if (!host_integerp (step, 0))
+ return true;
+ cd = gcd (cd, tree_low_cst (step, 0));
+ chrec = CHREC_LEFT (chrec);
}
+
+ return val % cd == 0;
}
/* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
variables. In the MIV case we have to solve a Diophantine
equation with 2*n variables (if the subscript uses n IVs).
*/
- bool divide_p = true;
tree difference;
dependence_stats.num_miv++;
if (dump_file && (dump_flags & TDF_DETAILS))
else if (evolution_function_is_constant_p (difference)
/* For the moment, the following is verified:
evolution_function_is_affine_multivariate_p (chrec_a) */
- && chrec_steps_divide_constant_p (chrec_a, difference, ÷_p)
- && !divide_p)
+ && !gcd_of_steps_may_divide_p (chrec_a, difference))
{
/* testsuite/.../ssa-chrec-33.c
{{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
- The difference is 1, and the evolution steps are equal to 2,
- consequently there are no overlapping elements. */
+ The difference is 1, and all the evolution steps are multiples
+ of 2, consequently there are no overlapping elements. */
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
return true;
}
+/* Return true when the DDR contains only constant access functions. */
+
+static bool
+constant_access_functions (struct data_dependence_relation *ddr)
+{
+ unsigned i;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
+ || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
+ return false;
+
+ return true;
+}
+
+
/* Helper function for the case where DDR_A and DDR_B are the same
multivariate access function. */
add_outer_distances (ddr, dist_v, index_carry);
}
+static void
+insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
+{
+ lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+ dist_v[DDR_INNER_LOOP (ddr)] = 1;
+ save_dist_v (ddr, dist_v);
+}
+
+/* Adds a unit distance vector to DDR when there is a 0 overlap. This
+ is the case for example when access functions are the same and
+ equal to a constant, as in:
+
+ | loop_1
+ | A[3] = ...
+ | ... = A[3]
+ | endloop_1
+
+ in which case the distance vectors are (0) and (1). */
+
+static void
+add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
+{
+ unsigned i, j;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ subscript_p sub = DDR_SUBSCRIPT (ddr, i);
+ conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
+ conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
+
+ for (j = 0; j < ca->n; j++)
+ if (affine_function_zero_p (ca->fns[j]))
+ {
+ insert_innermost_unit_dist_vector (ddr);
+ return;
+ }
+
+ for (j = 0; j < cb->n; j++)
+ if (affine_function_zero_p (cb->fns[j]))
+ {
+ insert_innermost_unit_dist_vector (ddr);
+ return;
+ }
+ }
+}
+
/* Compute the classic per loop distance vector. DDR is the data
dependence relation to build a vector from. Return false when fail
to represent the data dependence as a distance vector. */
dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
save_dist_v (ddr, dist_v);
+ if (constant_access_functions (ddr))
+ add_distance_for_zero_overlaps (ddr);
+
if (DDR_NB_LOOPS (ddr) > 1)
add_other_self_distances (ddr);
OSDN Git Service
