+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 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);
+
+ /* 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 (integer_type_node, 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);
OSDN Git Service
