/* 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.
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
-#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
/* Returns true iff A divides B. */
static inline bool
-tree_fold_divides_p (tree a, tree b)
+tree_fold_divides_p (const_tree a, const_tree b)
{
gcc_assert (TREE_CODE (a) == INTEGER_CST);
gcc_assert (TREE_CODE (b) == INTEGER_CST);
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
+debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs)
+{
+ dump_data_dependence_relations (stderr, ddrs);
+}
+
/* Dump into FILE 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
unsigned int i;
fprintf (outf, "(Data Ref: \n stmt: ");
- print_generic_stmt (outf, DR_STMT (dr), 0);
+ print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
fprintf (outf, " ref: ");
print_generic_stmt (outf, DR_REF (dr), 0);
fprintf (outf, " base_object: ");
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)
{
{
struct data_reference *dra, *drb;
+ fprintf (outf, "(Data Dep: \n");
+
+ if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ {
+ fprintf (outf, " (don't know)\n)\n");
+ return;
+ }
+
dra = DDR_A (ddr);
drb = DDR_B (ddr);
- fprintf (outf, "(Data Dep: \n");
- if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
- fprintf (outf, " (don't know)\n");
-
- else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ dump_data_reference (outf, dra);
+ dump_data_reference (outf, drb);
+
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
fprintf (outf, " (no dependence)\n");
else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
fprintf (file, "\n\n");
}
-/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
- will be ssizetype. */
+/* Helper function for split_constant_offset. Expresses OP0 CODE OP1
+ (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
+ constant of type ssizetype, and returns true. If we cannot do this
+ with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
+ is returned. */
-static void
-split_constant_offset (tree exp, tree *var, tree *off)
+static bool
+split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
+ tree *var, tree *off)
{
- tree type = TREE_TYPE (exp), otype;
tree var0, var1;
tree off0, off1;
- enum tree_code code;
+ enum tree_code ocode = code;
- *var = exp;
- STRIP_NOPS (exp);
- otype = TREE_TYPE (exp);
- code = TREE_CODE (exp);
+ *var = NULL_TREE;
+ *off = NULL_TREE;
switch (code)
{
case INTEGER_CST:
*var = build_int_cst (type, 0);
- *off = fold_convert (ssizetype, exp);
- return;
+ *off = fold_convert (ssizetype, op0);
+ return true;
case POINTER_PLUS_EXPR:
- code = PLUS_EXPR;
+ ocode = PLUS_EXPR;
/* FALLTHROUGH */
case PLUS_EXPR:
case MINUS_EXPR:
- split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
- split_constant_offset (TREE_OPERAND (exp, 1), &var1, &off1);
- *var = fold_convert (type, fold_build2 (TREE_CODE (exp), otype,
- var0, var1));
- *off = size_binop (code, off0, off1);
- return;
+ split_constant_offset (op0, &var0, &off0);
+ split_constant_offset (op1, &var1, &off1);
+ *var = fold_build2 (code, type, var0, var1);
+ *off = size_binop (ocode, off0, off1);
+ return true;
case MULT_EXPR:
- off1 = TREE_OPERAND (exp, 1);
- if (TREE_CODE (off1) != INTEGER_CST)
- break;
+ if (TREE_CODE (op1) != INTEGER_CST)
+ return false;
- split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
- *var = fold_convert (type, fold_build2 (MULT_EXPR, otype,
- var0, off1));
- *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, off1));
- return;
+ split_constant_offset (op0, &var0, &off0);
+ *var = fold_build2 (MULT_EXPR, type, var0, op1);
+ *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
+ return true;
case ADDR_EXPR:
{
- tree op, base, poffset;
+ tree base, poffset;
HOST_WIDE_INT pbitsize, pbitpos;
enum machine_mode pmode;
int punsignedp, pvolatilep;
- op = TREE_OPERAND (exp, 0);
- if (!handled_component_p (op))
- break;
+ op0 = TREE_OPERAND (op0, 0);
+ if (!handled_component_p (op0))
+ return false;
- base = get_inner_reference (op, &pbitsize, &pbitpos, &poffset,
+ base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
&pmode, &punsignedp, &pvolatilep, false);
if (pbitpos % BITS_PER_UNIT != 0)
- break;
+ return false;
base = build_fold_addr_expr (base);
off0 = ssize_int (pbitpos / BITS_PER_UNIT);
{
split_constant_offset (poffset, &poffset, &off1);
off0 = size_binop (PLUS_EXPR, off0, off1);
- base = fold_build2 (PLUS_EXPR, TREE_TYPE (base),
- base,
- fold_convert (TREE_TYPE (base), poffset));
+ if (POINTER_TYPE_P (TREE_TYPE (base)))
+ base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base),
+ base, fold_convert (sizetype, poffset));
+ else
+ base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
+ fold_convert (TREE_TYPE (base), poffset));
}
- *var = fold_convert (type, base);
+ var0 = fold_convert (type, base);
+
+ /* If variable length types are involved, punt, otherwise casts
+ might be converted into ARRAY_REFs in gimplify_conversion.
+ To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
+ possibly no longer appears in current GIMPLE, might resurface.
+ This perhaps could run
+ if (CONVERT_EXPR_P (var0))
+ {
+ gimplify_conversion (&var0);
+ // Attempt to fill in any within var0 found ARRAY_REF's
+ // element size from corresponding op embedded ARRAY_REF,
+ // if unsuccessful, just punt.
+ } */
+ while (POINTER_TYPE_P (type))
+ type = TREE_TYPE (type);
+ if (int_size_in_bytes (type) < 0)
+ return false;
+
+ *var = var0;
*off = off0;
- return;
+ return true;
+ }
+
+ case SSA_NAME:
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (op0);
+ enum tree_code subcode;
+
+ if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
+ return false;
+
+ var0 = gimple_assign_rhs1 (def_stmt);
+ subcode = gimple_assign_rhs_code (def_stmt);
+ var1 = gimple_assign_rhs2 (def_stmt);
+
+ return split_constant_offset_1 (type, var0, subcode, var1, var, off);
}
default:
- break;
+ return false;
}
+}
+
+/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
+ will be ssizetype. */
+
+void
+split_constant_offset (tree exp, tree *var, tree *off)
+{
+ tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
+ enum tree_code code;
+ *var = exp;
*off = ssize_int (0);
+ STRIP_NOPS (exp);
+
+ if (automatically_generated_chrec_p (exp))
+ return;
+
+ otype = TREE_TYPE (exp);
+ code = TREE_CODE (exp);
+ extract_ops_from_tree (exp, &code, &op0, &op1);
+ if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
+ {
+ *var = fold_convert (type, e);
+ *off = o;
+ }
}
/* Returns the address ADDR of an object in a canonical shape (without nop
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)
{
- tree stmt = DR_STMT (dr);
+ gimple stmt = DR_STMT (dr);
struct loop *loop = loop_containing_stmt (stmt);
tree ref = DR_REF (dr);
HOST_WIDE_INT pbitsize, pbitpos;
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
static void
dr_analyze_indices (struct data_reference *dr, struct loop *nest)
{
- tree stmt = DR_STMT (dr);
+ 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;
-
+ 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 = resolve_mixers (nest, 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);
- access_fn = resolve_mixers (nest, access_fn);
+ access_fn = instantiate_scev (before_loop, loop, access_fn);
base = initial_condition (access_fn);
split_constant_offset (base, &base, &off);
access_fn = chrec_replace_initial_condition (access_fn,
static void
dr_analyze_alias (struct data_reference *dr)
{
- tree 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;
- if (smt && var_can_have_subvars (smt))
- DR_SUBVARS (dr) = get_subvars_for_var (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. */
/* Frees data reference DR. */
-static void
+void
free_data_ref (data_reference_p dr)
{
- BITMAP_FREE (DR_VOPS (dr));
VEC_free (tree, heap, DR_ACCESS_FNS (dr));
free (dr);
}
loop nest in that the reference should be analyzed. */
struct data_reference *
-create_data_ref (struct loop *nest, tree memref, tree stmt, bool is_read)
+create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read)
{
struct data_reference *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");
}
&& affine_function_constant_p (fn));
}
+/* Returns a signed integer type with the largest precision from TA
+ and TB. */
+
+static tree
+signed_type_for_types (tree ta, tree tb)
+{
+ if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
+ return signed_type_for (ta);
+ else
+ return signed_type_for (tb);
+}
+
/* Applies operation OP on affine functions FNA and FNB, and returns the
result. */
ret = VEC_alloc (tree, heap, m);
for (i = 0; i < n; i++)
- VEC_quick_push (tree, ret,
- fold_build2 (op, integer_type_node,
- VEC_index (tree, fna, i),
- VEC_index (tree, fnb, i)));
+ {
+ tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)),
+ TREE_TYPE (VEC_index (tree, fnb, i)));
+
+ VEC_quick_push (tree, ret,
+ fold_build2 (op, type,
+ VEC_index (tree, fna, i),
+ VEC_index (tree, fnb, i)));
+ }
for (; VEC_iterate (tree, fna, i, coef); i++)
VEC_quick_push (tree, ret,
- fold_build2 (op, integer_type_node,
+ fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
coef, integer_zero_node));
for (; VEC_iterate (tree, fnb, i, coef); i++)
VEC_quick_push (tree, ret,
- fold_build2 (op, integer_type_node,
+ fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
integer_zero_node, coef));
return ret;
/* Returns true if the address of OBJ is invariant in LOOP. */
static bool
-object_address_invariant_in_loop_p (struct loop *loop, tree obj)
+object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
{
while (handled_component_p (obj))
{
/* Returns false if we can prove that data references A and B do not alias,
true otherwise. */
-static bool
-dr_may_alias_p (struct data_reference *a, struct data_reference *b)
+bool
+dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
{
- tree addr_a = DR_BASE_ADDRESS (a);
- tree addr_b = DR_BASE_ADDRESS (b);
- tree type_a, type_b;
- 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;
+ const_tree addr_a = DR_BASE_ADDRESS (a);
+ const_tree addr_b = DR_BASE_ADDRESS (b);
+ const_tree type_a, type_b;
+ const_tree decl_a = NULL_TREE, decl_b = NULL_TREE;
/* 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);
return true;
}
+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. */
DDR_B (res) = b;
DDR_LOOP_NEST (res) = NULL;
DDR_REVERSED_P (res) = false;
+ DDR_SUBSCRIPTS (res) = NULL;
+ DDR_DIR_VECTS (res) = NULL;
+ DDR_DIST_VECTS (res) = NULL;
if (a == NULL || b == NULL)
{
return res;
}
+ /* When the references are exactly the same, don't spend time doing
+ the data dependence tests, just initialize the ddr and return. */
+ if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
+ {
+ 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);
+ return res;
+ }
+
/* If the references do not access the same object, we do not know
whether they alias or not. */
if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (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;
DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
DDR_LOOP_NEST (res) = loop_nest;
DDR_INNER_LOOP (res) = 0;
- DDR_DIR_VECTS (res) = NULL;
- DDR_DIST_VECTS (res) = NULL;
+ DDR_SELF_REFERENCE (res) = false;
for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
{
{
free_conflict_function (s->conflicting_iterations_in_a);
free_conflict_function (s->conflicting_iterations_in_b);
+ free (s);
}
VEC_free (subscript_p, heap, subscripts);
}
DDR_ARE_DEPENDENT (ddr) = chrec;
free_subscripts (DDR_SUBSCRIPTS (ddr));
+ DDR_SUBSCRIPTS (ddr) = NULL;
}
/* The dependence relation DDR cannot be represented by a distance
variables, i.e., if the ZIV (Zero Index Variable) test is true. */
static inline bool
-ziv_subscript_p (tree chrec_a,
- tree chrec_b)
+ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
{
return (evolution_function_is_constant_p (chrec_a)
&& evolution_function_is_constant_p (chrec_b));
variable, i.e., if the SIV (Single Index Variable) test is true. */
static bool
-siv_subscript_p (tree chrec_a,
- tree chrec_b)
+siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
{
if ((evolution_function_is_constant_p (chrec_a)
&& evolution_function_is_univariate_p (chrec_b))
conflict_function **overlaps_b,
tree *last_conflicts)
{
- tree difference;
+ tree type, difference;
dependence_stats.num_ziv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_ziv_subscript \n");
-
- chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
- chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
- difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
+
+ type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+ chrec_a = chrec_convert (type, chrec_a, NULL);
+ chrec_b = chrec_convert (type, chrec_b, NULL);
+ difference = chrec_fold_minus (type, chrec_a, chrec_b);
switch (TREE_CODE (difference))
{
tree *last_conflicts)
{
bool value0, value1, value2;
- tree difference, tmp;
+ tree type, difference, tmp;
- chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
- chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
- difference = chrec_fold_minus
- (integer_type_node, initial_condition (chrec_b), chrec_a);
+ type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+ chrec_a = chrec_convert (type, chrec_a, NULL);
+ chrec_b = chrec_convert (type, chrec_b, NULL);
+ difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
if (!chrec_is_positive (initial_condition (difference), &value0))
{
struct loop *loop = get_chrec_loop (chrec_b);
*overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
- fold_build1 (ABS_EXPR,
- integer_type_node,
- difference),
+ tmp = fold_build2 (EXACT_DIV_EXPR, type,
+ fold_build1 (ABS_EXPR, type, difference),
CHREC_RIGHT (chrec_b));
*overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
*last_conflicts = integer_one_node;
struct loop *loop = get_chrec_loop (chrec_b);
*overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- tmp = fold_build2 (EXACT_DIV_EXPR,
- integer_type_node, difference,
+ tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
CHREC_RIGHT (chrec_b));
*overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
*last_conflicts = integer_one_node;
/* Helper recursive function for initializing the matrix A. Returns
the initial value of CHREC. */
-static int
+static tree
initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
{
gcc_assert (chrec);
- if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
- return int_cst_value (chrec);
+ switch (TREE_CODE (chrec))
+ {
+ case POLYNOMIAL_CHREC:
+ gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
+
+ A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
+ return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
+
+ case PLUS_EXPR:
+ case MULT_EXPR:
+ case MINUS_EXPR:
+ {
+ tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
+ tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
+
+ return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
+ }
+
+ case NOP_EXPR:
+ {
+ tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
+ 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;
- A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
- return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
+ default:
+ gcc_unreachable ();
+ return NULL_TREE;
+ }
}
#define FLOOR_DIV(x,y) ((x) / (y))
step_overlaps_a = step_b / gcd_steps_a_b;
step_overlaps_b = step_a / gcd_steps_a_b;
- tau2 = FLOOR_DIV (niter, step_overlaps_a);
- tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
- last_conflict = tau2;
+ if (niter > 0)
+ {
+ tau2 = FLOOR_DIV (niter, step_overlaps_a);
+ tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
+ last_conflict = tau2;
+ *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+ }
+ else
+ *last_conflicts = chrec_dont_know;
*overlaps_a = affine_fn_univar (integer_zero_node, dim,
build_int_cst (NULL_TREE,
*overlaps_b = affine_fn_univar (integer_zero_node, dim,
build_int_cst (NULL_TREE,
step_overlaps_b));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
}
else
{
unsigned nb_vars_a, nb_vars_b, dim;
HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
- HOST_WIDE_INT tau1, tau2;
lambda_matrix A, U, S;
if (eq_evolutions_p (chrec_a, chrec_b))
A = lambda_matrix_new (dim, 1);
S = lambda_matrix_new (dim, 1);
- init_a = initialize_matrix_A (A, chrec_a, 0, 1);
- init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
+ init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
+ init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
gamma = init_b - init_a;
/* Don't do all the hard work of solving the Diophantine equation
false);
niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
false);
- if (niter_a < 0 || niter_b < 0)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- goto end_analyze_subs_aa;
- }
-
niter = MIN (niter_a, niter_b);
-
step_a = int_cst_value (CHREC_RIGHT (chrec_a));
step_b = int_cst_value (CHREC_RIGHT (chrec_b));
| x0 = i0 + i1 * t,
| y0 = j0 + j1 * t. */
-
- HOST_WIDE_INT i0, j0, i1, j1;
-
- /* X0 and Y0 are the first iterations for which there is a
- dependence. X0, Y0 are two solutions of the Diophantine
- equation: chrec_a (X0) = chrec_b (Y0). */
- HOST_WIDE_INT x0, y0;
- HOST_WIDE_INT niter, niter_a, niter_b;
-
- niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
- false);
- niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
- false);
-
- if (niter_a < 0 || niter_b < 0)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- goto end_analyze_subs_aa;
- }
-
- niter = MIN (niter_a, niter_b);
+ HOST_WIDE_INT i0, j0, i1, j1;
i0 = U[0][0] * gamma / gcd_alpha_beta;
j0 = U[0][1] * gamma / gcd_alpha_beta;
*overlaps_a = conflict_fn_no_dependence ();
*overlaps_b = conflict_fn_no_dependence ();
*last_conflicts = integer_zero_node;
+ goto end_analyze_subs_aa;
}
- else
+ if (i1 > 0 && j1 > 0)
{
- if (i1 > 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 = MIN (niter_a, niter_b);
+
+ /* (X0, Y0) is a solution of the Diophantine equation:
+ "chrec_a (X0) = chrec_b (Y0)". */
+ HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
+ CEIL (-j0, j1));
+ HOST_WIDE_INT x0 = i1 * tau1 + i0;
+ HOST_WIDE_INT y0 = j1 * tau1 + j0;
+
+ /* (X1, Y1) is the smallest positive solution of the eq
+ "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
+ first conflict occurs. */
+ HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
+ HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
+ HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
+
+ if (niter > 0)
{
- tau1 = CEIL (-i0, i1);
- tau2 = FLOOR_DIV (niter - i0, i1);
+ HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
+ FLOOR_DIV (niter - j0, j1));
+ HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
- if (j1 > 0)
+ /* If the overlap occurs outside of the bounds of the
+ loop, there is no dependence. */
+ if (x1 >= niter || y1 >= niter)
{
- int last_conflict, min_multiple;
- tau1 = MAX (tau1, CEIL (-j0, j1));
- tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
-
- x0 = i1 * tau1 + i0;
- y0 = j1 * tau1 + j0;
-
- /* At this point (x0, y0) is one of the
- solutions to the Diophantine equation. The
- next step has to compute the smallest
- positive solution: the first conflicts. */
- min_multiple = MIN (x0 / i1, y0 / j1);
- x0 -= i1 * min_multiple;
- y0 -= j1 * min_multiple;
-
- tau1 = (x0 - i0)/i1;
- last_conflict = tau2 - tau1;
-
- /* If the overlap occurs outside of the bounds of the
- loop, there is no dependence. */
- if (x0 > niter || y0 > niter)
- {
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- }
- else
- {
- *overlaps_a
- = conflict_fn (1,
- affine_fn_univar (build_int_cst (NULL_TREE, x0),
- 1,
- build_int_cst (NULL_TREE, i1)));
- *overlaps_b
- = conflict_fn (1,
- affine_fn_univar (build_int_cst (NULL_TREE, y0),
- 1,
- build_int_cst (NULL_TREE, j1)));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
- }
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ goto end_analyze_subs_aa;
}
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 = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- }
+ *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
}
-
else
- {
- /* 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 = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- }
+ *last_conflicts = chrec_dont_know;
+
+ *overlaps_a
+ = conflict_fn (1,
+ affine_fn_univar (build_int_cst (NULL_TREE, x1),
+ 1,
+ build_int_cst (NULL_TREE, i1)));
+ *overlaps_b
+ = conflict_fn (1,
+ affine_fn_univar (build_int_cst (NULL_TREE, y1),
+ 1,
+ build_int_cst (NULL_TREE, j1)));
+ }
+ else
+ {
+ /* FIXME: For the moment, the upper bound of the
+ iteration domain for i and j is not checked. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
}
}
else
*last_conflicts = chrec_dont_know;
}
}
-
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
type = chrec_type (*chrec_a);
left_a = CHREC_LEFT (*chrec_a);
- left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
+ left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
diff = chrec_fold_minus (type, left_a, left_b);
if (!evolution_function_is_constant_p (diff))
*chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
diff, CHREC_RIGHT (*chrec_a));
- right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
+ right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
*chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
build_int_cst (type, 0),
right_b);
tree chrec_b,
conflict_function **overlaps_a,
conflict_function **overlaps_b,
- tree *last_conflicts)
+ tree *last_conflicts,
+ int loop_nest_num)
{
dependence_stats.num_siv++;
fprintf (dump_file, "(analyze_siv_subscript \n");
if (evolution_function_is_constant_p (chrec_a)
- && evolution_function_is_affine_p (chrec_b))
+ && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b, last_conflicts);
- else if (evolution_function_is_affine_p (chrec_a)
+ else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
&& evolution_function_is_constant_p (chrec_b))
analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
overlaps_b, overlaps_a, last_conflicts);
- else if (evolution_function_is_affine_p (chrec_a)
- && evolution_function_is_affine_p (chrec_b))
+ else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
+ && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
{
if (!chrec_contains_symbols (chrec_a)
&& !chrec_contains_symbols (chrec_b))
of CHREC does not divide CST, false otherwise. */
static bool
-gcd_of_steps_may_divide_p (tree chrec, tree cst)
+gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
{
HOST_WIDE_INT cd = 0, val;
tree step;
variables. In the MIV case we have to solve a Diophantine
equation with 2*n variables (if the subscript uses n IVs).
*/
- tree difference;
+ tree type, difference;
+
dependence_stats.num_miv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_miv_subscript \n");
- chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
- chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
- difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
+ type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+ chrec_a = chrec_convert (type, chrec_a, NULL);
+ chrec_b = chrec_convert (type, chrec_b, NULL);
+ difference = chrec_fold_minus (type, chrec_a, chrec_b);
if (eq_evolutions_p (chrec_a, chrec_b))
{
else if (siv_subscript_p (chrec_a, chrec_b))
analyze_siv_subscript (chrec_a, chrec_b,
overlap_iterations_a, overlap_iterations_b,
- last_conflicts);
+ last_conflicts, lnn);
else
analyze_miv_subscript (chrec_a, chrec_b,
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++)
- if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
- DR_ACCESS_FN (DDR_B (ddr), i)))
- return false;
-
- return true;
-}
-
/* Return true when the DDR contains only constant access functions. */
static bool
-constant_access_functions (struct data_dependence_relation *ddr)
+constant_access_functions (const struct data_dependence_relation *ddr)
{
unsigned i;
return true;
}
-
/* Helper function for the case where DDR_A and DDR_B are the same
- multivariate access function. */
+ multivariate access function with a constant step. For an example
+ see pr34635-1.c. */
static void
add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
return;
}
- add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
+ access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
+
+ if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
+ add_multivariate_self_dist (ddr, access_fun);
+ else
+ /* The evolution step is not constant: it varies in
+ the outer loop, so this cannot be represented by a
+ distance vector. For example in pr34635.c the
+ evolution is {0, +, {0, +, 4}_1}_2. */
+ DDR_AFFINE_P (ddr) = false;
+
return;
}
lambda_vector dist_v;
if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return true;
+ return false;
if (same_access_functions (ddr))
{
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),
- loop_nest);
+ if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ loop_nest))
+ return false;
compute_subscript_distance (ddr);
- build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- save_v, &init_b, &index_carry);
+ if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ save_v, &init_b, &index_carry))
+ return false;
save_dist_v (ddr, save_v);
DDR_REVERSED_P (ddr) = true;
{
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);
if (DDR_NB_LOOPS (ddr) > 1)
{
lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- loop_nest);
+ if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
+ DDR_A (ddr), loop_nest))
+ return false;
compute_subscript_distance (ddr);
- build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- opposite_v, &init_b, &index_carry);
+ if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+ opposite_v, &init_b,
+ &index_carry))
+ return false;
+ save_dist_v (ddr, save_v);
add_outer_distances (ddr, dist_v, index_carry);
add_outer_distances (ddr, opposite_v, index_carry);
}
+ else
+ save_dist_v (ddr, save_v);
}
}
else
else
{
+ 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));
+
SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
SUB_LAST_CONFLICT (subscript) = last_conflicts;
constant with respect to LOOP_NEST. */
static bool
-access_functions_are_affine_or_constant_p (struct data_reference *a,
- struct loop *loop_nest)
+access_functions_are_affine_or_constant_p (const struct data_reference *a,
+ const struct loop *loop_nest)
{
unsigned int i;
VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
omega_pb pb, bool *maybe_dependent)
{
int eq;
- tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE);
- tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE);
- tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b);
+ tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
+ TREE_TYPE (access_fun_b));
+ 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);
/* 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 (integer_type_node, fun_b,
- integer_minus_one_node);
+ fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
eq = omega_add_zero_eq (pb, omega_black);
if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
{
fprintf (dump_file, "(compute_affine_dependence\n");
fprintf (dump_file, " (stmt_a = \n");
- print_generic_expr (dump_file, DR_STMT (dra), 0);
+ print_gimple_stmt (dump_file, DR_STMT (dra), 0, 0);
fprintf (dump_file, ")\n (stmt_b = \n");
- print_generic_expr (dump_file, DR_STMT (drb), 0);
+ print_gimple_stmt (dump_file, DR_STMT (drb), 0, 0);
fprintf (dump_file, ")\n");
}
/* Analyze only when the dependence relation is not yet known. */
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
+ && !DDR_SELF_REFERENCE (ddr))
{
dependence_stats.num_dependence_tests++;
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));
+ = conflict_fn (1, affine_fn_cst (integer_zero_node));
SUB_CONFLICTS_IN_B (subscript)
- = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ = conflict_fn (1, affine_fn_cst (integer_zero_node));
SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
}
{
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)
true if STMT clobbers memory, false otherwise. */
bool
-get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
+get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
{
bool clobbers_memory = false;
data_ref_loc *ref;
- tree *op0, *op1, call;
+ tree *op0, *op1;
+ enum gimple_code stmt_code = gimple_code (stmt);
*references = NULL;
/* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
Calls have side-effects, except those to const or pure
functions. */
- call = get_call_expr_in (stmt);
- if ((call
- && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
- || (TREE_CODE (stmt) == ASM_EXPR
- && ASM_VOLATILE_P (stmt)))
+ if ((stmt_code == GIMPLE_CALL
+ && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
+ || (stmt_code == GIMPLE_ASM
+ && 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 (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ if (stmt_code == GIMPLE_ASSIGN)
{
- op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
- op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
+ tree base;
+ op0 = gimple_assign_lhs_ptr (stmt);
+ op1 = gimple_assign_rhs1_ptr (stmt);
if (DECL_P (*op1)
- || REFERENCE_CLASS_P (*op1))
+ || (REFERENCE_CLASS_P (*op1)
+ && (base = get_base_address (*op1))
+ && TREE_CODE (base) != SSA_NAME))
{
ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
ref->pos = op1;
}
if (DECL_P (*op0)
- || REFERENCE_CLASS_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;
}
}
-
- if (call)
+ else if (stmt_code == GIMPLE_CALL)
{
- unsigned i, n = call_expr_nargs (call);
+ unsigned i, n = gimple_call_num_args (stmt);
for (i = 0; i < n; i++)
{
- op0 = &CALL_EXPR_ARG (call, i);
+ op0 = gimple_call_arg_ptr (stmt, i);
if (DECL_P (*op0)
- || REFERENCE_CLASS_P (*op0))
+ || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
{
ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
ref->pos = op0;
/* 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 that the references should be analyzed. */
+ loop of the loop nest in which the references should be analyzed. */
-static bool
-find_data_references_in_stmt (struct loop *nest, tree stmt,
+bool
+find_data_references_in_stmt (struct loop *nest, gimple stmt,
VEC (data_reference_p, heap) **datarefs)
{
unsigned i;
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;
}
-/* 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.
-
- TODO: This function should be made smarter so that it can handle address
- arithmetic as if they were array accesses, etc. */
+/* 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. */
-static tree
-find_data_references_in_loop (struct loop *loop,
+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.
+
+ TODO: This function should be made smarter so that it can handle address
+ arithmetic as if they were array accesses, etc. */
+
+tree
+find_data_references_in_loop (struct loop *loop,
VEC (data_reference_p, heap) **datarefs)
{
basic_block bb, *bbs;
unsigned int i;
- block_stmt_iterator bsi;
bbs = get_loop_body_in_dom_order (loop);
{
bb = bbs[i];
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- {
- tree stmt = bsi_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 true;
}
-/* Given a loop nest LOOP, the following vectors are returned:
+/* Returns true when the data dependences have been computed, false otherwise.
+ 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.
Compute read-read and self relations if
COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
-void
+bool
compute_data_dependences_for_loop (struct loop *loop,
bool compute_self_and_read_read_dependences,
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));
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,
dependence_stats.num_miv_independent);
fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
dependence_stats.num_miv_unimplemented);
- }
+ }
+
+ 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
{
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++;
if (ddr == NULL)
return;
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
+ if (DDR_SUBSCRIPTS (ddr))
free_subscripts (DDR_SUBSCRIPTS (ddr));
+ if (DDR_DIST_VECTS (ddr))
+ VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
+ if (DDR_DIR_VECTS (ddr))
+ VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
free (ddr);
}
\f
-/* Returns the index of STMT in RDG. */
+/* Dump vertex I in RDG to FILE. */
-static int
-find_vertex_for_stmt (struct graph *rdg, tree stmt)
+void
+dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
+{
+ struct vertex *v = &(rdg->vertices[i]);
+ struct graph_edge *e;
+
+ fprintf (file, "(vertex %d: (%s%s) (in:", i,
+ RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
+ RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
+
+ if (v->pred)
+ for (e = v->pred; e; e = e->pred_next)
+ fprintf (file, " %d", e->src);
+
+ fprintf (file, ") (out:");
+
+ if (v->succ)
+ for (e = v->succ; e; e = e->succ_next)
+ fprintf (file, " %d", e->dest);
+
+ fprintf (file, ") \n");
+ print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
+ fprintf (file, ")\n");
+}
+
+/* Call dump_rdg_vertex on stderr. */
+
+void
+debug_rdg_vertex (struct graph *rdg, int i)
+{
+ dump_rdg_vertex (stderr, rdg, i);
+}
+
+/* Dump component C of RDG to FILE. If DUMPED is non-null, set the
+ dumped vertices to that bitmap. */
+
+void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
{
int i;
+ fprintf (file, "(%d\n", c);
+
for (i = 0; i < rdg->n_vertices; i++)
- if (RDGV_STMT (&(rdg->vertices[i])) == stmt)
- return i;
+ if (rdg->vertices[i].component == c)
+ {
+ if (dumped)
+ bitmap_set_bit (dumped, i);
- gcc_unreachable ();
- return 0;
+ dump_rdg_vertex (file, rdg, i);
+ }
+
+ fprintf (file, ")\n");
}
-/* Creates an edge in RDG for each distance vector from DDR. */
+/* Call dump_rdg_vertex on stderr. */
+
+void
+debug_rdg_component (struct graph *rdg, int c)
+{
+ dump_rdg_component (stderr, rdg, c, NULL);
+}
+
+/* Dump the reduced dependence graph RDG to FILE. */
+
+void
+dump_rdg (FILE *file, struct graph *rdg)
+{
+ int i;
+ bitmap dumped = BITMAP_ALLOC (NULL);
+
+ fprintf (file, "(rdg\n");
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ if (!bitmap_bit_p (dumped, i))
+ dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
+
+ fprintf (file, ")\n");
+ BITMAP_FREE (dumped);
+}
+
+/* Call dump_rdg on stderr. */
+
+void
+debug_rdg (struct graph *rdg)
+{
+ dump_rdg (stderr, rdg);
+}
static void
-create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
+dot_rdg_1 (FILE *file, struct graph *rdg)
{
- int va, vb;
- data_reference_p dra;
- data_reference_p drb;
- struct graph_edge *e;
+ int i;
+
+ fprintf (file, "digraph RDG {\n");
- if (DDR_REVERSED_P (ddr))
+ for (i = 0; i < rdg->n_vertices; i++)
{
- dra = DDR_B (ddr);
- drb = DDR_A (ddr);
+ struct vertex *v = &(rdg->vertices[i]);
+ struct graph_edge *e;
+
+ /* Highlight reads from memory. */
+ if (RDG_MEM_READS_STMT (rdg, i))
+ fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
+
+ /* Highlight stores to memory. */
+ if (RDG_MEM_WRITE_STMT (rdg, i))
+ fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
+
+ if (v->succ)
+ for (e = v->succ; e; e = e->succ_next)
+ switch (RDGE_TYPE (e))
+ {
+ case input_dd:
+ fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
+ break;
+
+ case output_dd:
+ fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
+ break;
+
+ case flow_dd:
+ /* These are the most common dependences: don't print these. */
+ fprintf (file, "%d -> %d \n", i, e->dest);
+ break;
+
+ case anti_dd:
+ fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
}
- else
+
+ fprintf (file, "}\n\n");
+}
+
+/* Display SCOP using dotty. */
+
+void
+dot_rdg (struct graph *rdg)
+{
+ FILE *file = fopen ("/tmp/rdg.dot", "w");
+ gcc_assert (file != NULL);
+
+ dot_rdg_1 (file, rdg);
+ fclose (file);
+
+ system ("dotty /tmp/rdg.dot");
+}
+
+
+/* This structure is used for recording the mapping statement index in
+ the RDG. */
+
+struct GTY(()) rdg_vertex_info
+{
+ gimple stmt;
+ int index;
+};
+
+/* Returns the index of STMT in RDG. */
+
+int
+rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
+{
+ struct rdg_vertex_info rvi, *slot;
+
+ rvi.stmt = stmt;
+ slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
+
+ if (!slot)
+ return -1;
+
+ return slot->index;
+}
+
+/* Creates an edge in RDG for each distance vector from DDR. The
+ order that we keep track of in the RDG is the order in which
+ statements have to be executed. */
+
+static void
+create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
+{
+ struct graph_edge *e;
+ int va, vb;
+ data_reference_p dra = DDR_A (ddr);
+ data_reference_p drb = DDR_B (ddr);
+ unsigned level = ddr_dependence_level (ddr);
+
+ /* For non scalar dependences, when the dependence is REVERSED,
+ statement B has to be executed before statement A. */
+ if (level > 0
+ && !DDR_REVERSED_P (ddr))
{
- dra = DDR_A (ddr);
- drb = DDR_B (ddr);
+ data_reference_p tmp = dra;
+ dra = drb;
+ drb = tmp;
}
- va = find_vertex_for_stmt (rdg, DR_STMT (dra));
- vb = find_vertex_for_stmt (rdg, DR_STMT (drb));
+ va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
+ vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
+
+ if (va < 0 || vb < 0)
+ return;
e = add_edge (rdg, va, vb);
e->data = XNEW (struct rdg_edge);
+ RDGE_LEVEL (e) = level;
+ RDGE_RELATION (e) = ddr;
+
/* Determines the type of the data dependence. */
if (DR_IS_READ (dra) && DR_IS_READ (drb))
RDGE_TYPE (e) = input_dd;
FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
{
- int use = find_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
- struct graph_edge *e = add_edge (rdg, idef, use);
+ struct graph_edge *e;
+ int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
+
+ if (use < 0)
+ continue;
+ e = add_edge (rdg, idef, use);
e->data = XNEW (struct rdg_edge);
RDGE_TYPE (e) = flow_dd;
+ RDGE_RELATION (e) = NULL;
}
}
create_rdg_edge_for_ddr (rdg, ddr);
for (i = 0; i < rdg->n_vertices; i++)
- FOR_EACH_PHI_OR_STMT_DEF (def_p, RDGV_STMT (&(rdg->vertices[i])),
- iter, SSA_OP_ALL_DEFS)
+ FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
+ iter, SSA_OP_DEF)
create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
}
/* Build the vertices of the reduced dependence graph RDG. */
-static void
-create_rdg_vertices (struct graph *rdg, VEC (tree, heap) *stmts)
+void
+create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
{
- int i;
- tree s;
+ int i, j;
+ gimple stmt;
- for (i = 0; VEC_iterate (tree, stmts, i, s); i++)
+ for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++)
{
+ VEC (data_ref_loc, heap) *references;
+ data_ref_loc *ref;
struct vertex *v = &(rdg->vertices[i]);
+ struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
+ struct rdg_vertex_info **slot;
+
+ rvi->stmt = stmt;
+ rvi->index = i;
+ slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
+
+ if (!*slot)
+ *slot = rvi;
+ else
+ free (rvi);
v->data = XNEW (struct rdg_vertex);
- RDGV_STMT (v) = s;
+ RDG_STMT (rdg, i) = stmt;
+
+ RDG_MEM_WRITE_STMT (rdg, i) = false;
+ RDG_MEM_READS_STMT (rdg, i) = false;
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ continue;
+
+ get_references_in_stmt (stmt, &references);
+ for (j = 0; VEC_iterate (data_ref_loc, references, j, ref); j++)
+ if (!ref->is_read)
+ RDG_MEM_WRITE_STMT (rdg, i) = true;
+ else
+ RDG_MEM_READS_STMT (rdg, i) = true;
+
+ VEC_free (data_ref_loc, heap, references);
}
}
-/* Initialize STMTS with all the statements and PHI nodes of LOOP. */
+/* Initialize STMTS with all the statements of LOOP. When
+ INCLUDE_PHIS is true, include also the PHI nodes. The order in
+ which we discover statements is important as
+ generate_loops_for_partition is using the same traversal for
+ identifying statements. */
static void
-stmts_from_loop (struct loop *loop, VEC (tree, heap) **stmts)
+stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
{
unsigned int i;
basic_block *bbs = get_loop_body_in_dom_order (loop);
for (i = 0; i < loop->num_nodes; i++)
{
- tree phi;
basic_block bb = bbs[i];
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
+ gimple stmt;
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- VEC_safe_push (tree, heap, *stmts, phi);
+ for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- VEC_safe_push (tree, heap, *stmts, bsi_stmt (bsi));
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ {
+ stmt = gsi_stmt (bsi);
+ if (gimple_code (stmt) != GIMPLE_LABEL)
+ VEC_safe_push (gimple, heap, *stmts, stmt);
+ }
}
free (bbs);
return true;
}
-/* Build a Reduced Dependence Graph with one vertex per statement of the
- loop nest and one edge per data dependence or scalar dependence. */
+/* Computes a hash function for element ELT. */
+
+static hashval_t
+hash_stmt_vertex_info (const void *elt)
+{
+ const struct rdg_vertex_info *const rvi =
+ (const struct rdg_vertex_info *) elt;
+ gimple stmt = rvi->stmt;
+
+ return htab_hash_pointer (stmt);
+}
+
+/* Compares database elements E1 and E2. */
+
+static int
+eq_stmt_vertex_info (const void *e1, const void *e2)
+{
+ const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
+ const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
+
+ return elt1->stmt == elt2->stmt;
+}
+
+/* Free the element E. */
+
+static void
+hash_stmt_vertex_del (void *e)
+{
+ free (e);
+}
+
+/* Build the Reduced Dependence Graph (RDG) with one vertex per
+ statement of the loop nest, and one edge per data dependence or
+ scalar dependence. */
+
+struct graph *
+build_empty_rdg (int n_stmts)
+{
+ int nb_data_refs = 10;
+ struct graph *rdg = new_graph (n_stmts);
+
+ rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
+ eq_stmt_vertex_info, hash_stmt_vertex_del);
+ return rdg;
+}
+
+/* Build the Reduced Dependence Graph (RDG) with one vertex per
+ statement of the loop nest, and one edge per data dependence or
+ scalar dependence. */
struct graph *
build_rdg (struct loop *loop)
struct graph *rdg = NULL;
VEC (ddr_p, heap) *dependence_relations;
VEC (data_reference_p, heap) *datarefs;
- VEC (tree, heap) *stmts = VEC_alloc (tree, heap, 10);
+ 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);
false,
&datarefs,
&dependence_relations);
-
+
if (!known_dependences_p (dependence_relations))
- goto end_rdg;
+ {
+ free_dependence_relations (dependence_relations);
+ free_data_refs (datarefs);
+ VEC_free (gimple, heap, stmts);
+
+ return rdg;
+ }
stmts_from_loop (loop, &stmts);
- rdg = new_graph (VEC_length (tree, stmts));
+ rdg = build_empty_rdg (VEC_length (gimple, stmts));
+
+ 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);
- end_rdg:
- free_dependence_relations (dependence_relations);
- free_data_refs (datarefs);
- VEC_free (tree, heap, stmts);
-
+ VEC_free (gimple, heap, stmts);
return rdg;
}
+
+/* Free the reduced dependence graph RDG. */
+
+void
+free_rdg (struct graph *rdg)
+{
+ int i;
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ free (rdg->vertices[i].data);
+
+ htab_delete (rdg->indices);
+ free_graph (rdg);
+}
+
+/* Initialize STMTS with all the statements of LOOP that contain a
+ store to memory. */
+
+void
+stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
+{
+ unsigned int i;
+ basic_block *bbs = get_loop_body_in_dom_order (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = bbs[i];
+ gimple_stmt_iterator bsi;
+
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ if (gimple_vdef (gsi_stmt (bsi)))
+ VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
+ }
+
+ free (bbs);
+}
+
+/* For a data reference REF, return the declaration of its base
+ address or NULL_TREE if the base is not determined. */
+
+static inline tree
+ref_base_address (gimple stmt, data_ref_loc *ref)
+{
+ tree base = NULL_TREE;
+ tree base_address;
+ struct data_reference *dr = XCNEW (struct data_reference);
+
+ DR_STMT (dr) = stmt;
+ DR_REF (dr) = *ref->pos;
+ dr_analyze_innermost (dr);
+ base_address = DR_BASE_ADDRESS (dr);
+
+ if (!base_address)
+ goto end;
+
+ switch (TREE_CODE (base_address))
+ {
+ case ADDR_EXPR:
+ base = TREE_OPERAND (base_address, 0);
+ break;
+
+ default:
+ base = base_address;
+ break;
+ }
+
+ end:
+ free_data_ref (dr);
+ return base;
+}
+
+/* Determines whether the statement from vertex V of the RDG has a
+ definition used outside the loop that contains this statement. */
+
+bool
+rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
+{
+ gimple stmt = RDG_STMT (rdg, v);
+ struct loop *loop = loop_containing_stmt (stmt);
+ use_operand_p imm_use_p;
+ imm_use_iterator iterator;
+ ssa_op_iter it;
+ def_operand_p def_p;
+
+ if (!loop)
+ return true;
+
+ FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
+ {
+ FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
+ {
+ if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/* Determines whether statements S1 and S2 access to similar memory
+ locations. Two memory accesses are considered similar when they
+ have the same base address declaration, i.e. when their
+ ref_base_address is the same. */
+
+bool
+have_similar_memory_accesses (gimple s1, gimple s2)
+{
+ bool res = false;
+ unsigned i, j;
+ VEC (data_ref_loc, heap) *refs1, *refs2;
+ data_ref_loc *ref1, *ref2;
+
+ get_references_in_stmt (s1, &refs1);
+ get_references_in_stmt (s2, &refs2);
+
+ for (i = 0; VEC_iterate (data_ref_loc, refs1, i, ref1); i++)
+ {
+ tree base1 = ref_base_address (s1, ref1);
+
+ if (base1)
+ for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++)
+ if (base1 == ref_base_address (s2, ref2))
+ {
+ res = true;
+ goto end;
+ }
+ }
+
+ end:
+ VEC_free (data_ref_loc, heap, refs1);
+ VEC_free (data_ref_loc, heap, refs2);
+ return res;
+}
+
+/* Helper function for the hashtab. */
+
+static int
+have_similar_memory_accesses_1 (const void *s1, const void *s2)
+{
+ return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1),
+ CONST_CAST_GIMPLE ((const_gimple) s2));
+}
+
+/* Helper function for the hashtab. */
+
+static hashval_t
+ref_base_address_1 (const void *s)
+{
+ gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s);
+ unsigned i;
+ VEC (data_ref_loc, heap) *refs;
+ data_ref_loc *ref;
+ hashval_t res = 0;
+
+ get_references_in_stmt (stmt, &refs);
+
+ for (i = 0; VEC_iterate (data_ref_loc, refs, i, ref); i++)
+ if (!ref->is_read)
+ {
+ res = htab_hash_pointer (ref_base_address (stmt, ref));
+ break;
+ }
+
+ VEC_free (data_ref_loc, heap, refs);
+ return res;
+}
+
+/* Try to remove duplicated write data references from STMTS. */
+
+void
+remove_similar_memory_refs (VEC (gimple, heap) **stmts)
+{
+ unsigned i;
+ gimple stmt;
+ htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1,
+ have_similar_memory_accesses_1, NULL);
+
+ for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); )
+ {
+ void **slot;
+
+ slot = htab_find_slot (seen, stmt, INSERT);
+
+ if (*slot)
+ VEC_ordered_remove (gimple, *stmts, i);
+ else
+ {
+ *slot = (void *) stmt;
+ i++;
+ }
+ }
+
+ htab_delete (seen);
+}
+
+/* Returns the index of PARAMETER in the parameters vector of the
+ ACCESS_MATRIX. If PARAMETER does not exist return -1. */
+
+int
+access_matrix_get_index_for_parameter (tree parameter,
+ struct access_matrix *access_matrix)
+{
+ int i;
+ VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
+ tree lambda_parameter;
+
+ for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++)
+ if (lambda_parameter == parameter)
+ return i + AM_NB_INDUCTION_VARS (access_matrix);
+
+ return -1;
+}