#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
+#include "langhooks.h"
static struct datadep_stats
{
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 symbol memory tag for PTR. */
struct data_reference *ptr_dr,
bool *aliased)
{
- tree tag;
-
+ tree tag = NULL_TREE;
+ struct ptr_info_def *pi = DR_PTR_INFO (ptr_dr);
+
gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
- tag = get_var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
+ if (pi)
+ tag = pi->name_mem_tag;
+ if (!tag)
+ tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
if (!tag)
tag = DR_MEMTAG (ptr_dr);
if (!tag)
return false;
-
+
*aliased = is_aliased_with (tag, decl);
return true;
}
struct data_reference *drb,
bool *aliased)
{
- tree tag_a, tag_b;
+ tree tag_a = NULL_TREE, tag_b = NULL_TREE;
+ struct ptr_info_def *pi_a = DR_PTR_INFO (dra);
+ struct ptr_info_def *pi_b = DR_PTR_INFO (drb);
- 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))->symbol_mem_tag;
- if (!tag_b)
- tag_b = DR_MEMTAG (drb);
- if (!tag_b)
- return false;
+ if (pi_a && pi_a->name_mem_tag && pi_b && pi_b->name_mem_tag)
+ {
+ tag_a = pi_a->name_mem_tag;
+ tag_b = pi_b->name_mem_tag;
+ }
+ else
+ {
+ tag_a = symbol_mem_tag (SSA_NAME_VAR (ptr_a));
+ if (!tag_a)
+ tag_a = DR_MEMTAG (dra);
+ if (!tag_a)
+ return false;
+
+ tag_b = symbol_mem_tag (SSA_NAME_VAR (ptr_b));
+ if (!tag_b)
+ tag_b = DR_MEMTAG (drb);
+ if (!tag_b)
+ return false;
+ }
*aliased = (tag_a == tag_b);
return true;
}
return false;
}
+/* Determine if two record/union accesses are aliased. Return TRUE if they
+ differ. */
+static bool
+record_record_differ_p (struct data_reference *dra,
+ struct data_reference *drb)
+{
+ bool aliased;
+ tree base_a = DR_BASE_OBJECT (dra);
+ tree base_b = DR_BASE_OBJECT (drb);
+
+ if (TREE_CODE (base_b) != COMPONENT_REF
+ || TREE_CODE (base_a) != COMPONENT_REF)
+ return false;
+
+ /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
+ For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
+ Probably will be unnecessary with struct alias analysis. */
+ while (TREE_CODE (base_b) == COMPONENT_REF)
+ base_b = TREE_OPERAND (base_b, 0);
+ while (TREE_CODE (base_a) == COMPONENT_REF)
+ base_a = TREE_OPERAND (base_a, 0);
+
+ if (TREE_CODE (base_a) == INDIRECT_REF
+ && TREE_CODE (base_b) == INDIRECT_REF
+ && ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
+ TREE_OPERAND (base_b, 0),
+ dra, drb, &aliased)
+ && !aliased)
+ return true;
+ else
+ return false;
+}
/* Determine if an array access (BASE_A) and a record/union access (BASE_B)
are not aliased. Return TRUE if they differ. */
return true;
}
+ /* Compare two record/union accesses (b.c[i] or p->c[i]). */
+ if (record_record_differ_p (a, b))
+ {
+ *differ_p = true;
+ return true;
+ }
+
return false;
}
/* 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");
}
\f
-/* Estimate the number of iterations from the size of the data and the
- access functions. */
-
-static void
-estimate_niter_from_size_of_data (struct loop *loop,
- tree opnd0,
- tree access_fn,
- tree stmt)
-{
- tree estimation = NULL_TREE;
- tree array_size, data_size, element_size;
- tree init, step;
-
- init = initial_condition (access_fn);
- step = evolution_part_in_loop_num (access_fn, loop->num);
-
- array_size = TYPE_SIZE (TREE_TYPE (opnd0));
- element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
- if (array_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);
-
- if (init != NULL_TREE
- && step != NULL_TREE
- && TREE_CODE (init) == INTEGER_CST
- && TREE_CODE (step) == INTEGER_CST)
- {
- tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step);
- tree sign = fold_binary (GT_EXPR, boolean_type_node, i_plus_s, init);
-
- if (sign == boolean_true_node)
- estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
- fold_build2 (MINUS_EXPR, integer_type_node,
- data_size, init), step);
-
- /* When the step is negative, as in PR23386: (init = 3, step =
- 0ffffffff, data_size = 100), we have to compute the
- estimation as ceil_div (init, 0 - step) + 1. */
- else if (sign == boolean_false_node)
- estimation =
- fold_build2 (PLUS_EXPR, integer_type_node,
- fold_build2 (CEIL_DIV_EXPR, integer_type_node,
- init,
- fold_build2 (MINUS_EXPR, unsigned_type_node,
- integer_zero_node, step)),
- integer_one_node);
-
- if (estimation)
- record_estimate (loop, estimation, boolean_true_node, stmt);
- }
-}
-
/* Given an ARRAY_REF node REF, records its access functions.
Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
i.e. the constant "3", then recursively call the function on opnd0,
i.e. the ARRAY_REF "A[i]".
- If ESTIMATE_ONLY is true, we just set the estimated number of loop
- iterations, we don't store the access function.
The function returns the base name: "A". */
static tree
analyze_array_indexes (struct loop *loop,
VEC(tree,heap) **access_fns,
- tree ref, tree stmt,
- bool estimate_only)
+ tree ref, tree stmt)
{
tree opnd0, opnd1;
tree access_fn;
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, opnd1));
- if (estimate_only
- && chrec_contains_undetermined (loop->estimated_nb_iterations))
- estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
-
- if (!estimate_only)
- VEC_safe_push (tree, heap, *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)
- return analyze_array_indexes (loop, access_fns, opnd0, stmt, estimate_only);
+ return analyze_array_indexes (loop, access_fns, opnd0, stmt);
/* Return the base name of the data access. */
else
return opnd0;
}
-/* For an array reference REF contained in STMT, attempt to bound the
- number of iterations in the loop containing STMT */
-
-void
-estimate_iters_using_array (tree stmt, tree ref)
-{
- analyze_array_indexes (loop_containing_stmt (stmt), NULL, ref, stmt,
- true);
-}
-
/* For a data reference REF contained in the statement STMT, initialize
a DATA_REFERENCE structure, and return it. IS_READ flag has to be
set to true when REF is in the right hand side of an
DR_REF (res) = ref;
acc_fns = VEC_alloc (tree, heap, 3);
DR_BASE_OBJECT (res) = analyze_array_indexes
- (loop_containing_stmt (stmt), &acc_fns, ref, stmt, false);
+ (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
DR_TYPE (res) = ARRAY_REF_TYPE;
DR_SET_ACCESS_FNS (res, acc_fns);
DR_IS_READ (res) = is_read;
switch (TREE_CODE (base_address))
{
case SSA_NAME:
- *memtag = get_var_ann (SSA_NAME_VAR (base_address))->symbol_mem_tag;
+ *memtag = symbol_mem_tag (SSA_NAME_VAR (base_address));
if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
- *memtag = get_var_ann (
- SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->symbol_mem_tag;
+ *memtag = symbol_mem_tag (SSA_NAME_VAR (TREE_OPERAND (memref, 0)));
break;
case ADDR_EXPR:
*memtag = TREE_OPERAND (base_address, 0);
*invariant = invariant_0 ? invariant_0 : invariant_1;
}
+/* Free the memory used by the data reference DR. */
+
+static void
+free_data_ref (data_reference_p dr)
+{
+ DR_FREE_ACCESS_FNS (dr);
+ free (dr);
+}
/* Function create_data_ref.
constant, type_size);
}
else
- DR_INIT (dr) = init_cond = ssize_int (0);;
-
+ DR_INIT (dr) = init_cond = ssize_int (0);
+
if (invariant)
DR_OFFSET (dr) = invariant;
else
/* Update access function. */
access_fn = DR_ACCESS_FN (dr, 0);
+ if (automatically_generated_chrec_p (access_fn))
+ {
+ free_data_ref (dr);
+ return NULL;
+ }
+
new_step = size_binop (TRUNC_DIV_EXPR,
fold_convert (ssizetype, step), type_size);
+ init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt);
+ new_step = chrec_convert (chrec_type (access_fn), new_step, stmt);
+ if (automatically_generated_chrec_p (init_cond)
+ || automatically_generated_chrec_p (new_step))
+ {
+ free_data_ref (dr);
+ return NULL;
+ }
access_fn = chrec_replace_initial_condition (access_fn, init_cond);
access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
int j;
for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
- {
- tree chrec_j = TREE_VEC_ELT (chrec, j);
- tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
- if (!integer_zerop
- (chrec_fold_minus
- (integer_type_node, chrec_j, chrec_j_1)))
- return false;
- }
+ if (!eq_evolutions_p (TREE_VEC_ELT (chrec, j),
+ TREE_VEC_ELT (chrec, j + 1)))
+ return false;
+
return true;
}
conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
}
+ conflicts_b = chrec_convert (integer_type_node, conflicts_b,
+ NULL_TREE);
+ conflicts_a = chrec_convert (integer_type_node, conflicts_a,
+ NULL_TREE);
difference = chrec_fold_minus
(integer_type_node, conflicts_b, conflicts_a);
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;
res = XNEW (struct data_dependence_relation);
DDR_A (res) = a;
DDR_B (res) = b;
+ DDR_LOOP_NEST (res) = NULL;
if (a == NULL || b == NULL)
{
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
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_ziv_subscript \n");
+ chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
+ chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
switch (TREE_CODE (difference))
static tree
get_number_of_iters_for_loop (int loopnum)
{
- tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
+ struct loop *loop = get_loop (loopnum);
+ tree numiter = number_of_exit_cond_executions (loop);
+
+ if (TREE_CODE (numiter) == INTEGER_CST)
+ return numiter;
+
+ if (loop->estimate_state == EST_AVAILABLE)
+ {
+ tree type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
+ if (double_int_fits_to_tree_p (type, loop->estimated_nb_iterations))
+ return double_int_to_tree (type, loop->estimated_nb_iterations);
+ }
- if (TREE_CODE (numiter) != INTEGER_CST)
- numiter = current_loops->parray[loopnum]->estimated_nb_iterations;
- if (chrec_contains_undetermined (numiter))
- return NULL_TREE;
- return numiter;
+ return NULL_TREE;
}
/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
tree *last_conflicts)
{
bool value0, value1, value2;
- tree difference = chrec_fold_minus
- (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
+ tree difference;
+
+ chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
+ chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
+ difference = chrec_fold_minus
+ (integer_type_node, initial_condition (chrec_b), chrec_a);
if (!chrec_is_positive (initial_condition (difference), &value0))
{
*overlaps_b = integer_zero_node;
if (xz_p)
{
- TREE_VEC_ELT (*overlaps_a, 0) =
- chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
- overlaps_a_xz);
- *overlaps_b =
- chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
+ tree t0 = chrec_convert (integer_type_node,
+ TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
+ tree t1 = chrec_convert (integer_type_node, overlaps_a_xz,
+ NULL_TREE);
+ tree t2 = chrec_convert (integer_type_node, *overlaps_b,
+ NULL_TREE);
+ tree t3 = chrec_convert (integer_type_node, overlaps_b_xz,
+ NULL_TREE);
+
+ TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
+ t0, t1);
+ *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
*last_conflicts = last_conflicts_xz;
}
if (yz_p)
{
- TREE_VEC_ELT (*overlaps_a, 1) =
- chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
- overlaps_a_yz);
- *overlaps_b =
- chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
+ tree t0 = chrec_convert (integer_type_node,
+ TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
+ tree t1 = chrec_convert (integer_type_node, overlaps_a_yz, NULL_TREE);
+ tree t2 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
+ tree t3 = chrec_convert (integer_type_node, overlaps_b_yz, NULL_TREE);
+
+ TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
+ t0, t1);
+ *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
*last_conflicts = last_conflicts_yz;
}
if (xyz_p)
{
- TREE_VEC_ELT (*overlaps_a, 0) =
- chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
- overlaps_a_xyz);
- TREE_VEC_ELT (*overlaps_a, 1) =
- chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
- overlaps_a_xyz);
- *overlaps_b =
- chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
+ tree t0 = chrec_convert (integer_type_node,
+ TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
+ tree t1 = chrec_convert (integer_type_node, overlaps_a_xyz,
+ NULL_TREE);
+ tree t2 = chrec_convert (integer_type_node,
+ TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
+ tree t3 = chrec_convert (integer_type_node, overlaps_a_xyz,
+ NULL_TREE);
+ tree t4 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
+ tree t5 = chrec_convert (integer_type_node, overlaps_b_xyz,
+ NULL_TREE);
+
+ TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
+ t0, t1);
+ TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
+ t2, t3);
+ *overlaps_b = chrec_fold_plus (integer_type_node, t4, t5);
*last_conflicts = last_conflicts_xyz;
}
}
int init_a, init_b, gamma, gcd_alpha_beta;
int tau1, tau2;
lambda_matrix A, U, S;
- tree difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
- if (integer_zerop (difference))
+ if (eq_evolutions_p (chrec_a, chrec_b))
{
- /* The difference is equal to zero: the accessed index
- overlaps for each iteration in the loop. */
+ /* The accessed index overlaps for each iteration in the
+ loop. */
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
*last_conflicts = chrec_dont_know;
there is no dependence. This function outputs a description of
the iterations that hold the intersections. */
-
nb_vars_a = nb_vars_in_chrec (chrec_a);
nb_vars_b = nb_vars_in_chrec (chrec_b);
}
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))
{
static bool
can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
{
- tree diff;
+ tree diff, type, left_a, left_b, right_b;
if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
|| chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
/* FIXME: For the moment not handled. Might be refined later. */
return false;
- diff = chrec_fold_minus (chrec_type (*chrec_a), CHREC_LEFT (*chrec_a),
- CHREC_LEFT (*chrec_b));
+ type = chrec_type (*chrec_a);
+ left_a = CHREC_LEFT (*chrec_a);
+ left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
+ diff = chrec_fold_minus (type, left_a, left_b);
+
if (!evolution_function_is_constant_p (diff))
return false;
*chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
diff, CHREC_RIGHT (*chrec_a));
+ right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
*chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
- integer_zero_node,
- CHREC_RIGHT (*chrec_b));
+ build_int_cst (type, 0),
+ right_b);
return true;
}
dependence_stats.num_miv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_miv_subscript \n");
-
+
+ chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
+ chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
- if (chrec_zerop (difference))
+ if (eq_evolutions_p (chrec_a, chrec_b))
{
/* Access functions are the same: all the elements are accessed
in the same order. */
}
}
-\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;
+
+ 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;
-/* This section contains the affine functions dependences detector. */
+ VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
+}
-/* Compute the classic per loop distance vector.
+/* Helper function for uniquely inserting direction vectors. */
+
+static void
+save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
+{
+ unsigned i;
+ lambda_vector v;
- 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. */
+ 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 (struct data_dependence_relation *ddr,
- int first_loop_depth)
+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 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);
-
- if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return true;
+ 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++)
+ if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
+ DR_ACCESS_FN (DDR_B (ddr), i)))
+ 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;
+ ddr = initialize_data_dependence_relation (a, a, loop_nest);
+ VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+ compute_self_dependence (ddr);
+ }
+}
+
+/* Stores the locations of memory references in STMT to REFERENCES. Returns
+ true if STMT clobbers memory, false otherwise. */
+
+bool
+get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
+{
+ bool clobbers_memory = false;
+ data_ref_loc *ref;
+ tree *op0, *op1, args, call;
+
+ *references = NULL;
+
+ /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
+ Calls have side-effects, except those to const or pure
+ functions. */
+ call = get_call_expr_in (stmt);
+ if ((call
+ && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
+ || (TREE_CODE (stmt) == ASM_EXPR
+ && ASM_VOLATILE_P (stmt)))
+ clobbers_memory = true;
+
+ if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+ return clobbers_memory;
+
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ {
+ op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
+ op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
+
+ if (DECL_P (*op1)
+ || REFERENCE_CLASS_P (*op1))
+ {
+ ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+ ref->pos = op1;
+ ref->is_read = true;
+ }
- a = VARRAY_GENERIC_PTR (datarefs, i);
- b = VARRAY_GENERIC_PTR (datarefs, j);
+ if (DECL_P (*op0)
+ || REFERENCE_CLASS_P (*op0))
+ {
+ ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+ ref->pos = op0;
+ ref->is_read = false;
+ }
+ }
- if (DR_IS_READ (a) && DR_IS_READ (b)
- && !compute_self_and_read_read_dependences)
- continue;
+ if (call)
+ {
+ for (args = TREE_OPERAND (call, 1); args; args = TREE_CHAIN (args))
+ {
+ op0 = &TREE_VALUE (args);
+ if (DECL_P (*op0)
+ || REFERENCE_CLASS_P (*op0))
+ {
+ ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+ ref->pos = op0;
+ ref->is_read = true;
+ }
+ }
+ }
- ddr = initialize_data_dependence_relation (a, b, nb_loops);
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_affine_dependence (ddr, loop_nest_depth);
- }
+ return clobbers_memory;
+}
- if (!compute_self_and_read_read_dependences)
- return;
+/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
+ reference, returns false, otherwise returns true. */
- /* Compute self dependence relation of each dataref to itself. */
- for (i = 0; i < N; i++)
+static bool
+find_data_references_in_stmt (tree stmt,
+ VEC (data_reference_p, heap) **datarefs)
+{
+ unsigned i;
+ VEC (data_ref_loc, heap) *references;
+ data_ref_loc *ref;
+ bool ret = true;
+ data_reference_p dr;
+
+ if (get_references_in_stmt (stmt, &references))
{
- struct data_reference *a, *b;
- struct data_dependence_relation *ddr;
+ VEC_free (data_ref_loc, heap, references);
+ return false;
+ }
- 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);
+ for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
+ {
+ dr = create_data_ref (*ref->pos, stmt, ref->is_read);
+ if (dr)
+ VEC_safe_push (data_reference_p, heap, *datarefs, dr);
+ else
+ {
+ ret = false;
+ break;
+ }
}
+ VEC_free (data_ref_loc, heap, references);
+ return ret;
}
/* 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;
block_stmt_iterator bsi;
- struct data_reference *dr;
bbs = get_loop_body (loop);
bb = bbs[i];
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- {
+ {
tree stmt = bsi_stmt (bsi);
- /* 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 (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
- continue;
-
- switch (TREE_CODE (stmt))
+ if (!find_data_references_in_stmt (stmt, datarefs))
{
- case MODIFY_EXPR:
- {
- bool one_inserted = false;
- tree opnd0 = TREE_OPERAND (stmt, 0);
- tree opnd1 = TREE_OPERAND (stmt, 1);
-
- if (TREE_CODE (opnd0) == ARRAY_REF
- || TREE_CODE (opnd0) == INDIRECT_REF
- || TREE_CODE (opnd0) == COMPONENT_REF)
- {
- dr = create_data_ref (opnd0, stmt, false);
- if (dr)
- {
- VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
- one_inserted = true;
- }
- }
-
- if (TREE_CODE (opnd1) == ARRAY_REF
- || TREE_CODE (opnd1) == INDIRECT_REF
- || TREE_CODE (opnd1) == COMPONENT_REF)
- {
- dr = create_data_ref (opnd1, stmt, true);
- if (dr)
- {
- VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
- one_inserted = true;
- }
- }
-
- if (!one_inserted)
- goto insert_dont_know_node;
-
- 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
- || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF
- || TREE_CODE (TREE_VALUE (args)) == COMPONENT_REF)
- {
- dr = create_data_ref (TREE_VALUE (args), stmt, true);
- if (dr)
- {
- VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
- one_inserted = true;
- }
- }
-
- if (!one_inserted)
- goto insert_dont_know_node;
-
- break;
- }
-
- default:
- {
- struct data_reference *res;
-
- insert_dont_know_node:;
- res = XNEW (struct data_reference);
- DR_STMT (res) = NULL_TREE;
- DR_REF (res) = NULL_TREE;
- DR_BASE_OBJECT (res) = NULL;
- DR_TYPE (res) = ARRAY_REF_TYPE;
- DR_SET_ACCESS_FNS (res, NULL);
- DR_BASE_OBJECT (res) = NULL;
- DR_IS_READ (res) = false;
- DR_BASE_ADDRESS (res) = NULL_TREE;
- DR_OFFSET (res) = NULL_TREE;
- DR_INIT (res) = NULL_TREE;
- DR_STEP (res) = NULL_TREE;
- DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
- DR_MEMTAG (res) = NULL_TREE;
- DR_PTR_INFO (res) = NULL;
- VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
-
- free (bbs);
- return chrec_dont_know;
- }
+ struct data_reference *res;
+ res = XNEW (struct data_reference);
+ DR_STMT (res) = NULL_TREE;
+ DR_REF (res) = NULL_TREE;
+ DR_BASE_OBJECT (res) = NULL;
+ DR_TYPE (res) = ARRAY_REF_TYPE;
+ DR_SET_ACCESS_FNS (res, NULL);
+ DR_BASE_OBJECT (res) = NULL;
+ DR_IS_READ (res) = false;
+ DR_BASE_ADDRESS (res) = NULL_TREE;
+ DR_OFFSET (res) = NULL_TREE;
+ DR_INIT (res) = NULL_TREE;
+ DR_STEP (res) = NULL_TREE;
+ DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
+ DR_MEMTAG (res) = NULL_TREE;
+ DR_PTR_INFO (res) = NULL;
+ VEC_safe_push (data_reference_p, heap, *datarefs, res);
+
+ free (bbs);
+ return chrec_dont_know;
}
-
- /* When there are no defs in the loop, the loop is parallel. */
- if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
- loop->parallel_p = false;
}
}
-
free (bbs);
return NULL_TREE;
}
-\f
+/* Recursive helper function. */
+
+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;
-/* This section contains all the entry points. */
+ 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;
+ VEC (loop_p, heap) *loop_nest = NULL;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
- free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
- varray_clear (dependence_relations);
+ for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+ {
+ if (ddr == NULL)
+ continue;
+ if (loop_nest == NULL)
+ loop_nest = DDR_LOOP_NEST (ddr);
+ else
+ gcc_assert (DDR_LOOP_NEST (ddr) == NULL
+ || DDR_LOOP_NEST (ddr) == loop_nest);
+ free_dependence_relation (ddr);
+ }
+
+ if (loop_nest)
+ VEC_free (loop_p, heap, loop_nest);
+ 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++)
- {
- struct data_reference *dr = (struct data_reference *)
- VARRAY_GENERIC_PTR (datarefs, i);
- if (dr)
- {
- DR_FREE_ACCESS_FNS (dr);
- free (dr);
- }
- }
- varray_clear (datarefs);
+ for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
+ free_data_ref (dr);
+ VEC_free (data_reference_p, heap, datarefs);
}
OSDN Git Service
