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
static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
struct data_reference *,
- struct data_reference *);
+ struct data_reference *,
+ struct loop *);
/* Returns true iff A divides B. */
static inline bool
tree type = TREE_TYPE (exp), otype;
tree var0, var1;
tree off0, off1;
+ enum tree_code code;
*var = exp;
STRIP_NOPS (exp);
otype = TREE_TYPE (exp);
+ code = TREE_CODE (exp);
- switch (TREE_CODE (exp))
+ switch (code)
{
case INTEGER_CST:
*var = build_int_cst (type, 0);
*off = fold_convert (ssizetype, exp);
return;
+ case POINTER_PLUS_EXPR:
+ code = PLUS_EXPR;
+ /* FALLTHROUGH */
case PLUS_EXPR:
case MINUS_EXPR:
split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
split_constant_offset (TREE_OPERAND (exp, 1), &var1, &off1);
*var = fold_convert (type, fold_build2 (TREE_CODE (exp), otype,
var0, var1));
- *off = size_binop (TREE_CODE (exp), off0, off1);
+ *off = size_binop (code, off0, off1);
return;
case MULT_EXPR:
}
/* Determines the base object and the list of indices of memory reference
- DR, analysed in loop nest NEST. */
+ DR, analyzed in loop nest NEST. */
static void
dr_analyze_indices (struct data_reference *dr, struct loop *nest)
}
DR_SYMBOL_TAG (dr) = smt;
- if (var_can_have_subvars (smt))
+ if (smt && var_can_have_subvars (smt))
DR_SUBVARS (dr) = get_subvars_for_var (smt);
vops = BITMAP_ALLOC (NULL);
/* Analyzes memory reference MEMREF accessed in STMT. The reference
is read if IS_READ is true, write otherwise. Returns the
data_reference description of MEMREF. NEST is the outermost loop of the
- loop nest in that the reference should be analysed. */
+ loop nest in that the reference should be analyzed. */
-static struct data_reference *
+struct data_reference *
create_data_ref (struct loop *nest, tree memref, tree stmt, bool is_read)
{
struct data_reference *dr;
if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b)
&& (!DR_IS_READ (a) || !DR_IS_READ (b))
- && decl_a && TREE_CODE (decl_a) == PARM_DECL
- && decl_b && TREE_CODE (decl_b) == PARM_DECL
+ && decl_a && DECL_P (decl_a)
+ && decl_b && DECL_P (decl_b)
+ && decl_a != decl_b
&& TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
&& DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
return false;
DDR_A (res) = a;
DDR_B (res) = b;
DDR_LOOP_NEST (res) = NULL;
+ DDR_REVERSED_P (res) = false;
if (a == NULL || b == NULL)
{
}
/* If the base of the object is not invariant in the loop nest, we cannot
- analyse it. TODO -- in fact, it would suffice to record that there may
- be arbitrary depencences in the loops where the base object varies. */
+ analyze it. TODO -- in fact, it would suffice to record that there may
+ be arbitrary dependences in the loops where the base object varies. */
if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
DR_BASE_OBJECT (a)))
{
/* 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)
/* 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)
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;
+ HOST_WIDE_INT tau1, tau2;
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);
+ niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
+ false);
+ niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
+ false);
if (niter_a < 0 || niter_b < 0)
{
if (dump_file && (dump_flags & TDF_DETAILS))
| x0 = i0 + i1 * t,
| y0 = j0 + j1 * t. */
- int i0, j0, i1, j1;
+ HOST_WIDE_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;
+ HOST_WIDE_INT x0, y0;
+ HOST_WIDE_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);
+ niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
+ false);
+ niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
+ false);
if (niter_a < 0 || niter_b < 0)
{
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))
return val % cd == 0;
}
-/* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
- *OVERLAPS_B are initialized to the functions that describe the
- relation between the elements accessed twice by CHREC_A and
- CHREC_B. For k >= 0, the following property is verified:
+/* Analyze a MIV (Multiple Index Variable) subscript with respect to
+ LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
+ functions that describe the relation between the elements accessed
+ twice by CHREC_A and CHREC_B. For k >= 0, the following property
+ is verified:
CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
tree chrec_b,
conflict_function **overlaps_a,
conflict_function **overlaps_b,
- tree *last_conflicts)
+ tree *last_conflicts,
+ struct loop *loop_nest)
{
/* FIXME: This is a MIV subscript, not yet handled.
Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
else if (evolution_function_is_constant_p (difference)
/* For the moment, the following is verified:
- evolution_function_is_affine_multivariate_p (chrec_a, 0) */
+ 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
dependence_stats.num_miv_independent++;
}
- else if (evolution_function_is_affine_multivariate_p (chrec_a, 0)
+ 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, 0)
+ && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
&& !chrec_contains_symbols (chrec_b))
{
/* testsuite/.../ssa-chrec-35.c
fprintf (dump_file, ")\n");
}
-/* Determines the iterations for which CHREC_A is equal to CHREC_B.
- OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
- two functions that describe the iterations that contain conflicting
- elements.
+/* 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:
tree chrec_b,
conflict_function **overlap_iterations_a,
conflict_function **overlap_iterations_b,
- tree *last_conflicts)
+ 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))
/* 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, 0))
+ && 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));
yet. */
else if ((chrec_contains_symbols (chrec_a)
|| chrec_contains_symbols (chrec_b))
- && (!evolution_function_is_affine_multivariate_p (chrec_a, 0)
- || !evolution_function_is_affine_multivariate_p (chrec_b, 0)))
+ && (!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 ();
else
analyze_miv_subscript (chrec_a, chrec_b,
overlap_iterations_a, overlap_iterations_b,
- last_conflicts);
+ last_conflicts, loop_nest);
if (dump_file && (dump_flags & TDF_DETAILS))
{
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;
}
to represent the data dependence as a distance vector. */
static bool
-build_classic_dist_vector (struct data_dependence_relation *ddr)
+build_classic_dist_vector (struct data_dependence_relation *ddr,
+ struct loop *loop_nest)
{
bool init_b = false;
int index_carry = DDR_NB_LOOPS (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));
+ subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ loop_nest);
compute_subscript_distance (ddr);
build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
save_v, &init_b, &index_carry);
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 opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
+ subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ loop_nest);
compute_subscript_distance (ddr);
build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
opposite_v, &init_b, &index_carry);
static bool
subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
struct data_reference *dra,
- struct data_reference *drb)
+ struct data_reference *drb,
+ struct loop *loop_nest)
{
unsigned int i;
tree last_conflicts;
analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
DR_ACCESS_FN (drb, i),
&overlaps_a, &overlaps_b,
- &last_conflicts);
+ &last_conflicts, loop_nest);
if (CF_NOT_KNOWN_P (overlaps_a)
|| CF_NOT_KNOWN_P (overlaps_b))
return true;
}
-/* Computes the conflicting iterations, and initialize DDR. */
+/* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
static void
-subscript_dependence_tester (struct data_dependence_relation *ddr)
+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)))
+ 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))
+ if (build_classic_dist_vector (ddr, loop_nest))
build_classic_dir_vector (ddr);
if (dump_file && (dump_flags & TDF_DETAILS))
}
/* Returns true when all the access functions of A are affine or
- constant. */
+ constant with respect to LOOP_NEST. */
static bool
-access_functions_are_affine_or_constant_p (struct data_reference *a)
+access_functions_are_affine_or_constant_p (struct data_reference *a,
+ 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_constant_p (t)
- && !evolution_function_is_affine_multivariate_p (t, 0))
+ if (!evolution_function_is_invariant_p (t, loop_nest->num)
+ && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
return false;
return true;
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);
return true;
}
-/* This computes the affine dependence relation between A and B.
- CHREC_KNOWN is used for representing the independence between two
- accesses, while CHREC_DONT_KNOW is used for representing the unknown
- relation.
+/* 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)
+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);
{
dependence_stats.num_dependence_tests++;
- if (access_functions_are_affine_or_constant_p (dra)
- && access_functions_are_affine_or_constant_p (drb))
+ 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);
+ subscript_dependence_tester (ddr, loop_nest);
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
}
else
- subscript_dependence_tester (ddr);
+ subscript_dependence_tester (ddr, loop_nest);
}
/* As a last case, if the dependence cannot be determined, or if
COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
relations. */
-static void
+void
compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
VEC (ddr_p, heap) **dependence_relations,
VEC (loop_p, heap) *loop_nest,
{
ddr = initialize_data_dependence_relation (a, b, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_affine_dependence (ddr);
+ compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
}
if (compute_self_and_rr)
/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
reference, returns false, otherwise returns true. NEST is the outermost
- loop of the loop nest in that the references should be analysed. */
+ loop of the loop nest in that the references should be analyzed. */
static bool
find_data_references_in_stmt (struct loop *nest, tree stmt,
contain the loops from the outermost to the innermost, as they will
appear in the classic distance vector. */
-static bool
+bool
find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
{
VEC_safe_push (loop_p, heap, *loop_nest, loop);
VEC_free (data_reference_p, heap, datarefs);
}
+\f
+
+/* Returns the index of STMT in RDG. */
+
+static int
+find_vertex_for_stmt (struct graph *rdg, 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
