+ tree type, difference;
+
+ dependence_stats.num_miv++;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_miv_subscript \n");
+
+ 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))
+ {
+ /* Access functions are the same: all the elements are accessed
+ in the same order. */
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *last_conflicts = estimated_loop_iterations_tree
+ (get_chrec_loop (chrec_a), true);
+ dependence_stats.num_miv_dependent++;
+ }
+
+ else if (evolution_function_is_constant_p (difference)
+ /* For the moment, the following is verified:
+ evolution_function_is_affine_multivariate_p (chrec_a,
+ loop_nest->num) */
+ && !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 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;
+ dependence_stats.num_miv_independent++;
+ }
+
+ else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
+ && !chrec_contains_symbols (chrec_a)
+ && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
+ && !chrec_contains_symbols (chrec_b))
+ {
+ /* testsuite/.../ssa-chrec-35.c
+ {0, +, 1}_2 vs. {0, +, 1}_3
+ the overlapping elements are respectively located at iterations:
+ {0, +, 1}_x and {0, +, 1}_x,
+ in other words, we have the equality:
+ {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
+
+ Other examples:
+ {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
+ {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
+
+ {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
+ {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
+ */
+ analyze_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b, last_conflicts);
+
+ if (CF_NOT_KNOWN_P (*overlaps_a)
+ || CF_NOT_KNOWN_P (*overlaps_b))
+ dependence_stats.num_miv_unimplemented++;
+ else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+ || CF_NO_DEPENDENCE_P (*overlaps_b))
+ dependence_stats.num_miv_independent++;
+ else
+ dependence_stats.num_miv_dependent++;
+ }
+
+ else
+ {
+ /* When the analysis is too difficult, answer "don't know". */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
+
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ dependence_stats.num_miv_unimplemented++;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Determines the iterations for which CHREC_A is equal to CHREC_B in
+ with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
+ OVERLAP_ITERATIONS_B are initialized with two functions that
+ describe the iterations that contain conflicting elements.
+
+ Remark: For an integer k >= 0, the following equality is true:
+
+ CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
+*/
+
+static void
+analyze_overlapping_iterations (tree chrec_a,
+ tree chrec_b,
+ conflict_function **overlap_iterations_a,
+ conflict_function **overlap_iterations_b,
+ tree *last_conflicts, struct loop *loop_nest)
+{
+ unsigned int lnn = loop_nest->num;
+
+ dependence_stats.num_subscript_tests++;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(analyze_overlapping_iterations \n");
+ fprintf (dump_file, " (chrec_a = ");
+ print_generic_expr (dump_file, chrec_a, 0);
+ fprintf (dump_file, ")\n (chrec_b = ");
+ print_generic_expr (dump_file, chrec_b, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ if (chrec_a == NULL_TREE
+ || chrec_b == NULL_TREE
+ || chrec_contains_undetermined (chrec_a)
+ || chrec_contains_undetermined (chrec_b))
+ {
+ dependence_stats.num_subscript_undetermined++;
+
+ *overlap_iterations_a = conflict_fn_not_known ();
+ *overlap_iterations_b = conflict_fn_not_known ();
+ }
+
+ /* If they are the same chrec, and are affine, they overlap
+ on every iteration. */
+ else if (eq_evolutions_p (chrec_a, chrec_b)
+ && evolution_function_is_affine_multivariate_p (chrec_a, lnn))
+ {
+ dependence_stats.num_same_subscript_function++;
+ *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *last_conflicts = chrec_dont_know;
+ }
+
+ /* If they aren't the same, and aren't affine, we can't do anything
+ yet. */
+ else if ((chrec_contains_symbols (chrec_a)
+ || chrec_contains_symbols (chrec_b))
+ && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
+ || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
+ {
+ dependence_stats.num_subscript_undetermined++;
+ *overlap_iterations_a = conflict_fn_not_known ();
+ *overlap_iterations_b = conflict_fn_not_known ();
+ }
+
+ else if (ziv_subscript_p (chrec_a, chrec_b))
+ analyze_ziv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b,
+ last_conflicts);
+
+ else if (siv_subscript_p (chrec_a, chrec_b))
+ analyze_siv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b,
+ last_conflicts);
+
+ else
+ analyze_miv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b,
+ last_conflicts, loop_nest);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (overlap_iterations_a = ");
+ dump_conflict_function (dump_file, *overlap_iterations_a);
+ fprintf (dump_file, ")\n (overlap_iterations_b = ");
+ dump_conflict_function (dump_file, *overlap_iterations_b);
+ fprintf (dump_file, ")\n");
+ fprintf (dump_file, ")\n");
+ }
+}
+
+/* Helper function for uniquely inserting distance vectors. */
+
+static void
+save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
+{
+ unsigned i;
+ lambda_vector v;
+
+ for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
+ if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
+ return;
+
+ VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
+}
+
+/* Helper function for uniquely inserting direction vectors. */
+
+static void
+save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
+{
+ unsigned i;
+ lambda_vector v;
+
+ for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
+ if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
+ return;
+
+ VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
+}
+
+/* Add a distance of 1 on all the loops outer than INDEX. If we
+ haven't yet determined a distance for this outer loop, push a new
+ distance vector composed of the previous distance, and a distance
+ of 1 for this outer loop. Example:
+
+ | loop_1
+ | loop_2
+ | A[10]
+ | endloop_2
+ | endloop_1
+
+ Saved vectors are of the form (dist_in_1, dist_in_2). First, we
+ save (0, 1), then we have to save (1, 0). */
+
+static void
+add_outer_distances (struct data_dependence_relation *ddr,
+ lambda_vector dist_v, int index)
+{
+ /* For each outer loop where init_v is not set, the accesses are
+ in dependence of distance 1 in the loop. */
+ while (--index >= 0)
+ {
+ lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
+ save_v[index] = 1;
+ save_dist_v (ddr, save_v);
+ }
+}
+
+/* Return false when fail to represent the data dependence as a
+ distance vector. INIT_B is set to true when a component has been
+ added to the distance vector DIST_V. INDEX_CARRY is then set to
+ the index in DIST_V that carries the dependence. */
+
+static bool
+build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
+ struct data_reference *ddr_a,
+ struct data_reference *ddr_b,
+ lambda_vector dist_v, bool *init_b,
+ int *index_carry)
+{
+ unsigned i;
+ lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ tree access_fn_a, access_fn_b;
+ struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
+
+ if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ {
+ non_affine_dependence_relation (ddr);
+ return false;
+ }
+
+ access_fn_a = DR_ACCESS_FN (ddr_a, i);
+ access_fn_b = DR_ACCESS_FN (ddr_b, i);
+
+ if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
+ && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
+ {
+ int dist, index;
+ int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
+ DDR_LOOP_NEST (ddr));
+ int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
+ DDR_LOOP_NEST (ddr));
+
+ /* The dependence is carried by the outermost loop. Example:
+ | loop_1
+ | A[{4, +, 1}_1]
+ | loop_2
+ | A[{5, +, 1}_2]
+ | endloop_2
+ | endloop_1
+ In this case, the dependence is carried by loop_1. */
+ index = index_a < index_b ? index_a : index_b;
+ *index_carry = MIN (index, *index_carry);
+
+ if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ {
+ non_affine_dependence_relation (ddr);
+ return false;
+ }
+
+ dist = int_cst_value (SUB_DISTANCE (subscript));
+
+ /* This is the subscript coupling test. If we have already
+ recorded a distance for this loop (a distance coming from
+ another subscript), it should be the same. For example,
+ in the following code, there is no dependence:
+
+ | loop i = 0, N, 1
+ | T[i+1][i] = ...
+ | ... = T[i][i]
+ | endloop
+ */
+ if (init_v[index] != 0 && dist_v[index] != dist)
+ {
+ finalize_ddr_dependent (ddr, chrec_known);
+ return false;
+ }
+
+ dist_v[index] = dist;
+ init_v[index] = 1;
+ *init_b = true;
+ }
+ else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
+ {
+ /* This can be for example an affine vs. constant dependence
+ (T[i] vs. T[3]) that is not an affine dependence and is
+ not representable as a distance vector. */
+ non_affine_dependence_relation (ddr);
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/* Return true when the DDR contains only constant access functions. */
+
+static bool
+constant_access_functions (const 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 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)
+{
+ int x_1, x_2;
+ tree c_1 = CHREC_LEFT (c_2);
+ tree c_0 = CHREC_LEFT (c_1);
+ lambda_vector dist_v;
+ int v1, v2, cd;
+
+ /* 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_AFFINE_P (ddr) = false;
+ return;
+ }
+
+ x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
+ x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
+
+ /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ v1 = int_cst_value (CHREC_RIGHT (c_1));
+ v2 = int_cst_value (CHREC_RIGHT (c_2));
+ cd = gcd (v1, v2);
+ v1 /= cd;
+ v2 /= cd;
+
+ if (v2 < 0)
+ {
+ v2 = -v2;
+ v1 = -v1;
+ }
+
+ dist_v[x_1] = v2;
+ dist_v[x_2] = -v1;
+ save_dist_v (ddr, dist_v);
+
+ add_outer_distances (ddr, dist_v, x_1);
+}
+
+/* Helper function for the case where DDR_A and DDR_B are the same
+ access functions. */
+
+static void
+add_other_self_distances (struct data_dependence_relation *ddr)
+{
+ lambda_vector dist_v;
+ unsigned i;
+ int index_carry = DDR_NB_LOOPS (ddr);
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
+
+ if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
+ {
+ if (!evolution_function_is_univariate_p (access_fun))
+ {
+ if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
+ {
+ DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+ return;
+ }
+
+ 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;
+ }
+
+ index_carry = MIN (index_carry,
+ index_in_loop_nest (CHREC_VARIABLE (access_fun),
+ DDR_LOOP_NEST (ddr)));
+ }
+ }
+
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ 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. */
+
+static bool
+build_classic_dist_vector (struct data_dependence_relation *ddr,
+ struct loop *loop_nest)
+{
+ bool init_b = false;
+ int index_carry = DDR_NB_LOOPS (ddr);
+ lambda_vector dist_v;
+
+ if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
+ return false;
+
+ if (same_access_functions (ddr))
+ {
+ /* Save the 0 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);
+
+ return true;
+ }
+
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
+ dist_v, &init_b, &index_carry))
+ return false;
+
+ /* Save the distance vector if we initialized one. */
+ if (init_b)
+ {
+ /* Verify a basic constraint: classic distance vectors should
+ always be lexicographically positive.
+
+ Data references are collected in the order of execution of
+ the program, thus for the following loop
+
+ | for (i = 1; i < 100; i++)
+ | for (j = 1; j < 100; j++)
+ | {
+ | t = T[j+1][i-1]; // A
+ | T[j][i] = t + 2; // B
+ | }
+
+ references are collected following the direction of the wind:
+ A then B. The data dependence tests are performed also
+ following this order, such that we're looking at the distance
+ separating the elements accessed by A from the elements later
+ accessed by B. But in this example, the distance returned by
+ test_dep (A, B) is lexicographically negative (-1, 1), that
+ means that the access A occurs later than B with respect to
+ the outer loop, ie. we're actually looking upwind. In this
+ case we solve test_dep (B, A) looking downwind to the
+ lexicographically positive solution, that returns the
+ distance vector (1, -1). */
+ if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
+ {
+ lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ loop_nest))
+ return false;
+ compute_subscript_distance (ddr);
+ 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:
+
+ | for (k = 1; k < 100; k++)
+ | for (i = 1; i < 100; i++)
+ | for (j = 1; j < 100; j++)
+ | {
+ | t = T[j+1][i-1]; // A
+ | T[j][i] = t + 2; // B
+ | }
+
+ the vectors are:
+ (0, 1, -1)
+ (1, 1, -1)
+ (1, -1, 1)
+ */
+ if (DDR_NB_LOOPS (ddr) > 1)
+ {
+ add_outer_distances (ddr, save_v, index_carry);
+ add_outer_distances (ddr, dist_v, index_carry);
+ }
+ }
+ else
+ {
+ lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
+
+ if (DDR_NB_LOOPS (ddr) > 1)
+ {
+ lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+ if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
+ DDR_A (ddr), loop_nest))
+ return false;
+ compute_subscript_distance (ddr);
+ 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
+ {
+ /* There is a distance of 1 on all the outer loops: Example:
+ there is a dependence of distance 1 on loop_1 for the array A.
+
+ | loop_1
+ | A[5] = ...
+ | endloop
+ */
+ add_outer_distances (ddr, dist_v,
+ lambda_vector_first_nz (dist_v,
+ DDR_NB_LOOPS (ddr), 0));
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ unsigned i;
+
+ fprintf (dump_file, "(build_classic_dist_vector\n");
+ for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+ {
+ fprintf (dump_file, " dist_vector = (");
+ print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
+ DDR_NB_LOOPS (ddr));
+ fprintf (dump_file, " )\n");
+ }
+ fprintf (dump_file, ")\n");
+ }
+
+ return true;
+}
+
+/* Return the direction for a given distance.
+ FIXME: Computing dir this way is suboptimal, since dir can catch
+ cases that dist is unable to represent. */
+
+static inline enum data_dependence_direction
+dir_from_dist (int dist)
+{
+ if (dist > 0)
+ return dir_positive;
+ else if (dist < 0)
+ return dir_negative;
+ else
+ return dir_equal;
+}
+
+/* Compute the classic per loop direction vector. DDR is the data
+ dependence relation to build a vector from. */
+
+static void
+build_classic_dir_vector (struct data_dependence_relation *ddr)
+{
+ unsigned i, j;
+ lambda_vector dist_v;
+
+ for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
+ {
+ lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+ for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
+ dir_v[j] = dir_from_dist (dist_v[j]);
+
+ save_dir_v (ddr, dir_v);
+ }
+}
+
+/* Helper function. Returns true when there is a dependence between
+ data references DRA and DRB. */
+
+static bool
+subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
+ struct data_reference *dra,
+ struct data_reference *drb,
+ struct loop *loop_nest)
+{
+ unsigned int i;
+ tree last_conflicts;
+ struct subscript *subscript;
+
+ for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
+ i++)
+ {
+ conflict_function *overlaps_a, *overlaps_b;
+
+ analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
+ DR_ACCESS_FN (drb, i),
+ &overlaps_a, &overlaps_b,
+ &last_conflicts, loop_nest);
+
+ if (CF_NOT_KNOWN_P (overlaps_a)
+ || CF_NOT_KNOWN_P (overlaps_b))
+ {
+ finalize_ddr_dependent (ddr, chrec_dont_know);
+ dependence_stats.num_dependence_undetermined++;
+ free_conflict_function (overlaps_a);
+ free_conflict_function (overlaps_b);
+ return false;
+ }
+
+ else if (CF_NO_DEPENDENCE_P (overlaps_a)
+ || CF_NO_DEPENDENCE_P (overlaps_b))
+ {
+ finalize_ddr_dependent (ddr, chrec_known);
+ dependence_stats.num_dependence_independent++;
+ free_conflict_function (overlaps_a);
+ free_conflict_function (overlaps_b);
+ return false;
+ }
+
+ 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;
+ }
+ }
+
+ return true;
+}
+
+/* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
+
+static void
+subscript_dependence_tester (struct data_dependence_relation *ddr,
+ struct loop *loop_nest)
+{
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(subscript_dependence_tester \n");
+
+ if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
+ dependence_stats.num_dependence_dependent++;
+
+ compute_subscript_distance (ddr);
+ if (build_classic_dist_vector (ddr, loop_nest))
+ build_classic_dir_vector (ddr);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Returns true when all the access functions of A are affine or
+ constant with respect to LOOP_NEST. */
+
+static bool
+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);
+ tree t;
+
+ for (i = 0; VEC_iterate (tree, fns, i, t); i++)
+ if (!evolution_function_is_invariant_p (t, loop_nest->num)
+ && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
+ return false;
+
+ return true;
+}
+
+/* Initializes an equation for an OMEGA problem using the information
+ contained in the ACCESS_FUN. Returns true when the operation
+ succeeded.
+
+ PB is the omega constraint system.
+ EQ is the number of the equation to be initialized.
+ OFFSET is used for shifting the variables names in the constraints:
+ a constrain is composed of 2 * the number of variables surrounding
+ dependence accesses. OFFSET is set either to 0 for the first n variables,
+ then it is set to n.
+ ACCESS_FUN is expected to be an affine chrec. */
+
+static bool
+init_omega_eq_with_af (omega_pb pb, unsigned eq,
+ unsigned int offset, tree access_fun,
+ struct data_dependence_relation *ddr)
+{
+ switch (TREE_CODE (access_fun))
+ {
+ case POLYNOMIAL_CHREC:
+ {
+ tree left = CHREC_LEFT (access_fun);
+ tree right = CHREC_RIGHT (access_fun);
+ int var = CHREC_VARIABLE (access_fun);
+ unsigned var_idx;
+
+ if (TREE_CODE (right) != INTEGER_CST)
+ return false;
+
+ var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
+ pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
+
+ /* Compute the innermost loop index. */
+ DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
+
+ if (offset == 0)
+ pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
+ += int_cst_value (right);
+
+ switch (TREE_CODE (left))
+ {
+ case POLYNOMIAL_CHREC:
+ return init_omega_eq_with_af (pb, eq, offset, left, ddr);
+
+ case INTEGER_CST:
+ pb->eqs[eq].coef[0] += int_cst_value (left);
+ return true;
+
+ default:
+ return false;
+ }
+ }
+
+ case INTEGER_CST:
+ pb->eqs[eq].coef[0] += int_cst_value (access_fun);
+ return true;
+
+ default:
+ return false;
+ }
+}
+
+/* As explained in the comments preceding init_omega_for_ddr, we have
+ to set up a system for each loop level, setting outer loops
+ variation to zero, and current loop variation to positive or zero.
+ Save each lexico positive distance vector. */
+
+static void
+omega_extract_distance_vectors (omega_pb pb,
+ struct data_dependence_relation *ddr)
+{
+ int eq, geq;
+ unsigned i, j;
+ struct loop *loopi, *loopj;
+ enum omega_result res;
+
+ /* Set a new problem for each loop in the nest. The basis is the
+ problem that we have initialized until now. On top of this we
+ add new constraints. */
+ for (i = 0; i <= DDR_INNER_LOOP (ddr)
+ && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
+ {
+ int dist = 0;
+ omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
+ DDR_NB_LOOPS (ddr));
+
+ omega_copy_problem (copy, pb);
+
+ /* For all the outer loops "loop_j", add "dj = 0". */
+ for (j = 0;
+ j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
+ {
+ eq = omega_add_zero_eq (copy, omega_black);
+ copy->eqs[eq].coef[j + 1] = 1;
+ }
+
+ /* For "loop_i", add "0 <= di". */
+ geq = omega_add_zero_geq (copy, omega_black);
+ copy->geqs[geq].coef[i + 1] = 1;
+
+ /* Reduce the constraint system, and test that the current
+ problem is feasible. */
+ res = omega_simplify_problem (copy);
+ if (res == omega_false
+ || res == omega_unknown
+ || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
+ goto next_problem;
+
+ for (eq = 0; eq < copy->num_subs; eq++)
+ if (copy->subs[eq].key == (int) i + 1)
+ {
+ dist = copy->subs[eq].coef[0];
+ goto found_dist;
+ }
+
+ if (dist == 0)
+ {
+ /* Reinitialize problem... */
+ omega_copy_problem (copy, pb);
+ for (j = 0;
+ j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
+ {
+ eq = omega_add_zero_eq (copy, omega_black);
+ copy->eqs[eq].coef[j + 1] = 1;
+ }
+
+ /* ..., but this time "di = 1". */
+ eq = omega_add_zero_eq (copy, omega_black);
+ copy->eqs[eq].coef[i + 1] = 1;
+ copy->eqs[eq].coef[0] = -1;
+
+ res = omega_simplify_problem (copy);
+ if (res == omega_false
+ || res == omega_unknown
+ || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
+ goto next_problem;
+
+ for (eq = 0; eq < copy->num_subs; eq++)
+ if (copy->subs[eq].key == (int) i + 1)
+ {
+ dist = copy->subs[eq].coef[0];
+ goto found_dist;
+ }
+ }
+
+ found_dist:;
+ /* Save the lexicographically positive distance vector. */
+ if (dist >= 0)
+ {
+ lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+ dist_v[i] = dist;
+
+ for (eq = 0; eq < copy->num_subs; eq++)
+ if (copy->subs[eq].key > 0)
+ {
+ dist = copy->subs[eq].coef[0];
+ dist_v[copy->subs[eq].key - 1] = dist;
+ }
+
+ for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
+ dir_v[j] = dir_from_dist (dist_v[j]);
+
+ save_dist_v (ddr, dist_v);
+ save_dir_v (ddr, dir_v);
+ }
+
+ next_problem:;
+ omega_free_problem (copy);
+ }
+}
+
+/* This is called for each subscript of a tuple of data references:
+ insert an equality for representing the conflicts. */
+
+static bool
+omega_setup_subscript (tree access_fun_a, tree access_fun_b,
+ struct data_dependence_relation *ddr,
+ omega_pb pb, bool *maybe_dependent)
+{
+ int eq;
+ 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. */
+ if (TREE_CODE (difference) != INTEGER_CST)
+ return false;
+
+ /* ZIV test. */
+ if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
+ {
+ /* There is no dependence. */
+ *maybe_dependent = false;
+ return true;
+ }
+
+ 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)
+ || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
+ /* There is probably a dependence, but the system of
+ constraints cannot be built: answer "don't know". */
+ return false;
+
+ /* GCD test. */
+ if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
+ && !int_divides_p (lambda_vector_gcd
+ ((lambda_vector) &(pb->eqs[eq].coef[1]),
+ 2 * DDR_NB_LOOPS (ddr)),
+ pb->eqs[eq].coef[0]))
+ {
+ /* There is no dependence. */
+ *maybe_dependent = false;
+ return true;
+ }
+
+ return true;
+}
+
+/* Helper function, same as init_omega_for_ddr but specialized for
+ data references A and B. */
+
+static bool
+init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
+ struct data_dependence_relation *ddr,
+ omega_pb pb, bool *maybe_dependent)
+{
+ unsigned i;
+ int ineq;
+ struct loop *loopi;
+ unsigned nb_loops = DDR_NB_LOOPS (ddr);
+
+ /* Insert an equality per subscript. */
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
+ ddr, pb, maybe_dependent))
+ return false;
+ else if (*maybe_dependent == false)
+ {
+ /* There is no dependence. */
+ DDR_ARE_DEPENDENT (ddr) = chrec_known;
+ return true;
+ }
+ }
+
+ /* Insert inequalities: constraints corresponding to the iteration
+ domain, i.e. the loops surrounding the references "loop_x" and
+ the distance variables "dx". The layout of the OMEGA
+ representation is as follows:
+ - coef[0] is the constant
+ - coef[1..nb_loops] are the protected variables that will not be
+ removed by the solver: the "dx"
+ - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
+ */
+ 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, false);
+
+ /* 0 <= loop_x */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
+
+ /* 0 <= loop_x + dx */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
+ pb->geqs[ineq].coef[i + 1] = 1;
+
+ if (nbi != -1)
+ {
+ /* loop_x <= nb_iters */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
+ pb->geqs[ineq].coef[0] = nbi;
+
+ /* loop_x + dx <= nb_iters */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
+ pb->geqs[ineq].coef[i + 1] = -1;
+ pb->geqs[ineq].coef[0] = nbi;
+
+ /* A step "dx" bigger than nb_iters is not feasible, so
+ add "0 <= nb_iters + dx", */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + 1] = 1;
+ pb->geqs[ineq].coef[0] = nbi;
+ /* and "dx <= nb_iters". */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + 1] = -1;
+ pb->geqs[ineq].coef[0] = nbi;
+ }
+ }
+
+ omega_extract_distance_vectors (pb, ddr);
+
+ return true;
+}
+
+/* Sets up the Omega dependence problem for the data dependence
+ relation DDR. Returns false when the constraint system cannot be
+ built, ie. when the test answers "don't know". Returns true
+ otherwise, and when independence has been proved (using one of the
+ trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
+ set MAYBE_DEPENDENT to true.
+
+ Example: for setting up the dependence system corresponding to the
+ conflicting accesses
+
+ | loop_i
+ | loop_j
+ | A[i, i+1] = ...
+ | ... A[2*j, 2*(i + j)]
+ | endloop_j
+ | endloop_i
+
+ the following constraints come from the iteration domain:
+
+ 0 <= i <= Ni
+ 0 <= i + di <= Ni
+ 0 <= j <= Nj
+ 0 <= j + dj <= Nj
+
+ where di, dj are the distance variables. The constraints
+ representing the conflicting elements are:
+
+ i = 2 * (j + dj)
+ i + 1 = 2 * (i + di + j + dj)
+
+ For asking that the resulting distance vector (di, dj) be
+ lexicographically positive, we insert the constraint "di >= 0". If
+ "di = 0" in the solution, we fix that component to zero, and we
+ look at the inner loops: we set a new problem where all the outer
+ loop distances are zero, and fix this inner component to be
+ positive. When one of the components is positive, we save that
+ distance, and set a new problem where the distance on this loop is
+ zero, searching for other distances in the inner loops. Here is
+ the classic example that illustrates that we have to set for each
+ inner loop a new problem:
+
+ | loop_1
+ | loop_2
+ | A[10]
+ | endloop_2
+ | endloop_1
+
+ we have to save two distances (1, 0) and (0, 1).
+
+ Given two array references, refA and refB, we have to set the
+ dependence problem twice, refA vs. refB and refB vs. refA, and we
+ cannot do a single test, as refB might occur before refA in the
+ inner loops, and the contrary when considering outer loops: ex.
+
+ | loop_0
+ | loop_1
+ | loop_2
+ | T[{1,+,1}_2][{1,+,1}_1] // refA
+ | T[{2,+,1}_2][{0,+,1}_1] // refB
+ | endloop_2
+ | endloop_1
+ | endloop_0
+
+ refB touches the elements in T before refA, and thus for the same
+ loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
+ but for successive loop_0 iterations, we have (1, -1, 1)
+
+ The Omega solver expects the distance variables ("di" in the
+ previous example) to come first in the constraint system (as
+ variables to be protected, or "safe" variables), the constraint
+ system is built using the following layout:
+
+ "cst | distance vars | index vars".
+*/
+
+static bool
+init_omega_for_ddr (struct data_dependence_relation *ddr,
+ bool *maybe_dependent)
+{
+ omega_pb pb;
+ bool res = false;
+
+ *maybe_dependent = true;
+
+ if (same_access_functions (ddr))
+ {
+ unsigned j;
+ lambda_vector dir_v;
+
+ /* Save the 0 vector. */
+ save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+ dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
+ dir_v[j] = dir_equal;
+ save_dir_v (ddr, dir_v);
+
+ /* Save the dependences carried by outer loops. */
+ pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
+ res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
+ maybe_dependent);
+ omega_free_problem (pb);
+ return res;
+ }
+
+ /* Omega expects the protected variables (those that have to be kept
+ after elimination) to appear first in the constraint system.
+ These variables are the distance variables. In the following
+ initialization we declare NB_LOOPS safe variables, and the total
+ number of variables for the constraint system is 2*NB_LOOPS. */
+ pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
+ res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
+ maybe_dependent);
+ omega_free_problem (pb);
+
+ /* Stop computation if not decidable, or no dependence. */
+ if (res == false || *maybe_dependent == false)
+ return res;
+
+ pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
+ res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
+ maybe_dependent);
+ omega_free_problem (pb);
+
+ return res;
+}
+
+/* Return true when DDR contains the same information as that stored
+ in DIR_VECTS and in DIST_VECTS, return false otherwise. */
+
+static bool
+ddr_consistent_p (FILE *file,
+ struct data_dependence_relation *ddr,
+ VEC (lambda_vector, heap) *dist_vects,
+ VEC (lambda_vector, heap) *dir_vects)
+{
+ unsigned int i, j;
+
+ /* If dump_file is set, output there. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ file = dump_file;
+
+ if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
+ {
+ lambda_vector b_dist_v;
+ fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
+ VEC_length (lambda_vector, dist_vects),
+ DDR_NUM_DIST_VECTS (ddr));
+
+ fprintf (file, "Banerjee dist vectors:\n");
+ for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
+ print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
+
+ fprintf (file, "Omega dist vectors:\n");
+ for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+ print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
+
+ fprintf (file, "data dependence relation:\n");
+ dump_data_dependence_relation (file, ddr);
+
+ fprintf (file, ")\n");
+ return false;
+ }
+
+ if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
+ {
+ fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
+ VEC_length (lambda_vector, dir_vects),
+ DDR_NUM_DIR_VECTS (ddr));
+ return false;
+ }
+
+ for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+ {
+ lambda_vector a_dist_v;
+ lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
+
+ /* Distance vectors are not ordered in the same way in the DDR
+ and in the DIST_VECTS: search for a matching vector. */
+ for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
+ if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
+ break;
+
+ if (j == VEC_length (lambda_vector, dist_vects))
+ {
+ fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
+ print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
+ fprintf (file, "not found in Omega dist vectors:\n");
+ print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
+ fprintf (file, "data dependence relation:\n");
+ dump_data_dependence_relation (file, ddr);
+ fprintf (file, ")\n");
+ }
+ }
+
+ for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
+ {
+ lambda_vector a_dir_v;
+ lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
+
+ /* Direction vectors are not ordered in the same way in the DDR
+ and in the DIR_VECTS: search for a matching vector. */
+ for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
+ if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
+ break;
+
+ if (j == VEC_length (lambda_vector, dist_vects))
+ {
+ fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
+ print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
+ fprintf (file, "not found in Omega dir vectors:\n");
+ print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
+ fprintf (file, "data dependence relation:\n");
+ dump_data_dependence_relation (file, ddr);
+ fprintf (file, ")\n");
+ }
+ }
+
+ return true;
+}
+
+/* This computes the affine dependence relation between A and B with
+ respect to LOOP_NEST. CHREC_KNOWN is used for representing the
+ independence between two accesses, while CHREC_DONT_KNOW is used
+ for representing the unknown relation.
+
+ Note that it is possible to stop the computation of the dependence
+ relation the first time we detect a CHREC_KNOWN element for a given
+ subscript. */
+
+static void
+compute_affine_dependence (struct data_dependence_relation *ddr,
+ struct loop *loop_nest)
+{
+ struct data_reference *dra = DDR_A (ddr);
+ struct data_reference *drb = DDR_B (ddr);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(compute_affine_dependence\n");
+ fprintf (dump_file, " (stmt_a = \n");
+ print_generic_expr (dump_file, DR_STMT (dra), 0);
+ fprintf (dump_file, ")\n (stmt_b = \n");
+ print_generic_expr (dump_file, DR_STMT (drb), 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ /* Analyze only when the dependence relation is not yet known. */
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ {
+ dependence_stats.num_dependence_tests++;
+
+ if (access_functions_are_affine_or_constant_p (dra, loop_nest)
+ && access_functions_are_affine_or_constant_p (drb, loop_nest))
+ {
+ if (flag_check_data_deps)
+ {
+ /* Compute the dependences using the first algorithm. */
+ subscript_dependence_tester (ddr, loop_nest);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\n\nBanerjee Analyzer\n");
+ dump_data_dependence_relation (dump_file, ddr);
+ }
+
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ {
+ bool maybe_dependent;
+ VEC (lambda_vector, heap) *dir_vects, *dist_vects;
+
+ /* Save the result of the first DD analyzer. */
+ dist_vects = DDR_DIST_VECTS (ddr);
+ dir_vects = DDR_DIR_VECTS (ddr);
+
+ /* Reset the information. */
+ DDR_DIST_VECTS (ddr) = NULL;
+ DDR_DIR_VECTS (ddr) = NULL;
+
+ /* Compute the same information using Omega. */
+ if (!init_omega_for_ddr (ddr, &maybe_dependent))
+ goto csys_dont_know;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Omega Analyzer\n");
+ dump_data_dependence_relation (dump_file, ddr);
+ }
+
+ /* Check that we get the same information. */
+ if (maybe_dependent)
+ gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
+ dir_vects));
+ }
+ }
+ else
+ subscript_dependence_tester (ddr, loop_nest);
+ }
+
+ /* As a last case, if the dependence cannot be determined, or if
+ the dependence is considered too difficult to determine, answer
+ "don't know". */
+ else
+ {
+ csys_dont_know:;
+ dependence_stats.num_dependence_undetermined++;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Data ref a:\n");
+ dump_data_reference (dump_file, dra);
+ fprintf (dump_file, "Data ref b:\n");
+ dump_data_reference (dump_file, drb);
+ fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
+ }
+ finalize_ddr_dependent (ddr, chrec_dont_know);
+ }
+ }
OSDN Git Service
