tree, tree, tree, tree, tree,
struct ptr_info_def *,
enum data_ref_type);
+static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
+ struct data_reference *,
+ struct data_reference *);
/* Determine if PTR and DECL may alias, the result is put in ALIASED.
- Return FALSE if there is no type memory tag for PTR.
-*/
+ Return FALSE if there is no symbol memory tag for PTR. */
+
static bool
ptr_decl_may_alias_p (tree ptr, tree decl,
struct data_reference *ptr_dr,
gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
- tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
+ tag = get_var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
if (!tag)
tag = DR_MEMTAG (ptr_dr);
if (!tag)
/* Determine if two pointers may alias, the result is put in ALIASED.
- Return FALSE if there is no type memory tag for one of the pointers.
-*/
+ Return FALSE if there is no symbol memory tag for one of the pointers. */
+
static bool
ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b,
struct data_reference *dra,
{
tree tag_a, tag_b;
- tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->type_mem_tag;
+ tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->symbol_mem_tag;
if (!tag_a)
tag_a = DR_MEMTAG (dra);
if (!tag_a)
return false;
- tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->type_mem_tag;
+ tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->symbol_mem_tag;
if (!tag_b)
tag_b = DR_MEMTAG (drb);
if (!tag_b)
/* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
- Return FALSE if there is no type memory tag for one of the symbols.
-*/
+ Return FALSE if there is no symbol memory tag for one of the symbols. */
+
static bool
may_alias_p (tree base_a, tree base_b,
struct data_reference *dra,
/* Dump into FILE all the data references from DATAREFS. */
void
-dump_data_references (FILE *file,
- varray_type datarefs)
+dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
{
unsigned int i;
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
- dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
+ struct data_reference *dr;
+
+ for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
+ dump_data_reference (file, dr);
}
-/* Dump into FILE all the dependence relations from DDR. */
+/* Dump into FILE all the dependence relations from DDRS. */
void
dump_data_dependence_relations (FILE *file,
- varray_type ddr)
+ VEC (ddr_p, heap) *ddrs)
{
unsigned int i;
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
- dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
+ struct data_dependence_relation *ddr;
+
+ for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+ dump_data_dependence_relation (file, ddr);
}
/* Dump function for a DATA_REFERENCE structure. */
fprintf (outf, "\n");
}
+/* Print a vector of direction vectors. */
+
+void
+print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
+ int length)
+{
+ unsigned j;
+ lambda_vector v;
+
+ for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
+ print_direction_vector (outf, v, length);
+}
+
+/* Print a vector of distance vectors. */
+
+void
+print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
+ int length)
+{
+ unsigned j;
+ lambda_vector v;
+
+ for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
+ print_lambda_vector (outf, v, length);
+}
+
+/* Debug version. */
+
+void
+debug_data_dependence_relation (struct data_dependence_relation *ddr)
+{
+ dump_data_dependence_relation (stderr, ddr);
+}
+
/* Dump function for a DATA_DEPENDENCE_RELATION structure. */
void
else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
unsigned int i;
+ struct loop *loopi;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
}
+ fprintf (outf, " loop nest: (");
+ for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
+ fprintf (outf, "%d ", loopi->num);
+ fprintf (outf, ")\n");
+
for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
{
fprintf (outf, " distance_vector: ");
print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
- DDR_SIZE_VECT (ddr));
+ DDR_NB_LOOPS (ddr));
}
for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
{
fprintf (outf, " direction_vector: ");
print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
- DDR_SIZE_VECT (ddr));
+ DDR_NB_LOOPS (ddr));
}
}
considered nest. */
void
-dump_dist_dir_vectors (FILE *file, varray_type ddrs)
+dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
{
unsigned int i, j;
+ struct data_dependence_relation *ddr;
+ lambda_vector v;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
- {
- struct data_dependence_relation *ddr =
- (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (ddrs, i);
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
- && DDR_AFFINE_P (ddr))
- {
- for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
- {
- fprintf (file, "DISTANCE_V (");
- print_lambda_vector (file, DDR_DIST_VECT (ddr, j),
- DDR_SIZE_VECT (ddr));
- fprintf (file, ")\n");
- }
+ for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
+ {
+ for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
+ {
+ fprintf (file, "DISTANCE_V (");
+ print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
+ fprintf (file, ")\n");
+ }
+
+ for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
+ {
+ fprintf (file, "DIRECTION_V (");
+ print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
+ fprintf (file, ")\n");
+ }
+ }
- for (j = 0; j < DDR_NUM_DIR_VECTS (ddr); j++)
- {
- fprintf (file, "DIRECTION_V (");
- print_direction_vector (file, DDR_DIR_VECT (ddr, j),
- DDR_SIZE_VECT (ddr));
- fprintf (file, ")\n");
- }
- }
- }
fprintf (file, "\n\n");
}
/* Dumps the data dependence relations DDRS in FILE. */
void
-dump_ddrs (FILE *file, varray_type ddrs)
+dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
{
unsigned int i;
+ struct data_dependence_relation *ddr;
+
+ for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+ dump_data_dependence_relation (file, ddr);
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
- {
- struct data_dependence_relation *ddr =
- (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (ddrs, i);
- dump_data_dependence_relation (file, ddr);
- }
fprintf (file, "\n\n");
}
switch (TREE_CODE (base_address))
{
case SSA_NAME:
- *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
+ *memtag = get_var_ann (SSA_NAME_VAR (base_address))->symbol_mem_tag;
if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
*memtag = get_var_ann (
- SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
+ SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->symbol_mem_tag;
break;
case ADDR_EXPR:
*memtag = TREE_OPERAND (base_address, 0);
static struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
struct data_reference *b,
- int nb_loops)
+ VEC (loop_p, heap) *loop_nest)
{
struct data_dependence_relation *res;
bool differ_p, known_dependence;
DDR_ARE_DEPENDENT (res) = chrec_known;
return res;
}
-
+
DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
- DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
- DDR_SIZE_VECT (res) = nb_loops;
+ DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
+ DDR_LOOP_NEST (res) = loop_nest;
DDR_DIR_VECTS (res) = NULL;
DDR_DIST_VECTS (res) = NULL;
SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
SUB_DISTANCE (subscript) = chrec_dont_know;
- VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
+ VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
}
-
+
return res;
}
}
DDR_ARE_DEPENDENT (ddr) = chrec;
- varray_clear (DDR_SUBSCRIPTS (ddr));
+ VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
}
/* The dependence relation DDR cannot be represented by a distance
}
gcd_alpha_beta = S[0][0];
+ /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
+ but that is a quite strange case. Instead of ICEing, answer
+ don't know. */
+ if (gcd_alpha_beta == 0)
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ goto end_analyze_subs_aa;
+ }
+
/* The classic "gcd-test". */
if (!int_divides_p (gcd_alpha_beta, gamma))
{
}
}
-\f
+/* 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;
-/* This section contains the affine functions dependences detector. */
+ 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;
-/* Compute the classic per loop distance vector.
+ VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
+}
- DDR is the data dependence relation to build a vector from.
- NB_LOOPS is the total number of loops we are considering.
- FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
- loop nest.
- Return FALSE when fail to represent the data dependence as a distance
- vector.
- Return TRUE otherwise. */
+/* Helper function for uniquely inserting direction vectors. */
-static bool
-build_classic_dist_vector (struct data_dependence_relation *ddr,
- int first_loop_depth)
+static void
+save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
{
unsigned i;
- lambda_vector dist_v, init_v;
- int nb_loops = DDR_SIZE_VECT (ddr);
- bool init_b = false;
-
- DDR_SIZE_VECT (ddr) = nb_loops;
- dist_v = lambda_vector_new (nb_loops);
- init_v = lambda_vector_new (nb_loops);
+ lambda_vector v;
- if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return true;
+ 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++)
{
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
- return true;
+ return false;
}
- access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
- access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
+ 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, 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))
- {
- /* Example: when there are two consecutive loops,
-
- | loop_1
- | A[{0, +, 1}_1]
- | endloop_1
- | loop_2
- | A[{0, +, 1}_2]
- | endloop_2
-
- the dependence relation cannot be captured by the
- distance abstraction. */
- non_affine_dependence_relation (ddr);
- return true;
- }
+ 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
| endloop_2
| 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_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_depth >= 0);
- gcc_assert (loop_depth < nb_loops);
+ 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 true;
+ return false;
}
dist = int_cst_value (SUB_DISTANCE (subscript));
- /* This is the subscript coupling test.
+ /* 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
- There is no dependence. */
- if (init_v[loop_depth] != 0
- && dist_v[loop_depth] != dist)
+ */
+ if (init_v[index] != 0 && dist_v[index] != dist)
{
finalize_ddr_dependent (ddr, chrec_known);
- return true;
+ return false;
}
- dist_v[loop_depth] = dist;
- init_v[loop_depth] = 1;
- init_b = true;
+ dist_v[index] = dist;
+ init_v[index] = 1;
+ *init_b = true;
+ }
+ else
+ {
+ /* 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;
}
}
- /* Save the distance vector if we initialized one. */
- if (init_b)
- {
- lambda_vector save_v;
+ return true;
+}
- /* Verify a basic constraint: classic distance vectors should always
- be lexicographically positive. */
- if (!lambda_vector_lexico_pos (dist_v, DDR_SIZE_VECT (ddr)))
- {
- if (DDR_SIZE_VECT (ddr) == 1)
- /* This one is simple to fix, and can be fixed.
- Multidimensional arrays cannot be fixed that simply. */
- lambda_vector_negate (dist_v, dist_v, DDR_SIZE_VECT (ddr));
- else
- /* This is not valid: we need the delta test for properly
- fixing all this. */
- return false;
- }
+/* Return true when the DDR contains two data references that have the
+ same access functions. */
- save_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
- lambda_vector_copy (dist_v, save_v, DDR_SIZE_VECT (ddr));
- VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), save_v);
+static bool
+same_access_functions (struct data_dependence_relation *ddr)
+{
+ unsigned i;
- /* There is nothing more to do when there are no outer loops. */
- if (DDR_SIZE_VECT (ddr) == 1)
- goto classic_dist_done;
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ tree access_fun_a = DR_ACCESS_FN (DDR_A (ddr), i);
+ tree access_fun_b = DR_ACCESS_FN (DDR_B (ddr), i);
+ tree difference = chrec_fold_minus (integer_type_node, access_fun_a,
+ access_fun_b);
+ if (TREE_CODE (difference) != INTEGER_CST
+ || !integer_zerop (difference))
+ return false;
}
- /* 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
- */
- {
- struct loop *lca, *loop_a, *loop_b;
- struct data_reference *a = DDR_A (ddr);
- struct data_reference *b = DDR_B (ddr);
- 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_depth = lca->depth - first_loop_depth;
+ return true;
+}
- 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. */
- while (lca->depth != 0)
- {
- /* If we're considering just a sub-nest, then don't record
- any information on the outer loops. */
- if (lca_depth < 0)
- break;
+/* Helper function for the case where DDR_A and DDR_B are the same
+ multivariate access function. */
- gcc_assert (lca_depth < nb_loops);
+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;
- /* 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:
+ /* Polynomials with more than 2 variables are not handled yet. */
+ if (TREE_CODE (c_0) != INTEGER_CST)
+ {
+ DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+ return;
+ }
- | loop_1
- | loop_2
- | A[10]
- | endloop_2
- | endloop_1
+ 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));
- Saved vectors are of the form (dist_in_1, dist_in_2).
- First, we save (0, 1), then we have to save (1, 0). */
- if (init_v[lca_depth] == 0)
- {
- lambda_vector save_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
+ /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
+ dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
+ save_dist_v (ddr, dist_v);
- lambda_vector_copy (dist_v, save_v, DDR_SIZE_VECT (ddr));
- save_v[lca_depth] = 1;
- VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), save_v);
- }
+ add_outer_distances (ddr, dist_v, x_1);
+}
- lca = lca->outer;
- lca_depth = lca->depth - first_loop_depth;
- }
- }
+/* Helper function for the case where DDR_A and DDR_B are the same
+ access functions. */
- classic_dist_done:;
+static void
+add_other_self_distances (struct data_dependence_relation *ddr)
+{
+ lambda_vector dist_v;
+ unsigned i;
+ int index_carry = DDR_NB_LOOPS (ddr);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
- fprintf (dump_file, "(build_classic_dist_vector\n");
+ tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
- for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+ if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
{
- fprintf (dump_file, " dist_vector = (");
- print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
- DDR_SIZE_VECT (ddr));
- fprintf (dump_file, " )\n");
+ if (!evolution_function_is_univariate_p (access_fun))
+ {
+ if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
+ {
+ DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+ return;
+ }
+
+ add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
+ return;
+ }
+
+ index_carry = MIN (index_carry,
+ index_in_loop_nest (CHREC_VARIABLE (access_fun),
+ DDR_LOOP_NEST (ddr)));
}
- fprintf (dump_file, ")\n");
}
- return true;
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ add_outer_distances (ddr, dist_v, index_carry);
}
-/* 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_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. */
+/* 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_dir_vector (struct data_dependence_relation *ddr,
- int first_loop_depth)
+build_classic_dist_vector (struct data_dependence_relation *ddr)
{
- unsigned i;
- lambda_vector dir_v, init_v;
- int nb_loops = DDR_SIZE_VECT (ddr);
bool init_b = false;
-
- dir_v = lambda_vector_new (nb_loops);
- init_v = lambda_vector_new (nb_loops);
+ int index_carry = DDR_NB_LOOPS (ddr);
+ lambda_vector dist_v;
- DDR_SIZE_VECT (ddr) = nb_loops;
-
if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
return true;
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+
+ if (same_access_functions (ddr))
{
- tree access_fn_a, access_fn_b;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
+ /* Save the 0 vector. */
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ save_dist_v (ddr, dist_v);
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
- {
- non_affine_dependence_relation (ddr);
- return true;
- }
+ if (DDR_NB_LOOPS (ddr) > 1)
+ add_other_self_distances (ddr);
- access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
- access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
- if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
- && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
- {
- 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)
- && !flow_loop_nested_p (loop_b, loop_a))
- {
- /* Example: when there are two consecutive loops,
+ return true;
+ }
- | loop_1
- | A[{0, +, 1}_1]
- | endloop_1
- | loop_2
- | A[{0, +, 1}_2]
- | endloop_2
+ 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;
- the dependence relation cannot be captured by the
- distance abstraction. */
- non_affine_dependence_relation (ddr);
- return true;
+ /* 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));
+ subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
+ 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);
+
+ /* 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));
+ save_dist_v (ddr, save_v);
- /* 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. */
- loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
- 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_depth >= 0);
- gcc_assert (loop_depth < nb_loops);
-
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ if (DDR_NB_LOOPS (ddr) > 1)
{
- non_affine_dependence_relation (ddr);
- return true;
- }
+ lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- dist = int_cst_value (SUB_DISTANCE (subscript));
+ subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
+ compute_subscript_distance (ddr);
+ build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ opposite_v, &init_b, &index_carry);
- if (dist == 0)
- dir = dir_equal;
- else if (dist > 0)
- dir = dir_positive;
- else if (dist < 0)
- dir = dir_negative;
-
- /* This is the subscript coupling test.
- | loop i = 0, N, 1
- | T[i+1][i] = ...
- | ... = T[i][i]
- | endloop
- There is no dependence. */
- if (init_v[loop_depth] != 0
- && dir != 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 true;
+ add_outer_distances (ddr, dist_v, index_carry);
+ add_outer_distances (ddr, opposite_v, index_carry);
}
-
- dir_v[loop_depth] = dir;
- init_v[loop_depth] = 1;
- init_b = true;
}
}
+ 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.
- /* Save the direction vector if we initialized one. */
- if (init_b)
+ | 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))
{
- lambda_vector save_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
+ unsigned i;
- lambda_vector_copy (dir_v, save_v, DDR_SIZE_VECT (ddr));
- VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), save_v);
+ 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");
}
- /* 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
- */
- {
- struct loop *lca, *loop_a, *loop_b;
- struct data_reference *a = DDR_A (ddr);
- struct data_reference *b = DDR_B (ddr);
- 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_depth = lca->depth - first_loop_depth;
+ return true;
+}
- gcc_assert (lca_depth >= 0);
- gcc_assert (lca_depth < nb_loops);
+/* 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. */
- while (lca->depth != 0)
- {
- /* If we're considering just a sub-nest, then don't record
- any information on the outer loops. */
- if (lca_depth < 0)
- break;
+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;
+}
- gcc_assert (lca_depth < nb_loops);
+/* Compute the classic per loop direction vector. DDR is the data
+ dependence relation to build a vector from. */
- if (init_v[lca_depth] == 0)
- {
- lambda_vector save_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
+static void
+build_classic_dir_vector (struct data_dependence_relation *ddr)
+{
+ unsigned i, j;
+ lambda_vector dist_v;
- lambda_vector_copy (dir_v, save_v, DDR_SIZE_VECT (ddr));
- save_v[lca_depth] = dir_positive;
- VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), save_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));
- lca = lca->outer;
- lca_depth = lca->depth - first_loop_depth;
- }
- }
+ for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
+ dir_v[j] = dir_from_dist (dist_v[j]);
- return true;
+ save_dir_v (ddr, dir_v);
+ }
}
-/* Computes the conflicting iterations, and initialize DDR. */
+/* Helper function. Returns true when there is a dependence between
+ data references DRA and DRB. */
-static void
-subscript_dependence_tester (struct data_dependence_relation *ddr,
- int loop_nest_depth)
+static bool
+subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
+ struct data_reference *dra,
+ struct data_reference *drb)
{
unsigned int i;
- struct data_reference *dra = DDR_A (ddr);
- struct data_reference *drb = DDR_B (ddr);
tree last_conflicts;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(subscript_dependence_tester \n");
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ struct subscript *subscript;
+
+ for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
+ i++)
{
tree overlaps_a, overlaps_b;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
-
+
analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
DR_ACCESS_FN (drb, i),
&overlaps_a, &overlaps_b,
&last_conflicts);
-
+
if (chrec_contains_undetermined (overlaps_a)
|| chrec_contains_undetermined (overlaps_b))
{
finalize_ddr_dependent (ddr, chrec_dont_know);
dependence_stats.num_dependence_undetermined++;
- goto subs_test_end;
+ return false;
}
-
+
else if (overlaps_a == chrec_known
|| overlaps_b == chrec_known)
{
finalize_ddr_dependent (ddr, chrec_known);
dependence_stats.num_dependence_independent++;
- goto subs_test_end;
+ return false;
}
-
+
else
{
SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
}
}
- dependence_stats.num_dependence_dependent++;
+ return true;
+}
+
+/* Computes the conflicting iterations, and initialize DDR. */
+
+static void
+subscript_dependence_tester (struct data_dependence_relation *ddr)
+{
+
+ 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)))
+ dependence_stats.num_dependence_dependent++;
- subs_test_end:;
compute_subscript_distance (ddr);
- if (build_classic_dist_vector (ddr, loop_nest_depth))
- build_classic_dir_vector (ddr, loop_nest_depth);
+ if (build_classic_dist_vector (ddr))
+ build_classic_dir_vector (ddr);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
subscript. */
static void
-compute_affine_dependence (struct data_dependence_relation *ddr,
- int loop_nest_depth)
+compute_affine_dependence (struct data_dependence_relation *ddr)
{
struct data_reference *dra = DDR_A (ddr);
struct data_reference *drb = DDR_B (ddr);
if (access_functions_are_affine_or_constant_p (dra)
&& access_functions_are_affine_or_constant_p (drb))
- subscript_dependence_tester (ddr, loop_nest_depth);
+ subscript_dependence_tester (ddr);
/* As a last case, if the dependence cannot be determined, or if
the dependence is considered too difficult to determine, answer
compute_self_dependence (struct data_dependence_relation *ddr)
{
unsigned int i;
- lambda_vector dir_v, dist_v;
+ struct subscript *subscript;
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
+ i++)
{
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
-
/* The accessed index overlaps for each iteration. */
SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
}
/* The distance vector is the zero vector. */
- dist_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
- dir_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
-
- VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
- VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
-
- compute_subscript_distance (ddr);
+ save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+ save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
}
-/* Compute a subset of the data dependence relation graph. Don't
- compute read-read and self relations if
- COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation
- of the opposite relation, i.e. when AB has been computed, don't compute BA.
- DATAREFS contains a list of data references, and the result is set
- in DEPENDENCE_RELATIONS. */
+/* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
+ the data references in DATAREFS, in the LOOP_NEST. When
+ COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
+ relations. */
static void
-compute_all_dependences (varray_type datarefs,
- VEC(ddr_p,heap) **dependence_relations,
- bool compute_self_and_read_read_dependences,
- unsigned nb_loops, unsigned loop_nest_depth)
+compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
+ VEC (ddr_p, heap) **dependence_relations,
+ VEC (loop_p, heap) *loop_nest,
+ bool compute_self_and_rr)
{
- unsigned int i, j, N;
-
- N = VARRAY_ACTIVE_SIZE (datarefs);
+ struct data_dependence_relation *ddr;
+ struct data_reference *a, *b;
+ unsigned int i, j;
- /* Note that we specifically skip i == j because it's a self dependence, and
- use compute_self_dependence below. */
+ for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
+ for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
+ if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
+ {
+ ddr = initialize_data_dependence_relation (a, b, loop_nest);
+ VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+ compute_affine_dependence (ddr);
+ }
- for (i = 0; i < N; i++)
- for (j = i + 1; j < N; j++)
+ if (compute_self_and_rr)
+ for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
{
- struct data_reference *a, *b;
- struct data_dependence_relation *ddr;
-
- a = VARRAY_GENERIC_PTR (datarefs, i);
- b = VARRAY_GENERIC_PTR (datarefs, j);
-
- if (DR_IS_READ (a) && DR_IS_READ (b)
- && !compute_self_and_read_read_dependences)
- continue;
-
- ddr = initialize_data_dependence_relation (a, b, nb_loops);
+ ddr = initialize_data_dependence_relation (a, a, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_affine_dependence (ddr, loop_nest_depth);
+ compute_self_dependence (ddr);
}
-
- if (!compute_self_and_read_read_dependences)
- return;
-
- /* Compute self dependence relation of each dataref to itself. */
- for (i = 0; i < N; i++)
- {
- struct data_reference *a, *b;
- struct data_dependence_relation *ddr;
-
- a = VARRAY_GENERIC_PTR (datarefs, i);
- b = VARRAY_GENERIC_PTR (datarefs, i);
- ddr = initialize_data_dependence_relation (a, b, nb_loops);
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_self_dependence (ddr);
- }
}
/* Search the data references in LOOP, and record the information into
arithmetic as if they were array accesses, etc. */
tree
-find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
+find_data_references_in_loop (struct loop *loop,
+ VEC (data_reference_p, heap) **datarefs)
{
basic_block bb, *bbs;
unsigned int i;
dr = create_data_ref (opnd0, stmt, false);
if (dr)
{
- VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
+ VEC_safe_push (data_reference_p, heap, *datarefs, dr);
one_inserted = true;
}
}
dr = create_data_ref (opnd1, stmt, true);
if (dr)
{
- VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
+ VEC_safe_push (data_reference_p, heap, *datarefs, dr);
one_inserted = true;
}
}
dr = create_data_ref (TREE_VALUE (args), stmt, true);
if (dr)
{
- VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
+ VEC_safe_push (data_reference_p, heap, *datarefs, dr);
one_inserted = true;
}
}
DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
DR_MEMTAG (res) = NULL_TREE;
DR_PTR_INFO (res) = NULL;
- VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
+ VEC_safe_push (data_reference_p, heap, *datarefs, res);
free (bbs);
return chrec_dont_know;
return NULL_TREE;
}
-\f
+/* Recursive helper function. */
-/* This section contains all the entry points. */
+static bool
+find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) *loop_nest)
+{
+ /* Inner loops of the nest should not contain siblings. Example:
+ when there are two consecutive loops,
+
+ | loop_0
+ | loop_1
+ | A[{0, +, 1}_1]
+ | endloop_1
+ | loop_2
+ | A[{0, +, 1}_2]
+ | endloop_2
+ | endloop_0
+
+ the dependence relation cannot be captured by the distance
+ abstraction. */
+ if (loop->next)
+ return false;
+
+ VEC_safe_push (loop_p, heap, loop_nest, loop);
+ if (loop->inner)
+ return find_loop_nest_1 (loop->inner, loop_nest);
+ return true;
+}
+
+/* Return false when the LOOP is not well nested. Otherwise return
+ true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
+ contain the loops from the outermost to the innermost, as they will
+ appear in the classic distance vector. */
+
+static bool
+find_loop_nest (struct loop *loop, VEC (loop_p, heap) *loop_nest)
+{
+ VEC_safe_push (loop_p, heap, loop_nest, loop);
+ if (loop->inner)
+ return find_loop_nest_1 (loop->inner, loop_nest);
+ return true;
+}
/* Given a loop nest LOOP, the following vectors are returned:
- *DATAREFS is initialized to all the array elements contained in this loop,
- *DEPENDENCE_RELATIONS contains the relations between the data references.
+ DATAREFS is initialized to all the array elements contained in this loop,
+ DEPENDENCE_RELATIONS contains the relations between the data references.
Compute read-read and self relations if
COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
void
compute_data_dependences_for_loop (struct loop *loop,
bool compute_self_and_read_read_dependences,
- varray_type *datarefs,
- varray_type *dependence_relations)
+ VEC (data_reference_p, heap) **datarefs,
+ VEC (ddr_p, heap) **dependence_relations)
{
- unsigned int i, nb_loops;
- VEC(ddr_p,heap) *allrelations;
- struct data_dependence_relation *ddr;
struct loop *loop_nest = loop;
+ VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
- while (loop_nest && loop_nest->outer && loop_nest->outer->outer)
- loop_nest = loop_nest->outer;
-
- nb_loops = loop_nest->level;
memset (&dependence_stats, 0, sizeof (dependence_stats));
- /* If one of the data references is not computable, give up without
- spending time to compute other dependences. */
- if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
+ /* If the loop nest is not well formed, or one of the data references
+ is not computable, give up without spending time to compute other
+ dependences. */
+ if (!loop_nest
+ || !find_loop_nest (loop_nest, vloops)
+ || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
{
struct data_dependence_relation *ddr;
/* Insert a single relation into dependence_relations:
chrec_dont_know. */
- ddr = initialize_data_dependence_relation (NULL, NULL, nb_loops);
- VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- return;
+ ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
+ VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
}
-
- allrelations = NULL;
- compute_all_dependences (*datarefs, &allrelations,
- compute_self_and_read_read_dependences,
- nb_loops, loop_nest->depth);
-
- /* FIXME: We copy the contents of allrelations back to a VARRAY
- because the vectorizer has not yet been converted to use VECs. */
- for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
- VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+ else
+ compute_all_dependences (*datarefs, dependence_relations, vloops,
+ compute_self_and_read_read_dependences);
if (dump_file && (dump_flags & TDF_STATS))
{
analyze_all_data_dependences (struct loops *loops)
{
unsigned int i;
- varray_type datarefs;
- varray_type dependence_relations;
int nb_data_refs = 10;
-
- VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
- VARRAY_GENERIC_PTR_INIT (dependence_relations,
- nb_data_refs * nb_data_refs,
- "dependence_relations");
+ VEC (data_reference_p, heap) *datarefs =
+ VEC_alloc (data_reference_p, heap, nb_data_refs);
+ VEC (ddr_p, heap) *dependence_relations =
+ VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
/* Compute DDs on the whole function. */
compute_data_dependences_for_loop (loops->parray[0], false,
unsigned nb_bot_relations = 0;
unsigned nb_basename_differ = 0;
unsigned nb_chrec_relations = 0;
+ struct data_dependence_relation *ddr;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
{
- struct data_dependence_relation *ddr;
- ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
-
if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
nb_top_relations++;
return;
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
- varray_clear (DDR_SUBSCRIPTS (ddr));
+ VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
+
free (ddr);
}
DEPENDENCE_RELATIONS. */
void
-free_dependence_relations (varray_type dependence_relations)
+free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
{
unsigned int i;
- if (dependence_relations == NULL)
- return;
+ struct data_dependence_relation *ddr;
+
+ for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+ free_dependence_relation (ddr);
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
- free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
- varray_clear (dependence_relations);
+ VEC_free (ddr_p, heap, dependence_relations);
}
/* Free the memory used by the data references from DATAREFS. */
void
-free_data_refs (varray_type datarefs)
+free_data_refs (VEC (data_reference_p, heap) *datarefs)
{
unsigned int i;
-
- if (datarefs == NULL)
- return;
+ struct data_reference *dr;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
+ for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
{
- struct data_reference *dr = (struct data_reference *)
- VARRAY_GENERIC_PTR (datarefs, i);
- if (dr)
- {
- DR_FREE_ACCESS_FNS (dr);
- free (dr);
- }
+ if (DR_TYPE(dr) == ARRAY_REF_TYPE)
+ VEC_free (tree, heap, (dr)->object_info.access_fns);
+ else
+ VEC_free (tree, heap, (dr)->first_location.access_fns);
+
+ free (dr);
}
- varray_clear (datarefs);
+ VEC_free (data_reference_p, heap, datarefs);
}
OSDN Git Service
