/* Data references and dependences detectors.
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
- Contributed by Sebastian Pop <s.pop@laposte.net>
+ Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+ Contributed by Sebastian Pop <pop@cri.ensmp.fr>
This file is part of GCC.
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
+static struct datadep_stats
+{
+ int num_dependence_tests;
+ int num_dependence_dependent;
+ int num_dependence_independent;
+ int num_dependence_undetermined;
+
+ int num_subscript_tests;
+ int num_subscript_undetermined;
+ int num_same_subscript_function;
+
+ int num_ziv;
+ int num_ziv_independent;
+ int num_ziv_dependent;
+ int num_ziv_unimplemented;
+
+ int num_siv;
+ int num_siv_independent;
+ int num_siv_dependent;
+ int num_siv_unimplemented;
+
+ int num_miv;
+ int num_miv_independent;
+ int num_miv_dependent;
+ int num_miv_unimplemented;
+} dependence_stats;
+
static tree object_analysis (tree, tree, bool, struct data_reference **,
tree *, tree *, tree *, tree *, tree *,
struct ptr_info_def **, subvar_t *);
tree, tree, tree, tree, tree,
struct ptr_info_def *,
enum data_ref_type);
+static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
+ struct data_reference *,
+ struct data_reference *);
/* Determine if PTR and DECL may alias, the result is put in ALIASED.
- Return FALSE if there is no type memory tag for PTR.
-*/
+ Return FALSE if there is no symbol memory tag for PTR. */
+
static bool
ptr_decl_may_alias_p (tree ptr, tree decl,
struct data_reference *ptr_dr,
gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
- tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
+ tag = get_var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
if (!tag)
tag = DR_MEMTAG (ptr_dr);
if (!tag)
/* Determine if two pointers may alias, the result is put in ALIASED.
- Return FALSE if there is no type memory tag for one of the pointers.
-*/
+ Return FALSE if there is no symbol memory tag for one of the pointers. */
+
static bool
ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b,
struct data_reference *dra,
{
tree tag_a, tag_b;
- tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->type_mem_tag;
+ tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->symbol_mem_tag;
if (!tag_a)
tag_a = DR_MEMTAG (dra);
if (!tag_a)
return false;
- tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->type_mem_tag;
+ tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->symbol_mem_tag;
if (!tag_b)
tag_b = DR_MEMTAG (drb);
if (!tag_b)
/* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
- Return FALSE if there is no type memory tag for one of the symbols.
-*/
+ Return FALSE if there is no symbol memory tag for one of the symbols. */
+
static bool
may_alias_p (tree base_a, tree base_b,
struct data_reference *dra,
only try to prove that the bases are surely different
*/
-
static bool
base_addr_differ_p (struct data_reference *dra,
struct data_reference *drb,
type_b = TREE_TYPE (addr_b);
gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
-
+
/* 1. if (both DRA and DRB are represented as arrays)
compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
return base_object_differ_p (dra, drb, differ_p);
-
/* 2. else if (both DRA and DRB are represented as pointers)
try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
/* If base addresses are the same, we check the offsets, since the access of
/* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
PLUS_EXPR. */
- if ((offset_a == offset_b)
+ if (offset_a == offset_b
|| (TREE_CODE (offset_a) == MULT_EXPR
&& TREE_CODE (offset_b) == MULT_EXPR
&& TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
return false;
}
-
/* Returns true iff A divides B. */
static inline bool
-tree_fold_divides_p (tree type,
- tree a,
+tree_fold_divides_p (tree a,
tree b)
{
/* Determines whether (A == gcd (A, B)). */
- return integer_zerop
- (fold_build2 (MINUS_EXPR, type, a, tree_fold_gcd (a, b)));
-}
-
-/* Compute the greatest common denominator of two numbers using
- Euclid's algorithm. */
-
-static int
-gcd (int a, int b)
-{
-
- int x, y, z;
-
- x = abs (a);
- y = abs (b);
-
- while (x>0)
- {
- z = y % x;
- y = x;
- x = z;
- }
-
- return (y);
+ return tree_int_cst_equal (a, tree_fold_gcd (a, b));
}
/* 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. */
print_generic_stmt (outf, DR_STMT (dr), 0);
fprintf (outf, " ref: ");
print_generic_stmt (outf, DR_REF (dr), 0);
- fprintf (outf, " base_name: ");
+ fprintf (outf, " base_object: ");
print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
fprintf (outf, " )\n");
}
+/* Print the classic direction vector DIRV to OUTF. */
+
+void
+print_direction_vector (FILE *outf,
+ lambda_vector dirv,
+ int length)
+{
+ int eq;
+
+ for (eq = 0; eq < length; eq++)
+ {
+ enum data_dependence_direction dir = dirv[eq];
+
+ switch (dir)
+ {
+ case dir_positive:
+ fprintf (outf, " +");
+ break;
+ case dir_negative:
+ fprintf (outf, " -");
+ break;
+ case dir_equal:
+ fprintf (outf, " =");
+ break;
+ case dir_positive_or_equal:
+ fprintf (outf, " +=");
+ break;
+ case dir_positive_or_negative:
+ fprintf (outf, " +-");
+ break;
+ case dir_negative_or_equal:
+ fprintf (outf, " -=");
+ break;
+ case dir_star:
+ fprintf (outf, " *");
+ break;
+ default:
+ fprintf (outf, "indep");
+ break;
+ }
+ }
+ 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++)
{
fprintf (outf, " access_fn_A: ");
print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
}
- if (DDR_DIST_VECT (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_vect: ");
- print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
+ fprintf (outf, " distance_vector: ");
+ print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
+ DDR_NB_LOOPS (ddr));
}
- if (DDR_DIR_VECT (ddr))
+
+ for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
{
- fprintf (outf, " direction_vect: ");
- print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
+ fprintf (outf, " direction_vector: ");
+ print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
+ DDR_NB_LOOPS (ddr));
}
}
fprintf (outf, ")\n");
}
-
-
/* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
void
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;
+ unsigned int i, j;
+ struct data_dependence_relation *ddr;
+ lambda_vector v;
+
+ 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 (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))
- {
- fprintf (file, "DISTANCE_V (");
- print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
- fprintf (file, ")\n");
- fprintf (file, "DIRECTION_V (");
- print_lambda_vector (file, DDR_DIR_VECT (ddr), 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");
}
&& TREE_CODE (step) == INTEGER_CST)
{
tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step);
- tree sign = fold_build2 (GT_EXPR, boolean_type_node, i_plus_s, init);
+ 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,
/* 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]". The function returns the base name:
- "A". */
+ 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)
+ tree ref, tree stmt,
+ bool estimate_only)
{
tree opnd0, opnd1;
tree access_fn;
-
+
opnd0 = TREE_OPERAND (ref, 0);
opnd1 = TREE_OPERAND (ref, 1);
-
+
/* The detection of the evolution function for this data access is
postponed until the dependence test. This lazy strategy avoids
the computation of access functions that are of no interest for
the optimizers. */
- access_fn = instantiate_parameters
+ access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, opnd1));
- if (chrec_contains_undetermined (loop->estimated_nb_iterations))
+ if (estimate_only
+ && chrec_contains_undetermined (loop->estimated_nb_iterations))
estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
-
- VEC_safe_push (tree, heap, *access_fns, access_fn);
+
+ if (!estimate_only)
+ 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);
-
+ return analyze_array_indexes (loop, access_fns, opnd0, stmt, estimate_only);
+
/* 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
print_generic_stmt (dump_file, ref, 0);
fprintf (dump_file, ")\n");
}
-
- res = xmalloc (sizeof (struct data_reference));
-
+
+ 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);
+ DR_BASE_OBJECT (res) = analyze_array_indexes
+ (loop_containing_stmt (stmt), &acc_fns, ref, stmt, false);
DR_TYPE (res) = ARRAY_REF_TYPE;
DR_SET_ACCESS_FNS (res, acc_fns);
DR_IS_READ (res) = is_read;
DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
DR_MEMTAG (res) = NULL_TREE;
DR_PTR_INFO (res) = NULL;
-
+
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.
Return a new data reference structure representing the indirect_ref, or
NULL if we cannot describe the access function. */
-
+
static struct data_reference *
-analyze_indirect_ref (tree stmt, tree ref, bool is_read)
+analyze_indirect_ref (tree stmt, tree ref, bool is_read)
{
struct loop *loop = loop_containing_stmt (stmt);
tree ptr_ref = TREE_OPERAND (ref, 0);
if (TREE_CODE (ptr_ref) == SSA_NAME)
ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
- STRIP_NOPS (init);
+ STRIP_NOPS (init);
if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
{
if (dump_file && (dump_flags & TDF_DETAILS))
print_generic_stmt (dump_file, ref, 0);
fprintf (dump_file, ")\n");
}
-
- res = xmalloc (sizeof (struct data_reference));
-
+
+ res = XNEW (struct data_reference);
+
DR_STMT (res) = stmt;
DR_REF (res) = ref;
DR_BASE_OBJECT (res) = base;
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;
}
-\f
-
/* Function strip_conversions
Strip conversions that don't narrow the mode. */
return false;
init = initial_condition_in_loop_num (access_fn, loop->num);
- if (init == expr && !expr_invariant_in_loop_p (loop, init))
+ if (!expr_invariant_in_loop_p (loop, init))
/* Not enough information: may be not loop invariant.
E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
initial_condition is D, but it depends on i - loop's induction
struct loop *loop = loop_containing_stmt (stmt);
struct data_reference *ptr_dr = NULL;
tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
+ tree comp_ref = NULL_TREE;
*ptr_info = NULL;
if (handled_component_p (memref))
{
/* 1.1 build data-reference structure for MEMREF. */
- /* TODO: handle COMPONENT_REFs. */
if (!(*dr))
{
if (TREE_CODE (memref) == ARRAY_REF)
*dr = analyze_array (stmt, memref, is_read);
- else
+ else if (TREE_CODE (memref) == COMPONENT_REF)
+ comp_ref = memref;
+ else
{
- /* FORNOW. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\ndata-ref of unsupported type ");
/* Part 1: Case 2. Declarations. */
if (DECL_P (memref))
{
- /* We expect to get a decl only if we already have a DR. */
+ /* We expect to get a decl only if we already have a DR, or with
+ COMPONENT_REFs of type 'a[i].b'. */
if (!(*dr))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
{
- fprintf (dump_file, "\nunhandled decl ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
+ *dr = analyze_array (stmt, TREE_OPERAND (comp_ref, 0), is_read);
+ if (DR_NUM_DIMENSIONS (*dr) != 1)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\n multidimensional component ref ");
+ print_generic_expr (dump_file, comp_ref, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+ return NULL_TREE;
+ }
+ }
+ else
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\nunhandled decl ");
+ print_generic_expr (dump_file, memref, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+ return NULL_TREE;
}
- return NULL_TREE;
}
/* TODO: if during the analysis of INDIRECT_REF we get to an object, put
switch (TREE_CODE (base_address))
{
case SSA_NAME:
- *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
+ *memtag = get_var_ann (SSA_NAME_VAR (base_address))->symbol_mem_tag;
if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
*memtag = get_var_ann (
- SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
+ SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->symbol_mem_tag;
break;
case ADDR_EXPR:
*memtag = TREE_OPERAND (base_address, 0);
return NULL_TREE;
}
+ if (comp_ref)
+ DR_REF (*dr) = comp_ref;
+
if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
*subvars = get_subvars_for_var (*memtag);
*constant = constant_0 ? constant_0 : constant_1;
if (invariant_0 && invariant_1)
*invariant =
- fold (build (code, TREE_TYPE (invariant_0), invariant_0, invariant_1));
+ fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
else
*invariant = invariant_0 ? invariant_0 : invariant_1;
}
tree type_size, init_cond;
struct ptr_info_def *ptr_info;
subvar_t subvars = NULL;
- tree aligned_to;
+ tree aligned_to, type = NULL_TREE, orig_offset;
if (!memref)
return NULL;
type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
+ /* Extract CONSTANT and INVARIANT from OFFSET. */
+ /* Remove cast from OFFSET and restore it for INVARIANT part. */
+ orig_offset = offset;
+ STRIP_NOPS (offset);
+ if (offset != orig_offset)
+ type = TREE_TYPE (orig_offset);
+ analyze_offset (offset, &invariant, &constant);
+ if (type && invariant)
+ invariant = fold_convert (type, invariant);
+
+ /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
+ of DR. */
+ if (constant)
+ {
+ DR_INIT (dr) = fold_convert (ssizetype, constant);
+ init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
+ constant, type_size);
+ }
+ else
+ DR_INIT (dr) = init_cond = ssize_int (0);;
+
+ if (invariant)
+ DR_OFFSET (dr) = invariant;
+ else
+ DR_OFFSET (dr) = ssize_int (0);
+
/* Change the access function for INIDIRECT_REFs, according to
DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
an expression that can contain loop invariant expressions and constants.
The evolution part of the access function is STEP calculated in
object_analysis divided by the size of data type.
*/
- if (!DR_BASE_OBJECT (dr))
+ if (!DR_BASE_OBJECT (dr)
+ || (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1))
{
tree access_fn;
tree new_step;
- /* Extract CONSTANT and INVARIANT from OFFSET, and put them in DR_INIT and
- DR_OFFSET fields of DR. */
- analyze_offset (offset, &invariant, &constant);
- if (constant)
- {
- DR_INIT (dr) = fold_convert (ssizetype, constant);
- init_cond = fold (build (TRUNC_DIV_EXPR, TREE_TYPE (constant),
- constant, type_size));
- }
- else
- DR_INIT (dr) = init_cond = ssize_int (0);;
-
- if (invariant)
- DR_OFFSET (dr) = invariant;
- else
- DR_OFFSET (dr) = ssize_int (0);
-
/* Update access function. */
access_fn = DR_ACCESS_FN (dr, 0);
new_step = size_binop (TRUNC_DIV_EXPR,
/* Determine for each subscript in the data dependence relation DDR
the distance. */
-void
+static void
compute_subscript_distance (struct data_dependence_relation *ddr)
{
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
}
}
-/* Initialize a ddr. */
+/* 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. */
-struct data_dependence_relation *
+static struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
- struct data_reference *b)
+ struct data_reference *b,
+ VEC (loop_p, heap) *loop_nest)
{
struct data_dependence_relation *res;
- bool differ_p;
- unsigned int i;
+ bool differ_p, known_dependence;
+ unsigned int i;
- res = xmalloc (sizeof (struct data_dependence_relation));
+ res = XNEW (struct data_dependence_relation);
DDR_A (res) = a;
DDR_B (res) = b;
return res;
}
- /* Compare the bases of the data-refs. */
- if (!base_addr_differ_p (a, b, &differ_p))
+ if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
+ known_dependence = base_addr_differ_p (a, b, &differ_p);
+ else
+ known_dependence = base_object_differ_p (a, b, &differ_p);
+
+ if (!known_dependence)
{
/* Can't determine whether the data-refs access the same memory
region. */
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
return res;
}
+
if (differ_p)
{
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) = 0;
- DDR_DIST_VECT (res) = NULL;
- DDR_DIR_VECT (res) = NULL;
-
+ DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
+ DDR_LOOP_NEST (res) = loop_nest;
+ DDR_DIR_VECTS (res) = NULL;
+ DDR_DIST_VECTS (res) = NULL;
+
for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
{
struct subscript *subscript;
- subscript = xmalloc (sizeof (struct subscript));
+ subscript = XNEW (struct subscript);
SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
SUB_DISTANCE (subscript) = chrec_dont_know;
- VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
+ VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
}
-
+
return res;
}
}
DDR_ARE_DEPENDENT (ddr) = chrec;
- varray_clear (DDR_SUBSCRIPTS (ddr));
+ VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
}
/* The dependence relation DDR cannot be represented by a distance
tree *last_conflicts)
{
tree difference;
+ dependence_stats.num_ziv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_ziv_subscript \n");
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
*last_conflicts = chrec_dont_know;
+ dependence_stats.num_ziv_dependent++;
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
+ dependence_stats.num_ziv_independent++;
}
break;
default:
/* We're not sure whether the indexes overlap. For the moment,
conservatively answer "don't know". */
+ 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;
*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. */
+
+static tree
+get_number_of_iters_for_loop (int loopnum)
+{
+ tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
+
+ if (TREE_CODE (numiter) != INTEGER_CST)
+ numiter = current_loops->parray[loopnum]->estimated_nb_iterations;
+ if (chrec_contains_undetermined (numiter))
+ return NULL_TREE;
+ return numiter;
+}
+
/* 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
if (!chrec_is_positive (initial_condition (difference), &value0))
{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ 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;
*last_conflicts = chrec_dont_know;
{
if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
{
+ 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;
*last_conflicts = chrec_dont_know;
+ dependence_stats.num_siv_unimplemented++;
return;
}
else
chrec_b = {10, +, 1}
*/
- if (tree_fold_divides_p
- (integer_type_node, CHREC_RIGHT (chrec_b), difference))
+ 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,
difference),
CHREC_RIGHT (chrec_b));
*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);
+
+ if (numiter != NULL_TREE
+ && TREE_CODE (*overlaps_b) == INTEGER_CST
+ && tree_int_cst_lt (numiter, *overlaps_b))
+ {
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
+ return;
+ }
+ dependence_stats.num_siv_dependent++;
return;
}
- /* When the step does not divides the difference, there are
+ /* When the step does not divide the difference, there are
no overlaps. */
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
return;
}
}
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
return;
}
}
{
if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
{
+ 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;
*last_conflicts = chrec_dont_know;
+ dependence_stats.num_siv_unimplemented++;
return;
}
else
chrec_a = 3
chrec_b = {10, +, -1}
*/
- if (tree_fold_divides_p
- (integer_type_node, CHREC_RIGHT (chrec_b), difference))
+ 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
- (build (EXACT_DIV_EXPR, integer_type_node, difference,
- CHREC_RIGHT (chrec_b)));
+ *overlaps_b = fold_build2 (EXACT_DIV_EXPR,
+ integer_type_node, difference,
+ CHREC_RIGHT (chrec_b));
*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);
+
+ if (numiter != NULL_TREE
+ && TREE_CODE (*overlaps_b) == INTEGER_CST
+ && tree_int_cst_lt (numiter, *overlaps_b))
+ {
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
+ return;
+ }
+ dependence_stats.num_siv_dependent++;
return;
}
- /* When the step does not divides the difference, there
+ /* When the step does not divide the difference, there
are no overlaps. */
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
return;
}
}
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
return;
}
}
step_y = int_cst_value (CHREC_RIGHT (chrec_a));
step_z = int_cst_value (CHREC_RIGHT (chrec_b));
- numiter_x = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
- numiter_y = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- numiter_z = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
-
- if (TREE_CODE (numiter_x) != INTEGER_CST)
- numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_y) != INTEGER_CST)
- numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_z) != INTEGER_CST)
- numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
- ->estimated_nb_iterations;
-
- if (chrec_contains_undetermined (numiter_x)
- || chrec_contains_undetermined (numiter_y)
- || chrec_contains_undetermined (numiter_z)
- || TREE_CODE (numiter_x) != INTEGER_CST
- || TREE_CODE (numiter_y) != INTEGER_CST
- || TREE_CODE (numiter_z) != INTEGER_CST)
+ 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));
+
+ if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
+ || numiter_z == NULL_TREE)
{
+ 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;
*last_conflicts = chrec_dont_know;
}
/* Determines the overlapping elements due to accesses CHREC_A and
- CHREC_B, that are affine functions. This is a part of the
- subscript analyzer. */
+ CHREC_B, that are affine functions. This function cannot handle
+ symbolic evolution functions, ie. when initial conditions are
+ parameters, because it uses lambda matrices of integers. */
static void
analyze_subscript_affine_affine (tree chrec_a,
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))
+ {
+ /* 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;
+ *last_conflicts = chrec_dont_know;
+ return;
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_subscript_affine_affine \n");
int niter, niter_a, niter_b;
tree numiter_a, numiter_b;
- numiter_a = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- numiter_b = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
-
- if (TREE_CODE (numiter_a) != INTEGER_CST)
- numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_b) != INTEGER_CST)
- numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
- ->estimated_nb_iterations;
- if (chrec_contains_undetermined (numiter_a)
- || chrec_contains_undetermined (numiter_b)
- || TREE_CODE (numiter_a) != INTEGER_CST
- || TREE_CODE (numiter_b) != INTEGER_CST)
+ 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)
{
+ 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;
*last_conflicts = chrec_dont_know;
- return;
+ goto end_analyze_subs_aa;
}
niter_a = int_cst_value (numiter_a);
else
{
+ 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;
*last_conflicts = chrec_dont_know;
}
- return;
+ goto end_analyze_subs_aa;
}
/* U.A = S */
}
gcd_alpha_beta = S[0][0];
+ /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
+ but that is a quite strange case. Instead of ICEing, answer
+ don't know. */
+ if (gcd_alpha_beta == 0)
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ goto end_analyze_subs_aa;
+ }
+
/* The classic "gcd-test". */
if (!int_divides_p (gcd_alpha_beta, gamma))
{
int niter, niter_a, niter_b;
tree numiter_a, numiter_b;
- numiter_a = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- numiter_b = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
-
- if (TREE_CODE (numiter_a) != INTEGER_CST)
- numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_b) != INTEGER_CST)
- numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
- ->estimated_nb_iterations;
- if (chrec_contains_undetermined (numiter_a)
- || chrec_contains_undetermined (numiter_b)
- || TREE_CODE (numiter_a) != INTEGER_CST
- || TREE_CODE (numiter_b) != INTEGER_CST)
+ 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)
{
+ 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;
*last_conflicts = chrec_dont_know;
- return;
+ goto end_analyze_subs_aa;
}
niter_a = int_cst_value (numiter_a);
tau1 = (x0 - i0)/i1;
last_conflict = tau2 - tau1;
- *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));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+ /* If the overlap occurs outside of the bounds of the
+ loop, there is no dependence. */
+ if (x0 > niter || y0 > niter)
+ {
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *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));
+ *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+ }
}
else
{
/* FIXME: For the moment, the upper bound of the
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;
*last_conflicts = chrec_dont_know;
{
/* FIXME: For the moment, the upper bound of the
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;
*last_conflicts = chrec_dont_know;
}
else
{
+ 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;
*last_conflicts = chrec_dont_know;
else
{
+ 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;
*last_conflicts = chrec_dont_know;
}
-
+end_analyze_subs_aa:
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (overlaps_a = ");
fprintf (dump_file, ")\n (overlaps_b = ");
print_generic_expr (dump_file, *overlaps_b, 0);
fprintf (dump_file, ")\n");
+ fprintf (dump_file, ")\n");
}
-
+}
+
+/* Returns true when analyze_subscript_affine_affine can be used for
+ determining the dependence relation between chrec_a and chrec_b,
+ that contain symbols. This function modifies chrec_a and chrec_b
+ such that the analysis result is the same, and such that they don't
+ contain symbols, and then can safely be passed to the analyzer.
+
+ Example: The analysis of the following tuples of evolutions produce
+ the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
+ vs. {0, +, 1}_1
+
+ {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
+ {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
+*/
+
+static bool
+can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
+{
+ tree diff;
+
+ 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));
+ if (!evolution_function_is_constant_p (diff))
+ return false;
+
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
+ fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
+
+ *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
+ diff, CHREC_RIGHT (*chrec_a));
+ *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
+ integer_zero_node,
+ CHREC_RIGHT (*chrec_b));
+ return true;
}
/* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
tree *overlaps_b,
tree *last_conflicts)
{
+ dependence_stats.num_siv++;
+
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_siv_subscript \n");
else if (evolution_function_is_affine_p (chrec_a)
&& evolution_function_is_affine_p (chrec_b))
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b, last_conflicts);
+ {
+ if (!chrec_contains_symbols (chrec_a)
+ && !chrec_contains_symbols (chrec_b))
+ {
+ 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)
+ dependence_stats.num_siv_unimplemented++;
+ else if (*overlaps_a == chrec_known
+ || *overlaps_b == chrec_known)
+ dependence_stats.num_siv_independent++;
+ else
+ dependence_stats.num_siv_dependent++;
+ }
+ else if (can_use_analyze_subscript_affine_affine (&chrec_a,
+ &chrec_b))
+ {
+ analyze_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b,
+ last_conflicts);
+ /* FIXME: The number of iterations is a symbolic expression.
+ Compute it properly. */
+ *last_conflicts = chrec_dont_know;
+
+ if (*overlaps_a == chrec_dont_know
+ || *overlaps_b == chrec_dont_know)
+ dependence_stats.num_siv_unimplemented++;
+ else if (*overlaps_a == chrec_known
+ || *overlaps_b == chrec_known)
+ dependence_stats.num_siv_independent++;
+ else
+ dependence_stats.num_siv_dependent++;
+ }
+ else
+ goto siv_subscript_dontknow;
+ }
+
else
{
+ 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;
*last_conflicts = chrec_dont_know;
+ dependence_stats.num_siv_unimplemented++;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
-/* Return true when the evolution steps of an affine CHREC divide the
- constant CST. */
+/* 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. */
static bool
chrec_steps_divide_constant_p (tree chrec,
- tree cst)
+ tree cst,
+ bool *res)
{
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
- return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
- && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
-
- default:
- /* On the initial condition, return true. */
- return true;
+ 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;
+
+ default:
+ /* On the initial condition, return true. */
+ return true;
}
}
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");
in the same order. */
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
- *last_conflicts = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
+ *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
+ 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))
+ && chrec_steps_divide_constant_p (chrec_a, difference, ÷_p)
+ && !divide_p)
{
/* 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;
*last_conflicts = integer_zero_node;
+ dependence_stats.num_miv_independent++;
}
else if (evolution_function_is_affine_multivariate_p (chrec_a)
- && evolution_function_is_affine_multivariate_p (chrec_b))
+ && !chrec_contains_symbols (chrec_a)
+ && evolution_function_is_affine_multivariate_p (chrec_b)
+ && !chrec_contains_symbols (chrec_b))
{
/* testsuite/.../ssa-chrec-35.c
{0, +, 1}_2 vs. {0, +, 1}_3
*/
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)
+ dependence_stats.num_miv_unimplemented++;
+ else if (*overlaps_a == chrec_known
+ || *overlaps_b == chrec_known)
+ dependence_stats.num_miv_independent++;
+ else
+ dependence_stats.num_miv_dependent++;
}
else
{
/* When the analysis is too difficult, answer "don't know". */
+ 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;
*last_conflicts = chrec_dont_know;
+ dependence_stats.num_miv_unimplemented++;
}
if (dump_file && (dump_flags & TDF_DETAILS))
tree *overlap_iterations_b,
tree *last_conflicts)
{
+ dependence_stats.num_subscript_tests++;
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(analyze_overlapping_iterations \n");
fprintf (dump_file, " (chrec_a = ");
print_generic_expr (dump_file, chrec_a, 0);
- fprintf (dump_file, ")\n chrec_b = ");
+ fprintf (dump_file, ")\n (chrec_b = ");
print_generic_expr (dump_file, chrec_b, 0);
fprintf (dump_file, ")\n");
}
-
+
if (chrec_a == NULL_TREE
|| chrec_b == NULL_TREE
|| chrec_contains_undetermined (chrec_a)
- || chrec_contains_undetermined (chrec_b)
- || chrec_contains_symbols (chrec_a)
- || chrec_contains_symbols (chrec_b))
+ || chrec_contains_undetermined (chrec_b))
{
+ dependence_stats.num_subscript_undetermined++;
+
*overlap_iterations_a = chrec_dont_know;
*overlap_iterations_b = chrec_dont_know;
}
-
+
+ /* If they are the same chrec, and are affine, they overlap
+ on every iteration. */
+ else if (eq_evolutions_p (chrec_a, chrec_b)
+ && evolution_function_is_affine_multivariate_p (chrec_a))
+ {
+ dependence_stats.num_same_subscript_function++;
+ *overlap_iterations_a = integer_zero_node;
+ *overlap_iterations_b = integer_zero_node;
+ *last_conflicts = chrec_dont_know;
+ }
+
+ /* If they aren't the same, and aren't affine, we can't do anything
+ yet. */
+ else if ((chrec_contains_symbols (chrec_a)
+ || chrec_contains_symbols (chrec_b))
+ && (!evolution_function_is_affine_multivariate_p (chrec_a)
+ || !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;
+ }
+
else if (ziv_subscript_p (chrec_a, chrec_b))
analyze_ziv_subscript (chrec_a, chrec_b,
overlap_iterations_a, overlap_iterations_b,
fprintf (dump_file, ")\n (overlap_iterations_b = ");
print_generic_expr (dump_file, *overlap_iterations_b, 0);
fprintf (dump_file, ")\n");
+ fprintf (dump_file, ")\n");
}
}
-\f
+/* Helper function for uniquely inserting distance vectors. */
+
+static void
+save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
+{
+ unsigned i;
+ lambda_vector v;
-/* This section contains the affine functions dependences detector. */
+ for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
+ if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
+ return;
-/* Computes the conflicting iterations, and initialize DDR. */
+ VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
+}
+
+/* Helper function for uniquely inserting direction vectors. */
static void
-subscript_dependence_tester (struct data_dependence_relation *ddr)
+save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
{
- 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++)
+ unsigned i;
+ lambda_vector v;
+
+ 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)
{
- tree overlaps_a, overlaps_b;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
-
- analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
- DR_ACCESS_FN (drb, i),
- &overlaps_a, &overlaps_b,
- &last_conflicts);
-
- if (chrec_contains_undetermined (overlaps_a)
- || chrec_contains_undetermined (overlaps_b))
- {
- finalize_ddr_dependent (ddr, chrec_dont_know);
- break;
- }
-
- else if (overlaps_a == chrec_known
- || overlaps_b == chrec_known)
- {
- finalize_ddr_dependent (ddr, chrec_known);
- break;
- }
-
- else
- {
- SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
- SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
- SUB_LAST_CONFLICT (subscript) = last_conflicts;
- }
+ 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);
}
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
}
-/* Compute the classic per loop distance vector.
-
- DDR is the data dependence relation to build a vector from.
- NB_LOOPS is the total number of loops we are considering.
- FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
- loop nest.
- Return FALSE if the dependence relation is outside of the loop nest
- starting at FIRST_LOOP_DEPTH.
- Return TRUE otherwise. */
+/* Return false when fail to represent the data dependence as a
+ distance vector. INIT_B is set to true when a component has been
+ added to the distance vector DIST_V. INDEX_CARRY is then set to
+ the index in DIST_V that carries the dependence. */
static bool
-build_classic_dist_vector (struct data_dependence_relation *ddr,
- int nb_loops, int first_loop_depth)
+build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
+ struct data_reference *ddr_a,
+ struct data_reference *ddr_b,
+ lambda_vector dist_v, bool *init_b,
+ int *index_carry)
{
unsigned i;
- lambda_vector dist_v, init_v;
-
- dist_v = lambda_vector_new (nb_loops);
- init_v = lambda_vector_new (nb_loops);
- lambda_vector_clear (dist_v, nb_loops);
- lambda_vector_clear (init_v, nb_loops);
-
- if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return true;
-
+ lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
tree access_fn_a, access_fn_b;
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;
+ dist_v[index] = dist;
+ init_v[index] = 1;
+ *init_b = true;
+ }
+ else
+ {
+ /* This can be for example an affine vs. constant dependence
+ (T[i] vs. T[3]) that is not an affine dependence and is
+ not representable as a distance vector. */
+ non_affine_dependence_relation (ddr);
+ return false;
}
}
-
- /* 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;
- lca_depth -= first_loop_depth;
- gcc_assert (lca_depth >= 0);
- gcc_assert (lca_depth < nb_loops);
-
- /* For each outer loop where init_v is not set, the accesses are
- in dependence of distance 1 in the loop. */
- if (lca != loop_a
- && lca != loop_b
- && init_v[lca_depth] == 0)
- dist_v[lca_depth] = 1;
-
- lca = lca->outer;
-
- if (lca)
- {
- lca_depth = lca->depth - first_loop_depth;
- while (lca->depth != 0)
- {
- /* If we're considering just a sub-nest, then don't record
- any information on the outer loops. */
- if (lca_depth < 0)
- break;
- gcc_assert (lca_depth < nb_loops);
+ return true;
+}
+
+/* Return true when the DDR contains two data references that have the
+ same access functions. */
+
+static bool
+same_access_functions (struct data_dependence_relation *ddr)
+{
+ unsigned i;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ tree access_fun_a = DR_ACCESS_FN (DDR_A (ddr), i);
+ tree access_fun_b = DR_ACCESS_FN (DDR_B (ddr), i);
+ tree difference = chrec_fold_minus (integer_type_node, access_fun_a,
+ access_fun_b);
+ if (TREE_CODE (difference) != INTEGER_CST
+ || !integer_zerop (difference))
+ return false;
+ }
- if (init_v[lca_depth] == 0)
- dist_v[lca_depth] = 1;
- lca = lca->outer;
- lca_depth = lca->depth - first_loop_depth;
-
- }
- }
- }
-
- DDR_DIST_VECT (ddr) = dist_v;
- DDR_SIZE_VECT (ddr) = nb_loops;
return true;
}
-/* Compute the classic per loop direction vector.
+/* Helper function for the case where DDR_A and DDR_B are the same
+ multivariate access function. */
- 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. */
+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;
-static bool
-build_classic_dir_vector (struct data_dependence_relation *ddr,
- int nb_loops, int first_loop_depth)
+ /* Polynomials with more than 2 variables are not handled yet. */
+ if (TREE_CODE (c_0) != INTEGER_CST)
+ {
+ DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+ return;
+ }
+
+ 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));
+ dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
+ dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
+ save_dist_v (ddr, dist_v);
+
+ 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;
- lambda_vector dir_v, init_v;
-
- dir_v = lambda_vector_new (nb_loops);
- init_v = lambda_vector_new (nb_loops);
- lambda_vector_clear (dir_v, nb_loops);
- lambda_vector_clear (init_v, nb_loops);
-
- if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return true;
-
+ int index_carry = DDR_NB_LOOPS (ddr);
+
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
- tree access_fn_a, access_fn_b;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
+ tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
{
- non_affine_dependence_relation (ddr);
- return true;
+ 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)));
}
+ }
- access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
- access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
- if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
- && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
- {
- int dist, loop_nb, loop_depth;
- enum data_dependence_direction dir = dir_star;
- int loop_nb_a = CHREC_VARIABLE (access_fn_a);
- int loop_nb_b = CHREC_VARIABLE (access_fn_b);
- struct loop *loop_a = current_loops->parray[loop_nb_a];
- struct loop *loop_b = current_loops->parray[loop_nb_b];
-
- /* If the loop for either variable is at a lower depth than
- the first_loop's depth, then we can't possibly have a
- dependency at this level of the loop. */
-
- if (loop_a->depth < first_loop_depth
- || loop_b->depth < first_loop_depth)
- return false;
-
- if (loop_nb_a != loop_nb_b
- && !flow_loop_nested_p (loop_a, loop_b)
- && !flow_loop_nested_p (loop_b, loop_a))
- {
- /* Example: when there are two consecutive loops,
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ add_outer_distances (ddr, dist_v, index_carry);
+}
- | loop_1
- | A[{0, +, 1}_1]
- | endloop_1
- | loop_2
- | A[{0, +, 1}_2]
- | endloop_2
+/* 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. */
- the dependence relation cannot be captured by the
- distance abstraction. */
- non_affine_dependence_relation (ddr);
- return true;
- }
+static bool
+build_classic_dist_vector (struct data_dependence_relation *ddr)
+{
+ bool init_b = false;
+ int index_carry = DDR_NB_LOOPS (ddr);
+ lambda_vector dist_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 (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
+ return true;
- /* 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 (same_access_functions (ddr))
+ {
+ /* 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)))
+ if (DDR_NB_LOOPS (ddr) > 1)
+ add_other_self_distances (ddr);
+
+ return true;
+ }
+
+ 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;
+
+ /* 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)
{
- non_affine_dependence_relation (ddr);
- return true;
+ 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);
- dist = int_cst_value (SUB_DISTANCE (subscript));
-
- 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)
+ if (DDR_NB_LOOPS (ddr) > 1)
{
- finalize_ddr_dependent (ddr, chrec_known);
- return true;
+ lambda_vector opposite_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),
+ opposite_v, &init_b, &index_carry);
+
+ 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;
}
}
-
- /* 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;
-
- gcc_assert (lca_depth >= 0);
- gcc_assert (lca_depth < nb_loops);
-
- /* For each outer loop where init_v is not set, the accesses are
- in dependence of distance 1 in the loop. */
- if (lca != loop_a
- && lca != loop_b
- && init_v[lca_depth] == 0)
- dir_v[lca_depth] = dir_positive;
-
- lca = lca->outer;
- if (lca)
- {
- lca_depth = lca->depth - first_loop_depth;
- while (lca->depth != 0)
- {
- /* If we're considering just a sub-nest, then don't record
- any information on the outer loops. */
- if (lca_depth < 0)
- break;
+ 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.
- gcc_assert (lca_depth < nb_loops);
+ | 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))
+ {
+ unsigned i;
+
+ 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");
+ }
+
+ return true;
+}
+
+/* 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. */
+
+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;
+}
+
+/* Compute the classic per loop direction vector. DDR is the data
+ dependence relation to build a vector from. */
+
+static void
+build_classic_dir_vector (struct data_dependence_relation *ddr)
+{
+ unsigned i, j;
+ lambda_vector dist_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));
+
+ for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
+ dir_v[j] = dir_from_dist (dist_v[j]);
+
+ save_dir_v (ddr, dir_v);
+ }
+}
+
+/* Helper function. Returns true when there is a dependence between
+ data references DRA and DRB. */
+
+static bool
+subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
+ struct data_reference *dra,
+ struct data_reference *drb)
+{
+ unsigned int i;
+ tree last_conflicts;
+ struct subscript *subscript;
+
+ for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
+ i++)
+ {
+ tree 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))
+ {
+ finalize_ddr_dependent (ddr, chrec_dont_know);
+ dependence_stats.num_dependence_undetermined++;
+ return false;
+ }
+
+ else if (overlaps_a == chrec_known
+ || overlaps_b == chrec_known)
+ {
+ finalize_ddr_dependent (ddr, chrec_known);
+ dependence_stats.num_dependence_independent++;
+ return false;
+ }
+
+ else
+ {
+ SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
+ SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
+ SUB_LAST_CONFLICT (subscript) = last_conflicts;
+ }
+ }
- if (init_v[lca_depth] == 0)
- dir_v[lca_depth] = dir_positive;
- lca = lca->outer;
- lca_depth = lca->depth - first_loop_depth;
-
- }
- }
- }
-
- DDR_DIR_VECT (ddr) = dir_v;
- DDR_SIZE_VECT (ddr) = nb_loops;
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++;
+
+ compute_subscript_distance (ddr);
+ if (build_classic_dist_vector (ddr))
+ build_classic_dir_vector (ddr);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
/* Returns true when all the access functions of A are affine or
constant. */
relation the first time we detect a CHREC_KNOWN element for a given
subscript. */
-void
+static void
compute_affine_dependence (struct data_dependence_relation *ddr)
{
struct data_reference *dra = DDR_A (ddr);
print_generic_expr (dump_file, DR_STMT (drb), 0);
fprintf (dump_file, ")\n");
}
-
+
/* Analyze only when the dependence relation is not yet known. */
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
+ dependence_stats.num_dependence_tests++;
+
if (access_functions_are_affine_or_constant_p (dra)
&& access_functions_are_affine_or_constant_p (drb))
subscript_dependence_tester (ddr);
the dependence is considered too difficult to determine, answer
"don't know". */
else
- finalize_ddr_dependent (ddr, chrec_dont_know);
+ {
+ dependence_stats.num_dependence_undetermined++;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Data ref a:\n");
+ dump_data_reference (dump_file, dra);
+ fprintf (dump_file, "Data ref b:\n");
+ dump_data_reference (dump_file, drb);
+ fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
+ }
+ finalize_ddr_dependent (ddr, chrec_dont_know);
+ }
}
if (dump_file && (dump_flags & TDF_DETAILS))
compute_self_dependence (struct data_dependence_relation *ddr)
{
unsigned int i;
+ 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_LAST_CONFLICT (subscript) = chrec_dont_know;
}
-}
-
-typedef struct data_dependence_relation *ddr_p;
-DEF_VEC_P(ddr_p);
-DEF_VEC_ALLOC_P(ddr_p,heap);
+ /* The distance vector is the zero vector. */
+ save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+ save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+}
-/* Compute a subset of the data dependence relation graph. Don't
- compute read-read and self relations if
- COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation
- of the opposite relation, i.e. when AB has been computed, don't compute BA.
- DATAREFS contains a list of data references, and the result is set
- in DEPENDENCE_RELATIONS. */
+/* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
+ the data references in DATAREFS, in the LOOP_NEST. When
+ COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
+ relations. */
static void
-compute_all_dependences (varray_type datarefs,
- bool compute_self_and_read_read_dependences,
- VEC(ddr_p,heap) **dependence_relations)
+compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
+ VEC (ddr_p, heap) **dependence_relations,
+ VEC (loop_p, heap) *loop_nest,
+ bool compute_self_and_rr)
{
- unsigned int i, j, N;
-
- N = VARRAY_ACTIVE_SIZE (datarefs);
+ struct data_dependence_relation *ddr;
+ struct data_reference *a, *b;
+ unsigned int i, j;
- /* Note that we specifically skip i == j because it's a self dependence, and
- use compute_self_dependence below. */
+ for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
+ for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
+ if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
+ {
+ ddr = initialize_data_dependence_relation (a, b, loop_nest);
+ VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+ compute_affine_dependence (ddr);
+ }
- for (i = 0; i < N; i++)
- for (j = i + 1; j < N; j++)
+ if (compute_self_and_rr)
+ for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
{
- struct data_reference *a, *b;
- struct data_dependence_relation *ddr;
-
- a = VARRAY_GENERIC_PTR (datarefs, i);
- b = VARRAY_GENERIC_PTR (datarefs, j);
- if (DR_IS_READ (a) && DR_IS_READ (b)
- && !compute_self_and_read_read_dependences)
- continue;
- ddr = initialize_data_dependence_relation (a, b);
-
+ ddr = initialize_data_dependence_relation (a, a, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_affine_dependence (ddr);
- compute_subscript_distance (ddr);
+ compute_self_dependence (ddr);
}
- if (!compute_self_and_read_read_dependences)
- return;
-
- /* Compute self dependence relation of each dataref to itself. */
-
- for (i = 0; i < N; i++)
- {
- struct data_reference *a, *b;
- struct data_dependence_relation *ddr;
-
- a = VARRAY_GENERIC_PTR (datarefs, i);
- b = VARRAY_GENERIC_PTR (datarefs, i);
- ddr = initialize_data_dependence_relation (a, b);
-
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_self_dependence (ddr);
- compute_subscript_distance (ddr);
- }
}
/* Search the data references in LOOP, and record the information into
arithmetic as if they were array accesses, etc. */
tree
-find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
+find_data_references_in_loop (struct loop *loop,
+ VEC (data_reference_p, heap) **datarefs)
{
basic_block bb, *bbs;
unsigned int i;
tree opnd1 = TREE_OPERAND (stmt, 1);
if (TREE_CODE (opnd0) == ARRAY_REF
- || TREE_CODE (opnd0) == INDIRECT_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);
+ VEC_safe_push (data_reference_p, heap, *datarefs, dr);
one_inserted = true;
}
}
if (TREE_CODE (opnd1) == ARRAY_REF
- || TREE_CODE (opnd1) == INDIRECT_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);
+ VEC_safe_push (data_reference_p, heap, *datarefs, dr);
one_inserted = true;
}
}
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)) == 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);
+ VEC_safe_push (data_reference_p, heap, *datarefs, dr);
one_inserted = true;
}
}
struct data_reference *res;
insert_dont_know_node:;
- res = xmalloc (sizeof (struct data_reference));
+ res = XNEW (struct data_reference);
DR_STMT (res) = NULL_TREE;
DR_REF (res) = NULL_TREE;
DR_BASE_OBJECT (res) = NULL;
DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
DR_MEMTAG (res) = NULL_TREE;
DR_PTR_INFO (res) = NULL;
- VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
+ VEC_safe_push (data_reference_p, heap, *datarefs, res);
free (bbs);
return chrec_dont_know;
return NULL_TREE;
}
-\f
+/* Recursive helper function. */
+
+static bool
+find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) *loop_nest)
+{
+ /* Inner loops of the nest should not contain siblings. Example:
+ when there are two consecutive loops,
+
+ | loop_0
+ | loop_1
+ | A[{0, +, 1}_1]
+ | endloop_1
+ | loop_2
+ | A[{0, +, 1}_2]
+ | endloop_2
+ | endloop_0
+
+ the dependence relation cannot be captured by the distance
+ abstraction. */
+ if (loop->next)
+ return false;
+
+ VEC_safe_push (loop_p, heap, loop_nest, loop);
+ if (loop->inner)
+ return find_loop_nest_1 (loop->inner, loop_nest);
+ return true;
+}
+
+/* Return false when the LOOP is not well nested. Otherwise return
+ true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
+ contain the loops from the outermost to the innermost, as they will
+ appear in the classic distance vector. */
-/* This section contains all the entry points. */
+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);
- VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- build_classic_dist_vector (ddr, nb_loops, loop->depth);
- build_classic_dir_vector (ddr, nb_loops, loop->depth);
- return;
+ ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
+ VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
}
+ else
+ compute_all_dependences (*datarefs, dependence_relations, vloops,
+ compute_self_and_read_read_dependences);
- allrelations = NULL;
- compute_all_dependences (*datarefs, compute_self_and_read_read_dependences,
- &allrelations);
-
- for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
+ if (dump_file && (dump_flags & TDF_STATS))
{
- if (build_classic_dist_vector (ddr, nb_loops, loop_nest->depth))
- {
- VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- build_classic_dir_vector (ddr, nb_loops, loop_nest->depth);
- }
- }
+ fprintf (dump_file, "Dependence tester statistics:\n");
+
+ fprintf (dump_file, "Number of dependence tests: %d\n",
+ dependence_stats.num_dependence_tests);
+ fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
+ dependence_stats.num_dependence_dependent);
+ fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
+ dependence_stats.num_dependence_independent);
+ fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
+ dependence_stats.num_dependence_undetermined);
+
+ fprintf (dump_file, "Number of subscript tests: %d\n",
+ dependence_stats.num_subscript_tests);
+ fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
+ dependence_stats.num_subscript_undetermined);
+ fprintf (dump_file, "Number of same subscript function: %d\n",
+ dependence_stats.num_same_subscript_function);
+
+ fprintf (dump_file, "Number of ziv tests: %d\n",
+ dependence_stats.num_ziv);
+ fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
+ dependence_stats.num_ziv_dependent);
+ fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
+ dependence_stats.num_ziv_independent);
+ fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
+ dependence_stats.num_ziv_unimplemented);
+
+ fprintf (dump_file, "Number of siv tests: %d\n",
+ dependence_stats.num_siv);
+ fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
+ dependence_stats.num_siv_dependent);
+ fprintf (dump_file, "Number of siv tests returning independent: %d\n",
+ dependence_stats.num_siv_independent);
+ fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
+ dependence_stats.num_siv_unimplemented);
+
+ fprintf (dump_file, "Number of miv tests: %d\n",
+ dependence_stats.num_miv);
+ fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
+ dependence_stats.num_miv_dependent);
+ fprintf (dump_file, "Number of miv tests returning independent: %d\n",
+ dependence_stats.num_miv_independent);
+ fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
+ dependence_stats.num_miv_unimplemented);
+ }
}
/* Entry point (for testing only). Analyze all the data references
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. */
-
-void
+#if 0
+static void
analyze_all_data_dependences (struct loops *loops)
{
unsigned int i;
- varray_type datarefs;
- varray_type dependence_relations;
int nb_data_refs = 10;
-
- VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
- VARRAY_GENERIC_PTR_INIT (dependence_relations,
- nb_data_refs * nb_data_refs,
- "dependence_relations");
+ VEC (data_reference_p, heap) *datarefs =
+ VEC_alloc (data_reference_p, heap, nb_data_refs);
+ VEC (ddr_p, heap) *dependence_relations =
+ VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
/* Compute DDs on the whole function. */
compute_data_dependences_for_loop (loops->parray[0], false,
unsigned nb_bot_relations = 0;
unsigned nb_basename_differ = 0;
unsigned nb_chrec_relations = 0;
+ struct data_dependence_relation *ddr;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
{
- struct data_dependence_relation *ddr;
- ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
-
if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
nb_top_relations++;
free_dependence_relations (dependence_relations);
free_data_refs (datarefs);
}
+#endif
/* 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));
+ VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
+
free (ddr);
}
DEPENDENCE_RELATIONS. */
void
-free_dependence_relations (varray_type dependence_relations)
+free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
{
unsigned int i;
- if (dependence_relations == NULL)
- return;
+ struct data_dependence_relation *ddr;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
- free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
- varray_clear (dependence_relations);
+ for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+ free_dependence_relation (ddr);
+
+ VEC_free (ddr_p, heap, dependence_relations);
}
/* Free the memory used by the data references from DATAREFS. */
void
-free_data_refs (varray_type datarefs)
+free_data_refs (VEC (data_reference_p, heap) *datarefs)
{
unsigned int i;
-
- if (datarefs == NULL)
- return;
+ struct data_reference *dr;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
+ for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
{
- struct data_reference *dr = (struct data_reference *)
- VARRAY_GENERIC_PTR (datarefs, i);
- if (dr)
- {
- DR_FREE_ACCESS_FNS (dr);
- free (dr);
- }
+ if (DR_TYPE(dr) == ARRAY_REF_TYPE)
+ VEC_free (tree, heap, (dr)->object_info.access_fns);
+ else
+ VEC_free (tree, heap, (dr)->first_location.access_fns);
+
+ free (dr);
}
- varray_clear (datarefs);
+ VEC_free (data_reference_p, heap, datarefs);
}
OSDN Git Service
