/* Data references and dependences detectors.
- Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
Contributed by Sebastian Pop <pop@cri.ensmp.fr>
This file is part of GCC.
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
+#include "langhooks.h"
static struct datadep_stats
{
static tree object_analysis (tree, tree, bool, struct data_reference **,
tree *, tree *, tree *, tree *, tree *,
struct ptr_info_def **, subvar_t *);
-static struct data_reference * init_data_ref (tree, tree, tree, tree, bool,
- 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);
+ bitmap bal1, bal2;
- 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;
- *aliased = (tag_a == tag_b);
+ 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;
+ }
+ bal1 = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (bal1, DECL_UID (tag_a));
+ if (MTAG_P (tag_a) && MTAG_ALIASES (tag_a))
+ bitmap_ior_into (bal1, MTAG_ALIASES (tag_a));
+
+ bal2 = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (bal2, DECL_UID (tag_b));
+ if (MTAG_P (tag_b) && MTAG_ALIASES (tag_b))
+ bitmap_ior_into (bal2, MTAG_ALIASES (tag_b));
+ *aliased = bitmap_intersect_p (bal1, bal2);
+
+ BITMAP_FREE (bal1);
+ BITMAP_FREE (bal2);
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;
}
tree addr_a = DR_BASE_ADDRESS (dra);
tree addr_b = DR_BASE_ADDRESS (drb);
tree type_a, type_b;
+ tree decl_a, decl_b;
bool aliased;
if (!addr_a || !addr_b)
}
/* An instruction writing through a restricted pointer is "independent" of any
- instruction reading or writing through a different pointer, in the same
- block/scope. */
- else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
- || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
+ instruction reading or writing through a different restricted pointer,
+ in the same block/scope. */
+ else if (TYPE_RESTRICT (type_a)
+ && TYPE_RESTRICT (type_b)
+ && (!DR_IS_READ (drb) || !DR_IS_READ (dra))
+ && TREE_CODE (DR_BASE_ADDRESS (dra)) == SSA_NAME
+ && (decl_a = SSA_NAME_VAR (DR_BASE_ADDRESS (dra)))
+ && TREE_CODE (decl_a) == PARM_DECL
+ && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
+ && TREE_CODE (DR_BASE_ADDRESS (drb)) == SSA_NAME
+ && (decl_b = SSA_NAME_VAR (DR_BASE_ADDRESS (drb)))
+ && TREE_CODE (decl_b) == PARM_DECL
+ && TREE_CODE (DECL_CONTEXT (decl_b)) == FUNCTION_DECL
+ && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
{
*differ_p = true;
return true;
}
+
return false;
}
/* Returns true iff A divides B. */
static inline bool
-tree_fold_divides_p (tree a,
- tree b)
+tree_fold_divides_p (tree a, tree b)
{
- /* Determines whether (A == gcd (A, B)). */
- return tree_int_cst_equal (a, tree_fold_gcd (a, b));
+ gcc_assert (TREE_CODE (a) == INTEGER_CST);
+ gcc_assert (TREE_CODE (b) == INTEGER_CST);
+ return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
}
/* Returns true iff A divides B. */
/* 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");
}
+/* Dumps the affine function described by FN to the file OUTF. */
+
+static void
+dump_affine_function (FILE *outf, affine_fn fn)
+{
+ unsigned i;
+ tree coef;
+
+ print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
+ for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
+ {
+ fprintf (outf, " + ");
+ print_generic_expr (outf, coef, TDF_SLIM);
+ fprintf (outf, " * x_%u", i);
+ }
+}
+
+/* Dumps the conflict function CF to the file OUTF. */
+
+static void
+dump_conflict_function (FILE *outf, conflict_function *cf)
+{
+ unsigned i;
+
+ if (cf->n == NO_DEPENDENCE)
+ fprintf (outf, "no dependence\n");
+ else if (cf->n == NOT_KNOWN)
+ fprintf (outf, "not known\n");
+ else
+ {
+ for (i = 0; i < cf->n; i++)
+ {
+ fprintf (outf, "[");
+ dump_affine_function (outf, cf->fns[i]);
+ fprintf (outf, "]\n");
+ }
+ }
+}
+
/* Dump function for a SUBSCRIPT structure. */
void
dump_subscript (FILE *outf, struct subscript *subscript)
{
- tree chrec = SUB_CONFLICTS_IN_A (subscript);
+ conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
fprintf (outf, "\n (subscript \n");
fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
- print_generic_stmt (outf, chrec, 0);
- if (chrec == chrec_known)
- fprintf (outf, " (no dependence)\n");
- else if (chrec_contains_undetermined (chrec))
- fprintf (outf, " (don't know)\n");
- else
+ dump_conflict_function (outf, cf);
+ if (CF_NONTRIVIAL_P (cf))
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
fprintf (outf, " last_conflict: ");
print_generic_stmt (outf, last_iteration, 0);
}
- chrec = SUB_CONFLICTS_IN_B (subscript);
+ cf = SUB_CONFLICTS_IN_B (subscript);
fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
- print_generic_stmt (outf, chrec, 0);
- if (chrec == chrec_known)
- fprintf (outf, " (no dependence)\n");
- else if (chrec_contains_undetermined (chrec))
- fprintf (outf, " (don't know)\n");
- else
+ dump_conflict_function (outf, cf);
+ if (CF_NONTRIVIAL_P (cf))
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
fprintf (outf, " last_conflict: ");
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, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
+ 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
assignment. */
-struct data_reference *
-analyze_array (tree stmt, tree ref, bool is_read)
+static struct data_reference *
+init_array_ref (tree stmt, tree ref, bool is_read)
{
- struct data_reference *res;
- VEC(tree,heap) *acc_fns;
+ struct loop *loop = loop_containing_stmt (stmt);
+ VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3);
+ struct data_reference *res = XNEW (struct data_reference);;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "(analyze_array \n");
+ fprintf (dump_file, "(init_array_ref \n");
fprintf (dump_file, " (ref = ");
print_generic_stmt (dump_file, ref, 0);
fprintf (dump_file, ")\n");
}
- res = XNEW (struct data_reference);
-
DR_STMT (res) = stmt;
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);
+ DR_BASE_OBJECT (res) = analyze_array_indexes (loop, &acc_fns, ref, stmt);
DR_TYPE (res) = ARRAY_REF_TYPE;
DR_SET_ACCESS_FNS (res, acc_fns);
DR_IS_READ (res) = is_read;
return res;
}
+/* For a data reference REF contained in the statement STMT, initialize
+ a DATA_REFERENCE structure, and return it. */
+
+static struct data_reference *
+init_pointer_ref (tree stmt, tree ref, tree access_fn, bool is_read,
+ tree base_address, tree step, struct ptr_info_def *ptr_info)
+{
+ struct data_reference *res = XNEW (struct data_reference);
+ VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(init_pointer_ref \n");
+ fprintf (dump_file, " (ref = ");
+ print_generic_stmt (dump_file, ref, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ DR_STMT (res) = stmt;
+ DR_REF (res) = ref;
+ DR_BASE_OBJECT (res) = NULL_TREE;
+ DR_TYPE (res) = POINTER_REF_TYPE;
+ DR_SET_ACCESS_FNS (res, acc_fns);
+ VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
+ DR_IS_READ (res) = is_read;
+ DR_BASE_ADDRESS (res) = base_address;
+ DR_OFFSET (res) = NULL_TREE;
+ DR_INIT (res) = NULL_TREE;
+ DR_STEP (res) = step;
+ DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
+ DR_MEMTAG (res) = NULL_TREE;
+ DR_PTR_INFO (res) = ptr_info;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+
+ return res;
+}
+
/* Analyze an indirect memory reference, REF, that comes from STMT.
IS_READ is true if this is an indirect load, and false if it is
an indirect store.
if (!expr_invariant_in_loop_p (loop, init))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
}
else
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nunknown evolution of ptr.\n");
}
- return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address,
- NULL_TREE, step, NULL_TREE, NULL_TREE,
- ptr_info, POINTER_REF_TYPE);
-}
-
-/* For a data reference REF contained in the statement STMT, initialize
- a DATA_REFERENCE structure, and return it. */
-
-struct data_reference *
-init_data_ref (tree stmt,
- tree ref,
- tree base,
- tree access_fn,
- bool is_read,
- tree base_address,
- tree init_offset,
- tree step,
- tree misalign,
- tree memtag,
- struct ptr_info_def *ptr_info,
- enum data_ref_type type)
-{
- struct data_reference *res;
- VEC(tree,heap) *acc_fns;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(init_data_ref \n");
- fprintf (dump_file, " (ref = ");
- print_generic_stmt (dump_file, ref, 0);
- fprintf (dump_file, ")\n");
- }
-
- res = XNEW (struct data_reference);
-
- DR_STMT (res) = stmt;
- DR_REF (res) = ref;
- DR_BASE_OBJECT (res) = base;
- DR_TYPE (res) = type;
- acc_fns = VEC_alloc (tree, heap, 3);
- DR_SET_ACCESS_FNS (res, acc_fns);
- VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
- DR_IS_READ (res) = is_read;
- DR_BASE_ADDRESS (res) = base_address;
- DR_OFFSET (res) = init_offset;
- DR_INIT (res) = NULL_TREE;
- DR_STEP (res) = step;
- DR_OFFSET_MISALIGNMENT (res) = misalign;
- DR_MEMTAG (res) = memtag;
- DR_PTR_INFO (res) = ptr_info;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-
- return res;
+ return init_pointer_ref (stmt, ref, access_fn, is_read, base_address,
+ step, ptr_info);
}
/* Function strip_conversions
if (!(*dr))
{
if (TREE_CODE (memref) == ARRAY_REF)
- *dr = analyze_array (stmt, memref, is_read);
+ *dr = init_array_ref (stmt, memref, is_read);
else if (TREE_CODE (memref) == COMPONENT_REF)
comp_ref = memref;
else
{
if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
{
- *dr = analyze_array (stmt, TREE_OPERAND (comp_ref, 0), is_read);
+ *dr = init_array_ref (stmt, TREE_OPERAND (comp_ref, 0), is_read);
if (DR_NUM_DIMENSIONS (*dr) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
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);
Extract INVARIANT and CONSTANT parts from OFFSET.
*/
-static void
+static bool
analyze_offset (tree offset, tree *invariant, tree *constant)
{
tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
*constant = offset;
else
*invariant = offset;
- return;
+ return true;
}
op0 = TREE_OPERAND (offset, 0);
op1 = TREE_OPERAND (offset, 1);
/* Recursive call with the operands. */
- analyze_offset (op0, &invariant_0, &constant_0);
- analyze_offset (op1, &invariant_1, &constant_1);
+ if (!analyze_offset (op0, &invariant_0, &constant_0)
+ || !analyze_offset (op1, &invariant_1, &constant_1))
+ return false;
- /* Combine the results. */
+ /* Combine the results. Add negation to the subtrahend in case of
+ subtraction. */
+ if (constant_0 && constant_1)
+ return false;
*constant = constant_0 ? constant_0 : constant_1;
+ if (code == MINUS_EXPR && constant_1)
+ *constant = fold_build1 (NEGATE_EXPR, TREE_TYPE (*constant), *constant);
+
if (invariant_0 && invariant_1)
*invariant =
fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
else
- *invariant = invariant_0 ? invariant_0 : invariant_1;
+ {
+ *invariant = invariant_0 ? invariant_0 : invariant_1;
+ if (code == MINUS_EXPR && invariant_1)
+ *invariant =
+ fold_build1 (NEGATE_EXPR, TREE_TYPE (*invariant), *invariant);
+ }
+ return true;
}
+/* 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.
STRIP_NOPS (offset);
if (offset != orig_offset)
type = TREE_TYPE (orig_offset);
- analyze_offset (offset, &invariant, &constant);
+ if (!analyze_offset (offset, &invariant, &constant))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\ncreate_data_ref: failed to analyze dr's");
+ fprintf (dump_file, " offset for ");
+ print_generic_expr (dump_file, memref, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+ return NULL;
+ }
if (type && invariant)
invariant = fold_convert (type, invariant);
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);
return dr;
}
+/* Returns true if FNA == FNB. */
-/* Returns true when all the functions of a tree_vec CHREC are the
- same. */
-
-static bool
-all_chrecs_equal_p (tree chrec)
+static bool
+affine_function_equal_p (affine_fn fna, affine_fn fnb)
{
- int j;
+ unsigned i, n = VEC_length (tree, fna);
+
+ if (n != VEC_length (tree, fnb))
+ return false;
+
+ for (i = 0; i < n; i++)
+ if (!operand_equal_p (VEC_index (tree, fna, i),
+ VEC_index (tree, fnb, i), 0))
+ return false;
- 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;
- }
return true;
}
-/* Determine for each subscript in the data dependence relation DDR
- the distance. */
+/* If all the functions in CF are the same, returns one of them,
+ otherwise returns NULL. */
-static void
-compute_subscript_distance (struct data_dependence_relation *ddr)
+static affine_fn
+common_affine_function (conflict_function *cf)
{
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- {
- unsigned int i;
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree conflicts_a, conflicts_b, difference;
- struct subscript *subscript;
-
- subscript = DDR_SUBSCRIPT (ddr, i);
- conflicts_a = SUB_CONFLICTS_IN_A (subscript);
- conflicts_b = SUB_CONFLICTS_IN_B (subscript);
+ unsigned i;
+ affine_fn comm;
- if (TREE_CODE (conflicts_a) == TREE_VEC)
- {
- if (!all_chrecs_equal_p (conflicts_a))
- {
- SUB_DISTANCE (subscript) = chrec_dont_know;
- return;
- }
- else
- conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
- }
+ if (!CF_NONTRIVIAL_P (cf))
+ return NULL;
- if (TREE_CODE (conflicts_b) == TREE_VEC)
- {
- if (!all_chrecs_equal_p (conflicts_b))
- {
- SUB_DISTANCE (subscript) = chrec_dont_know;
- return;
- }
- else
- conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
- }
+ comm = cf->fns[0];
+
+ for (i = 1; i < cf->n; i++)
+ if (!affine_function_equal_p (comm, cf->fns[i]))
+ return NULL;
+
+ return comm;
+}
+
+/* Returns the base of the affine function FN. */
+
+static tree
+affine_function_base (affine_fn fn)
+{
+ return VEC_index (tree, fn, 0);
+}
+
+/* Returns true if FN is a constant. */
+
+static bool
+affine_function_constant_p (affine_fn fn)
+{
+ unsigned i;
+ tree coef;
+
+ for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
+ if (!integer_zerop (coef))
+ return false;
+
+ return true;
+}
+
+/* Returns true if FN is the zero constant function. */
+
+static bool
+affine_function_zero_p (affine_fn fn)
+{
+ return (integer_zerop (affine_function_base (fn))
+ && affine_function_constant_p (fn));
+}
+
+/* Applies operation OP on affine functions FNA and FNB, and returns the
+ result. */
+
+static affine_fn
+affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
+{
+ unsigned i, n, m;
+ affine_fn ret;
+ tree coef;
+
+ if (VEC_length (tree, fnb) > VEC_length (tree, fna))
+ {
+ n = VEC_length (tree, fna);
+ m = VEC_length (tree, fnb);
+ }
+ else
+ {
+ n = VEC_length (tree, fnb);
+ m = VEC_length (tree, fna);
+ }
+
+ ret = VEC_alloc (tree, heap, m);
+ for (i = 0; i < n; i++)
+ VEC_quick_push (tree, ret,
+ fold_build2 (op, integer_type_node,
+ VEC_index (tree, fna, i),
+ VEC_index (tree, fnb, i)));
+
+ for (; VEC_iterate (tree, fna, i, coef); i++)
+ VEC_quick_push (tree, ret,
+ fold_build2 (op, integer_type_node,
+ coef, integer_zero_node));
+ for (; VEC_iterate (tree, fnb, i, coef); i++)
+ VEC_quick_push (tree, ret,
+ fold_build2 (op, integer_type_node,
+ integer_zero_node, coef));
+
+ return ret;
+}
+
+/* Returns the sum of affine functions FNA and FNB. */
+
+static affine_fn
+affine_fn_plus (affine_fn fna, affine_fn fnb)
+{
+ return affine_fn_op (PLUS_EXPR, fna, fnb);
+}
+
+/* Returns the difference of affine functions FNA and FNB. */
+
+static affine_fn
+affine_fn_minus (affine_fn fna, affine_fn fnb)
+{
+ return affine_fn_op (MINUS_EXPR, fna, fnb);
+}
+
+/* Frees affine function FN. */
+
+static void
+affine_fn_free (affine_fn fn)
+{
+ VEC_free (tree, heap, fn);
+}
+
+/* Determine for each subscript in the data dependence relation DDR
+ the distance. */
+
+static void
+compute_subscript_distance (struct data_dependence_relation *ddr)
+{
+ conflict_function *cf_a, *cf_b;
+ affine_fn fn_a, fn_b, diff;
- difference = chrec_fold_minus
- (integer_type_node, conflicts_b, conflicts_a);
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ {
+ unsigned int i;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ struct subscript *subscript;
- if (evolution_function_is_constant_p (difference))
- SUB_DISTANCE (subscript) = difference;
+ subscript = DDR_SUBSCRIPT (ddr, i);
+ cf_a = SUB_CONFLICTS_IN_A (subscript);
+ cf_b = SUB_CONFLICTS_IN_B (subscript);
+
+ fn_a = common_affine_function (cf_a);
+ fn_b = common_affine_function (cf_b);
+ if (!fn_a || !fn_b)
+ {
+ SUB_DISTANCE (subscript) = chrec_dont_know;
+ return;
+ }
+ diff = affine_fn_minus (fn_a, fn_b);
+ if (affine_function_constant_p (diff))
+ SUB_DISTANCE (subscript) = affine_function_base (diff);
else
SUB_DISTANCE (subscript) = chrec_dont_know;
+
+ affine_fn_free (diff);
}
}
}
+/* Returns the conflict function for "unknown". */
+
+static conflict_function *
+conflict_fn_not_known (void)
+{
+ conflict_function *fn = XCNEW (conflict_function);
+ fn->n = NOT_KNOWN;
+
+ return fn;
+}
+
+/* Returns the conflict function for "independent". */
+
+static conflict_function *
+conflict_fn_no_dependence (void)
+{
+ conflict_function *fn = XCNEW (conflict_function);
+ fn->n = NO_DEPENDENCE;
+
+ return fn;
+}
+
/* Initialize a data dependence relation between data accesses A and
B. NB_LOOPS is the number of loops surrounding the references: the
size of the classic distance/direction vectors. */
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_INNER_LOOP (res) = 0;
DDR_DIR_VECTS (res) = NULL;
DDR_DIST_VECTS (res) = NULL;
struct subscript *subscript;
subscript = XNEW (struct subscript);
- SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
- SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
+ SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
+ SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
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;
}
+/* Frees memory used by the conflict function F. */
+
+static void
+free_conflict_function (conflict_function *f)
+{
+ unsigned i;
+
+ if (CF_NONTRIVIAL_P (f))
+ {
+ for (i = 0; i < f->n; i++)
+ affine_fn_free (f->fns[i]);
+ }
+ free (f);
+}
+
+/* Frees memory used by SUBSCRIPTS. */
+
+static void
+free_subscripts (VEC (subscript_p, heap) *subscripts)
+{
+ unsigned i;
+ subscript_p s;
+
+ for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
+ {
+ free_conflict_function (s->conflicting_iterations_in_a);
+ free_conflict_function (s->conflicting_iterations_in_b);
+ }
+ VEC_free (subscript_p, heap, subscripts);
+}
+
/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
description. */
}
DDR_ARE_DEPENDENT (ddr) = chrec;
- varray_clear (DDR_SUBSCRIPTS (ddr));
+ free_subscripts (DDR_SUBSCRIPTS (ddr));
}
/* The dependence relation DDR cannot be represented by a distance
return false;
}
+/* Creates a conflict function with N dimensions. The affine functions
+ in each dimension follow. */
+
+static conflict_function *
+conflict_fn (unsigned n, ...)
+{
+ unsigned i;
+ conflict_function *ret = XCNEW (conflict_function);
+ va_list ap;
+
+ gcc_assert (0 < n && n <= MAX_DIM);
+ va_start(ap, n);
+
+ ret->n = n;
+ for (i = 0; i < n; i++)
+ ret->fns[i] = va_arg (ap, affine_fn);
+ va_end(ap);
+
+ return ret;
+}
+
+/* Returns constant affine function with value CST. */
+
+static affine_fn
+affine_fn_cst (tree cst)
+{
+ affine_fn fn = VEC_alloc (tree, heap, 1);
+ VEC_quick_push (tree, fn, cst);
+ return fn;
+}
+
+/* Returns affine function with single variable, CST + COEF * x_DIM. */
+
+static affine_fn
+affine_fn_univar (tree cst, unsigned dim, tree coef)
+{
+ affine_fn fn = VEC_alloc (tree, heap, dim + 1);
+ unsigned i;
+
+ gcc_assert (dim > 0);
+ VEC_quick_push (tree, fn, cst);
+ for (i = 1; i < dim; i++)
+ VEC_quick_push (tree, fn, integer_zero_node);
+ VEC_quick_push (tree, fn, coef);
+ return fn;
+}
+
/* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
*OVERLAPS_B are initialized to the functions that describe the
relation between the elements accessed twice by CHREC_A and
static void
analyze_ziv_subscript (tree chrec_a,
tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
tree *last_conflicts)
{
tree difference;
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))
{
/* The difference is equal to zero: the accessed index
overlaps for each iteration in the loop. */
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
*last_conflicts = chrec_dont_know;
dependence_stats.num_ziv_dependent++;
}
else
{
/* The accesses do not overlap. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_ziv_independent++;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
dependence_stats.num_ziv_unimplemented++;
break;
fprintf (dump_file, ")\n");
}
-/* Get the real or estimated number of iterations for LOOPNUM, whichever is
- available. Return the number of iterations as a tree, or NULL_TREE if
- we don't know. */
+/* Sets NIT to the estimated number of executions of the statements in
+ LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
+ large as the number of iterations. If we have no reliable estimate,
+ the function returns false, otherwise returns true. */
-static tree
-get_number_of_iters_for_loop (int loopnum)
+bool
+estimated_loop_iterations (struct loop *loop, bool conservative,
+ double_int *nit)
+{
+ estimate_numbers_of_iterations_loop (loop);
+ if (conservative)
+ {
+ if (!loop->any_upper_bound)
+ return false;
+
+ *nit = loop->nb_iterations_upper_bound;
+ }
+ else
+ {
+ if (!loop->any_estimate)
+ return false;
+
+ *nit = loop->nb_iterations_estimate;
+ }
+
+ return true;
+}
+
+/* Similar to estimated_loop_iterations, but returns the estimate only
+ if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
+ on the number of iterations of LOOP could not be derived, returns -1. */
+
+HOST_WIDE_INT
+estimated_loop_iterations_int (struct loop *loop, bool conservative)
{
- tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
+ double_int nit;
+ HOST_WIDE_INT hwi_nit;
+
+ if (!estimated_loop_iterations (loop, conservative, &nit))
+ return -1;
+
+ if (!double_int_fits_in_shwi_p (nit))
+ return -1;
+ hwi_nit = double_int_to_shwi (nit);
- 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 hwi_nit < 0 ? -1 : hwi_nit;
}
+/* Similar to estimated_loop_iterations, but returns the estimate as a tree,
+ and only if it fits to the int type. If this is not the case, or the
+ estimate on the number of iterations of LOOP could not be derived, returns
+ chrec_dont_know. */
+
+static tree
+estimated_loop_iterations_tree (struct loop *loop, bool conservative)
+{
+ double_int nit;
+ tree type;
+
+ if (!estimated_loop_iterations (loop, conservative, &nit))
+ return chrec_dont_know;
+
+ type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
+ if (!double_int_fits_to_tree_p (type, nit))
+ return chrec_dont_know;
+
+ return double_int_to_tree (type, nit);
+}
+
/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
constant, and CHREC_B is an affine function. *OVERLAPS_A and
*OVERLAPS_B are initialized to the functions that describe the
static void
analyze_siv_subscript_cst_affine (tree chrec_a,
tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
tree *last_conflicts)
{
bool value0, value1, value2;
- tree difference = chrec_fold_minus
- (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
+ tree difference, tmp;
+
+ 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))
{
fprintf (dump_file, "siv test failed: chrec is not positive.\n");
dependence_stats.num_siv_unimplemented++;
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
return;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "siv test failed: chrec not positive.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
dependence_stats.num_siv_unimplemented++;
return;
if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
{
- tree numiter;
- int loopnum = CHREC_VARIABLE (chrec_b);
-
- *overlaps_a = integer_zero_node;
- *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
- fold_build1 (ABS_EXPR,
- integer_type_node,
- difference),
- CHREC_RIGHT (chrec_b));
+ HOST_WIDE_INT numiter;
+ struct loop *loop = get_chrec_loop (chrec_b);
+
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
+ fold_build1 (ABS_EXPR,
+ integer_type_node,
+ difference),
+ CHREC_RIGHT (chrec_b));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
*last_conflicts = integer_one_node;
/* Perform weak-zero siv test to see if overlap is
outside the loop bounds. */
- numiter = get_number_of_iters_for_loop (loopnum);
+ numiter = estimated_loop_iterations_int (loop, true);
- if (numiter != NULL_TREE
- && TREE_CODE (*overlaps_b) == INTEGER_CST
- && tree_int_cst_lt (numiter, *overlaps_b))
+ if (numiter >= 0
+ && compare_tree_int (tmp, numiter) > 0)
{
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ free_conflict_function (*overlaps_a);
+ free_conflict_function (*overlaps_b);
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
no overlaps. */
else
{
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
chrec_b = {10, +, -1}
In this case, chrec_a will not overlap with chrec_b. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "siv test failed: chrec not positive.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
dependence_stats.num_siv_unimplemented++;
return;
*/
if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
{
- tree numiter;
- int loopnum = CHREC_VARIABLE (chrec_b);
-
- *overlaps_a = integer_zero_node;
- *overlaps_b = fold_build2 (EXACT_DIV_EXPR,
- integer_type_node, difference,
- CHREC_RIGHT (chrec_b));
+ HOST_WIDE_INT numiter;
+ struct loop *loop = get_chrec_loop (chrec_b);
+
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ tmp = fold_build2 (EXACT_DIV_EXPR,
+ integer_type_node, difference,
+ CHREC_RIGHT (chrec_b));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
*last_conflicts = integer_one_node;
/* Perform weak-zero siv test to see if overlap is
outside the loop bounds. */
- numiter = get_number_of_iters_for_loop (loopnum);
+ numiter = estimated_loop_iterations_int (loop, true);
- if (numiter != NULL_TREE
- && TREE_CODE (*overlaps_b) == INTEGER_CST
- && tree_int_cst_lt (numiter, *overlaps_b))
+ if (numiter >= 0
+ && compare_tree_int (tmp, numiter) > 0)
{
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ free_conflict_function (*overlaps_a);
+ free_conflict_function (*overlaps_b);
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
are no overlaps. */
else
{
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
chrec_b = {4, +, 1}
In this case, chrec_a will not overlap with chrec_b. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
static void
compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
- tree *overlaps_a, tree *overlaps_b,
+ affine_fn *overlaps_a,
+ affine_fn *overlaps_b,
tree *last_conflicts, int dim)
{
if (((step_a > 0 && step_b > 0)
tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
last_conflict = tau2;
- *overlaps_a = build_polynomial_chrec
- (dim, integer_zero_node,
- build_int_cst (NULL_TREE, step_overlaps_a));
- *overlaps_b = build_polynomial_chrec
- (dim, integer_zero_node,
- build_int_cst (NULL_TREE, step_overlaps_b));
+ *overlaps_a = affine_fn_univar (integer_zero_node, dim,
+ build_int_cst (NULL_TREE,
+ step_overlaps_a));
+ *overlaps_b = affine_fn_univar (integer_zero_node, dim,
+ build_int_cst (NULL_TREE,
+ step_overlaps_b));
*last_conflicts = build_int_cst (NULL_TREE, last_conflict);
}
else
{
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
+ *overlaps_a = affine_fn_cst (integer_zero_node);
+ *overlaps_b = affine_fn_cst (integer_zero_node);
*last_conflicts = integer_zero_node;
}
}
-
/* Solves the special case of a Diophantine equation where CHREC_A is
an affine bivariate function, and CHREC_B is an affine univariate
function. For example,
static void
compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
- tree *overlaps_a, tree *overlaps_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
tree *last_conflicts)
{
bool xz_p, yz_p, xyz_p;
int step_x, step_y, step_z;
- int niter_x, niter_y, niter_z, niter;
- tree numiter_x, numiter_y, numiter_z;
- tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
- tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
- tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
+ HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
+ affine_fn overlaps_a_xz, overlaps_b_xz;
+ affine_fn overlaps_a_yz, overlaps_b_yz;
+ affine_fn overlaps_a_xyz, overlaps_b_xyz;
+ affine_fn ova1, ova2, ovb;
+ tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
step_y = int_cst_value (CHREC_RIGHT (chrec_a));
step_z = int_cst_value (CHREC_RIGHT (chrec_b));
- numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
- numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
- numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
+ niter_x = estimated_loop_iterations_int
+ (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
+ niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true);
+ niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true);
- if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
- || numiter_z == NULL_TREE)
+ if (niter_x < 0 || niter_y < 0 || niter_z < 0)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
return;
}
- niter_x = int_cst_value (numiter_x);
- niter_y = int_cst_value (numiter_y);
- niter_z = int_cst_value (numiter_z);
-
niter = MIN (niter_x, niter_z);
compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
&overlaps_a_xz,
if (xz_p || yz_p || xyz_p)
{
- *overlaps_a = make_tree_vec (2);
- TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
- TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
- *overlaps_b = integer_zero_node;
+ ova1 = affine_fn_cst (integer_zero_node);
+ ova2 = affine_fn_cst (integer_zero_node);
+ ovb = affine_fn_cst (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);
+ affine_fn t0 = ova1;
+ affine_fn t2 = ovb;
+
+ ova1 = affine_fn_plus (ova1, overlaps_a_xz);
+ ovb = affine_fn_plus (ovb, overlaps_b_xz);
+ affine_fn_free (t0);
+ affine_fn_free (t2);
*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);
+ affine_fn t0 = ova2;
+ affine_fn t2 = ovb;
+
+ ova2 = affine_fn_plus (ova2, overlaps_a_yz);
+ ovb = affine_fn_plus (ovb, overlaps_b_yz);
+ affine_fn_free (t0);
+ affine_fn_free (t2);
*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);
+ affine_fn t0 = ova1;
+ affine_fn t2 = ova2;
+ affine_fn t4 = ovb;
+
+ ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
+ ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
+ ovb = affine_fn_plus (ovb, overlaps_b_xyz);
+ affine_fn_free (t0);
+ affine_fn_free (t2);
+ affine_fn_free (t4);
*last_conflicts = last_conflicts_xyz;
}
+ *overlaps_a = conflict_fn (2, ova1, ova2);
+ *overlaps_b = conflict_fn (1, ovb);
}
else
{
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
*last_conflicts = integer_zero_node;
}
+
+ affine_fn_free (overlaps_a_xz);
+ affine_fn_free (overlaps_b_xz);
+ affine_fn_free (overlaps_a_yz);
+ affine_fn_free (overlaps_b_yz);
+ affine_fn_free (overlaps_a_xyz);
+ affine_fn_free (overlaps_b_xyz);
}
/* Determines the overlapping elements due to accesses CHREC_A and
static void
analyze_subscript_affine_affine (tree chrec_a,
tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
tree *last_conflicts)
{
unsigned nb_vars_a, nb_vars_b, dim;
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. */
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
+ /* The accessed index overlaps for each iteration in the
+ loop. */
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
*last_conflicts = chrec_dont_know;
return;
}
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);
if (nb_vars_a == 1 && nb_vars_b == 1)
{
int step_a, step_b;
- int niter, niter_a, niter_b;
- tree numiter_a, numiter_b;
-
- numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
- numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
- if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
+ HOST_WIDE_INT niter, niter_a, niter_b;
+ affine_fn ova, ovb;
+
+ niter_a = estimated_loop_iterations_int
+ (get_chrec_loop (chrec_a), true);
+ niter_b = estimated_loop_iterations_int
+ (get_chrec_loop (chrec_b), true);
+ if (niter_a < 0 || niter_b < 0)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
goto end_analyze_subs_aa;
}
- niter_a = int_cst_value (numiter_a);
- niter_b = int_cst_value (numiter_b);
niter = MIN (niter_a, niter_b);
step_a = int_cst_value (CHREC_RIGHT (chrec_a));
step_b = int_cst_value (CHREC_RIGHT (chrec_b));
compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
- overlaps_a, overlaps_b,
+ &ova, &ovb,
last_conflicts, 1);
+ *overlaps_a = conflict_fn (1, ova);
+ *overlaps_b = conflict_fn (1, ovb);
}
else if (nb_vars_a == 2 && nb_vars_b == 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: too many variables.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
}
goto end_analyze_subs_aa;
}
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 = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ goto end_analyze_subs_aa;
+ }
+
/* The classic "gcd-test". */
if (!int_divides_p (gcd_alpha_beta, gamma))
{
/* The "gcd-test" has determined that there is no integer
solution, i.e. there is no dependence. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
}
equation: chrec_a (X0) = chrec_b (Y0). */
int x0, y0;
int niter, niter_a, niter_b;
- tree numiter_a, numiter_b;
- numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
- numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
+ niter_a = estimated_loop_iterations_int
+ (get_chrec_loop (chrec_a), true);
+ niter_b = estimated_loop_iterations_int
+ (get_chrec_loop (chrec_b), true);
- if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
+ if (niter_a < 0 || niter_b < 0)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
goto end_analyze_subs_aa;
}
- niter_a = int_cst_value (numiter_a);
- niter_b = int_cst_value (numiter_b);
niter = MIN (niter_a, niter_b);
i0 = U[0][0] * gamma / gcd_alpha_beta;
FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
falls in here, but for the moment we don't look at the
upper bound of the iteration domain. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
}
loop, there is no dependence. */
if (x0 > niter || y0 > niter)
{
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
}
else
{
- *overlaps_a = build_polynomial_chrec
- (1,
- build_int_cst (NULL_TREE, x0),
- build_int_cst (NULL_TREE, i1));
- *overlaps_b = build_polynomial_chrec
- (1,
- build_int_cst (NULL_TREE, y0),
- build_int_cst (NULL_TREE, j1));
+ *overlaps_a
+ = conflict_fn (1,
+ affine_fn_univar (build_int_cst (NULL_TREE, x0),
+ 1,
+ build_int_cst (NULL_TREE, i1)));
+ *overlaps_b
+ = conflict_fn (1,
+ affine_fn_univar (build_int_cst (NULL_TREE, y0),
+ 1,
+ build_int_cst (NULL_TREE, j1)));
*last_conflicts = build_int_cst (NULL_TREE, last_conflict);
}
}
iteration domain for j is not checked. */
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
}
}
iteration domain for i is not checked. */
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
}
}
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
}
}
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (overlaps_a = ");
- print_generic_expr (dump_file, *overlaps_a, 0);
+ dump_conflict_function (dump_file, *overlaps_a);
fprintf (dump_file, ")\n (overlaps_b = ");
- print_generic_expr (dump_file, *overlaps_b, 0);
+ dump_conflict_function (dump_file, *overlaps_b);
fprintf (dump_file, ")\n");
fprintf (dump_file, ")\n");
}
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;
}
static void
analyze_siv_subscript (tree chrec_a,
tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
tree *last_conflicts)
{
dependence_stats.num_siv++;
overlaps_a, overlaps_b,
last_conflicts);
- if (*overlaps_a == chrec_dont_know
- || *overlaps_b == chrec_dont_know)
+ if (CF_NOT_KNOWN_P (*overlaps_a)
+ || CF_NOT_KNOWN_P (*overlaps_b))
dependence_stats.num_siv_unimplemented++;
- else if (*overlaps_a == chrec_known
- || *overlaps_b == chrec_known)
+ else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+ || CF_NO_DEPENDENCE_P (*overlaps_b))
dependence_stats.num_siv_independent++;
else
dependence_stats.num_siv_dependent++;
Compute it properly. */
*last_conflicts = chrec_dont_know;
- if (*overlaps_a == chrec_dont_know
- || *overlaps_b == chrec_dont_know)
+ if (CF_NOT_KNOWN_P (*overlaps_a)
+ || CF_NOT_KNOWN_P (*overlaps_b))
dependence_stats.num_siv_unimplemented++;
- else if (*overlaps_a == chrec_known
- || *overlaps_b == chrec_known)
+ else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+ || CF_NO_DEPENDENCE_P (*overlaps_b))
dependence_stats.num_siv_independent++;
else
dependence_stats.num_siv_dependent++;
siv_subscript_dontknow:;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "siv test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
dependence_stats.num_siv_unimplemented++;
}
fprintf (dump_file, ")\n");
}
-/* Return true when the property can be computed. RES should contain
- true when calling the first time this function, then it is set to
- false when one of the evolution steps of an affine CHREC does not
- divide the constant CST. */
+/* Returns false if we can prove that the greatest common divisor of the steps
+ of CHREC does not divide CST, false otherwise. */
static bool
-chrec_steps_divide_constant_p (tree chrec,
- tree cst,
- bool *res)
+gcd_of_steps_may_divide_p (tree chrec, tree cst)
{
- switch (TREE_CODE (chrec))
- {
- case POLYNOMIAL_CHREC:
- if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
- {
- if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
- /* Keep RES to true, and iterate on other dimensions. */
- return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
-
- *res = false;
- return true;
- }
- else
- /* When the step is a parameter the result is undetermined. */
- return false;
+ HOST_WIDE_INT cd = 0, val;
+ tree step;
- default:
- /* On the initial condition, return true. */
- return true;
+ if (!host_integerp (cst, 0))
+ return true;
+ val = tree_low_cst (cst, 0);
+
+ while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
+ {
+ step = CHREC_RIGHT (chrec);
+ if (!host_integerp (step, 0))
+ return true;
+ cd = gcd (cd, tree_low_cst (step, 0));
+ chrec = CHREC_LEFT (chrec);
}
+
+ return val % cd == 0;
}
/* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
static void
analyze_miv_subscript (tree chrec_a,
tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
tree *last_conflicts)
{
/* FIXME: This is a MIV subscript, not yet handled.
variables. In the MIV case we have to solve a Diophantine
equation with 2*n variables (if the subscript uses n IVs).
*/
- bool divide_p = true;
tree difference;
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. */
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *last_conflicts = estimated_loop_iterations_tree
+ (get_chrec_loop (chrec_a), true);
dependence_stats.num_miv_dependent++;
}
else if (evolution_function_is_constant_p (difference)
/* For the moment, the following is verified:
evolution_function_is_affine_multivariate_p (chrec_a) */
- && chrec_steps_divide_constant_p (chrec_a, difference, ÷_p)
- && !divide_p)
+ && !gcd_of_steps_may_divide_p (chrec_a, difference))
{
/* testsuite/.../ssa-chrec-33.c
{{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
- The difference is 1, and the evolution steps are equal to 2,
- consequently there are no overlapping elements. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
+ The difference is 1, and all the evolution steps are multiples
+ of 2, consequently there are no overlapping elements. */
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
dependence_stats.num_miv_independent++;
}
analyze_subscript_affine_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b, last_conflicts);
- if (*overlaps_a == chrec_dont_know
- || *overlaps_b == chrec_dont_know)
+ if (CF_NOT_KNOWN_P (*overlaps_a)
+ || CF_NOT_KNOWN_P (*overlaps_b))
dependence_stats.num_miv_unimplemented++;
- else if (*overlaps_a == chrec_known
- || *overlaps_b == chrec_known)
+ else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+ || CF_NO_DEPENDENCE_P (*overlaps_b))
dependence_stats.num_miv_independent++;
else
dependence_stats.num_miv_dependent++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
dependence_stats.num_miv_unimplemented++;
}
static void
analyze_overlapping_iterations (tree chrec_a,
tree chrec_b,
- tree *overlap_iterations_a,
- tree *overlap_iterations_b,
+ conflict_function **overlap_iterations_a,
+ conflict_function **overlap_iterations_b,
tree *last_conflicts)
{
dependence_stats.num_subscript_tests++;
{
dependence_stats.num_subscript_undetermined++;
- *overlap_iterations_a = chrec_dont_know;
- *overlap_iterations_b = chrec_dont_know;
+ *overlap_iterations_a = conflict_fn_not_known ();
+ *overlap_iterations_b = conflict_fn_not_known ();
}
/* If they are the same chrec, and are affine, they overlap
&& evolution_function_is_affine_multivariate_p (chrec_a))
{
dependence_stats.num_same_subscript_function++;
- *overlap_iterations_a = integer_zero_node;
- *overlap_iterations_b = integer_zero_node;
+ *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
*last_conflicts = chrec_dont_know;
}
|| !evolution_function_is_affine_multivariate_p (chrec_b)))
{
dependence_stats.num_subscript_undetermined++;
- *overlap_iterations_a = chrec_dont_know;
- *overlap_iterations_b = chrec_dont_know;
+ *overlap_iterations_a = conflict_fn_not_known ();
+ *overlap_iterations_b = conflict_fn_not_known ();
}
else if (ziv_subscript_p (chrec_a, chrec_b))
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (overlap_iterations_a = ");
- print_generic_expr (dump_file, *overlap_iterations_a, 0);
+ dump_conflict_function (dump_file, *overlap_iterations_a);
fprintf (dump_file, ")\n (overlap_iterations_b = ");
- print_generic_expr (dump_file, *overlap_iterations_b, 0);
+ dump_conflict_function (dump_file, *overlap_iterations_b);
fprintf (dump_file, ")\n");
fprintf (dump_file, ")\n");
}
}
-\f
+/* Helper function for uniquely inserting distance vectors. */
-/* This section contains the affine functions dependences detector. */
+static void
+save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
+{
+ unsigned i;
+ lambda_vector v;
-/* Compute the classic per loop distance vector.
+ 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;
- 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. */
+ VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
+}
-static bool
-build_classic_dist_vector (struct data_dependence_relation *ddr,
- int first_loop_depth)
+/* 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 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;
}
- }
-
- /* Save the distance vector if we initialized one. */
- if (init_b)
- {
- lambda_vector save_v;
-
- /* Verify a basic constraint: classic distance vectors should always
- be lexicographically positive. */
- if (!lambda_vector_lexico_pos (dist_v, DDR_SIZE_VECT (ddr)))
+ else
{
- 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;
+ /* 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_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);
-
- /* There is nothing more to do when there are no outer loops. */
- if (DDR_SIZE_VECT (ddr) == 1)
- goto classic_dist_done;
}
- /* 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;
+/* Return true when the DDR contains two data references that have the
+ same access functions. */
- gcc_assert (lca_depth < nb_loops);
+static bool
+same_access_functions (struct data_dependence_relation *ddr)
+{
+ unsigned i;
- /* 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:
+ 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;
- | loop_1
- | loop_2
- | A[10]
- | endloop_2
- | endloop_1
+ return true;
+}
- 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));
+/* Return true when the DDR contains only constant access functions. */
- 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);
- }
+static bool
+constant_access_functions (struct data_dependence_relation *ddr)
+{
+ unsigned i;
- lca = lca->outer;
- lca_depth = lca->depth - first_loop_depth;
- }
- }
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
+ || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
+ return false;
- classic_dist_done:;
+ return true;
+}
- if (dump_file && (dump_flags & TDF_DETAILS))
+
+/* Helper function for the case where DDR_A and DDR_B are the same
+ multivariate access function. */
+
+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;
+ int v1, v2, cd;
+
+ /* Polynomials with more than 2 variables are not handled yet. */
+ if (TREE_CODE (c_0) != INTEGER_CST)
{
- fprintf (dump_file, "(build_classic_dist_vector\n");
+ DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+ return;
+ }
- for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+ 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));
+
+ /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ v1 = int_cst_value (CHREC_RIGHT (c_1));
+ v2 = int_cst_value (CHREC_RIGHT (c_2));
+ cd = gcd (v1, v2);
+ v1 /= cd;
+ v2 /= cd;
+
+ if (v2 < 0)
+ {
+ v2 = -v2;
+ v1 = -v1;
+ }
+
+ dist_v[x_1] = v2;
+ dist_v[x_2] = -v1;
+ save_dist_v (ddr, dist_v);
+
+ add_outer_distances (ddr, dist_v, x_1);
+}
+
+/* Helper function for the case where DDR_A and DDR_B are the same
+ access functions. */
+
+static void
+add_other_self_distances (struct data_dependence_relation *ddr)
+{
+ lambda_vector dist_v;
+ unsigned i;
+ int index_carry = DDR_NB_LOOPS (ddr);
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ tree access_fun = DR_ACCESS_FN (DDR_A (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);
+}
+
+static void
+insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
+{
+ lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+ dist_v[DDR_INNER_LOOP (ddr)] = 1;
+ save_dist_v (ddr, dist_v);
}
-/* Compute the classic per loop direction vector.
+/* Adds a unit distance vector to DDR when there is a 0 overlap. This
+ is the case for example when access functions are the same and
+ equal to a constant, as in:
+
+ | loop_1
+ | A[3] = ...
+ | ... = A[3]
+ | endloop_1
+
+ in which case the distance vectors are (0) and (1). */
+
+static void
+add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
+{
+ unsigned i, j;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ subscript_p sub = DDR_SUBSCRIPT (ddr, i);
+ conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
+ conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
+
+ for (j = 0; j < ca->n; j++)
+ if (affine_function_zero_p (ca->fns[j]))
+ {
+ insert_innermost_unit_dist_vector (ddr);
+ return;
+ }
+
+ for (j = 0; j < cb->n; j++)
+ if (affine_function_zero_p (cb->fns[j]))
+ {
+ insert_innermost_unit_dist_vector (ddr);
+ return;
+ }
+ }
+}
- 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 (constant_access_functions (ddr))
+ add_distance_for_zero_overlaps (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 (DDR_NB_LOOPS (ddr) > 1)
+ add_other_self_distances (ddr);
- 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);
-
+ conflict_function *overlaps_a, *overlaps_b;
+
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))
+
+ if (CF_NOT_KNOWN_P (overlaps_a)
+ || CF_NOT_KNOWN_P (overlaps_b))
{
finalize_ddr_dependent (ddr, chrec_dont_know);
dependence_stats.num_dependence_undetermined++;
- goto subs_test_end;
+ free_conflict_function (overlaps_a);
+ free_conflict_function (overlaps_b);
+ return false;
}
-
- else if (overlaps_a == chrec_known
- || overlaps_b == chrec_known)
+
+ else if (CF_NO_DEPENDENCE_P (overlaps_a)
+ || CF_NO_DEPENDENCE_P (overlaps_b))
{
finalize_ddr_dependent (ddr, chrec_known);
dependence_stats.num_dependence_independent++;
- goto subs_test_end;
+ free_conflict_function (overlaps_a);
+ free_conflict_function (overlaps_b);
+ 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");
access_functions_are_affine_or_constant_p (struct data_reference *a)
{
unsigned int i;
- VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
+ VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
tree t;
-
- for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
+
+ for (i = 0; VEC_iterate (tree, fns, i, t); i++)
if (!evolution_function_is_constant_p (t)
&& !evolution_function_is_affine_multivariate_p (t))
return false;
return true;
}
+/* Initializes an equation for an OMEGA problem using the information
+ contained in the ACCESS_FUN. Returns true when the operation
+ succeeded.
+
+ PB is the omega constraint system.
+ EQ is the number of the equation to be initialized.
+ OFFSET is used for shifting the variables names in the constraints:
+ a constrain is composed of 2 * the number of variables surrounding
+ dependence accesses. OFFSET is set either to 0 for the first n variables,
+ then it is set to n.
+ ACCESS_FUN is expected to be an affine chrec. */
+
+static bool
+init_omega_eq_with_af (omega_pb pb, unsigned eq,
+ unsigned int offset, tree access_fun,
+ struct data_dependence_relation *ddr)
+{
+ switch (TREE_CODE (access_fun))
+ {
+ case POLYNOMIAL_CHREC:
+ {
+ tree left = CHREC_LEFT (access_fun);
+ tree right = CHREC_RIGHT (access_fun);
+ int var = CHREC_VARIABLE (access_fun);
+ unsigned var_idx;
+
+ if (TREE_CODE (right) != INTEGER_CST)
+ return false;
+
+ var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
+ pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
+
+ /* Compute the innermost loop index. */
+ DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
+
+ if (offset == 0)
+ pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
+ += int_cst_value (right);
+
+ switch (TREE_CODE (left))
+ {
+ case POLYNOMIAL_CHREC:
+ return init_omega_eq_with_af (pb, eq, offset, left, ddr);
+
+ case INTEGER_CST:
+ pb->eqs[eq].coef[0] += int_cst_value (left);
+ return true;
+
+ default:
+ return false;
+ }
+ }
+
+ case INTEGER_CST:
+ pb->eqs[eq].coef[0] += int_cst_value (access_fun);
+ return true;
+
+ default:
+ return false;
+ }
+}
+
+/* As explained in the comments preceding init_omega_for_ddr, we have
+ to set up a system for each loop level, setting outer loops
+ variation to zero, and current loop variation to positive or zero.
+ Save each lexico positive distance vector. */
+
+static void
+omega_extract_distance_vectors (omega_pb pb,
+ struct data_dependence_relation *ddr)
+{
+ int eq, geq;
+ unsigned i, j;
+ struct loop *loopi, *loopj;
+ enum omega_result res;
+
+ /* Set a new problem for each loop in the nest. The basis is the
+ problem that we have initialized until now. On top of this we
+ add new constraints. */
+ for (i = 0; i <= DDR_INNER_LOOP (ddr)
+ && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
+ {
+ int dist = 0;
+ omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
+ DDR_NB_LOOPS (ddr));
+
+ omega_copy_problem (copy, pb);
+
+ /* For all the outer loops "loop_j", add "dj = 0". */
+ for (j = 0;
+ j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
+ {
+ eq = omega_add_zero_eq (copy, omega_black);
+ copy->eqs[eq].coef[j + 1] = 1;
+ }
+
+ /* For "loop_i", add "0 <= di". */
+ geq = omega_add_zero_geq (copy, omega_black);
+ copy->geqs[geq].coef[i + 1] = 1;
+
+ /* Reduce the constraint system, and test that the current
+ problem is feasible. */
+ res = omega_simplify_problem (copy);
+ if (res == omega_false
+ || res == omega_unknown
+ || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
+ goto next_problem;
+
+ for (eq = 0; eq < copy->num_subs; eq++)
+ if (copy->subs[eq].key == (int) i + 1)
+ {
+ dist = copy->subs[eq].coef[0];
+ goto found_dist;
+ }
+
+ if (dist == 0)
+ {
+ /* Reinitialize problem... */
+ omega_copy_problem (copy, pb);
+ for (j = 0;
+ j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
+ {
+ eq = omega_add_zero_eq (copy, omega_black);
+ copy->eqs[eq].coef[j + 1] = 1;
+ }
+
+ /* ..., but this time "di = 1". */
+ eq = omega_add_zero_eq (copy, omega_black);
+ copy->eqs[eq].coef[i + 1] = 1;
+ copy->eqs[eq].coef[0] = -1;
+
+ res = omega_simplify_problem (copy);
+ if (res == omega_false
+ || res == omega_unknown
+ || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
+ goto next_problem;
+
+ for (eq = 0; eq < copy->num_subs; eq++)
+ if (copy->subs[eq].key == (int) i + 1)
+ {
+ dist = copy->subs[eq].coef[0];
+ goto found_dist;
+ }
+ }
+
+ found_dist:;
+ /* Save the lexicographically positive distance vector. */
+ if (dist >= 0)
+ {
+ lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+ dist_v[i] = dist;
+
+ for (eq = 0; eq < copy->num_subs; eq++)
+ if (copy->subs[eq].key > 0)
+ {
+ dist = copy->subs[eq].coef[0];
+ dist_v[copy->subs[eq].key - 1] = dist;
+ }
+
+ for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
+ dir_v[j] = dir_from_dist (dist_v[j]);
+
+ save_dist_v (ddr, dist_v);
+ save_dir_v (ddr, dir_v);
+ }
+
+ next_problem:;
+ omega_free_problem (copy);
+ }
+}
+
+/* This is called for each subscript of a tuple of data references:
+ insert an equality for representing the conflicts. */
+
+static bool
+omega_setup_subscript (tree access_fun_a, tree access_fun_b,
+ struct data_dependence_relation *ddr,
+ omega_pb pb, bool *maybe_dependent)
+{
+ int eq;
+ tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE);
+ tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE);
+ tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b);
+
+ /* When the fun_a - fun_b is not constant, the dependence is not
+ captured by the classic distance vector representation. */
+ if (TREE_CODE (difference) != INTEGER_CST)
+ return false;
+
+ /* ZIV test. */
+ if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
+ {
+ /* There is no dependence. */
+ *maybe_dependent = false;
+ return true;
+ }
+
+ fun_b = chrec_fold_multiply (integer_type_node, fun_b,
+ integer_minus_one_node);
+
+ eq = omega_add_zero_eq (pb, omega_black);
+ if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
+ || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
+ /* There is probably a dependence, but the system of
+ constraints cannot be built: answer "don't know". */
+ return false;
+
+ /* GCD test. */
+ if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
+ && !int_divides_p (lambda_vector_gcd
+ ((lambda_vector) &(pb->eqs[eq].coef[1]),
+ 2 * DDR_NB_LOOPS (ddr)),
+ pb->eqs[eq].coef[0]))
+ {
+ /* There is no dependence. */
+ *maybe_dependent = false;
+ return true;
+ }
+
+ return true;
+}
+
+/* Helper function, same as init_omega_for_ddr but specialized for
+ data references A and B. */
+
+static bool
+init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
+ struct data_dependence_relation *ddr,
+ omega_pb pb, bool *maybe_dependent)
+{
+ unsigned i;
+ int ineq;
+ struct loop *loopi;
+ unsigned nb_loops = DDR_NB_LOOPS (ddr);
+
+ /* Insert an equality per subscript. */
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
+ ddr, pb, maybe_dependent))
+ return false;
+ else if (*maybe_dependent == false)
+ {
+ /* There is no dependence. */
+ DDR_ARE_DEPENDENT (ddr) = chrec_known;
+ return true;
+ }
+ }
+
+ /* Insert inequalities: constraints corresponding to the iteration
+ domain, i.e. the loops surrounding the references "loop_x" and
+ the distance variables "dx". The layout of the OMEGA
+ representation is as follows:
+ - coef[0] is the constant
+ - coef[1..nb_loops] are the protected variables that will not be
+ removed by the solver: the "dx"
+ - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
+ */
+ for (i = 0; i <= DDR_INNER_LOOP (ddr)
+ && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
+ {
+ HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, true);
+
+ /* 0 <= loop_x */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
+
+ /* 0 <= loop_x + dx */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
+ pb->geqs[ineq].coef[i + 1] = 1;
+
+ if (nbi != -1)
+ {
+ /* loop_x <= nb_iters */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
+ pb->geqs[ineq].coef[0] = nbi;
+
+ /* loop_x + dx <= nb_iters */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
+ pb->geqs[ineq].coef[i + 1] = -1;
+ pb->geqs[ineq].coef[0] = nbi;
+
+ /* A step "dx" bigger than nb_iters is not feasible, so
+ add "0 <= nb_iters + dx", */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + 1] = 1;
+ pb->geqs[ineq].coef[0] = nbi;
+ /* and "dx <= nb_iters". */
+ ineq = omega_add_zero_geq (pb, omega_black);
+ pb->geqs[ineq].coef[i + 1] = -1;
+ pb->geqs[ineq].coef[0] = nbi;
+ }
+ }
+
+ omega_extract_distance_vectors (pb, ddr);
+
+ return true;
+}
+
+/* Sets up the Omega dependence problem for the data dependence
+ relation DDR. Returns false when the constraint system cannot be
+ built, ie. when the test answers "don't know". Returns true
+ otherwise, and when independence has been proved (using one of the
+ trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
+ set MAYBE_DEPENDENT to true.
+
+ Example: for setting up the dependence system corresponding to the
+ conflicting accesses
+
+ | loop_i
+ | loop_j
+ | A[i, i+1] = ...
+ | ... A[2*j, 2*(i + j)]
+ | endloop_j
+ | endloop_i
+
+ the following constraints come from the iteration domain:
+
+ 0 <= i <= Ni
+ 0 <= i + di <= Ni
+ 0 <= j <= Nj
+ 0 <= j + dj <= Nj
+
+ where di, dj are the distance variables. The constraints
+ representing the conflicting elements are:
+
+ i = 2 * (j + dj)
+ i + 1 = 2 * (i + di + j + dj)
+
+ For asking that the resulting distance vector (di, dj) be
+ lexicographically positive, we insert the constraint "di >= 0". If
+ "di = 0" in the solution, we fix that component to zero, and we
+ look at the inner loops: we set a new problem where all the outer
+ loop distances are zero, and fix this inner component to be
+ positive. When one of the components is positive, we save that
+ distance, and set a new problem where the distance on this loop is
+ zero, searching for other distances in the inner loops. Here is
+ the classic example that illustrates that we have to set for each
+ inner loop a new problem:
+
+ | loop_1
+ | loop_2
+ | A[10]
+ | endloop_2
+ | endloop_1
+
+ we have to save two distances (1, 0) and (0, 1).
+
+ Given two array references, refA and refB, we have to set the
+ dependence problem twice, refA vs. refB and refB vs. refA, and we
+ cannot do a single test, as refB might occur before refA in the
+ inner loops, and the contrary when considering outer loops: ex.
+
+ | loop_0
+ | loop_1
+ | loop_2
+ | T[{1,+,1}_2][{1,+,1}_1] // refA
+ | T[{2,+,1}_2][{0,+,1}_1] // refB
+ | endloop_2
+ | endloop_1
+ | endloop_0
+
+ refB touches the elements in T before refA, and thus for the same
+ loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
+ but for successive loop_0 iterations, we have (1, -1, 1)
+
+ The Omega solver expects the distance variables ("di" in the
+ previous example) to come first in the constraint system (as
+ variables to be protected, or "safe" variables), the constraint
+ system is built using the following layout:
+
+ "cst | distance vars | index vars".
+*/
+
+static bool
+init_omega_for_ddr (struct data_dependence_relation *ddr,
+ bool *maybe_dependent)
+{
+ omega_pb pb;
+ bool res = false;
+
+ *maybe_dependent = true;
+
+ if (same_access_functions (ddr))
+ {
+ unsigned j;
+ lambda_vector dir_v;
+
+ /* Save the 0 vector. */
+ save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+ dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
+ dir_v[j] = dir_equal;
+ save_dir_v (ddr, dir_v);
+
+ /* Save the dependences carried by outer loops. */
+ pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
+ res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
+ maybe_dependent);
+ omega_free_problem (pb);
+ return res;
+ }
+
+ /* Omega expects the protected variables (those that have to be kept
+ after elimination) to appear first in the constraint system.
+ These variables are the distance variables. In the following
+ initialization we declare NB_LOOPS safe variables, and the total
+ number of variables for the constraint system is 2*NB_LOOPS. */
+ pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
+ res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
+ maybe_dependent);
+ omega_free_problem (pb);
+
+ /* Stop computation if not decidable, or no dependence. */
+ if (res == false || *maybe_dependent == false)
+ return res;
+
+ pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
+ res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
+ maybe_dependent);
+ omega_free_problem (pb);
+
+ return res;
+}
+
+/* Return true when DDR contains the same information as that stored
+ in DIR_VECTS and in DIST_VECTS, return false otherwise. */
+
+static bool
+ddr_consistent_p (FILE *file,
+ struct data_dependence_relation *ddr,
+ VEC (lambda_vector, heap) *dist_vects,
+ VEC (lambda_vector, heap) *dir_vects)
+{
+ unsigned int i, j;
+
+ /* If dump_file is set, output there. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ file = dump_file;
+
+ if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
+ {
+ lambda_vector b_dist_v;
+ fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
+ VEC_length (lambda_vector, dist_vects),
+ DDR_NUM_DIST_VECTS (ddr));
+
+ fprintf (file, "Banerjee dist vectors:\n");
+ for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
+ print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
+
+ fprintf (file, "Omega dist vectors:\n");
+ for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+ print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
+
+ fprintf (file, "data dependence relation:\n");
+ dump_data_dependence_relation (file, ddr);
+
+ fprintf (file, ")\n");
+ return false;
+ }
+
+ if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
+ {
+ fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
+ VEC_length (lambda_vector, dir_vects),
+ DDR_NUM_DIR_VECTS (ddr));
+ return false;
+ }
+
+ for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+ {
+ lambda_vector a_dist_v;
+ lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
+
+ /* Distance vectors are not ordered in the same way in the DDR
+ and in the DIST_VECTS: search for a matching vector. */
+ for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
+ if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
+ break;
+
+ if (j == VEC_length (lambda_vector, dist_vects))
+ {
+ fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
+ print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
+ fprintf (file, "not found in Omega dist vectors:\n");
+ print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
+ fprintf (file, "data dependence relation:\n");
+ dump_data_dependence_relation (file, ddr);
+ fprintf (file, ")\n");
+ }
+ }
+
+ for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
+ {
+ lambda_vector a_dir_v;
+ lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
+
+ /* Direction vectors are not ordered in the same way in the DDR
+ and in the DIR_VECTS: search for a matching vector. */
+ for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
+ if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
+ break;
+
+ if (j == VEC_length (lambda_vector, dist_vects))
+ {
+ fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
+ print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
+ fprintf (file, "not found in Omega dir vectors:\n");
+ print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
+ fprintf (file, "data dependence relation:\n");
+ dump_data_dependence_relation (file, ddr);
+ fprintf (file, ")\n");
+ }
+ }
+
+ return true;
+}
+
/* This computes the affine dependence relation between A and B.
CHREC_KNOWN is used for representing the independence between two
accesses, while CHREC_DONT_KNOW is used for representing the unknown
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);
-
+ {
+ if (flag_check_data_deps)
+ {
+ /* Compute the dependences using the first algorithm. */
+ subscript_dependence_tester (ddr);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\n\nBanerjee Analyzer\n");
+ dump_data_dependence_relation (dump_file, ddr);
+ }
+
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ {
+ bool maybe_dependent;
+ VEC (lambda_vector, heap) *dir_vects, *dist_vects;
+
+ /* Save the result of the first DD analyzer. */
+ dist_vects = DDR_DIST_VECTS (ddr);
+ dir_vects = DDR_DIR_VECTS (ddr);
+
+ /* Reset the information. */
+ DDR_DIST_VECTS (ddr) = NULL;
+ DDR_DIR_VECTS (ddr) = NULL;
+
+ /* Compute the same information using Omega. */
+ if (!init_omega_for_ddr (ddr, &maybe_dependent))
+ goto csys_dont_know;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Omega Analyzer\n");
+ dump_data_dependence_relation (dump_file, ddr);
+ }
+
+ /* Check that we get the same information. */
+ if (maybe_dependent)
+ gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
+ dir_vects));
+ }
+ }
+ else
+ 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
"don't know". */
else
{
+ csys_dont_know:;
dependence_stats.num_dependence_undetermined++;
if (dump_file && (dump_flags & TDF_DETAILS))
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;
+ SUB_CONFLICTS_IN_A (subscript)
+ = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ SUB_CONFLICTS_IN_B (subscript)
+ = conflict_fn (1, affine_fn_cst (integer_zero_node));
SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
}
/* 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));
+ save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+ save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (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 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. */
- compute_subscript_distance (ddr);
+static void
+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)
+{
+ struct data_dependence_relation *ddr;
+ struct data_reference *a, *b;
+ unsigned int i, j;
+
+ 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);
+ }
+
+ if (compute_self_and_rr)
+ for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
+ {
+ ddr = initialize_data_dependence_relation (a, a, loop_nest);
+ VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+ compute_self_dependence (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. */
+/* Stores the locations of memory references in STMT to REFERENCES. Returns
+ true if STMT clobbers memory, false otherwise. */
-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)
+bool
+get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
{
- unsigned int i, j, N;
+ bool clobbers_memory = false;
+ data_ref_loc *ref;
+ tree *op0, *op1, 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;
+ }
- N = VARRAY_ACTIVE_SIZE (datarefs);
+ 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;
+ }
+ }
- /* Note that we specifically skip i == j because it's a self dependence, and
- use compute_self_dependence below. */
+ if (call)
+ {
+ unsigned i, n = call_expr_nargs (call);
- for (i = 0; i < N; i++)
- for (j = i + 1; j < N; j++)
- {
- struct data_reference *a, *b;
- struct data_dependence_relation *ddr;
+ for (i = 0; i < n; i++)
+ {
+ op0 = &CALL_EXPR_ARG (call, i);
- 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 = true;
+ }
+ }
+ }
- if (DR_IS_READ (a) && DR_IS_READ (b)
- && !compute_self_and_read_read_dependences)
- continue;
+ return clobbers_memory;
+}
- 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);
- }
+/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
+ reference, returns false, otherwise returns true. */
- if (!compute_self_and_read_read_dependences)
- return;
+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;
- /* Compute self dependence relation of each dataref to itself. */
- for (i = 0; i < N; i++)
+ 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))
{
}
/* Entry point (for testing only). Analyze all the data references
- and the dependence relations.
+ and the dependence relations in LOOP.
The data references are computed first.
recompute the same information. The implementation of this KB is
transparent to the optimizer, and thus the KB can be changed with a
more efficient implementation, or the KB could be disabled. */
-#if 0
static void
-analyze_all_data_dependences (struct loops *loops)
+analyze_all_data_dependences (struct loop *loop)
{
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,
- &datarefs, &dependence_relations);
+ compute_data_dependences_for_loop (loop, false, &datarefs,
+ &dependence_relations);
if (dump_file)
{
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++;
free_dependence_relations (dependence_relations);
free_data_refs (datarefs);
}
-#endif
+
+/* Computes all the data dependences and check that the results of
+ several analyzers are the same. */
+
+void
+tree_check_data_deps (void)
+{
+ loop_iterator li;
+ struct loop *loop_nest;
+
+ FOR_EACH_LOOP (li, loop_nest, 0)
+ analyze_all_data_dependences (loop_nest);
+}
/* Free the memory used by a data dependence relation DDR. */
return;
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
- varray_clear (DDR_SUBSCRIPTS (ddr));
+ free_subscripts (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; 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);
+ }
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
- free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
- varray_clear (dependence_relations);
+ 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
