/* Data references and dependences detectors.
- Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Free Software Foundation, Inc.
Contributed by Sebastian Pop <pop@cri.ensmp.fr>
This file is part of GCC.
dump_data_reference (file, dr);
}
+/* Dump into STDERR all the data references from DATAREFS. */
+
+void
+debug_data_references (VEC (data_reference_p, heap) *datarefs)
+{
+ dump_data_references (stderr, datarefs);
+}
+
/* Dump to STDERR all the dependence relations from DDRS. */
void
dump_data_dependence_relation (file, ddr);
}
+/* Print to STDERR the data_reference DR. */
+
+void
+debug_data_reference (struct data_reference *dr)
+{
+ dump_data_reference (stderr, dr);
+}
+
/* Dump function for a DATA_REFERENCE structure. */
void
for (eq = 0; eq < length; eq++)
{
- enum data_dependence_direction dir = dirv[eq];
+ enum data_dependence_direction dir = ((enum data_dependence_direction)
+ dirv[eq]);
switch (dir)
{
enum machine_mode pmode;
int punsignedp, pvolatilep;
+ op0 = TREE_OPERAND (op0, 0);
if (!handled_component_p (op0))
return false;
return build_fold_addr_expr (TREE_OPERAND (addr, 0));
}
-/* Analyzes the behavior of the memory reference DR in the innermost loop that
- contains it. */
+/* 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
+ otherwise. */
-void
+bool
dr_analyze_innermost (struct data_reference *dr)
{
gimple stmt = DR_STMT (dr);
int punsignedp, pvolatilep;
affine_iv base_iv, offset_iv;
tree init, dinit, step;
+ bool in_loop = (loop && loop->num);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "analyze_innermost: ");
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "failed: bit offset alignment.\n");
- return;
+ return false;
}
base = build_fold_addr_expr (base);
- if (!simple_iv (loop, stmt, base, &base_iv, false))
+ if (in_loop)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "failed: evolution of base is not affine.\n");
- return;
+ 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;
+ }
}
+ else
+ {
+ base_iv.base = base;
+ base_iv.step = ssize_int (0);
+ base_iv.no_overflow = true;
+ }
+
if (!poffset)
{
offset_iv.base = ssize_int (0);
offset_iv.step = ssize_int (0);
}
- else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
+ else
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "failed: evolution of offset is not affine.\n");
- return;
+ if (!in_loop)
+ {
+ offset_iv.base = poffset;
+ offset_iv.step = ssize_int (0);
+ }
+ 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;
+ }
}
init = ssize_int (pbitpos / BITS_PER_UNIT);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "success.\n");
+
+ return true;
}
/* Determines the base object and the list of indices of memory reference
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;
- basic_block before_loop = block_before_loop (nest);
-
+ tree base, off, access_fn = NULL_TREE;
+ basic_block before_loop = NULL;
+
+ if (nest)
+ before_loop = block_before_loop (nest);
+
while (handled_component_p (aref))
{
if (TREE_CODE (aref) == ARRAY_REF)
{
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);
+ if (nest)
+ {
+ 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);
+ }
TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
}
aref = TREE_OPERAND (aref, 0);
}
- if (INDIRECT_REF_P (aref))
+ if (nest && INDIRECT_REF_P (aref))
{
op = TREE_OPERAND (aref, 0);
access_fn = analyze_scalar_evolution (loop, op);
static void
dr_analyze_alias (struct data_reference *dr)
{
- gimple stmt = DR_STMT (dr);
tree ref = DR_REF (dr);
- tree base = get_base_address (ref), addr, smt = NULL_TREE;
- ssa_op_iter it;
- tree op;
- bitmap vops;
+ tree base = get_base_address (ref), addr;
- if (DECL_P (base))
- smt = base;
- else if (INDIRECT_REF_P (base))
+ if (INDIRECT_REF_P (base))
{
addr = TREE_OPERAND (base, 0);
if (TREE_CODE (addr) == SSA_NAME)
- {
- smt = symbol_mem_tag (SSA_NAME_VAR (addr));
- DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
- }
- }
-
- DR_SYMBOL_TAG (dr) = smt;
-
- vops = BITMAP_ALLOC (NULL);
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES)
- {
- bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op)));
+ DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
}
-
- DR_VOPS (dr) = vops;
}
/* Returns true if the address of DR is invariant. */
void
free_data_ref (data_reference_p dr)
{
- BITMAP_FREE (DR_VOPS (dr));
VEC_free (tree, heap, DR_ACCESS_FNS (dr));
free (dr);
}
print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
fprintf (dump_file, "\n\tbase_object: ");
print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
- fprintf (dump_file, "\n\tsymbol tag: ");
- print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM);
fprintf (dump_file, "\n");
}
const_tree type_a, type_b;
const_tree decl_a = NULL_TREE, decl_b = NULL_TREE;
- /* If the sets of virtual operands are disjoint, the memory references do not
- alias. */
- if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
- return false;
-
/* If the accessed objects are disjoint, the memory references do not
alias. */
if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b)))
return false;
+ /* Query the alias oracle. */
+ if (!DR_IS_READ (a) && !DR_IS_READ (b))
+ {
+ if (!refs_output_dependent_p (DR_REF (a), DR_REF (b)))
+ return false;
+ }
+ else if (DR_IS_READ (a) && !DR_IS_READ (b))
+ {
+ if (!refs_anti_dependent_p (DR_REF (a), DR_REF (b)))
+ return false;
+ }
+ else if (!refs_may_alias_p (DR_REF (a), DR_REF (b)))
+ return false;
+
if (!addr_a || !addr_b)
return true;
- /* If the references are based on different static objects, they cannot alias
- (PTA should be able to disambiguate such accesses, but often it fails to,
- since currently we cannot distinguish between pointer and offset in pointer
- arithmetics). */
+ /* If the references are based on different static objects, they cannot
+ alias (PTA should be able to disambiguate such accesses, but often
+ it fails to). */
if (TREE_CODE (addr_a) == ADDR_EXPR
&& TREE_CODE (addr_b) == ADDR_EXPR)
return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0);
/* If the base of the object is not invariant in the loop nest, we cannot
analyze it. TODO -- in fact, it would suffice to record that there may
be arbitrary dependences in the loops where the base object varies. */
- if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
- DR_BASE_OBJECT (a)))
+ 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;
{
free_conflict_function (s->conflicting_iterations_in_a);
free_conflict_function (s->conflicting_iterations_in_b);
+ free (s);
}
VEC_free (subscript_p, heap, subscripts);
}
return chrec_convert (chrec_type (chrec), op, NULL);
}
+ case BIT_NOT_EXPR:
+ {
+ /* Handle ~X as -1 - X. */
+ tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
+ return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
+ build_int_cst (TREE_TYPE (chrec), -1), op);
+ }
+
case INTEGER_CST:
return chrec;
/* If the overlap occurs outside of the bounds of the
loop, there is no dependence. */
- if (x1 > niter || y1 > niter)
+ if (x1 >= niter || y1 >= niter)
{
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
return true;
}
-/* Return true if we can create an affine data-ref for OP in STMT. */
-
-bool
-stmt_simple_memref_p (struct loop *loop, gimple stmt, tree op)
-{
- data_reference_p dr;
-
- dr = create_data_ref (loop, op, stmt, true);
- if (!access_functions_are_affine_or_constant_p (dr, loop))
- return false;
-
- free_data_ref (dr);
- return true;
-}
-
/* Initializes an equation for an OMEGA problem using the information
contained in the ACCESS_FUN. Returns true when the operation
succeeded.
{
ddr = initialize_data_dependence_relation (a, b, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
+ if (loop_nest)
+ compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
}
if (compute_self_and_rr)
&& gimple_asm_volatile_p (stmt)))
clobbers_memory = true;
- if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+ if (!gimple_vuse (stmt))
return clobbers_memory;
if (stmt_code == GIMPLE_ASSIGN)
dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
gcc_assert (dr != NULL);
- /* FIXME -- data dependence analysis does not work correctly for objects with
- invariant addresses. Let us fail here until the problem is fixed. */
- if (dr_address_invariant_p (dr))
+ /* 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))
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. */
+
+bool
+graphite_find_data_references_in_stmt (struct loop *nest, gimple stmt,
+ VEC (data_reference_p, heap) **datarefs)
+{
+ unsigned i;
+ VEC (data_ref_loc, heap) *references;
+ data_ref_loc *ref;
+ bool ret = true;
+ data_reference_p dr;
+
+ if (get_references_in_stmt (stmt, &references))
+ {
+ VEC_free (data_ref_loc, heap, references);
+ return false;
+ }
+
+ for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
+ {
+ dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
+ gcc_assert (dr != NULL);
+ VEC_safe_push (data_reference_p, heap, *datarefs, dr);
+ }
+
+ VEC_free (data_ref_loc, heap, references);
+ return ret;
+}
+
+/* Search the data references in LOOP, and record the information into
+ DATAREFS. Returns chrec_dont_know when failing to analyze a
+ difficult case, returns NULL_TREE otherwise. */
+
+static tree
+find_data_references_in_bb (struct loop *loop, basic_block bb,
+ VEC (data_reference_p, heap) **datarefs)
+{
+ gimple_stmt_iterator bsi;
+
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ {
+ gimple stmt = gsi_stmt (bsi);
+
+ if (!find_data_references_in_stmt (loop, stmt, datarefs))
+ {
+ struct data_reference *res;
+ res = XCNEW (struct data_reference);
+ VEC_safe_push (data_reference_p, heap, *datarefs, res);
+
+ return chrec_dont_know;
+ }
+ }
+
+ return NULL_TREE;
+}
+
/* Search the data references in LOOP, and record the information into
DATAREFS. Returns chrec_dont_know when failing to analyze a
difficult case, returns NULL_TREE otherwise.
{
basic_block bb, *bbs;
unsigned int i;
- gimple_stmt_iterator bsi;
bbs = get_loop_body_in_dom_order (loop);
{
bb = bbs[i];
- for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
- {
- gimple stmt = gsi_stmt (bsi);
-
- if (!find_data_references_in_stmt (loop, stmt, datarefs))
- {
- struct data_reference *res;
- res = XCNEW (struct data_reference);
- VEC_safe_push (data_reference_p, heap, *datarefs, res);
-
- free (bbs);
- return chrec_dont_know;
- }
- }
+ if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know)
+ {
+ free (bbs);
+ return chrec_dont_know;
+ }
}
free (bbs);
return res;
}
+/* Returns true when the data dependences for the basic block BB have been
+ computed, false otherwise.
+ DATAREFS is initialized to all the array elements contained in this basic
+ block, DEPENDENCE_RELATIONS contains the relations between the data
+ references. Compute read-read and self relations if
+ COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
+bool
+compute_data_dependences_for_bb (basic_block bb,
+ bool compute_self_and_read_read_dependences,
+ VEC (data_reference_p, heap) **datarefs,
+ VEC (ddr_p, heap) **dependence_relations)
+{
+ 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;
+}
+
/* Entry point (for testing only). Analyze all the data references
and the dependence relations in LOOP.
{
unsigned nb_top_relations = 0;
unsigned nb_bot_relations = 0;
- unsigned nb_basename_differ = 0;
unsigned nb_chrec_relations = 0;
struct data_dependence_relation *ddr;
nb_top_relations++;
else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
- {
- struct data_reference *a = DDR_A (ddr);
- struct data_reference *b = DDR_B (ddr);
-
- if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
- nb_basename_differ++;
- else
- nb_bot_relations++;
- }
+ nb_bot_relations++;
else
nb_chrec_relations++;
/* This structure is used for recording the mapping statement index in
the RDG. */
-struct rdg_vertex_info GTY(())
+struct GTY(()) rdg_vertex_info
{
gimple stmt;
int index;
gimple_stmt_iterator bsi;
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
- if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi), SSA_OP_VDEF))
+ if (gimple_vdef (gsi_stmt (bsi)))
VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
}
OSDN Git Service
