/* Data references and dependences detectors.
- Copyright (C) 2003-2015 Free Software Foundation, Inc.
+ Copyright (C) 2003-2019 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 "hash-set.h"
-#include "machmode.h"
-#include "vec.h"
-#include "double-int.h"
-#include "input.h"
-#include "alias.h"
-#include "symtab.h"
-#include "options.h"
-#include "wide-int.h"
-#include "inchash.h"
+#include "backend.h"
+#include "rtl.h"
#include "tree.h"
+#include "gimple.h"
+#include "gimple-pretty-print.h"
+#include "alias.h"
#include "fold-const.h"
#include "expr.h"
-#include "gimple-pretty-print.h"
-#include "predict.h"
-#include "tm.h"
-#include "hard-reg-set.h"
-#include "input.h"
-#include "function.h"
-#include "dominance.h"
-#include "cfg.h"
-#include "basic-block.h"
-#include "tree-ssa-alias.h"
-#include "internal-fn.h"
-#include "gimple-expr.h"
-#include "is-a.h"
-#include "gimple.h"
#include "gimple-iterator.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "dumpfile.h"
-#include "langhooks.h"
#include "tree-affine.h"
#include "params.h"
+#include "builtins.h"
+#include "tree-eh.h"
+#include "ssa.h"
static struct datadep_stats
{
} dependence_stats;
static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
- struct data_reference *,
- struct data_reference *,
+ unsigned int, unsigned int,
struct loop *);
/* Returns true iff A divides B. */
return ((b % a) == 0);
}
+/* Return true if reference REF contains a union access. */
+
+static bool
+ref_contains_union_access_p (tree ref)
+{
+ while (handled_component_p (ref))
+ {
+ ref = TREE_OPERAND (ref, 0);
+ if (TREE_CODE (TREE_TYPE (ref)) == UNION_TYPE
+ || TREE_CODE (TREE_TYPE (ref)) == QUAL_UNION_TYPE)
+ return true;
+ }
+ return false;
+}
+
\f
/* Dump into FILE all the data references from DATAREFS. */
fprintf (outf, "#(Data Ref: \n");
fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
fprintf (outf, "# stmt: ");
- print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
+ print_gimple_stmt (outf, DR_STMT (dr), 0);
fprintf (outf, "# ref: ");
- print_generic_stmt (outf, DR_REF (dr), 0);
+ print_generic_stmt (outf, DR_REF (dr));
fprintf (outf, "# base_object: ");
- print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
+ print_generic_stmt (outf, DR_BASE_OBJECT (dr));
for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
{
fprintf (outf, "# Access function %d: ", i);
- print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
+ print_generic_stmt (outf, DR_ACCESS_FN (dr, i));
}
fprintf (outf, "#)\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;
/* Dumps the conflict function CF to the file OUTF. */
-static void
+DEBUG_FUNCTION void
dump_conflict_function (FILE *outf, conflict_function *cf)
{
unsigned i;
/* 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);
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
fprintf (outf, "\n last_conflict: ");
- print_generic_expr (outf, last_iteration, 0);
+ print_generic_expr (outf, last_iteration);
}
cf = SUB_CONFLICTS_IN_B (subscript);
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
fprintf (outf, "\n last_conflict: ");
- print_generic_expr (outf, last_iteration, 0);
+ print_generic_expr (outf, last_iteration);
}
fprintf (outf, "\n (Subscript distance: ");
- print_generic_expr (outf, SUB_DISTANCE (subscript), 0);
+ print_generic_expr (outf, SUB_DISTANCE (subscript));
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
+DEBUG_FUNCTION void
print_dir_vectors (FILE *outf, vec<lambda_vector> dir_vects,
int 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;
for (i = 0; i < n; i++)
- fprintf (outfile, "%3d ", vector[i]);
+ fprintf (outfile, "%3d ", (int)vector[i]);
fprintf (outfile, "\n");
}
/* Print a vector of distance vectors. */
-static void
+DEBUG_FUNCTION void
print_dist_vectors (FILE *outf, vec<lambda_vector> dist_vects,
int 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)
{
unsigned int i;
struct loop *loopi;
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ subscript *sub;
+ FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr), i, sub)
{
fprintf (outf, " access_fn_A: ");
- print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
+ print_generic_stmt (outf, SUB_ACCESS_FN (sub, 0));
fprintf (outf, " access_fn_B: ");
- print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
- dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
+ print_generic_stmt (outf, SUB_ACCESS_FN (sub, 1));
+ dump_subscript (outf, sub);
}
- fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
fprintf (outf, " loop nest: (");
FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr), i, loopi)
fprintf (outf, "%d ", loopi->num);
/* Dump into FILE all the dependence relations from DDRS. */
-void
+DEBUG_FUNCTION void
dump_data_dependence_relations (FILE *file,
vec<ddr_p> ddrs)
{
dependence vectors, or in other words the number of loops in the
considered nest. */
-static void
+DEBUG_FUNCTION void
dump_dist_dir_vectors (FILE *file, vec<ddr_p> ddrs)
{
unsigned int i, j;
/* Dumps the data dependence relations DDRS in FILE. */
-static void
+DEBUG_FUNCTION void
dump_ddrs (FILE *file, vec<ddr_p> ddrs)
{
unsigned int i;
dump_ddrs (stderr, ddrs);
}
+static void
+split_constant_offset (tree exp, tree *var, tree *off,
+ hash_map<tree, std::pair<tree, tree> > &cache);
+
/* Helper function for split_constant_offset. Expresses OP0 CODE OP1
(the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
constant of type ssizetype, and returns true. If we cannot do this
static bool
split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
- tree *var, tree *off)
+ tree *var, tree *off,
+ hash_map<tree, std::pair<tree, tree> > &cache)
{
tree var0, var1;
tree off0, off1;
/* FALLTHROUGH */
case PLUS_EXPR:
case MINUS_EXPR:
- split_constant_offset (op0, &var0, &off0);
- split_constant_offset (op1, &var1, &off1);
+ split_constant_offset (op0, &var0, &off0, cache);
+ split_constant_offset (op1, &var1, &off1, cache);
*var = fold_build2 (code, type, var0, var1);
*off = size_binop (ocode, off0, off1);
return true;
if (TREE_CODE (op1) != INTEGER_CST)
return false;
- split_constant_offset (op0, &var0, &off0);
+ split_constant_offset (op0, &var0, &off0, cache);
*var = fold_build2 (MULT_EXPR, type, var0, op1);
*off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
return true;
case ADDR_EXPR:
{
tree base, poffset;
- HOST_WIDE_INT pbitsize, pbitpos;
+ poly_int64 pbitsize, pbitpos, pbytepos;
machine_mode pmode;
- int punsignedp, pvolatilep;
+ 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);
- if (pbitpos % BITS_PER_UNIT != 0)
+ if (!multiple_p (pbitpos, BITS_PER_UNIT, &pbytepos))
return false;
base = build_fold_addr_expr (base);
- off0 = ssize_int (pbitpos / BITS_PER_UNIT);
+ off0 = ssize_int (pbytepos);
if (poffset)
{
- split_constant_offset (poffset, &poffset, &off1);
+ split_constant_offset (poffset, &poffset, &off1, cache);
off0 = size_binop (PLUS_EXPR, off0, off1);
if (POINTER_TYPE_P (TREE_TYPE (base)))
base = fold_build_pointer_plus (base, poffset);
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
return false;
- gimple def_stmt = SSA_NAME_DEF_STMT (op0);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
enum tree_code subcode;
if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
return false;
- var0 = gimple_assign_rhs1 (def_stmt);
subcode = gimple_assign_rhs_code (def_stmt);
+
+ /* We are using a cache to avoid un-CSEing large amounts of code. */
+ bool use_cache = false;
+ if (!has_single_use (op0)
+ && (subcode == POINTER_PLUS_EXPR
+ || subcode == PLUS_EXPR
+ || subcode == MINUS_EXPR
+ || subcode == MULT_EXPR
+ || subcode == ADDR_EXPR
+ || CONVERT_EXPR_CODE_P (subcode)))
+ {
+ use_cache = true;
+ bool existed;
+ std::pair<tree, tree> &e = cache.get_or_insert (op0, &existed);
+ if (existed)
+ {
+ if (integer_zerop (e.second))
+ return false;
+ *var = e.first;
+ *off = e.second;
+ return true;
+ }
+ e = std::make_pair (op0, ssize_int (0));
+ }
+
+ var0 = gimple_assign_rhs1 (def_stmt);
var1 = gimple_assign_rhs2 (def_stmt);
- return split_constant_offset_1 (type, var0, subcode, var1, var, off);
+ bool res = split_constant_offset_1 (type, var0, subcode, var1,
+ var, off, cache);
+ if (res && use_cache)
+ *cache.get (op0) = std::make_pair (*var, *off);
+ return res;
}
CASE_CONVERT:
{
- /* We must not introduce undefined overflow, and we must not change the value.
- Hence we're okay if the inner type doesn't overflow to start with
- (pointer or signed), the outer type also is an integer or pointer
- and the outer precision is at least as large as the inner. */
+ /* We must not introduce undefined overflow, and we must not change
+ the value. Hence we're okay if the inner type doesn't overflow
+ to start with (pointer or signed), the outer type also is an
+ integer or pointer and the outer precision is at least as large
+ as the inner. */
tree itype = TREE_TYPE (op0);
if ((POINTER_TYPE_P (itype)
- || (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_UNDEFINED (itype)))
+ || (INTEGRAL_TYPE_P (itype) && !TYPE_OVERFLOW_TRAPS (itype)))
&& TYPE_PRECISION (type) >= TYPE_PRECISION (itype)
&& (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type)))
{
- split_constant_offset (op0, &var0, off);
+ if (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_WRAPS (itype))
+ {
+ /* Split the unconverted operand and try to prove that
+ wrapping isn't a problem. */
+ tree tmp_var, tmp_off;
+ split_constant_offset (op0, &tmp_var, &tmp_off, cache);
+
+ /* See whether we have an SSA_NAME whose range is known
+ to be [A, B]. */
+ if (TREE_CODE (tmp_var) != SSA_NAME)
+ return false;
+ wide_int var_min, var_max;
+ value_range_kind vr_type = get_range_info (tmp_var, &var_min,
+ &var_max);
+ wide_int var_nonzero = get_nonzero_bits (tmp_var);
+ signop sgn = TYPE_SIGN (itype);
+ if (intersect_range_with_nonzero_bits (vr_type, &var_min,
+ &var_max, var_nonzero,
+ sgn) != VR_RANGE)
+ return false;
+
+ /* See whether the range of OP0 (i.e. TMP_VAR + TMP_OFF)
+ is known to be [A + TMP_OFF, B + TMP_OFF], with all
+ operations done in ITYPE. The addition must overflow
+ at both ends of the range or at neither. */
+ wi::overflow_type overflow[2];
+ unsigned int prec = TYPE_PRECISION (itype);
+ wide_int woff = wi::to_wide (tmp_off, prec);
+ wide_int op0_min = wi::add (var_min, woff, sgn, &overflow[0]);
+ wi::add (var_max, woff, sgn, &overflow[1]);
+ if ((overflow[0] != wi::OVF_NONE) != (overflow[1] != wi::OVF_NONE))
+ return false;
+
+ /* Calculate (ssizetype) OP0 - (ssizetype) TMP_VAR. */
+ widest_int diff = (widest_int::from (op0_min, sgn)
+ - widest_int::from (var_min, sgn));
+ var0 = tmp_var;
+ *off = wide_int_to_tree (ssizetype, diff);
+ }
+ else
+ split_constant_offset (op0, &var0, off, cache);
*var = fold_convert (type, var0);
return true;
}
/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
will be ssizetype. */
-void
-split_constant_offset (tree exp, tree *var, tree *off)
+static void
+split_constant_offset (tree exp, tree *var, tree *off,
+ hash_map<tree, std::pair<tree, tree> > &cache)
{
- tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
+ tree type = TREE_TYPE (exp), op0, op1, e, o;
enum tree_code code;
*var = exp;
*off = ssize_int (0);
- STRIP_NOPS (exp);
if (tree_is_chrec (exp)
|| get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS)
return;
- otype = TREE_TYPE (exp);
code = TREE_CODE (exp);
extract_ops_from_tree (exp, &code, &op0, &op1);
- if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
+ if (split_constant_offset_1 (type, op0, code, op1, &e, &o, cache))
{
- *var = fold_convert (type, e);
+ *var = e;
*off = o;
}
}
+void
+split_constant_offset (tree exp, tree *var, tree *off)
+{
+ static hash_map<tree, std::pair<tree, tree> > *cache;
+ if (!cache)
+ cache = new hash_map<tree, std::pair<tree, tree> > (37);
+ split_constant_offset (exp, var, off, *cache);
+ cache->empty ();
+}
+
/* Returns the address ADDR of an object in a canonical shape (without nop
casts, and with type of pointer to the object). */
return build_fold_addr_expr (TREE_OPERAND (addr, 0));
}
-/* Analyzes the behavior of the memory reference DR in the innermost loop or
- basic block that contains it. Returns true if analysis succeed or false
- otherwise. */
+/* Analyze the behavior of memory reference REF within STMT.
+ There are two modes:
-bool
-dr_analyze_innermost (struct data_reference *dr, struct loop *nest)
+ - BB analysis. In this case we simply split the address into base,
+ init and offset components, without reference to any containing loop.
+ The resulting base and offset are general expressions and they can
+ vary arbitrarily from one iteration of the containing loop to the next.
+ The step is always zero.
+
+ - loop analysis. In this case we analyze the reference both wrt LOOP
+ and on the basis that the reference occurs (is "used") in LOOP;
+ see the comment above analyze_scalar_evolution_in_loop for more
+ information about this distinction. The base, init, offset and
+ step fields are all invariant in LOOP.
+
+ Perform BB analysis if LOOP is null, or if LOOP is the function's
+ dummy outermost loop. In other cases perform loop analysis.
+
+ Return true if the analysis succeeded and store the results in DRB if so.
+ BB analysis can only fail for bitfield or reversed-storage accesses. */
+
+opt_result
+dr_analyze_innermost (innermost_loop_behavior *drb, tree ref,
+ struct loop *loop, const gimple *stmt)
{
- gimple stmt = DR_STMT (dr);
- struct loop *loop = loop_containing_stmt (stmt);
- tree ref = DR_REF (dr);
- HOST_WIDE_INT pbitsize, pbitpos;
+ poly_int64 pbitsize, pbitpos;
tree base, poffset;
machine_mode pmode;
- int punsignedp, pvolatilep;
+ 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);
gcc_assert (base != NULL_TREE);
- if (pbitpos % BITS_PER_UNIT != 0)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "failed: bit offset alignment.\n");
- return false;
- }
+ poly_int64 pbytepos;
+ if (!multiple_p (pbitpos, BITS_PER_UNIT, &pbytepos))
+ return opt_result::failure_at (stmt,
+ "failed: bit offset alignment.\n");
+
+ if (preversep)
+ return opt_result::failure_at (stmt,
+ "failed: reverse storage order.\n");
+
+ /* Calculate the alignment and misalignment for the inner reference. */
+ unsigned int HOST_WIDE_INT bit_base_misalignment;
+ unsigned int bit_base_alignment;
+ get_object_alignment_1 (base, &bit_base_alignment, &bit_base_misalignment);
+
+ /* There are no bitfield references remaining in BASE, so the values
+ we got back must be whole bytes. */
+ gcc_assert (bit_base_alignment % BITS_PER_UNIT == 0
+ && bit_base_misalignment % BITS_PER_UNIT == 0);
+ unsigned int base_alignment = bit_base_alignment / BITS_PER_UNIT;
+ poly_int64 base_misalignment = bit_base_misalignment / BITS_PER_UNIT;
if (TREE_CODE (base) == MEM_REF)
{
if (!integer_zerop (TREE_OPERAND (base, 1)))
{
- offset_int moff = mem_ref_offset (base);
+ /* Subtract MOFF from the base and add it to POFFSET instead.
+ Adjust the misalignment to reflect the amount we subtracted. */
+ poly_offset_int moff = mem_ref_offset (base);
+ base_misalignment -= moff.force_shwi ();
tree mofft = wide_int_to_tree (sizetype, moff);
if (!poffset)
poffset = mofft;
if (in_loop)
{
- if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
- nest ? true : false))
- {
- if (nest)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "failed: evolution of base is not"
- " affine.\n");
- return false;
- }
- else
- {
- base_iv.base = base;
- base_iv.step = ssize_int (0);
- base_iv.no_overflow = true;
- }
- }
+ if (!simple_iv (loop, loop, base, &base_iv, true))
+ return opt_result::failure_at
+ (stmt, "failed: evolution of base is not affine.\n");
}
else
{
offset_iv.base = poffset;
offset_iv.step = ssize_int (0);
}
- else if (!simple_iv (loop, loop_containing_stmt (stmt),
- poffset, &offset_iv,
- nest ? true : false))
- {
- if (nest)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "failed: evolution of offset is not"
- " affine.\n");
- return false;
- }
- else
- {
- offset_iv.base = poffset;
- offset_iv.step = ssize_int (0);
- }
- }
+ else if (!simple_iv (loop, loop, poffset, &offset_iv, true))
+ return opt_result::failure_at
+ (stmt, "failed: evolution of offset is not affine.\n");
}
- init = ssize_int (pbitpos / BITS_PER_UNIT);
+ init = ssize_int (pbytepos);
+
+ /* Subtract any constant component from the base and add it to INIT instead.
+ Adjust the misalignment to reflect the amount we subtracted. */
split_constant_offset (base_iv.base, &base_iv.base, &dinit);
- init = size_binop (PLUS_EXPR, init, dinit);
+ init = size_binop (PLUS_EXPR, init, dinit);
+ base_misalignment -= TREE_INT_CST_LOW (dinit);
+
split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
- init = size_binop (PLUS_EXPR, init, dinit);
+ init = size_binop (PLUS_EXPR, init, dinit);
step = size_binop (PLUS_EXPR,
fold_convert (ssizetype, base_iv.step),
fold_convert (ssizetype, offset_iv.step));
- DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
+ base = canonicalize_base_object_address (base_iv.base);
- DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
- DR_INIT (dr) = init;
- DR_STEP (dr) = step;
+ /* See if get_pointer_alignment can guarantee a higher alignment than
+ the one we calculated above. */
+ unsigned int HOST_WIDE_INT alt_misalignment;
+ unsigned int alt_alignment;
+ get_pointer_alignment_1 (base, &alt_alignment, &alt_misalignment);
- DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
+ /* As above, these values must be whole bytes. */
+ gcc_assert (alt_alignment % BITS_PER_UNIT == 0
+ && alt_misalignment % BITS_PER_UNIT == 0);
+ alt_alignment /= BITS_PER_UNIT;
+ alt_misalignment /= BITS_PER_UNIT;
+
+ if (base_alignment < alt_alignment)
+ {
+ base_alignment = alt_alignment;
+ base_misalignment = alt_misalignment;
+ }
+
+ drb->base_address = base;
+ drb->offset = fold_convert (ssizetype, offset_iv.base);
+ drb->init = init;
+ drb->step = step;
+ if (known_misalignment (base_misalignment, base_alignment,
+ &drb->base_misalignment))
+ drb->base_alignment = base_alignment;
+ else
+ {
+ drb->base_alignment = known_alignment (base_misalignment);
+ drb->base_misalignment = 0;
+ }
+ drb->offset_alignment = highest_pow2_factor (offset_iv.base);
+ drb->step_alignment = highest_pow2_factor (step);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "success.\n");
- return true;
+ return opt_result::success ();
+}
+
+/* Return true if OP is a valid component reference for a DR access
+ function. This accepts a subset of what handled_component_p accepts. */
+
+static bool
+access_fn_component_p (tree op)
+{
+ switch (TREE_CODE (op))
+ {
+ case REALPART_EXPR:
+ case IMAGPART_EXPR:
+ case ARRAY_REF:
+ return true;
+
+ case COMPONENT_REF:
+ return TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == RECORD_TYPE;
+
+ default:
+ return false;
+ }
}
/* Determines the base object and the list of indices of memory reference
- DR, analyzed in LOOP and instantiated in loop nest NEST. */
+ DR, analyzed in LOOP and instantiated before NEST. */
static void
-dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
+dr_analyze_indices (struct data_reference *dr, edge nest, loop_p loop)
{
vec<tree> access_fns = vNULL;
tree ref, op;
tree base, off, access_fn;
- basic_block before_loop;
/* If analyzing a basic-block there are no indices to analyze
and thus no access functions. */
}
ref = DR_REF (dr);
- before_loop = block_before_loop (nest);
/* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
into a two element array with a constant index. The base is
access_fns.safe_push (integer_one_node);
}
- /* Analyze access functions of dimensions we know to be independent. */
+ /* Analyze access functions of dimensions we know to be independent.
+ The list of component references handled here should be kept in
+ sync with access_fn_component_p. */
while (handled_component_p (ref))
{
if (TREE_CODE (ref) == ARRAY_REF)
{
op = TREE_OPERAND (ref, 1);
access_fn = analyze_scalar_evolution (loop, op);
- access_fn = instantiate_scev (before_loop, loop, access_fn);
+ access_fn = instantiate_scev (nest, loop, access_fn);
access_fns.safe_push (access_fn);
}
else if (TREE_CODE (ref) == COMPONENT_REF
{
op = TREE_OPERAND (ref, 0);
access_fn = analyze_scalar_evolution (loop, op);
- access_fn = instantiate_scev (before_loop, loop, access_fn);
+ access_fn = instantiate_scev (nest, loop, access_fn);
if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
{
tree orig_type;
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
+ (wi::to_wide (off),
+ wi::to_wide (TYPE_SIZE_UNIT (TREE_TYPE (ref))),
+ SIGNED);
+ else
+ /* If we can't compute the remainder simply force the initial
+ condition to zero. */
+ rem = wi::to_wide (off);
+ off = wide_int_to_tree (ssizetype, wi::to_wide (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
base, memoff);
MR_DEPENDENCE_CLIQUE (ref) = MR_DEPENDENCE_CLIQUE (old);
MR_DEPENDENCE_BASE (ref) = MR_DEPENDENCE_BASE (old);
+ DR_UNCONSTRAINED_BASE (dr) = true;
access_fns.safe_push (access_fn);
}
}
free (dr);
}
-/* Analyzes memory reference MEMREF accessed in STMT. The reference
- is read if IS_READ is true, write otherwise. Returns the
- data_reference description of MEMREF. NEST is the outermost loop
- in which the reference should be instantiated, LOOP is the loop in
- which the data reference should be analyzed. */
+/* Analyze memory reference MEMREF, which is accessed in STMT.
+ The reference is a read if IS_READ is true, otherwise it is a write.
+ IS_CONDITIONAL_IN_STMT indicates that the reference is conditional
+ within STMT, i.e. that it might not occur even if STMT is executed
+ and runs to completion.
+
+ Return the data_reference description of MEMREF. NEST is the outermost
+ loop in which the reference should be instantiated, LOOP is the loop
+ in which the data reference should be analyzed. */
struct data_reference *
-create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
- bool is_read)
+create_data_ref (edge nest, loop_p loop, tree memref, gimple *stmt,
+ bool is_read, bool is_conditional_in_stmt)
{
struct data_reference *dr;
DR_STMT (dr) = stmt;
DR_REF (dr) = memref;
DR_IS_READ (dr) = is_read;
+ DR_IS_CONDITIONAL_IN_STMT (dr) = is_conditional_in_stmt;
- dr_analyze_innermost (dr, nest);
+ dr_analyze_innermost (&DR_INNERMOST (dr), memref,
+ nest != NULL ? loop : NULL, stmt);
dr_analyze_indices (dr, nest, loop);
dr_analyze_alias (dr);
print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
fprintf (dump_file, "\n\tstep: ");
print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
- fprintf (dump_file, "\n\taligned to: ");
- print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
+ fprintf (dump_file, "\n\tbase alignment: %d", DR_BASE_ALIGNMENT (dr));
+ fprintf (dump_file, "\n\tbase misalignment: %d",
+ DR_BASE_MISALIGNMENT (dr));
+ fprintf (dump_file, "\n\toffset alignment: %d",
+ DR_OFFSET_ALIGNMENT (dr));
+ fprintf (dump_file, "\n\tstep alignment: %d", DR_STEP_ALIGNMENT (dr));
fprintf (dump_file, "\n\tbase_object: ");
print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
fprintf (dump_file, "\n");
return dr;
}
-/* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
- expressions. */
-static bool
-dr_equal_offsets_p1 (tree offset1, tree offset2)
+/* A helper function computes order between two tree expressions T1 and T2.
+ This is used in comparator functions sorting objects based on the order
+ of tree expressions. The function returns -1, 0, or 1. */
+
+int
+data_ref_compare_tree (tree t1, tree t2)
{
- bool res;
+ int i, cmp;
+ enum tree_code code;
+ char tclass;
- STRIP_NOPS (offset1);
- STRIP_NOPS (offset2);
+ if (t1 == t2)
+ return 0;
+ if (t1 == NULL)
+ return -1;
+ if (t2 == NULL)
+ return 1;
- if (offset1 == offset2)
- return true;
+ STRIP_USELESS_TYPE_CONVERSION (t1);
+ STRIP_USELESS_TYPE_CONVERSION (t2);
+ if (t1 == t2)
+ return 0;
- if (TREE_CODE (offset1) != TREE_CODE (offset2)
- || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
- return false;
+ if (TREE_CODE (t1) != TREE_CODE (t2)
+ && ! (CONVERT_EXPR_P (t1) && CONVERT_EXPR_P (t2)))
+ return TREE_CODE (t1) < TREE_CODE (t2) ? -1 : 1;
- res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
- TREE_OPERAND (offset2, 0));
+ code = TREE_CODE (t1);
+ switch (code)
+ {
+ case INTEGER_CST:
+ return tree_int_cst_compare (t1, t2);
- if (!res || !BINARY_CLASS_P (offset1))
- return res;
+ case STRING_CST:
+ if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
+ return TREE_STRING_LENGTH (t1) < TREE_STRING_LENGTH (t2) ? -1 : 1;
+ return memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
+ TREE_STRING_LENGTH (t1));
- res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
- TREE_OPERAND (offset2, 1));
+ case SSA_NAME:
+ if (SSA_NAME_VERSION (t1) != SSA_NAME_VERSION (t2))
+ return SSA_NAME_VERSION (t1) < SSA_NAME_VERSION (t2) ? -1 : 1;
+ break;
- return res;
-}
+ default:
+ if (POLY_INT_CST_P (t1))
+ return compare_sizes_for_sort (wi::to_poly_widest (t1),
+ wi::to_poly_widest (t2));
-/* Check if DRA and DRB have equal offsets. */
-bool
-dr_equal_offsets_p (struct data_reference *dra,
- struct data_reference *drb)
-{
- tree offset1, offset2;
+ tclass = TREE_CODE_CLASS (code);
- offset1 = DR_OFFSET (dra);
- offset2 = DR_OFFSET (drb);
+ /* For decls, compare their UIDs. */
+ if (tclass == tcc_declaration)
+ {
+ if (DECL_UID (t1) != DECL_UID (t2))
+ return DECL_UID (t1) < DECL_UID (t2) ? -1 : 1;
+ break;
+ }
+ /* For expressions, compare their operands recursively. */
+ else if (IS_EXPR_CODE_CLASS (tclass))
+ {
+ for (i = TREE_OPERAND_LENGTH (t1) - 1; i >= 0; --i)
+ {
+ cmp = data_ref_compare_tree (TREE_OPERAND (t1, i),
+ TREE_OPERAND (t2, i));
+ if (cmp != 0)
+ return cmp;
+ }
+ }
+ else
+ gcc_unreachable ();
+ }
- return dr_equal_offsets_p1 (offset1, offset2);
+ return 0;
}
-/* Returns true if FNA == FNB. */
+/* Return TRUE it's possible to resolve data dependence DDR by runtime alias
+ check. */
-static bool
-affine_function_equal_p (affine_fn fna, affine_fn fnb)
+opt_result
+runtime_alias_check_p (ddr_p ddr, struct loop *loop, bool speed_p)
{
- unsigned i, n = fna.length ();
+ if (dump_enabled_p ())
+ dump_printf (MSG_NOTE,
+ "consider run-time aliasing test between %T and %T\n",
+ DR_REF (DDR_A (ddr)), DR_REF (DDR_B (ddr)));
+
+ if (!speed_p)
+ return opt_result::failure_at (DR_STMT (DDR_A (ddr)),
+ "runtime alias check not supported when"
+ " optimizing for size.\n");
+
+ /* FORNOW: We don't support versioning with outer-loop in either
+ vectorization or loop distribution. */
+ if (loop != NULL && loop->inner != NULL)
+ return opt_result::failure_at (DR_STMT (DDR_A (ddr)),
+ "runtime alias check not supported for"
+ " outer loop.\n");
+
+ return opt_result::success ();
+}
- if (n != fnb.length ())
- return false;
+/* Operator == between two dr_with_seg_len objects.
- for (i = 0; i < n; i++)
- if (!operand_equal_p (fna[i], fnb[i], 0))
- return false;
+ This equality operator is used to make sure two data refs
+ are the same one so that we will consider to combine the
+ aliasing checks of those two pairs of data dependent data
+ refs. */
- return true;
+static bool
+operator == (const dr_with_seg_len& d1,
+ const dr_with_seg_len& d2)
+{
+ return (operand_equal_p (DR_BASE_ADDRESS (d1.dr),
+ DR_BASE_ADDRESS (d2.dr), 0)
+ && data_ref_compare_tree (DR_OFFSET (d1.dr), DR_OFFSET (d2.dr)) == 0
+ && data_ref_compare_tree (DR_INIT (d1.dr), DR_INIT (d2.dr)) == 0
+ && data_ref_compare_tree (d1.seg_len, d2.seg_len) == 0
+ && known_eq (d1.access_size, d2.access_size)
+ && d1.align == d2.align);
}
-/* If all the functions in CF are the same, returns one of them,
- otherwise returns NULL. */
+/* Comparison function for sorting objects of dr_with_seg_len_pair_t
+ so that we can combine aliasing checks in one scan. */
-static affine_fn
-common_affine_function (conflict_function *cf)
+static int
+comp_dr_with_seg_len_pair (const void *pa_, const void *pb_)
{
- unsigned i;
- affine_fn comm;
+ const dr_with_seg_len_pair_t* pa = (const dr_with_seg_len_pair_t *) pa_;
+ const dr_with_seg_len_pair_t* pb = (const dr_with_seg_len_pair_t *) pb_;
+ const dr_with_seg_len &a1 = pa->first, &a2 = pa->second;
+ const dr_with_seg_len &b1 = pb->first, &b2 = pb->second;
+
+ /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks
+ if a and c have the same basic address snd step, and b and d have the same
+ address and step. Therefore, if any a&c or b&d don't have the same address
+ and step, we don't care the order of those two pairs after sorting. */
+ int comp_res;
+
+ if ((comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (a1.dr),
+ DR_BASE_ADDRESS (b1.dr))) != 0)
+ return comp_res;
+ if ((comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (a2.dr),
+ DR_BASE_ADDRESS (b2.dr))) != 0)
+ return comp_res;
+ if ((comp_res = data_ref_compare_tree (DR_STEP (a1.dr),
+ DR_STEP (b1.dr))) != 0)
+ return comp_res;
+ if ((comp_res = data_ref_compare_tree (DR_STEP (a2.dr),
+ DR_STEP (b2.dr))) != 0)
+ return comp_res;
+ if ((comp_res = data_ref_compare_tree (DR_OFFSET (a1.dr),
+ DR_OFFSET (b1.dr))) != 0)
+ return comp_res;
+ if ((comp_res = data_ref_compare_tree (DR_INIT (a1.dr),
+ DR_INIT (b1.dr))) != 0)
+ return comp_res;
+ if ((comp_res = data_ref_compare_tree (DR_OFFSET (a2.dr),
+ DR_OFFSET (b2.dr))) != 0)
+ return comp_res;
+ if ((comp_res = data_ref_compare_tree (DR_INIT (a2.dr),
+ DR_INIT (b2.dr))) != 0)
+ return comp_res;
+
+ return 0;
+}
- if (!CF_NONTRIVIAL_P (cf))
- return affine_fn ();
+/* Merge alias checks recorded in ALIAS_PAIRS and remove redundant ones.
+ FACTOR is number of iterations that each data reference is accessed.
- comm = cf->fns[0];
+ Basically, for each pair of dependent data refs store_ptr_0 & load_ptr_0,
+ we create an expression:
- for (i = 1; i < cf->n; i++)
- if (!affine_function_equal_p (comm, cf->fns[i]))
- return affine_fn ();
+ ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
+ || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
- return comm;
-}
+ for aliasing checks. However, in some cases we can decrease the number
+ of checks by combining two checks into one. For example, suppose we have
+ another pair of data refs store_ptr_0 & load_ptr_1, and if the following
+ condition is satisfied:
-/* Returns the base of the affine function FN. */
+ load_ptr_0 < load_ptr_1 &&
+ load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0
-static tree
-affine_function_base (affine_fn fn)
-{
- return fn[0];
-}
+ (this condition means, in each iteration of vectorized loop, the accessed
+ memory of store_ptr_0 cannot be between the memory of load_ptr_0 and
+ load_ptr_1.)
-/* Returns true if FN is a constant. */
+ we then can use only the following expression to finish the alising checks
+ between store_ptr_0 & load_ptr_0 and store_ptr_0 & load_ptr_1:
-static bool
-affine_function_constant_p (affine_fn fn)
+ ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
+ || (load_ptr_1 + load_segment_length_1 <= store_ptr_0))
+
+ Note that we only consider that load_ptr_0 and load_ptr_1 have the same
+ basic address. */
+
+void
+prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs,
+ poly_uint64)
{
- unsigned i;
- tree coef;
+ /* Sort the collected data ref pairs so that we can scan them once to
+ combine all possible aliasing checks. */
+ alias_pairs->qsort (comp_dr_with_seg_len_pair);
- for (i = 1; fn.iterate (i, &coef); i++)
- if (!integer_zerop (coef))
- return false;
+ /* Scan the sorted dr pairs and check if we can combine alias checks
+ of two neighboring dr pairs. */
+ for (size_t i = 1; i < alias_pairs->length (); ++i)
+ {
+ /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2). */
+ dr_with_seg_len *dr_a1 = &(*alias_pairs)[i-1].first,
+ *dr_b1 = &(*alias_pairs)[i-1].second,
+ *dr_a2 = &(*alias_pairs)[i].first,
+ *dr_b2 = &(*alias_pairs)[i].second;
+
+ /* Remove duplicate data ref pairs. */
+ if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2)
+ {
+ if (dump_enabled_p ())
+ dump_printf (MSG_NOTE, "found equal ranges %T, %T and %T, %T\n",
+ DR_REF (dr_a1->dr), DR_REF (dr_b1->dr),
+ DR_REF (dr_a2->dr), DR_REF (dr_b2->dr));
+ alias_pairs->ordered_remove (i--);
+ continue;
+ }
- return true;
-}
+ if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2)
+ {
+ /* We consider the case that DR_B1 and DR_B2 are same memrefs,
+ and DR_A1 and DR_A2 are two consecutive memrefs. */
+ if (*dr_a1 == *dr_a2)
+ {
+ std::swap (dr_a1, dr_b1);
+ std::swap (dr_a2, dr_b2);
+ }
-/* Returns true if FN is the zero constant function. */
+ poly_int64 init_a1, init_a2;
+ /* Only consider cases in which the distance between the initial
+ DR_A1 and the initial DR_A2 is known at compile time. */
+ if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
+ DR_BASE_ADDRESS (dr_a2->dr), 0)
+ || !operand_equal_p (DR_OFFSET (dr_a1->dr),
+ DR_OFFSET (dr_a2->dr), 0)
+ || !poly_int_tree_p (DR_INIT (dr_a1->dr), &init_a1)
+ || !poly_int_tree_p (DR_INIT (dr_a2->dr), &init_a2))
+ continue;
+
+ /* Don't combine if we can't tell which one comes first. */
+ if (!ordered_p (init_a1, init_a2))
+ continue;
+
+ /* Make sure dr_a1 starts left of dr_a2. */
+ if (maybe_gt (init_a1, init_a2))
+ {
+ std::swap (*dr_a1, *dr_a2);
+ std::swap (init_a1, init_a2);
+ }
-static bool
-affine_function_zero_p (affine_fn fn)
-{
- return (integer_zerop (affine_function_base (fn))
- && affine_function_constant_p (fn));
-}
+ /* Work out what the segment length would be if we did combine
+ DR_A1 and DR_A2:
-/* Returns a signed integer type with the largest precision from TA
- and TB. */
+ - If DR_A1 and DR_A2 have equal lengths, that length is
+ also the combined length.
-static tree
-signed_type_for_types (tree ta, tree tb)
-{
- if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
- return signed_type_for (ta);
- else
- return signed_type_for (tb);
-}
+ - If DR_A1 and DR_A2 both have negative "lengths", the combined
+ length is the lower bound on those lengths.
-/* Applies operation OP on affine functions FNA and FNB, and returns the
- result. */
+ - If DR_A1 and DR_A2 both have positive lengths, the combined
+ length is the upper bound on those lengths.
-static affine_fn
-affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
-{
- unsigned i, n, m;
- affine_fn ret;
- tree coef;
+ Other cases are unlikely to give a useful combination.
- if (fnb.length () > fna.length ())
- {
- n = fna.length ();
- m = fnb.length ();
- }
- else
- {
- n = fnb.length ();
- m = fna.length ();
- }
+ The lengths both have sizetype, so the sign is taken from
+ the step instead. */
+ if (!operand_equal_p (dr_a1->seg_len, dr_a2->seg_len, 0))
+ {
+ poly_uint64 seg_len_a1, seg_len_a2;
+ if (!poly_int_tree_p (dr_a1->seg_len, &seg_len_a1)
+ || !poly_int_tree_p (dr_a2->seg_len, &seg_len_a2))
+ continue;
+
+ tree indicator_a = dr_direction_indicator (dr_a1->dr);
+ if (TREE_CODE (indicator_a) != INTEGER_CST)
+ continue;
+
+ tree indicator_b = dr_direction_indicator (dr_a2->dr);
+ if (TREE_CODE (indicator_b) != INTEGER_CST)
+ continue;
+
+ int sign_a = tree_int_cst_sgn (indicator_a);
+ int sign_b = tree_int_cst_sgn (indicator_b);
+
+ poly_uint64 new_seg_len;
+ if (sign_a <= 0 && sign_b <= 0)
+ new_seg_len = lower_bound (seg_len_a1, seg_len_a2);
+ else if (sign_a >= 0 && sign_b >= 0)
+ new_seg_len = upper_bound (seg_len_a1, seg_len_a2);
+ else
+ continue;
- ret.create (m);
- for (i = 0; i < n; 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]));
- }
+ dr_a1->seg_len = build_int_cst (TREE_TYPE (dr_a1->seg_len),
+ new_seg_len);
+ dr_a1->align = MIN (dr_a1->align, known_alignment (new_seg_len));
+ }
- for (; fna.iterate (i, &coef); i++)
- ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
- coef, integer_zero_node));
- for (; fnb.iterate (i, &coef); i++)
- ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
- integer_zero_node, coef));
+ /* This is always positive due to the swap above. */
+ poly_uint64 diff = init_a2 - init_a1;
- return ret;
+ /* The new check will start at DR_A1. Make sure that its access
+ size encompasses the initial DR_A2. */
+ if (maybe_lt (dr_a1->access_size, diff + dr_a2->access_size))
+ {
+ dr_a1->access_size = upper_bound (dr_a1->access_size,
+ diff + dr_a2->access_size);
+ unsigned int new_align = known_alignment (dr_a1->access_size);
+ dr_a1->align = MIN (dr_a1->align, new_align);
+ }
+ if (dump_enabled_p ())
+ dump_printf (MSG_NOTE, "merging ranges for %T, %T and %T, %T\n",
+ DR_REF (dr_a1->dr), DR_REF (dr_b1->dr),
+ DR_REF (dr_a2->dr), DR_REF (dr_b2->dr));
+ alias_pairs->ordered_remove (i);
+ i--;
+ }
+ }
}
-/* Returns the sum of affine functions FNA and FNB. */
+/* Given LOOP's two data references and segment lengths described by DR_A
+ and DR_B, create expression checking if the two addresses ranges intersect
+ with each other based on index of the two addresses. This can only be
+ done if DR_A and DR_B referring to the same (array) object and the index
+ is the only difference. For example:
-static affine_fn
-affine_fn_plus (affine_fn fna, affine_fn fnb)
-{
- return affine_fn_op (PLUS_EXPR, fna, fnb);
-}
+ DR_A DR_B
+ data-ref arr[i] arr[j]
+ base_object arr arr
+ index {i_0, +, 1}_loop {j_0, +, 1}_loop
-/* Returns the difference of affine functions FNA and FNB. */
+ The addresses and their index are like:
-static affine_fn
-affine_fn_minus (affine_fn fna, affine_fn fnb)
-{
- return affine_fn_op (MINUS_EXPR, fna, fnb);
-}
+ |<- ADDR_A ->| |<- ADDR_B ->|
+ ------------------------------------------------------->
+ | | | | | | | | | |
+ ------------------------------------------------------->
+ i_0 ... i_0+4 j_0 ... j_0+4
-/* Frees affine function FN. */
+ We can create expression based on index rather than address:
-static void
-affine_fn_free (affine_fn fn)
-{
- fn.release ();
-}
+ (i_0 + 4 < j_0 || j_0 + 4 < i_0)
-/* Determine for each subscript in the data dependence relation DDR
- the distance. */
+ Note evolution step of index needs to be considered in comparison. */
-static void
-compute_subscript_distance (struct data_dependence_relation *ddr)
+static bool
+create_intersect_range_checks_index (struct loop *loop, tree *cond_expr,
+ const dr_with_seg_len& dr_a,
+ const dr_with_seg_len& dr_b)
{
- conflict_function *cf_a, *cf_b;
- affine_fn fn_a, fn_b, diff;
+ if (integer_zerop (DR_STEP (dr_a.dr))
+ || integer_zerop (DR_STEP (dr_b.dr))
+ || DR_NUM_DIMENSIONS (dr_a.dr) != DR_NUM_DIMENSIONS (dr_b.dr))
+ return false;
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- {
- unsigned int i;
+ poly_uint64 seg_len1, seg_len2;
+ if (!poly_int_tree_p (dr_a.seg_len, &seg_len1)
+ || !poly_int_tree_p (dr_b.seg_len, &seg_len2))
+ return false;
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- struct subscript *subscript;
+ if (!tree_fits_shwi_p (DR_STEP (dr_a.dr)))
+ return false;
- subscript = DDR_SUBSCRIPT (ddr, i);
- cf_a = SUB_CONFLICTS_IN_A (subscript);
- cf_b = SUB_CONFLICTS_IN_B (subscript);
+ if (!operand_equal_p (DR_BASE_OBJECT (dr_a.dr), DR_BASE_OBJECT (dr_b.dr), 0))
+ return false;
- fn_a = common_affine_function (cf_a);
- fn_b = common_affine_function (cf_b);
- if (!fn_a.exists () || !fn_b.exists ())
- {
- SUB_DISTANCE (subscript) = chrec_dont_know;
- return;
- }
- diff = affine_fn_minus (fn_a, fn_b);
+ if (!operand_equal_p (DR_STEP (dr_a.dr), DR_STEP (dr_b.dr), 0))
+ return false;
- if (affine_function_constant_p (diff))
- SUB_DISTANCE (subscript) = affine_function_base (diff);
- else
- SUB_DISTANCE (subscript) = chrec_dont_know;
+ gcc_assert (TREE_CODE (DR_STEP (dr_a.dr)) == INTEGER_CST);
- affine_fn_free (diff);
- }
+ bool neg_step = tree_int_cst_compare (DR_STEP (dr_a.dr), size_zero_node) < 0;
+ unsigned HOST_WIDE_INT abs_step = tree_to_shwi (DR_STEP (dr_a.dr));
+ if (neg_step)
+ {
+ abs_step = -abs_step;
+ seg_len1 = -seg_len1;
+ seg_len2 = -seg_len2;
+ }
+ else
+ {
+ /* Include the access size in the length, so that we only have one
+ tree addition below. */
+ seg_len1 += dr_a.access_size;
+ seg_len2 += dr_b.access_size;
}
-}
-
-/* Returns the conflict function for "unknown". */
-static conflict_function *
-conflict_fn_not_known (void)
-{
- conflict_function *fn = XCNEW (conflict_function);
- fn->n = NOT_KNOWN;
+ /* Infer the number of iterations with which the memory segment is accessed
+ by DR. In other words, alias is checked if memory segment accessed by
+ DR_A in some iterations intersect with memory segment accessed by DR_B
+ in the same amount iterations.
+ Note segnment length is a linear function of number of iterations with
+ DR_STEP as the coefficient. */
+ poly_uint64 niter_len1, niter_len2;
+ if (!can_div_trunc_p (seg_len1 + abs_step - 1, abs_step, &niter_len1)
+ || !can_div_trunc_p (seg_len2 + abs_step - 1, abs_step, &niter_len2))
+ return false;
- return fn;
-}
+ poly_uint64 niter_access1 = 0, niter_access2 = 0;
+ if (neg_step)
+ {
+ /* Divide each access size by the byte step, rounding up. */
+ if (!can_div_trunc_p (dr_a.access_size - abs_step - 1,
+ abs_step, &niter_access1)
+ || !can_div_trunc_p (dr_b.access_size + abs_step - 1,
+ abs_step, &niter_access2))
+ return false;
+ }
-/* Returns the conflict function for "independent". */
+ unsigned int i;
+ for (i = 0; i < DR_NUM_DIMENSIONS (dr_a.dr); i++)
+ {
+ tree access1 = DR_ACCESS_FN (dr_a.dr, i);
+ tree access2 = DR_ACCESS_FN (dr_b.dr, i);
+ /* Two indices must be the same if they are not scev, or not scev wrto
+ current loop being vecorized. */
+ if (TREE_CODE (access1) != POLYNOMIAL_CHREC
+ || TREE_CODE (access2) != POLYNOMIAL_CHREC
+ || CHREC_VARIABLE (access1) != (unsigned)loop->num
+ || CHREC_VARIABLE (access2) != (unsigned)loop->num)
+ {
+ if (operand_equal_p (access1, access2, 0))
+ continue;
-static conflict_function *
-conflict_fn_no_dependence (void)
-{
- conflict_function *fn = XCNEW (conflict_function);
- fn->n = NO_DEPENDENCE;
+ return false;
+ }
+ /* The two indices must have the same step. */
+ if (!operand_equal_p (CHREC_RIGHT (access1), CHREC_RIGHT (access2), 0))
+ return false;
- return fn;
-}
+ tree idx_step = CHREC_RIGHT (access1);
+ /* Index must have const step, otherwise DR_STEP won't be constant. */
+ gcc_assert (TREE_CODE (idx_step) == INTEGER_CST);
+ /* Index must evaluate in the same direction as DR. */
+ gcc_assert (!neg_step || tree_int_cst_sign_bit (idx_step) == 1);
-/* Returns true if the address of OBJ is invariant in LOOP. */
+ tree min1 = CHREC_LEFT (access1);
+ tree min2 = CHREC_LEFT (access2);
+ if (!types_compatible_p (TREE_TYPE (min1), TREE_TYPE (min2)))
+ return false;
-static bool
-object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
-{
- while (handled_component_p (obj))
- {
- if (TREE_CODE (obj) == ARRAY_REF)
- {
- /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
- need to check the stride and the lower bound of the reference. */
- if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
- loop->num)
- || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
- loop->num))
- return false;
- }
- else if (TREE_CODE (obj) == COMPONENT_REF)
+ /* Ideally, alias can be checked against loop's control IV, but we
+ need to prove linear mapping between control IV and reference
+ index. Although that should be true, we check against (array)
+ index of data reference. Like segment length, index length is
+ linear function of the number of iterations with index_step as
+ the coefficient, i.e, niter_len * idx_step. */
+ tree idx_len1 = fold_build2 (MULT_EXPR, TREE_TYPE (min1), idx_step,
+ build_int_cst (TREE_TYPE (min1),
+ niter_len1));
+ tree idx_len2 = fold_build2 (MULT_EXPR, TREE_TYPE (min2), idx_step,
+ build_int_cst (TREE_TYPE (min2),
+ niter_len2));
+ tree max1 = fold_build2 (PLUS_EXPR, TREE_TYPE (min1), min1, idx_len1);
+ tree max2 = fold_build2 (PLUS_EXPR, TREE_TYPE (min2), min2, idx_len2);
+ /* Adjust ranges for negative step. */
+ if (neg_step)
{
- if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
- loop->num))
- return false;
+ /* IDX_LEN1 and IDX_LEN2 are negative in this case. */
+ std::swap (min1, max1);
+ std::swap (min2, max2);
+
+ /* As with the lengths just calculated, we've measured the access
+ sizes in iterations, so multiply them by the index step. */
+ tree idx_access1
+ = fold_build2 (MULT_EXPR, TREE_TYPE (min1), idx_step,
+ build_int_cst (TREE_TYPE (min1), niter_access1));
+ tree idx_access2
+ = fold_build2 (MULT_EXPR, TREE_TYPE (min2), idx_step,
+ build_int_cst (TREE_TYPE (min2), niter_access2));
+
+ /* MINUS_EXPR because the above values are negative. */
+ max1 = fold_build2 (MINUS_EXPR, TREE_TYPE (max1), max1, idx_access1);
+ max2 = fold_build2 (MINUS_EXPR, TREE_TYPE (max2), max2, idx_access2);
}
- obj = TREE_OPERAND (obj, 0);
+ tree part_cond_expr
+ = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ fold_build2 (LE_EXPR, boolean_type_node, max1, min2),
+ fold_build2 (LE_EXPR, boolean_type_node, max2, min1));
+ if (*cond_expr)
+ *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ *cond_expr, part_cond_expr);
+ else
+ *cond_expr = part_cond_expr;
}
+ return true;
+}
- if (!INDIRECT_REF_P (obj)
- && TREE_CODE (obj) != MEM_REF)
- return true;
+/* If ALIGN is nonzero, set up *SEQ_MIN_OUT and *SEQ_MAX_OUT so that for
+ every address ADDR accessed by D:
- return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
- loop->num);
-}
+ *SEQ_MIN_OUT <= ADDR (== ADDR & -ALIGN) <= *SEQ_MAX_OUT
-/* Returns false if we can prove that data references A and B do not alias,
- true otherwise. If LOOP_NEST is false no cross-iteration aliases are
- considered. */
+ In this case, every element accessed by D is aligned to at least
+ ALIGN bytes.
-bool
-dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
- bool loop_nest)
-{
- tree addr_a = DR_BASE_OBJECT (a);
- tree addr_b = DR_BASE_OBJECT (b);
+ If ALIGN is zero then instead set *SEG_MAX_OUT so that:
- /* If we are not processing a loop nest but scalar code we
- do not need to care about possible cross-iteration dependences
- and thus can process the full original reference. Do so,
- similar to how loop invariant motion applies extra offset-based
- disambiguation. */
- if (!loop_nest)
- {
- aff_tree off1, off2;
- 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, -1);
- aff_combination_add (&off2, &off1);
- if (aff_comb_cannot_overlap_p (&off2, size1, size2))
- return false;
- }
+ *SEQ_MIN_OUT <= ADDR < *SEQ_MAX_OUT. */
- 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;
+static void
+get_segment_min_max (const dr_with_seg_len &d, tree *seg_min_out,
+ tree *seg_max_out, HOST_WIDE_INT align)
+{
+ /* Each access has the following pattern:
- /* 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
- && TREE_CODE (TREE_OPERAND (addr_a, 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_b) == 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 (TREE_OPERAND (addr_a, 0),
- build_fold_addr_expr (addr_b));
- }
- else if (TREE_CODE (addr_b) == MEM_REF
- && 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));
- }
+ <- |seg_len| ->
+ <--- A: -ve step --->
+ +-----+-------+-----+-------+-----+
+ | n-1 | ,.... | 0 | ..... | n-1 |
+ +-----+-------+-----+-------+-----+
+ <--- B: +ve step --->
+ <- |seg_len| ->
+ |
+ base address
- /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
- that is being subsetted in the loop nest. */
- if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
- return refs_output_dependent_p (addr_a, addr_b);
- else if (DR_IS_READ (a) && DR_IS_WRITE (b))
- return refs_anti_dependent_p (addr_a, addr_b);
- return refs_may_alias_p (addr_a, addr_b);
-}
+ where "n" is the number of scalar iterations covered by the segment.
+ (This should be VF for a particular pair if we know that both steps
+ are the same, otherwise it will be the full number of scalar loop
+ iterations.)
-/* Initialize a data dependence relation between data accesses A and
- B. NB_LOOPS is the number of loops surrounding the references: the
- size of the classic distance/direction vectors. */
+ A is the range of bytes accessed when the step is negative,
+ B is the range when the step is positive.
-struct data_dependence_relation *
-initialize_data_dependence_relation (struct data_reference *a,
- struct data_reference *b,
- vec<loop_p> loop_nest)
-{
- struct data_dependence_relation *res;
- unsigned int i;
+ If the access size is "access_size" bytes, the lowest addressed byte is:
- res = XNEW (struct data_dependence_relation);
- DDR_A (res) = a;
- DDR_B (res) = b;
- DDR_LOOP_NEST (res).create (0);
- DDR_REVERSED_P (res) = false;
- DDR_SUBSCRIPTS (res).create (0);
- DDR_DIR_VECTS (res).create (0);
- DDR_DIST_VECTS (res).create (0);
+ base + (step < 0 ? seg_len : 0) [LB]
- if (a == NULL || b == NULL)
- {
- DDR_ARE_DEPENDENT (res) = chrec_dont_know;
- return res;
- }
+ and the highest addressed byte is always below:
- /* If the data references do not alias, then they are independent. */
- if (!dr_may_alias_p (a, b, loop_nest.exists ()))
- {
- DDR_ARE_DEPENDENT (res) = chrec_known;
- return res;
- }
+ base + (step < 0 ? 0 : seg_len) + access_size [UB]
- /* The case where the references are exactly the same. */
- if (operand_equal_p (DR_REF (a), DR_REF (b), 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;
- return res;
- }
- DDR_AFFINE_P (res) = true;
- DDR_ARE_DEPENDENT (res) = NULL_TREE;
- DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
- DDR_LOOP_NEST (res) = loop_nest;
- DDR_INNER_LOOP (res) = 0;
- DDR_SELF_REFERENCE (res) = true;
- for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
- {
- struct subscript *subscript;
-
- subscript = XNEW (struct subscript);
- SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
- SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
- SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
- SUB_DISTANCE (subscript) = chrec_dont_know;
- DDR_SUBSCRIPTS (res).safe_push (subscript);
- }
- return res;
- }
+ Thus:
- /* If the references do not access the same object, we do not know
- whether they alias or not. */
- if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
- {
- DDR_ARE_DEPENDENT (res) = chrec_dont_know;
- return res;
- }
+ LB <= ADDR < UB
- /* 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.exists ()
- && !object_address_invariant_in_loop_p (loop_nest[0],
- DR_BASE_OBJECT (a)))
- {
- DDR_ARE_DEPENDENT (res) = chrec_dont_know;
- return res;
- }
+ If ALIGN is nonzero, all three values are aligned to at least ALIGN
+ bytes, so:
- /* If the number of dimensions of the access to not agree we can have
- a pointer access to a component of the array element type and an
- array access while the base-objects are still the same. Punt. */
- if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
- {
- DDR_ARE_DEPENDENT (res) = chrec_dont_know;
- return res;
- }
+ LB <= ADDR <= UB - ALIGN
- DDR_AFFINE_P (res) = true;
- DDR_ARE_DEPENDENT (res) = NULL_TREE;
- DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
- DDR_LOOP_NEST (res) = loop_nest;
- DDR_INNER_LOOP (res) = 0;
- DDR_SELF_REFERENCE (res) = false;
+ where "- ALIGN" folds naturally with the "+ access_size" and often
+ cancels it out.
- for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
- {
- struct subscript *subscript;
+ We don't try to simplify LB and UB beyond this (e.g. by using
+ MIN and MAX based on whether seg_len rather than the stride is
+ negative) because it is possible for the absolute size of the
+ segment to overflow the range of a ssize_t.
- subscript = XNEW (struct subscript);
- SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
- SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
- SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
- SUB_DISTANCE (subscript) = chrec_dont_know;
- DDR_SUBSCRIPTS (res).safe_push (subscript);
- }
+ Keeping the pointer_plus outside of the cond_expr should allow
+ the cond_exprs to be shared with other alias checks. */
+ tree indicator = dr_direction_indicator (d.dr);
+ tree neg_step = fold_build2 (LT_EXPR, boolean_type_node,
+ fold_convert (ssizetype, indicator),
+ ssize_int (0));
+ tree addr_base = fold_build_pointer_plus (DR_BASE_ADDRESS (d.dr),
+ DR_OFFSET (d.dr));
+ addr_base = fold_build_pointer_plus (addr_base, DR_INIT (d.dr));
+ tree seg_len
+ = fold_convert (sizetype, rewrite_to_non_trapping_overflow (d.seg_len));
- return res;
+ tree min_reach = fold_build3 (COND_EXPR, sizetype, neg_step,
+ seg_len, size_zero_node);
+ tree max_reach = fold_build3 (COND_EXPR, sizetype, neg_step,
+ size_zero_node, seg_len);
+ max_reach = fold_build2 (PLUS_EXPR, sizetype, max_reach,
+ size_int (d.access_size - align));
+
+ *seg_min_out = fold_build_pointer_plus (addr_base, min_reach);
+ *seg_max_out = fold_build_pointer_plus (addr_base, max_reach);
}
-/* Frees memory used by the conflict function F. */
+/* Given two data references and segment lengths described by DR_A and DR_B,
+ create expression checking if the two addresses ranges intersect with
+ each other:
+
+ ((DR_A_addr_0 + DR_A_segment_length_0) <= DR_B_addr_0)
+ || (DR_B_addr_0 + DER_B_segment_length_0) <= DR_A_addr_0)) */
static void
-free_conflict_function (conflict_function *f)
+create_intersect_range_checks (struct loop *loop, tree *cond_expr,
+ const dr_with_seg_len& dr_a,
+ const dr_with_seg_len& dr_b)
{
- unsigned i;
+ *cond_expr = NULL_TREE;
+ if (create_intersect_range_checks_index (loop, cond_expr, dr_a, dr_b))
+ return;
- if (CF_NONTRIVIAL_P (f))
+ unsigned HOST_WIDE_INT min_align;
+ tree_code cmp_code;
+ if (TREE_CODE (DR_STEP (dr_a.dr)) == INTEGER_CST
+ && TREE_CODE (DR_STEP (dr_b.dr)) == INTEGER_CST)
{
- for (i = 0; i < f->n; i++)
- affine_fn_free (f->fns[i]);
+ /* In this case adding access_size to seg_len is likely to give
+ a simple X * step, where X is either the number of scalar
+ iterations or the vectorization factor. We're better off
+ keeping that, rather than subtracting an alignment from it.
+
+ In this case the maximum values are exclusive and so there is
+ no alias if the maximum of one segment equals the minimum
+ of another. */
+ min_align = 0;
+ cmp_code = LE_EXPR;
+ }
+ else
+ {
+ /* Calculate the minimum alignment shared by all four pointers,
+ then arrange for this alignment to be subtracted from the
+ exclusive maximum values to get inclusive maximum values.
+ This "- min_align" is cumulative with a "+ access_size"
+ in the calculation of the maximum values. In the best
+ (and common) case, the two cancel each other out, leaving
+ us with an inclusive bound based only on seg_len. In the
+ worst case we're simply adding a smaller number than before.
+
+ Because the maximum values are inclusive, there is an alias
+ if the maximum value of one segment is equal to the minimum
+ value of the other. */
+ min_align = MIN (dr_a.align, dr_b.align);
+ cmp_code = LT_EXPR;
}
- free (f);
-}
-/* Frees memory used by SUBSCRIPTS. */
+ tree seg_a_min, seg_a_max, seg_b_min, seg_b_max;
+ get_segment_min_max (dr_a, &seg_a_min, &seg_a_max, min_align);
+ get_segment_min_max (dr_b, &seg_b_min, &seg_b_max, min_align);
-static void
-free_subscripts (vec<subscript_p> subscripts)
+ *cond_expr
+ = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ fold_build2 (cmp_code, boolean_type_node, seg_a_max, seg_b_min),
+ fold_build2 (cmp_code, boolean_type_node, seg_b_max, seg_a_min));
+}
+
+/* Create a conditional expression that represents the run-time checks for
+ overlapping of address ranges represented by a list of data references
+ pairs passed in ALIAS_PAIRS. Data references are in LOOP. The returned
+ COND_EXPR is the conditional expression to be used in the if statement
+ that controls which version of the loop gets executed at runtime. */
+
+void
+create_runtime_alias_checks (struct loop *loop,
+ vec<dr_with_seg_len_pair_t> *alias_pairs,
+ tree * cond_expr)
{
- unsigned i;
- subscript_p s;
+ tree part_cond_expr;
- FOR_EACH_VEC_ELT (subscripts, i, s)
+ fold_defer_overflow_warnings ();
+ for (size_t i = 0, s = alias_pairs->length (); i < s; ++i)
{
- free_conflict_function (s->conflicting_iterations_in_a);
- free_conflict_function (s->conflicting_iterations_in_b);
- free (s);
+ const dr_with_seg_len& dr_a = (*alias_pairs)[i].first;
+ const dr_with_seg_len& dr_b = (*alias_pairs)[i].second;
+
+ if (dump_enabled_p ())
+ dump_printf (MSG_NOTE,
+ "create runtime check for data references %T and %T\n",
+ DR_REF (dr_a.dr), DR_REF (dr_b.dr));
+
+ /* Create condition expression for each pair data references. */
+ create_intersect_range_checks (loop, &part_cond_expr, dr_a, dr_b);
+ if (*cond_expr)
+ *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ *cond_expr, part_cond_expr);
+ else
+ *cond_expr = part_cond_expr;
}
- subscripts.release ();
+ fold_undefer_and_ignore_overflow_warnings ();
}
-/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
- description. */
+/* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
+ expressions. */
+static bool
+dr_equal_offsets_p1 (tree offset1, tree offset2)
+{
+ bool res;
-static inline void
-finalize_ddr_dependent (struct data_dependence_relation *ddr,
- tree chrec)
+ STRIP_NOPS (offset1);
+ STRIP_NOPS (offset2);
+
+ if (offset1 == offset2)
+ return true;
+
+ if (TREE_CODE (offset1) != TREE_CODE (offset2)
+ || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
+ return false;
+
+ res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
+ TREE_OPERAND (offset2, 0));
+
+ if (!res || !BINARY_CLASS_P (offset1))
+ return res;
+
+ res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
+ TREE_OPERAND (offset2, 1));
+
+ return res;
+}
+
+/* Check if DRA and DRB have equal offsets. */
+bool
+dr_equal_offsets_p (struct data_reference *dra,
+ struct data_reference *drb)
{
- DDR_ARE_DEPENDENT (ddr) = chrec;
- free_subscripts (DDR_SUBSCRIPTS (ddr));
- DDR_SUBSCRIPTS (ddr).create (0);
+ tree offset1, offset2;
+
+ offset1 = DR_OFFSET (dra);
+ offset2 = DR_OFFSET (drb);
+
+ return dr_equal_offsets_p1 (offset1, offset2);
}
-/* The dependence relation DDR cannot be represented by a distance
- vector. */
+/* Returns true if FNA == FNB. */
-static inline void
-non_affine_dependence_relation (struct data_dependence_relation *ddr)
+static bool
+affine_function_equal_p (affine_fn fna, affine_fn fnb)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
+ unsigned i, n = fna.length ();
- DDR_AFFINE_P (ddr) = false;
+ if (n != fnb.length ())
+ return false;
+
+ for (i = 0; i < n; i++)
+ if (!operand_equal_p (fna[i], fnb[i], 0))
+ return false;
+
+ return true;
}
-\f
+/* If all the functions in CF are the same, returns one of them,
+ otherwise returns NULL. */
-/* This section contains the classic Banerjee tests. */
+static affine_fn
+common_affine_function (conflict_function *cf)
+{
+ unsigned i;
+ affine_fn comm;
-/* Returns true iff CHREC_A and CHREC_B are not dependent on any index
- variables, i.e., if the ZIV (Zero Index Variable) test is true. */
+ if (!CF_NONTRIVIAL_P (cf))
+ return affine_fn ();
-static inline bool
-ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
+ comm = cf->fns[0];
+
+ for (i = 1; i < cf->n; i++)
+ if (!affine_function_equal_p (comm, cf->fns[i]))
+ return affine_fn ();
+
+ return comm;
+}
+
+/* Returns the base of the affine function FN. */
+
+static tree
+affine_function_base (affine_fn fn)
{
- return (evolution_function_is_constant_p (chrec_a)
- && evolution_function_is_constant_p (chrec_b));
+ return fn[0];
}
-/* Returns true iff CHREC_A and CHREC_B are dependent on an index
- variable, i.e., if the SIV (Single Index Variable) test is true. */
+/* Returns true if FN is a constant. */
static bool
-siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
+affine_function_constant_p (affine_fn fn)
{
- if ((evolution_function_is_constant_p (chrec_a)
- && evolution_function_is_univariate_p (chrec_b))
- || (evolution_function_is_constant_p (chrec_b)
- && evolution_function_is_univariate_p (chrec_a)))
- return true;
+ unsigned i;
+ tree coef;
- if (evolution_function_is_univariate_p (chrec_a)
- && evolution_function_is_univariate_p (chrec_b))
- {
- switch (TREE_CODE (chrec_a))
- {
- case POLYNOMIAL_CHREC:
- switch (TREE_CODE (chrec_b))
- {
- case POLYNOMIAL_CHREC:
- if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
- return false;
+ for (i = 1; fn.iterate (i, &coef); i++)
+ if (!integer_zerop (coef))
+ return false;
- default:
- return true;
- }
+ return true;
+}
- default:
- return true;
- }
- }
+/* Returns true if FN is the zero constant function. */
- return false;
+static bool
+affine_function_zero_p (affine_fn fn)
+{
+ return (integer_zerop (affine_function_base (fn))
+ && affine_function_constant_p (fn));
}
-/* Creates a conflict function with N dimensions. The affine functions
- in each dimension follow. */
+/* Returns a signed integer type with the largest precision from TA
+ and TB. */
-static conflict_function *
-conflict_fn (unsigned n, ...)
+static tree
+signed_type_for_types (tree ta, tree tb)
{
- unsigned i;
- conflict_function *ret = XCNEW (conflict_function);
- va_list ap;
+ if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
+ return signed_type_for (ta);
+ else
+ return signed_type_for (tb);
+}
- gcc_assert (0 < n && n <= MAX_DIM);
- va_start (ap, n);
+/* Applies operation OP on affine functions FNA and FNB, and returns the
+ result. */
- ret->n = n;
+static affine_fn
+affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
+{
+ unsigned i, n, m;
+ affine_fn ret;
+ tree coef;
+
+ if (fnb.length () > fna.length ())
+ {
+ n = fna.length ();
+ m = fnb.length ();
+ }
+ else
+ {
+ n = fnb.length ();
+ m = fna.length ();
+ }
+
+ ret.create (m);
for (i = 0; i < n; i++)
- ret->fns[i] = va_arg (ap, affine_fn);
- va_end (ap);
+ {
+ 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 (; fna.iterate (i, &coef); i++)
+ ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
+ coef, integer_zero_node));
+ for (; fnb.iterate (i, &coef); i++)
+ ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
+ integer_zero_node, coef));
return ret;
}
-/* Returns constant affine function with value CST. */
+/* Returns the sum of affine functions FNA and FNB. */
static affine_fn
-affine_fn_cst (tree cst)
+affine_fn_plus (affine_fn fna, affine_fn fnb)
{
- affine_fn fn;
- fn.create (1);
- fn.quick_push (cst);
- return fn;
+ return affine_fn_op (PLUS_EXPR, fna, fnb);
}
-/* Returns affine function with single variable, CST + COEF * x_DIM. */
+/* Returns the difference of affine functions FNA and FNB. */
static affine_fn
-affine_fn_univar (tree cst, unsigned dim, tree coef)
+affine_fn_minus (affine_fn fna, affine_fn fnb)
{
- affine_fn fn;
- fn.create (dim + 1);
- unsigned i;
-
- gcc_assert (dim > 0);
- fn.quick_push (cst);
- for (i = 1; i < dim; i++)
- fn.quick_push (integer_zero_node);
- fn.quick_push (coef);
- return fn;
+ return affine_fn_op (MINUS_EXPR, fna, fnb);
}
-/* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
- *OVERLAPS_B are initialized to the functions that describe the
- relation between the elements accessed twice by CHREC_A and
- CHREC_B. For k >= 0, the following property is verified:
-
- CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
+/* Frees affine function FN. */
static void
-analyze_ziv_subscript (tree chrec_a,
- tree chrec_b,
- conflict_function **overlaps_a,
- conflict_function **overlaps_b,
- tree *last_conflicts)
+affine_fn_free (affine_fn fn)
{
- tree type, difference;
- dependence_stats.num_ziv++;
+ fn.release ();
+}
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_ziv_subscript \n");
+/* Determine for each subscript in the data dependence relation DDR
+ the distance. */
- type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
- chrec_a = chrec_convert (type, chrec_a, NULL);
- chrec_b = chrec_convert (type, chrec_b, NULL);
- difference = chrec_fold_minus (type, chrec_a, chrec_b);
+static void
+compute_subscript_distance (struct data_dependence_relation *ddr)
+{
+ conflict_function *cf_a, *cf_b;
+ affine_fn fn_a, fn_b, diff;
- switch (TREE_CODE (difference))
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
- case INTEGER_CST:
- if (integer_zerop (difference))
- {
- /* The difference is equal to zero: the accessed index
- overlaps for each iteration in the loop. */
- *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_ziv_dependent++;
- }
- else
- {
- /* The accesses do not overlap. */
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- dependence_stats.num_ziv_independent++;
- }
- break;
+ unsigned int i;
- default:
- /* We're not sure whether the indexes overlap. For the moment,
- conservatively answer "don't know". */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ struct subscript *subscript;
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_ziv_unimplemented++;
- break;
- }
+ subscript = DDR_SUBSCRIPT (ddr, i);
+ cf_a = SUB_CONFLICTS_IN_A (subscript);
+ cf_b = SUB_CONFLICTS_IN_B (subscript);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
+ fn_a = common_affine_function (cf_a);
+ fn_b = common_affine_function (cf_b);
+ if (!fn_a.exists () || !fn_b.exists ())
+ {
+ SUB_DISTANCE (subscript) = chrec_dont_know;
+ return;
+ }
+ diff = affine_fn_minus (fn_a, fn_b);
+
+ if (affine_function_constant_p (diff))
+ SUB_DISTANCE (subscript) = affine_function_base (diff);
+ else
+ SUB_DISTANCE (subscript) = chrec_dont_know;
+
+ affine_fn_free (diff);
+ }
+ }
}
-/* Similar to max_stmt_executions_int, but returns the bound as a tree,
- and only if it fits to the int type. If this is not the case, or the
- bound on the number of iterations of LOOP could not be derived, returns
- chrec_dont_know. */
+/* Returns the conflict function for "unknown". */
-static tree
-max_stmt_executions_tree (struct loop *loop)
+static conflict_function *
+conflict_fn_not_known (void)
{
- widest_int nit;
+ conflict_function *fn = XCNEW (conflict_function);
+ fn->n = NOT_KNOWN;
- if (!max_stmt_executions (loop, &nit))
- return chrec_dont_know;
+ return fn;
+}
- if (!wi::fits_to_tree_p (nit, unsigned_type_node))
- return chrec_dont_know;
+/* Returns the conflict function for "independent". */
- return wide_int_to_tree (unsigned_type_node, nit);
+static conflict_function *
+conflict_fn_no_dependence (void)
+{
+ conflict_function *fn = XCNEW (conflict_function);
+ fn->n = NO_DEPENDENCE;
+
+ return fn;
}
-/* Determine whether the CHREC is always positive/negative. If the expression
- cannot be statically analyzed, return false, otherwise set the answer into
- VALUE. */
+/* Returns true if the address of OBJ is invariant in LOOP. */
static bool
-chrec_is_positive (tree chrec, bool *value)
+object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
{
- bool value0, value1, value2;
- tree end_value, nb_iter;
-
- switch (TREE_CODE (chrec))
+ while (handled_component_p (obj))
{
- case POLYNOMIAL_CHREC:
- if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
- || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
- return false;
-
- /* FIXME -- overflows. */
- if (value0 == value1)
+ if (TREE_CODE (obj) == ARRAY_REF)
{
- *value = value0;
- return true;
+ for (int i = 1; i < 4; ++i)
+ if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, i),
+ loop->num))
+ return false;
}
-
- /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
- and the proof consists in showing that the sign never
- changes during the execution of the loop, from 0 to
- loop->nb_iterations. */
- if (!evolution_function_is_affine_p (chrec))
- return false;
-
- nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
- if (chrec_contains_undetermined (nb_iter))
- return false;
-
-#if 0
- /* TODO -- If the test is after the exit, we may decrease the number of
- iterations by one. */
- if (after_exit)
- nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
-#endif
-
- end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
-
- if (!chrec_is_positive (end_value, &value2))
- return false;
-
- *value = value0;
- return value0 == value1;
-
- case INTEGER_CST:
- switch (tree_int_cst_sgn (chrec))
+ else if (TREE_CODE (obj) == COMPONENT_REF)
{
- case -1:
- *value = false;
- break;
- case 1:
- *value = true;
- break;
- default:
- return false;
+ if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
+ loop->num))
+ return false;
}
- return true;
-
- default:
- return false;
+ obj = TREE_OPERAND (obj, 0);
}
-}
+ if (!INDIRECT_REF_P (obj)
+ && TREE_CODE (obj) != MEM_REF)
+ return true;
-/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
- constant, and CHREC_B is an affine function. *OVERLAPS_A and
- *OVERLAPS_B are initialized to the functions that describe the
- relation between the elements accessed twice by CHREC_A and
- CHREC_B. For k >= 0, the following property is verified:
+ return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
+ loop->num);
+}
- CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
+/* Returns false if we can prove that data references A and B do not alias,
+ true otherwise. If LOOP_NEST is false no cross-iteration aliases are
+ considered. */
-static void
-analyze_siv_subscript_cst_affine (tree chrec_a,
- tree chrec_b,
- conflict_function **overlaps_a,
- conflict_function **overlaps_b,
- tree *last_conflicts)
+bool
+dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
+ struct loop *loop_nest)
{
- bool value0, value1, value2;
- tree type, difference, tmp;
-
- type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
- chrec_a = chrec_convert (type, chrec_a, NULL);
- chrec_b = chrec_convert (type, chrec_b, NULL);
- difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
+ tree addr_a = DR_BASE_OBJECT (a);
+ tree addr_b = DR_BASE_OBJECT (b);
- /* Special case overlap in the first iteration. */
- if (integer_zerop (difference))
+ /* If we are not processing a loop nest but scalar code we
+ do not need to care about possible cross-iteration dependences
+ and thus can process the full original reference. Do so,
+ similar to how loop invariant motion applies extra offset-based
+ disambiguation. */
+ if (!loop_nest)
{
- *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
- *last_conflicts = integer_one_node;
- return;
+ aff_tree off1, off2;
+ poly_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, -1);
+ aff_combination_add (&off2, &off1);
+ if (aff_comb_cannot_overlap_p (&off2, size1, size2))
+ return false;
}
- if (!chrec_is_positive (initial_condition (difference), &value0))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "siv test failed: chrec is not positive.\n");
+ 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)
+ /* For cross-iteration dependences the cliques must be valid for the
+ whole loop, not just individual iterations. */
+ && (!loop_nest
+ || MR_DEPENDENCE_CLIQUE (addr_a) == 1
+ || MR_DEPENDENCE_CLIQUE (addr_a) == loop_nest->owned_clique)
+ && MR_DEPENDENCE_CLIQUE (addr_a) == MR_DEPENDENCE_CLIQUE (addr_b)
+ && MR_DEPENDENCE_BASE (addr_a) != MR_DEPENDENCE_BASE (addr_b))
+ return false;
- dependence_stats.num_siv_unimplemented++;
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- return;
+ /* 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)
+ || TREE_CODE (TREE_OPERAND (addr_a, 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_b) == 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 (TREE_OPERAND (addr_a, 0),
+ build_fold_addr_expr (addr_b));
}
- else
+ else if (TREE_CODE (addr_b) == MEM_REF
+ && (DR_UNCONSTRAINED_BASE (b)
+ || TREE_CODE (TREE_OPERAND (addr_b, 0)) == SSA_NAME))
{
- if (value0 == false)
- {
- if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "siv test failed: chrec not positive.\n");
-
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_siv_unimplemented++;
- return;
- }
- else
- {
- if (value1 == true)
- {
- /* Example:
- chrec_a = 12
- chrec_b = {10, +, 1}
- */
+ /* 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));
+ }
- if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
- {
- HOST_WIDE_INT numiter;
- struct loop *loop = get_chrec_loop (chrec_b);
+ /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
+ that is being subsetted in the loop nest. */
+ if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
+ return refs_output_dependent_p (addr_a, addr_b);
+ else if (DR_IS_READ (a) && DR_IS_WRITE (b))
+ return refs_anti_dependent_p (addr_a, addr_b);
+ return refs_may_alias_p (addr_a, addr_b);
+}
- *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- tmp = fold_build2 (EXACT_DIV_EXPR, type,
- fold_build1 (ABS_EXPR, type, difference),
- CHREC_RIGHT (chrec_b));
- *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
- *last_conflicts = integer_one_node;
+/* REF_A and REF_B both satisfy access_fn_component_p. Return true
+ if it is meaningful to compare their associated access functions
+ when checking for dependencies. */
+static bool
+access_fn_components_comparable_p (tree ref_a, tree ref_b)
+{
+ /* Allow pairs of component refs from the following sets:
+
+ { REALPART_EXPR, IMAGPART_EXPR }
+ { COMPONENT_REF }
+ { ARRAY_REF }. */
+ tree_code code_a = TREE_CODE (ref_a);
+ tree_code code_b = TREE_CODE (ref_b);
+ if (code_a == IMAGPART_EXPR)
+ code_a = REALPART_EXPR;
+ if (code_b == IMAGPART_EXPR)
+ code_b = REALPART_EXPR;
+ if (code_a != code_b)
+ return false;
- /* Perform weak-zero siv test to see if overlap is
- outside the loop bounds. */
- numiter = max_stmt_executions_int (loop);
+ if (TREE_CODE (ref_a) == COMPONENT_REF)
+ /* ??? We cannot simply use the type of operand #0 of the refs here as
+ the Fortran compiler smuggles type punning into COMPONENT_REFs.
+ Use the DECL_CONTEXT of the FIELD_DECLs instead. */
+ return (DECL_CONTEXT (TREE_OPERAND (ref_a, 1))
+ == DECL_CONTEXT (TREE_OPERAND (ref_b, 1)));
- if (numiter >= 0
- && compare_tree_int (tmp, numiter) > 0)
- {
- free_conflict_function (*overlaps_a);
- free_conflict_function (*overlaps_b);
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- dependence_stats.num_siv_independent++;
- return;
- }
- dependence_stats.num_siv_dependent++;
- return;
- }
+ return types_compatible_p (TREE_TYPE (TREE_OPERAND (ref_a, 0)),
+ TREE_TYPE (TREE_OPERAND (ref_b, 0)));
+}
- /* When the step does not divide the difference, there are
- no overlaps. */
- else
- {
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- dependence_stats.num_siv_independent++;
- return;
- }
- }
+/* Initialize a data dependence relation between data accesses A and
+ B. NB_LOOPS is the number of loops surrounding the references: the
+ size of the classic distance/direction vectors. */
- else
- {
- /* Example:
- chrec_a = 12
- chrec_b = {10, +, -1}
+struct data_dependence_relation *
+initialize_data_dependence_relation (struct data_reference *a,
+ struct data_reference *b,
+ vec<loop_p> loop_nest)
+{
+ struct data_dependence_relation *res;
+ unsigned int i;
- In this case, chrec_a will not overlap with chrec_b. */
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- dependence_stats.num_siv_independent++;
- return;
- }
- }
- }
- else
- {
- if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "siv test failed: chrec not positive.\n");
+ res = XCNEW (struct data_dependence_relation);
+ DDR_A (res) = a;
+ DDR_B (res) = b;
+ DDR_LOOP_NEST (res).create (0);
+ DDR_SUBSCRIPTS (res).create (0);
+ DDR_DIR_VECTS (res).create (0);
+ DDR_DIST_VECTS (res).create (0);
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_siv_unimplemented++;
- return;
- }
- else
- {
- if (value2 == false)
- {
- /* Example:
- chrec_a = 3
- chrec_b = {10, +, -1}
- */
- if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
- {
- HOST_WIDE_INT numiter;
- struct loop *loop = get_chrec_loop (chrec_b);
+ if (a == NULL || b == NULL)
+ {
+ DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+ return res;
+ }
- *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
- CHREC_RIGHT (chrec_b));
- *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
- *last_conflicts = integer_one_node;
+ /* If the data references do not alias, then they are independent. */
+ if (!dr_may_alias_p (a, b, loop_nest.exists () ? loop_nest[0] : NULL))
+ {
+ DDR_ARE_DEPENDENT (res) = chrec_known;
+ return res;
+ }
- /* Perform weak-zero siv test to see if overlap is
- outside the loop bounds. */
- numiter = max_stmt_executions_int (loop);
+ unsigned int num_dimensions_a = DR_NUM_DIMENSIONS (a);
+ unsigned int num_dimensions_b = DR_NUM_DIMENSIONS (b);
+ if (num_dimensions_a == 0 || num_dimensions_b == 0)
+ {
+ DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+ return res;
+ }
- if (numiter >= 0
- && compare_tree_int (tmp, numiter) > 0)
- {
- free_conflict_function (*overlaps_a);
- free_conflict_function (*overlaps_b);
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- dependence_stats.num_siv_independent++;
- return;
- }
- dependence_stats.num_siv_dependent++;
- return;
- }
+ /* For unconstrained bases, the root (highest-indexed) subscript
+ describes a variation in the base of the original DR_REF rather
+ than a component access. We have no type that accurately describes
+ the new DR_BASE_OBJECT (whose TREE_TYPE describes the type *after*
+ applying this subscript) so limit the search to the last real
+ component access.
- /* When the step does not divide the difference, there
- are no overlaps. */
- else
- {
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- dependence_stats.num_siv_independent++;
- return;
- }
- }
- else
- {
- /* Example:
- chrec_a = 3
- chrec_b = {4, +, 1}
+ E.g. for:
- In this case, chrec_a will not overlap with chrec_b. */
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- dependence_stats.num_siv_independent++;
- return;
- }
- }
+ void
+ f (int a[][8], int b[][8])
+ {
+ for (int i = 0; i < 8; ++i)
+ a[i * 2][0] = b[i][0];
}
- }
-}
-
-/* Helper recursive function for initializing the matrix A. Returns
- the initial value of CHREC. */
-static tree
-initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
-{
- gcc_assert (chrec);
-
- switch (TREE_CODE (chrec))
+ the a and b accesses have a single ARRAY_REF component reference [0]
+ but have two subscripts. */
+ if (DR_UNCONSTRAINED_BASE (a))
+ num_dimensions_a -= 1;
+ if (DR_UNCONSTRAINED_BASE (b))
+ num_dimensions_b -= 1;
+
+ /* These structures describe sequences of component references in
+ DR_REF (A) and DR_REF (B). Each component reference is tied to a
+ specific access function. */
+ struct {
+ /* The sequence starts at DR_ACCESS_FN (A, START_A) of A and
+ DR_ACCESS_FN (B, START_B) of B (inclusive) and extends to higher
+ indices. In C notation, these are the indices of the rightmost
+ component references; e.g. for a sequence .b.c.d, the start
+ index is for .d. */
+ unsigned int start_a;
+ unsigned int start_b;
+
+ /* The sequence contains LENGTH consecutive access functions from
+ each DR. */
+ unsigned int length;
+
+ /* The enclosing objects for the A and B sequences respectively,
+ i.e. the objects to which DR_ACCESS_FN (A, START_A + LENGTH - 1)
+ and DR_ACCESS_FN (B, START_B + LENGTH - 1) are applied. */
+ tree object_a;
+ tree object_b;
+ } full_seq = {}, struct_seq = {};
+
+ /* Before each iteration of the loop:
+
+ - REF_A is what you get after applying DR_ACCESS_FN (A, INDEX_A) and
+ - REF_B is what you get after applying DR_ACCESS_FN (B, INDEX_B). */
+ unsigned int index_a = 0;
+ unsigned int index_b = 0;
+ tree ref_a = DR_REF (a);
+ tree ref_b = DR_REF (b);
+
+ /* Now walk the component references from the final DR_REFs back up to
+ the enclosing base objects. Each component reference corresponds
+ to one access function in the DR, with access function 0 being for
+ the final DR_REF and the highest-indexed access function being the
+ one that is applied to the base of the DR.
+
+ Look for a sequence of component references whose access functions
+ are comparable (see access_fn_components_comparable_p). If more
+ than one such sequence exists, pick the one nearest the base
+ (which is the leftmost sequence in C notation). Store this sequence
+ in FULL_SEQ.
+
+ For example, if we have:
+
+ struct foo { struct bar s; ... } (*a)[10], (*b)[10];
+
+ A: a[0][i].s.c.d
+ B: __real b[0][i].s.e[i].f
+
+ (where d is the same type as the real component of f) then the access
+ functions would be:
+
+ 0 1 2 3
+ A: .d .c .s [i]
+
+ 0 1 2 3 4 5
+ B: __real .f [i] .e .s [i]
+
+ The A0/B2 column isn't comparable, since .d is a COMPONENT_REF
+ and [i] is an ARRAY_REF. However, the A1/B3 column contains two
+ COMPONENT_REF accesses for struct bar, so is comparable. Likewise
+ the A2/B4 column contains two COMPONENT_REF accesses for struct foo,
+ so is comparable. The A3/B5 column contains two ARRAY_REFs that
+ index foo[10] arrays, so is again comparable. The sequence is
+ therefore:
+
+ A: [1, 3] (i.e. [i].s.c)
+ B: [3, 5] (i.e. [i].s.e)
+
+ Also look for sequences of component references whose access
+ functions are comparable and whose enclosing objects have the same
+ RECORD_TYPE. Store this sequence in STRUCT_SEQ. In the above
+ example, STRUCT_SEQ would be:
+
+ A: [1, 2] (i.e. s.c)
+ B: [3, 4] (i.e. s.e) */
+ while (index_a < num_dimensions_a && index_b < num_dimensions_b)
{
- case POLYNOMIAL_CHREC:
- gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
+ /* REF_A and REF_B must be one of the component access types
+ allowed by dr_analyze_indices. */
+ gcc_checking_assert (access_fn_component_p (ref_a));
+ gcc_checking_assert (access_fn_component_p (ref_b));
+
+ /* Get the immediately-enclosing objects for REF_A and REF_B,
+ i.e. the references *before* applying DR_ACCESS_FN (A, INDEX_A)
+ and DR_ACCESS_FN (B, INDEX_B). */
+ tree object_a = TREE_OPERAND (ref_a, 0);
+ tree object_b = TREE_OPERAND (ref_b, 0);
+
+ tree type_a = TREE_TYPE (object_a);
+ tree type_b = TREE_TYPE (object_b);
+ if (access_fn_components_comparable_p (ref_a, ref_b))
+ {
+ /* This pair of component accesses is comparable for dependence
+ analysis, so we can include DR_ACCESS_FN (A, INDEX_A) and
+ DR_ACCESS_FN (B, INDEX_B) in the sequence. */
+ if (full_seq.start_a + full_seq.length != index_a
+ || full_seq.start_b + full_seq.length != index_b)
+ {
+ /* The accesses don't extend the current sequence,
+ so start a new one here. */
+ full_seq.start_a = index_a;
+ full_seq.start_b = index_b;
+ full_seq.length = 0;
+ }
- A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
- return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
+ /* Add this pair of references to the sequence. */
+ full_seq.length += 1;
+ full_seq.object_a = object_a;
+ full_seq.object_b = object_b;
+
+ /* If the enclosing objects are structures (and thus have the
+ same RECORD_TYPE), record the new sequence in STRUCT_SEQ. */
+ if (TREE_CODE (type_a) == RECORD_TYPE)
+ struct_seq = full_seq;
+
+ /* Move to the next containing reference for both A and B. */
+ ref_a = object_a;
+ ref_b = object_b;
+ index_a += 1;
+ index_b += 1;
+ continue;
+ }
- case PLUS_EXPR:
- case MULT_EXPR:
- case MINUS_EXPR:
- {
- tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
- tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
+ /* Try to approach equal type sizes. */
+ if (!COMPLETE_TYPE_P (type_a)
+ || !COMPLETE_TYPE_P (type_b)
+ || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_a))
+ || !tree_fits_uhwi_p (TYPE_SIZE_UNIT (type_b)))
+ break;
- return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
- }
+ unsigned HOST_WIDE_INT size_a = tree_to_uhwi (TYPE_SIZE_UNIT (type_a));
+ unsigned HOST_WIDE_INT size_b = tree_to_uhwi (TYPE_SIZE_UNIT (type_b));
+ if (size_a <= size_b)
+ {
+ index_a += 1;
+ ref_a = object_a;
+ }
+ if (size_b <= size_a)
+ {
+ index_b += 1;
+ ref_b = object_b;
+ }
+ }
- CASE_CONVERT:
- {
- tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
- return chrec_convert (chrec_type (chrec), op, NULL);
- }
+ /* See whether FULL_SEQ ends at the base and whether the two bases
+ are equal. We do not care about TBAA or alignment info so we can
+ use OEP_ADDRESS_OF to avoid false negatives. */
+ tree base_a = DR_BASE_OBJECT (a);
+ tree base_b = DR_BASE_OBJECT (b);
+ bool same_base_p = (full_seq.start_a + full_seq.length == num_dimensions_a
+ && full_seq.start_b + full_seq.length == num_dimensions_b
+ && DR_UNCONSTRAINED_BASE (a) == DR_UNCONSTRAINED_BASE (b)
+ && operand_equal_p (base_a, base_b, OEP_ADDRESS_OF)
+ && types_compatible_p (TREE_TYPE (base_a),
+ TREE_TYPE (base_b))
+ && (!loop_nest.exists ()
+ || (object_address_invariant_in_loop_p
+ (loop_nest[0], base_a))));
+
+ /* If the bases are the same, we can include the base variation too.
+ E.g. the b accesses in:
+
+ for (int i = 0; i < n; ++i)
+ b[i + 4][0] = b[i][0];
+
+ have a definite dependence distance of 4, while for:
+
+ for (int i = 0; i < n; ++i)
+ a[i + 4][0] = b[i][0];
+
+ the dependence distance depends on the gap between a and b.
+
+ If the bases are different then we can only rely on the sequence
+ rooted at a structure access, since arrays are allowed to overlap
+ arbitrarily and change shape arbitrarily. E.g. we treat this as
+ valid code:
+
+ int a[256];
+ ...
+ ((int (*)[4][3]) &a[1])[i][0] += ((int (*)[4][3]) &a[2])[i][0];
+
+ where two lvalues with the same int[4][3] type overlap, and where
+ both lvalues are distinct from the object's declared type. */
+ if (same_base_p)
+ {
+ if (DR_UNCONSTRAINED_BASE (a))
+ full_seq.length += 1;
+ }
+ else
+ full_seq = struct_seq;
- case BIT_NOT_EXPR:
- {
- /* Handle ~X as -1 - X. */
- tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
- return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
- build_int_cst (TREE_TYPE (chrec), -1), op);
- }
+ /* Punt if we didn't find a suitable sequence. */
+ if (full_seq.length == 0)
+ {
+ DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+ return res;
+ }
- case INTEGER_CST:
- return chrec;
+ if (!same_base_p)
+ {
+ /* Partial overlap is possible for different bases when strict aliasing
+ is not in effect. It's also possible if either base involves a union
+ access; e.g. for:
+
+ struct s1 { int a[2]; };
+ struct s2 { struct s1 b; int c; };
+ struct s3 { int d; struct s1 e; };
+ union u { struct s2 f; struct s3 g; } *p, *q;
+
+ the s1 at "p->f.b" (base "p->f") partially overlaps the s1 at
+ "p->g.e" (base "p->g") and might partially overlap the s1 at
+ "q->g.e" (base "q->g"). */
+ if (!flag_strict_aliasing
+ || ref_contains_union_access_p (full_seq.object_a)
+ || ref_contains_union_access_p (full_seq.object_b))
+ {
+ DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+ return res;
+ }
- default:
- gcc_unreachable ();
- return NULL_TREE;
+ DDR_COULD_BE_INDEPENDENT_P (res) = true;
+ if (!loop_nest.exists ()
+ || (object_address_invariant_in_loop_p (loop_nest[0],
+ full_seq.object_a)
+ && object_address_invariant_in_loop_p (loop_nest[0],
+ full_seq.object_b)))
+ {
+ DDR_OBJECT_A (res) = full_seq.object_a;
+ DDR_OBJECT_B (res) = full_seq.object_b;
+ }
}
-}
-#define FLOOR_DIV(x,y) ((x) / (y))
+ DDR_AFFINE_P (res) = true;
+ DDR_ARE_DEPENDENT (res) = NULL_TREE;
+ DDR_SUBSCRIPTS (res).create (full_seq.length);
+ DDR_LOOP_NEST (res) = loop_nest;
+ DDR_SELF_REFERENCE (res) = false;
-/* Solves the special case of the Diophantine equation:
- | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
+ for (i = 0; i < full_seq.length; ++i)
+ {
+ struct subscript *subscript;
- Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
- number of iterations that loops X and Y run. The overlaps will be
- constructed as evolutions in dimension DIM. */
+ subscript = XNEW (struct subscript);
+ SUB_ACCESS_FN (subscript, 0) = DR_ACCESS_FN (a, full_seq.start_a + i);
+ SUB_ACCESS_FN (subscript, 1) = DR_ACCESS_FN (b, full_seq.start_b + i);
+ SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
+ SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
+ SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
+ SUB_DISTANCE (subscript) = chrec_dont_know;
+ DDR_SUBSCRIPTS (res).safe_push (subscript);
+ }
+
+ return res;
+}
+
+/* Frees memory used by the conflict function F. */
static void
-compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
- affine_fn *overlaps_a,
- affine_fn *overlaps_b,
- tree *last_conflicts, int dim)
+free_conflict_function (conflict_function *f)
{
- if (((step_a > 0 && step_b > 0)
- || (step_a < 0 && step_b < 0)))
- {
- int step_overlaps_a, step_overlaps_b;
- int gcd_steps_a_b, last_conflict, tau2;
+ unsigned i;
- gcd_steps_a_b = gcd (step_a, step_b);
- step_overlaps_a = step_b / gcd_steps_a_b;
- step_overlaps_b = step_a / gcd_steps_a_b;
+ if (CF_NONTRIVIAL_P (f))
+ {
+ for (i = 0; i < f->n; i++)
+ affine_fn_free (f->fns[i]);
+ }
+ free (f);
+}
- if (niter > 0)
- {
- tau2 = FLOOR_DIV (niter, step_overlaps_a);
- tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
- last_conflict = tau2;
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
- }
- else
- *last_conflicts = chrec_dont_know;
+/* Frees memory used by SUBSCRIPTS. */
- *overlaps_a = affine_fn_univar (integer_zero_node, dim,
- build_int_cst (NULL_TREE,
- step_overlaps_a));
- *overlaps_b = affine_fn_univar (integer_zero_node, dim,
- build_int_cst (NULL_TREE,
- step_overlaps_b));
- }
+static void
+free_subscripts (vec<subscript_p> subscripts)
+{
+ unsigned i;
+ subscript_p s;
- else
+ FOR_EACH_VEC_ELT (subscripts, i, s)
{
- *overlaps_a = affine_fn_cst (integer_zero_node);
- *overlaps_b = affine_fn_cst (integer_zero_node);
- *last_conflicts = integer_zero_node;
+ free_conflict_function (s->conflicting_iterations_in_a);
+ free_conflict_function (s->conflicting_iterations_in_b);
+ free (s);
}
+ subscripts.release ();
}
-/* Solves the special case of a Diophantine equation where CHREC_A is
- an affine bivariate function, and CHREC_B is an affine univariate
- function. For example,
-
- | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
-
- has the following overlapping functions:
+/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
+ description. */
- | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
- | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
- | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
+static inline void
+finalize_ddr_dependent (struct data_dependence_relation *ddr,
+ tree chrec)
+{
+ DDR_ARE_DEPENDENT (ddr) = chrec;
+ free_subscripts (DDR_SUBSCRIPTS (ddr));
+ DDR_SUBSCRIPTS (ddr).create (0);
+}
- FORNOW: This is a specialized implementation for a case occurring in
- a common benchmark. Implement the general algorithm. */
+/* The dependence relation DDR cannot be represented by a distance
+ vector. */
-static void
-compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
- conflict_function **overlaps_a,
- conflict_function **overlaps_b,
- tree *last_conflicts)
+static inline void
+non_affine_dependence_relation (struct data_dependence_relation *ddr)
{
- bool xz_p, yz_p, xyz_p;
- int step_x, step_y, step_z;
- HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
- affine_fn overlaps_a_xz, overlaps_b_xz;
- affine_fn overlaps_a_yz, overlaps_b_yz;
- affine_fn overlaps_a_xyz, overlaps_b_xyz;
- affine_fn ova1, ova2, ovb;
- tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
- step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
- step_y = int_cst_value (CHREC_RIGHT (chrec_a));
- step_z = int_cst_value (CHREC_RIGHT (chrec_b));
+ DDR_AFFINE_P (ddr) = false;
+}
- niter_x = max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)));
- niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a));
- niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b));
+\f
- if (niter_x < 0 || niter_y < 0 || niter_z < 0)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
+/* This section contains the classic Banerjee tests. */
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- return;
- }
+/* Returns true iff CHREC_A and CHREC_B are not dependent on any index
+ variables, i.e., if the ZIV (Zero Index Variable) test is true. */
- niter = MIN (niter_x, niter_z);
- compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
- &overlaps_a_xz,
- &overlaps_b_xz,
- &last_conflicts_xz, 1);
- niter = MIN (niter_y, niter_z);
- compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
- &overlaps_a_yz,
- &overlaps_b_yz,
- &last_conflicts_yz, 2);
- niter = MIN (niter_x, niter_z);
- niter = MIN (niter_y, niter);
- compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
- &overlaps_a_xyz,
- &overlaps_b_xyz,
- &last_conflicts_xyz, 3);
+static inline bool
+ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
+{
+ return (evolution_function_is_constant_p (chrec_a)
+ && evolution_function_is_constant_p (chrec_b));
+}
- xz_p = !integer_zerop (last_conflicts_xz);
- yz_p = !integer_zerop (last_conflicts_yz);
- xyz_p = !integer_zerop (last_conflicts_xyz);
+/* Returns true iff CHREC_A and CHREC_B are dependent on an index
+ variable, i.e., if the SIV (Single Index Variable) test is true. */
- if (xz_p || yz_p || xyz_p)
- {
- ova1 = affine_fn_cst (integer_zero_node);
- ova2 = affine_fn_cst (integer_zero_node);
- ovb = affine_fn_cst (integer_zero_node);
- if (xz_p)
- {
- affine_fn t0 = ova1;
- affine_fn t2 = ovb;
+static bool
+siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
+{
+ if ((evolution_function_is_constant_p (chrec_a)
+ && evolution_function_is_univariate_p (chrec_b))
+ || (evolution_function_is_constant_p (chrec_b)
+ && evolution_function_is_univariate_p (chrec_a)))
+ return true;
- ova1 = affine_fn_plus (ova1, overlaps_a_xz);
- ovb = affine_fn_plus (ovb, overlaps_b_xz);
- affine_fn_free (t0);
- affine_fn_free (t2);
- *last_conflicts = last_conflicts_xz;
- }
- if (yz_p)
+ if (evolution_function_is_univariate_p (chrec_a)
+ && evolution_function_is_univariate_p (chrec_b))
+ {
+ switch (TREE_CODE (chrec_a))
{
- affine_fn t0 = ova2;
- affine_fn t2 = ovb;
+ case POLYNOMIAL_CHREC:
+ switch (TREE_CODE (chrec_b))
+ {
+ case POLYNOMIAL_CHREC:
+ if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
+ return false;
+ /* FALLTHRU */
- ova2 = affine_fn_plus (ova2, overlaps_a_yz);
- ovb = affine_fn_plus (ovb, overlaps_b_yz);
- affine_fn_free (t0);
- affine_fn_free (t2);
- *last_conflicts = last_conflicts_yz;
- }
- if (xyz_p)
- {
- affine_fn t0 = ova1;
- affine_fn t2 = ova2;
- affine_fn t4 = ovb;
+ default:
+ return true;
+ }
- ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
- ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
- ovb = affine_fn_plus (ovb, overlaps_b_xyz);
- affine_fn_free (t0);
- affine_fn_free (t2);
- affine_fn_free (t4);
- *last_conflicts = last_conflicts_xyz;
+ default:
+ return true;
}
- *overlaps_a = conflict_fn (2, ova1, ova2);
- *overlaps_b = conflict_fn (1, ovb);
- }
- else
- {
- *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
- *last_conflicts = integer_zero_node;
}
- affine_fn_free (overlaps_a_xz);
- affine_fn_free (overlaps_b_xz);
- affine_fn_free (overlaps_a_yz);
- affine_fn_free (overlaps_b_yz);
- affine_fn_free (overlaps_a_xyz);
- affine_fn_free (overlaps_b_xyz);
+ return false;
}
-/* Copy the elements of vector VEC1 with length SIZE to VEC2. */
+/* Creates a conflict function with N dimensions. The affine functions
+ in each dimension follow. */
-static void
-lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
- int size)
+static conflict_function *
+conflict_fn (unsigned n, ...)
{
- memcpy (vec2, vec1, size * sizeof (*vec1));
-}
+ unsigned i;
+ conflict_function *ret = XCNEW (conflict_function);
+ va_list ap;
-/* Copy the elements of M x N matrix MAT1 to MAT2. */
+ gcc_assert (n > 0 && n <= MAX_DIM);
+ va_start (ap, n);
-static void
-lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2,
- int m, int n)
-{
- int i;
+ ret->n = n;
+ for (i = 0; i < n; i++)
+ ret->fns[i] = va_arg (ap, affine_fn);
+ va_end (ap);
- for (i = 0; i < m; i++)
- lambda_vector_copy (mat1[i], mat2[i], n);
+ return ret;
}
-/* Store the N x N identity matrix in MAT. */
+/* Returns constant affine function with value CST. */
-static void
-lambda_matrix_id (lambda_matrix mat, int size)
+static affine_fn
+affine_fn_cst (tree cst)
{
- int i, j;
-
- for (i = 0; i < size; i++)
- for (j = 0; j < size; j++)
- mat[i][j] = (i == j) ? 1 : 0;
+ affine_fn fn;
+ fn.create (1);
+ fn.quick_push (cst);
+ return fn;
}
-/* Return the first nonzero element of vector VEC1 between START and N.
- We must have START <= N. Returns N if VEC1 is the zero vector. */
+/* Returns affine function with single variable, CST + COEF * x_DIM. */
-static int
-lambda_vector_first_nz (lambda_vector vec1, int n, int start)
+static affine_fn
+affine_fn_univar (tree cst, unsigned dim, tree coef)
{
- int j = start;
- while (j < n && vec1[j] == 0)
- j++;
- return j;
+ affine_fn fn;
+ fn.create (dim + 1);
+ unsigned i;
+
+ gcc_assert (dim > 0);
+ fn.quick_push (cst);
+ for (i = 1; i < dim; i++)
+ fn.quick_push (integer_zero_node);
+ fn.quick_push (coef);
+ return fn;
}
-/* Add a multiple of row R1 of matrix MAT with N columns to row R2:
- R2 = R2 + CONST1 * R1. */
+/* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
+ *OVERLAPS_B are initialized to the functions that describe the
+ relation between the elements accessed twice by CHREC_A and
+ CHREC_B. For k >= 0, the following property is verified:
+
+ CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
static void
-lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1)
+analyze_ziv_subscript (tree chrec_a,
+ tree chrec_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
+ tree *last_conflicts)
{
- int i;
-
- if (const1 == 0)
- return;
-
- for (i = 0; i < n; i++)
- mat[r2][i] += const1 * mat[r1][i];
-}
+ tree type, difference;
+ dependence_stats.num_ziv++;
-/* Swap rows R1 and R2 in matrix MAT. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_ziv_subscript \n");
-static void
-lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2)
-{
- lambda_vector row;
+ type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+ chrec_a = chrec_convert (type, chrec_a, NULL);
+ chrec_b = chrec_convert (type, chrec_b, NULL);
+ difference = chrec_fold_minus (type, chrec_a, chrec_b);
- row = mat[r1];
- mat[r1] = mat[r2];
- mat[r2] = row;
-}
+ switch (TREE_CODE (difference))
+ {
+ case INTEGER_CST:
+ if (integer_zerop (difference))
+ {
+ /* The difference is equal to zero: the accessed index
+ overlaps for each iteration in the loop. */
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *last_conflicts = chrec_dont_know;
+ dependence_stats.num_ziv_dependent++;
+ }
+ else
+ {
+ /* The accesses do not overlap. */
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_ziv_independent++;
+ }
+ break;
-/* Multiply vector VEC1 of length SIZE by a constant CONST1,
- and store the result in VEC2. */
+ default:
+ /* We're not sure whether the indexes overlap. For the moment,
+ conservatively answer "don't know". */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
-static void
-lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
- int size, int const1)
-{
- int i;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ dependence_stats.num_ziv_unimplemented++;
+ break;
+ }
- if (const1 == 0)
- lambda_vector_clear (vec2, size);
- else
- for (i = 0; i < size; i++)
- vec2[i] = const1 * vec1[i];
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
}
-/* Negate vector VEC1 with length SIZE and store it in VEC2. */
+/* Similar to max_stmt_executions_int, but returns the bound as a tree,
+ and only if it fits to the int type. If this is not the case, or the
+ bound on the number of iterations of LOOP could not be derived, returns
+ chrec_dont_know. */
-static void
-lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
- int size)
+static tree
+max_stmt_executions_tree (struct loop *loop)
{
- lambda_vector_mult_const (vec1, vec2, size, -1);
-}
+ widest_int nit;
-/* Negate row R1 of matrix MAT which has N columns. */
+ if (!max_stmt_executions (loop, &nit))
+ return chrec_dont_know;
-static void
-lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
-{
- lambda_vector_negate (mat[r1], mat[r1], n);
+ if (!wi::fits_to_tree_p (nit, unsigned_type_node))
+ return chrec_dont_know;
+
+ return wide_int_to_tree (unsigned_type_node, nit);
}
-/* Return true if two vectors are equal. */
+/* Determine whether the CHREC is always positive/negative. If the expression
+ cannot be statically analyzed, return false, otherwise set the answer into
+ VALUE. */
static bool
-lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
+chrec_is_positive (tree chrec, bool *value)
{
- int i;
- for (i = 0; i < size; i++)
- if (vec1[i] != vec2[i])
- return false;
- return true;
-}
+ bool value0, value1, value2;
+ tree end_value, nb_iter;
-/* Given an M x N integer matrix A, this function determines an M x
- M unimodular matrix U, and an M x N echelon matrix S such that
- "U.A = S". This decomposition is also known as "right Hermite".
+ switch (TREE_CODE (chrec))
+ {
+ case POLYNOMIAL_CHREC:
+ if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
+ || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
+ return false;
- Ref: Algorithm 2.1 page 33 in "Loop Transformations for
- Restructuring Compilers" Utpal Banerjee. */
+ /* FIXME -- overflows. */
+ if (value0 == value1)
+ {
+ *value = value0;
+ return true;
+ }
-static void
-lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
- lambda_matrix S, lambda_matrix U)
-{
- int i, j, i0 = 0;
+ /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
+ and the proof consists in showing that the sign never
+ changes during the execution of the loop, from 0 to
+ loop->nb_iterations. */
+ if (!evolution_function_is_affine_p (chrec))
+ return false;
- lambda_matrix_copy (A, S, m, n);
- lambda_matrix_id (U, m);
+ nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
+ if (chrec_contains_undetermined (nb_iter))
+ return false;
- for (j = 0; j < n; j++)
- {
- if (lambda_vector_first_nz (S[j], m, i0) < m)
- {
- ++i0;
- for (i = m - 1; i >= i0; i--)
- {
- while (S[i][j] != 0)
- {
- int sigma, factor, a, b;
+#if 0
+ /* TODO -- If the test is after the exit, we may decrease the number of
+ iterations by one. */
+ if (after_exit)
+ nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
+#endif
- a = S[i-1][j];
- b = S[i][j];
- sigma = (a * b < 0) ? -1: 1;
- a = abs (a);
- b = abs (b);
- factor = sigma * (a / b);
+ end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
- lambda_matrix_row_add (S, n, i, i-1, -factor);
- lambda_matrix_row_exchange (S, i, i-1);
+ if (!chrec_is_positive (end_value, &value2))
+ return false;
- lambda_matrix_row_add (U, m, i, i-1, -factor);
- lambda_matrix_row_exchange (U, i, i-1);
- }
- }
+ *value = value0;
+ return value0 == value1;
+
+ case INTEGER_CST:
+ switch (tree_int_cst_sgn (chrec))
+ {
+ case -1:
+ *value = false;
+ break;
+ case 1:
+ *value = true;
+ break;
+ default:
+ return false;
}
+ return true;
+
+ default:
+ return false;
}
}
-/* Determines the overlapping elements due to accesses CHREC_A and
- CHREC_B, that are affine functions. This function cannot handle
- symbolic evolution functions, ie. when initial conditions are
- parameters, because it uses lambda matrices of integers. */
+
+/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
+ constant, and CHREC_B is an affine function. *OVERLAPS_A and
+ *OVERLAPS_B are initialized to the functions that describe the
+ relation between the elements accessed twice by CHREC_A and
+ CHREC_B. For k >= 0, the following property is verified:
+
+ CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
static void
-analyze_subscript_affine_affine (tree chrec_a,
- tree chrec_b,
- conflict_function **overlaps_a,
- conflict_function **overlaps_b,
- tree *last_conflicts)
+analyze_siv_subscript_cst_affine (tree chrec_a,
+ tree chrec_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
+ tree *last_conflicts)
{
- unsigned nb_vars_a, nb_vars_b, dim;
- HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
- lambda_matrix A, U, S;
- struct obstack scratch_obstack;
+ bool value0, value1, value2;
+ tree type, difference, tmp;
- if (eq_evolutions_p (chrec_a, chrec_b))
- {
- /* The accessed index overlaps for each iteration in the
- loop. */
+ type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+ chrec_a = chrec_convert (type, chrec_a, NULL);
+ chrec_b = chrec_convert (type, chrec_b, NULL);
+ difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
+
+ /* Special case overlap in the first iteration. */
+ if (integer_zerop (difference))
+ {
*overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
*overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *last_conflicts = integer_one_node;
+ return;
+ }
+
+ if (!chrec_is_positive (initial_condition (difference), &value0))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "siv test failed: chrec is not positive.\n");
+
+ dependence_stats.num_siv_unimplemented++;
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
*last_conflicts = chrec_dont_know;
return;
}
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_subscript_affine_affine \n");
+ else
+ {
+ if (value0 == false)
+ {
+ if (TREE_CODE (chrec_b) != POLYNOMIAL_CHREC
+ || !chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "siv test failed: chrec not positive.\n");
- /* For determining the initial intersection, we have to solve a
- Diophantine equation. This is the most time consuming part.
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ dependence_stats.num_siv_unimplemented++;
+ return;
+ }
+ else
+ {
+ if (value1 == true)
+ {
+ /* Example:
+ chrec_a = 12
+ chrec_b = {10, +, 1}
+ */
- For answering to the question: "Is there a dependence?" we have
- to prove that there exists a solution to the Diophantine
- equation, and that the solution is in the iteration domain,
- i.e. the solution is positive or zero, and that the solution
- happens before the upper bound loop.nb_iterations. Otherwise
- there is no dependence. This function outputs a description of
- the iterations that hold the intersections. */
+ if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
+ {
+ HOST_WIDE_INT numiter;
+ struct loop *loop = get_chrec_loop (chrec_b);
- nb_vars_a = nb_vars_in_chrec (chrec_a);
- nb_vars_b = nb_vars_in_chrec (chrec_b);
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ tmp = fold_build2 (EXACT_DIV_EXPR, type,
+ fold_build1 (ABS_EXPR, type, difference),
+ CHREC_RIGHT (chrec_b));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
+ *last_conflicts = integer_one_node;
- gcc_obstack_init (&scratch_obstack);
- dim = nb_vars_a + nb_vars_b;
- U = lambda_matrix_new (dim, dim, &scratch_obstack);
- A = lambda_matrix_new (dim, 1, &scratch_obstack);
- S = lambda_matrix_new (dim, 1, &scratch_obstack);
+ /* Perform weak-zero siv test to see if overlap is
+ outside the loop bounds. */
+ numiter = max_stmt_executions_int (loop);
- init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
- init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
- gamma = init_b - init_a;
+ if (numiter >= 0
+ && compare_tree_int (tmp, numiter) > 0)
+ {
+ free_conflict_function (*overlaps_a);
+ free_conflict_function (*overlaps_b);
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
+ return;
+ }
+ dependence_stats.num_siv_dependent++;
+ return;
+ }
- /* Don't do all the hard work of solving the Diophantine equation
- when we already know the solution: for example,
- | {3, +, 1}_1
- | {3, +, 4}_2
- | gamma = 3 - 3 = 0.
- Then the first overlap occurs during the first iterations:
- | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
- */
- if (gamma == 0)
- {
- if (nb_vars_a == 1 && nb_vars_b == 1)
- {
- HOST_WIDE_INT step_a, step_b;
- HOST_WIDE_INT niter, niter_a, niter_b;
- affine_fn ova, ovb;
+ /* When the step does not divide the difference, there are
+ no overlaps. */
+ else
+ {
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
+ return;
+ }
+ }
- niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a));
- niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b));
- niter = MIN (niter_a, niter_b);
- step_a = int_cst_value (CHREC_RIGHT (chrec_a));
- step_b = int_cst_value (CHREC_RIGHT (chrec_b));
+ else
+ {
+ /* Example:
+ chrec_a = 12
+ chrec_b = {10, +, -1}
- compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
- &ova, &ovb,
- last_conflicts, 1);
- *overlaps_a = conflict_fn (1, ova);
- *overlaps_b = conflict_fn (1, ovb);
+ In this case, chrec_a will not overlap with chrec_b. */
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
+ return;
+ }
+ }
}
+ else
+ {
+ if (TREE_CODE (chrec_b) != POLYNOMIAL_CHREC
+ || !chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "siv test failed: chrec not positive.\n");
- else if (nb_vars_a == 2 && nb_vars_b == 1)
- compute_overlap_steps_for_affine_1_2
- (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ dependence_stats.num_siv_unimplemented++;
+ return;
+ }
+ else
+ {
+ if (value2 == false)
+ {
+ /* Example:
+ chrec_a = 3
+ chrec_b = {10, +, -1}
+ */
+ if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
+ {
+ HOST_WIDE_INT numiter;
+ struct loop *loop = get_chrec_loop (chrec_b);
- else if (nb_vars_a == 1 && nb_vars_b == 2)
- compute_overlap_steps_for_affine_1_2
- (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
+ CHREC_RIGHT (chrec_b));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
+ *last_conflicts = integer_one_node;
- else
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: too many variables.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- }
- goto end_analyze_subs_aa;
- }
+ /* Perform weak-zero siv test to see if overlap is
+ outside the loop bounds. */
+ numiter = max_stmt_executions_int (loop);
- /* U.A = S */
- lambda_matrix_right_hermite (A, dim, 1, S, U);
+ if (numiter >= 0
+ && compare_tree_int (tmp, numiter) > 0)
+ {
+ free_conflict_function (*overlaps_a);
+ free_conflict_function (*overlaps_b);
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
+ return;
+ }
+ dependence_stats.num_siv_dependent++;
+ return;
+ }
- if (S[0][0] < 0)
- {
- S[0][0] *= -1;
- lambda_matrix_row_negate (U, dim, 0);
- }
- gcd_alpha_beta = S[0][0];
+ /* When the step does not divide the difference, there
+ are no overlaps. */
+ else
+ {
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
+ return;
+ }
+ }
+ else
+ {
+ /* Example:
+ chrec_a = 3
+ chrec_b = {4, +, 1}
- /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
- but that is a quite strange case. Instead of ICEing, answer
- don't know. */
- if (gcd_alpha_beta == 0)
- {
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- goto end_analyze_subs_aa;
+ In this case, chrec_a will not overlap with chrec_b. */
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_siv_independent++;
+ return;
+ }
+ }
+ }
}
+}
- /* The classic "gcd-test". */
- if (!int_divides_p (gcd_alpha_beta, gamma))
- {
- /* The "gcd-test" has determined that there is no integer
- solution, i.e. there is no dependence. */
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- }
+/* Helper recursive function for initializing the matrix A. Returns
+ the initial value of CHREC. */
- /* Both access functions are univariate. This includes SIV and MIV cases. */
- else if (nb_vars_a == 1 && nb_vars_b == 1)
+static tree
+initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
+{
+ gcc_assert (chrec);
+
+ switch (TREE_CODE (chrec))
{
- /* Both functions should have the same evolution sign. */
- if (((A[0][0] > 0 && -A[1][0] > 0)
- || (A[0][0] < 0 && -A[1][0] < 0)))
- {
- /* The solutions are given by:
- |
- | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
- | [u21 u22] [y0]
+ case POLYNOMIAL_CHREC:
+ if (!cst_and_fits_in_hwi (CHREC_RIGHT (chrec)))
+ return chrec_dont_know;
+ A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
+ return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
- For a given integer t. Using the following variables,
+ case PLUS_EXPR:
+ case MULT_EXPR:
+ case MINUS_EXPR:
+ {
+ tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
+ tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
- | i0 = u11 * gamma / gcd_alpha_beta
- | j0 = u12 * gamma / gcd_alpha_beta
- | i1 = u21
- | j1 = u22
+ return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
+ }
- the solutions are:
+ CASE_CONVERT:
+ {
+ tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
+ return chrec_convert (chrec_type (chrec), op, NULL);
+ }
- | x0 = i0 + i1 * t,
- | y0 = j0 + j1 * t. */
- HOST_WIDE_INT i0, j0, i1, j1;
+ case BIT_NOT_EXPR:
+ {
+ /* Handle ~X as -1 - X. */
+ tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
+ return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
+ build_int_cst (TREE_TYPE (chrec), -1), op);
+ }
- i0 = U[0][0] * gamma / gcd_alpha_beta;
- j0 = U[0][1] * gamma / gcd_alpha_beta;
- i1 = U[1][0];
- j1 = U[1][1];
+ case INTEGER_CST:
+ return chrec;
- if ((i1 == 0 && i0 < 0)
- || (j1 == 0 && j0 < 0))
- {
- /* There is no solution.
- FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
- falls in here, but for the moment we don't look at the
- upper bound of the iteration domain. */
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- goto end_analyze_subs_aa;
- }
+ default:
+ gcc_unreachable ();
+ return NULL_TREE;
+ }
+}
- if (i1 > 0 && j1 > 0)
- {
- HOST_WIDE_INT niter_a
- = max_stmt_executions_int (get_chrec_loop (chrec_a));
- HOST_WIDE_INT niter_b
- = max_stmt_executions_int (get_chrec_loop (chrec_b));
- HOST_WIDE_INT niter = MIN (niter_a, niter_b);
+#define FLOOR_DIV(x,y) ((x) / (y))
- /* (X0, Y0) is a solution of the Diophantine equation:
- "chrec_a (X0) = chrec_b (Y0)". */
- HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
- CEIL (-j0, j1));
- HOST_WIDE_INT x0 = i1 * tau1 + i0;
- HOST_WIDE_INT y0 = j1 * tau1 + j0;
+/* Solves the special case of the Diophantine equation:
+ | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
- /* (X1, Y1) is the smallest positive solution of the eq
- "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
- first conflict occurs. */
- HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
- HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
- HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
+ Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
+ number of iterations that loops X and Y run. The overlaps will be
+ constructed as evolutions in dimension DIM. */
- if (niter > 0)
- {
- HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
- FLOOR_DIV (niter - j0, j1));
- HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
+static void
+compute_overlap_steps_for_affine_univar (HOST_WIDE_INT niter,
+ HOST_WIDE_INT step_a,
+ HOST_WIDE_INT step_b,
+ affine_fn *overlaps_a,
+ affine_fn *overlaps_b,
+ tree *last_conflicts, int dim)
+{
+ if (((step_a > 0 && step_b > 0)
+ || (step_a < 0 && step_b < 0)))
+ {
+ HOST_WIDE_INT step_overlaps_a, step_overlaps_b;
+ HOST_WIDE_INT gcd_steps_a_b, last_conflict, tau2;
- /* If the overlap occurs outside of the bounds of the
- loop, there is no dependence. */
- if (x1 >= niter || y1 >= niter)
- {
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- goto end_analyze_subs_aa;
- }
- else
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
- }
- else
- *last_conflicts = chrec_dont_know;
+ gcd_steps_a_b = gcd (step_a, step_b);
+ step_overlaps_a = step_b / gcd_steps_a_b;
+ step_overlaps_b = step_a / gcd_steps_a_b;
- *overlaps_a
- = conflict_fn (1,
- affine_fn_univar (build_int_cst (NULL_TREE, x1),
- 1,
- build_int_cst (NULL_TREE, i1)));
- *overlaps_b
- = conflict_fn (1,
- affine_fn_univar (build_int_cst (NULL_TREE, y1),
- 1,
- build_int_cst (NULL_TREE, j1)));
- }
- else
- {
- /* FIXME: For the moment, the upper bound of the
- iteration domain for i and j is not checked. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- }
- }
- else
+ if (niter > 0)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
+ tau2 = FLOOR_DIV (niter, step_overlaps_a);
+ tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
+ last_conflict = tau2;
+ *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
}
- }
- else
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
+ else
+ *last_conflicts = chrec_dont_know;
+
+ *overlaps_a = affine_fn_univar (integer_zero_node, dim,
+ build_int_cst (NULL_TREE,
+ step_overlaps_a));
+ *overlaps_b = affine_fn_univar (integer_zero_node, dim,
+ build_int_cst (NULL_TREE,
+ step_overlaps_b));
}
-end_analyze_subs_aa:
- obstack_free (&scratch_obstack, NULL);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ else
{
- fprintf (dump_file, " (overlaps_a = ");
- dump_conflict_function (dump_file, *overlaps_a);
- fprintf (dump_file, ")\n (overlaps_b = ");
- dump_conflict_function (dump_file, *overlaps_b);
- fprintf (dump_file, "))\n");
+ *overlaps_a = affine_fn_cst (integer_zero_node);
+ *overlaps_b = affine_fn_cst (integer_zero_node);
+ *last_conflicts = integer_zero_node;
}
}
-/* Returns true when analyze_subscript_affine_affine can be used for
- determining the dependence relation between chrec_a and chrec_b,
- that contain symbols. This function modifies chrec_a and chrec_b
- such that the analysis result is the same, and such that they don't
- contain symbols, and then can safely be passed to the analyzer.
-
- Example: The analysis of the following tuples of evolutions produce
- the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
- vs. {0, +, 1}_1
-
- {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
- {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
-*/
-
-static bool
-can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
-{
- tree diff, type, left_a, left_b, right_b;
+/* Solves the special case of a Diophantine equation where CHREC_A is
+ an affine bivariate function, and CHREC_B is an affine univariate
+ function. For example,
- if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
- || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
- /* FIXME: For the moment not handled. Might be refined later. */
- return false;
+ | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
- type = chrec_type (*chrec_a);
- left_a = CHREC_LEFT (*chrec_a);
- left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
- diff = chrec_fold_minus (type, left_a, left_b);
+ has the following overlapping functions:
- if (!evolution_function_is_constant_p (diff))
- return false;
+ | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
+ | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
+ | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
+ FORNOW: This is a specialized implementation for a case occurring in
+ a common benchmark. Implement the general algorithm. */
- *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
- diff, CHREC_RIGHT (*chrec_a));
- right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
- *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
- build_int_cst (type, 0),
- right_b);
- return true;
-}
+static void
+compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
+ tree *last_conflicts)
+{
+ bool xz_p, yz_p, xyz_p;
+ HOST_WIDE_INT step_x, step_y, step_z;
+ HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
+ affine_fn overlaps_a_xz, overlaps_b_xz;
+ affine_fn overlaps_a_yz, overlaps_b_yz;
+ affine_fn overlaps_a_xyz, overlaps_b_xyz;
+ affine_fn ova1, ova2, ovb;
+ tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
-/* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
- *OVERLAPS_B are initialized to the functions that describe the
- relation between the elements accessed twice by CHREC_A and
- CHREC_B. For k >= 0, the following property is verified:
+ step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
+ step_y = int_cst_value (CHREC_RIGHT (chrec_a));
+ step_z = int_cst_value (CHREC_RIGHT (chrec_b));
- CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
+ niter_x = max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)));
+ niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a));
+ niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b));
-static void
-analyze_siv_subscript (tree chrec_a,
- tree chrec_b,
- conflict_function **overlaps_a,
- conflict_function **overlaps_b,
- tree *last_conflicts,
- int loop_nest_num)
-{
- dependence_stats.num_siv++;
+ if (niter_x < 0 || niter_y < 0 || niter_z < 0)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_siv_subscript \n");
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ return;
+ }
- if (evolution_function_is_constant_p (chrec_a)
- && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
- analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b, last_conflicts);
+ niter = MIN (niter_x, niter_z);
+ compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
+ &overlaps_a_xz,
+ &overlaps_b_xz,
+ &last_conflicts_xz, 1);
+ niter = MIN (niter_y, niter_z);
+ compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
+ &overlaps_a_yz,
+ &overlaps_b_yz,
+ &last_conflicts_yz, 2);
+ niter = MIN (niter_x, niter_z);
+ niter = MIN (niter_y, niter);
+ compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
+ &overlaps_a_xyz,
+ &overlaps_b_xyz,
+ &last_conflicts_xyz, 3);
- else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
- && evolution_function_is_constant_p (chrec_b))
- analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
- overlaps_b, overlaps_a, last_conflicts);
+ xz_p = !integer_zerop (last_conflicts_xz);
+ yz_p = !integer_zerop (last_conflicts_yz);
+ xyz_p = !integer_zerop (last_conflicts_xyz);
- else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
- && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
+ if (xz_p || yz_p || xyz_p)
{
- if (!chrec_contains_symbols (chrec_a)
- && !chrec_contains_symbols (chrec_b))
+ ova1 = affine_fn_cst (integer_zero_node);
+ ova2 = affine_fn_cst (integer_zero_node);
+ ovb = affine_fn_cst (integer_zero_node);
+ if (xz_p)
{
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b,
- last_conflicts);
+ affine_fn t0 = ova1;
+ affine_fn t2 = ovb;
- if (CF_NOT_KNOWN_P (*overlaps_a)
- || CF_NOT_KNOWN_P (*overlaps_b))
- dependence_stats.num_siv_unimplemented++;
- else if (CF_NO_DEPENDENCE_P (*overlaps_a)
- || CF_NO_DEPENDENCE_P (*overlaps_b))
- dependence_stats.num_siv_independent++;
- else
- dependence_stats.num_siv_dependent++;
+ ova1 = affine_fn_plus (ova1, overlaps_a_xz);
+ ovb = affine_fn_plus (ovb, overlaps_b_xz);
+ affine_fn_free (t0);
+ affine_fn_free (t2);
+ *last_conflicts = last_conflicts_xz;
}
- else if (can_use_analyze_subscript_affine_affine (&chrec_a,
- &chrec_b))
+ if (yz_p)
{
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b,
- last_conflicts);
+ affine_fn t0 = ova2;
+ affine_fn t2 = ovb;
- if (CF_NOT_KNOWN_P (*overlaps_a)
- || CF_NOT_KNOWN_P (*overlaps_b))
- dependence_stats.num_siv_unimplemented++;
- else if (CF_NO_DEPENDENCE_P (*overlaps_a)
- || CF_NO_DEPENDENCE_P (*overlaps_b))
- dependence_stats.num_siv_independent++;
- else
- dependence_stats.num_siv_dependent++;
+ ova2 = affine_fn_plus (ova2, overlaps_a_yz);
+ ovb = affine_fn_plus (ovb, overlaps_b_yz);
+ affine_fn_free (t0);
+ affine_fn_free (t2);
+ *last_conflicts = last_conflicts_yz;
}
- else
- goto siv_subscript_dontknow;
- }
+ if (xyz_p)
+ {
+ affine_fn t0 = ova1;
+ affine_fn t2 = ova2;
+ affine_fn t4 = ovb;
+ ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
+ ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
+ ovb = affine_fn_plus (ovb, overlaps_b_xyz);
+ affine_fn_free (t0);
+ affine_fn_free (t2);
+ affine_fn_free (t4);
+ *last_conflicts = last_conflicts_xyz;
+ }
+ *overlaps_a = conflict_fn (2, ova1, ova2);
+ *overlaps_b = conflict_fn (1, ovb);
+ }
else
{
- siv_subscript_dontknow:;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " siv test failed: unimplemented");
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_siv_unimplemented++;
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *last_conflicts = integer_zero_node;
}
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
+ affine_fn_free (overlaps_a_xz);
+ affine_fn_free (overlaps_b_xz);
+ affine_fn_free (overlaps_a_yz);
+ affine_fn_free (overlaps_b_yz);
+ affine_fn_free (overlaps_a_xyz);
+ affine_fn_free (overlaps_b_xyz);
}
-/* Returns false if we can prove that the greatest common divisor of the steps
- of CHREC does not divide CST, false otherwise. */
+/* Copy the elements of vector VEC1 with length SIZE to VEC2. */
-static bool
-gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
+static void
+lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
+ int size)
{
- HOST_WIDE_INT cd = 0, val;
- tree step;
+ memcpy (vec2, vec1, size * sizeof (*vec1));
+}
- if (!tree_fits_shwi_p (cst))
- return true;
- val = tree_to_shwi (cst);
+/* Copy the elements of M x N matrix MAT1 to MAT2. */
- while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
- {
- step = CHREC_RIGHT (chrec);
- if (!tree_fits_shwi_p (step))
- return true;
- cd = gcd (cd, tree_to_shwi (step));
- chrec = CHREC_LEFT (chrec);
- }
+static void
+lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2,
+ int m, int n)
+{
+ int i;
- return val % cd == 0;
+ for (i = 0; i < m; i++)
+ lambda_vector_copy (mat1[i], mat2[i], n);
}
-/* Analyze a MIV (Multiple Index Variable) subscript with respect to
- LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
- functions that describe the relation between the elements accessed
- twice by CHREC_A and CHREC_B. For k >= 0, the following property
- is verified:
-
- CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
+/* Store the N x N identity matrix in MAT. */
static void
-analyze_miv_subscript (tree chrec_a,
- tree chrec_b,
- conflict_function **overlaps_a,
- conflict_function **overlaps_b,
- tree *last_conflicts,
- struct loop *loop_nest)
+lambda_matrix_id (lambda_matrix mat, int size)
{
- tree type, difference;
+ int i, j;
- dependence_stats.num_miv++;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_miv_subscript \n");
+ for (i = 0; i < size; i++)
+ for (j = 0; j < size; j++)
+ mat[i][j] = (i == j) ? 1 : 0;
+}
- type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
- chrec_a = chrec_convert (type, chrec_a, NULL);
- chrec_b = chrec_convert (type, chrec_b, NULL);
- difference = chrec_fold_minus (type, chrec_a, chrec_b);
+/* Return the index of the first nonzero element of vector VEC1 between
+ START and N. We must have START <= N.
+ Returns N if VEC1 is the zero vector. */
- if (eq_evolutions_p (chrec_a, chrec_b))
- {
- /* Access functions are the same: all the elements are accessed
- in the same order. */
- *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
- *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a));
- dependence_stats.num_miv_dependent++;
- }
+static int
+lambda_vector_first_nz (lambda_vector vec1, int n, int start)
+{
+ int j = start;
+ while (j < n && vec1[j] == 0)
+ j++;
+ return j;
+}
- else if (evolution_function_is_constant_p (difference)
- /* For the moment, the following is verified:
- evolution_function_is_affine_multivariate_p (chrec_a,
- loop_nest->num) */
- && !gcd_of_steps_may_divide_p (chrec_a, difference))
- {
- /* testsuite/.../ssa-chrec-33.c
- {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
+/* Add a multiple of row R1 of matrix MAT with N columns to row R2:
+ R2 = R2 + CONST1 * R1. */
- The difference is 1, and all the evolution steps are multiples
- of 2, consequently there are no overlapping elements. */
- *overlaps_a = conflict_fn_no_dependence ();
- *overlaps_b = conflict_fn_no_dependence ();
- *last_conflicts = integer_zero_node;
- dependence_stats.num_miv_independent++;
- }
+static void
+lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2,
+ lambda_int const1)
+{
+ int i;
- else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
- && !chrec_contains_symbols (chrec_a)
- && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
- && !chrec_contains_symbols (chrec_b))
- {
- /* testsuite/.../ssa-chrec-35.c
- {0, +, 1}_2 vs. {0, +, 1}_3
- the overlapping elements are respectively located at iterations:
- {0, +, 1}_x and {0, +, 1}_x,
- in other words, we have the equality:
- {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
+ if (const1 == 0)
+ return;
- Other examples:
- {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
- {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
+ for (i = 0; i < n; i++)
+ mat[r2][i] += const1 * mat[r1][i];
+}
- {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
- {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
- */
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b, last_conflicts);
+/* Multiply vector VEC1 of length SIZE by a constant CONST1,
+ and store the result in VEC2. */
- if (CF_NOT_KNOWN_P (*overlaps_a)
- || CF_NOT_KNOWN_P (*overlaps_b))
- dependence_stats.num_miv_unimplemented++;
- else if (CF_NO_DEPENDENCE_P (*overlaps_a)
- || CF_NO_DEPENDENCE_P (*overlaps_b))
- dependence_stats.num_miv_independent++;
- else
- dependence_stats.num_miv_dependent++;
- }
+static void
+lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
+ int size, lambda_int const1)
+{
+ int i;
+ if (const1 == 0)
+ lambda_vector_clear (vec2, size);
else
- {
- /* When the analysis is too difficult, answer "don't know". */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
+ for (i = 0; i < size; i++)
+ vec2[i] = const1 * vec1[i];
+}
- *overlaps_a = conflict_fn_not_known ();
- *overlaps_b = conflict_fn_not_known ();
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_miv_unimplemented++;
- }
+/* Negate vector VEC1 with length SIZE and store it in VEC2. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
+static void
+lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
+ int size)
+{
+ lambda_vector_mult_const (vec1, vec2, size, -1);
}
-/* Determines the iterations for which CHREC_A is equal to CHREC_B in
- with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
- OVERLAP_ITERATIONS_B are initialized with two functions that
- describe the iterations that contain conflicting elements.
+/* Negate row R1 of matrix MAT which has N columns. */
- Remark: For an integer k >= 0, the following equality is true:
+static void
+lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
+{
+ lambda_vector_negate (mat[r1], mat[r1], n);
+}
- CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
-*/
+/* Return true if two vectors are equal. */
+
+static bool
+lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
+{
+ int i;
+ for (i = 0; i < size; i++)
+ if (vec1[i] != vec2[i])
+ return false;
+ return true;
+}
+
+/* Given an M x N integer matrix A, this function determines an M x
+ M unimodular matrix U, and an M x N echelon matrix S such that
+ "U.A = S". This decomposition is also known as "right Hermite".
+
+ Ref: Algorithm 2.1 page 33 in "Loop Transformations for
+ Restructuring Compilers" Utpal Banerjee. */
static void
-analyze_overlapping_iterations (tree chrec_a,
- tree chrec_b,
- conflict_function **overlap_iterations_a,
- conflict_function **overlap_iterations_b,
- tree *last_conflicts, struct loop *loop_nest)
+lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
+ lambda_matrix S, lambda_matrix U)
{
- unsigned int lnn = loop_nest->num;
+ int i, j, i0 = 0;
- dependence_stats.num_subscript_tests++;
+ lambda_matrix_copy (A, S, m, n);
+ lambda_matrix_id (U, m);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ for (j = 0; j < n; j++)
{
- fprintf (dump_file, "(analyze_overlapping_iterations \n");
- fprintf (dump_file, " (chrec_a = ");
- print_generic_expr (dump_file, chrec_a, 0);
- fprintf (dump_file, ")\n (chrec_b = ");
- print_generic_expr (dump_file, chrec_b, 0);
- fprintf (dump_file, ")\n");
- }
+ if (lambda_vector_first_nz (S[j], m, i0) < m)
+ {
+ ++i0;
+ for (i = m - 1; i >= i0; i--)
+ {
+ while (S[i][j] != 0)
+ {
+ lambda_int sigma, factor, a, b;
- if (chrec_a == NULL_TREE
- || chrec_b == NULL_TREE
- || chrec_contains_undetermined (chrec_a)
- || chrec_contains_undetermined (chrec_b))
- {
- dependence_stats.num_subscript_undetermined++;
+ a = S[i-1][j];
+ b = S[i][j];
+ sigma = (a * b < 0) ? -1: 1;
+ a = abs_hwi (a);
+ b = abs_hwi (b);
+ factor = sigma * (a / b);
- *overlap_iterations_a = conflict_fn_not_known ();
- *overlap_iterations_b = conflict_fn_not_known ();
+ lambda_matrix_row_add (S, n, i, i-1, -factor);
+ std::swap (S[i], S[i-1]);
+
+ lambda_matrix_row_add (U, m, i, i-1, -factor);
+ std::swap (U[i], U[i-1]);
+ }
+ }
+ }
}
+}
- /* If they are the same chrec, and are affine, they overlap
- on every iteration. */
- else if (eq_evolutions_p (chrec_a, chrec_b)
- && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
- || operand_equal_p (chrec_a, chrec_b, 0)))
+/* Determines the overlapping elements due to accesses CHREC_A and
+ CHREC_B, that are affine functions. This function cannot handle
+ symbolic evolution functions, ie. when initial conditions are
+ parameters, because it uses lambda matrices of integers. */
+
+static void
+analyze_subscript_affine_affine (tree chrec_a,
+ tree chrec_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
+ tree *last_conflicts)
+{
+ unsigned nb_vars_a, nb_vars_b, dim;
+ HOST_WIDE_INT gamma, gcd_alpha_beta;
+ lambda_matrix A, U, S;
+ struct obstack scratch_obstack;
+
+ if (eq_evolutions_p (chrec_a, chrec_b))
{
- dependence_stats.num_same_subscript_function++;
- *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
- *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ /* The accessed index overlaps for each iteration in the
+ loop. */
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
*last_conflicts = chrec_dont_know;
+ return;
}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_subscript_affine_affine \n");
- /* If they aren't the same, and aren't affine, we can't do anything
- yet. */
- else if ((chrec_contains_symbols (chrec_a)
- || chrec_contains_symbols (chrec_b))
- && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
- || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
- {
- dependence_stats.num_subscript_undetermined++;
- *overlap_iterations_a = conflict_fn_not_known ();
- *overlap_iterations_b = conflict_fn_not_known ();
- }
+ /* For determining the initial intersection, we have to solve a
+ Diophantine equation. This is the most time consuming part.
- else if (ziv_subscript_p (chrec_a, chrec_b))
- analyze_ziv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b,
- last_conflicts);
+ For answering to the question: "Is there a dependence?" we have
+ to prove that there exists a solution to the Diophantine
+ equation, and that the solution is in the iteration domain,
+ i.e. the solution is positive or zero, and that the solution
+ happens before the upper bound loop.nb_iterations. Otherwise
+ there is no dependence. This function outputs a description of
+ the iterations that hold the intersections. */
- else if (siv_subscript_p (chrec_a, chrec_b))
- analyze_siv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b,
- last_conflicts, lnn);
+ nb_vars_a = nb_vars_in_chrec (chrec_a);
+ nb_vars_b = nb_vars_in_chrec (chrec_b);
- else
- analyze_miv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b,
- last_conflicts, loop_nest);
+ gcc_obstack_init (&scratch_obstack);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ dim = nb_vars_a + nb_vars_b;
+ U = lambda_matrix_new (dim, dim, &scratch_obstack);
+ A = lambda_matrix_new (dim, 1, &scratch_obstack);
+ S = lambda_matrix_new (dim, 1, &scratch_obstack);
+
+ tree init_a = initialize_matrix_A (A, chrec_a, 0, 1);
+ tree init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
+ if (init_a == chrec_dont_know
+ || init_b == chrec_dont_know)
{
- fprintf (dump_file, " (overlap_iterations_a = ");
- 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");
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "affine-affine test failed: "
+ "representation issue.\n");
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ goto end_analyze_subs_aa;
}
-}
-
-/* Helper function for uniquely inserting distance vectors. */
-
-static void
-save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
-{
- unsigned i;
- lambda_vector v;
+ gamma = int_cst_value (init_b) - int_cst_value (init_a);
- FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, v)
- if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
- return;
+ /* Don't do all the hard work of solving the Diophantine equation
+ when we already know the solution: for example,
+ | {3, +, 1}_1
+ | {3, +, 4}_2
+ | gamma = 3 - 3 = 0.
+ Then the first overlap occurs during the first iterations:
+ | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
+ */
+ if (gamma == 0)
+ {
+ if (nb_vars_a == 1 && nb_vars_b == 1)
+ {
+ HOST_WIDE_INT step_a, step_b;
+ HOST_WIDE_INT niter, niter_a, niter_b;
+ affine_fn ova, ovb;
- DDR_DIST_VECTS (ddr).safe_push (dist_v);
-}
+ niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a));
+ niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b));
+ niter = MIN (niter_a, niter_b);
+ step_a = int_cst_value (CHREC_RIGHT (chrec_a));
+ step_b = int_cst_value (CHREC_RIGHT (chrec_b));
-/* Helper function for uniquely inserting direction vectors. */
+ compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
+ &ova, &ovb,
+ last_conflicts, 1);
+ *overlaps_a = conflict_fn (1, ova);
+ *overlaps_b = conflict_fn (1, ovb);
+ }
-static void
-save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
-{
- unsigned i;
- lambda_vector v;
+ else if (nb_vars_a == 2 && nb_vars_b == 1)
+ compute_overlap_steps_for_affine_1_2
+ (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
- FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr), i, v)
- if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
- return;
+ else if (nb_vars_a == 1 && nb_vars_b == 2)
+ compute_overlap_steps_for_affine_1_2
+ (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
- DDR_DIR_VECTS (ddr).safe_push (dir_v);
-}
+ else
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "affine-affine test failed: too many variables.\n");
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ }
+ goto end_analyze_subs_aa;
+ }
-/* Add a distance of 1 on all the loops outer than INDEX. If we
- haven't yet determined a distance for this outer loop, push a new
- distance vector composed of the previous distance, and a distance
- of 1 for this outer loop. Example:
+ /* U.A = S */
+ lambda_matrix_right_hermite (A, dim, 1, S, U);
- | loop_1
- | loop_2
- | A[10]
- | endloop_2
- | endloop_1
+ if (S[0][0] < 0)
+ {
+ S[0][0] *= -1;
+ lambda_matrix_row_negate (U, dim, 0);
+ }
+ gcd_alpha_beta = S[0][0];
- Saved vectors are of the form (dist_in_1, dist_in_2). First, we
- save (0, 1), then we have to save (1, 0). */
+ /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
+ but that is a quite strange case. Instead of ICEing, answer
+ don't know. */
+ if (gcd_alpha_beta == 0)
+ {
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ goto end_analyze_subs_aa;
+ }
-static void
-add_outer_distances (struct data_dependence_relation *ddr,
- lambda_vector dist_v, int index)
-{
- /* For each outer loop where init_v is not set, the accesses are
- in dependence of distance 1 in the loop. */
- while (--index >= 0)
+ /* The classic "gcd-test". */
+ if (!int_divides_p (gcd_alpha_beta, gamma))
{
- lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
- save_v[index] = 1;
- save_dist_v (ddr, save_v);
+ /* The "gcd-test" has determined that there is no integer
+ solution, i.e. there is no dependence. */
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
}
-}
-/* Return false when fail to represent the data dependence as a
- distance vector. INIT_B is set to true when a component has been
- added to the distance vector DIST_V. INDEX_CARRY is then set to
- the index in DIST_V that carries the dependence. */
+ /* Both access functions are univariate. This includes SIV and MIV cases. */
+ else if (nb_vars_a == 1 && nb_vars_b == 1)
+ {
+ /* Both functions should have the same evolution sign. */
+ if (((A[0][0] > 0 && -A[1][0] > 0)
+ || (A[0][0] < 0 && -A[1][0] < 0)))
+ {
+ /* The solutions are given by:
+ |
+ | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
+ | [u21 u22] [y0]
-static bool
-build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
- struct data_reference *ddr_a,
- struct data_reference *ddr_b,
- lambda_vector dist_v, bool *init_b,
- int *index_carry)
-{
- unsigned i;
- lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ For a given integer t. Using the following variables,
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree access_fn_a, access_fn_b;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
+ | i0 = u11 * gamma / gcd_alpha_beta
+ | j0 = u12 * gamma / gcd_alpha_beta
+ | i1 = u21
+ | j1 = u22
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
- {
- non_affine_dependence_relation (ddr);
- return false;
- }
+ the solutions are:
- access_fn_a = DR_ACCESS_FN (ddr_a, i);
- access_fn_b = DR_ACCESS_FN (ddr_b, i);
+ | x0 = i0 + i1 * t,
+ | y0 = j0 + j1 * t. */
+ HOST_WIDE_INT i0, j0, i1, j1;
- if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
- && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
- {
- int dist, index;
- int var_a = CHREC_VARIABLE (access_fn_a);
- int var_b = CHREC_VARIABLE (access_fn_b);
+ i0 = U[0][0] * gamma / gcd_alpha_beta;
+ j0 = U[0][1] * gamma / gcd_alpha_beta;
+ i1 = U[1][0];
+ j1 = U[1][1];
- if (var_a != var_b
- || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ if ((i1 == 0 && i0 < 0)
+ || (j1 == 0 && j0 < 0))
{
- non_affine_dependence_relation (ddr);
- return false;
+ /* There is no solution.
+ FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
+ falls in here, but for the moment we don't look at the
+ upper bound of the iteration domain. */
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ goto end_analyze_subs_aa;
}
- dist = int_cst_value (SUB_DISTANCE (subscript));
- index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
- *index_carry = MIN (index, *index_carry);
+ if (i1 > 0 && j1 > 0)
+ {
+ HOST_WIDE_INT niter_a
+ = max_stmt_executions_int (get_chrec_loop (chrec_a));
+ HOST_WIDE_INT niter_b
+ = max_stmt_executions_int (get_chrec_loop (chrec_b));
+ HOST_WIDE_INT niter = MIN (niter_a, niter_b);
- /* This is the subscript coupling test. If we have already
- recorded a distance for this loop (a distance coming from
- another subscript), it should be the same. For example,
- in the following code, there is no dependence:
+ /* (X0, Y0) is a solution of the Diophantine equation:
+ "chrec_a (X0) = chrec_b (Y0)". */
+ HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
+ CEIL (-j0, j1));
+ HOST_WIDE_INT x0 = i1 * tau1 + i0;
+ HOST_WIDE_INT y0 = j1 * tau1 + j0;
- | loop i = 0, N, 1
- | T[i+1][i] = ...
- | ... = T[i][i]
- | endloop
- */
- if (init_v[index] != 0 && dist_v[index] != dist)
+ /* (X1, Y1) is the smallest positive solution of the eq
+ "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
+ first conflict occurs. */
+ HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
+ HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
+ HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
+
+ if (niter > 0)
+ {
+ /* If the overlap occurs outside of the bounds of the
+ loop, there is no dependence. */
+ if (x1 >= niter_a || y1 >= niter_b)
+ {
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ goto end_analyze_subs_aa;
+ }
+
+ /* max stmt executions can get quite large, avoid
+ overflows by using wide ints here. */
+ widest_int tau2
+ = wi::smin (wi::sdiv_floor (wi::sub (niter_a, i0), i1),
+ wi::sdiv_floor (wi::sub (niter_b, j0), j1));
+ widest_int last_conflict = wi::sub (tau2, (x1 - i0)/i1);
+ if (wi::min_precision (last_conflict, SIGNED)
+ <= TYPE_PRECISION (integer_type_node))
+ *last_conflicts
+ = build_int_cst (integer_type_node,
+ last_conflict.to_shwi ());
+ else
+ *last_conflicts = chrec_dont_know;
+ }
+ else
+ *last_conflicts = chrec_dont_know;
+
+ *overlaps_a
+ = conflict_fn (1,
+ affine_fn_univar (build_int_cst (NULL_TREE, x1),
+ 1,
+ build_int_cst (NULL_TREE, i1)));
+ *overlaps_b
+ = conflict_fn (1,
+ affine_fn_univar (build_int_cst (NULL_TREE, y1),
+ 1,
+ build_int_cst (NULL_TREE, j1)));
+ }
+ else
{
- finalize_ddr_dependent (ddr, chrec_known);
- return false;
+ /* FIXME: For the moment, the upper bound of the
+ iteration domain for i and j is not checked. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
}
-
- dist_v[index] = dist;
- init_v[index] = 1;
- *init_b = true;
}
- else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
+ else
{
- /* This can be for example an affine vs. constant dependence
- (T[i] vs. T[3]) that is not an affine dependence and is
- not representable as a distance vector. */
- non_affine_dependence_relation (ddr);
- return false;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
}
}
+ else
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ }
- return true;
+end_analyze_subs_aa:
+ obstack_free (&scratch_obstack, NULL);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (overlaps_a = ");
+ dump_conflict_function (dump_file, *overlaps_a);
+ fprintf (dump_file, ")\n (overlaps_b = ");
+ dump_conflict_function (dump_file, *overlaps_b);
+ fprintf (dump_file, "))\n");
+ }
}
-/* Return true when the DDR contains only constant access functions. */
-
-static bool
-constant_access_functions (const struct data_dependence_relation *ddr)
-{
- unsigned i;
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
- || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
- return false;
+/* Returns true when analyze_subscript_affine_affine can be used for
+ determining the dependence relation between chrec_a and chrec_b,
+ that contain symbols. This function modifies chrec_a and chrec_b
+ such that the analysis result is the same, and such that they don't
+ contain symbols, and then can safely be passed to the analyzer.
- return true;
-}
+ Example: The analysis of the following tuples of evolutions produce
+ the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
+ vs. {0, +, 1}_1
-/* Helper function for the case where DDR_A and DDR_B are the same
- multivariate access function with a constant step. For an example
- see pr34635-1.c. */
+ {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
+ {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
+*/
-static void
-add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
+static bool
+can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
{
- int x_1, x_2;
- tree c_1 = CHREC_LEFT (c_2);
- tree c_0 = CHREC_LEFT (c_1);
- lambda_vector dist_v;
- int v1, v2, cd;
-
- /* Polynomials with more than 2 variables are not handled yet. When
- the evolution steps are parameters, it is not possible to
- represent the dependence using classical distance vectors. */
- if (TREE_CODE (c_0) != INTEGER_CST
- || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
- || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
- {
- DDR_AFFINE_P (ddr) = false;
- return;
- }
+ tree diff, type, left_a, left_b, right_b;
- x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
- x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
+ if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
+ || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
+ /* FIXME: For the moment not handled. Might be refined later. */
+ return false;
- /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
- dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- v1 = int_cst_value (CHREC_RIGHT (c_1));
- v2 = int_cst_value (CHREC_RIGHT (c_2));
- cd = gcd (v1, v2);
- v1 /= cd;
- v2 /= cd;
+ type = chrec_type (*chrec_a);
+ left_a = CHREC_LEFT (*chrec_a);
+ left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
+ diff = chrec_fold_minus (type, left_a, left_b);
- if (v2 < 0)
- {
- v2 = -v2;
- v1 = -v1;
- }
+ if (!evolution_function_is_constant_p (diff))
+ return false;
- dist_v[x_1] = v2;
- dist_v[x_2] = -v1;
- save_dist_v (ddr, dist_v);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
- add_outer_distances (ddr, dist_v, x_1);
+ *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
+ diff, CHREC_RIGHT (*chrec_a));
+ right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
+ *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
+ build_int_cst (type, 0),
+ right_b);
+ return true;
}
-/* Helper function for the case where DDR_A and DDR_B are the same
- access functions. */
+/* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
+ *OVERLAPS_B are initialized to the functions that describe the
+ relation between the elements accessed twice by CHREC_A and
+ CHREC_B. For k >= 0, the following property is verified:
+
+ CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
static void
-add_other_self_distances (struct data_dependence_relation *ddr)
+analyze_siv_subscript (tree chrec_a,
+ tree chrec_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
+ tree *last_conflicts,
+ int loop_nest_num)
{
- lambda_vector dist_v;
- unsigned i;
- int index_carry = DDR_NB_LOOPS (ddr);
+ dependence_stats.num_siv++;
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_siv_subscript \n");
- if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
- {
- if (!evolution_function_is_univariate_p (access_fun))
- {
- if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
- {
- DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
- return;
- }
+ if (evolution_function_is_constant_p (chrec_a)
+ && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
+ analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b, last_conflicts);
- access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
+ else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
+ && evolution_function_is_constant_p (chrec_b))
+ analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
+ overlaps_b, overlaps_a, last_conflicts);
- if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
- add_multivariate_self_dist (ddr, access_fun);
- else
- /* The evolution step is not constant: it varies in
- the outer loop, so this cannot be represented by a
- distance vector. For example in pr34635.c the
- evolution is {0, +, {0, +, 4}_1}_2. */
- DDR_AFFINE_P (ddr) = false;
+ else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
+ && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
+ {
+ if (!chrec_contains_symbols (chrec_a)
+ && !chrec_contains_symbols (chrec_b))
+ {
+ analyze_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b,
+ last_conflicts);
- return;
- }
+ if (CF_NOT_KNOWN_P (*overlaps_a)
+ || CF_NOT_KNOWN_P (*overlaps_b))
+ dependence_stats.num_siv_unimplemented++;
+ else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+ || CF_NO_DEPENDENCE_P (*overlaps_b))
+ dependence_stats.num_siv_independent++;
+ else
+ dependence_stats.num_siv_dependent++;
+ }
+ else if (can_use_analyze_subscript_affine_affine (&chrec_a,
+ &chrec_b))
+ {
+ analyze_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b,
+ last_conflicts);
- index_carry = MIN (index_carry,
- index_in_loop_nest (CHREC_VARIABLE (access_fun),
- DDR_LOOP_NEST (ddr)));
+ if (CF_NOT_KNOWN_P (*overlaps_a)
+ || CF_NOT_KNOWN_P (*overlaps_b))
+ dependence_stats.num_siv_unimplemented++;
+ else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+ || CF_NO_DEPENDENCE_P (*overlaps_b))
+ dependence_stats.num_siv_independent++;
+ else
+ dependence_stats.num_siv_dependent++;
}
+ else
+ goto siv_subscript_dontknow;
}
- dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- add_outer_distances (ddr, dist_v, index_carry);
+ else
+ {
+ siv_subscript_dontknow:;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " siv test failed: unimplemented");
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ dependence_stats.num_siv_unimplemented++;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
}
-static void
-insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
+/* Returns false if we can prove that the greatest common divisor of the steps
+ of CHREC does not divide CST, false otherwise. */
+
+static bool
+gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
{
- lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ HOST_WIDE_INT cd = 0, val;
+ tree step;
- dist_v[DDR_INNER_LOOP (ddr)] = 1;
- save_dist_v (ddr, dist_v);
-}
+ if (!tree_fits_shwi_p (cst))
+ return true;
+ val = tree_to_shwi (cst);
+
+ while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
+ {
+ step = CHREC_RIGHT (chrec);
+ if (!tree_fits_shwi_p (step))
+ return true;
+ cd = gcd (cd, tree_to_shwi (step));
+ chrec = CHREC_LEFT (chrec);
+ }
-/* Adds a unit distance vector to DDR when there is a 0 overlap. This
- is the case for example when access functions are the same and
- equal to a constant, as in:
+ return val % cd == 0;
+}
- | loop_1
- | A[3] = ...
- | ... = A[3]
- | endloop_1
+/* Analyze a MIV (Multiple Index Variable) subscript with respect to
+ LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
+ functions that describe the relation between the elements accessed
+ twice by CHREC_A and CHREC_B. For k >= 0, the following property
+ is verified:
- in which case the distance vectors are (0) and (1). */
+ CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
static void
-add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
+analyze_miv_subscript (tree chrec_a,
+ tree chrec_b,
+ conflict_function **overlaps_a,
+ conflict_function **overlaps_b,
+ tree *last_conflicts,
+ struct loop *loop_nest)
{
- unsigned i, j;
+ tree type, difference;
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- subscript_p sub = DDR_SUBSCRIPT (ddr, i);
- conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
- conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
+ dependence_stats.num_miv++;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_miv_subscript \n");
- for (j = 0; j < ca->n; j++)
- if (affine_function_zero_p (ca->fns[j]))
- {
- insert_innermost_unit_dist_vector (ddr);
- return;
- }
+ type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+ chrec_a = chrec_convert (type, chrec_a, NULL);
+ chrec_b = chrec_convert (type, chrec_b, NULL);
+ difference = chrec_fold_minus (type, chrec_a, chrec_b);
- for (j = 0; j < cb->n; j++)
- if (affine_function_zero_p (cb->fns[j]))
- {
- insert_innermost_unit_dist_vector (ddr);
- return;
- }
+ if (eq_evolutions_p (chrec_a, chrec_b))
+ {
+ /* Access functions are the same: all the elements are accessed
+ in the same order. */
+ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a));
+ dependence_stats.num_miv_dependent++;
}
-}
-
-/* Compute the classic per loop distance vector. DDR is the data
- dependence relation to build a vector from. Return false when fail
- to represent the data dependence as a distance vector. */
-static bool
-build_classic_dist_vector (struct data_dependence_relation *ddr,
- struct loop *loop_nest)
-{
- bool init_b = false;
- int index_carry = DDR_NB_LOOPS (ddr);
- lambda_vector dist_v;
+ else if (evolution_function_is_constant_p (difference)
+ && evolution_function_is_affine_multivariate_p (chrec_a,
+ loop_nest->num)
+ && !gcd_of_steps_may_divide_p (chrec_a, difference))
+ {
+ /* testsuite/.../ssa-chrec-33.c
+ {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
- if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return false;
+ The difference is 1, and all the evolution steps are multiples
+ of 2, consequently there are no overlapping elements. */
+ *overlaps_a = conflict_fn_no_dependence ();
+ *overlaps_b = conflict_fn_no_dependence ();
+ *last_conflicts = integer_zero_node;
+ dependence_stats.num_miv_independent++;
+ }
- if (same_access_functions (ddr))
+ else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest->num)
+ && !chrec_contains_symbols (chrec_a, loop_nest)
+ && evolution_function_is_affine_in_loop (chrec_b, loop_nest->num)
+ && !chrec_contains_symbols (chrec_b, loop_nest))
{
- /* Save the 0 vector. */
- dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- save_dist_v (ddr, dist_v);
+ /* testsuite/.../ssa-chrec-35.c
+ {0, +, 1}_2 vs. {0, +, 1}_3
+ the overlapping elements are respectively located at iterations:
+ {0, +, 1}_x and {0, +, 1}_x,
+ in other words, we have the equality:
+ {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
- if (constant_access_functions (ddr))
- add_distance_for_zero_overlaps (ddr);
+ Other examples:
+ {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
+ {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
- if (DDR_NB_LOOPS (ddr) > 1)
- add_other_self_distances (ddr);
+ {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
+ {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
+ */
+ analyze_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b, last_conflicts);
- return true;
+ if (CF_NOT_KNOWN_P (*overlaps_a)
+ || CF_NOT_KNOWN_P (*overlaps_b))
+ dependence_stats.num_miv_unimplemented++;
+ else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+ || CF_NO_DEPENDENCE_P (*overlaps_b))
+ dependence_stats.num_miv_independent++;
+ else
+ dependence_stats.num_miv_dependent++;
}
- dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
- dist_v, &init_b, &index_carry))
- return false;
-
- /* Save the distance vector if we initialized one. */
- if (init_b)
+ else
{
- /* Verify a basic constraint: classic distance vectors should
- always be lexicographically positive.
+ /* When the analysis is too difficult, answer "don't know". */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
- Data references are collected in the order of execution of
- the program, thus for the following loop
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ dependence_stats.num_miv_unimplemented++;
+ }
- | for (i = 1; i < 100; i++)
- | for (j = 1; j < 100; j++)
- | {
- | t = T[j+1][i-1]; // A
- | T[j][i] = t + 2; // B
- | }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
- references are collected following the direction of the wind:
- A then B. The data dependence tests are performed also
- following this order, such that we're looking at the distance
- separating the elements accessed by A from the elements later
- accessed by B. But in this example, the distance returned by
- test_dep (A, B) is lexicographically negative (-1, 1), that
- means that the access A occurs later than B with respect to
- the outer loop, ie. we're actually looking upwind. In this
- case we solve test_dep (B, A) looking downwind to the
- lexicographically positive solution, that returns the
- distance vector (1, -1). */
- if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
- {
- lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- loop_nest))
- return false;
- compute_subscript_distance (ddr);
- if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- save_v, &init_b, &index_carry))
- return false;
- save_dist_v (ddr, save_v);
- DDR_REVERSED_P (ddr) = true;
+/* Determines the iterations for which CHREC_A is equal to CHREC_B in
+ with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
+ OVERLAP_ITERATIONS_B are initialized with two functions that
+ describe the iterations that contain conflicting elements.
- /* In this case there is a dependence forward for all the
- outer loops:
+ Remark: For an integer k >= 0, the following equality is true:
- | for (k = 1; k < 100; k++)
- | for (i = 1; i < 100; i++)
- | for (j = 1; j < 100; j++)
- | {
- | t = T[j+1][i-1]; // A
- | T[j][i] = t + 2; // B
- | }
+ CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
+*/
- the vectors are:
- (0, 1, -1)
- (1, 1, -1)
- (1, -1, 1)
- */
- if (DDR_NB_LOOPS (ddr) > 1)
- {
- add_outer_distances (ddr, save_v, index_carry);
- add_outer_distances (ddr, dist_v, index_carry);
- }
- }
- else
- {
- lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
+static void
+analyze_overlapping_iterations (tree chrec_a,
+ tree chrec_b,
+ conflict_function **overlap_iterations_a,
+ conflict_function **overlap_iterations_b,
+ tree *last_conflicts, struct loop *loop_nest)
+{
+ unsigned int lnn = loop_nest->num;
- if (DDR_NB_LOOPS (ddr) > 1)
- {
- lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ dependence_stats.num_subscript_tests++;
- if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
- DDR_A (ddr), loop_nest))
- return false;
- compute_subscript_distance (ddr);
- if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- opposite_v, &init_b,
- &index_carry))
- return false;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(analyze_overlapping_iterations \n");
+ fprintf (dump_file, " (chrec_a = ");
+ print_generic_expr (dump_file, chrec_a);
+ fprintf (dump_file, ")\n (chrec_b = ");
+ print_generic_expr (dump_file, chrec_b);
+ fprintf (dump_file, ")\n");
+ }
- save_dist_v (ddr, save_v);
- add_outer_distances (ddr, dist_v, index_carry);
- add_outer_distances (ddr, opposite_v, index_carry);
- }
- else
- save_dist_v (ddr, save_v);
- }
+ if (chrec_a == NULL_TREE
+ || chrec_b == NULL_TREE
+ || chrec_contains_undetermined (chrec_a)
+ || chrec_contains_undetermined (chrec_b))
+ {
+ dependence_stats.num_subscript_undetermined++;
+
+ *overlap_iterations_a = conflict_fn_not_known ();
+ *overlap_iterations_b = conflict_fn_not_known ();
}
- else
+
+ /* If they are the same chrec, and are affine, they overlap
+ on every iteration. */
+ else if (eq_evolutions_p (chrec_a, chrec_b)
+ && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
+ || operand_equal_p (chrec_a, chrec_b, 0)))
{
- /* There is a distance of 1 on all the outer loops: Example:
- there is a dependence of distance 1 on loop_1 for the array A.
+ dependence_stats.num_same_subscript_function++;
+ *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ *last_conflicts = chrec_dont_know;
+ }
- | loop_1
- | A[5] = ...
- | endloop
- */
- add_outer_distances (ddr, dist_v,
- lambda_vector_first_nz (dist_v,
- DDR_NB_LOOPS (ddr), 0));
+ /* If they aren't the same, and aren't affine, we can't do anything
+ yet. */
+ else if ((chrec_contains_symbols (chrec_a)
+ || chrec_contains_symbols (chrec_b))
+ && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
+ || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
+ {
+ dependence_stats.num_subscript_undetermined++;
+ *overlap_iterations_a = conflict_fn_not_known ();
+ *overlap_iterations_b = conflict_fn_not_known ();
}
+ else if (ziv_subscript_p (chrec_a, chrec_b))
+ analyze_ziv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b,
+ last_conflicts);
+
+ else if (siv_subscript_p (chrec_a, chrec_b))
+ analyze_siv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b,
+ last_conflicts, lnn);
+
+ else
+ analyze_miv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b,
+ last_conflicts, loop_nest);
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
- unsigned i;
-
- fprintf (dump_file, "(build_classic_dist_vector\n");
- for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
- {
- fprintf (dump_file, " dist_vector = (");
- print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
- DDR_NB_LOOPS (ddr));
- fprintf (dump_file, " )\n");
- }
- fprintf (dump_file, ")\n");
+ fprintf (dump_file, " (overlap_iterations_a = ");
+ 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");
}
-
- return true;
}
-/* Return the direction for a given distance.
- FIXME: Computing dir this way is suboptimal, since dir can catch
- cases that dist is unable to represent. */
+/* Helper function for uniquely inserting distance vectors. */
-static inline enum data_dependence_direction
-dir_from_dist (int dist)
+static void
+save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
{
- if (dist > 0)
- return dir_positive;
- else if (dist < 0)
- return dir_negative;
- else
- return dir_equal;
+ unsigned i;
+ lambda_vector v;
+
+ FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, v)
+ if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
+ return;
+
+ DDR_DIST_VECTS (ddr).safe_push (dist_v);
}
-/* Compute the classic per loop direction vector. DDR is the data
- dependence relation to build a vector from. */
+/* Helper function for uniquely inserting direction vectors. */
static void
-build_classic_dir_vector (struct data_dependence_relation *ddr)
+save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
{
- unsigned i, j;
- lambda_vector dist_v;
+ unsigned i;
+ lambda_vector v;
- FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
- {
- lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr), i, v)
+ if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
+ return;
- for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
- dir_v[j] = dir_from_dist (dist_v[j]);
+ DDR_DIR_VECTS (ddr).safe_push (dir_v);
+}
- save_dir_v (ddr, dir_v);
+/* Add a distance of 1 on all the loops outer than INDEX. If we
+ haven't yet determined a distance for this outer loop, push a new
+ distance vector composed of the previous distance, and a distance
+ of 1 for this outer loop. Example:
+
+ | loop_1
+ | loop_2
+ | A[10]
+ | endloop_2
+ | endloop_1
+
+ Saved vectors are of the form (dist_in_1, dist_in_2). First, we
+ save (0, 1), then we have to save (1, 0). */
+
+static void
+add_outer_distances (struct data_dependence_relation *ddr,
+ lambda_vector dist_v, int index)
+{
+ /* For each outer loop where init_v is not set, the accesses are
+ in dependence of distance 1 in the loop. */
+ while (--index >= 0)
+ {
+ lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
+ save_v[index] = 1;
+ save_dist_v (ddr, save_v);
}
}
-/* Helper function. Returns true when there is a dependence between
- data references DRA and DRB. */
+/* Return false when fail to represent the data dependence as a
+ distance vector. A_INDEX is the index of the first reference
+ (0 for DDR_A, 1 for DDR_B) and B_INDEX is the index of the
+ second reference. INIT_B is set to true when a component has been
+ added to the distance vector DIST_V. INDEX_CARRY is then set to
+ the index in DIST_V that carries the dependence. */
static bool
-subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
- struct data_reference *dra,
- struct data_reference *drb,
- struct loop *loop_nest)
+build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
+ unsigned int a_index, unsigned int b_index,
+ lambda_vector dist_v, bool *init_b,
+ int *index_carry)
{
- unsigned int i;
- tree last_conflicts;
- struct subscript *subscript;
- tree res = NULL_TREE;
+ unsigned i;
+ lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ struct loop *loop = DDR_LOOP_NEST (ddr)[0];
- for (i = 0; DDR_SUBSCRIPTS (ddr).iterate (i, &subscript); i++)
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
- conflict_function *overlaps_a, *overlaps_b;
+ tree access_fn_a, access_fn_b;
+ struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
- analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
- DR_ACCESS_FN (drb, i),
- &overlaps_a, &overlaps_b,
- &last_conflicts, loop_nest);
+ if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ {
+ non_affine_dependence_relation (ddr);
+ return false;
+ }
- if (SUB_CONFLICTS_IN_A (subscript))
- free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
- if (SUB_CONFLICTS_IN_B (subscript))
- free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
+ access_fn_a = SUB_ACCESS_FN (subscript, a_index);
+ access_fn_b = SUB_ACCESS_FN (subscript, b_index);
- SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
- SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
- SUB_LAST_CONFLICT (subscript) = last_conflicts;
+ if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
+ && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
+ {
+ HOST_WIDE_INT dist;
+ int index;
+ int var_a = CHREC_VARIABLE (access_fn_a);
+ int var_b = CHREC_VARIABLE (access_fn_b);
- /* If there is any undetermined conflict function we have to
- give a conservative answer in case we cannot prove that
- no dependence exists when analyzing another subscript. */
- if (CF_NOT_KNOWN_P (overlaps_a)
- || CF_NOT_KNOWN_P (overlaps_b))
- {
- res = chrec_dont_know;
- continue;
- }
+ if (var_a != var_b
+ || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ {
+ non_affine_dependence_relation (ddr);
+ return false;
+ }
- /* When there is a subscript with no dependence we can stop. */
- else if (CF_NO_DEPENDENCE_P (overlaps_a)
- || CF_NO_DEPENDENCE_P (overlaps_b))
- {
- res = chrec_known;
- break;
- }
- }
+ /* When data references are collected in a loop while data
+ dependences are analyzed in loop nest nested in the loop, we
+ would have more number of access functions than number of
+ loops. Skip access functions of loops not in the loop nest.
- if (res == NULL_TREE)
- return true;
+ See PR89725 for more information. */
+ if (flow_loop_nested_p (get_loop (cfun, var_a), loop))
+ continue;
- if (res == chrec_known)
- dependence_stats.num_dependence_independent++;
- else
- dependence_stats.num_dependence_undetermined++;
- finalize_ddr_dependent (ddr, res);
- return false;
-}
+ dist = int_cst_value (SUB_DISTANCE (subscript));
+ index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
+ *index_carry = MIN (index, *index_carry);
-/* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
+ /* This is the subscript coupling test. If we have already
+ recorded a distance for this loop (a distance coming from
+ another subscript), it should be the same. For example,
+ in the following code, there is no dependence:
-static void
-subscript_dependence_tester (struct data_dependence_relation *ddr,
- struct loop *loop_nest)
-{
- if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
- dependence_stats.num_dependence_dependent++;
+ | loop i = 0, N, 1
+ | T[i+1][i] = ...
+ | ... = T[i][i]
+ | endloop
+ */
+ if (init_v[index] != 0 && dist_v[index] != dist)
+ {
+ finalize_ddr_dependent (ddr, chrec_known);
+ return false;
+ }
- compute_subscript_distance (ddr);
- if (build_classic_dist_vector (ddr, loop_nest))
- build_classic_dir_vector (ddr);
+ dist_v[index] = dist;
+ init_v[index] = 1;
+ *init_b = true;
+ }
+ else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
+ {
+ /* This can be for example an affine vs. constant dependence
+ (T[i] vs. T[3]) that is not an affine dependence and is
+ not representable as a distance vector. */
+ non_affine_dependence_relation (ddr);
+ return false;
+ }
+ }
+
+ return true;
}
-/* Returns true when all the access functions of A are affine or
- constant with respect to LOOP_NEST. */
+/* Return true when the DDR contains only constant access functions. */
static bool
-access_functions_are_affine_or_constant_p (const struct data_reference *a,
- const struct loop *loop_nest)
+constant_access_functions (const struct data_dependence_relation *ddr)
{
- unsigned int i;
- vec<tree> fns = DR_ACCESS_FNS (a);
- tree t;
+ unsigned i;
+ subscript *sub;
- 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))
+ FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr), i, sub)
+ if (!evolution_function_is_constant_p (SUB_ACCESS_FN (sub, 0))
+ || !evolution_function_is_constant_p (SUB_ACCESS_FN (sub, 1)))
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.
-
- 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. */
+/* Helper function for the case where DDR_A and DDR_B are the same
+ multivariate access function with a constant step. For an example
+ see pr34635-1.c. */
-static bool
-init_omega_eq_with_af (omega_pb pb, unsigned eq,
- unsigned int offset, tree access_fun,
- struct data_dependence_relation *ddr)
+static void
+add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
{
- switch (TREE_CODE (access_fun))
- {
- case POLYNOMIAL_CHREC:
- {
- tree left = CHREC_LEFT (access_fun);
- tree right = CHREC_RIGHT (access_fun);
- int var = CHREC_VARIABLE (access_fun);
- unsigned var_idx;
-
- if (TREE_CODE (right) != INTEGER_CST)
- return false;
-
- var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
- pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
-
- /* Compute the innermost loop index. */
- DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
+ int x_1, x_2;
+ tree c_1 = CHREC_LEFT (c_2);
+ tree c_0 = CHREC_LEFT (c_1);
+ lambda_vector dist_v;
+ HOST_WIDE_INT v1, v2, cd;
- if (offset == 0)
- pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
- += int_cst_value (right);
+ /* Polynomials with more than 2 variables are not handled yet. When
+ the evolution steps are parameters, it is not possible to
+ represent the dependence using classical distance vectors. */
+ if (TREE_CODE (c_0) != INTEGER_CST
+ || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
+ || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
+ {
+ DDR_AFFINE_P (ddr) = false;
+ return;
+ }
- switch (TREE_CODE (left))
- {
- case POLYNOMIAL_CHREC:
- return init_omega_eq_with_af (pb, eq, offset, left, ddr);
+ x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
+ x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
- case INTEGER_CST:
- pb->eqs[eq].coef[0] += int_cst_value (left);
- return true;
+ /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ v1 = int_cst_value (CHREC_RIGHT (c_1));
+ v2 = int_cst_value (CHREC_RIGHT (c_2));
+ cd = gcd (v1, v2);
+ v1 /= cd;
+ v2 /= cd;
- default:
- return false;
- }
- }
+ if (v2 < 0)
+ {
+ v2 = -v2;
+ v1 = -v1;
+ }
- case INTEGER_CST:
- pb->eqs[eq].coef[0] += int_cst_value (access_fun);
- return true;
+ dist_v[x_1] = v2;
+ dist_v[x_2] = -v1;
+ save_dist_v (ddr, dist_v);
- default:
- return false;
- }
+ add_outer_distances (ddr, dist_v, x_1);
}
-/* 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. */
+/* Helper function for the case where DDR_A and DDR_B are the same
+ access functions. */
static void
-omega_extract_distance_vectors (omega_pb pb,
- struct data_dependence_relation *ddr)
+add_other_self_distances (struct data_dependence_relation *ddr)
{
- 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)
- && DDR_LOOP_NEST (ddr).iterate (i, &loopi); i++)
- {
- int dist = 0;
- omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
- DDR_NB_LOOPS (ddr));
+ lambda_vector dist_v;
+ unsigned i;
+ int index_carry = DDR_NB_LOOPS (ddr);
+ subscript *sub;
+ struct loop *loop = DDR_LOOP_NEST (ddr)[0];
- omega_copy_problem (copy, pb);
+ FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr), i, sub)
+ {
+ tree access_fun = SUB_ACCESS_FN (sub, 0);
- /* For all the outer loops "loop_j", add "dj = 0". */
- for (j = 0; j < i && DDR_LOOP_NEST (ddr).iterate (j, &loopj); j++)
+ if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
{
- 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;
+ if (!evolution_function_is_univariate_p (access_fun, loop->num))
+ {
+ if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
+ {
+ DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+ return;
+ }
- /* 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;
+ access_fun = SUB_ACCESS_FN (DDR_SUBSCRIPT (ddr, 0), 0);
- 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 (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
+ add_multivariate_self_dist (ddr, access_fun);
+ else
+ /* The evolution step is not constant: it varies in
+ the outer loop, so this cannot be represented by a
+ distance vector. For example in pr34635.c the
+ evolution is {0, +, {0, +, 4}_1}_2. */
+ DDR_AFFINE_P (ddr) = false;
- if (dist == 0)
- {
- /* Reinitialize problem... */
- omega_copy_problem (copy, pb);
- for (j = 0; j < i && DDR_LOOP_NEST (ddr).iterate (j, &loopj); j++)
- {
- eq = omega_add_zero_eq (copy, omega_black);
- copy->eqs[eq].coef[j + 1] = 1;
+ return;
}
- /* ..., 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;
+ /* When data references are collected in a loop while data
+ dependences are analyzed in loop nest nested in the loop, we
+ would have more number of access functions than number of
+ loops. Skip access functions of loops not in the loop nest.
- res = omega_simplify_problem (copy);
- if (res == omega_false
- || res == omega_unknown
- || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
- goto next_problem;
+ See PR89725 for more information. */
+ if (flow_loop_nested_p (get_loop (cfun, CHREC_VARIABLE (access_fun)),
+ loop))
+ continue;
- 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;
- }
+ index_carry = MIN (index_carry,
+ index_in_loop_nest (CHREC_VARIABLE (access_fun),
+ DDR_LOOP_NEST (ddr)));
}
+ }
- 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));
-
- dist_v[i] = dist;
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ add_outer_distances (ddr, dist_v, index_carry);
+}
- 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;
- }
+static void
+insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
+{
+ lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
- dir_v[j] = dir_from_dist (dist_v[j]);
+ dist_v[0] = 1;
+ save_dist_v (ddr, dist_v);
+}
- save_dist_v (ddr, dist_v);
- save_dir_v (ddr, dir_v);
- }
+/* Adds a unit distance vector to DDR when there is a 0 overlap. This
+ is the case for example when access functions are the same and
+ equal to a constant, as in:
- next_problem:;
- omega_free_problem (copy);
- }
-}
+ | loop_1
+ | A[3] = ...
+ | ... = A[3]
+ | endloop_1
-/* This is called for each subscript of a tuple of data references:
- insert an equality for representing the conflicts. */
+ in which case the distance vectors are (0) and (1). */
-static bool
-omega_setup_subscript (tree access_fun_a, tree access_fun_b,
- struct data_dependence_relation *ddr,
- omega_pb pb, bool *maybe_dependent)
+static void
+add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
{
- 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;
+ unsigned i, j;
- /* ZIV test. */
- if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
- /* There is no dependence. */
- *maybe_dependent = false;
- return true;
+ subscript_p sub = DDR_SUBSCRIPT (ddr, i);
+ conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
+ conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
+
+ for (j = 0; j < ca->n; j++)
+ if (affine_function_zero_p (ca->fns[j]))
+ {
+ insert_innermost_unit_dist_vector (ddr);
+ return;
+ }
+
+ for (j = 0; j < cb->n; j++)
+ if (affine_function_zero_p (cb->fns[j]))
+ {
+ insert_innermost_unit_dist_vector (ddr);
+ return;
+ }
}
+}
- minus_one = build_int_cst (type, -1);
- fun_b = chrec_fold_multiply (type, fun_b, minus_one);
+/* Return true when the DDR contains two data references that have the
+ same access functions. */
- 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;
+static inline bool
+same_access_functions (const struct data_dependence_relation *ddr)
+{
+ unsigned i;
+ subscript *sub;
- /* 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;
- }
+ FOR_EACH_VEC_ELT (DDR_SUBSCRIPTS (ddr), i, sub)
+ if (!eq_evolutions_p (SUB_ACCESS_FN (sub, 0),
+ SUB_ACCESS_FN (sub, 1)))
+ return false;
return true;
}
-/* Helper function, same as init_omega_for_ddr but specialized for
- data references A and B. */
+/* Compute the classic per loop distance vector. DDR is the data
+ dependence relation to build a vector from. Return false when fail
+ to represent the data dependence as a distance vector. */
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)
+build_classic_dist_vector (struct data_dependence_relation *ddr,
+ struct loop *loop_nest)
{
- unsigned i;
- int ineq;
- struct loop *loopi;
- unsigned nb_loops = DDR_NB_LOOPS (ddr);
+ bool init_b = false;
+ int index_carry = DDR_NB_LOOPS (ddr);
+ lambda_vector dist_v;
- /* 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;
- }
- }
+ if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
+ return false;
- /* 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)
- && DDR_LOOP_NEST (ddr).iterate (i, &loopi); i++)
+ if (same_access_functions (ddr))
{
- HOST_WIDE_INT nbi = max_stmt_executions_int (loopi);
+ /* Save the 0 vector. */
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ save_dist_v (ddr, dist_v);
- /* 0 <= loop_x */
- ineq = omega_add_zero_geq (pb, omega_black);
- pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
+ if (constant_access_functions (ddr))
+ add_distance_for_zero_overlaps (ddr);
- /* 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 (DDR_NB_LOOPS (ddr) > 1)
+ add_other_self_distances (ddr);
- 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;
- }
+ return true;
}
- omega_extract_distance_vectors (pb, ddr);
+ dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ if (!build_classic_dist_vector_1 (ddr, 0, 1, dist_v, &init_b, &index_carry))
+ return false;
- return true;
-}
+ /* Save the distance vector if we initialized one. */
+ if (init_b)
+ {
+ /* Verify a basic constraint: classic distance vectors should
+ always be lexicographically positive.
+
+ Data references are collected in the order of execution of
+ the program, thus for the following loop
-/* 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.
+ | for (i = 1; i < 100; i++)
+ | for (j = 1; j < 100; j++)
+ | {
+ | t = T[j+1][i-1]; // A
+ | T[j][i] = t + 2; // B
+ | }
- Example: for setting up the dependence system corresponding to the
- conflicting accesses
+ references are collected following the direction of the wind:
+ A then B. The data dependence tests are performed also
+ following this order, such that we're looking at the distance
+ separating the elements accessed by A from the elements later
+ accessed by B. But in this example, the distance returned by
+ test_dep (A, B) is lexicographically negative (-1, 1), that
+ means that the access A occurs later than B with respect to
+ the outer loop, ie. we're actually looking upwind. In this
+ case we solve test_dep (B, A) looking downwind to the
+ lexicographically positive solution, that returns the
+ distance vector (1, -1). */
+ if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
+ {
+ lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ if (!subscript_dependence_tester_1 (ddr, 1, 0, loop_nest))
+ return false;
+ compute_subscript_distance (ddr);
+ if (!build_classic_dist_vector_1 (ddr, 1, 0, save_v, &init_b,
+ &index_carry))
+ return false;
+ save_dist_v (ddr, save_v);
+ DDR_REVERSED_P (ddr) = true;
- | loop_i
- | loop_j
- | A[i, i+1] = ...
- | ... A[2*j, 2*(i + j)]
- | endloop_j
- | endloop_i
+ /* In this case there is a dependence forward for all the
+ outer loops:
- the following constraints come from the iteration domain:
+ | for (k = 1; k < 100; k++)
+ | for (i = 1; i < 100; i++)
+ | for (j = 1; j < 100; j++)
+ | {
+ | t = T[j+1][i-1]; // A
+ | T[j][i] = t + 2; // B
+ | }
- 0 <= i <= Ni
- 0 <= i + di <= Ni
- 0 <= j <= Nj
- 0 <= j + dj <= Nj
+ the vectors are:
+ (0, 1, -1)
+ (1, 1, -1)
+ (1, -1, 1)
+ */
+ if (DDR_NB_LOOPS (ddr) > 1)
+ {
+ add_outer_distances (ddr, save_v, index_carry);
+ add_outer_distances (ddr, dist_v, index_carry);
+ }
+ }
+ else
+ {
+ lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
- where di, dj are the distance variables. The constraints
- representing the conflicting elements are:
+ if (DDR_NB_LOOPS (ddr) > 1)
+ {
+ lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- i = 2 * (j + dj)
- i + 1 = 2 * (i + di + j + dj)
+ if (!subscript_dependence_tester_1 (ddr, 1, 0, loop_nest))
+ return false;
+ compute_subscript_distance (ddr);
+ if (!build_classic_dist_vector_1 (ddr, 1, 0, opposite_v, &init_b,
+ &index_carry))
+ return false;
- 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:
+ save_dist_v (ddr, save_v);
+ add_outer_distances (ddr, dist_v, index_carry);
+ add_outer_distances (ddr, opposite_v, index_carry);
+ }
+ else
+ save_dist_v (ddr, save_v);
+ }
+ }
+ else
+ {
+ /* There is a distance of 1 on all the outer loops: Example:
+ there is a dependence of distance 1 on loop_1 for the array A.
- | loop_1
- | loop_2
- | A[10]
- | endloop_2
- | endloop_1
+ | loop_1
+ | A[5] = ...
+ | endloop
+ */
+ add_outer_distances (ddr, dist_v,
+ lambda_vector_first_nz (dist_v,
+ DDR_NB_LOOPS (ddr), 0));
+ }
- we have to save two distances (1, 0) and (0, 1).
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ unsigned i;
- 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.
+ fprintf (dump_file, "(build_classic_dist_vector\n");
+ for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+ {
+ fprintf (dump_file, " dist_vector = (");
+ print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
+ DDR_NB_LOOPS (ddr));
+ fprintf (dump_file, " )\n");
+ }
+ fprintf (dump_file, ")\n");
+ }
- | 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
+ return true;
+}
- 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)
+/* Return the direction for a given distance.
+ FIXME: Computing dir this way is suboptimal, since dir can catch
+ cases that dist is unable to represent. */
- 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:
+static inline enum data_dependence_direction
+dir_from_dist (int dist)
+{
+ if (dist > 0)
+ return dir_positive;
+ else if (dist < 0)
+ return dir_negative;
+ else
+ return dir_equal;
+}
- "cst | distance vars | index vars".
-*/
+/* Compute the classic per loop direction vector. DDR is the data
+ dependence relation to build a vector from. */
-static bool
-init_omega_for_ddr (struct data_dependence_relation *ddr,
- bool *maybe_dependent)
+static void
+build_classic_dir_vector (struct data_dependence_relation *ddr)
{
- omega_pb pb;
- bool res = false;
-
- *maybe_dependent = true;
+ unsigned i, j;
+ lambda_vector dist_v;
- if (same_access_functions (ddr))
+ FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
{
- unsigned j;
- lambda_vector dir_v;
+ lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- /* 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);
+ dir_v[j] = dir_from_dist (dist_v[j]);
- /* 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;
+ save_dir_v (ddr, dir_v);
}
-
- /* 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. */
+/* Helper function. Returns true when there is a dependence between the
+ data references. A_INDEX is the index of the first reference (0 for
+ DDR_A, 1 for DDR_B) and B_INDEX is the index of the second reference. */
static bool
-ddr_consistent_p (FILE *file,
- struct data_dependence_relation *ddr,
- vec<lambda_vector> dist_vects,
- vec<lambda_vector> dir_vects)
+subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
+ unsigned int a_index, unsigned int b_index,
+ struct loop *loop_nest)
{
- unsigned int i, j;
-
- /* If dump_file is set, output there. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- file = dump_file;
+ unsigned int i;
+ tree last_conflicts;
+ struct subscript *subscript;
+ tree res = NULL_TREE;
- if (dist_vects.length () != DDR_NUM_DIST_VECTS (ddr))
+ for (i = 0; DDR_SUBSCRIPTS (ddr).iterate (i, &subscript); i++)
{
- lambda_vector b_dist_v;
- fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
- dist_vects.length (),
- DDR_NUM_DIST_VECTS (ddr));
+ conflict_function *overlaps_a, *overlaps_b;
+
+ analyze_overlapping_iterations (SUB_ACCESS_FN (subscript, a_index),
+ SUB_ACCESS_FN (subscript, b_index),
+ &overlaps_a, &overlaps_b,
+ &last_conflicts, loop_nest);
- fprintf (file, "Banerjee dist vectors:\n");
- FOR_EACH_VEC_ELT (dist_vects, i, b_dist_v)
- print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
+ if (SUB_CONFLICTS_IN_A (subscript))
+ free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
+ if (SUB_CONFLICTS_IN_B (subscript))
+ free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
- 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));
+ SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
+ SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
+ SUB_LAST_CONFLICT (subscript) = last_conflicts;
- fprintf (file, "data dependence relation:\n");
- dump_data_dependence_relation (file, ddr);
+ /* If there is any undetermined conflict function we have to
+ give a conservative answer in case we cannot prove that
+ no dependence exists when analyzing another subscript. */
+ if (CF_NOT_KNOWN_P (overlaps_a)
+ || CF_NOT_KNOWN_P (overlaps_b))
+ {
+ res = chrec_dont_know;
+ continue;
+ }
- fprintf (file, ")\n");
- return false;
+ /* When there is a subscript with no dependence we can stop. */
+ else if (CF_NO_DEPENDENCE_P (overlaps_a)
+ || CF_NO_DEPENDENCE_P (overlaps_b))
+ {
+ res = chrec_known;
+ break;
+ }
}
- if (dir_vects.length () != DDR_NUM_DIR_VECTS (ddr))
- {
- fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
- dir_vects.length (),
- DDR_NUM_DIR_VECTS (ddr));
- return false;
- }
+ if (res == NULL_TREE)
+ return true;
- 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);
+ if (res == chrec_known)
+ dependence_stats.num_dependence_independent++;
+ else
+ dependence_stats.num_dependence_undetermined++;
+ finalize_ddr_dependent (ddr, res);
+ return false;
+}
- /* 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 (dist_vects, j, a_dist_v)
- if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
- break;
+/* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
- if (j == dist_vects.length ())
- {
- 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");
- }
- }
+static void
+subscript_dependence_tester (struct data_dependence_relation *ddr,
+ struct loop *loop_nest)
+{
+ if (subscript_dependence_tester_1 (ddr, 0, 1, loop_nest))
+ dependence_stats.num_dependence_dependent++;
- 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);
+ compute_subscript_distance (ddr);
+ if (build_classic_dist_vector (ddr, loop_nest))
+ build_classic_dir_vector (ddr);
+}
- /* 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 (dir_vects, j, a_dir_v)
- if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
- break;
+/* Returns true when all the access functions of A are affine or
+ constant with respect to LOOP_NEST. */
- if (j == dist_vects.length ())
- {
- 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");
- }
- }
+static bool
+access_functions_are_affine_or_constant_p (const struct data_reference *a,
+ const struct loop *loop_nest)
+{
+ unsigned int i;
+ vec<tree> fns = DR_ACCESS_FNS (a);
+ tree 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;
}
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);
-
- if (flag_check_data_deps)
- {
- /* Dump the dependences from the first algorithm. */
- 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> 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).create (0);
- DDR_DIR_VECTS (ddr).create (0);
-
- /* 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));
- }
- }
- }
+ 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))
/* Describes a location of a memory reference. */
-typedef struct data_ref_loc_d
+struct data_ref_loc
{
/* The memory reference. */
tree ref;
/* True if the memory reference is read. */
bool is_read;
-} data_ref_loc;
+
+ /* True if the data reference is conditional within the containing
+ statement, i.e. if it might not occur even when the statement
+ is executed and runs to completion. */
+ bool is_conditional_in_stmt;
+};
/* 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, va_heap> *references)
+get_references_in_stmt (gimple *stmt, vec<data_ref_loc, va_heap> *references)
{
bool clobbers_memory = false;
data_ref_loc ref;
if (DECL_P (op1)
|| (REFERENCE_CLASS_P (op1)
&& (base = get_base_address (op1))
- && TREE_CODE (base) != SSA_NAME))
+ && TREE_CODE (base) != SSA_NAME
+ && !is_gimple_min_invariant (base)))
{
ref.ref = op1;
ref.is_read = true;
+ ref.is_conditional_in_stmt = false;
references->safe_push (ref);
}
}
else if (stmt_code == GIMPLE_CALL)
{
unsigned i, n;
+ tree ptr, type;
+ unsigned int align;
ref.is_read = false;
if (gimple_call_internal_p (stmt))
if (gimple_call_lhs (stmt) == NULL_TREE)
break;
ref.is_read = true;
+ /* FALLTHRU */
case IFN_MASK_STORE:
- ref.ref = fold_build2 (MEM_REF,
- ref.is_read
- ? TREE_TYPE (gimple_call_lhs (stmt))
- : TREE_TYPE (gimple_call_arg (stmt, 3)),
- gimple_call_arg (stmt, 0),
- gimple_call_arg (stmt, 1));
+ 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.is_conditional_in_stmt = true;
+ ref.ref = fold_build2 (MEM_REF, type, gimple_call_arg (stmt, 0),
+ ptr);
references->safe_push (ref);
return false;
default:
{
ref.ref = op1;
ref.is_read = true;
+ ref.is_conditional_in_stmt = false;
references->safe_push (ref);
}
}
{
ref.ref = op0;
ref.is_read = false;
+ ref.is_conditional_in_stmt = false;
references->safe_push (ref);
}
return clobbers_memory;
}
+
+/* Returns true if the loop-nest has any data reference. */
+
+bool
+loop_nest_has_data_refs (loop_p loop)
+{
+ basic_block *bbs = get_loop_body (loop);
+ auto_vec<data_ref_loc, 3> references;
+
+ for (unsigned i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = bbs[i];
+ gimple_stmt_iterator bsi;
+
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ {
+ gimple *stmt = gsi_stmt (bsi);
+ get_references_in_stmt (stmt, &references);
+ if (references.length ())
+ {
+ free (bbs);
+ return true;
+ }
+ }
+ }
+ free (bbs);
+ return false;
+}
+
/* 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,
+opt_result
+find_data_references_in_stmt (struct loop *nest, gimple *stmt,
vec<data_reference_p> *datarefs)
{
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;
+ return opt_result::failure_at (stmt, "statement clobbers memory: %G",
+ stmt);
FOR_EACH_VEC_ELT (references, i, ref)
{
- dr = create_data_ref (nest, loop_containing_stmt (stmt),
- ref->ref, stmt, ref->is_read);
+ dr = create_data_ref (nest ? loop_preheader_edge (nest) : NULL,
+ loop_containing_stmt (stmt), ref->ref,
+ stmt, ref->is_read, ref->is_conditional_in_stmt);
gcc_assert (dr != NULL);
datarefs->safe_push (dr);
}
- references.release ();
- return ret;
+
+ return opt_result::success ();
}
/* Stores the data references in STMT to DATAREFS. If there is an
should be analyzed. */
bool
-graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
+graphite_find_data_references_in_stmt (edge nest, loop_p loop, gimple *stmt,
vec<data_reference_p> *datarefs)
{
unsigned i;
FOR_EACH_VEC_ELT (references, i, ref)
{
- dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read);
+ dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read,
+ ref->is_conditional_in_stmt);
gcc_assert (dr != NULL);
datarefs->safe_push (dr);
}
- references.release ();
return ret;
}
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
{
- gimple stmt = gsi_stmt (bsi);
+ gimple *stmt = gsi_stmt (bsi);
if (!find_data_references_in_stmt (loop, stmt, datarefs))
{
return NULL_TREE;
}
+/* Return the alignment in bytes that DRB is guaranteed to have at all
+ times. */
+
+unsigned int
+dr_alignment (innermost_loop_behavior *drb)
+{
+ /* Get the alignment of BASE_ADDRESS + INIT. */
+ unsigned int alignment = drb->base_alignment;
+ unsigned int misalignment = (drb->base_misalignment
+ + TREE_INT_CST_LOW (drb->init));
+ if (misalignment != 0)
+ alignment = MIN (alignment, misalignment & -misalignment);
+
+ /* Cap it to the alignment of OFFSET. */
+ if (!integer_zerop (drb->offset))
+ alignment = MIN (alignment, drb->offset_alignment);
+
+ /* Cap it to the alignment of STEP. */
+ if (!integer_zerop (drb->step))
+ alignment = MIN (alignment, drb->step_alignment);
+
+ return alignment;
+}
+
+/* If BASE is a pointer-typed SSA name, try to find the object that it
+ is based on. Return this object X on success and store the alignment
+ in bytes of BASE - &X in *ALIGNMENT_OUT. */
+
+static tree
+get_base_for_alignment_1 (tree base, unsigned int *alignment_out)
+{
+ if (TREE_CODE (base) != SSA_NAME || !POINTER_TYPE_P (TREE_TYPE (base)))
+ return NULL_TREE;
+
+ gimple *def = SSA_NAME_DEF_STMT (base);
+ base = analyze_scalar_evolution (loop_containing_stmt (def), base);
+
+ /* Peel chrecs and record the minimum alignment preserved by
+ all steps. */
+ unsigned int alignment = MAX_OFILE_ALIGNMENT / BITS_PER_UNIT;
+ while (TREE_CODE (base) == POLYNOMIAL_CHREC)
+ {
+ unsigned int step_alignment = highest_pow2_factor (CHREC_RIGHT (base));
+ alignment = MIN (alignment, step_alignment);
+ base = CHREC_LEFT (base);
+ }
+
+ /* Punt if the expression is too complicated to handle. */
+ if (tree_contains_chrecs (base, NULL) || !POINTER_TYPE_P (TREE_TYPE (base)))
+ return NULL_TREE;
+
+ /* The only useful cases are those for which a dereference folds to something
+ other than an INDIRECT_REF. */
+ tree ref_type = TREE_TYPE (TREE_TYPE (base));
+ tree ref = fold_indirect_ref_1 (UNKNOWN_LOCATION, ref_type, base);
+ if (!ref)
+ return NULL_TREE;
+
+ /* Analyze the base to which the steps we peeled were applied. */
+ poly_int64 bitsize, bitpos, bytepos;
+ machine_mode mode;
+ int unsignedp, reversep, volatilep;
+ tree offset;
+ base = get_inner_reference (ref, &bitsize, &bitpos, &offset, &mode,
+ &unsignedp, &reversep, &volatilep);
+ if (!base || !multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
+ return NULL_TREE;
+
+ /* Restrict the alignment to that guaranteed by the offsets. */
+ unsigned int bytepos_alignment = known_alignment (bytepos);
+ if (bytepos_alignment != 0)
+ alignment = MIN (alignment, bytepos_alignment);
+ if (offset)
+ {
+ unsigned int offset_alignment = highest_pow2_factor (offset);
+ alignment = MIN (alignment, offset_alignment);
+ }
+
+ *alignment_out = alignment;
+ return base;
+}
+
+/* Return the object whose alignment would need to be changed in order
+ to increase the alignment of ADDR. Store the maximum achievable
+ alignment in *MAX_ALIGNMENT. */
+
+tree
+get_base_for_alignment (tree addr, unsigned int *max_alignment)
+{
+ tree base = get_base_for_alignment_1 (addr, max_alignment);
+ if (base)
+ return base;
+
+ if (TREE_CODE (addr) == ADDR_EXPR)
+ addr = TREE_OPERAND (addr, 0);
+ *max_alignment = MAX_OFILE_ALIGNMENT / BITS_PER_UNIT;
+ return addr;
+}
+
/* Recursive helper function. */
static bool
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> *datarefs,
- vec<ddr_p> *dependence_relations)
-{
- if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know)
- return false;
-
- return compute_all_dependences (*datarefs, dependence_relations, vNULL,
- 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> datarefs;
- datarefs.create (nb_data_refs);
- vec<ddr_p> dependence_relations;
- dependence_relations.create (nb_data_refs * nb_data_refs);
- vec<loop_p> loop_nest;
- loop_nest.create (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)
- {
- unsigned nb_top_relations = 0;
- unsigned nb_bot_relations = 0;
- unsigned nb_chrec_relations = 0;
- struct data_dependence_relation *ddr;
-
- FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
- {
- 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++;
- }
-
- gather_stats_on_scev_database ();
- }
- }
-
- loop_nest.release ();
- 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)
-{
- struct loop *loop_nest;
-
- FOR_EACH_LOOP (loop_nest, 0)
- analyze_all_data_dependences (loop_nest);
-}
-
/* Free the memory used by a data dependence relation DDR. */
void
free_data_ref (dr);
datarefs.release ();
}
+
+/* Common routine implementing both dr_direction_indicator and
+ dr_zero_step_indicator. Return USEFUL_MIN if the indicator is known
+ to be >= USEFUL_MIN and -1 if the indicator is known to be negative.
+ Return the step as the indicator otherwise. */
+
+static tree
+dr_step_indicator (struct data_reference *dr, int useful_min)
+{
+ tree step = DR_STEP (dr);
+ if (!step)
+ return NULL_TREE;
+ STRIP_NOPS (step);
+ /* Look for cases where the step is scaled by a positive constant
+ integer, which will often be the access size. If the multiplication
+ doesn't change the sign (due to overflow effects) then we can
+ test the unscaled value instead. */
+ if (TREE_CODE (step) == MULT_EXPR
+ && TREE_CODE (TREE_OPERAND (step, 1)) == INTEGER_CST
+ && tree_int_cst_sgn (TREE_OPERAND (step, 1)) > 0)
+ {
+ tree factor = TREE_OPERAND (step, 1);
+ step = TREE_OPERAND (step, 0);
+
+ /* Strip widening and truncating conversions as well as nops. */
+ if (CONVERT_EXPR_P (step)
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (step, 0))))
+ step = TREE_OPERAND (step, 0);
+ tree type = TREE_TYPE (step);
+
+ /* Get the range of step values that would not cause overflow. */
+ widest_int minv = (wi::to_widest (TYPE_MIN_VALUE (ssizetype))
+ / wi::to_widest (factor));
+ widest_int maxv = (wi::to_widest (TYPE_MAX_VALUE (ssizetype))
+ / wi::to_widest (factor));
+
+ /* Get the range of values that the unconverted step actually has. */
+ wide_int step_min, step_max;
+ if (TREE_CODE (step) != SSA_NAME
+ || get_range_info (step, &step_min, &step_max) != VR_RANGE)
+ {
+ step_min = wi::to_wide (TYPE_MIN_VALUE (type));
+ step_max = wi::to_wide (TYPE_MAX_VALUE (type));
+ }
+
+ /* Check whether the unconverted step has an acceptable range. */
+ signop sgn = TYPE_SIGN (type);
+ if (wi::les_p (minv, widest_int::from (step_min, sgn))
+ && wi::ges_p (maxv, widest_int::from (step_max, sgn)))
+ {
+ if (wi::ge_p (step_min, useful_min, sgn))
+ return ssize_int (useful_min);
+ else if (wi::lt_p (step_max, 0, sgn))
+ return ssize_int (-1);
+ else
+ return fold_convert (ssizetype, step);
+ }
+ }
+ return DR_STEP (dr);
+}
+
+/* Return a value that is negative iff DR has a negative step. */
+
+tree
+dr_direction_indicator (struct data_reference *dr)
+{
+ return dr_step_indicator (dr, 0);
+}
+
+/* Return a value that is zero iff DR has a zero step. */
+
+tree
+dr_zero_step_indicator (struct data_reference *dr)
+{
+ return dr_step_indicator (dr, 1);
+}
+
+/* Return true if DR is known to have a nonnegative (but possibly zero)
+ step. */
+
+bool
+dr_known_forward_stride_p (struct data_reference *dr)
+{
+ tree indicator = dr_direction_indicator (dr);
+ tree neg_step_val = fold_binary (LT_EXPR, boolean_type_node,
+ fold_convert (ssizetype, indicator),
+ ssize_int (0));
+ return neg_step_val && integer_zerop (neg_step_val);
+}
projects / thirdparty / gcc.git / blobdiff