/* Data references and dependences detectors.
- Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Sebastian Pop <s.pop@laposte.net>
This file is part of GCC.
{
tree base_a = DR_BASE_NAME (a);
tree base_b = DR_BASE_NAME (b);
- tree ta = TREE_TYPE (base_a);
- tree tb = TREE_TYPE (base_b);
+ if (!base_a || !base_b)
+ return false;
/* Determine if same base. Example: for the array accesses
a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
return true;
}
- if (!alias_sets_conflict_p (get_alias_set (base_a), get_alias_set (base_b)))
- {
- *differ_p = true;
- return true;
- }
-
- /* An instruction writing through a restricted pointer is
- "independent" of any instruction reading or writing through a
- different pointer, in the same block/scope. */
- if ((TREE_CODE (ta) == POINTER_TYPE && TYPE_RESTRICT (ta)
- && !DR_IS_READ(a))
- || (TREE_CODE (tb) == POINTER_TYPE && TYPE_RESTRICT (tb)
- && !DR_IS_READ(b)))
- {
- *differ_p = true;
- return true;
- }
-
return false;
}
array_size = TYPE_SIZE (TREE_TYPE (opnd0));
element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
if (array_size == NULL_TREE
- || element_size == NULL_TREE)
+ || TREE_CODE (array_size) != INTEGER_CST
+ || TREE_CODE (element_size) != INTEGER_CST)
return;
data_size = fold (build2 (EXACT_DIV_EXPR, integer_type_node,
- array_size, element_size));
+ array_size, element_size));
if (init != NULL_TREE
&& step != NULL_TREE
static tree
analyze_array_indexes (struct loop *loop,
- varray_type *access_fns,
+ VEC(tree,heap) **access_fns,
tree ref, tree stmt)
{
tree opnd0, opnd1;
if (loop->estimated_nb_iterations == NULL_TREE)
estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
- VARRAY_PUSH_TREE (*access_fns, access_fn);
+ VEC_safe_push (tree, heap, *access_fns, access_fn);
/* Recursively record other array access functions. */
if (TREE_CODE (opnd0) == ARRAY_REF)
DR_STMT (res) = stmt;
DR_REF (res) = ref;
- VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
+ DR_ACCESS_FNS (res) = VEC_alloc (tree, heap, 3);
DR_BASE_NAME (res) = analyze_array_indexes
(loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt);
DR_IS_READ (res) = is_read;
DR_STMT (res) = stmt;
DR_REF (res) = ref;
- VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
+ DR_ACCESS_FNS (res) = VEC_alloc (tree, heap, 5);
DR_BASE_NAME (res) = base;
- VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
+ VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
DR_IS_READ (res) = is_read;
if (dump_file && (dump_flags & TDF_DETAILS))
/* Determine for each subscript in the data dependence relation DDR
the distance. */
-static void
+void
compute_subscript_distance (struct data_dependence_relation *ddr)
{
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
| y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
| z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
- FORNOW: This is a specialized implementation for a case occuring in
+ FORNOW: This is a specialized implementation for a case occurring in
a common benchmark. Implement the general algorithm. */
static void
if (j1 > 0)
{
- int last_conflict;
+ int last_conflict, min_multiple;
tau1 = MAX (tau1, CEIL (-j0, j1));
tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
- x0 = (i1 * tau1 + i0) % i1;
- y0 = (j1 * tau1 + 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;
DDR is the data dependence relation to build a vector from.
NB_LOOPS is the total number of loops we are considering.
- FIRST_LOOP is the loop->num of the first loop in the analyzed
- loop nest. */
+ FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
+ loop nest.
+ Return FALSE if the dependence relation is outside of the loop nest
+ starting at FIRST_LOOP_DEPTH.
+ Return TRUE otherwise. */
-static void
+bool
build_classic_dist_vector (struct data_dependence_relation *ddr,
- int nb_loops, unsigned int first_loop)
+ int nb_loops, int first_loop_depth)
{
unsigned i;
lambda_vector dist_v, init_v;
lambda_vector_clear (init_v, nb_loops);
if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return;
+ return true;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
- return;
+ return true;
}
access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
&& TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
{
- int dist, loop_nb;
+ int dist, loop_nb, loop_depth;
int loop_nb_a = CHREC_VARIABLE (access_fn_a);
int loop_nb_b = CHREC_VARIABLE (access_fn_b);
struct loop *loop_a = current_loops->parray[loop_nb_a];
struct loop *loop_b = current_loops->parray[loop_nb_b];
+ /* If the loop for either variable is at a lower depth than
+ the first_loop's depth, then we can't possibly have a
+ dependency at this level of the loop. */
+
+ if (loop_a->depth < first_loop_depth
+ || loop_b->depth < first_loop_depth)
+ return false;
+
if (loop_nb_a != loop_nb_b
&& !flow_loop_nested_p (loop_a, loop_b)
&& !flow_loop_nested_p (loop_b, loop_a))
the dependence relation cannot be captured by the
distance abstraction. */
non_affine_dependence_relation (ddr);
- return;
+ return true;
}
/* The dependence is carried by the outermost loop. Example:
| endloop_1
In this case, the dependence is carried by loop_1. */
loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
- loop_nb -= first_loop;
+ loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
/* If the loop number is still greater than the number of
loops we've been asked to analyze, or negative,
something is borked. */
- gcc_assert (loop_nb >= 0);
- gcc_assert (loop_nb < nb_loops);
+ gcc_assert (loop_depth >= 0);
+ gcc_assert (loop_depth < nb_loops);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
- return;
+ return true;
}
dist = int_cst_value (SUB_DISTANCE (subscript));
| ... = T[i][i]
| endloop
There is no dependence. */
- if (init_v[loop_nb] != 0
- && dist_v[loop_nb] != dist)
+ if (init_v[loop_depth] != 0
+ && dist_v[loop_depth] != dist)
{
finalize_ddr_dependent (ddr, chrec_known);
- return;
+ return true;
}
- dist_v[loop_nb] = dist;
- init_v[loop_nb] = 1;
+ dist_v[loop_depth] = dist;
+ init_v[loop_depth] = 1;
}
}
struct loop *lca, *loop_a, *loop_b;
struct data_reference *a = DDR_A (ddr);
struct data_reference *b = DDR_B (ddr);
- int lca_nb;
+ int lca_depth;
loop_a = loop_containing_stmt (DR_STMT (a));
loop_b = loop_containing_stmt (DR_STMT (b));
/* Get the common ancestor loop. */
lca = find_common_loop (loop_a, loop_b);
- lca_nb = lca->num;
- lca_nb -= first_loop;
- gcc_assert (lca_nb >= 0);
- gcc_assert (lca_nb < nb_loops);
+ lca_depth = lca->depth;
+ lca_depth -= first_loop_depth;
+ gcc_assert (lca_depth >= 0);
+ gcc_assert (lca_depth < nb_loops);
/* For each outer loop where init_v is not set, the accesses are
in dependence of distance 1 in the loop. */
if (lca != loop_a
&& lca != loop_b
- && init_v[lca_nb] == 0)
- dist_v[lca_nb] = 1;
+ && init_v[lca_depth] == 0)
+ dist_v[lca_depth] = 1;
lca = lca->outer;
if (lca)
{
- lca_nb = lca->num - first_loop;
+ lca_depth = lca->depth - first_loop_depth;
while (lca->depth != 0)
{
/* If we're considering just a sub-nest, then don't record
any information on the outer loops. */
- if (lca_nb < 0)
+ if (lca_depth < 0)
break;
- gcc_assert (lca_nb < nb_loops);
+ gcc_assert (lca_depth < nb_loops);
- if (init_v[lca_nb] == 0)
- dist_v[lca_nb] = 1;
+ if (init_v[lca_depth] == 0)
+ dist_v[lca_depth] = 1;
lca = lca->outer;
- lca_nb = lca->num - first_loop;
+ lca_depth = lca->depth - first_loop_depth;
}
}
DDR_DIST_VECT (ddr) = dist_v;
DDR_SIZE_VECT (ddr) = nb_loops;
+ return true;
}
/* Compute the classic per loop direction vector.
DDR is the data dependence relation to build a vector from.
NB_LOOPS is the total number of loops we are considering.
- FIRST_LOOP is the loop->num of the first loop in the analyzed
- loop nest. */
+ FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
+ loop nest.
+ Return FALSE if the dependence relation is outside of the loop nest
+ at FIRST_LOOP_DEPTH.
+ Return TRUE otherwise. */
-static void
+static bool
build_classic_dir_vector (struct data_dependence_relation *ddr,
- int nb_loops, unsigned int first_loop)
+ int nb_loops, int first_loop_depth)
{
unsigned i;
lambda_vector dir_v, init_v;
lambda_vector_clear (init_v, nb_loops);
if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return;
+ return true;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
- return;
+ return true;
}
access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
&& TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
{
- int dist, loop_nb;
+ int dist, loop_nb, loop_depth;
enum data_dependence_direction dir = dir_star;
int loop_nb_a = CHREC_VARIABLE (access_fn_a);
int loop_nb_b = CHREC_VARIABLE (access_fn_b);
struct loop *loop_a = current_loops->parray[loop_nb_a];
struct loop *loop_b = current_loops->parray[loop_nb_b];
+
+ /* If the loop for either variable is at a lower depth than
+ the first_loop's depth, then we can't possibly have a
+ dependency at this level of the loop. */
+
+ if (loop_a->depth < first_loop_depth
+ || loop_b->depth < first_loop_depth)
+ return false;
if (loop_nb_a != loop_nb_b
&& !flow_loop_nested_p (loop_a, loop_b)
the dependence relation cannot be captured by the
distance abstraction. */
non_affine_dependence_relation (ddr);
- return;
+ return true;
}
/* The dependence is carried by the outermost loop. Example:
| endloop_1
In this case, the dependence is carried by loop_1. */
loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
- loop_nb -= first_loop;
+ loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
/* If the loop number is still greater than the number of
loops we've been asked to analyze, or negative,
something is borked. */
- gcc_assert (loop_nb >= 0);
- gcc_assert (loop_nb < nb_loops);
+ gcc_assert (loop_depth >= 0);
+ gcc_assert (loop_depth < nb_loops);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
- return;
+ return true;
}
dist = int_cst_value (SUB_DISTANCE (subscript));
| ... = T[i][i]
| endloop
There is no dependence. */
- if (init_v[loop_nb] != 0
+ if (init_v[loop_depth] != 0
&& dir != dir_star
- && (enum data_dependence_direction) dir_v[loop_nb] != dir
- && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
+ && (enum data_dependence_direction) dir_v[loop_depth] != dir
+ && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
{
finalize_ddr_dependent (ddr, chrec_known);
- return;
+ return true;
}
- dir_v[loop_nb] = dir;
- init_v[loop_nb] = 1;
+ dir_v[loop_depth] = dir;
+ init_v[loop_depth] = 1;
}
}
struct loop *lca, *loop_a, *loop_b;
struct data_reference *a = DDR_A (ddr);
struct data_reference *b = DDR_B (ddr);
- int lca_nb;
+ int lca_depth;
loop_a = loop_containing_stmt (DR_STMT (a));
loop_b = loop_containing_stmt (DR_STMT (b));
/* Get the common ancestor loop. */
lca = find_common_loop (loop_a, loop_b);
- lca_nb = lca->num - first_loop;
+ lca_depth = lca->depth - first_loop_depth;
- gcc_assert (lca_nb >= 0);
- gcc_assert (lca_nb < nb_loops);
+ gcc_assert (lca_depth >= 0);
+ gcc_assert (lca_depth < nb_loops);
/* For each outer loop where init_v is not set, the accesses are
in dependence of distance 1 in the loop. */
if (lca != loop_a
&& lca != loop_b
- && init_v[lca_nb] == 0)
- dir_v[lca_nb] = dir_positive;
+ && init_v[lca_depth] == 0)
+ dir_v[lca_depth] = dir_positive;
lca = lca->outer;
if (lca)
{
- lca_nb = lca->num - first_loop;
+ lca_depth = lca->depth - first_loop_depth;
while (lca->depth != 0)
{
/* If we're considering just a sub-nest, then don't record
any information on the outer loops. */
- if (lca_nb < 0)
+ if (lca_depth < 0)
break;
- gcc_assert (lca_nb < nb_loops);
+ gcc_assert (lca_depth < nb_loops);
- if (init_v[lca_nb] == 0)
- dir_v[lca_nb] = dir_positive;
+ if (init_v[lca_depth] == 0)
+ dir_v[lca_depth] = dir_positive;
lca = lca->outer;
- lca_nb = lca->num - first_loop;
+ lca_depth = lca->depth - first_loop_depth;
}
}
DDR_DIR_VECT (ddr) = dir_v;
DDR_SIZE_VECT (ddr) = nb_loops;
+ return true;
}
/* Returns true when all the access functions of A are affine or
access_functions_are_affine_or_constant_p (struct data_reference *a)
{
unsigned int i;
- varray_type fns = DR_ACCESS_FNS (a);
+ VEC(tree,heap) **fns = &DR_ACCESS_FNS (a);
+ tree t;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
- if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
- && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
+ for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
+ if (!evolution_function_is_constant_p (t)
+ && !evolution_function_is_affine_multivariate_p (t))
return false;
return true;
fprintf (dump_file, ")\n");
}
+
+typedef struct data_dependence_relation *ddr_p;
+DEF_VEC_P(ddr_p);
+DEF_VEC_ALLOC_P(ddr_p,heap);
+
/* Compute a subset of the data dependence relation graph. Don't
compute read-read relations, and avoid the computation of the
opposite relation, i.e. when AB has been computed, don't compute BA.
static void
compute_all_dependences (varray_type datarefs,
- varray_type *dependence_relations)
+ VEC(ddr_p,heap) **dependence_relations)
{
unsigned int i, j, N;
b = VARRAY_GENERIC_PTR (datarefs, j);
ddr = initialize_data_dependence_relation (a, b);
- VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+ VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
compute_affine_dependence (ddr);
compute_subscript_distance (ddr);
}
DATAREFS. Returns chrec_dont_know when failing to analyze a
difficult case, returns NULL_TREE otherwise.
- FIXME: This is a "dumb" walker over all the trees in the loop body.
- Find another technique that avoids this costly walk. This is
- acceptable for the moment, since this function is used only for
- debugging purposes. */
+ TODO: This function should be made smarter so that it can handle address
+ arithmetic as if they were array accesses, etc. */
tree
find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
{
- bool dont_know_node_not_inserted = true;
- basic_block bb;
+ basic_block bb, *bbs;
+ unsigned int i;
block_stmt_iterator bsi;
- FOR_EACH_BB (bb)
+ bbs = get_loop_body (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
{
- if (!flow_bb_inside_loop_p (loop, bb))
- continue;
-
+ bb = bbs[i];
+
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
- stmt_ann_t ann = stmt_ann (stmt);
- if (TREE_CODE (stmt) != MODIFY_EXPR)
- continue;
+ /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
+ Calls have side-effects, except those to const or pure
+ functions. */
+ if ((TREE_CODE (stmt) == CALL_EXPR
+ && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
+ || (TREE_CODE (stmt) == ASM_EXPR
+ && ASM_VOLATILE_P (stmt)))
+ goto insert_dont_know_node;
- if (!VUSE_OPS (ann)
- && !V_MUST_DEF_OPS (ann)
- && !V_MAY_DEF_OPS (ann))
+ if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
continue;
- /* In the GIMPLE representation, a modify expression
- contains a single load or store to memory. */
- if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
- VARRAY_PUSH_GENERIC_PTR
- (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
- false));
+ switch (TREE_CODE (stmt))
+ {
+ case MODIFY_EXPR:
+ if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
+ VARRAY_PUSH_GENERIC_PTR
+ (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
+ false));
+
+ if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
+ VARRAY_PUSH_GENERIC_PTR
+ (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
+ true));
- else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
- VARRAY_PUSH_GENERIC_PTR
- (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
- true));
+ if (TREE_CODE (TREE_OPERAND (stmt, 0)) != ARRAY_REF
+ && TREE_CODE (TREE_OPERAND (stmt, 1)) != ARRAY_REF)
+ goto insert_dont_know_node;
- else
- {
- if (dont_know_node_not_inserted)
+ break;
+
+ case CALL_EXPR:
+ {
+ tree args;
+ bool one_inserted = false;
+
+ for (args = TREE_OPERAND (stmt, 1); args; args = TREE_CHAIN (args))
+ if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF)
+ {
+ VARRAY_PUSH_GENERIC_PTR
+ (*datarefs, analyze_array (stmt, TREE_VALUE (args), true));
+ one_inserted = true;
+ }
+
+ if (!one_inserted)
+ goto insert_dont_know_node;
+
+ break;
+ }
+
+ default:
{
struct data_reference *res;
+
+ insert_dont_know_node:;
res = xmalloc (sizeof (struct data_reference));
DR_STMT (res) = NULL_TREE;
DR_REF (res) = NULL_TREE;
DR_IS_READ (res) = false;
VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
- dont_know_node_not_inserted = false;
+ free (bbs);
+ return chrec_dont_know;
}
}
/* When there are no defs in the loop, the loop is parallel. */
- if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
- || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
bb->loop_father->parallel_p = false;
}
compute_estimated_nb_iterations (bb->loop_father);
}
- return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
+ free (bbs);
+
+ return NULL_TREE;
}
\f
varray_type *dependence_relations)
{
unsigned int i;
+ VEC(ddr_p,heap) *allrelations;
+ struct data_dependence_relation *ddr;
/* If one of the data references is not computable, give up without
spending time to compute other dependences. */
chrec_dont_know. */
ddr = initialize_data_dependence_relation (NULL, NULL);
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- build_classic_dist_vector (ddr, nb_loops, loop->num);
- build_classic_dir_vector (ddr, nb_loops, loop->num);
+ build_classic_dist_vector (ddr, nb_loops, loop->depth);
+ build_classic_dir_vector (ddr, nb_loops, loop->depth);
return;
}
- compute_all_dependences (*datarefs, dependence_relations);
+ allrelations = NULL;
+ compute_all_dependences (*datarefs, &allrelations);
- for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
+ for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
{
- struct data_dependence_relation *ddr;
- ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
- build_classic_dist_vector (ddr, nb_loops, loop->num);
- build_classic_dir_vector (ddr, nb_loops, loop->num);
+ if (build_classic_dist_vector (ddr, nb_loops, loop->depth))
+ {
+ VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+ build_classic_dir_vector (ddr, nb_loops, loop->depth);
+ }
}
}
{
struct data_reference *dr = (struct data_reference *)
VARRAY_GENERIC_PTR (datarefs, i);
- if (dr && DR_ACCESS_FNS (dr))
- varray_clear (DR_ACCESS_FNS (dr));
+ if (dr)
+ {
+ VEC_free (tree, heap, DR_ACCESS_FNS (dr));
+ free (dr);
+ }
}
varray_clear (datarefs);
}
OSDN Git Service
