#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.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-fold-const.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "lambda.h"
static void subscript_dependence_tester (struct data_dependence_relation *);
static unsigned int data_ref_id = 0;
void
dump_data_references (FILE *file,
varray_type datarefs)
{
unsigned int i;
for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
}
void
dump_data_dependence_relations (FILE *file,
varray_type ddr)
{
unsigned int i;
for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
}
void
dump_data_reference (FILE *outf,
struct data_reference *dr)
{
unsigned int i;
fprintf (outf, "(Data Ref %d: \n stmt: ", DR_ID (dr));
print_generic_stmt (outf, DR_STMT (dr), 0);
fprintf (outf, " ref: ");
print_generic_stmt (outf, DR_REF (dr), 0);
fprintf (outf, " base_name: ");
print_generic_stmt (outf, DR_BASE_NAME (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_data_dependence_relation (FILE *outf,
struct data_dependence_relation *ddr)
{
unsigned int i;
struct data_reference *dra, *drb;
dra = DDR_A (ddr);
drb = DDR_B (ddr);
fprintf (outf, "(Data Dep (A = %d, B = %d):", DR_ID (dra), DR_ID (drb));
if (DDR_ARE_DEPENDENT (ddr) == chrec_top)
fprintf (outf, " (don't know)\n");
else if (DDR_ARE_DEPENDENT (ddr) == chrec_bot)
fprintf (outf, " (no dependence)\n");
else
{
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
tree chrec;
struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
fprintf (outf, "\n (subscript %d:\n", 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);
chrec = SUB_CONFLICTS_IN_A (subscript);
fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
print_generic_stmt (outf, chrec, 0);
if (chrec == chrec_bot)
fprintf (outf, " (no dependence)\n");
else if (chrec == chrec_top)
fprintf (outf, " (don't know)\n");
else
{
tree last_iteration = SUB_LAST_CONFLICT_IN_A (subscript);
fprintf (outf, " last_iteration_that_access_an_element_twice_in_A: ");
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_bot)
fprintf (outf, " (no dependence)\n");
else if (chrec == chrec_top)
fprintf (outf, " (don't know)\n");
else
{
tree last_iteration = SUB_LAST_CONFLICT_IN_B (subscript);
fprintf (outf, " last_iteration_that_access_an_element_twice_in_B: ");
print_generic_stmt (outf, last_iteration, 0);
}
fprintf (outf, " )\n");
}
fprintf (outf, " (Distance Vector: \n");
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
fprintf (outf, "(");
print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
fprintf (outf, ")\n");
}
fprintf (outf, " )\n");
}
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;
}
}
static tree
analyze_array_indexes (struct loop *loop,
varray_type access_fns,
tree ref)
{
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));
VARRAY_PUSH_TREE (access_fns, access_fn);
if (TREE_CODE (opnd0) == ARRAY_REF)
return analyze_array_indexes (loop, access_fns, opnd0);
else
return opnd0;
}
struct data_reference *
analyze_array (tree stmt, tree ref, bool is_read)
{
struct data_reference *res;
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 = ggc_alloc (sizeof (struct data_reference));
DR_ID (res) = data_ref_id++;
DR_STMT (res) = stmt;
DR_REF (res) = ref;
VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
DR_BASE_NAME (res) = analyze_array_indexes
(loop_of_stmt (stmt), DR_ACCESS_FNS (res), ref);
DR_IS_READ (res) = is_read;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
return res;
}
struct data_reference *
init_data_ref (tree stmt,
tree ref,
tree base,
tree access_fn)
{
struct data_reference *res;
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 = ggc_alloc (sizeof (struct data_reference));
DR_ID (res) = data_ref_id++;
DR_STMT (res) = stmt;
DR_REF (res) = ref;
VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
DR_BASE_NAME (res) = base;
VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
return res;
}
static struct data_reference *
analyze_array_top (tree stmt)
{
struct data_reference *res;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_array_top \n");
res = ggc_alloc (sizeof (struct data_reference));
DR_ID (res) = data_ref_id++;
DR_STMT (res) = stmt;
DR_REF (res) = NULL_TREE;
DR_BASE_NAME (res) = NULL_TREE;
VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 1, "access_fns");
VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), chrec_top);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
return res;
}
static void
compute_distance_vector (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);
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_top;
}
}
}
static struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
struct data_reference *b)
{
struct data_dependence_relation *res;
res = ggc_alloc (sizeof (struct data_dependence_relation));
DDR_A (res) = a;
DDR_B (res) = b;
if (DR_BASE_NAME (a) == NULL_TREE
|| DR_BASE_NAME (b) == NULL_TREE)
DDR_ARE_DEPENDENT (res) = chrec_top;
else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
|| array_base_name_differ_p (a, b))
DDR_ARE_DEPENDENT (res) = chrec_bot;
else
{
unsigned int i;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
{
struct subscript *subscript;
subscript = ggc_alloc (sizeof (struct subscript));
SUB_CONFLICTS_IN_A (subscript) = chrec_top;
SUB_CONFLICTS_IN_B (subscript) = chrec_top;
SUB_LAST_CONFLICT_IN_A (subscript) = chrec_top;
SUB_LAST_CONFLICT_IN_B (subscript) = chrec_top;
SUB_DISTANCE (subscript) = chrec_top;
SUB_DIRECTION (subscript) = dir_star;
VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
}
}
return res;
}
static inline void
finalize_ddr_dependent (struct data_dependence_relation *ddr,
tree chrec)
{
DDR_ARE_DEPENDENT (ddr) = chrec;
varray_clear (DDR_SUBSCRIPTS (ddr));
}
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:
case EXPONENTIAL_CHREC:
switch (TREE_CODE (chrec_b))
{
case POLYNOMIAL_CHREC:
case EXPONENTIAL_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 difference;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_ziv_subscript \n");
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;
}
else
{
*overlaps_a = chrec_bot;
*overlaps_b = chrec_bot;
}
break;
case INTERVAL_CHREC:
if (integer_zerop (CHREC_LOW (difference))
&& integer_zerop (CHREC_UP (difference)))
{
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
}
else
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
}
break;
default:
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
break;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static void
analyze_siv_subscript_cst_affine (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b)
{
bool value0, value1, value2;
tree difference = chrec_fold_minus
(integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
if (!chrec_is_positive (initial_condition (difference), &value0))
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
return;
}
else
{
if (value0 == false)
{
if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
return;
}
else
{
if (value1 == true)
{
if (tree_fold_divides_p
(integer_type_node, CHREC_RIGHT (chrec_b), difference))
{
*overlaps_a = integer_zero_node;
*overlaps_b = tree_fold_exact_div
(integer_type_node,
tree_fold_abs (integer_type_node, difference),
CHREC_RIGHT (chrec_b));
return;
}
else
{
*overlaps_a = chrec_bot;
*overlaps_b = chrec_bot;
return;
}
}
else
{
*overlaps_a = chrec_bot;
*overlaps_b = chrec_bot;
return;
}
}
}
else
{
if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
return;
}
else
{
if (value2 == false)
{
if (tree_fold_divides_p
(integer_type_node, CHREC_RIGHT (chrec_b), difference))
{
*overlaps_a = integer_zero_node;
*overlaps_b = tree_fold_exact_div
(integer_type_node, difference, CHREC_RIGHT (chrec_b));
return;
}
else
{
*overlaps_a = chrec_bot;
*overlaps_b = chrec_bot;
return;
}
}
else
{
*overlaps_a = chrec_bot;
*overlaps_b = chrec_bot;
return;
}
}
}
}
}
static void
analyze_siv_subscript_affine_cst (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b)
{
analyze_siv_subscript_cst_affine (chrec_b, chrec_a, overlaps_b, overlaps_a);
}
static void
analyze_subscript_affine_affine (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b)
{
tree left_a, left_b, right_a, right_b;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_subscript_affine_affine \n");
left_a = CHREC_LEFT (chrec_a);
left_b = CHREC_LEFT (chrec_b);
right_a = CHREC_RIGHT (chrec_a);
right_b = CHREC_RIGHT (chrec_b);
if (chrec_zerop (chrec_fold_minus (integer_type_node, left_a, left_b)))
{
*overlaps_a = build_polynomial_chrec
(CHREC_VARIABLE (chrec_b), integer_zero_node, integer_one_node);
*overlaps_b = build_polynomial_chrec
(CHREC_VARIABLE (chrec_a), integer_zero_node, integer_one_node);
}
else if (TREE_CODE (left_a) == INTEGER_CST
&& TREE_CODE (left_b) == INTEGER_CST
&& TREE_CODE (right_a) == INTEGER_CST
&& TREE_CODE (right_b) == INTEGER_CST
&& ((tree_int_cst_sgn (right_a) > 0
&& tree_int_cst_sgn (right_b) > 0)
|| (tree_int_cst_sgn (right_a) < 0
&& tree_int_cst_sgn (right_b) < 0)))
{
tree alpha, beta, gamma;
tree la, lb;
tree gcd_alpha_beta;
tree u11, u12, u21, u22;
alpha = copy_node (right_a);
beta = copy_node (right_b);
la = copy_node (left_a);
lb = copy_node (left_b);
TREE_TYPE (alpha) = integer_type_node;
TREE_TYPE (beta) = integer_type_node;
TREE_TYPE (la) = integer_type_node;
TREE_TYPE (lb) = integer_type_node;
gamma = tree_fold_minus (integer_type_node, lb, la);
gcd_alpha_beta = tree_fold_bezout
(alpha,
tree_fold_multiply (integer_type_node, beta, integer_minus_one_node),
&u11, &u12,
&u21, &u22);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (alpha = ");
print_generic_expr (dump_file, alpha, 0);
fprintf (dump_file, ")\n (beta = ");
print_generic_expr (dump_file, beta, 0);
fprintf (dump_file, ")\n (gamma = ");
print_generic_expr (dump_file, gamma, 0);
fprintf (dump_file, ")\n (gcd_alpha_beta = ");
print_generic_expr (dump_file, gcd_alpha_beta, 0);
fprintf (dump_file, ")\n");
}
if (!tree_fold_divides_p (integer_type_node, gcd_alpha_beta, gamma))
{
*overlaps_a = chrec_bot;
*overlaps_b = chrec_bot;
}
else
{
tree i0, j0, i1, j1, t;
tree gamma_gcd;
tree x0, y0;
gamma_gcd = tree_fold_exact_div
(integer_type_node, gamma, gcd_alpha_beta);
i0 = tree_fold_multiply (integer_type_node, u11, gamma_gcd);
j0 = tree_fold_multiply (integer_type_node, u12, gamma_gcd);
i1 = u21;
j1 = u22;
if ((tree_int_cst_sgn (i1) == 0
&& tree_int_cst_sgn (i0) < 0)
|| (tree_int_cst_sgn (j1) == 0
&& tree_int_cst_sgn (j0) < 0))
{
*overlaps_a = chrec_bot;
*overlaps_b = chrec_bot;
}
else
{
if (tree_int_cst_sgn (i1) > 0)
{
t = tree_fold_ceil_div
(integer_type_node,
tree_fold_multiply (integer_type_node, i0,
integer_minus_one_node),
i1);
if (tree_int_cst_sgn (j1) > 0)
{
t = tree_fold_max
(integer_type_node, t,
tree_fold_ceil_div (integer_type_node,
tree_fold_multiply
(integer_type_node, j0,
integer_minus_one_node),
j1));
x0 = tree_fold_plus
(integer_type_node, i0,
tree_fold_multiply (integer_type_node, i1, t));
y0 = tree_fold_plus
(integer_type_node, j0,
tree_fold_multiply (integer_type_node, j1, t));
*overlaps_a = build_polynomial_chrec
(CHREC_VARIABLE (chrec_b), x0, u21);
*overlaps_b = build_polynomial_chrec
(CHREC_VARIABLE (chrec_a), y0, u22);
}
else
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
}
}
else
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
}
}
}
}
else
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
}
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");
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static void
analyze_siv_subscript (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b)
{
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);
else if (evolution_function_is_affine_p (chrec_a)
&& evolution_function_is_constant_p (chrec_b))
analyze_siv_subscript_affine_cst (chrec_a, chrec_b,
overlaps_a, overlaps_b);
else if (evolution_function_is_affine_p (chrec_a)
&& evolution_function_is_affine_p (chrec_b)
&& (CHREC_VARIABLE (chrec_a) == CHREC_VARIABLE (chrec_b)))
analyze_subscript_affine_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b);
else
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static bool
chrec_steps_divide_constant_p (tree chrec,
tree cst)
{
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
&& chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
default:
return true;
}
}
static void
analyze_miv_subscript (tree chrec_a,
tree chrec_b,
tree *overlaps_a,
tree *overlaps_b)
{
tree difference;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_miv_subscript \n");
difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
if (chrec_zerop (difference))
{
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
}
else if (evolution_function_is_constant_p (difference)
&& !chrec_steps_divide_constant_p (chrec_a, difference))
{
*overlaps_a = chrec_bot;
*overlaps_b = chrec_bot;
}
else if (evolution_function_is_univariate_p (chrec_a)
&& evolution_function_is_univariate_p (chrec_b))
{
if (evolution_function_is_affine_p (chrec_a)
&& evolution_function_is_affine_p (chrec_b))
analyze_subscript_affine_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b);
else
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
}
}
else
{
*overlaps_a = chrec_top;
*overlaps_b = chrec_top;
}
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)
{
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)
|| chrec_contains_symbols (chrec_a)
|| chrec_contains_symbols (chrec_b)
|| chrec_contains_intervals (chrec_a)
|| chrec_contains_intervals (chrec_b))
{
*overlap_iterations_a = chrec_top;
*overlap_iterations_b = chrec_top;
}
else if (ziv_subscript_p (chrec_a, chrec_b))
analyze_ziv_subscript (chrec_a, chrec_b,
overlap_iterations_a, overlap_iterations_b);
else if (siv_subscript_p (chrec_a, chrec_b))
analyze_siv_subscript (chrec_a, chrec_b,
overlap_iterations_a, overlap_iterations_b);
else
analyze_miv_subscript (chrec_a, chrec_b,
overlap_iterations_a, overlap_iterations_b);
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");
}
}
static void
subscript_dependence_tester (struct data_dependence_relation *ddr)
{
unsigned int i;
struct data_reference *dra = DDR_A (ddr);
struct data_reference *drb = DDR_B (ddr);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(subscript_dependence_tester \n");
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
tree overlaps_a, overlaps_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);
if (overlaps_a == chrec_top
|| overlaps_b == chrec_top)
{
finalize_ddr_dependent (ddr, chrec_top);
break;
}
else if (overlaps_a == chrec_bot
|| overlaps_b == chrec_bot)
{
finalize_ddr_dependent (ddr, chrec_bot);
break;
}
else
{
SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static void
build_classic_dist_vector (struct data_dependence_relation *res,
varray_type *classic_dist,
unsigned nb_loops)
{
unsigned i;
lambda_vector dist_v, init_v;
dist_v = lambda_vector_new (nb_loops);
init_v = lambda_vector_new (nb_loops);
lambda_vector_clear (dist_v, nb_loops);
lambda_vector_clear (init_v, nb_loops);
if (DDR_ARE_DEPENDENT (res) != NULL_TREE)
return;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++)
{
struct subscript *subscript = DDR_SUBSCRIPT (res, i);
if (SUB_DISTANCE (subscript) == chrec_top)
return;
if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC)
{
int dist;
unsigned loop_nb;
loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
dist = int_cst_value (SUB_DISTANCE (subscript));
if (init_v[loop_nb] != 0
&& dist_v[loop_nb] != dist)
{
finalize_ddr_dependent (res, chrec_bot);
return;
}
dist_v[loop_nb] = dist;
init_v[loop_nb] = 1;
}
}
{
struct loop *lca, *loop_a, *loop_b;
struct data_reference *a = DDR_A (res);
struct data_reference *b = DDR_B (res);
loop_a = loop_of_stmt (DR_STMT (a));
loop_b = loop_of_stmt (DR_STMT (b));
lca = find_common_loop (loop_a, loop_b);
if (lca != loop_a
&& lca != loop_b
&& init_v[loop_num (lca)] == 0)
dist_v[loop_num (lca)] = 1;
lca = outer_loop (lca);
if (lca)
while (loop_depth (lca) != 0)
{
if (init_v[loop_num (lca)] == 0)
dist_v[loop_num (lca)] = 1;
lca = outer_loop (lca);
}
}
VARRAY_PUSH_GENERIC_PTR (*classic_dist, dist_v);
}
static void
build_classic_dir_vector (struct data_dependence_relation *res,
varray_type *classic_dir,
unsigned nb_loops)
{
unsigned i;
lambda_vector dir_v, init_v;
dir_v = lambda_vector_new (nb_loops);
init_v = lambda_vector_new (nb_loops);
lambda_vector_clear (dir_v, nb_loops);
lambda_vector_clear (init_v, nb_loops);
if (DDR_ARE_DEPENDENT (res) != NULL_TREE)
return;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++)
{
struct subscript *subscript = DDR_SUBSCRIPT (res, i);
if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC
&& TREE_CODE (SUB_CONFLICTS_IN_B (subscript)) == POLYNOMIAL_CHREC)
{
unsigned loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
enum data_dependence_direction dir = dir_star;
if (SUB_DISTANCE (subscript) == chrec_top)
{
}
else
{
int dist = int_cst_value (SUB_DISTANCE (subscript));
if (dist == 0)
dir = dir_equal;
else if (dist > 0)
dir = dir_positive;
else if (dist < 0)
dir = dir_negative;
}
if (init_v[loop_nb] != 0
&& dir != dir_star
&& (enum data_dependence_direction) dir_v[loop_nb] != dir
&& (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
{
finalize_ddr_dependent (res, chrec_bot);
return;
}
dir_v[loop_nb] = dir;
init_v[loop_nb] = 1;
}
}
{
struct loop *lca, *loop_a, *loop_b;
struct data_reference *a = DDR_A (res);
struct data_reference *b = DDR_B (res);
loop_a = loop_of_stmt (DR_STMT (a));
loop_b = loop_of_stmt (DR_STMT (b));
lca = find_common_loop (loop_a, loop_b);
if (lca != loop_a
&& lca != loop_b
&& init_v[loop_num (lca)] == 0)
dir_v[loop_num (lca)] = dir_positive;
lca = outer_loop (lca);
if (lca)
while (loop_depth (lca) != 0)
{
if (init_v[loop_num (lca)] == 0)
dir_v[loop_num (lca)] = dir_positive;
lca = outer_loop (lca);
}
}
VARRAY_PUSH_GENERIC_PTR (*classic_dir, dir_v);
}
static bool
access_functions_are_affine_or_constant_p (struct data_reference *a)
{
unsigned int i;
varray_type fns = DR_ACCESS_FNS (a);
for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
&& !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
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 (%d, %d)\n",
DR_ID (dra), DR_ID (drb));
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)
{
if (access_functions_are_affine_or_constant_p (dra)
&& access_functions_are_affine_or_constant_p (drb))
subscript_dependence_tester (ddr);
else
finalize_ddr_dependent (ddr, chrec_top);
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static void
compute_rw_wr_ww_dependences (varray_type datarefs,
varray_type *dependence_relations)
{
unsigned int i, j, N;
N = VARRAY_ACTIVE_SIZE (datarefs);
for (i = 0; i < N; i++)
for (j = i; j < N; j++)
{
struct data_reference *a, *b;
struct data_dependence_relation *ddr;
a = VARRAY_GENERIC_PTR (datarefs, i);
b = VARRAY_GENERIC_PTR (datarefs, j);
if (DR_IS_READ (a) && DR_IS_READ (b))
continue;
ddr = initialize_data_dependence_relation (a, b);
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
compute_affine_dependence (ddr);
compute_distance_vector (ddr);
}
}
static void
find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
{
basic_block bb;
block_stmt_iterator bsi;
FOR_EACH_BB (bb)
{
if (!flow_bb_inside_loop_p (loop, bb))
continue;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
vdef_optype vdefs = VDEF_OPS (stmt_ann (stmt));
vuse_optype vuses = VUSE_OPS (stmt_ann (stmt));
if (vuses || vdefs)
switch (TREE_CODE (stmt))
{
case MODIFY_EXPR:
if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
VARRAY_PUSH_GENERIC_PTR
(*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
false));
else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
VARRAY_PUSH_GENERIC_PTR
(*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
true));
else
VARRAY_PUSH_GENERIC_PTR (*datarefs,
analyze_array_top (stmt));
break;
case COND_EXPR:
case CALL_EXPR:
case VA_ARG_EXPR:
case ASM_EXPR:
case RETURN_EXPR:
break;
default:
break;
}
}
}
}
void
compute_data_dependences_for_loop (unsigned nb_loops,
struct loop *loop,
varray_type *datarefs,
varray_type *dependence_relations,
varray_type *classic_dist,
varray_type *classic_dir)
{
unsigned int i;
find_data_references_in_loop (loop, datarefs);
compute_rw_wr_ww_dependences (*datarefs, dependence_relations);
for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
{
struct data_dependence_relation *ddr;
ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
build_classic_dist_vector (ddr, classic_dist, nb_loops);
build_classic_dir_vector (ddr, classic_dir, nb_loops);
}
}
void
analyze_all_data_dependences (struct loops *loops)
{
unsigned int i;
varray_type datarefs;
varray_type dependence_relations;
varray_type classic_dist, classic_dir;
int nb_data_refs = 10;
#if 0
dump_file = stderr;
dump_flags = 31;
#endif
VARRAY_GENERIC_PTR_INIT (classic_dist, 10, "classic_dist");
VARRAY_GENERIC_PTR_INIT (classic_dir, 10, "classic_dir");
VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
VARRAY_GENERIC_PTR_INIT (dependence_relations,
nb_data_refs * nb_data_refs,
"dependence_relations");
compute_data_dependences_for_loop (loops->num, loop_from_num (loops, 0),
&datarefs, &dependence_relations,
&classic_dist, &classic_dir);
if (dump_file)
{
dump_data_dependence_relations (dump_file, dependence_relations);
fprintf (dump_file, "\n\n");
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dist); i++)
{
fprintf (dump_file, "DISTANCE_V (");
print_lambda_vector (dump_file,
VARRAY_GENERIC_PTR (classic_dist, i),
loops->num);
fprintf (dump_file, ")\n");
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dir); i++)
{
fprintf (dump_file, "DIRECTION_V (");
print_lambda_vector (dump_file,
VARRAY_GENERIC_PTR (classic_dir, i),
loops->num);
fprintf (dump_file, ")\n");
}
fprintf (dump_file, "\n\n");
}
if (dump_file && (dump_flags & TDF_STATS))
{
unsigned nb_top_relations = 0;
unsigned nb_bot_relations = 0;
unsigned nb_basename_differ = 0;
unsigned nb_chrec_relations = 0;
for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
{
struct data_dependence_relation *ddr;
ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
if (DDR_ARE_DEPENDENT (ddr) == chrec_top)
nb_top_relations++;
else if (DDR_ARE_DEPENDENT (ddr) == chrec_bot)
{
struct data_reference *a = DDR_A (ddr);
struct data_reference *b = DDR_B (ddr);
if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
|| array_base_name_differ_p (a, b))
nb_basename_differ++;
else
nb_bot_relations++;
}
else
nb_chrec_relations++;
}
fprintf (dump_file, "\n(\n");
fprintf (dump_file, "%d\tnb_top_relations\n", nb_top_relations);
fprintf (dump_file, "%d\tnb_bot_relations\n", nb_bot_relations);
fprintf (dump_file, "%d\tnb_basename_differ\n", nb_basename_differ);
fprintf (dump_file, "%d\tnb_distance_relations\n", (int) VARRAY_ACTIVE_SIZE (classic_dist));
fprintf (dump_file, "%d\tnb_chrec_relations\n", nb_chrec_relations);
fprintf (dump_file, "\n)\n");
gather_stats_on_scev_database ();
}
varray_clear (dependence_relations);
varray_clear (datarefs);
varray_clear (classic_dist);
varray_clear (classic_dir);
}