/* Data references and dependences detectors.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
Free Software Foundation, Inc.
Contributed by Sebastian Pop <pop@cri.ensmp.fr>
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "ggc.h"
-#include "flags.h"
-#include "tree.h"
-#include "basic-block.h"
-#include "tree-pretty-print.h"
#include "gimple-pretty-print.h"
#include "tree-flow.h"
-#include "tree-dump.h"
-#include "timevar.h"
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "langhooks.h"
+#include "tree-affine.h"
+#include "params.h"
static struct datadep_stats
{
{
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));
+ return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a));
}
/* Returns true iff A divides B. */
{
unsigned int i;
- fprintf (outf, "#(Data Ref: \n# stmt: ");
+ fprintf (outf, "#(Data Ref: \n");
+ fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
+ fprintf (outf, "# stmt: ");
print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
fprintf (outf, "# ref: ");
print_generic_stmt (outf, DR_REF (dr), 0);
print_direction_vector (outf, v, length);
}
+/* Print out a vector VEC of length N to OUTFILE. */
+
+static inline void
+print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
+{
+ int i;
+
+ for (i = 0; i < n; i++)
+ fprintf (outfile, "%3d ", vector[i]);
+ fprintf (outfile, "\n");
+}
+
/* Print a vector of distance vectors. */
void
int punsignedp, pvolatilep;
op0 = TREE_OPERAND (op0, 0);
- if (!handled_component_p (op0))
- return false;
-
base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
&pmode, &punsignedp, &pvolatilep, false);
split_constant_offset (poffset, &poffset, &off1);
off0 = size_binop (PLUS_EXPR, off0, off1);
if (POINTER_TYPE_P (TREE_TYPE (base)))
- base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base),
- base, fold_convert (sizetype, poffset));
+ base = fold_build_pointer_plus (base, poffset);
else
base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
fold_convert (TREE_TYPE (base), poffset));
*off = ssize_int (0);
STRIP_NOPS (exp);
- if (automatically_generated_chrec_p (exp))
+ if (tree_is_chrec (exp)
+ || get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS)
return;
otype = TREE_TYPE (exp);
}
/* Analyzes the behavior of the memory reference DR in the innermost loop or
- basic block that contains it. Returns true if analysis succeed or false
+ basic block that contains it. Returns true if analysis succeed or false
otherwise. */
bool
-dr_analyze_innermost (struct data_reference *dr)
+dr_analyze_innermost (struct data_reference *dr, struct loop *nest)
{
gimple stmt = DR_STMT (dr);
struct loop *loop = loop_containing_stmt (stmt);
}
else
base = build_fold_addr_expr (base);
+
if (in_loop)
{
if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
false))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "failed: evolution of base is not affine.\n");
- return false;
+ if (nest)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "failed: evolution of base is not"
+ " affine.\n");
+ return false;
+ }
+ else
+ {
+ base_iv.base = base;
+ base_iv.step = ssize_int (0);
+ base_iv.no_overflow = true;
+ }
}
}
else
else if (!simple_iv (loop, loop_containing_stmt (stmt),
poffset, &offset_iv, false))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "failed: evolution of offset is not"
- " affine.\n");
- return false;
+ if (nest)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "failed: evolution of offset is not"
+ " affine.\n");
+ return false;
+ }
+ else
+ {
+ offset_iv.base = poffset;
+ offset_iv.step = ssize_int (0);
+ }
}
}
}
/* Determines the base object and the list of indices of memory reference
- DR, analyzed in loop nest NEST. */
+ DR, analyzed in LOOP and instantiated in loop nest NEST. */
static void
-dr_analyze_indices (struct data_reference *dr, struct loop *nest)
+dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
{
- gimple stmt = DR_STMT (dr);
- struct loop *loop = loop_containing_stmt (stmt);
VEC (tree, heap) *access_fns = NULL;
- tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
- tree base, off, access_fn = NULL_TREE;
- basic_block before_loop = NULL;
+ tree ref, *aref, op;
+ tree base, off, access_fn;
+ basic_block before_loop;
- if (nest)
- before_loop = block_before_loop (nest);
+ /* If analyzing a basic-block there are no indices to analyze
+ and thus no access functions. */
+ if (!nest)
+ {
+ DR_BASE_OBJECT (dr) = DR_REF (dr);
+ DR_ACCESS_FNS (dr) = NULL;
+ return;
+ }
- while (handled_component_p (aref))
+ ref = unshare_expr (DR_REF (dr));
+ before_loop = block_before_loop (nest);
+
+ /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
+ into a two element array with a constant index. The base is
+ then just the immediate underlying object. */
+ if (TREE_CODE (ref) == REALPART_EXPR)
{
- if (TREE_CODE (aref) == ARRAY_REF)
+ ref = TREE_OPERAND (ref, 0);
+ VEC_safe_push (tree, heap, access_fns, integer_zero_node);
+ }
+ else if (TREE_CODE (ref) == IMAGPART_EXPR)
+ {
+ ref = TREE_OPERAND (ref, 0);
+ VEC_safe_push (tree, heap, access_fns, integer_one_node);
+ }
+
+ /* Analyze access functions of dimensions we know to be independent. */
+ aref = &ref;
+ while (handled_component_p (*aref))
+ {
+ if (TREE_CODE (*aref) == ARRAY_REF)
{
- op = TREE_OPERAND (aref, 1);
- if (nest)
+ op = TREE_OPERAND (*aref, 1);
+ access_fn = analyze_scalar_evolution (loop, op);
+ access_fn = instantiate_scev (before_loop, loop, access_fn);
+ VEC_safe_push (tree, heap, access_fns, access_fn);
+ /* For ARRAY_REFs the base is the reference with the index replaced
+ by zero if we can not strip it as the outermost component. */
+ if (*aref == ref)
{
- access_fn = analyze_scalar_evolution (loop, op);
- access_fn = instantiate_scev (before_loop, loop, access_fn);
- VEC_safe_push (tree, heap, access_fns, access_fn);
+ *aref = TREE_OPERAND (*aref, 0);
+ continue;
}
-
- TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
+ else
+ TREE_OPERAND (*aref, 1) = build_int_cst (TREE_TYPE (op), 0);
}
- aref = TREE_OPERAND (aref, 0);
+ aref = &TREE_OPERAND (*aref, 0);
}
- if (nest
- && (INDIRECT_REF_P (aref)
- || TREE_CODE (aref) == MEM_REF))
+ /* If the address operand of a MEM_REF base has an evolution in the
+ analyzed nest, add it as an additional independent access-function. */
+ if (TREE_CODE (*aref) == MEM_REF)
{
- op = TREE_OPERAND (aref, 0);
+ op = TREE_OPERAND (*aref, 0);
access_fn = analyze_scalar_evolution (loop, op);
access_fn = instantiate_scev (before_loop, loop, access_fn);
- base = initial_condition (access_fn);
- split_constant_offset (base, &base, &off);
- if (TREE_CODE (aref) == MEM_REF)
- off = size_binop (PLUS_EXPR, off,
- fold_convert (ssizetype, TREE_OPERAND (aref, 1)));
- access_fn = chrec_replace_initial_condition (access_fn,
- fold_convert (TREE_TYPE (base), off));
-
- TREE_OPERAND (aref, 0) = base;
- VEC_safe_push (tree, heap, access_fns, access_fn);
+ if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
+ {
+ tree orig_type;
+ base = initial_condition (access_fn);
+ orig_type = TREE_TYPE (base);
+ STRIP_USELESS_TYPE_CONVERSION (base);
+ split_constant_offset (base, &base, &off);
+ /* Fold the MEM_REF offset into the evolutions initial
+ value to make more bases comparable. */
+ if (!integer_zerop (TREE_OPERAND (*aref, 1)))
+ {
+ off = size_binop (PLUS_EXPR, off,
+ fold_convert (ssizetype,
+ TREE_OPERAND (*aref, 1)));
+ TREE_OPERAND (*aref, 1)
+ = build_int_cst (TREE_TYPE (TREE_OPERAND (*aref, 1)), 0);
+ }
+ access_fn = chrec_replace_initial_condition
+ (access_fn, fold_convert (orig_type, off));
+ *aref = fold_build2_loc (EXPR_LOCATION (*aref),
+ MEM_REF, TREE_TYPE (*aref),
+ base, TREE_OPERAND (*aref, 1));
+ VEC_safe_push (tree, heap, access_fns, access_fn);
+ }
}
- if (TREE_CODE (aref) == MEM_REF)
- TREE_OPERAND (aref, 1)
- = build_int_cst (TREE_TYPE (TREE_OPERAND (aref, 1)), 0);
-
- if (TREE_CODE (ref) == MEM_REF
- && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR
- && integer_zerop (TREE_OPERAND (ref, 1)))
- ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
-
- /* For canonicalization purposes we'd like to strip all outermost
- zero-offset component-refs.
- ??? For now simply handle zero-index array-refs. */
- while (TREE_CODE (ref) == ARRAY_REF
- && integer_zerop (TREE_OPERAND (ref, 1)))
- ref = TREE_OPERAND (ref, 0);
-
DR_BASE_OBJECT (dr) = ref;
DR_ACCESS_FNS (dr) = access_fns;
}
}
}
-/* Returns true if the address of DR is invariant. */
-
-static bool
-dr_address_invariant_p (struct data_reference *dr)
-{
- unsigned i;
- tree idx;
-
- FOR_EACH_VEC_ELT (tree, DR_ACCESS_FNS (dr), i, idx)
- if (tree_contains_chrecs (idx, NULL))
- return false;
-
- return true;
-}
-
/* Frees data reference DR. */
void
/* Analyzes memory reference MEMREF accessed in STMT. The reference
is read if IS_READ is true, write otherwise. Returns the
- data_reference description of MEMREF. NEST is the outermost loop of the
- loop nest in that the reference should be analyzed. */
+ data_reference description of MEMREF. NEST is the outermost loop
+ in which the reference should be instantiated, LOOP is the loop in
+ which the data reference should be analyzed. */
struct data_reference *
-create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read)
+create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
+ bool is_read)
{
struct data_reference *dr;
DR_REF (dr) = memref;
DR_IS_READ (dr) = is_read;
- dr_analyze_innermost (dr);
- dr_analyze_indices (dr, nest);
+ dr_analyze_innermost (dr, nest);
+ dr_analyze_indices (dr, nest, loop);
dr_analyze_alias (dr);
if (dump_file && (dump_flags & TDF_DETAILS))
{
+ unsigned i;
fprintf (dump_file, "\tbase_address: ");
print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
fprintf (dump_file, "\n\toffset from base address: ");
fprintf (dump_file, "\n\tbase_object: ");
print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
fprintf (dump_file, "\n");
+ for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
+ {
+ fprintf (dump_file, "\tAccess function %d: ", i);
+ print_generic_stmt (dump_file, DR_ACCESS_FN (dr, i), TDF_SLIM);
+ }
}
return dr;
}
+/* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
+ expressions. */
+static bool
+dr_equal_offsets_p1 (tree offset1, tree offset2)
+{
+ bool res;
+
+ STRIP_NOPS (offset1);
+ STRIP_NOPS (offset2);
+
+ if (offset1 == offset2)
+ return true;
+
+ if (TREE_CODE (offset1) != TREE_CODE (offset2)
+ || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
+ return false;
+
+ res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
+ TREE_OPERAND (offset2, 0));
+
+ if (!res || !BINARY_CLASS_P (offset1))
+ return res;
+
+ res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
+ TREE_OPERAND (offset2, 1));
+
+ return res;
+}
+
+/* Check if DRA and DRB have equal offsets. */
+bool
+dr_equal_offsets_p (struct data_reference *dra,
+ struct data_reference *drb)
+{
+ tree offset1, offset2;
+
+ offset1 = DR_OFFSET (dra);
+ offset2 = DR_OFFSET (drb);
+
+ return dr_equal_offsets_p1 (offset1, offset2);
+}
+
/* Returns true if FNA == FNB. */
static bool
}
/* Returns false if we can prove that data references A and B do not alias,
- true otherwise. */
+ true otherwise. If LOOP_NEST is false no cross-iteration aliases are
+ considered. */
bool
-dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
+dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
+ bool loop_nest)
{
tree addr_a = DR_BASE_OBJECT (a);
tree addr_b = DR_BASE_OBJECT (b);
+ /* If we are not processing a loop nest but scalar code we
+ do not need to care about possible cross-iteration dependences
+ and thus can process the full original reference. Do so,
+ similar to how loop invariant motion applies extra offset-based
+ disambiguation. */
+ if (!loop_nest)
+ {
+ aff_tree off1, off2;
+ double_int size1, size2;
+ get_inner_reference_aff (DR_REF (a), &off1, &size1);
+ get_inner_reference_aff (DR_REF (b), &off2, &size2);
+ aff_combination_scale (&off1, double_int_minus_one);
+ aff_combination_add (&off2, &off1);
+ if (aff_comb_cannot_overlap_p (&off2, size1, size2))
+ return false;
+ }
+
if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
return refs_output_dependent_p (addr_a, addr_b);
else if (DR_IS_READ (a) && DR_IS_WRITE (b))
return refs_may_alias_p (addr_a, addr_b);
}
-static void compute_self_dependence (struct data_dependence_relation *);
-
/* 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 *
+struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
struct data_reference *b,
VEC (loop_p, heap) *loop_nest)
}
/* If the data references do not alias, then they are independent. */
- if (!dr_may_alias_p (a, b))
+ if (!dr_may_alias_p (a, b, loop_nest != NULL))
{
DDR_ARE_DEPENDENT (res) = chrec_known;
return res;
}
- /* When the references are exactly the same, don't spend time doing
- the data dependence tests, just initialize the ddr and return. */
+ /* The case where the references are exactly the same. */
if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
{
+ if (loop_nest
+ && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
+ DR_BASE_OBJECT (a)))
+ {
+ DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+ return res;
+ }
DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
DDR_LOOP_NEST (res) = loop_nest;
DDR_INNER_LOOP (res) = 0;
DDR_SELF_REFERENCE (res) = true;
- compute_self_dependence (res);
+ for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+ {
+ struct subscript *subscript;
+
+ subscript = XNEW (struct subscript);
+ 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;
+ VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
+ }
return res;
}
fprintf (dump_file, ")\n");
}
-/* 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. */
-
-bool
-estimated_loop_iterations (struct loop *loop, bool conservative,
- double_int *nit)
-{
- estimate_numbers_of_iterations_loop (loop, true);
- 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)
-{
- 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);
-
- return hwi_nit < 0 ? -1 : hwi_nit;
-}
-
-/* Similar to estimated_loop_iterations, but returns the estimate as a tree,
+/* Similar to max_stmt_executions_int, but returns the bound 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
+ bound 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)
+max_stmt_executions_tree (struct loop *loop)
{
double_int nit;
- tree type;
- if (!estimated_loop_iterations (loop, conservative, &nit))
+ if (!max_stmt_executions (loop, true, &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))
+ if (!double_int_fits_to_tree_p (unsigned_type_node, nit))
return chrec_dont_know;
- return double_int_to_tree (type, nit);
+ return double_int_to_tree (unsigned_type_node, nit);
}
/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
/* Perform weak-zero siv test to see if overlap is
outside the loop bounds. */
- numiter = estimated_loop_iterations_int (loop, false);
+ numiter = max_stmt_executions_int (loop, true);
if (numiter >= 0
&& compare_tree_int (tmp, numiter) > 0)
/* Perform weak-zero siv test to see if overlap is
outside the loop bounds. */
- numiter = estimated_loop_iterations_int (loop, false);
+ numiter = max_stmt_executions_int (loop, true);
if (numiter >= 0
&& compare_tree_int (tmp, numiter) > 0)
step_z = int_cst_value (CHREC_RIGHT (chrec_b));
niter_x =
- estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)),
- false);
- niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false);
- niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false);
+ max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
+ niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
+ niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b), true);
if (niter_x < 0 || niter_y < 0 || niter_z < 0)
{
affine_fn_free (overlaps_b_xyz);
}
+/* Copy the elements of vector VEC1 with length SIZE to VEC2. */
+
+static void
+lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
+ int size)
+{
+ memcpy (vec2, vec1, size * sizeof (*vec1));
+}
+
+/* Copy the elements of M x N matrix MAT1 to MAT2. */
+
+static void
+lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2,
+ int m, int n)
+{
+ int i;
+
+ for (i = 0; i < m; i++)
+ lambda_vector_copy (mat1[i], mat2[i], n);
+}
+
+/* Store the N x N identity matrix in MAT. */
+
+static void
+lambda_matrix_id (lambda_matrix mat, int size)
+{
+ int i, j;
+
+ for (i = 0; i < size; i++)
+ for (j = 0; j < size; j++)
+ mat[i][j] = (i == j) ? 1 : 0;
+}
+
+/* Return the first nonzero element of vector VEC1 between START and N.
+ We must have START <= N. Returns N if VEC1 is the zero vector. */
+
+static int
+lambda_vector_first_nz (lambda_vector vec1, int n, int start)
+{
+ int j = start;
+ while (j < n && vec1[j] == 0)
+ j++;
+ return j;
+}
+
+/* Add a multiple of row R1 of matrix MAT with N columns to row R2:
+ R2 = R2 + CONST1 * R1. */
+
+static void
+lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1)
+{
+ int i;
+
+ if (const1 == 0)
+ return;
+
+ for (i = 0; i < n; i++)
+ mat[r2][i] += const1 * mat[r1][i];
+}
+
+/* Swap rows R1 and R2 in matrix MAT. */
+
+static void
+lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2)
+{
+ lambda_vector row;
+
+ row = mat[r1];
+ mat[r1] = mat[r2];
+ mat[r2] = row;
+}
+
+/* Multiply vector VEC1 of length SIZE by a constant CONST1,
+ and store the result in VEC2. */
+
+static void
+lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
+ int size, int const1)
+{
+ int i;
+
+ if (const1 == 0)
+ lambda_vector_clear (vec2, size);
+ else
+ for (i = 0; i < size; i++)
+ vec2[i] = const1 * vec1[i];
+}
+
+/* Negate vector VEC1 with length SIZE and store it in VEC2. */
+
+static void
+lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
+ int size)
+{
+ lambda_vector_mult_const (vec1, vec2, size, -1);
+}
+
+/* Negate row R1 of matrix MAT which has N columns. */
+
+static void
+lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
+{
+ lambda_vector_negate (mat[r1], mat[r1], n);
+}
+
+/* Return true if two vectors are equal. */
+
+static bool
+lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
+{
+ int i;
+ for (i = 0; i < size; i++)
+ if (vec1[i] != vec2[i])
+ return false;
+ return true;
+}
+
+/* Given an M x N integer matrix A, this function determines an M x
+ M unimodular matrix U, and an M x N echelon matrix S such that
+ "U.A = S". This decomposition is also known as "right Hermite".
+
+ Ref: Algorithm 2.1 page 33 in "Loop Transformations for
+ Restructuring Compilers" Utpal Banerjee. */
+
+static void
+lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
+ lambda_matrix S, lambda_matrix U)
+{
+ int i, j, i0 = 0;
+
+ lambda_matrix_copy (A, S, m, n);
+ lambda_matrix_id (U, m);
+
+ for (j = 0; j < n; j++)
+ {
+ if (lambda_vector_first_nz (S[j], m, i0) < m)
+ {
+ ++i0;
+ for (i = m - 1; i >= i0; i--)
+ {
+ while (S[i][j] != 0)
+ {
+ int sigma, factor, a, b;
+
+ a = S[i-1][j];
+ b = S[i][j];
+ sigma = (a * b < 0) ? -1: 1;
+ a = abs (a);
+ b = abs (b);
+ factor = sigma * (a / b);
+
+ lambda_matrix_row_add (S, n, i, i-1, -factor);
+ lambda_matrix_row_exchange (S, i, i-1);
+
+ lambda_matrix_row_add (U, m, i, i-1, -factor);
+ lambda_matrix_row_exchange (U, i, i-1);
+ }
+ }
+ }
+ }
+}
+
/* Determines the overlapping elements due to accesses CHREC_A and
CHREC_B, that are affine functions. This function cannot handle
symbolic evolution functions, ie. when initial conditions are
HOST_WIDE_INT niter, niter_a, niter_b;
affine_fn ova, ovb;
- niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
- false);
- niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
- false);
+ niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
+ niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b), true);
niter = MIN (niter_a, niter_b);
step_a = int_cst_value (CHREC_RIGHT (chrec_a));
step_b = int_cst_value (CHREC_RIGHT (chrec_b));
if (i1 > 0 && j1 > 0)
{
- HOST_WIDE_INT niter_a = estimated_loop_iterations_int
- (get_chrec_loop (chrec_a), false);
- HOST_WIDE_INT niter_b = estimated_loop_iterations_int
- (get_chrec_loop (chrec_b), false);
+ HOST_WIDE_INT niter_a = max_stmt_executions_int
+ (get_chrec_loop (chrec_a), true);
+ HOST_WIDE_INT niter_b = max_stmt_executions_int
+ (get_chrec_loop (chrec_b), true);
HOST_WIDE_INT niter = MIN (niter_a, niter_b);
/* (X0, Y0) is a solution of the Diophantine equation:
tree *last_conflicts,
struct loop *loop_nest)
{
- /* FIXME: This is a MIV subscript, not yet handled.
- Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
- (A[i] vs. A[j]).
-
- In the SIV test we had to solve a Diophantine equation with two
- variables. In the MIV case we have to solve a Diophantine
- equation with 2*n variables (if the subscript uses n IVs).
- */
tree type, difference;
dependence_stats.num_miv++;
in the same order. */
*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);
+ *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a));
dependence_stats.num_miv_dependent++;
}
/* 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, lnn))
+ && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
+ || operand_equal_p (chrec_a, chrec_b, 0)))
{
dependence_stats.num_same_subscript_function++;
*overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
}
/* If they aren't the same, and aren't affine, we can't do anything
- yet. */
+ yet. */
else if ((chrec_contains_symbols (chrec_a)
|| chrec_contains_symbols (chrec_b))
&& (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
&& TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
{
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
- | A[{4, +, 1}_1]
- | loop_2
- | A[{5, +, 1}_2]
- | endloop_2
- | endloop_1
- In this case, the dependence is carried by loop_1. */
- index = index_a < index_b ? index_a : index_b;
- *index_carry = MIN (index, *index_carry);
+ int var_a = CHREC_VARIABLE (access_fn_a);
+ int var_b = CHREC_VARIABLE (access_fn_b);
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ if (var_a != var_b
+ || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
return false;
}
dist = int_cst_value (SUB_DISTANCE (subscript));
+ index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
+ *index_carry = MIN (index, *index_carry);
/* This is the subscript coupling test. If we have already
recorded a distance for this loop (a distance coming from
tree fun_a = chrec_convert (type, access_fun_a, NULL);
tree fun_b = chrec_convert (type, access_fun_b, NULL);
tree difference = chrec_fold_minus (type, fun_a, fun_b);
+ tree minus_one;
/* When the fun_a - fun_b is not constant, the dependence is not
captured by the classic distance vector representation. */
return true;
}
- fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
+ minus_one = build_int_cst (type, -1);
+ fun_b = chrec_fold_multiply (type, fun_b, minus_one);
eq = omega_add_zero_eq (pb, omega_black);
if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
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, false);
+ HOST_WIDE_INT nbi = max_stmt_executions_int (loopi, true);
/* 0 <= loop_x */
ineq = omega_add_zero_geq (pb, omega_black);
}
/* Analyze only when the dependence relation is not yet known. */
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
- && !DDR_SELF_REFERENCE (ddr))
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
dependence_stats.num_dependence_tests++;
fprintf (dump_file, ")\n");
}
-/* This computes the dependence relation for the same data
- reference into DDR. */
-
-static void
-compute_self_dependence (struct data_dependence_relation *ddr)
-{
- unsigned int i;
- struct subscript *subscript;
-
- if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return;
-
- for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
- i++)
- {
- if (SUB_CONFLICTS_IN_A (subscript))
- free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
- if (SUB_CONFLICTS_IN_B (subscript))
- free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
-
- /* The accessed index overlaps for each iteration. */
- 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. */
- save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
- save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
-}
-
/* 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. */
+ relations. Return true when successful, i.e. data references number
+ is small enough to be handled. */
-void
+bool
compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
VEC (ddr_p, heap) **dependence_relations,
VEC (loop_p, heap) *loop_nest,
struct data_reference *a, *b;
unsigned int i, j;
+ if ((int) VEC_length (data_reference_p, datarefs)
+ > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
+ {
+ struct data_dependence_relation *ddr;
+
+ /* Insert a single relation into dependence_relations:
+ chrec_dont_know. */
+ ddr = initialize_data_dependence_relation (NULL, NULL, loop_nest);
+ VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+ return false;
+ }
+
FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
{
ddr = initialize_data_dependence_relation (a, a, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_self_dependence (ddr);
+ if (loop_nest)
+ compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
}
+
+ return true;
}
/* Stores the locations of memory references in STMT to REFERENCES. Returns
if ((stmt_code == GIMPLE_CALL
&& !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
|| (stmt_code == GIMPLE_ASM
- && gimple_asm_volatile_p (stmt)))
+ && (gimple_asm_volatile_p (stmt) || gimple_vuse (stmt))))
clobbers_memory = true;
if (!gimple_vuse (stmt))
ref->pos = op1;
ref->is_read = true;
}
-
- if (DECL_P (*op0)
- || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
- {
- ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
- ref->pos = op0;
- ref->is_read = false;
- }
}
else if (stmt_code == GIMPLE_CALL)
{
- unsigned i, n = gimple_call_num_args (stmt);
+ unsigned i, n;
+ op0 = gimple_call_lhs_ptr (stmt);
+ n = gimple_call_num_args (stmt);
for (i = 0; i < n; i++)
{
- op0 = gimple_call_arg_ptr (stmt, i);
+ op1 = gimple_call_arg_ptr (stmt, i);
- if (DECL_P (*op0)
- || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
+ if (DECL_P (*op1)
+ || (REFERENCE_CLASS_P (*op1) && get_base_address (*op1)))
{
ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
- ref->pos = op0;
+ ref->pos = op1;
ref->is_read = true;
}
}
}
+ else
+ return clobbers_memory;
+ if (*op0
+ && (DECL_P (*op0)
+ || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))))
+ {
+ ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+ ref->pos = op0;
+ ref->is_read = false;
+ }
return clobbers_memory;
}
FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
{
- dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
+ dr = create_data_ref (nest, loop_containing_stmt (stmt),
+ *ref->pos, stmt, ref->is_read);
gcc_assert (dr != NULL);
-
- /* FIXME -- data dependence analysis does not work correctly for objects
- with invariant addresses in loop nests. Let us fail here until the
- problem is fixed. */
- if (dr_address_invariant_p (dr) && nest)
- {
- free_data_ref (dr);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\tFAILED as dr address is invariant\n");
- ret = false;
- break;
- }
-
VEC_safe_push (data_reference_p, heap, *datarefs, dr);
}
VEC_free (data_ref_loc, heap, references);
return ret;
}
-/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
- reference, returns false, otherwise returns true. NEST is the outermost
- loop of the loop nest in which the references should be analyzed. */
+/* Stores the data references in STMT to DATAREFS. If there is an
+ unanalyzable reference, returns false, otherwise returns true.
+ NEST is the outermost loop of the loop nest in which the references
+ should be instantiated, LOOP is the loop in which the references
+ should be analyzed. */
bool
-graphite_find_data_references_in_stmt (struct loop *nest, gimple stmt,
+graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
VEC (data_reference_p, heap) **datarefs)
{
unsigned i;
FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
{
- dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
+ dr = create_data_ref (nest, loop, *ref->pos, stmt, ref->is_read);
gcc_assert (dr != NULL);
VEC_safe_push (data_reference_p, heap, *datarefs, dr);
}
DATAREFS. Returns chrec_dont_know when failing to analyze a
difficult case, returns NULL_TREE otherwise. */
-static tree
+tree
find_data_references_in_bb (struct loop *loop, basic_block bb,
VEC (data_reference_p, heap) **datarefs)
{
TODO: This function should be made smarter so that it can handle address
arithmetic as if they were array accesses, etc. */
-tree
+static tree
find_data_references_in_loop (struct loop *loop,
VEC (data_reference_p, heap) **datarefs)
{
bool
compute_data_dependences_for_loop (struct loop *loop,
bool compute_self_and_read_read_dependences,
+ VEC (loop_p, heap) **loop_nest,
VEC (data_reference_p, heap) **datarefs,
VEC (ddr_p, heap) **dependence_relations)
{
bool res = true;
- VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
memset (&dependence_stats, 0, sizeof (dependence_stats));
is not computable, give up without spending time to compute other
dependences. */
if (!loop
- || !find_loop_nest (loop, &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, vloops);
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- res = false;
- }
- else
- compute_all_dependences (*datarefs, dependence_relations, vloops,
- compute_self_and_read_read_dependences);
+ || !find_loop_nest (loop, loop_nest)
+ || find_data_references_in_loop (loop, datarefs) == chrec_dont_know
+ || !compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
+ compute_self_and_read_read_dependences))
+ res = false;
if (dump_file && (dump_flags & TDF_STATS))
{
if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know)
return false;
- compute_all_dependences (*datarefs, dependence_relations, NULL,
- compute_self_and_read_read_dependences);
- return true;
+ return compute_all_dependences (*datarefs, dependence_relations, NULL,
+ compute_self_and_read_read_dependences);
}
/* Entry point (for testing only). Analyze all the data references
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);
+ VEC (loop_p, heap) *loop_nest = VEC_alloc (loop_p, heap, 3);
/* Compute DDs on the whole function. */
- compute_data_dependences_for_loop (loop, false, &datarefs,
+ compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs,
&dependence_relations);
if (dump_file)
}
}
+ VEC_free (loop_p, heap, loop_nest);
free_dependence_relations (dependence_relations);
free_data_refs (datarefs);
}
{
unsigned int i;
struct data_dependence_relation *ddr;
- VEC (loop_p, heap) *loop_nest = NULL;
FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
- {
- 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);
+ if (ddr)
free_dependence_relation (ddr);
- }
- if (loop_nest)
- VEC_free (loop_p, heap, loop_nest);
VEC_free (ddr_p, heap, dependence_relations);
}
for (e = v->succ; e; e = e->succ_next)
fprintf (file, " %d", e->dest);
- fprintf (file, ") \n");
+ fprintf (file, ")\n");
print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
fprintf (file, ")\n");
}
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
{
stmt = gsi_stmt (bsi);
- if (gimple_code (stmt) != GIMPLE_LABEL)
+ if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
VEC_safe_push (gimple, heap, *stmts, stmt);
}
}
scalar dependence. */
struct graph *
-build_rdg (struct loop *loop)
+build_rdg (struct loop *loop,
+ VEC (loop_p, heap) **loop_nest,
+ VEC (ddr_p, heap) **dependence_relations,
+ VEC (data_reference_p, heap) **datarefs)
{
- int nb_data_refs = 10;
struct graph *rdg = NULL;
- VEC (ddr_p, heap) *dependence_relations;
- VEC (data_reference_p, heap) *datarefs;
- VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs);
-
- dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
- datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
- compute_data_dependences_for_loop (loop,
- false,
- &datarefs,
- &dependence_relations);
-
- if (!known_dependences_p (dependence_relations))
- {
- free_dependence_relations (dependence_relations);
- free_data_refs (datarefs);
- VEC_free (gimple, heap, stmts);
-
- return rdg;
- }
+ VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
- stmts_from_loop (loop, &stmts);
- rdg = build_empty_rdg (VEC_length (gimple, stmts));
+ compute_data_dependences_for_loop (loop, false, loop_nest, datarefs,
+ dependence_relations);
- rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
- eq_stmt_vertex_info, hash_stmt_vertex_del);
- create_rdg_vertices (rdg, stmts);
- create_rdg_edges (rdg, dependence_relations);
+ if (known_dependences_p (*dependence_relations))
+ {
+ stmts_from_loop (loop, &stmts);
+ rdg = build_empty_rdg (VEC_length (gimple, stmts));
+ create_rdg_vertices (rdg, stmts);
+ create_rdg_edges (rdg, *dependence_relations);
+ }
VEC_free (gimple, heap, stmts);
return rdg;
int i;
for (i = 0; i < rdg->n_vertices; i++)
- free (rdg->vertices[i].data);
+ {
+ struct vertex *v = &(rdg->vertices[i]);
+ struct graph_edge *e;
+
+ for (e = v->succ; e; e = e->succ_next)
+ free (e->data);
+
+ free (v->data);
+ }
htab_delete (rdg->indices);
free_graph (rdg);
free (bbs);
}
-/* Returns true when STMT is an assignment that contains a data
- reference on its LHS with a stride of the same size as its unit
- type. */
+/* Returns true when the statement at STMT is of the form "A[i] = 0"
+ that contains a data reference on its LHS with a stride of the same
+ size as its unit type. */
-static bool
-mem_write_stride_of_same_size_as_unit_type_p (gimple stmt)
+bool
+stmt_with_adjacent_zero_store_dr_p (gimple stmt)
{
- struct data_reference *dr = XCNEW (struct data_reference);
- tree op0 = gimple_assign_lhs (stmt);
+ tree op0, op1;
bool res;
+ struct data_reference *dr;
+
+ if (!stmt
+ || !gimple_vdef (stmt)
+ || !is_gimple_assign (stmt)
+ || !gimple_assign_single_p (stmt)
+ || !(op1 = gimple_assign_rhs1 (stmt))
+ || !(integer_zerop (op1) || real_zerop (op1)))
+ return false;
+
+ dr = XCNEW (struct data_reference);
+ op0 = gimple_assign_lhs (stmt);
DR_STMT (dr) = stmt;
DR_REF (dr) = op0;
- res = dr_analyze_innermost (dr)
+ res = dr_analyze_innermost (dr, loop_containing_stmt (stmt))
&& stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0));
free_data_ref (dr);
basic_block bb;
gimple_stmt_iterator si;
gimple stmt;
- tree op;
basic_block *bbs = get_loop_body_in_dom_order (loop);
for (i = 0; i < loop->num_nodes; i++)
for (bb = bbs[i], si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
if ((stmt = gsi_stmt (si))
- && gimple_vdef (stmt)
- && is_gimple_assign (stmt)
- && gimple_assign_rhs_code (stmt) == INTEGER_CST
- && (op = gimple_assign_rhs1 (stmt))
- && (integer_zerop (op) || real_zerop (op))
- && mem_write_stride_of_same_size_as_unit_type_p (stmt))
+ && stmt_with_adjacent_zero_store_dr_p (stmt))
VEC_safe_push (gimple, heap, *stmts, gsi_stmt (si));
free (bbs);
DR_STMT (dr) = stmt;
DR_REF (dr) = *ref->pos;
- dr_analyze_innermost (dr);
+ dr_analyze_innermost (dr, loop_containing_stmt (stmt));
base_address = DR_BASE_ADDRESS (dr);
if (!base_address)