#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
static struct datadep_stats
{
int num_dependence_tests;
int num_dependence_dependent;
int num_dependence_independent;
int num_dependence_undetermined;
int num_subscript_tests;
int num_subscript_undetermined;
int num_same_subscript_function;
int num_ziv;
int num_ziv_independent;
int num_ziv_dependent;
int num_ziv_unimplemented;
int num_siv;
int num_siv_independent;
int num_siv_dependent;
int num_siv_unimplemented;
int num_miv;
int num_miv_independent;
int num_miv_dependent;
int num_miv_unimplemented;
} dependence_stats;
static tree object_analysis (tree, tree, bool, struct data_reference **,
tree *, tree *, tree *, tree *, tree *,
struct ptr_info_def **, subvar_t *);
static struct data_reference * init_data_ref (tree, tree, tree, tree, bool,
tree, tree, tree, tree, tree,
struct ptr_info_def *,
enum data_ref_type);
static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
struct data_reference *,
struct data_reference *);
static bool
ptr_decl_may_alias_p (tree ptr, tree decl,
struct data_reference *ptr_dr,
bool *aliased)
{
tree tag = NULL_TREE;
struct ptr_info_def *pi = DR_PTR_INFO (ptr_dr);
gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
if (pi)
tag = pi->name_mem_tag;
if (!tag)
tag = get_var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
if (!tag)
tag = DR_MEMTAG (ptr_dr);
if (!tag)
return false;
*aliased = is_aliased_with (tag, decl);
return true;
}
static bool
ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b,
struct data_reference *dra,
struct data_reference *drb,
bool *aliased)
{
tree tag_a = NULL_TREE, tag_b = NULL_TREE;
struct ptr_info_def *pi_a = DR_PTR_INFO (dra);
struct ptr_info_def *pi_b = DR_PTR_INFO (drb);
if (pi_a && pi_a->name_mem_tag && pi_b && pi_b->name_mem_tag)
{
tag_a = pi_a->name_mem_tag;
tag_b = pi_b->name_mem_tag;
}
else
{
tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->symbol_mem_tag;
if (!tag_a)
tag_a = DR_MEMTAG (dra);
if (!tag_a)
return false;
tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->symbol_mem_tag;
if (!tag_b)
tag_b = DR_MEMTAG (drb);
if (!tag_b)
return false;
}
if (tag_a == tag_b)
*aliased = true;
else
*aliased = may_aliases_intersect (tag_a, tag_b);
return true;
}
static bool
may_alias_p (tree base_a, tree base_b,
struct data_reference *dra,
struct data_reference *drb,
bool *aliased)
{
if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
{
if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
{
*aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
return true;
}
if (TREE_CODE (base_a) == ADDR_EXPR)
return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb,
aliased);
else
return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra,
aliased);
}
return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
}
static bool
record_ptr_differ_p (struct data_reference *dra,
struct data_reference *drb)
{
bool aliased;
tree base_a = DR_BASE_OBJECT (dra);
tree base_b = DR_BASE_OBJECT (drb);
if (TREE_CODE (base_b) != COMPONENT_REF)
return false;
while (TREE_CODE (base_b) == COMPONENT_REF)
base_b = TREE_OPERAND (base_b, 0);
if (TREE_CODE (base_a) == INDIRECT_REF
&& ((TREE_CODE (base_b) == VAR_DECL
&& (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra,
&aliased)
&& !aliased))
|| (TREE_CODE (base_b) == INDIRECT_REF
&& (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
TREE_OPERAND (base_b, 0), dra, drb,
&aliased)
&& !aliased))))
return true;
else
return false;
}
static bool
record_record_differ_p (struct data_reference *dra,
struct data_reference *drb)
{
bool aliased;
tree base_a = DR_BASE_OBJECT (dra);
tree base_b = DR_BASE_OBJECT (drb);
if (TREE_CODE (base_b) != COMPONENT_REF
|| TREE_CODE (base_a) != COMPONENT_REF)
return false;
while (TREE_CODE (base_b) == COMPONENT_REF)
base_b = TREE_OPERAND (base_b, 0);
while (TREE_CODE (base_a) == COMPONENT_REF)
base_a = TREE_OPERAND (base_a, 0);
if (TREE_CODE (base_a) == INDIRECT_REF
&& TREE_CODE (base_b) == INDIRECT_REF
&& ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
TREE_OPERAND (base_b, 0),
dra, drb, &aliased)
&& !aliased)
return true;
else
return false;
}
static bool
record_array_differ_p (struct data_reference *dra,
struct data_reference *drb)
{
bool aliased;
tree base_a = DR_BASE_OBJECT (dra);
tree base_b = DR_BASE_OBJECT (drb);
if (TREE_CODE (base_b) != COMPONENT_REF)
return false;
while (TREE_CODE (base_b) == COMPONENT_REF)
base_b = TREE_OPERAND (base_b, 0);
if (TREE_CODE (base_a) == VAR_DECL
&& (TREE_CODE (base_b) == VAR_DECL
|| (TREE_CODE (base_b) == INDIRECT_REF
&& (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb,
&aliased)
&& !aliased))))
return true;
else
return false;
}
static bool
array_ptr_differ_p (tree base_a, tree base_b,
struct data_reference *drb)
{
bool aliased;
if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF
&& (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
&& !aliased))
return true;
else
return false;
}
static bool
base_object_differ_p (struct data_reference *a,
struct data_reference *b,
bool *differ_p)
{
tree base_a = DR_BASE_OBJECT (a);
tree base_b = DR_BASE_OBJECT (b);
bool aliased;
if (!base_a || !base_b)
return false;
if (base_a == base_b)
{
*differ_p = false;
return true;
}
if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
&& TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
{
*differ_p = false;
return true;
}
if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
&& TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
&& TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
{
*differ_p = false;
return true;
}
if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
{
*differ_p = true;
return true;
}
if (array_ptr_differ_p (base_a, base_b, b)
|| array_ptr_differ_p (base_b, base_a, a))
{
*differ_p = true;
return true;
}
if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
&& (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b,
&aliased)
&& !aliased))
{
*differ_p = true;
return true;
}
if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
&& ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
&& TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
&& TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
|| (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
&& TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
&& TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
{
*differ_p = true;
return true;
}
if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
{
*differ_p = true;
return true;
}
if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
{
*differ_p = true;
return true;
}
if (record_record_differ_p (a, b))
{
*differ_p = true;
return true;
}
return false;
}
static bool
base_addr_differ_p (struct data_reference *dra,
struct data_reference *drb,
bool *differ_p)
{
tree addr_a = DR_BASE_ADDRESS (dra);
tree addr_b = DR_BASE_ADDRESS (drb);
tree type_a, type_b;
bool aliased;
if (!addr_a || !addr_b)
return false;
type_a = TREE_TYPE (addr_a);
type_b = TREE_TYPE (addr_b);
gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
return base_object_differ_p (dra, drb, differ_p);
if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE
&& (addr_a == addr_b
|| (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
&& TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0))))
{
tree offset_a = DR_OFFSET (dra);
tree offset_b = DR_OFFSET (drb);
STRIP_NOPS (offset_a);
STRIP_NOPS (offset_b);
if (offset_a == offset_b
|| (TREE_CODE (offset_a) == MULT_EXPR
&& TREE_CODE (offset_b) == MULT_EXPR
&& TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
&& TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
{
*differ_p = false;
return true;
}
}
if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
{
*differ_p = true;
return true;
}
else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
|| (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
{
*differ_p = true;
return true;
}
return false;
}
static inline bool
tree_fold_divides_p (tree a,
tree b)
{
return tree_int_cst_equal (a, tree_fold_gcd (a, b));
}
static inline bool
int_divides_p (int a, int b)
{
return ((b % a) == 0);
}
void
dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
{
unsigned int i;
struct data_reference *dr;
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
dump_data_reference (file, dr);
}
void
dump_data_dependence_relations (FILE *file,
VEC (ddr_p, heap) *ddrs)
{
unsigned int i;
struct data_dependence_relation *ddr;
for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
dump_data_dependence_relation (file, ddr);
}
void
dump_data_reference (FILE *outf,
struct data_reference *dr)
{
unsigned int i;
fprintf (outf, "(Data Ref: \n stmt: ");
print_generic_stmt (outf, DR_STMT (dr), 0);
fprintf (outf, " ref: ");
print_generic_stmt (outf, DR_REF (dr), 0);
fprintf (outf, " base_object: ");
print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
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);
}
fprintf (outf, ")\n");
}
void
dump_subscript (FILE *outf, struct subscript *subscript)
{
tree chrec = SUB_CONFLICTS_IN_A (subscript);
fprintf (outf, "\n (subscript \n");
fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
print_generic_stmt (outf, chrec, 0);
if (chrec == chrec_known)
fprintf (outf, " (no dependence)\n");
else if (chrec_contains_undetermined (chrec))
fprintf (outf, " (don't know)\n");
else
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
fprintf (outf, " last_conflict: ");
print_generic_stmt (outf, last_iteration, 0);
}
chrec = SUB_CONFLICTS_IN_B (subscript);
fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
print_generic_stmt (outf, chrec, 0);
if (chrec == chrec_known)
fprintf (outf, " (no dependence)\n");
else if (chrec_contains_undetermined (chrec))
fprintf (outf, " (don't know)\n");
else
{
tree last_iteration = SUB_LAST_CONFLICT (subscript);
fprintf (outf, " last_conflict: ");
print_generic_stmt (outf, last_iteration, 0);
}
fprintf (outf, " (Subscript distance: ");
print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
fprintf (outf, " )\n");
fprintf (outf, " )\n");
}
void
print_direction_vector (FILE *outf,
lambda_vector dirv,
int length)
{
int eq;
for (eq = 0; eq < length; eq++)
{
enum data_dependence_direction dir = dirv[eq];
switch (dir)
{
case dir_positive:
fprintf (outf, " +");
break;
case dir_negative:
fprintf (outf, " -");
break;
case dir_equal:
fprintf (outf, " =");
break;
case dir_positive_or_equal:
fprintf (outf, " +=");
break;
case dir_positive_or_negative:
fprintf (outf, " +-");
break;
case dir_negative_or_equal:
fprintf (outf, " -=");
break;
case dir_star:
fprintf (outf, " *");
break;
default:
fprintf (outf, "indep");
break;
}
}
fprintf (outf, "\n");
}
void
print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
int length)
{
unsigned j;
lambda_vector v;
for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
print_direction_vector (outf, v, length);
}
void
print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
int length)
{
unsigned j;
lambda_vector v;
for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
print_lambda_vector (outf, v, length);
}
void
debug_data_dependence_relation (struct data_dependence_relation *ddr)
{
dump_data_dependence_relation (stderr, ddr);
}
void
dump_data_dependence_relation (FILE *outf,
struct data_dependence_relation *ddr)
{
struct data_reference *dra, *drb;
dra = DDR_A (ddr);
drb = DDR_B (ddr);
fprintf (outf, "(Data Dep: \n");
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
fprintf (outf, " (don't know)\n");
else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
fprintf (outf, " (no dependence)\n");
else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
unsigned int i;
struct loop *loopi;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
fprintf (outf, " access_fn_A: ");
print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
fprintf (outf, " access_fn_B: ");
print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
}
fprintf (outf, " loop nest: (");
for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
fprintf (outf, "%d ", loopi->num);
fprintf (outf, ")\n");
for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
{
fprintf (outf, " distance_vector: ");
print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
DDR_NB_LOOPS (ddr));
}
for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
{
fprintf (outf, " direction_vector: ");
print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
DDR_NB_LOOPS (ddr));
}
}
fprintf (outf, ")\n");
}
void
dump_data_dependence_direction (FILE *file,
enum data_dependence_direction dir)
{
switch (dir)
{
case dir_positive:
fprintf (file, "+");
break;
case dir_negative:
fprintf (file, "-");
break;
case dir_equal:
fprintf (file, "=");
break;
case dir_positive_or_negative:
fprintf (file, "+-");
break;
case dir_positive_or_equal:
fprintf (file, "+=");
break;
case dir_negative_or_equal:
fprintf (file, "-=");
break;
case dir_star:
fprintf (file, "*");
break;
default:
break;
}
}
void
dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
{
unsigned int i, j;
struct data_dependence_relation *ddr;
lambda_vector v;
for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
{
for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
{
fprintf (file, "DISTANCE_V (");
print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
fprintf (file, ")\n");
}
for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
{
fprintf (file, "DIRECTION_V (");
print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
fprintf (file, ")\n");
}
}
fprintf (file, "\n\n");
}
void
dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
{
unsigned int i;
struct data_dependence_relation *ddr;
for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
dump_data_dependence_relation (file, ddr);
fprintf (file, "\n\n");
}
static void
estimate_niter_from_size_of_data (struct loop *loop,
tree opnd0,
tree access_fn,
tree stmt)
{
tree estimation = NULL_TREE;
tree array_size, data_size, element_size;
tree init, step;
init = initial_condition (access_fn);
step = evolution_part_in_loop_num (access_fn, loop->num);
array_size = TYPE_SIZE (TREE_TYPE (opnd0));
element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
if (array_size == NULL_TREE
|| TREE_CODE (array_size) != INTEGER_CST
|| TREE_CODE (element_size) != INTEGER_CST)
return;
data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
array_size, element_size);
if (init != NULL_TREE
&& step != NULL_TREE
&& TREE_CODE (init) == INTEGER_CST
&& TREE_CODE (step) == INTEGER_CST)
{
tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step);
tree sign = fold_binary (GT_EXPR, boolean_type_node, i_plus_s, init);
if (sign == boolean_true_node)
estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
fold_build2 (MINUS_EXPR, integer_type_node,
data_size, init), step);
else if (sign == boolean_false_node)
estimation =
fold_build2 (PLUS_EXPR, integer_type_node,
fold_build2 (CEIL_DIV_EXPR, integer_type_node,
init,
fold_build2 (MINUS_EXPR, unsigned_type_node,
integer_zero_node, step)),
integer_one_node);
if (estimation)
record_estimate (loop, estimation, boolean_true_node, stmt);
}
}
static tree
analyze_array_indexes (struct loop *loop,
VEC(tree,heap) **access_fns,
tree ref, tree stmt,
bool estimate_only)
{
tree opnd0, opnd1;
tree access_fn;
opnd0 = TREE_OPERAND (ref, 0);
opnd1 = TREE_OPERAND (ref, 1);
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, opnd1));
if (estimate_only
&& chrec_contains_undetermined (loop->estimated_nb_iterations))
estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
if (!estimate_only)
VEC_safe_push (tree, heap, *access_fns, access_fn);
if (TREE_CODE (opnd0) == ARRAY_REF)
return analyze_array_indexes (loop, access_fns, opnd0, stmt, estimate_only);
else
return opnd0;
}
void
estimate_iters_using_array (tree stmt, tree ref)
{
analyze_array_indexes (loop_containing_stmt (stmt), NULL, ref, stmt,
true);
}
struct data_reference *
analyze_array (tree stmt, tree ref, bool is_read)
{
struct data_reference *res;
VEC(tree,heap) *acc_fns;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(analyze_array \n");
fprintf (dump_file, " (ref = ");
print_generic_stmt (dump_file, ref, 0);
fprintf (dump_file, ")\n");
}
res = XNEW (struct data_reference);
DR_STMT (res) = stmt;
DR_REF (res) = ref;
acc_fns = VEC_alloc (tree, heap, 3);
DR_BASE_OBJECT (res) = analyze_array_indexes
(loop_containing_stmt (stmt), &acc_fns, ref, stmt, false);
DR_TYPE (res) = ARRAY_REF_TYPE;
DR_SET_ACCESS_FNS (res, acc_fns);
DR_IS_READ (res) = is_read;
DR_BASE_ADDRESS (res) = NULL_TREE;
DR_OFFSET (res) = NULL_TREE;
DR_INIT (res) = NULL_TREE;
DR_STEP (res) = NULL_TREE;
DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
DR_MEMTAG (res) = NULL_TREE;
DR_PTR_INFO (res) = NULL;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
return res;
}
static struct data_reference *
analyze_indirect_ref (tree stmt, tree ref, bool is_read)
{
struct loop *loop = loop_containing_stmt (stmt);
tree ptr_ref = TREE_OPERAND (ref, 0);
tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
tree init = initial_condition_in_loop_num (access_fn, loop->num);
tree base_address = NULL_TREE, evolution, step = NULL_TREE;
struct ptr_info_def *ptr_info = NULL;
if (TREE_CODE (ptr_ref) == SSA_NAME)
ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
STRIP_NOPS (init);
if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nBad access function of ptr: ");
print_generic_expr (dump_file, ref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nAccess function of ptr: ");
print_generic_expr (dump_file, access_fn, TDF_SLIM);
fprintf (dump_file, "\n");
}
if (!expr_invariant_in_loop_p (loop, init))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
}
else
{
base_address = init;
evolution = evolution_part_in_loop_num (access_fn, loop->num);
if (evolution != chrec_dont_know)
{
if (!evolution)
step = ssize_int (0);
else
{
if (TREE_CODE (evolution) == INTEGER_CST)
step = fold_convert (ssizetype, evolution);
else
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nnon constant step for ptr access.\n");
}
}
else
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nunknown evolution of ptr.\n");
}
return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address,
NULL_TREE, step, NULL_TREE, NULL_TREE,
ptr_info, POINTER_REF_TYPE);
}
struct data_reference *
init_data_ref (tree stmt,
tree ref,
tree base,
tree access_fn,
bool is_read,
tree base_address,
tree init_offset,
tree step,
tree misalign,
tree memtag,
struct ptr_info_def *ptr_info,
enum data_ref_type type)
{
struct data_reference *res;
VEC(tree,heap) *acc_fns;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(init_data_ref \n");
fprintf (dump_file, " (ref = ");
print_generic_stmt (dump_file, ref, 0);
fprintf (dump_file, ")\n");
}
res = XNEW (struct data_reference);
DR_STMT (res) = stmt;
DR_REF (res) = ref;
DR_BASE_OBJECT (res) = base;
DR_TYPE (res) = type;
acc_fns = VEC_alloc (tree, heap, 3);
DR_SET_ACCESS_FNS (res, acc_fns);
VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
DR_IS_READ (res) = is_read;
DR_BASE_ADDRESS (res) = base_address;
DR_OFFSET (res) = init_offset;
DR_INIT (res) = NULL_TREE;
DR_STEP (res) = step;
DR_OFFSET_MISALIGNMENT (res) = misalign;
DR_MEMTAG (res) = memtag;
DR_PTR_INFO (res) = ptr_info;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
return res;
}
static tree
strip_conversion (tree expr)
{
tree to, ti, oprnd0;
while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
{
to = TREE_TYPE (expr);
oprnd0 = TREE_OPERAND (expr, 0);
ti = TREE_TYPE (oprnd0);
if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
return NULL_TREE;
if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
return NULL_TREE;
expr = oprnd0;
}
return expr;
}
static bool
analyze_offset_expr (tree expr,
struct loop *loop,
tree *initial_offset,
tree *misalign,
tree *aligned_to,
tree *step)
{
tree oprnd0;
tree oprnd1;
tree left_offset = ssize_int (0);
tree right_offset = ssize_int (0);
tree left_misalign = ssize_int (0);
tree right_misalign = ssize_int (0);
tree left_step = ssize_int (0);
tree right_step = ssize_int (0);
enum tree_code code;
tree init, evolution;
tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
*step = NULL_TREE;
*misalign = NULL_TREE;
*aligned_to = NULL_TREE;
*initial_offset = NULL_TREE;
expr = strip_conversion (expr);
if (!expr)
return false;
if (TREE_CODE (expr) == INTEGER_CST)
{
*initial_offset = fold_convert (ssizetype, expr);
*misalign = fold_convert (ssizetype, expr);
*step = ssize_int (0);
return true;
}
if (SSA_VAR_P (expr))
{
tree access_fn = analyze_scalar_evolution (loop, expr);
if (access_fn == chrec_dont_know)
return false;
init = initial_condition_in_loop_num (access_fn, loop->num);
if (!expr_invariant_in_loop_p (loop, init))
return false;
evolution = evolution_part_in_loop_num (access_fn, loop->num);
if (evolution && TREE_CODE (evolution) != INTEGER_CST)
return false;
if (TREE_CODE (init) == INTEGER_CST)
*misalign = fold_convert (ssizetype, init);
else
*misalign = NULL_TREE;
*initial_offset = fold_convert (ssizetype, init);
*step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
return true;
}
if (!BINARY_CLASS_P (expr))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nNot binary expression ");
print_generic_expr (dump_file, expr, TDF_SLIM);
fprintf (dump_file, "\n");
}
return false;
}
oprnd0 = TREE_OPERAND (expr, 0);
oprnd1 = TREE_OPERAND (expr, 1);
if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
&left_aligned_to, &left_step)
|| !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
&right_aligned_to, &right_step))
return false;
code = TREE_CODE (expr);
switch (code)
{
case MULT_EXPR:
if (TREE_CODE (right_offset) != INTEGER_CST)
return false;
left_offset = strip_conversion (left_offset);
if (!left_offset)
return false;
if (SSA_VAR_P (left_offset))
{
*misalign = NULL_TREE;
*aligned_to = ssize_int (highest_pow2_factor (right_offset));
}
else
{
if (left_misalign)
{
*misalign = size_binop (code, left_misalign, right_misalign);
if (left_aligned_to && right_aligned_to)
*aligned_to = size_binop (MIN_EXPR, left_aligned_to,
right_aligned_to);
else
*aligned_to = left_aligned_to ?
left_aligned_to : right_aligned_to;
}
else
*misalign = NULL_TREE;
}
*step = size_binop (MULT_EXPR, left_step, right_offset);
break;
case PLUS_EXPR:
case MINUS_EXPR:
*step = size_binop (code, left_step, right_step);
if ((!left_misalign && !left_aligned_to)
|| (!right_misalign && !right_aligned_to))
{
*misalign = NULL_TREE;
*aligned_to = NULL_TREE;
break;
}
if (left_misalign && right_misalign)
*misalign = size_binop (code, left_misalign, right_misalign);
else
*misalign = left_misalign ? left_misalign : right_misalign;
if (left_aligned_to && right_aligned_to)
*aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
else
*aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
break;
default:
gcc_unreachable ();
}
*initial_offset = fold_convert (ssizetype,
fold_build2 (code, TREE_TYPE (left_offset),
left_offset,
right_offset));
return true;
}
static tree
address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
tree *offset, tree *misalign, tree *aligned_to, tree *step)
{
tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
tree dummy, address_aligned_to = NULL_TREE;
struct ptr_info_def *dummy1;
subvar_t dummy2;
switch (TREE_CODE (expr))
{
case PLUS_EXPR:
case MINUS_EXPR:
oprnd0 = TREE_OPERAND (expr, 0);
oprnd1 = TREE_OPERAND (expr, 1);
STRIP_NOPS (oprnd0);
STRIP_NOPS (oprnd1);
base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
&address_misalign, &address_aligned_to,
step);
base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
&address_misalign, &address_aligned_to,
step);
if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
"\neither more than one address or no addresses in expr ");
print_generic_expr (dump_file, expr, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
oprnd0 = TREE_OPERAND (expr, 0);
oprnd1 = TREE_OPERAND (expr, 1);
offset_expr = base_addr0 ?
fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
{
*misalign = size_binop (TREE_CODE (expr), address_misalign,
offset_expr);
*aligned_to = address_aligned_to;
}
else
{
*misalign = NULL_TREE;
*aligned_to = NULL_TREE;
}
*offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
return base_addr0 ? base_addr0 : base_addr1;
case ADDR_EXPR:
base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
&dr, offset, misalign, aligned_to, step,
&dummy, &dummy1, &dummy2);
return base_address;
case SSA_NAME:
if (!POINTER_TYPE_P (TREE_TYPE (expr)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nnot pointer SSA_NAME ");
print_generic_expr (dump_file, expr, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
*aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
*misalign = ssize_int (0);
*offset = ssize_int (0);
*step = ssize_int (0);
return expr;
default:
return NULL_TREE;
}
}
static tree
object_analysis (tree memref, tree stmt, bool is_read,
struct data_reference **dr, tree *offset, tree *misalign,
tree *aligned_to, tree *step, tree *memtag,
struct ptr_info_def **ptr_info, subvar_t *subvars)
{
tree base = NULL_TREE, base_address = NULL_TREE;
tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
tree object_step = ssize_int (0), address_step = ssize_int (0);
tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
HOST_WIDE_INT pbitsize, pbitpos;
tree poffset, bit_pos_in_bytes;
enum machine_mode pmode;
int punsignedp, pvolatilep;
tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
struct loop *loop = loop_containing_stmt (stmt);
struct data_reference *ptr_dr = NULL;
tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
tree comp_ref = NULL_TREE;
*ptr_info = NULL;
if (handled_component_p (memref))
{
if (!(*dr))
{
if (TREE_CODE (memref) == ARRAY_REF)
*dr = analyze_array (stmt, memref, is_read);
else if (TREE_CODE (memref) == COMPONENT_REF)
comp_ref = memref;
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\ndata-ref of unsupported type ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
}
base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
&pmode, &punsignedp, &pvolatilep, false);
if (!base)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nfailed to get inner ref for ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
if (poffset
&& !analyze_offset_expr (poffset, loop, &object_offset,
&object_misalign, &object_aligned_to,
&object_step))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nfailed to compute offset or step for ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
if (pbitpos%BITS_PER_UNIT)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nbit offset alignment.\n");
return NULL_TREE;
}
object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
if (object_misalign)
object_misalign = size_binop (PLUS_EXPR, object_misalign,
bit_pos_in_bytes);
memref = base;
}
if (DECL_P (memref))
{
if (!(*dr))
{
if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
{
*dr = analyze_array (stmt, TREE_OPERAND (comp_ref, 0), is_read);
if (DR_NUM_DIMENSIONS (*dr) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\n multidimensional component ref ");
print_generic_expr (dump_file, comp_ref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
}
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nunhandled decl ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
}
if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
*subvars = get_subvars_for_var (memref);
base_address = build_fold_addr_expr (memref);
*memtag = memref;
}
else if (TREE_CODE (memref) == INDIRECT_REF)
{
tree ptr_ref = TREE_OPERAND (memref, 0);
if (TREE_CODE (ptr_ref) == SSA_NAME)
*ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
if (!ptr_dr)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nfailed to create dr for ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
ptr_step = DR_STEP (ptr_dr);
ptr_init = DR_BASE_ADDRESS (ptr_dr);
if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
{
*dr = (*dr) ? *dr : ptr_dr;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nbad pointer access ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
if (integer_zerop (ptr_step) && !(*dr))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nptr is loop invariant.\n");
*dr = ptr_dr;
return NULL_TREE;
}
object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
if (!*dr)
*dr = ptr_dr;
base_address = address_analysis (ptr_init, stmt, is_read, *dr,
&address_offset, &address_misalign,
&address_aligned_to, &address_step);
if (!base_address)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nfailed to analyze address ");
print_generic_expr (dump_file, ptr_init, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
switch (TREE_CODE (base_address))
{
case SSA_NAME:
*memtag = get_var_ann (SSA_NAME_VAR (base_address))->symbol_mem_tag;
if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
*memtag = get_var_ann (
SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->symbol_mem_tag;
break;
case ADDR_EXPR:
*memtag = TREE_OPERAND (base_address, 0);
break;
default:
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nno memtag for ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
*memtag = NULL_TREE;
break;
}
}
if (!base_address)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\ndata-ref of unsupported type ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL_TREE;
}
if (comp_ref)
DR_REF (*dr) = comp_ref;
if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
*subvars = get_subvars_for_var (*memtag);
*offset = size_binop (PLUS_EXPR, object_offset, address_offset);
if ((!object_misalign && !object_aligned_to)
|| (!address_misalign && !address_aligned_to))
{
*misalign = NULL_TREE;
*aligned_to = NULL_TREE;
}
else
{
if (object_misalign && address_misalign)
*misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
else
*misalign = object_misalign ? object_misalign : address_misalign;
if (object_aligned_to && address_aligned_to)
*aligned_to = size_binop (MIN_EXPR, object_aligned_to,
address_aligned_to);
else
*aligned_to = object_aligned_to ?
object_aligned_to : address_aligned_to;
}
*step = size_binop (PLUS_EXPR, object_step, address_step);
return base_address;
}
static bool
analyze_offset (tree offset, tree *invariant, tree *constant)
{
tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
enum tree_code code = TREE_CODE (offset);
*invariant = NULL_TREE;
*constant = NULL_TREE;
if (code != PLUS_EXPR && code != MINUS_EXPR)
{
if (TREE_CODE (offset) == INTEGER_CST)
*constant = offset;
else
*invariant = offset;
return true;
}
op0 = TREE_OPERAND (offset, 0);
op1 = TREE_OPERAND (offset, 1);
if (!analyze_offset (op0, &invariant_0, &constant_0)
|| !analyze_offset (op1, &invariant_1, &constant_1))
return false;
if (constant_0 && constant_1)
return false;
*constant = constant_0 ? constant_0 : constant_1;
if (code == MINUS_EXPR && constant_1)
*constant = fold_build1 (NEGATE_EXPR, TREE_TYPE (*constant), *constant);
if (invariant_0 && invariant_1)
*invariant =
fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
else
{
*invariant = invariant_0 ? invariant_0 : invariant_1;
if (code == MINUS_EXPR && invariant_1)
*invariant =
fold_build1 (NEGATE_EXPR, TREE_TYPE (*invariant), *invariant);
}
return true;
}
static void
free_data_ref (data_reference_p dr)
{
DR_FREE_ACCESS_FNS (dr);
free (dr);
}
static struct data_reference *
create_data_ref (tree memref, tree stmt, bool is_read)
{
struct data_reference *dr = NULL;
tree base_address, offset, step, misalign, memtag;
struct loop *loop = loop_containing_stmt (stmt);
tree invariant = NULL_TREE, constant = NULL_TREE;
tree type_size, init_cond;
struct ptr_info_def *ptr_info;
subvar_t subvars = NULL;
tree aligned_to, type = NULL_TREE, orig_offset;
if (!memref)
return NULL;
base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
&misalign, &aligned_to, &step, &memtag,
&ptr_info, &subvars);
if (!dr || !base_address)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL;
}
DR_BASE_ADDRESS (dr) = base_address;
DR_OFFSET (dr) = offset;
DR_INIT (dr) = ssize_int (0);
DR_STEP (dr) = step;
DR_OFFSET_MISALIGNMENT (dr) = misalign;
DR_ALIGNED_TO (dr) = aligned_to;
DR_MEMTAG (dr) = memtag;
DR_PTR_INFO (dr) = ptr_info;
DR_SUBVARS (dr) = subvars;
type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
orig_offset = offset;
STRIP_NOPS (offset);
if (offset != orig_offset)
type = TREE_TYPE (orig_offset);
if (!analyze_offset (offset, &invariant, &constant))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\ncreate_data_ref: failed to analyze dr's");
fprintf (dump_file, " offset for ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n");
}
return NULL;
}
if (type && invariant)
invariant = fold_convert (type, invariant);
if (constant)
{
DR_INIT (dr) = fold_convert (ssizetype, constant);
init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
constant, type_size);
}
else
DR_INIT (dr) = init_cond = ssize_int (0);
if (invariant)
DR_OFFSET (dr) = invariant;
else
DR_OFFSET (dr) = ssize_int (0);
if (!DR_BASE_OBJECT (dr)
|| (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1))
{
tree access_fn;
tree new_step;
access_fn = DR_ACCESS_FN (dr, 0);
if (automatically_generated_chrec_p (access_fn))
{
free_data_ref (dr);
return NULL;
}
new_step = size_binop (TRUNC_DIV_EXPR,
fold_convert (ssizetype, step), type_size);
init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt);
new_step = chrec_convert (chrec_type (access_fn), new_step, stmt);
if (automatically_generated_chrec_p (init_cond)
|| automatically_generated_chrec_p (new_step))
{
free_data_ref (dr);
return NULL;
}
access_fn = chrec_replace_initial_condition (access_fn, init_cond);
access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
struct ptr_info_def *pi = DR_PTR_INFO (dr);
fprintf (dump_file, "\nCreated dr for ");
print_generic_expr (dump_file, memref, TDF_SLIM);
fprintf (dump_file, "\n\tbase_address: ");
print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
fprintf (dump_file, "\n\toffset from base address: ");
print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
fprintf (dump_file, "\n\tconstant offset from base address: ");
print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
fprintf (dump_file, "\n\tbase_object: ");
print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
fprintf (dump_file, "\n\tstep: ");
print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
fprintf (dump_file, "B\n\tmisalignment from base: ");
print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
if (DR_OFFSET_MISALIGNMENT (dr))
fprintf (dump_file, "B");
if (DR_ALIGNED_TO (dr))
{
fprintf (dump_file, "\n\taligned to: ");
print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
}
fprintf (dump_file, "\n\tmemtag: ");
print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
fprintf (dump_file, "\n");
if (pi && pi->name_mem_tag)
{
fprintf (dump_file, "\n\tnametag: ");
print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
fprintf (dump_file, "\n");
}
}
return dr;
}
static bool
all_chrecs_equal_p (tree chrec)
{
int j;
for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
if (!eq_evolutions_p (TREE_VEC_ELT (chrec, j),
TREE_VEC_ELT (chrec, j + 1)))
return false;
return true;
}
static void
compute_subscript_distance (struct data_dependence_relation *ddr)
{
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
unsigned int i;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
tree conflicts_a, conflicts_b, difference;
struct subscript *subscript;
subscript = DDR_SUBSCRIPT (ddr, i);
conflicts_a = SUB_CONFLICTS_IN_A (subscript);
conflicts_b = SUB_CONFLICTS_IN_B (subscript);
if (TREE_CODE (conflicts_a) == TREE_VEC)
{
if (!all_chrecs_equal_p (conflicts_a))
{
SUB_DISTANCE (subscript) = chrec_dont_know;
return;
}
else
conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
}
if (TREE_CODE (conflicts_b) == TREE_VEC)
{
if (!all_chrecs_equal_p (conflicts_b))
{
SUB_DISTANCE (subscript) = chrec_dont_know;
return;
}
else
conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
}
conflicts_b = chrec_convert (integer_type_node, conflicts_b,
NULL_TREE);
conflicts_a = chrec_convert (integer_type_node, conflicts_a,
NULL_TREE);
difference = chrec_fold_minus
(integer_type_node, conflicts_b, conflicts_a);
if (evolution_function_is_constant_p (difference))
SUB_DISTANCE (subscript) = difference;
else
SUB_DISTANCE (subscript) = chrec_dont_know;
}
}
}
static struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
struct data_reference *b,
VEC (loop_p, heap) *loop_nest)
{
struct data_dependence_relation *res;
bool differ_p, known_dependence;
unsigned int i;
res = XNEW (struct data_dependence_relation);
DDR_A (res) = a;
DDR_B (res) = b;
DDR_LOOP_NEST (res) = NULL;
if (a == NULL || b == NULL)
{
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
return res;
}
if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
&& DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
{
DDR_ARE_DEPENDENT (res) = chrec_known;
return res;
}
if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
known_dependence = base_addr_differ_p (a, b, &differ_p);
else
known_dependence = base_object_differ_p (a, b, &differ_p);
if (!known_dependence)
{
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
return res;
}
if (differ_p)
{
DDR_ARE_DEPENDENT (res) = chrec_known;
return res;
}
DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
DDR_LOOP_NEST (res) = loop_nest;
DDR_DIR_VECTS (res) = NULL;
DDR_DIST_VECTS (res) = NULL;
for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
{
struct subscript *subscript;
subscript = XNEW (struct subscript);
SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
SUB_DISTANCE (subscript) = chrec_dont_know;
VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
}
return res;
}
static inline void
finalize_ddr_dependent (struct data_dependence_relation *ddr,
tree chrec)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(dependence classified: ");
print_generic_expr (dump_file, chrec, 0);
fprintf (dump_file, ")\n");
}
DDR_ARE_DEPENDENT (ddr) = chrec;
VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
}
static inline void
non_affine_dependence_relation (struct data_dependence_relation *ddr)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
DDR_AFFINE_P (ddr) = false;
}
static inline bool
ziv_subscript_p (tree chrec_a,
tree chrec_b)
{
return (evolution_function_is_constant_p (chrec_a)
&& evolution_function_is_constant_p (chrec_b));
}
static bool
siv_subscript_p (tree chrec_a,
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;
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;
default:
return true;
}
default:
return true;
}
}
return false;
}
static void
analyze_ziv_subscript (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b,
tree *last_conflicts)
{
tree difference;
dependence_stats.num_ziv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_ziv_subscript \n");
chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
switch (TREE_CODE (difference))
{
case INTEGER_CST:
if (integer_zerop (difference))
{
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
*last_conflicts = chrec_dont_know;
dependence_stats.num_ziv_dependent++;
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
dependence_stats.num_ziv_independent++;
}
break;
default:
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
dependence_stats.num_ziv_unimplemented++;
break;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static tree
get_number_of_iters_for_loop (int loopnum)
{
tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
if (TREE_CODE (numiter) != INTEGER_CST)
numiter = current_loops->parray[loopnum]->estimated_nb_iterations;
if (chrec_contains_undetermined (numiter))
return NULL_TREE;
return numiter;
}
static void
analyze_siv_subscript_cst_affine (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b,
tree *last_conflicts)
{
bool value0, value1, value2;
tree difference;
chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
difference = chrec_fold_minus
(integer_type_node, initial_condition (chrec_b), chrec_a);
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 = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
return;
}
else
{
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 = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
dependence_stats.num_siv_unimplemented++;
return;
}
else
{
if (value1 == true)
{
if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
{
tree numiter;
int loopnum = CHREC_VARIABLE (chrec_b);
*overlaps_a = integer_zero_node;
*overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
fold_build1 (ABS_EXPR,
integer_type_node,
difference),
CHREC_RIGHT (chrec_b));
*last_conflicts = integer_one_node;
numiter = get_number_of_iters_for_loop (loopnum);
if (numiter != NULL_TREE
&& TREE_CODE (*overlaps_b) == INTEGER_CST
&& tree_int_cst_lt (numiter, *overlaps_b))
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
dependence_stats.num_siv_dependent++;
return;
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*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");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
dependence_stats.num_siv_unimplemented++;
return;
}
else
{
if (value2 == false)
{
if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
{
tree numiter;
int loopnum = CHREC_VARIABLE (chrec_b);
*overlaps_a = integer_zero_node;
*overlaps_b = fold_build2 (EXACT_DIV_EXPR,
integer_type_node, difference,
CHREC_RIGHT (chrec_b));
*last_conflicts = integer_one_node;
numiter = get_number_of_iters_for_loop (loopnum);
if (numiter != NULL_TREE
&& TREE_CODE (*overlaps_b) == INTEGER_CST
&& tree_int_cst_lt (numiter, *overlaps_b))
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
dependence_stats.num_siv_dependent++;
return;
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
dependence_stats.num_siv_independent++;
return;
}
}
}
}
}
static int
initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
{
gcc_assert (chrec);
if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
return int_cst_value (chrec);
A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
}
#define FLOOR_DIV(x,y) ((x) / (y))
static void
compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
tree *overlaps_a, tree *overlaps_b,
tree *last_conflicts, int dim)
{
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;
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;
tau2 = FLOOR_DIV (niter, step_overlaps_a);
tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
last_conflict = tau2;
*overlaps_a = build_polynomial_chrec
(dim, integer_zero_node,
build_int_cst (NULL_TREE, step_overlaps_a));
*overlaps_b = build_polynomial_chrec
(dim, integer_zero_node,
build_int_cst (NULL_TREE, step_overlaps_b));
*last_conflicts = build_int_cst (NULL_TREE, last_conflict);
}
else
{
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
*last_conflicts = integer_zero_node;
}
}
static void
compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
tree *overlaps_a, tree *overlaps_b,
tree *last_conflicts)
{
bool xz_p, yz_p, xyz_p;
int step_x, step_y, step_z;
int niter_x, niter_y, niter_z, niter;
tree numiter_x, numiter_y, numiter_z;
tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
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));
numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
|| numiter_z == NULL_TREE)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
return;
}
niter_x = int_cst_value (numiter_x);
niter_y = int_cst_value (numiter_y);
niter_z = int_cst_value (numiter_z);
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);
xz_p = !integer_zerop (last_conflicts_xz);
yz_p = !integer_zerop (last_conflicts_yz);
xyz_p = !integer_zerop (last_conflicts_xyz);
if (xz_p || yz_p || xyz_p)
{
*overlaps_a = make_tree_vec (2);
TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
*overlaps_b = integer_zero_node;
if (xz_p)
{
tree t0 = chrec_convert (integer_type_node,
TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
tree t1 = chrec_convert (integer_type_node, overlaps_a_xz,
NULL_TREE);
tree t2 = chrec_convert (integer_type_node, *overlaps_b,
NULL_TREE);
tree t3 = chrec_convert (integer_type_node, overlaps_b_xz,
NULL_TREE);
TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
t0, t1);
*overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
*last_conflicts = last_conflicts_xz;
}
if (yz_p)
{
tree t0 = chrec_convert (integer_type_node,
TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
tree t1 = chrec_convert (integer_type_node, overlaps_a_yz, NULL_TREE);
tree t2 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
tree t3 = chrec_convert (integer_type_node, overlaps_b_yz, NULL_TREE);
TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
t0, t1);
*overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
*last_conflicts = last_conflicts_yz;
}
if (xyz_p)
{
tree t0 = chrec_convert (integer_type_node,
TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
tree t1 = chrec_convert (integer_type_node, overlaps_a_xyz,
NULL_TREE);
tree t2 = chrec_convert (integer_type_node,
TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
tree t3 = chrec_convert (integer_type_node, overlaps_a_xyz,
NULL_TREE);
tree t4 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
tree t5 = chrec_convert (integer_type_node, overlaps_b_xyz,
NULL_TREE);
TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
t0, t1);
TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
t2, t3);
*overlaps_b = chrec_fold_plus (integer_type_node, t4, t5);
*last_conflicts = last_conflicts_xyz;
}
}
else
{
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
*last_conflicts = integer_zero_node;
}
}
static void
analyze_subscript_affine_affine (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b,
tree *last_conflicts)
{
unsigned nb_vars_a, nb_vars_b, dim;
int init_a, init_b, gamma, gcd_alpha_beta;
int tau1, tau2;
lambda_matrix A, U, S;
if (eq_evolutions_p (chrec_a, chrec_b))
{
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
*last_conflicts = chrec_dont_know;
return;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_subscript_affine_affine \n");
nb_vars_a = nb_vars_in_chrec (chrec_a);
nb_vars_b = nb_vars_in_chrec (chrec_b);
dim = nb_vars_a + nb_vars_b;
U = lambda_matrix_new (dim, dim);
A = lambda_matrix_new (dim, 1);
S = lambda_matrix_new (dim, 1);
init_a = initialize_matrix_A (A, chrec_a, 0, 1);
init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
gamma = init_b - init_a;
if (gamma == 0)
{
if (nb_vars_a == 1 && nb_vars_b == 1)
{
int step_a, step_b;
int niter, niter_a, niter_b;
tree numiter_a, numiter_b;
numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
goto end_analyze_subs_aa;
}
niter_a = int_cst_value (numiter_a);
niter_b = int_cst_value (numiter_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));
compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
overlaps_a, overlaps_b,
last_conflicts, 1);
}
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);
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);
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: too many variables.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
goto end_analyze_subs_aa;
}
lambda_matrix_right_hermite (A, dim, 1, S, U);
if (S[0][0] < 0)
{
S[0][0] *= -1;
lambda_matrix_row_negate (U, dim, 0);
}
gcd_alpha_beta = S[0][0];
if (gcd_alpha_beta == 0)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
goto end_analyze_subs_aa;
}
if (!int_divides_p (gcd_alpha_beta, gamma))
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
}
else if (nb_vars_a == 1 && nb_vars_b == 1)
{
if (((A[0][0] > 0 && -A[1][0] > 0)
|| (A[0][0] < 0 && -A[1][0] < 0)))
{
int i0, j0, i1, j1;
int x0, y0;
int niter, niter_a, niter_b;
tree numiter_a, numiter_b;
numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
goto end_analyze_subs_aa;
}
niter_a = int_cst_value (numiter_a);
niter_b = int_cst_value (numiter_b);
niter = MIN (niter_a, niter_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 ((i1 == 0 && i0 < 0)
|| (j1 == 0 && j0 < 0))
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
}
else
{
if (i1 > 0)
{
tau1 = CEIL (-i0, i1);
tau2 = FLOOR_DIV (niter - i0, i1);
if (j1 > 0)
{
int last_conflict, min_multiple;
tau1 = MAX (tau1, CEIL (-j0, j1));
tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
x0 = i1 * tau1 + i0;
y0 = j1 * tau1 + j0;
min_multiple = MIN (x0 / i1, y0 / j1);
x0 -= i1 * min_multiple;
y0 -= j1 * min_multiple;
tau1 = (x0 - i0)/i1;
last_conflict = tau2 - tau1;
if (x0 > niter || y0 > niter)
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
}
else
{
*overlaps_a = build_polynomial_chrec
(1,
build_int_cst (NULL_TREE, x0),
build_int_cst (NULL_TREE, i1));
*overlaps_b = build_polynomial_chrec
(1,
build_int_cst (NULL_TREE, y0),
build_int_cst (NULL_TREE, j1));
*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 = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
}
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
}
}
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
}
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
end_analyze_subs_aa:
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (overlaps_a = ");
print_generic_expr (dump_file, *overlaps_a, 0);
fprintf (dump_file, ")\n (overlaps_b = ");
print_generic_expr (dump_file, *overlaps_b, 0);
fprintf (dump_file, ")\n");
fprintf (dump_file, ")\n");
}
}
static bool
can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
{
tree diff, type, left_a, left_b, right_b;
if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
|| chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
return false;
type = chrec_type (*chrec_a);
left_a = CHREC_LEFT (*chrec_a);
left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
diff = chrec_fold_minus (type, left_a, left_b);
if (!evolution_function_is_constant_p (diff))
return false;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
*chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
diff, CHREC_RIGHT (*chrec_a));
right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
*chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
build_int_cst (type, 0),
right_b);
return true;
}
static void
analyze_siv_subscript (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b,
tree *last_conflicts)
{
dependence_stats.num_siv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_siv_subscript \n");
if (evolution_function_is_constant_p (chrec_a)
&& evolution_function_is_affine_p (chrec_b))
analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b, last_conflicts);
else if (evolution_function_is_affine_p (chrec_a)
&& evolution_function_is_constant_p (chrec_b))
analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
overlaps_b, overlaps_a, last_conflicts);
else if (evolution_function_is_affine_p (chrec_a)
&& evolution_function_is_affine_p (chrec_b))
{
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);
if (*overlaps_a == chrec_dont_know
|| *overlaps_b == chrec_dont_know)
dependence_stats.num_siv_unimplemented++;
else if (*overlaps_a == chrec_known
|| *overlaps_b == chrec_known)
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);
*last_conflicts = chrec_dont_know;
if (*overlaps_a == chrec_dont_know
|| *overlaps_b == chrec_dont_know)
dependence_stats.num_siv_unimplemented++;
else if (*overlaps_a == chrec_known
|| *overlaps_b == chrec_known)
dependence_stats.num_siv_independent++;
else
dependence_stats.num_siv_dependent++;
}
else
goto siv_subscript_dontknow;
}
else
{
siv_subscript_dontknow:;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "siv test failed: unimplemented.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
dependence_stats.num_siv_unimplemented++;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static bool
chrec_steps_divide_constant_p (tree chrec,
tree cst,
bool *res)
{
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
{
if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
*res = false;
return true;
}
else
return false;
default:
return true;
}
}
static void
analyze_miv_subscript (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b,
tree *last_conflicts)
{
bool divide_p = true;
tree difference;
dependence_stats.num_miv++;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_miv_subscript \n");
chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
if (eq_evolutions_p (chrec_a, chrec_b))
{
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
*last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
dependence_stats.num_miv_dependent++;
}
else if (evolution_function_is_constant_p (difference)
&& chrec_steps_divide_constant_p (chrec_a, difference, ÷_p)
&& !divide_p)
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
dependence_stats.num_miv_independent++;
}
else if (evolution_function_is_affine_multivariate_p (chrec_a)
&& !chrec_contains_symbols (chrec_a)
&& evolution_function_is_affine_multivariate_p (chrec_b)
&& !chrec_contains_symbols (chrec_b))
{
analyze_subscript_affine_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b, last_conflicts);
if (*overlaps_a == chrec_dont_know
|| *overlaps_b == chrec_dont_know)
dependence_stats.num_miv_unimplemented++;
else if (*overlaps_a == chrec_known
|| *overlaps_b == chrec_known)
dependence_stats.num_miv_independent++;
else
dependence_stats.num_miv_dependent++;
}
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
dependence_stats.num_miv_unimplemented++;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static void
analyze_overlapping_iterations (tree chrec_a,
tree chrec_b,
tree *overlap_iterations_a,
tree *overlap_iterations_b,
tree *last_conflicts)
{
dependence_stats.num_subscript_tests++;
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, 0);
fprintf (dump_file, ")\n (chrec_b = ");
print_generic_expr (dump_file, chrec_b, 0);
fprintf (dump_file, ")\n");
}
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 = chrec_dont_know;
*overlap_iterations_b = chrec_dont_know;
}
else if (eq_evolutions_p (chrec_a, chrec_b)
&& evolution_function_is_affine_multivariate_p (chrec_a))
{
dependence_stats.num_same_subscript_function++;
*overlap_iterations_a = integer_zero_node;
*overlap_iterations_b = integer_zero_node;
*last_conflicts = chrec_dont_know;
}
else if ((chrec_contains_symbols (chrec_a)
|| chrec_contains_symbols (chrec_b))
&& (!evolution_function_is_affine_multivariate_p (chrec_a)
|| !evolution_function_is_affine_multivariate_p (chrec_b)))
{
dependence_stats.num_subscript_undetermined++;
*overlap_iterations_a = chrec_dont_know;
*overlap_iterations_b = chrec_dont_know;
}
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);
else
analyze_miv_subscript (chrec_a, chrec_b,
overlap_iterations_a, overlap_iterations_b,
last_conflicts);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (overlap_iterations_a = ");
print_generic_expr (dump_file, *overlap_iterations_a, 0);
fprintf (dump_file, ")\n (overlap_iterations_b = ");
print_generic_expr (dump_file, *overlap_iterations_b, 0);
fprintf (dump_file, ")\n");
fprintf (dump_file, ")\n");
}
}
static void
save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
{
unsigned i;
lambda_vector v;
for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
return;
VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
}
static void
save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
{
unsigned i;
lambda_vector v;
for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
return;
VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
}
static void
add_outer_distances (struct data_dependence_relation *ddr,
lambda_vector dist_v, int index)
{
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);
}
}
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 (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
tree access_fn_a, access_fn_b;
struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
return false;
}
access_fn_a = DR_ACCESS_FN (ddr_a, i);
access_fn_b = DR_ACCESS_FN (ddr_b, i);
if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
&& TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
{
int dist, index;
int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
DDR_LOOP_NEST (ddr));
int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
DDR_LOOP_NEST (ddr));
index = index_a < index_b ? index_a : index_b;
*index_carry = MIN (index, *index_carry);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
return false;
}
dist = int_cst_value (SUB_DISTANCE (subscript));
if (init_v[index] != 0 && dist_v[index] != dist)
{
finalize_ddr_dependent (ddr, chrec_known);
return false;
}
dist_v[index] = dist;
init_v[index] = 1;
*init_b = true;
}
else
{
non_affine_dependence_relation (ddr);
return false;
}
}
return true;
}
static bool
same_access_functions (struct data_dependence_relation *ddr)
{
unsigned i;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
DR_ACCESS_FN (DDR_B (ddr), i)))
return false;
return true;
}
static void
add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
{
int x_1, x_2;
tree c_1 = CHREC_LEFT (c_2);
tree c_0 = CHREC_LEFT (c_1);
lambda_vector dist_v;
if (TREE_CODE (c_0) != INTEGER_CST)
{
DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
return;
}
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));
dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
save_dist_v (ddr, dist_v);
add_outer_distances (ddr, dist_v, x_1);
}
static void
add_other_self_distances (struct data_dependence_relation *ddr)
{
lambda_vector dist_v;
unsigned i;
int index_carry = DDR_NB_LOOPS (ddr);
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
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;
}
add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
return;
}
index_carry = MIN (index_carry,
index_in_loop_nest (CHREC_VARIABLE (access_fun),
DDR_LOOP_NEST (ddr)));
}
}
dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
add_outer_distances (ddr, dist_v, index_carry);
}
static bool
build_classic_dist_vector (struct data_dependence_relation *ddr)
{
bool init_b = false;
int index_carry = DDR_NB_LOOPS (ddr);
lambda_vector dist_v;
if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
return true;
if (same_access_functions (ddr))
{
dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
save_dist_v (ddr, dist_v);
if (DDR_NB_LOOPS (ddr) > 1)
add_other_self_distances (ddr);
return true;
}
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;
if (init_b)
{
if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
{
lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
compute_subscript_distance (ddr);
build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
save_v, &init_b, &index_carry);
save_dist_v (ddr, save_v);
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));
save_dist_v (ddr, save_v);
if (DDR_NB_LOOPS (ddr) > 1)
{
lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
compute_subscript_distance (ddr);
build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
opposite_v, &init_b, &index_carry);
add_outer_distances (ddr, dist_v, index_carry);
add_outer_distances (ddr, opposite_v, index_carry);
}
}
}
else
{
add_outer_distances (ddr, dist_v,
lambda_vector_first_nz (dist_v,
DDR_NB_LOOPS (ddr), 0));
}
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");
}
return true;
}
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;
}
static void
build_classic_dir_vector (struct data_dependence_relation *ddr)
{
unsigned i, j;
lambda_vector dist_v;
for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
{
lambda_vector dir_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]);
save_dir_v (ddr, dir_v);
}
}
static bool
subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
struct data_reference *dra,
struct data_reference *drb)
{
unsigned int i;
tree last_conflicts;
struct subscript *subscript;
for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
i++)
{
tree overlaps_a, overlaps_b;
analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
DR_ACCESS_FN (drb, i),
&overlaps_a, &overlaps_b,
&last_conflicts);
if (chrec_contains_undetermined (overlaps_a)
|| chrec_contains_undetermined (overlaps_b))
{
finalize_ddr_dependent (ddr, chrec_dont_know);
dependence_stats.num_dependence_undetermined++;
return false;
}
else if (overlaps_a == chrec_known
|| overlaps_b == chrec_known)
{
finalize_ddr_dependent (ddr, chrec_known);
dependence_stats.num_dependence_independent++;
return false;
}
else
{
SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
SUB_LAST_CONFLICT (subscript) = last_conflicts;
}
}
return true;
}
static void
subscript_dependence_tester (struct data_dependence_relation *ddr)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(subscript_dependence_tester \n");
if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
dependence_stats.num_dependence_dependent++;
compute_subscript_distance (ddr);
if (build_classic_dist_vector (ddr))
build_classic_dir_vector (ddr);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static bool
access_functions_are_affine_or_constant_p (struct data_reference *a)
{
unsigned int i;
VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
tree t;
for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
if (!evolution_function_is_constant_p (t)
&& !evolution_function_is_affine_multivariate_p (t))
return false;
return true;
}
static void
compute_affine_dependence (struct data_dependence_relation *ddr)
{
struct data_reference *dra = DDR_A (ddr);
struct data_reference *drb = DDR_B (ddr);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(compute_affine_dependence\n");
fprintf (dump_file, " (stmt_a = \n");
print_generic_expr (dump_file, DR_STMT (dra), 0);
fprintf (dump_file, ")\n (stmt_b = \n");
print_generic_expr (dump_file, DR_STMT (drb), 0);
fprintf (dump_file, ")\n");
}
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
dependence_stats.num_dependence_tests++;
if (access_functions_are_affine_or_constant_p (dra)
&& access_functions_are_affine_or_constant_p (drb))
subscript_dependence_tester (ddr);
else
{
dependence_stats.num_dependence_undetermined++;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Data ref a:\n");
dump_data_reference (dump_file, dra);
fprintf (dump_file, "Data ref b:\n");
dump_data_reference (dump_file, drb);
fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
}
finalize_ddr_dependent (ddr, chrec_dont_know);
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static void
compute_self_dependence (struct data_dependence_relation *ddr)
{
unsigned int i;
struct subscript *subscript;
for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
i++)
{
SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
}
save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
}
static void
compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
VEC (ddr_p, heap) **dependence_relations,
VEC (loop_p, heap) *loop_nest,
bool compute_self_and_rr)
{
struct data_dependence_relation *ddr;
struct data_reference *a, *b;
unsigned int i, j;
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
{
ddr = initialize_data_dependence_relation (a, b, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
compute_affine_dependence (ddr);
}
if (compute_self_and_rr)
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
{
ddr = initialize_data_dependence_relation (a, a, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
compute_self_dependence (ddr);
}
}
tree
find_data_references_in_loop (struct loop *loop,
VEC (data_reference_p, heap) **datarefs)
{
basic_block bb, *bbs;
unsigned int i;
block_stmt_iterator bsi;
struct data_reference *dr;
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
bb = bbs[i];
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if ((TREE_CODE (stmt) == CALL_EXPR
&& !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
|| (TREE_CODE (stmt) == ASM_EXPR
&& ASM_VOLATILE_P (stmt)))
goto insert_dont_know_node;
if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
continue;
switch (TREE_CODE (stmt))
{
case MODIFY_EXPR:
{
bool one_inserted = false;
tree opnd0 = TREE_OPERAND (stmt, 0);
tree opnd1 = TREE_OPERAND (stmt, 1);
if (TREE_CODE (opnd0) == ARRAY_REF
|| TREE_CODE (opnd0) == INDIRECT_REF
|| TREE_CODE (opnd0) == COMPONENT_REF)
{
dr = create_data_ref (opnd0, stmt, false);
if (dr)
{
VEC_safe_push (data_reference_p, heap, *datarefs, dr);
one_inserted = true;
}
}
if (TREE_CODE (opnd1) == ARRAY_REF
|| TREE_CODE (opnd1) == INDIRECT_REF
|| TREE_CODE (opnd1) == COMPONENT_REF)
{
dr = create_data_ref (opnd1, stmt, true);
if (dr)
{
VEC_safe_push (data_reference_p, heap, *datarefs, dr);
one_inserted = true;
}
}
if (!one_inserted)
goto insert_dont_know_node;
break;
}
case CALL_EXPR:
{
tree args;
bool one_inserted = false;
for (args = TREE_OPERAND (stmt, 1); args;
args = TREE_CHAIN (args))
if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
|| TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF
|| TREE_CODE (TREE_VALUE (args)) == COMPONENT_REF)
{
dr = create_data_ref (TREE_VALUE (args), stmt, true);
if (dr)
{
VEC_safe_push (data_reference_p, heap, *datarefs, dr);
one_inserted = true;
}
}
if (!one_inserted)
goto insert_dont_know_node;
break;
}
default:
{
struct data_reference *res;
insert_dont_know_node:;
res = XNEW (struct data_reference);
DR_STMT (res) = NULL_TREE;
DR_REF (res) = NULL_TREE;
DR_BASE_OBJECT (res) = NULL;
DR_TYPE (res) = ARRAY_REF_TYPE;
DR_SET_ACCESS_FNS (res, NULL);
DR_BASE_OBJECT (res) = NULL;
DR_IS_READ (res) = false;
DR_BASE_ADDRESS (res) = NULL_TREE;
DR_OFFSET (res) = NULL_TREE;
DR_INIT (res) = NULL_TREE;
DR_STEP (res) = NULL_TREE;
DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
DR_MEMTAG (res) = NULL_TREE;
DR_PTR_INFO (res) = NULL;
VEC_safe_push (data_reference_p, heap, *datarefs, res);
free (bbs);
return chrec_dont_know;
}
}
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
loop->parallel_p = false;
}
}
free (bbs);
return NULL_TREE;
}
static bool
find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
{
if (loop->next)
return false;
VEC_safe_push (loop_p, heap, *loop_nest, loop);
if (loop->inner)
return find_loop_nest_1 (loop->inner, loop_nest);
return true;
}
static bool
find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
{
VEC_safe_push (loop_p, heap, *loop_nest, loop);
if (loop->inner)
return find_loop_nest_1 (loop->inner, loop_nest);
return true;
}
void
compute_data_dependences_for_loop (struct loop *loop,
bool compute_self_and_read_read_dependences,
VEC (data_reference_p, heap) **datarefs,
VEC (ddr_p, heap) **dependence_relations)
{
struct loop *loop_nest = loop;
VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
memset (&dependence_stats, 0, sizeof (dependence_stats));
if (!loop_nest
|| !find_loop_nest (loop_nest, &vloops)
|| find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
{
struct data_dependence_relation *ddr;
ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
}
else
compute_all_dependences (*datarefs, dependence_relations, vloops,
compute_self_and_read_read_dependences);
if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "Dependence tester statistics:\n");
fprintf (dump_file, "Number of dependence tests: %d\n",
dependence_stats.num_dependence_tests);
fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
dependence_stats.num_dependence_dependent);
fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
dependence_stats.num_dependence_independent);
fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
dependence_stats.num_dependence_undetermined);
fprintf (dump_file, "Number of subscript tests: %d\n",
dependence_stats.num_subscript_tests);
fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
dependence_stats.num_subscript_undetermined);
fprintf (dump_file, "Number of same subscript function: %d\n",
dependence_stats.num_same_subscript_function);
fprintf (dump_file, "Number of ziv tests: %d\n",
dependence_stats.num_ziv);
fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
dependence_stats.num_ziv_dependent);
fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
dependence_stats.num_ziv_independent);
fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
dependence_stats.num_ziv_unimplemented);
fprintf (dump_file, "Number of siv tests: %d\n",
dependence_stats.num_siv);
fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
dependence_stats.num_siv_dependent);
fprintf (dump_file, "Number of siv tests returning independent: %d\n",
dependence_stats.num_siv_independent);
fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
dependence_stats.num_siv_unimplemented);
fprintf (dump_file, "Number of miv tests: %d\n",
dependence_stats.num_miv);
fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
dependence_stats.num_miv_dependent);
fprintf (dump_file, "Number of miv tests returning independent: %d\n",
dependence_stats.num_miv_independent);
fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
dependence_stats.num_miv_unimplemented);
}
}
#if 0
static void
analyze_all_data_dependences (struct loops *loops)
{
unsigned int i;
int nb_data_refs = 10;
VEC (data_reference_p, heap) *datarefs =
VEC_alloc (data_reference_p, heap, nb_data_refs);
VEC (ddr_p, heap) *dependence_relations =
VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
compute_data_dependences_for_loop (loops->parray[0], false,
&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_basename_differ = 0;
unsigned nb_chrec_relations = 0;
struct data_dependence_relation *ddr;
for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
{
if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
nb_top_relations++;
else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
{
struct data_reference *a = DDR_A (ddr);
struct data_reference *b = DDR_B (ddr);
bool differ_p;
if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
&& DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
|| (base_object_differ_p (a, b, &differ_p)
&& differ_p))
nb_basename_differ++;
else
nb_bot_relations++;
}
else
nb_chrec_relations++;
}
gather_stats_on_scev_database ();
}
}
free_dependence_relations (dependence_relations);
free_data_refs (datarefs);
}
#endif
void
free_dependence_relation (struct data_dependence_relation *ddr)
{
if (ddr == NULL)
return;
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
free (ddr);
}
void
free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
{
unsigned int i;
struct data_dependence_relation *ddr;
VEC (loop_p, heap) *loop_nest = NULL;
for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
{
if (ddr == NULL)
continue;
if (loop_nest == NULL)
loop_nest = DDR_LOOP_NEST (ddr);
else
gcc_assert (DDR_LOOP_NEST (ddr) == NULL
|| DDR_LOOP_NEST (ddr) == loop_nest);
free_dependence_relation (ddr);
}
if (loop_nest)
VEC_free (loop_p, heap, loop_nest);
VEC_free (ddr_p, heap, dependence_relations);
}
void
free_data_refs (VEC (data_reference_p, heap) *datarefs)
{
unsigned int i;
struct data_reference *dr;
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
free_data_ref (dr);
VEC_free (data_reference_p, heap, datarefs);
}