/* Data references and dependences detectors.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
+ 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 "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "langhooks.h"
+#include "tree-affine.h"
+#include "params.h"
static struct datadep_stats
{
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);
*off = ssize_int (0);
STRIP_NOPS (exp);
- if (tree_is_chrec (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);
+ }
}
}
dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
{
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;
+ }
+
+ 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)
+ {
+ 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);
+ }
- while (handled_component_p (aref))
+ /* Analyze access functions of dimensions we know to be independent. */
+ aref = &ref;
+ while (handled_component_p (*aref))
{
- if (TREE_CODE (aref) == ARRAY_REF)
+ 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
- && 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 (!integer_zerop (TREE_OPERAND (aref, 1)))
+ if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
{
- 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);
+ 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);
}
- 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 (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;
}
DR_REF (dr) = memref;
DR_IS_READ (dr) = is_read;
- dr_analyze_innermost (dr);
+ 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;
}
/* 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;
}
}
/* 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))
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)
{
dependences. */
if (!loop
|| !find_loop_nest (loop, loop_nest)
- || 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, *loop_nest);
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- res = false;
- }
- else
- compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
- compute_self_and_read_read_dependences);
+ || 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 (data_reference_p, heap) **datarefs)
{
struct graph *rdg = NULL;
- VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
-
- compute_data_dependences_for_loop (loop, false, loop_nest, datarefs,
- dependence_relations);
- if (known_dependences_p (*dependence_relations))
+ if (compute_data_dependences_for_loop (loop, false, loop_nest, datarefs,
+ dependence_relations)
+ && known_dependences_p (*dependence_relations))
{
+ VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
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);
}
- VEC_free (gimple, heap, stmts);
return rdg;
}
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);
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)
OSDN Git Service
