#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-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
bool
array_base_name_differ_p (struct data_reference *a,
struct data_reference *b,
bool *differ_p)
{
tree base_a = DR_BASE_NAME (a);
tree base_b = DR_BASE_NAME (b);
tree ta, tb;
if (!base_a || !base_b)
return false;
ta = TREE_TYPE (base_a);
tb = TREE_TYPE (base_b);
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 (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 ((TREE_CODE (base_a) == VAR_DECL
&& (TREE_CODE (base_b) == COMPONENT_REF
&& TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL))
|| (TREE_CODE (base_b) == VAR_DECL
&& (TREE_CODE (base_a) == COMPONENT_REF
&& TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL)))
{
*differ_p = true;
return true;
}
return false;
}
static inline bool
tree_fold_divides_p (tree type,
tree a,
tree b)
{
return integer_zerop
(fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
}
static int
gcd (int a, int b)
{
int x, y, z;
x = abs (a);
y = abs (b);
while (x>0)
{
z = y % x;
y = x;
x = z;
}
return (y);
}
static inline bool
int_divides_p (int a, int b)
{
return ((b % a) == 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: \n stmt: ");
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_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
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;
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));
}
if (DDR_DIST_VECT (ddr))
{
fprintf (outf, " distance_vect: ");
print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
}
if (DDR_DIR_VECT (ddr))
{
fprintf (outf, " direction_vect: ");
print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (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, varray_type ddrs)
{
unsigned int i;
for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
{
struct data_dependence_relation *ddr =
(struct data_dependence_relation *)
VARRAY_GENERIC_PTR (ddrs, i);
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
&& DDR_AFFINE_P (ddr))
{
fprintf (file, "DISTANCE_V (");
print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
fprintf (file, ")\n");
fprintf (file, "DIRECTION_V (");
print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
fprintf (file, ")\n");
}
}
fprintf (file, "\n\n");
}
void
dump_ddrs (FILE *file, varray_type ddrs)
{
unsigned int i;
for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
{
struct data_dependence_relation *ddr =
(struct data_dependence_relation *)
VARRAY_GENERIC_PTR (ddrs, i);
dump_data_dependence_relation (file, ddr);
}
fprintf (file, "\n\n");
}
static void
compute_estimated_nb_iterations (struct loop *loop)
{
tree estimation;
struct nb_iter_bound *bound, *next;
for (bound = loop->bounds; bound; bound = next)
{
next = bound->next;
estimation = bound->bound;
if (TREE_CODE (estimation) != INTEGER_CST)
continue;
if (loop->estimated_nb_iterations)
{
if (tree_int_cst_lt (estimation, loop->estimated_nb_iterations))
loop->estimated_nb_iterations = estimation;
}
else
loop->estimated_nb_iterations = estimation;
}
}
static void
estimate_niter_from_size_of_data (struct loop *loop,
tree opnd0,
tree access_fn,
tree stmt)
{
tree estimation;
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)
{
estimation = fold (build2 (CEIL_DIV_EXPR, integer_type_node,
fold (build2 (MINUS_EXPR, integer_type_node,
data_size, init)), step));
record_estimate (loop, estimation, boolean_true_node, stmt);
}
}
static tree
analyze_array_indexes (struct loop *loop,
varray_type *access_fns,
tree ref, tree stmt)
{
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 (loop->estimated_nb_iterations == NULL_TREE)
estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
VARRAY_PUSH_TREE (*access_fns, access_fn);
if (TREE_CODE (opnd0) == ARRAY_REF)
return analyze_array_indexes (loop, access_fns, opnd0, stmt);
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 = xmalloc (sizeof (struct data_reference));
DR_STMT (res) = stmt;
DR_REF (res) = ref;
DR_TYPE (res) = ARRAY_REF_TYPE;
VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
DR_BASE_NAME (res) = analyze_array_indexes
(loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt);
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,
bool is_read)
{
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 = xmalloc (sizeof (struct data_reference));
DR_STMT (res) = stmt;
DR_REF (res) = ref;
DR_TYPE (res) = 0;
VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
DR_BASE_NAME (res) = base;
VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
DR_IS_READ (res) = is_read;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
return res;
}
static bool
all_chrecs_equal_p (tree chrec)
{
int j;
for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
{
tree chrec_j = TREE_VEC_ELT (chrec, j);
tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
if (!integer_zerop
(chrec_fold_minus
(integer_type_node, chrec_j, chrec_j_1)))
return false;
}
return true;
}
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);
}
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;
}
}
}
struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
struct data_reference *b)
{
struct data_dependence_relation *res;
bool differ_p;
res = xmalloc (sizeof (struct data_dependence_relation));
DDR_A (res) = a;
DDR_B (res) = b;
if (a == NULL || b == NULL
|| DR_BASE_NAME (a) == NULL_TREE
|| DR_BASE_NAME (b) == NULL_TREE)
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
|| (array_base_name_differ_p (a, b, &differ_p) && differ_p))
DDR_ARE_DEPENDENT (res) = chrec_known;
else
{
unsigned int i;
DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
DDR_SIZE_VECT (res) = 0;
DDR_DIST_VECT (res) = NULL;
DDR_DIR_VECT (res) = NULL;
for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
{
struct subscript *subscript;
subscript = xmalloc (sizeof (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;
VARRAY_PUSH_GENERIC_PTR (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;
varray_clear (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;
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;
*last_conflicts = chrec_dont_know;
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
}
break;
default:
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
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,
tree *last_conflicts)
{
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_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))
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
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 = fold
(build (EXACT_DIV_EXPR, integer_type_node,
fold (build1 (ABS_EXPR, integer_type_node, difference)),
CHREC_RIGHT (chrec_b)));
*last_conflicts = integer_one_node;
return;
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
return;
}
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
return;
}
}
}
else
{
if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
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 = fold
(build (EXACT_DIV_EXPR, integer_type_node, difference,
CHREC_RIGHT (chrec_b)));
*last_conflicts = integer_one_node;
return;
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
return;
}
}
else
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
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 = number_of_iterations_in_loop
(current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
numiter_y = number_of_iterations_in_loop
(current_loops->parray[CHREC_VARIABLE (chrec_a)]);
numiter_z = number_of_iterations_in_loop
(current_loops->parray[CHREC_VARIABLE (chrec_b)]);
if (TREE_CODE (numiter_x) != INTEGER_CST)
numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
->estimated_nb_iterations;
if (TREE_CODE (numiter_y) != INTEGER_CST)
numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
->estimated_nb_iterations;
if (TREE_CODE (numiter_z) != INTEGER_CST)
numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
->estimated_nb_iterations;
if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
|| numiter_z == NULL_TREE)
{
*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_VEC_ELT (*overlaps_a, 0) =
chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
overlaps_a_xz);
*overlaps_b =
chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
*last_conflicts = last_conflicts_xz;
}
if (yz_p)
{
TREE_VEC_ELT (*overlaps_a, 1) =
chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
overlaps_a_yz);
*overlaps_b =
chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
*last_conflicts = last_conflicts_yz;
}
if (xyz_p)
{
TREE_VEC_ELT (*overlaps_a, 0) =
chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
overlaps_a_xyz);
TREE_VEC_ELT (*overlaps_a, 1) =
chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
overlaps_a_xyz);
*overlaps_b =
chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
*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 (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 = number_of_iterations_in_loop
(current_loops->parray[CHREC_VARIABLE (chrec_a)]);
numiter_b = number_of_iterations_in_loop
(current_loops->parray[CHREC_VARIABLE (chrec_b)]);
if (TREE_CODE (numiter_a) != INTEGER_CST)
numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
->estimated_nb_iterations;
if (TREE_CODE (numiter_b) != INTEGER_CST)
numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
->estimated_nb_iterations;
if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
return;
}
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
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
return;
}
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 (!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 = number_of_iterations_in_loop
(current_loops->parray[CHREC_VARIABLE (chrec_a)]);
numiter_b = number_of_iterations_in_loop
(current_loops->parray[CHREC_VARIABLE (chrec_b)]);
if (TREE_CODE (numiter_a) != INTEGER_CST)
numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
->estimated_nb_iterations;
if (TREE_CODE (numiter_b) != INTEGER_CST)
numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
->estimated_nb_iterations;
if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
return;
}
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;
*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
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
}
else
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
}
}
else
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
}
else
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
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,
tree *last_conflicts)
{
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))
analyze_subscript_affine_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b, last_conflicts);
else
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
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 *last_conflicts)
{
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;
*last_conflicts = number_of_iterations_in_loop
(current_loops->parray[CHREC_VARIABLE (chrec_a)]);
}
else if (evolution_function_is_constant_p (difference)
&& !chrec_steps_divide_constant_p (chrec_a, difference))
{
*overlaps_a = chrec_known;
*overlaps_b = chrec_known;
*last_conflicts = integer_zero_node;
}
else if (evolution_function_is_affine_multivariate_p (chrec_a)
&& evolution_function_is_affine_multivariate_p (chrec_b))
{
analyze_subscript_affine_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b, last_conflicts);
}
else
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*last_conflicts = chrec_dont_know;
}
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)
{
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))
{
*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");
}
}
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);
tree last_conflicts;
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,
&last_conflicts);
if (chrec_contains_undetermined (overlaps_a)
|| chrec_contains_undetermined (overlaps_b))
{
finalize_ddr_dependent (ddr, chrec_dont_know);
break;
}
else if (overlaps_a == chrec_known
|| overlaps_b == chrec_known)
{
finalize_ddr_dependent (ddr, chrec_known);
break;
}
else
{
SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
SUB_LAST_CONFLICT (subscript) = last_conflicts;
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
bool
build_classic_dist_vector (struct data_dependence_relation *ddr,
int nb_loops, int first_loop_depth)
{
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 (ddr) != NULL_TREE)
return true;
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 true;
}
access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
&& TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
{
int dist, loop_nb, loop_depth;
int loop_nb_a = CHREC_VARIABLE (access_fn_a);
int loop_nb_b = CHREC_VARIABLE (access_fn_b);
struct loop *loop_a = current_loops->parray[loop_nb_a];
struct loop *loop_b = current_loops->parray[loop_nb_b];
if (loop_a->depth < first_loop_depth
|| loop_b->depth < first_loop_depth)
return false;
if (loop_nb_a != loop_nb_b
&& !flow_loop_nested_p (loop_a, loop_b)
&& !flow_loop_nested_p (loop_b, loop_a))
{
non_affine_dependence_relation (ddr);
return true;
}
loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
gcc_assert (loop_depth >= 0);
gcc_assert (loop_depth < nb_loops);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
return true;
}
dist = int_cst_value (SUB_DISTANCE (subscript));
if (init_v[loop_depth] != 0
&& dist_v[loop_depth] != dist)
{
finalize_ddr_dependent (ddr, chrec_known);
return true;
}
dist_v[loop_depth] = dist;
init_v[loop_depth] = 1;
}
}
{
struct loop *lca, *loop_a, *loop_b;
struct data_reference *a = DDR_A (ddr);
struct data_reference *b = DDR_B (ddr);
int lca_depth;
loop_a = loop_containing_stmt (DR_STMT (a));
loop_b = loop_containing_stmt (DR_STMT (b));
lca = find_common_loop (loop_a, loop_b);
lca_depth = lca->depth;
lca_depth -= first_loop_depth;
gcc_assert (lca_depth >= 0);
gcc_assert (lca_depth < nb_loops);
if (lca != loop_a
&& lca != loop_b
&& init_v[lca_depth] == 0)
dist_v[lca_depth] = 1;
lca = lca->outer;
if (lca)
{
lca_depth = lca->depth - first_loop_depth;
while (lca->depth != 0)
{
if (lca_depth < 0)
break;
gcc_assert (lca_depth < nb_loops);
if (init_v[lca_depth] == 0)
dist_v[lca_depth] = 1;
lca = lca->outer;
lca_depth = lca->depth - first_loop_depth;
}
}
}
DDR_DIST_VECT (ddr) = dist_v;
DDR_SIZE_VECT (ddr) = nb_loops;
return true;
}
static bool
build_classic_dir_vector (struct data_dependence_relation *ddr,
int nb_loops, int first_loop_depth)
{
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 (ddr) != NULL_TREE)
return true;
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 true;
}
access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
&& TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
{
int dist, loop_nb, loop_depth;
enum data_dependence_direction dir = dir_star;
int loop_nb_a = CHREC_VARIABLE (access_fn_a);
int loop_nb_b = CHREC_VARIABLE (access_fn_b);
struct loop *loop_a = current_loops->parray[loop_nb_a];
struct loop *loop_b = current_loops->parray[loop_nb_b];
if (loop_a->depth < first_loop_depth
|| loop_b->depth < first_loop_depth)
return false;
if (loop_nb_a != loop_nb_b
&& !flow_loop_nested_p (loop_a, loop_b)
&& !flow_loop_nested_p (loop_b, loop_a))
{
non_affine_dependence_relation (ddr);
return true;
}
loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
gcc_assert (loop_depth >= 0);
gcc_assert (loop_depth < nb_loops);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
return true;
}
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_depth] != 0
&& dir != dir_star
&& (enum data_dependence_direction) dir_v[loop_depth] != dir
&& (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
{
finalize_ddr_dependent (ddr, chrec_known);
return true;
}
dir_v[loop_depth] = dir;
init_v[loop_depth] = 1;
}
}
{
struct loop *lca, *loop_a, *loop_b;
struct data_reference *a = DDR_A (ddr);
struct data_reference *b = DDR_B (ddr);
int lca_depth;
loop_a = loop_containing_stmt (DR_STMT (a));
loop_b = loop_containing_stmt (DR_STMT (b));
lca = find_common_loop (loop_a, loop_b);
lca_depth = lca->depth - first_loop_depth;
gcc_assert (lca_depth >= 0);
gcc_assert (lca_depth < nb_loops);
if (lca != loop_a
&& lca != loop_b
&& init_v[lca_depth] == 0)
dir_v[lca_depth] = dir_positive;
lca = lca->outer;
if (lca)
{
lca_depth = lca->depth - first_loop_depth;
while (lca->depth != 0)
{
if (lca_depth < 0)
break;
gcc_assert (lca_depth < nb_loops);
if (init_v[lca_depth] == 0)
dir_v[lca_depth] = dir_positive;
lca = lca->outer;
lca_depth = lca->depth - first_loop_depth;
}
}
}
DDR_DIR_VECT (ddr) = dir_v;
DDR_SIZE_VECT (ddr) = nb_loops;
return true;
}
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;
}
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)
{
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_dont_know);
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
static void
compute_all_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);
ddr = initialize_data_dependence_relation (a, b);
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
compute_affine_dependence (ddr);
compute_subscript_distance (ddr);
}
}
tree
find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
{
bool dont_know_node_not_inserted = true;
basic_block bb, *bbs;
unsigned int i;
block_stmt_iterator bsi;
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);
stmt_ann_t ann = stmt_ann (stmt);
if (TREE_CODE (stmt) != MODIFY_EXPR)
continue;
if (!VUSE_OPS (ann)
&& !V_MUST_DEF_OPS (ann)
&& !V_MAY_DEF_OPS (ann))
continue;
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
{
if (dont_know_node_not_inserted)
{
struct data_reference *res;
res = xmalloc (sizeof (struct data_reference));
DR_STMT (res) = NULL_TREE;
DR_REF (res) = NULL_TREE;
DR_TYPE (res) = 0;
DR_ACCESS_FNS (res) = NULL;
DR_BASE_NAME (res) = NULL;
DR_IS_READ (res) = false;
VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
dont_know_node_not_inserted = false;
}
}
if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
|| NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
bb->loop_father->parallel_p = false;
}
if (bb->loop_father->estimated_nb_iterations == NULL_TREE)
compute_estimated_nb_iterations (bb->loop_father);
}
free (bbs);
return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
}
void
compute_data_dependences_for_loop (unsigned nb_loops,
struct loop *loop,
varray_type *datarefs,
varray_type *dependence_relations)
{
unsigned int i;
varray_type allrelations;
if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
{
struct data_dependence_relation *ddr;
ddr = initialize_data_dependence_relation (NULL, NULL);
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
build_classic_dist_vector (ddr, nb_loops, loop->depth);
build_classic_dir_vector (ddr, nb_loops, loop->depth);
return;
}
VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations");
compute_all_dependences (*datarefs, &allrelations);
for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++)
{
struct data_dependence_relation *ddr;
ddr = VARRAY_GENERIC_PTR (allrelations, i);
if (build_classic_dist_vector (ddr, nb_loops, loop->depth))
{
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
build_classic_dir_vector (ddr, nb_loops, loop->depth);
}
}
}
void
analyze_all_data_dependences (struct loops *loops)
{
unsigned int i;
varray_type datarefs;
varray_type dependence_relations;
int nb_data_refs = 10;
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, loops->parray[0],
&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;
for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
{
struct data_dependence_relation *ddr;
ddr = VARRAY_GENERIC_PTR (dependence_relations, 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_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
|| (array_base_name_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);
}
void
free_dependence_relation (struct data_dependence_relation *ddr)
{
if (ddr == NULL)
return;
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
varray_clear (DDR_SUBSCRIPTS (ddr));
free (ddr);
}
void
free_dependence_relations (varray_type dependence_relations)
{
unsigned int i;
if (dependence_relations == NULL)
return;
for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
varray_clear (dependence_relations);
}
void
free_data_refs (varray_type datarefs)
{
unsigned int i;
if (datarefs == NULL)
return;
for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
{
struct data_reference *dr = (struct data_reference *)
VARRAY_GENERIC_PTR (datarefs, i);
if (dr)
{
if (DR_ACCESS_FNS (dr))
varray_clear (DR_ACCESS_FNS (dr));
free (dr);
}
}
varray_clear (datarefs);
}