/* Data references and dependences detectors.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
- Free Software Foundation, Inc.
+ Copyright (C) 2003-2016 Free Software Foundation, Inc.
Contributed by Sebastian Pop <pop@cri.ensmp.fr>
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
+#include "backend.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
#include "gimple-pretty-print.h"
-#include "tree-flow.h"
+#include "alias.h"
+#include "fold-const.h"
+#include "expr.h"
+#include "gimple-iterator.h"
+#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop.h"
+#include "tree-ssa.h"
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
-#include "tree-pass.h"
-#include "langhooks.h"
+#include "dumpfile.h"
#include "tree-affine.h"
#include "params.h"
/* Dump into FILE all the data references from DATAREFS. */
static void
-dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
+dump_data_references (FILE *file, vec<data_reference_p> datarefs)
{
unsigned int i;
struct data_reference *dr;
- FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
+ FOR_EACH_VEC_ELT (datarefs, i, dr)
dump_data_reference (file, dr);
}
+/* Unified dump into FILE all the data references from DATAREFS. */
+
+DEBUG_FUNCTION void
+debug (vec<data_reference_p> &ref)
+{
+ dump_data_references (stderr, ref);
+}
+
+DEBUG_FUNCTION void
+debug (vec<data_reference_p> *ptr)
+{
+ if (ptr)
+ debug (*ptr);
+ else
+ fprintf (stderr, "<nil>\n");
+}
+
+
/* Dump into STDERR all the data references from DATAREFS. */
DEBUG_FUNCTION void
-debug_data_references (VEC (data_reference_p, heap) *datarefs)
+debug_data_references (vec<data_reference_p> datarefs)
{
dump_data_references (stderr, datarefs);
}
fprintf (outf, "#)\n");
}
+/* Unified dump function for a DATA_REFERENCE structure. */
+
+DEBUG_FUNCTION void
+debug (data_reference &ref)
+{
+ dump_data_reference (stderr, &ref);
+}
+
+DEBUG_FUNCTION void
+debug (data_reference *ptr)
+{
+ if (ptr)
+ debug (*ptr);
+ else
+ fprintf (stderr, "<nil>\n");
+}
+
+
/* Dumps the affine function described by FN to the file OUTF. */
-static void
+DEBUG_FUNCTION void
dump_affine_function (FILE *outf, affine_fn fn)
{
unsigned i;
tree coef;
- print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
- for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
+ print_generic_expr (outf, fn[0], TDF_SLIM);
+ for (i = 1; fn.iterate (i, &coef); i++)
{
fprintf (outf, " + ");
print_generic_expr (outf, coef, TDF_SLIM);
/* Dumps the conflict function CF to the file OUTF. */
-static void
+DEBUG_FUNCTION void
dump_conflict_function (FILE *outf, conflict_function *cf)
{
unsigned i;
if (cf->n == NO_DEPENDENCE)
- fprintf (outf, "no dependence\n");
+ fprintf (outf, "no dependence");
else if (cf->n == NOT_KNOWN)
- fprintf (outf, "not known\n");
+ fprintf (outf, "not known");
else
{
for (i = 0; i < cf->n; i++)
{
+ if (i != 0)
+ fprintf (outf, " ");
fprintf (outf, "[");
dump_affine_function (outf, cf->fns[i]);
- fprintf (outf, "]\n");
+ fprintf (outf, "]");
}
}
}
/* Dump function for a SUBSCRIPT structure. */
-static void
+DEBUG_FUNCTION void
dump_subscript (FILE *outf, struct subscript *subscript)
{
conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
if (CF_NONTRIVIAL_P (cf))
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
- fprintf (outf, " last_conflict: ");
- print_generic_stmt (outf, last_iteration, 0);
+ fprintf (outf, "\n last_conflict: ");
+ print_generic_expr (outf, last_iteration, 0);
}
cf = SUB_CONFLICTS_IN_B (subscript);
- fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
+ fprintf (outf, "\n iterations_that_access_an_element_twice_in_B: ");
dump_conflict_function (outf, cf);
if (CF_NONTRIVIAL_P (cf))
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
- fprintf (outf, " last_conflict: ");
- print_generic_stmt (outf, last_iteration, 0);
+ fprintf (outf, "\n last_conflict: ");
+ print_generic_expr (outf, last_iteration, 0);
}
- fprintf (outf, " (Subscript distance: ");
- print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
- fprintf (outf, " )\n");
- fprintf (outf, " )\n");
+ fprintf (outf, "\n (Subscript distance: ");
+ print_generic_expr (outf, SUB_DISTANCE (subscript), 0);
+ fprintf (outf, " ))\n");
}
/* Print the classic direction vector DIRV to OUTF. */
-static void
+DEBUG_FUNCTION void
print_direction_vector (FILE *outf,
lambda_vector dirv,
int length)
/* Print a vector of direction vectors. */
-static void
-print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
+DEBUG_FUNCTION void
+print_dir_vectors (FILE *outf, vec<lambda_vector> dir_vects,
int length)
{
unsigned j;
lambda_vector v;
- FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, v)
+ FOR_EACH_VEC_ELT (dir_vects, j, v)
print_direction_vector (outf, v, length);
}
/* Print out a vector VEC of length N to OUTFILE. */
-static inline void
+DEBUG_FUNCTION void
print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
{
int i;
/* Print a vector of distance vectors. */
-static void
-print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
+DEBUG_FUNCTION void
+print_dist_vectors (FILE *outf, vec<lambda_vector> dist_vects,
int length)
{
unsigned j;
lambda_vector v;
- FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, v)
+ FOR_EACH_VEC_ELT (dist_vects, j, v)
print_lambda_vector (outf, v, length);
}
/* Dump function for a DATA_DEPENDENCE_RELATION structure. */
-static void
+DEBUG_FUNCTION void
dump_data_dependence_relation (FILE *outf,
struct data_dependence_relation *ddr)
{
fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
fprintf (outf, " loop nest: (");
- FOR_EACH_VEC_ELT (loop_p, DDR_LOOP_NEST (ddr), i, loopi)
+ FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr), i, loopi)
fprintf (outf, "%d ", loopi->num);
fprintf (outf, ")\n");
/* Dump into FILE all the dependence relations from DDRS. */
-void
+DEBUG_FUNCTION void
dump_data_dependence_relations (FILE *file,
- VEC (ddr_p, heap) *ddrs)
+ vec<ddr_p> ddrs)
{
unsigned int i;
struct data_dependence_relation *ddr;
- FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
+ FOR_EACH_VEC_ELT (ddrs, i, ddr)
dump_data_dependence_relation (file, ddr);
}
+DEBUG_FUNCTION void
+debug (vec<ddr_p> &ref)
+{
+ dump_data_dependence_relations (stderr, ref);
+}
+
+DEBUG_FUNCTION void
+debug (vec<ddr_p> *ptr)
+{
+ if (ptr)
+ debug (*ptr);
+ else
+ fprintf (stderr, "<nil>\n");
+}
+
+
/* Dump to STDERR all the dependence relations from DDRS. */
DEBUG_FUNCTION void
-debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs)
+debug_data_dependence_relations (vec<ddr_p> ddrs)
{
dump_data_dependence_relations (stderr, ddrs);
}
dependence vectors, or in other words the number of loops in the
considered nest. */
-static void
-dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
+DEBUG_FUNCTION void
+dump_dist_dir_vectors (FILE *file, vec<ddr_p> ddrs)
{
unsigned int i, j;
struct data_dependence_relation *ddr;
lambda_vector v;
- FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
+ FOR_EACH_VEC_ELT (ddrs, i, ddr)
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
{
- FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), j, v)
+ FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), j, v)
{
fprintf (file, "DISTANCE_V (");
print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
fprintf (file, ")\n");
}
- FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), j, v)
+ FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr), j, v)
{
fprintf (file, "DIRECTION_V (");
print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
/* Dumps the data dependence relations DDRS in FILE. */
-static void
-dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
+DEBUG_FUNCTION void
+dump_ddrs (FILE *file, vec<ddr_p> ddrs)
{
unsigned int i;
struct data_dependence_relation *ddr;
- FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
+ FOR_EACH_VEC_ELT (ddrs, i, ddr)
dump_data_dependence_relation (file, ddr);
fprintf (file, "\n\n");
}
DEBUG_FUNCTION void
-debug_ddrs (VEC (ddr_p, heap) *ddrs)
+debug_ddrs (vec<ddr_p> ddrs)
{
dump_ddrs (stderr, ddrs);
}
{
tree base, poffset;
HOST_WIDE_INT pbitsize, pbitpos;
- enum machine_mode pmode;
- int punsignedp, pvolatilep;
+ machine_mode pmode;
+ int punsignedp, preversep, pvolatilep;
op0 = TREE_OPERAND (op0, 0);
- base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
- &pmode, &punsignedp, &pvolatilep, false);
+ base
+ = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset, &pmode,
+ &punsignedp, &preversep, &pvolatilep, false);
if (pbitpos % BITS_PER_UNIT != 0)
return false;
case SSA_NAME:
{
- gimple def_stmt = SSA_NAME_DEF_STMT (op0);
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
+ return false;
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
enum tree_code subcode;
if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
bool
dr_analyze_innermost (struct data_reference *dr, struct loop *nest)
{
- gimple 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;
tree base, poffset;
- enum machine_mode pmode;
- int punsignedp, pvolatilep;
+ machine_mode pmode;
+ int punsignedp, preversep, 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: ");
- base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
- &pmode, &punsignedp, &pvolatilep, false);
+ base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset, &pmode,
+ &punsignedp, &preversep, &pvolatilep, false);
gcc_assert (base != NULL_TREE);
if (pbitpos % BITS_PER_UNIT != 0)
return false;
}
+ if (preversep)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "failed: reverse storage order.\n");
+ return false;
+ }
+
if (TREE_CODE (base) == MEM_REF)
{
if (!integer_zerop (TREE_OPERAND (base, 1)))
{
+ offset_int moff = mem_ref_offset (base);
+ tree mofft = wide_int_to_tree (sizetype, moff);
if (!poffset)
- {
- double_int moff = mem_ref_offset (base);
- poffset = double_int_to_tree (sizetype, moff);
- }
+ poffset = mofft;
else
- poffset = size_binop (PLUS_EXPR, poffset, TREE_OPERAND (base, 1));
+ poffset = size_binop (PLUS_EXPR, poffset, mofft);
}
base = TREE_OPERAND (base, 0);
}
static void
dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
{
- VEC (tree, heap) *access_fns = NULL;
+ vec<tree> access_fns = vNULL;
tree ref, op;
tree base, off, access_fn;
basic_block before_loop;
if (!nest)
{
DR_BASE_OBJECT (dr) = DR_REF (dr);
- DR_ACCESS_FNS (dr) = NULL;
+ DR_ACCESS_FNS (dr).create (0);
return;
}
if (TREE_CODE (ref) == REALPART_EXPR)
{
ref = TREE_OPERAND (ref, 0);
- VEC_safe_push (tree, heap, access_fns, integer_zero_node);
+ access_fns.safe_push (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);
+ access_fns.safe_push (integer_one_node);
}
/* Analyze access functions of dimensions we know to be independent. */
op = TREE_OPERAND (ref, 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);
+ access_fns.safe_push (access_fn);
}
else if (TREE_CODE (ref) == COMPONENT_REF
&& TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
fold_convert (bitsizetype, off),
bitsize_int (BITS_PER_UNIT)),
DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1)));
- VEC_safe_push (tree, heap, access_fns, off);
+ access_fns.safe_push (off);
}
else
/* If we have an unhandled component we could not translate
orig_type = TREE_TYPE (base);
STRIP_USELESS_TYPE_CONVERSION (base);
split_constant_offset (base, &base, &off);
+ STRIP_USELESS_TYPE_CONVERSION (base);
/* Fold the MEM_REF offset into the evolutions initial
value to make more bases comparable. */
if (!integer_zerop (memoff))
fold_convert (ssizetype, memoff));
memoff = build_int_cst (TREE_TYPE (memoff), 0);
}
+ /* Adjust the offset so it is a multiple of the access type
+ size and thus we separate bases that can possibly be used
+ to produce partial overlaps (which the access_fn machinery
+ cannot handle). */
+ wide_int rem;
+ if (TYPE_SIZE_UNIT (TREE_TYPE (ref))
+ && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref))) == INTEGER_CST
+ && !integer_zerop (TYPE_SIZE_UNIT (TREE_TYPE (ref))))
+ rem = wi::mod_trunc (off, TYPE_SIZE_UNIT (TREE_TYPE (ref)), SIGNED);
+ else
+ /* If we can't compute the remainder simply force the initial
+ condition to zero. */
+ rem = off;
+ off = wide_int_to_tree (ssizetype, wi::sub (off, rem));
+ memoff = wide_int_to_tree (TREE_TYPE (memoff), rem);
+ /* And finally replace the initial condition. */
access_fn = chrec_replace_initial_condition
(access_fn, fold_convert (orig_type, off));
/* ??? This is still not a suitable base object for
guaranteed.
As a band-aid, mark the access so we can special-case
it in dr_may_alias_p. */
+ tree old = ref;
ref = fold_build2_loc (EXPR_LOCATION (ref),
MEM_REF, TREE_TYPE (ref),
base, memoff);
+ MR_DEPENDENCE_CLIQUE (ref) = MR_DEPENDENCE_CLIQUE (old);
+ MR_DEPENDENCE_BASE (ref) = MR_DEPENDENCE_BASE (old);
DR_UNCONSTRAINED_BASE (dr) = true;
- VEC_safe_push (tree, heap, access_fns, access_fn);
+ access_fns.safe_push (access_fn);
}
}
else if (DECL_P (ref))
void
free_data_ref (data_reference_p dr)
{
- VEC_free (tree, heap, DR_ACCESS_FNS (dr));
+ DR_ACCESS_FNS (dr).release ();
free (dr);
}
which the data reference should be analyzed. */
struct data_reference *
-create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
+create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt,
bool is_read)
{
struct data_reference *dr;
static bool
affine_function_equal_p (affine_fn fna, affine_fn fnb)
{
- unsigned i, n = VEC_length (tree, fna);
+ unsigned i, n = fna.length ();
- if (n != VEC_length (tree, fnb))
+ if (n != fnb.length ())
return false;
for (i = 0; i < n; i++)
- if (!operand_equal_p (VEC_index (tree, fna, i),
- VEC_index (tree, fnb, i), 0))
+ if (!operand_equal_p (fna[i], fnb[i], 0))
return false;
return true;
affine_fn comm;
if (!CF_NONTRIVIAL_P (cf))
- return NULL;
+ return affine_fn ();
comm = cf->fns[0];
for (i = 1; i < cf->n; i++)
if (!affine_function_equal_p (comm, cf->fns[i]))
- return NULL;
+ return affine_fn ();
return comm;
}
static tree
affine_function_base (affine_fn fn)
{
- return VEC_index (tree, fn, 0);
+ return fn[0];
}
/* Returns true if FN is a constant. */
unsigned i;
tree coef;
- for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
+ for (i = 1; fn.iterate (i, &coef); i++)
if (!integer_zerop (coef))
return false;
affine_fn ret;
tree coef;
- if (VEC_length (tree, fnb) > VEC_length (tree, fna))
+ if (fnb.length () > fna.length ())
{
- n = VEC_length (tree, fna);
- m = VEC_length (tree, fnb);
+ n = fna.length ();
+ m = fnb.length ();
}
else
{
- n = VEC_length (tree, fnb);
- m = VEC_length (tree, fna);
+ n = fnb.length ();
+ m = fna.length ();
}
- ret = VEC_alloc (tree, heap, m);
+ ret.create (m);
for (i = 0; i < n; 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)));
+ tree type = signed_type_for_types (TREE_TYPE (fna[i]),
+ TREE_TYPE (fnb[i]));
+ ret.quick_push (fold_build2 (op, type, fna[i], fnb[i]));
}
- for (; VEC_iterate (tree, fna, i, coef); i++)
- VEC_quick_push (tree, ret,
- fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
+ for (; fna.iterate (i, &coef); i++)
+ ret.quick_push (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, signed_type_for (TREE_TYPE (coef)),
+ for (; fnb.iterate (i, &coef); i++)
+ ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
integer_zero_node, coef));
return ret;
static void
affine_fn_free (affine_fn fn)
{
- VEC_free (tree, heap, fn);
+ fn.release ();
}
/* Determine for each subscript in the data dependence relation DDR
fn_a = common_affine_function (cf_a);
fn_b = common_affine_function (cf_b);
- if (!fn_a || !fn_b)
+ if (!fn_a.exists () || !fn_b.exists ())
{
SUB_DISTANCE (subscript) = chrec_dont_know;
return;
if (!loop_nest)
{
aff_tree off1, off2;
- double_int size1, size2;
+ widest_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_scale (&off1, -1);
aff_combination_add (&off2, &off1);
if (aff_comb_cannot_overlap_p (&off2, size1, size2))
return false;
}
- /* If we had an evolution in a MEM_REF BASE_OBJECT we do not know
- the size of the base-object. So we cannot do any offset/overlap
- based analysis but have to rely on points-to information only. */
+ if ((TREE_CODE (addr_a) == MEM_REF || TREE_CODE (addr_a) == TARGET_MEM_REF)
+ && (TREE_CODE (addr_b) == MEM_REF || TREE_CODE (addr_b) == TARGET_MEM_REF)
+ && MR_DEPENDENCE_CLIQUE (addr_a) == MR_DEPENDENCE_CLIQUE (addr_b)
+ && MR_DEPENDENCE_BASE (addr_a) != MR_DEPENDENCE_BASE (addr_b))
+ return false;
+
+ /* If we had an evolution in a pointer-based MEM_REF BASE_OBJECT we
+ do not know the size of the base-object. So we cannot do any
+ offset/overlap based analysis but have to rely on points-to
+ information only. */
if (TREE_CODE (addr_a) == MEM_REF
- && DR_UNCONSTRAINED_BASE (a))
+ && (DR_UNCONSTRAINED_BASE (a)
+ || TREE_CODE (TREE_OPERAND (addr_a, 0)) == SSA_NAME))
{
- if (TREE_CODE (addr_b) == MEM_REF
- && DR_UNCONSTRAINED_BASE (b))
+ /* For true dependences we can apply TBAA. */
+ if (flag_strict_aliasing
+ && DR_IS_WRITE (a) && DR_IS_READ (b)
+ && !alias_sets_conflict_p (get_alias_set (DR_REF (a)),
+ get_alias_set (DR_REF (b))))
+ return false;
+ if (TREE_CODE (addr_b) == MEM_REF)
return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
TREE_OPERAND (addr_b, 0));
else
build_fold_addr_expr (addr_b));
}
else if (TREE_CODE (addr_b) == MEM_REF
- && DR_UNCONSTRAINED_BASE (b))
- return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a),
- TREE_OPERAND (addr_b, 0));
+ && (DR_UNCONSTRAINED_BASE (b)
+ || TREE_CODE (TREE_OPERAND (addr_b, 0)) == SSA_NAME))
+ {
+ /* For true dependences we can apply TBAA. */
+ if (flag_strict_aliasing
+ && DR_IS_WRITE (a) && DR_IS_READ (b)
+ && !alias_sets_conflict_p (get_alias_set (DR_REF (a)),
+ get_alias_set (DR_REF (b))))
+ return false;
+ if (TREE_CODE (addr_a) == MEM_REF)
+ return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
+ TREE_OPERAND (addr_b, 0));
+ else
+ return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a),
+ TREE_OPERAND (addr_b, 0));
+ }
/* Otherwise DR_BASE_OBJECT is an access that covers the whole object
that is being subsetted in the loop nest. */
struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
struct data_reference *b,
- VEC (loop_p, heap) *loop_nest)
+ vec<loop_p> loop_nest)
{
struct data_dependence_relation *res;
unsigned int i;
res = XNEW (struct data_dependence_relation);
DDR_A (res) = a;
DDR_B (res) = b;
- DDR_LOOP_NEST (res) = NULL;
+ DDR_LOOP_NEST (res).create (0);
DDR_REVERSED_P (res) = false;
- DDR_SUBSCRIPTS (res) = NULL;
- DDR_DIR_VECTS (res) = NULL;
- DDR_DIST_VECTS (res) = NULL;
+ DDR_SUBSCRIPTS (res).create (0);
+ DDR_DIR_VECTS (res).create (0);
+ DDR_DIST_VECTS (res).create (0);
if (a == NULL || b == NULL)
{
}
/* If the data references do not alias, then they are independent. */
- if (!dr_may_alias_p (a, b, loop_nest != NULL))
+ if (!dr_may_alias_p (a, b, loop_nest.exists ()))
{
DDR_ARE_DEPENDENT (res) = chrec_known;
return res;
/* 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),
+ if (loop_nest.exists ()
+ && !object_address_invariant_in_loop_p (loop_nest[0],
DR_BASE_OBJECT (a)))
{
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
}
DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
- DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
+ DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
DDR_LOOP_NEST (res) = loop_nest;
DDR_INNER_LOOP (res) = 0;
DDR_SELF_REFERENCE (res) = true;
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);
+ DDR_SUBSCRIPTS (res).safe_push (subscript);
}
return res;
}
/* 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 (loop_nest
- && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
+ if (loop_nest.exists ()
+ && !object_address_invariant_in_loop_p (loop_nest[0],
DR_BASE_OBJECT (a)))
{
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
- DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
+ DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
DDR_LOOP_NEST (res) = loop_nest;
DDR_INNER_LOOP (res) = 0;
DDR_SELF_REFERENCE (res) = false;
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);
+ DDR_SUBSCRIPTS (res).safe_push (subscript);
}
return res;
/* Frees memory used by SUBSCRIPTS. */
static void
-free_subscripts (VEC (subscript_p, heap) *subscripts)
+free_subscripts (vec<subscript_p> subscripts)
{
unsigned i;
subscript_p s;
- FOR_EACH_VEC_ELT (subscript_p, subscripts, i, s)
+ FOR_EACH_VEC_ELT (subscripts, i, s)
{
free_conflict_function (s->conflicting_iterations_in_a);
free_conflict_function (s->conflicting_iterations_in_b);
free (s);
}
- VEC_free (subscript_p, heap, subscripts);
+ subscripts.release ();
}
/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
finalize_ddr_dependent (struct data_dependence_relation *ddr,
tree chrec)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(dependence classified: ");
- print_generic_expr (dump_file, chrec, 0);
- fprintf (dump_file, ")\n");
- }
-
DDR_ARE_DEPENDENT (ddr) = chrec;
free_subscripts (DDR_SUBSCRIPTS (ddr));
- DDR_SUBSCRIPTS (ddr) = NULL;
+ DDR_SUBSCRIPTS (ddr).create (0);
}
/* The dependence relation DDR cannot be represented by a distance
va_list ap;
gcc_assert (0 < n && n <= MAX_DIM);
- va_start(ap, n);
+ va_start (ap, n);
ret->n = n;
for (i = 0; i < n; i++)
ret->fns[i] = va_arg (ap, affine_fn);
- va_end(ap);
+ va_end (ap);
return ret;
}
static affine_fn
affine_fn_cst (tree cst)
{
- affine_fn fn = VEC_alloc (tree, heap, 1);
- VEC_quick_push (tree, fn, cst);
+ affine_fn fn;
+ fn.create (1);
+ fn.quick_push (cst);
return fn;
}
static affine_fn
affine_fn_univar (tree cst, unsigned dim, tree coef)
{
- affine_fn fn = VEC_alloc (tree, heap, dim + 1);
+ affine_fn fn;
+ fn.create (dim + 1);
unsigned i;
gcc_assert (dim > 0);
- VEC_quick_push (tree, fn, cst);
+ fn.quick_push (cst);
for (i = 1; i < dim; i++)
- VEC_quick_push (tree, fn, integer_zero_node);
- VEC_quick_push (tree, fn, coef);
+ fn.quick_push (integer_zero_node);
+ fn.quick_push (coef);
return fn;
}
static tree
max_stmt_executions_tree (struct loop *loop)
{
- double_int nit;
+ widest_int nit;
if (!max_stmt_executions (loop, &nit))
return chrec_dont_know;
- if (!double_int_fits_to_tree_p (unsigned_type_node, nit))
+ if (!wi::fits_to_tree_p (nit, unsigned_type_node))
return chrec_dont_know;
- return double_int_to_tree (unsigned_type_node, nit);
+ return wide_int_to_tree (unsigned_type_node, nit);
}
/* Determine whether the CHREC is always positive/negative. If the expression
return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
}
- case NOP_EXPR:
+ CASE_CONVERT:
{
tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
return chrec_convert (chrec_type (chrec), op, NULL);
mat[r2][i] += const1 * mat[r1][i];
}
-/* Swap rows R1 and R2 in matrix MAT. */
-
-static void
-lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2)
-{
- lambda_vector row;
-
- row = mat[r1];
- mat[r1] = mat[r2];
- mat[r2] = row;
-}
-
/* Multiply vector VEC1 of length SIZE by a constant CONST1,
and store the result in VEC2. */
factor = sigma * (a / b);
lambda_matrix_row_add (S, n, i, i-1, -factor);
- lambda_matrix_row_exchange (S, i, i-1);
+ std::swap (S[i], S[i-1]);
lambda_matrix_row_add (U, m, i, i-1, -factor);
- lambda_matrix_row_exchange (U, i, i-1);
+ std::swap (U[i], U[i-1]);
}
}
}
dump_conflict_function (dump_file, *overlaps_a);
fprintf (dump_file, ")\n (overlaps_b = ");
dump_conflict_function (dump_file, *overlaps_b);
- fprintf (dump_file, ")\n");
- fprintf (dump_file, ")\n");
+ fprintf (dump_file, "))\n");
}
}
{
siv_subscript_dontknow:;
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "siv test failed: unimplemented.\n");
+ fprintf (dump_file, " siv test failed: unimplemented");
*overlaps_a = conflict_fn_not_known ();
*overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
HOST_WIDE_INT cd = 0, val;
tree step;
- if (!host_integerp (cst, 0))
+ if (!tree_fits_shwi_p (cst))
return true;
- val = tree_low_cst (cst, 0);
+ val = tree_to_shwi (cst);
while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
{
step = CHREC_RIGHT (chrec);
- if (!host_integerp (step, 0))
+ if (!tree_fits_shwi_p (step))
return true;
- cd = gcd (cd, tree_low_cst (step, 0));
+ cd = gcd (cd, tree_to_shwi (step));
chrec = CHREC_LEFT (chrec);
}
dump_conflict_function (dump_file, *overlap_iterations_a);
fprintf (dump_file, ")\n (overlap_iterations_b = ");
dump_conflict_function (dump_file, *overlap_iterations_b);
- fprintf (dump_file, ")\n");
- fprintf (dump_file, ")\n");
+ fprintf (dump_file, "))\n");
}
}
unsigned i;
lambda_vector v;
- FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, v)
+ FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, v)
if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
return;
- VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
+ DDR_DIST_VECTS (ddr).safe_push (dist_v);
}
/* Helper function for uniquely inserting direction vectors. */
unsigned i;
lambda_vector v;
- FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), i, v)
+ FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr), i, v)
if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
return;
- VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
+ DDR_DIR_VECTS (ddr).safe_push (dir_v);
}
/* Add a distance of 1 on all the loops outer than INDEX. If we
unsigned i, j;
lambda_vector dist_v;
- FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v)
+ FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
{
lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
struct subscript *subscript;
tree res = NULL_TREE;
- for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
- i++)
+ for (i = 0; DDR_SUBSCRIPTS (ddr).iterate (i, &subscript); i++)
{
conflict_function *overlaps_a, *overlaps_b;
subscript_dependence_tester (struct data_dependence_relation *ddr,
struct loop *loop_nest)
{
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(subscript_dependence_tester \n");
-
if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
dependence_stats.num_dependence_dependent++;
compute_subscript_distance (ddr);
if (build_classic_dist_vector (ddr, loop_nest))
build_classic_dir_vector (ddr);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
}
/* Returns true when all the access functions of A are affine or
const struct loop *loop_nest)
{
unsigned int i;
- VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
+ vec<tree> fns = DR_ACCESS_FNS (a);
tree t;
- FOR_EACH_VEC_ELT (tree, fns, i, t)
+ FOR_EACH_VEC_ELT (fns, i, t)
if (!evolution_function_is_invariant_p (t, loop_nest->num)
&& !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
return false;
return true;
}
-/* Initializes an equation for an OMEGA problem using the information
- contained in the ACCESS_FUN. Returns true when the operation
- succeeded.
+/* This computes the affine dependence relation between A and B with
+ respect to LOOP_NEST. CHREC_KNOWN is used for representing the
+ independence between two accesses, while CHREC_DONT_KNOW is used
+ for representing the unknown relation.
- PB is the omega constraint system.
- EQ is the number of the equation to be initialized.
- OFFSET is used for shifting the variables names in the constraints:
- a constrain is composed of 2 * the number of variables surrounding
- dependence accesses. OFFSET is set either to 0 for the first n variables,
- then it is set to n.
- ACCESS_FUN is expected to be an affine chrec. */
+ Note that it is possible to stop the computation of the dependence
+ relation the first time we detect a CHREC_KNOWN element for a given
+ subscript. */
-static bool
-init_omega_eq_with_af (omega_pb pb, unsigned eq,
- unsigned int offset, tree access_fun,
- struct data_dependence_relation *ddr)
+void
+compute_affine_dependence (struct data_dependence_relation *ddr,
+ struct loop *loop_nest)
{
- switch (TREE_CODE (access_fun))
+ struct data_reference *dra = DDR_A (ddr);
+ struct data_reference *drb = DDR_B (ddr);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- case POLYNOMIAL_CHREC:
- {
- tree left = CHREC_LEFT (access_fun);
- tree right = CHREC_RIGHT (access_fun);
- int var = CHREC_VARIABLE (access_fun);
- unsigned var_idx;
+ fprintf (dump_file, "(compute_affine_dependence\n");
+ fprintf (dump_file, " stmt_a: ");
+ print_gimple_stmt (dump_file, DR_STMT (dra), 0, TDF_SLIM);
+ fprintf (dump_file, " stmt_b: ");
+ print_gimple_stmt (dump_file, DR_STMT (drb), 0, TDF_SLIM);
+ }
- if (TREE_CODE (right) != INTEGER_CST)
- return false;
+ /* Analyze only when the dependence relation is not yet known. */
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ {
+ dependence_stats.num_dependence_tests++;
- var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
- pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
+ if (access_functions_are_affine_or_constant_p (dra, loop_nest)
+ && access_functions_are_affine_or_constant_p (drb, loop_nest))
+ subscript_dependence_tester (ddr, loop_nest);
- /* Compute the innermost loop index. */
- DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
+ /* As a last case, if the dependence cannot be determined, or if
+ the dependence is considered too difficult to determine, answer
+ "don't know". */
+ else
+ {
+ dependence_stats.num_dependence_undetermined++;
- if (offset == 0)
- pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
- += int_cst_value (right);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Data ref a:\n");
+ dump_data_reference (dump_file, dra);
+ fprintf (dump_file, "Data ref b:\n");
+ dump_data_reference (dump_file, drb);
+ fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
+ }
+ finalize_ddr_dependent (ddr, chrec_dont_know);
+ }
+ }
- switch (TREE_CODE (left))
- {
- case POLYNOMIAL_CHREC:
- return init_omega_eq_with_af (pb, eq, offset, left, ddr);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ fprintf (dump_file, ") -> no dependence\n");
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ fprintf (dump_file, ") -> dependence analysis failed\n");
+ else
+ fprintf (dump_file, ")\n");
+ }
+}
- case INTEGER_CST:
- pb->eqs[eq].coef[0] += int_cst_value (left);
- return true;
+/* 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. Return true when successful, i.e. data references number
+ is small enough to be handled. */
- default:
- return false;
- }
- }
+bool
+compute_all_dependences (vec<data_reference_p> datarefs,
+ vec<ddr_p> *dependence_relations,
+ vec<loop_p> loop_nest,
+ bool compute_self_and_rr)
+{
+ struct data_dependence_relation *ddr;
+ struct data_reference *a, *b;
+ unsigned int i, j;
- case INTEGER_CST:
- pb->eqs[eq].coef[0] += int_cst_value (access_fun);
- return true;
+ if ((int) datarefs.length ()
+ > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
+ {
+ struct data_dependence_relation *ddr;
- default:
+ /* Insert a single relation into dependence_relations:
+ chrec_dont_know. */
+ ddr = initialize_data_dependence_relation (NULL, NULL, loop_nest);
+ dependence_relations->safe_push (ddr);
return false;
}
+
+ FOR_EACH_VEC_ELT (datarefs, i, a)
+ for (j = i + 1; datarefs.iterate (j, &b); j++)
+ if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
+ {
+ ddr = initialize_data_dependence_relation (a, b, loop_nest);
+ dependence_relations->safe_push (ddr);
+ if (loop_nest.exists ())
+ compute_affine_dependence (ddr, loop_nest[0]);
+ }
+
+ if (compute_self_and_rr)
+ FOR_EACH_VEC_ELT (datarefs, i, a)
+ {
+ ddr = initialize_data_dependence_relation (a, a, loop_nest);
+ dependence_relations->safe_push (ddr);
+ if (loop_nest.exists ())
+ compute_affine_dependence (ddr, loop_nest[0]);
+ }
+
+ return true;
}
-/* As explained in the comments preceding init_omega_for_ddr, we have
- to set up a system for each loop level, setting outer loops
- variation to zero, and current loop variation to positive or zero.
- Save each lexico positive distance vector. */
+/* Describes a location of a memory reference. */
-static void
-omega_extract_distance_vectors (omega_pb pb,
- struct data_dependence_relation *ddr)
+struct data_ref_loc
{
- int eq, geq;
- unsigned i, j;
- struct loop *loopi, *loopj;
- enum omega_result res;
-
- /* Set a new problem for each loop in the nest. The basis is the
- problem that we have initialized until now. On top of this we
- add new constraints. */
- for (i = 0; i <= DDR_INNER_LOOP (ddr)
- && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
- {
- int dist = 0;
- omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
- DDR_NB_LOOPS (ddr));
+ /* The memory reference. */
+ tree ref;
- omega_copy_problem (copy, pb);
+ /* True if the memory reference is read. */
+ bool is_read;
+};
- /* For all the outer loops "loop_j", add "dj = 0". */
- for (j = 0;
- j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
- {
- eq = omega_add_zero_eq (copy, omega_black);
- copy->eqs[eq].coef[j + 1] = 1;
- }
- /* For "loop_i", add "0 <= di". */
- geq = omega_add_zero_geq (copy, omega_black);
- copy->geqs[geq].coef[i + 1] = 1;
+/* Stores the locations of memory references in STMT to REFERENCES. Returns
+ true if STMT clobbers memory, false otherwise. */
- /* Reduce the constraint system, and test that the current
- problem is feasible. */
- res = omega_simplify_problem (copy);
- if (res == omega_false
- || res == omega_unknown
- || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
- goto next_problem;
+static bool
+get_references_in_stmt (gimple *stmt, vec<data_ref_loc, va_heap> *references)
+{
+ bool clobbers_memory = false;
+ data_ref_loc ref;
+ tree op0, op1;
+ enum gimple_code stmt_code = gimple_code (stmt);
- for (eq = 0; eq < copy->num_subs; eq++)
- if (copy->subs[eq].key == (int) i + 1)
+ /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
+ As we cannot model data-references to not spelled out
+ accesses give up if they may occur. */
+ if (stmt_code == GIMPLE_CALL
+ && !(gimple_call_flags (stmt) & ECF_CONST))
+ {
+ /* Allow IFN_GOMP_SIMD_LANE in their own loops. */
+ if (gimple_call_internal_p (stmt))
+ switch (gimple_call_internal_fn (stmt))
{
- dist = copy->subs[eq].coef[0];
- goto found_dist;
- }
-
- if (dist == 0)
- {
- /* Reinitialize problem... */
- omega_copy_problem (copy, pb);
- for (j = 0;
- j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
+ case IFN_GOMP_SIMD_LANE:
{
- eq = omega_add_zero_eq (copy, omega_black);
- copy->eqs[eq].coef[j + 1] = 1;
+ struct loop *loop = gimple_bb (stmt)->loop_father;
+ tree uid = gimple_call_arg (stmt, 0);
+ gcc_assert (TREE_CODE (uid) == SSA_NAME);
+ if (loop == NULL
+ || loop->simduid != SSA_NAME_VAR (uid))
+ clobbers_memory = true;
+ break;
}
+ case IFN_MASK_LOAD:
+ case IFN_MASK_STORE:
+ break;
+ default:
+ clobbers_memory = true;
+ break;
+ }
+ else
+ clobbers_memory = true;
+ }
+ else if (stmt_code == GIMPLE_ASM
+ && (gimple_asm_volatile_p (as_a <gasm *> (stmt))
+ || gimple_vuse (stmt)))
+ clobbers_memory = true;
- /* ..., but this time "di = 1". */
- eq = omega_add_zero_eq (copy, omega_black);
- copy->eqs[eq].coef[i + 1] = 1;
- copy->eqs[eq].coef[0] = -1;
-
- res = omega_simplify_problem (copy);
- if (res == omega_false
- || res == omega_unknown
- || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
- goto next_problem;
-
- for (eq = 0; eq < copy->num_subs; eq++)
- if (copy->subs[eq].key == (int) i + 1)
- {
- dist = copy->subs[eq].coef[0];
- goto found_dist;
- }
- }
+ if (!gimple_vuse (stmt))
+ return clobbers_memory;
- found_dist:;
- /* Save the lexicographically positive distance vector. */
- if (dist >= 0)
- {
- lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ if (stmt_code == GIMPLE_ASSIGN)
+ {
+ tree base;
+ op0 = gimple_assign_lhs (stmt);
+ op1 = gimple_assign_rhs1 (stmt);
- dist_v[i] = dist;
+ if (DECL_P (op1)
+ || (REFERENCE_CLASS_P (op1)
+ && (base = get_base_address (op1))
+ && TREE_CODE (base) != SSA_NAME))
+ {
+ ref.ref = op1;
+ ref.is_read = true;
+ references->safe_push (ref);
+ }
+ }
+ else if (stmt_code == GIMPLE_CALL)
+ {
+ unsigned i, n;
+ tree ptr, type;
+ unsigned int align;
- for (eq = 0; eq < copy->num_subs; eq++)
- if (copy->subs[eq].key > 0)
- {
- dist = copy->subs[eq].coef[0];
- dist_v[copy->subs[eq].key - 1] = dist;
- }
+ ref.is_read = false;
+ if (gimple_call_internal_p (stmt))
+ switch (gimple_call_internal_fn (stmt))
+ {
+ case IFN_MASK_LOAD:
+ if (gimple_call_lhs (stmt) == NULL_TREE)
+ break;
+ ref.is_read = true;
+ case IFN_MASK_STORE:
+ ptr = build_int_cst (TREE_TYPE (gimple_call_arg (stmt, 1)), 0);
+ align = tree_to_shwi (gimple_call_arg (stmt, 1));
+ if (ref.is_read)
+ type = TREE_TYPE (gimple_call_lhs (stmt));
+ else
+ type = TREE_TYPE (gimple_call_arg (stmt, 3));
+ if (TYPE_ALIGN (type) != align)
+ type = build_aligned_type (type, align);
+ ref.ref = fold_build2 (MEM_REF, type, gimple_call_arg (stmt, 0),
+ ptr);
+ references->safe_push (ref);
+ return false;
+ default:
+ break;
+ }
- for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
- dir_v[j] = dir_from_dist (dist_v[j]);
+ op0 = gimple_call_lhs (stmt);
+ n = gimple_call_num_args (stmt);
+ for (i = 0; i < n; i++)
+ {
+ op1 = gimple_call_arg (stmt, i);
- save_dist_v (ddr, dist_v);
- save_dir_v (ddr, dir_v);
+ if (DECL_P (op1)
+ || (REFERENCE_CLASS_P (op1) && get_base_address (op1)))
+ {
+ ref.ref = op1;
+ ref.is_read = true;
+ references->safe_push (ref);
+ }
}
+ }
+ else
+ return clobbers_memory;
- next_problem:;
- omega_free_problem (copy);
+ if (op0
+ && (DECL_P (op0)
+ || (REFERENCE_CLASS_P (op0) && get_base_address (op0))))
+ {
+ ref.ref = op0;
+ ref.is_read = false;
+ references->safe_push (ref);
}
+ return clobbers_memory;
}
-/* This is called for each subscript of a tuple of data references:
- insert an equality for representing the conflicts. */
-static bool
-omega_setup_subscript (tree access_fun_a, tree access_fun_b,
- struct data_dependence_relation *ddr,
- omega_pb pb, bool *maybe_dependent)
+/* Returns true if the loop-nest has any data reference. */
+
+bool
+loop_nest_has_data_refs (loop_p loop)
{
- int eq;
- 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);
- tree minus_one;
-
- /* When the fun_a - fun_b is not constant, the dependence is not
- captured by the classic distance vector representation. */
- if (TREE_CODE (difference) != INTEGER_CST)
- return false;
+ basic_block *bbs = get_loop_body (loop);
+ vec<data_ref_loc> references;
+ references.create (3);
- /* ZIV test. */
- if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
+ for (unsigned i = 0; i < loop->num_nodes; i++)
{
- /* There is no dependence. */
- *maybe_dependent = false;
- return true;
- }
-
- minus_one = build_int_cst (type, -1);
- fun_b = chrec_fold_multiply (type, fun_b, minus_one);
+ basic_block bb = bbs[i];
+ gimple_stmt_iterator bsi;
- eq = omega_add_zero_eq (pb, omega_black);
- if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
- || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
- /* There is probably a dependence, but the system of
- constraints cannot be built: answer "don't know". */
- return false;
-
- /* GCD test. */
- if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
- && !int_divides_p (lambda_vector_gcd
- ((lambda_vector) &(pb->eqs[eq].coef[1]),
- 2 * DDR_NB_LOOPS (ddr)),
- pb->eqs[eq].coef[0]))
- {
- /* There is no dependence. */
- *maybe_dependent = false;
- return true;
- }
-
- return true;
-}
-
-/* Helper function, same as init_omega_for_ddr but specialized for
- data references A and B. */
-
-static bool
-init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
- struct data_dependence_relation *ddr,
- omega_pb pb, bool *maybe_dependent)
-{
- unsigned i;
- int ineq;
- struct loop *loopi;
- unsigned nb_loops = DDR_NB_LOOPS (ddr);
-
- /* Insert an equality per subscript. */
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
- ddr, pb, maybe_dependent))
- return false;
- else if (*maybe_dependent == false)
- {
- /* There is no dependence. */
- DDR_ARE_DEPENDENT (ddr) = chrec_known;
- return true;
- }
- }
-
- /* Insert inequalities: constraints corresponding to the iteration
- domain, i.e. the loops surrounding the references "loop_x" and
- the distance variables "dx". The layout of the OMEGA
- representation is as follows:
- - coef[0] is the constant
- - coef[1..nb_loops] are the protected variables that will not be
- removed by the solver: the "dx"
- - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
- */
- for (i = 0; i <= DDR_INNER_LOOP (ddr)
- && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
- {
- HOST_WIDE_INT nbi = max_stmt_executions_int (loopi);
-
- /* 0 <= loop_x */
- ineq = omega_add_zero_geq (pb, omega_black);
- pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
-
- /* 0 <= loop_x + dx */
- ineq = omega_add_zero_geq (pb, omega_black);
- pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
- pb->geqs[ineq].coef[i + 1] = 1;
-
- if (nbi != -1)
- {
- /* loop_x <= nb_iters */
- ineq = omega_add_zero_geq (pb, omega_black);
- pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
- pb->geqs[ineq].coef[0] = nbi;
-
- /* loop_x + dx <= nb_iters */
- ineq = omega_add_zero_geq (pb, omega_black);
- pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
- pb->geqs[ineq].coef[i + 1] = -1;
- pb->geqs[ineq].coef[0] = nbi;
-
- /* A step "dx" bigger than nb_iters is not feasible, so
- add "0 <= nb_iters + dx", */
- ineq = omega_add_zero_geq (pb, omega_black);
- pb->geqs[ineq].coef[i + 1] = 1;
- pb->geqs[ineq].coef[0] = nbi;
- /* and "dx <= nb_iters". */
- ineq = omega_add_zero_geq (pb, omega_black);
- pb->geqs[ineq].coef[i + 1] = -1;
- pb->geqs[ineq].coef[0] = nbi;
- }
- }
-
- omega_extract_distance_vectors (pb, ddr);
-
- return true;
-}
-
-/* Sets up the Omega dependence problem for the data dependence
- relation DDR. Returns false when the constraint system cannot be
- built, ie. when the test answers "don't know". Returns true
- otherwise, and when independence has been proved (using one of the
- trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
- set MAYBE_DEPENDENT to true.
-
- Example: for setting up the dependence system corresponding to the
- conflicting accesses
-
- | loop_i
- | loop_j
- | A[i, i+1] = ...
- | ... A[2*j, 2*(i + j)]
- | endloop_j
- | endloop_i
-
- the following constraints come from the iteration domain:
-
- 0 <= i <= Ni
- 0 <= i + di <= Ni
- 0 <= j <= Nj
- 0 <= j + dj <= Nj
-
- where di, dj are the distance variables. The constraints
- representing the conflicting elements are:
-
- i = 2 * (j + dj)
- i + 1 = 2 * (i + di + j + dj)
-
- For asking that the resulting distance vector (di, dj) be
- lexicographically positive, we insert the constraint "di >= 0". If
- "di = 0" in the solution, we fix that component to zero, and we
- look at the inner loops: we set a new problem where all the outer
- loop distances are zero, and fix this inner component to be
- positive. When one of the components is positive, we save that
- distance, and set a new problem where the distance on this loop is
- zero, searching for other distances in the inner loops. Here is
- the classic example that illustrates that we have to set for each
- inner loop a new problem:
-
- | loop_1
- | loop_2
- | A[10]
- | endloop_2
- | endloop_1
-
- we have to save two distances (1, 0) and (0, 1).
-
- Given two array references, refA and refB, we have to set the
- dependence problem twice, refA vs. refB and refB vs. refA, and we
- cannot do a single test, as refB might occur before refA in the
- inner loops, and the contrary when considering outer loops: ex.
-
- | loop_0
- | loop_1
- | loop_2
- | T[{1,+,1}_2][{1,+,1}_1] // refA
- | T[{2,+,1}_2][{0,+,1}_1] // refB
- | endloop_2
- | endloop_1
- | endloop_0
-
- refB touches the elements in T before refA, and thus for the same
- loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
- but for successive loop_0 iterations, we have (1, -1, 1)
-
- The Omega solver expects the distance variables ("di" in the
- previous example) to come first in the constraint system (as
- variables to be protected, or "safe" variables), the constraint
- system is built using the following layout:
-
- "cst | distance vars | index vars".
-*/
-
-static bool
-init_omega_for_ddr (struct data_dependence_relation *ddr,
- bool *maybe_dependent)
-{
- omega_pb pb;
- bool res = false;
-
- *maybe_dependent = true;
-
- if (same_access_functions (ddr))
- {
- unsigned j;
- lambda_vector dir_v;
-
- /* Save the 0 vector. */
- save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
- dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
- dir_v[j] = dir_equal;
- save_dir_v (ddr, dir_v);
-
- /* Save the dependences carried by outer loops. */
- pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
- res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
- maybe_dependent);
- omega_free_problem (pb);
- return res;
- }
-
- /* Omega expects the protected variables (those that have to be kept
- after elimination) to appear first in the constraint system.
- These variables are the distance variables. In the following
- initialization we declare NB_LOOPS safe variables, and the total
- number of variables for the constraint system is 2*NB_LOOPS. */
- pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
- res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
- maybe_dependent);
- omega_free_problem (pb);
-
- /* Stop computation if not decidable, or no dependence. */
- if (res == false || *maybe_dependent == false)
- return res;
-
- pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
- res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
- maybe_dependent);
- omega_free_problem (pb);
-
- return res;
-}
-
-/* Return true when DDR contains the same information as that stored
- in DIR_VECTS and in DIST_VECTS, return false otherwise. */
-
-static bool
-ddr_consistent_p (FILE *file,
- struct data_dependence_relation *ddr,
- VEC (lambda_vector, heap) *dist_vects,
- VEC (lambda_vector, heap) *dir_vects)
-{
- unsigned int i, j;
-
- /* If dump_file is set, output there. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- file = dump_file;
-
- if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
- {
- lambda_vector b_dist_v;
- fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
- VEC_length (lambda_vector, dist_vects),
- DDR_NUM_DIST_VECTS (ddr));
-
- fprintf (file, "Banerjee dist vectors:\n");
- FOR_EACH_VEC_ELT (lambda_vector, dist_vects, i, b_dist_v)
- print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
-
- fprintf (file, "Omega dist vectors:\n");
- for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
- print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
-
- fprintf (file, "data dependence relation:\n");
- dump_data_dependence_relation (file, ddr);
-
- fprintf (file, ")\n");
- return false;
- }
-
- if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
- {
- fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
- VEC_length (lambda_vector, dir_vects),
- DDR_NUM_DIR_VECTS (ddr));
- return false;
- }
-
- for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
- {
- lambda_vector a_dist_v;
- lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
-
- /* Distance vectors are not ordered in the same way in the DDR
- and in the DIST_VECTS: search for a matching vector. */
- FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, a_dist_v)
- if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
- break;
-
- if (j == VEC_length (lambda_vector, dist_vects))
- {
- fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
- print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
- fprintf (file, "not found in Omega dist vectors:\n");
- print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
- fprintf (file, "data dependence relation:\n");
- dump_data_dependence_relation (file, ddr);
- fprintf (file, ")\n");
- }
- }
-
- for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
- {
- lambda_vector a_dir_v;
- lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
-
- /* Direction vectors are not ordered in the same way in the DDR
- and in the DIR_VECTS: search for a matching vector. */
- FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, a_dir_v)
- if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
- break;
-
- if (j == VEC_length (lambda_vector, dist_vects))
- {
- fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
- print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
- fprintf (file, "not found in Omega dir vectors:\n");
- print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
- fprintf (file, "data dependence relation:\n");
- dump_data_dependence_relation (file, ddr);
- fprintf (file, ")\n");
- }
- }
-
- return true;
-}
-
-/* This computes the affine dependence relation between A and B with
- respect to LOOP_NEST. CHREC_KNOWN is used for representing the
- independence between two accesses, while CHREC_DONT_KNOW is used
- for representing the unknown relation.
-
- Note that it is possible to stop the computation of the dependence
- relation the first time we detect a CHREC_KNOWN element for a given
- subscript. */
-
-static void
-compute_affine_dependence (struct data_dependence_relation *ddr,
- struct loop *loop_nest)
-{
- struct data_reference *dra = DDR_A (ddr);
- struct data_reference *drb = DDR_B (ddr);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(compute_affine_dependence\n");
- fprintf (dump_file, " stmt_a: ");
- print_gimple_stmt (dump_file, DR_STMT (dra), 0, TDF_SLIM);
- fprintf (dump_file, " stmt_b: ");
- print_gimple_stmt (dump_file, DR_STMT (drb), 0, TDF_SLIM);
- }
-
- /* Analyze only when the dependence relation is not yet known. */
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- {
- dependence_stats.num_dependence_tests++;
-
- if (access_functions_are_affine_or_constant_p (dra, loop_nest)
- && access_functions_are_affine_or_constant_p (drb, loop_nest))
- {
- if (flag_check_data_deps)
- {
- /* Compute the dependences using the first algorithm. */
- subscript_dependence_tester (ddr, loop_nest);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\n\nBanerjee Analyzer\n");
- dump_data_dependence_relation (dump_file, ddr);
- }
-
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- {
- bool maybe_dependent;
- VEC (lambda_vector, heap) *dir_vects, *dist_vects;
-
- /* Save the result of the first DD analyzer. */
- dist_vects = DDR_DIST_VECTS (ddr);
- dir_vects = DDR_DIR_VECTS (ddr);
-
- /* Reset the information. */
- DDR_DIST_VECTS (ddr) = NULL;
- DDR_DIR_VECTS (ddr) = NULL;
-
- /* Compute the same information using Omega. */
- if (!init_omega_for_ddr (ddr, &maybe_dependent))
- goto csys_dont_know;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Omega Analyzer\n");
- dump_data_dependence_relation (dump_file, ddr);
- }
-
- /* Check that we get the same information. */
- if (maybe_dependent)
- gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
- dir_vects));
- }
- }
- else
- subscript_dependence_tester (ddr, loop_nest);
- }
-
- /* As a last case, if the dependence cannot be determined, or if
- the dependence is considered too difficult to determine, answer
- "don't know". */
- else
- {
- csys_dont_know:;
- dependence_stats.num_dependence_undetermined++;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Data ref a:\n");
- dump_data_reference (dump_file, dra);
- fprintf (dump_file, "Data ref b:\n");
- dump_data_reference (dump_file, drb);
- fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
- }
- finalize_ddr_dependent (ddr, chrec_dont_know);
- }
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
- fprintf (dump_file, ") -> no dependence\n");
- else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
- fprintf (dump_file, ") -> dependence analysis failed\n");
- else
- fprintf (dump_file, ")\n");
- }
-}
-
-/* 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. Return true when successful, i.e. data references number
- is small enough to be handled. */
-
-bool
-compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
- VEC (ddr_p, heap) **dependence_relations,
- VEC (loop_p, heap) *loop_nest,
- bool compute_self_and_rr)
-{
- struct data_dependence_relation *ddr;
- 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, b, loop_nest);
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- if (loop_nest)
- compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
- }
-
- if (compute_self_and_rr)
- FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
- {
- ddr = initialize_data_dependence_relation (a, a, loop_nest);
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- if (loop_nest)
- compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
- }
-
- return true;
-}
-
-/* Describes a location of a memory reference. */
-
-typedef struct data_ref_loc_d
-{
- /* Position of the memory reference. */
- tree *pos;
-
- /* True if the memory reference is read. */
- bool is_read;
-} data_ref_loc;
-
-DEF_VEC_O (data_ref_loc);
-DEF_VEC_ALLOC_O (data_ref_loc, heap);
-
-/* Stores the locations of memory references in STMT to REFERENCES. Returns
- true if STMT clobbers memory, false otherwise. */
-
-static bool
-get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
-{
- bool clobbers_memory = false;
- data_ref_loc *ref;
- 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. */
- if ((stmt_code == GIMPLE_CALL
- && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
- || (stmt_code == GIMPLE_ASM
- && (gimple_asm_volatile_p (stmt) || gimple_vuse (stmt))))
- clobbers_memory = true;
-
- if (!gimple_vuse (stmt))
- return clobbers_memory;
-
- if (stmt_code == GIMPLE_ASSIGN)
- {
- tree base;
- op0 = gimple_assign_lhs_ptr (stmt);
- op1 = gimple_assign_rhs1_ptr (stmt);
-
- if (DECL_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;
- ref->is_read = true;
- }
- }
- else if (stmt_code == GIMPLE_CALL)
- {
- unsigned i, n;
-
- op0 = gimple_call_lhs_ptr (stmt);
- n = gimple_call_num_args (stmt);
- for (i = 0; i < n; i++)
- {
- op1 = gimple_call_arg_ptr (stmt, i);
-
- if (DECL_P (*op1)
- || (REFERENCE_CLASS_P (*op1) && get_base_address (*op1)))
- {
- ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
- ref->pos = op1;
- ref->is_read = true;
- }
- }
- }
- else
- return clobbers_memory;
-
- if (*op0
- && (DECL_P (*op0)
- || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))))
- {
- ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
- ref->pos = op0;
- ref->is_read = false;
- }
- return clobbers_memory;
-}
-
-/* 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
-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_EACH_VEC_ELT (data_ref_loc, references, i, ref)
- {
- dr = create_data_ref (nest, loop_containing_stmt (stmt),
- *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;
-}
-
-/* Stores the data references in STMT to DATAREFS. If there is an
- unanalyzable reference, returns false, otherwise returns true.
- NEST is the outermost loop of the loop nest in which the references
- should be instantiated, LOOP is the loop in which the references
- should be analyzed. */
-
-bool
-graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, 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_EACH_VEC_ELT (data_ref_loc, references, i, ref)
- {
- dr = create_data_ref (nest, loop, *ref->pos, stmt, ref->is_read);
- gcc_assert (dr != NULL);
- VEC_safe_push (data_reference_p, heap, *datarefs, dr);
- }
-
- 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. */
-
-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. */
-
-static tree
-find_data_references_in_loop (struct loop *loop,
- VEC (data_reference_p, heap) **datarefs)
-{
- basic_block bb, *bbs;
- unsigned int i;
-
- bbs = get_loop_body_in_dom_order (loop);
-
- for (i = 0; i < loop->num_nodes; i++)
- {
- bb = bbs[i];
-
- if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know)
- {
- free (bbs);
- return chrec_dont_know;
- }
- }
- free (bbs);
-
- return NULL_TREE;
-}
-
-/* Recursive helper function. */
-
-static bool
-find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
-{
- /* Inner loops of the nest should not contain siblings. Example:
- when there are two consecutive loops,
-
- | loop_0
- | loop_1
- | A[{0, +, 1}_1]
- | endloop_1
- | loop_2
- | A[{0, +, 1}_2]
- | endloop_2
- | endloop_0
-
- the dependence relation cannot be captured by the distance
- abstraction. */
- if (loop->next)
- return false;
-
- VEC_safe_push (loop_p, heap, *loop_nest, loop);
- if (loop->inner)
- return find_loop_nest_1 (loop->inner, loop_nest);
- return true;
-}
-
-/* Return false when the LOOP is not well nested. Otherwise return
- true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
- contain the loops from the outermost to the innermost, as they will
- appear in the classic distance vector. */
-
-bool
-find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
-{
- VEC_safe_push (loop_p, heap, *loop_nest, loop);
- if (loop->inner)
- return find_loop_nest_1 (loop->inner, loop_nest);
- return true;
-}
-
-/* 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. */
-
-bool
-compute_data_dependences_for_loop (struct loop *loop,
- bool compute_self_and_read_read_dependences,
- VEC (loop_p, heap) **loop_nest,
- VEC (data_reference_p, heap) **datarefs,
- VEC (ddr_p, heap) **dependence_relations)
-{
- bool res = true;
-
- memset (&dependence_stats, 0, sizeof (dependence_stats));
-
- /* If the loop nest is not well formed, or one of the data references
- is not computable, give up without spending time to compute other
- dependences. */
- if (!loop
- || !find_loop_nest (loop, loop_nest)
- || find_data_references_in_loop (loop, datarefs) == chrec_dont_know
- || !compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
- compute_self_and_read_read_dependences))
- res = false;
-
- if (dump_file && (dump_flags & TDF_STATS))
- {
- fprintf (dump_file, "Dependence tester statistics:\n");
-
- fprintf (dump_file, "Number of dependence tests: %d\n",
- dependence_stats.num_dependence_tests);
- fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
- dependence_stats.num_dependence_dependent);
- fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
- dependence_stats.num_dependence_independent);
- fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
- dependence_stats.num_dependence_undetermined);
-
- fprintf (dump_file, "Number of subscript tests: %d\n",
- dependence_stats.num_subscript_tests);
- fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
- dependence_stats.num_subscript_undetermined);
- fprintf (dump_file, "Number of same subscript function: %d\n",
- dependence_stats.num_same_subscript_function);
-
- fprintf (dump_file, "Number of ziv tests: %d\n",
- dependence_stats.num_ziv);
- fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
- dependence_stats.num_ziv_dependent);
- fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
- dependence_stats.num_ziv_independent);
- fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
- dependence_stats.num_ziv_unimplemented);
-
- fprintf (dump_file, "Number of siv tests: %d\n",
- dependence_stats.num_siv);
- fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
- dependence_stats.num_siv_dependent);
- fprintf (dump_file, "Number of siv tests returning independent: %d\n",
- dependence_stats.num_siv_independent);
- fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
- dependence_stats.num_siv_unimplemented);
-
- fprintf (dump_file, "Number of miv tests: %d\n",
- dependence_stats.num_miv);
- fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
- dependence_stats.num_miv_dependent);
- fprintf (dump_file, "Number of miv tests returning independent: %d\n",
- dependence_stats.num_miv_independent);
- fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
- dependence_stats.num_miv_unimplemented);
- }
-
- 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;
-
- return compute_all_dependences (*datarefs, dependence_relations, NULL,
- compute_self_and_read_read_dependences);
-}
-
-/* Entry point (for testing only). Analyze all the data references
- and the dependence relations in LOOP.
-
- The data references are computed first.
-
- A relation on these nodes is represented by a complete graph. Some
- of the relations could be of no interest, thus the relations can be
- computed on demand.
-
- In the following function we compute all the relations. This is
- just a first implementation that is here for:
- - for showing how to ask for the dependence relations,
- - for the debugging the whole dependence graph,
- - for the dejagnu testcases and maintenance.
-
- It is possible to ask only for a part of the graph, avoiding to
- compute the whole dependence graph. The computed dependences are
- stored in a knowledge base (KB) such that later queries don't
- recompute the same information. The implementation of this KB is
- transparent to the optimizer, and thus the KB can be changed with a
- more efficient implementation, or the KB could be disabled. */
-static void
-analyze_all_data_dependences (struct loop *loop)
-{
- unsigned int i;
- int nb_data_refs = 10;
- VEC (data_reference_p, heap) *datarefs =
- VEC_alloc (data_reference_p, heap, nb_data_refs);
- VEC (ddr_p, heap) *dependence_relations =
- VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
- VEC (loop_p, heap) *loop_nest = VEC_alloc (loop_p, heap, 3);
-
- /* Compute DDs on the whole function. */
- compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs,
- &dependence_relations);
-
- if (dump_file)
- {
- dump_data_dependence_relations (dump_file, dependence_relations);
- fprintf (dump_file, "\n\n");
-
- if (dump_flags & TDF_DETAILS)
- dump_dist_dir_vectors (dump_file, dependence_relations);
-
- if (dump_flags & TDF_STATS)
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
{
- unsigned nb_top_relations = 0;
- unsigned nb_bot_relations = 0;
- unsigned nb_chrec_relations = 0;
- struct data_dependence_relation *ddr;
-
- FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
+ gimple *stmt = gsi_stmt (bsi);
+ get_references_in_stmt (stmt, &references);
+ if (references.length ())
{
- if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
- nb_top_relations++;
-
- else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
- nb_bot_relations++;
-
- else
- nb_chrec_relations++;
+ free (bbs);
+ references.release ();
+ return true;
}
+ }
+ }
+ free (bbs);
+ references.release ();
- gather_stats_on_scev_database ();
- }
- }
-
- VEC_free (loop_p, heap, loop_nest);
- free_dependence_relations (dependence_relations);
- free_data_refs (datarefs);
-}
-
-/* Computes all the data dependences and check that the results of
- several analyzers are the same. */
-
-void
-tree_check_data_deps (void)
-{
- loop_iterator li;
- struct loop *loop_nest;
-
- FOR_EACH_LOOP (li, loop_nest, 0)
- analyze_all_data_dependences (loop_nest);
-}
-
-/* Free the memory used by a data dependence relation DDR. */
-
-void
-free_dependence_relation (struct data_dependence_relation *ddr)
-{
- if (ddr == NULL)
- return;
-
- 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);
-}
-
-/* Free the memory used by the data dependence relations from
- DEPENDENCE_RELATIONS. */
-
-void
-free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
-{
- unsigned int i;
- struct data_dependence_relation *ddr;
-
- FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
- if (ddr)
- free_dependence_relation (ddr);
-
- VEC_free (ddr_p, heap, dependence_relations);
-}
-
-/* Free the memory used by the data references from DATAREFS. */
-
-void
-free_data_refs (VEC (data_reference_p, heap) *datarefs)
-{
- unsigned int i;
- struct data_reference *dr;
-
- FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
- free_data_ref (dr);
- VEC_free (data_reference_p, heap, datarefs);
-}
-
-\f
-
-/* Dump vertex I in RDG to FILE. */
-
-static 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. */
-
-DEBUG_FUNCTION 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. */
-
-static 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 (rdg->vertices[i].component == c)
- {
- if (dumped)
- bitmap_set_bit (dumped, i);
-
- dump_rdg_vertex (file, rdg, i);
- }
-
- fprintf (file, ")\n");
-}
-
-/* Call dump_rdg_vertex on stderr. */
-
-DEBUG_FUNCTION 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. */
-
-DEBUG_FUNCTION void
-debug_rdg (struct graph *rdg)
-{
- dump_rdg (stderr, rdg);
-}
-
-static void
-dot_rdg_1 (FILE *file, struct graph *rdg)
-{
- int i;
-
- fprintf (file, "digraph RDG {\n");
-
- for (i = 0; i < rdg->n_vertices; i++)
- {
- 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 ();
- }
- }
-
- fprintf (file, "}\n\n");
-}
-
-/* Display the Reduced Dependence Graph using dotty. */
-extern void dot_rdg (struct graph *);
-
-DEBUG_FUNCTION void
-dot_rdg (struct graph *rdg)
-{
- /* When debugging, enable the following code. This cannot be used
- in production compilers because it calls "system". */
-#if 0
- FILE *file = fopen ("/tmp/rdg.dot", "w");
- gcc_assert (file != NULL);
-
- dot_rdg_1 (file, rdg);
- fclose (file);
-
- system ("dotty /tmp/rdg.dot &");
-#else
- dot_rdg_1 (stderr, rdg);
-#endif
-}
-
-/* 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))
- {
- data_reference_p tmp = dra;
- dra = drb;
- drb = tmp;
- }
-
- 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;
- else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
- RDGE_TYPE (e) = output_dd;
- else if (DR_IS_WRITE (dra) && DR_IS_READ (drb))
- RDGE_TYPE (e) = flow_dd;
- else if (DR_IS_READ (dra) && DR_IS_WRITE (drb))
- RDGE_TYPE (e) = anti_dd;
-}
-
-/* Creates dependence edges in RDG for all the uses of DEF. IDEF is
- the index of DEF in RDG. */
-
-static void
-create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
-{
- use_operand_p imm_use_p;
- imm_use_iterator iterator;
-
- FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
- {
- 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;
- }
-}
-
-/* Creates the edges of the reduced dependence graph RDG. */
-
-static void
-create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
-{
- int i;
- struct data_dependence_relation *ddr;
- def_operand_p def_p;
- ssa_op_iter iter;
-
- FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- create_rdg_edge_for_ddr (rdg, ddr);
-
- for (i = 0; i < rdg->n_vertices; i++)
- 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. */
-
-void
-create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
-{
- int i, j;
- gimple stmt;
-
- FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
- {
- 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);
- 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_EACH_VEC_ELT (data_ref_loc, references, j, ref)
- 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 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 (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;
- gimple stmt;
-
- for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
- VEC_safe_push (gimple, heap, *stmts, gsi_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 && !is_gimple_debug (stmt))
- VEC_safe_push (gimple, heap, *stmts, stmt);
- }
- }
-
- free (bbs);
-}
-
-/* Returns true when all the dependences are computable. */
-
-static bool
-known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
-{
- ddr_p ddr;
- unsigned int i;
-
- FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
- if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
- return false;
-
- return true;
-}
-
-/* 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;
+ if (loop->inner)
+ {
+ loop = loop->inner;
+ while (loop)
+ {
+ if (loop_nest_has_data_refs (loop))
+ return true;
+ loop = loop->next;
+ }
+ }
+ return false;
}
-/* Free the element E. */
+/* 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 void
-hash_stmt_vertex_del (void *e)
+bool
+find_data_references_in_stmt (struct loop *nest, gimple *stmt,
+ vec<data_reference_p> *datarefs)
{
- 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. */
+ unsigned i;
+ auto_vec<data_ref_loc, 2> references;
+ data_ref_loc *ref;
+ bool ret = true;
+ data_reference_p dr;
-struct graph *
-build_empty_rdg (int n_stmts)
-{
- int nb_data_refs = 10;
- struct graph *rdg = new_graph (n_stmts);
+ if (get_references_in_stmt (stmt, &references))
+ return false;
- rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
- eq_stmt_vertex_info, hash_stmt_vertex_del);
- return rdg;
+ FOR_EACH_VEC_ELT (references, i, ref)
+ {
+ dr = create_data_ref (nest, loop_containing_stmt (stmt),
+ ref->ref, stmt, ref->is_read);
+ gcc_assert (dr != NULL);
+ datarefs->safe_push (dr);
+ }
+ references.release ();
+ return ret;
}
-/* Build the Reduced Dependence Graph (RDG) with one vertex per
- statement of the loop nest, and one edge per data dependence or
- scalar dependence. */
+/* Stores the data references in STMT to DATAREFS. If there is an
+ unanalyzable reference, returns false, otherwise returns true.
+ NEST is the outermost loop of the loop nest in which the references
+ should be instantiated, LOOP is the loop in which the references
+ should be analyzed. */
-struct graph *
-build_rdg (struct loop *loop,
- VEC (loop_p, heap) **loop_nest,
- VEC (ddr_p, heap) **dependence_relations,
- VEC (data_reference_p, heap) **datarefs)
+bool
+graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple *stmt,
+ vec<data_reference_p> *datarefs)
{
- struct graph *rdg = NULL;
+ unsigned i;
+ auto_vec<data_ref_loc, 2> references;
+ data_ref_loc *ref;
+ bool ret = true;
+ data_reference_p dr;
+
+ if (get_references_in_stmt (stmt, &references))
+ return false;
- if (compute_data_dependences_for_loop (loop, false, loop_nest, datarefs,
- dependence_relations)
- && known_dependences_p (*dependence_relations))
+ FOR_EACH_VEC_ELT (references, i, ref)
{
- 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);
+ dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read);
+ gcc_assert (dr != NULL);
+ datarefs->safe_push (dr);
}
- return rdg;
+ references.release ();
+ return ret;
}
-/* Free the reduced dependence graph RDG. */
+/* 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. */
-void
-free_rdg (struct graph *rdg)
+tree
+find_data_references_in_bb (struct loop *loop, basic_block bb,
+ vec<data_reference_p> *datarefs)
{
- int i;
+ gimple_stmt_iterator bsi;
- for (i = 0; i < rdg->n_vertices; i++)
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
{
- struct vertex *v = &(rdg->vertices[i]);
- struct graph_edge *e;
+ gimple *stmt = gsi_stmt (bsi);
- for (e = v->succ; e; e = e->succ_next)
- free (e->data);
+ if (!find_data_references_in_stmt (loop, stmt, datarefs))
+ {
+ struct data_reference *res;
+ res = XCNEW (struct data_reference);
+ datarefs->safe_push (res);
- free (v->data);
+ return chrec_dont_know;
+ }
}
- htab_delete (rdg->indices);
- free_graph (rdg);
+ return NULL_TREE;
}
-/* Initialize STMTS with all the statements of LOOP that contain a
- store to memory. */
+/* 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.
-void
-stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
+ 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> *datarefs)
{
+ basic_block bb, *bbs;
unsigned int i;
- basic_block *bbs = get_loop_body_in_dom_order (loop);
+
+ 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;
+ bb = bbs[i];
- 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));
+ if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know)
+ {
+ free (bbs);
+ return chrec_dont_know;
+ }
}
-
free (bbs);
+
+ return NULL_TREE;
}
-/* Returns true when the statement at STMT is of the form "A[i] = 0"
- that contains a data reference on its LHS with a stride of the same
- size as its unit type. */
+/* Recursive helper function. */
-bool
-stmt_with_adjacent_zero_store_dr_p (gimple stmt)
+static bool
+find_loop_nest_1 (struct loop *loop, vec<loop_p> *loop_nest)
{
- tree lhs, rhs;
- bool res;
- struct data_reference *dr;
-
- if (!stmt
- || !gimple_vdef (stmt)
- || !gimple_assign_single_p (stmt))
- return false;
-
- lhs = gimple_assign_lhs (stmt);
- rhs = gimple_assign_rhs1 (stmt);
+ /* Inner loops of the nest should not contain siblings. Example:
+ when there are two consecutive loops,
- /* If this is a bitfield store bail out. */
- if (TREE_CODE (lhs) == COMPONENT_REF
- && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
- return false;
+ | loop_0
+ | loop_1
+ | A[{0, +, 1}_1]
+ | endloop_1
+ | loop_2
+ | A[{0, +, 1}_2]
+ | endloop_2
+ | endloop_0
- if (!(integer_zerop (rhs) || real_zerop (rhs)))
+ the dependence relation cannot be captured by the distance
+ abstraction. */
+ if (loop->next)
return false;
- dr = XCNEW (struct data_reference);
-
- DR_STMT (dr) = stmt;
- DR_REF (dr) = lhs;
-
- res = dr_analyze_innermost (dr, loop_containing_stmt (stmt))
- && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (lhs));
-
- free_data_ref (dr);
- return res;
+ loop_nest->safe_push (loop);
+ if (loop->inner)
+ return find_loop_nest_1 (loop->inner, loop_nest);
+ return true;
}
-/* Initialize STMTS with all the statements of LOOP that contain a
- store to memory of the form "A[i] = 0". */
+/* Return false when the LOOP is not well nested. Otherwise return
+ true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
+ contain the loops from the outermost to the innermost, as they will
+ appear in the classic distance vector. */
-void
-stores_zero_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
+bool
+find_loop_nest (struct loop *loop, vec<loop_p> *loop_nest)
{
- unsigned int i;
- basic_block bb;
- gimple_stmt_iterator si;
- gimple stmt;
- basic_block *bbs = get_loop_body_in_dom_order (loop);
-
- for (i = 0; i < loop->num_nodes; i++)
- for (bb = bbs[i], si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
- if ((stmt = gsi_stmt (si))
- && stmt_with_adjacent_zero_store_dr_p (stmt))
- VEC_safe_push (gimple, heap, *stmts, gsi_stmt (si));
-
- free (bbs);
+ loop_nest->safe_push (loop);
+ if (loop->inner)
+ return find_loop_nest_1 (loop->inner, loop_nest);
+ return true;
}
-/* For a data reference REF, return the declaration of its base
- address or NULL_TREE if the base is not determined. */
+/* 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. */
-static inline tree
-ref_base_address (gimple stmt, data_ref_loc *ref)
+bool
+compute_data_dependences_for_loop (struct loop *loop,
+ bool compute_self_and_read_read_dependences,
+ vec<loop_p> *loop_nest,
+ vec<data_reference_p> *datarefs,
+ vec<ddr_p> *dependence_relations)
{
- tree base = NULL_TREE;
- tree base_address;
- struct data_reference *dr = XCNEW (struct data_reference);
+ bool res = true;
- DR_STMT (dr) = stmt;
- DR_REF (dr) = *ref->pos;
- dr_analyze_innermost (dr, loop_containing_stmt (stmt));
- base_address = DR_BASE_ADDRESS (dr);
+ memset (&dependence_stats, 0, sizeof (dependence_stats));
- if (!base_address)
- goto end;
+ /* If the loop nest is not well formed, or one of the data references
+ is not computable, give up without spending time to compute other
+ dependences. */
+ if (!loop
+ || !find_loop_nest (loop, loop_nest)
+ || find_data_references_in_loop (loop, datarefs) == chrec_dont_know
+ || !compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
+ compute_self_and_read_read_dependences))
+ res = false;
- switch (TREE_CODE (base_address))
+ if (dump_file && (dump_flags & TDF_STATS))
{
- case ADDR_EXPR:
- base = TREE_OPERAND (base_address, 0);
- break;
-
- default:
- base = base_address;
- break;
- }
+ fprintf (dump_file, "Dependence tester statistics:\n");
- end:
- free_data_ref (dr);
- return base;
-}
+ fprintf (dump_file, "Number of dependence tests: %d\n",
+ dependence_stats.num_dependence_tests);
+ fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
+ dependence_stats.num_dependence_dependent);
+ fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
+ dependence_stats.num_dependence_independent);
+ fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
+ dependence_stats.num_dependence_undetermined);
-/* Determines whether the statement from vertex V of the RDG has a
- definition used outside the loop that contains this statement. */
+ fprintf (dump_file, "Number of subscript tests: %d\n",
+ dependence_stats.num_subscript_tests);
+ fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
+ dependence_stats.num_subscript_undetermined);
+ fprintf (dump_file, "Number of same subscript function: %d\n",
+ dependence_stats.num_same_subscript_function);
-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;
+ fprintf (dump_file, "Number of ziv tests: %d\n",
+ dependence_stats.num_ziv);
+ fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
+ dependence_stats.num_ziv_dependent);
+ fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
+ dependence_stats.num_ziv_independent);
+ fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
+ dependence_stats.num_ziv_unimplemented);
- if (!loop)
- return true;
+ fprintf (dump_file, "Number of siv tests: %d\n",
+ dependence_stats.num_siv);
+ fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
+ dependence_stats.num_siv_dependent);
+ fprintf (dump_file, "Number of siv tests returning independent: %d\n",
+ dependence_stats.num_siv_independent);
+ fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
+ dependence_stats.num_siv_unimplemented);
- 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;
- }
+ fprintf (dump_file, "Number of miv tests: %d\n",
+ dependence_stats.num_miv);
+ fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
+ dependence_stats.num_miv_dependent);
+ fprintf (dump_file, "Number of miv tests returning independent: %d\n",
+ dependence_stats.num_miv_independent);
+ fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
+ dependence_stats.num_miv_unimplemented);
}
- return false;
+ return res;
}
-/* 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. */
+/* Free the memory used by a data dependence relation DDR. */
-bool
-have_similar_memory_accesses (gimple s1, gimple s2)
+void
+free_dependence_relation (struct data_dependence_relation *ddr)
{
- 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_EACH_VEC_ELT (data_ref_loc, refs1, i, ref1)
- {
- tree base1 = ref_base_address (s1, ref1);
-
- if (base1)
- FOR_EACH_VEC_ELT (data_ref_loc, refs2, j, ref2)
- 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;
-}
+ if (ddr == NULL)
+ return;
-/* Helper function for the hashtab. */
+ if (DDR_SUBSCRIPTS (ddr).exists ())
+ free_subscripts (DDR_SUBSCRIPTS (ddr));
+ DDR_DIST_VECTS (ddr).release ();
+ DDR_DIR_VECTS (ddr).release ();
-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));
+ free (ddr);
}
-/* Helper function for the hashtab. */
+/* Free the memory used by the data dependence relations from
+ DEPENDENCE_RELATIONS. */
-static hashval_t
-ref_base_address_1 (const void *s)
+void
+free_dependence_relations (vec<ddr_p> dependence_relations)
{
- 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);
+ unsigned int i;
+ struct data_dependence_relation *ddr;
- FOR_EACH_VEC_ELT (data_ref_loc, refs, i, ref)
- if (!ref->is_read)
- {
- res = htab_hash_pointer (ref_base_address (stmt, ref));
- break;
- }
+ FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
+ if (ddr)
+ free_dependence_relation (ddr);
- VEC_free (data_ref_loc, heap, refs);
- return res;
+ dependence_relations.release ();
}
-/* Try to remove duplicated write data references from STMTS. */
+/* Free the memory used by the data references from DATAREFS. */
void
-remove_similar_memory_refs (VEC (gimple, heap) **stmts)
+free_data_refs (vec<data_reference_p> datarefs)
{
- 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++;
- }
- }
+ unsigned int i;
+ struct data_reference *dr;
- htab_delete (seen);
+ FOR_EACH_VEC_ELT (datarefs, i, dr)
+ free_data_ref (dr);
+ datarefs.release ();
}
-
projects / gcc.git / blobdiff