llvm / llvm-archive / 48649d2c83b557841c9e5c978d9ab5af13cb52e5 / . / llvm-gcc-4.0 / gcc / tree-data-ref.c

/* Data references and dependences detectors. | |

Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. | |

Contributed by Sebastian Pop <s.pop@laposte.net> | |

This file is part of GCC. | |

GCC is free software; you can redistribute it and/or modify it under | |

the terms of the GNU General Public License as published by the Free | |

Software Foundation; either version 2, or (at your option) any later | |

version. | |

GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |

WARRANTY; without even the implied warranty of MERCHANTABILITY or | |

FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |

for more details. | |

You should have received a copy of the GNU General Public License | |

along with GCC; see the file COPYING. If not, write to the Free | |

Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |

02111-1307, USA. */ | |

/* This pass walks a given loop structure searching for array | |

references. The information about the array accesses is recorded | |

in DATA_REFERENCE structures. | |

The basic test for determining the dependences is: | |

given two access functions chrec1 and chrec2 to a same array, and | |

x and y two vectors from the iteration domain, the same element of | |

the array is accessed twice at iterations x and y if and only if: | |

| chrec1 (x) == chrec2 (y). | |

The goals of this analysis are: | |

- to determine the independence: the relation between two | |

independent accesses is qualified with the chrec_known (this | |

information allows a loop parallelization), | |

- when two data references access the same data, to qualify the | |

dependence relation with classic dependence representations: | |

- distance vectors | |

- direction vectors | |

- loop carried level dependence | |

- polyhedron dependence | |

or with the chains of recurrences based representation, | |

- to define a knowledge base for storing the data dependence | |

information, | |

- to define an interface to access this data. | |

Definitions: | |

- subscript: given two array accesses a subscript is the tuple | |

composed of the access functions for a given dimension. Example: | |

Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts: | |

(f1, g1), (f2, g2), (f3, g3). | |

- Diophantine equation: an equation whose coefficients and | |

solutions are integer constants, for example the equation | |

| 3*x + 2*y = 1 | |

has an integer solution x = 1 and y = -1. | |

References: | |

- "Advanced Compilation for High Performance Computing" by Randy | |

Allen and Ken Kennedy. | |

http://citeseer.ist.psu.edu/goff91practical.html | |

- "Loop Transformations for Restructuring Compilers - The Foundations" | |

by Utpal Banerjee. | |

*/ | |

#include "config.h" | |

#include "system.h" | |

#include "coretypes.h" | |

#include "tm.h" | |

#include "errors.h" | |

#include "ggc.h" | |

#include "tree.h" | |

/* These RTL headers are needed for basic-block.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" | |

/* This is the simplest data dependence test: determines whether the | |

data references A and B access the same array/region. Returns | |

false when the property is not computable at compile time. | |

Otherwise return true, and DIFFER_P will record the result. This | |

utility will not be necessary when alias_sets_conflict_p will be | |

less conservative. */ | |

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); | |

/* Determine if same base. Example: for the array accesses | |

a[i], b[i] or pointer accesses *a, *b, bases are a, b. */ | |

if (base_a == base_b) | |

{ | |

*differ_p = false; | |

return true; | |

} | |

/* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p) | |

and (*q) */ | |

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; | |

} | |

/* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */ | |

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; | |

} | |

/* Determine if different bases. */ | |

/* At this point we know that base_a != base_b. However, pointer | |

accesses of the form x=(*p) and y=(*q), whose bases are p and q, | |

may still be pointing to the same base. In SSAed GIMPLE p and q will | |

be SSA_NAMES in this case. Therefore, here we check if they are | |

really two different declarations. */ | |

if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL) | |

{ | |

*differ_p = true; | |

return true; | |

} | |

/* Compare two record/union bases s.a and t.b: s != t or (a != b and | |

s and t are not unions). */ | |

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; | |

} | |

/* Compare a record/union access and an array access. */ | |

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; | |

} | |

/* Returns true iff A divides B. */ | |

static inline bool | |

tree_fold_divides_p (tree type, | |

tree a, | |

tree b) | |

{ | |

/* Determines whether (A == gcd (A, B)). */ | |

return integer_zerop | |

(fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b)))); | |

} | |

/* Compute the greatest common denominator of two numbers using | |

Euclid's algorithm. */ | |

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); | |

} | |

/* Returns true iff A divides B. */ | |

static inline bool | |

int_divides_p (int a, int b) | |

{ | |

return ((b % a) == 0); | |

} | |

/* Dump into FILE all the data references from DATAREFS. */ | |

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)); | |

} | |

/* Dump into FILE all the dependence relations from DDR. */ | |

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)); | |

} | |

/* Dump function for a DATA_REFERENCE structure. */ | |

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"); | |

} | |

/* Dump function for a SUBSCRIPT structure. */ | |

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"); | |

} | |

/* Dump function for a DATA_DEPENDENCE_RELATION structure. */ | |

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"); | |

} | |

/* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */ | |

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; | |

} | |

} | |

/* Dumps the distance and direction vectors in FILE. DDRS contains | |

the dependence relations, and VECT_SIZE is the size of the | |

dependence vectors, or in other words the number of loops in the | |

considered nest. */ | |

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"); | |

} | |

/* Dumps the data dependence relations DDRS in FILE. */ | |

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"); | |

} | |

/* Compute the lowest iteration bound for LOOP. It is an | |

INTEGER_CST. */ | |

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) | |

{ | |

/* Update only if estimation is smaller. */ | |

if (tree_int_cst_lt (estimation, loop->estimated_nb_iterations)) | |

loop->estimated_nb_iterations = estimation; | |

} | |

else | |

loop->estimated_nb_iterations = estimation; | |

} | |

} | |

/* Estimate the number of iterations from the size of the data and the | |

access functions. */ | |

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); | |

} | |

} | |

/* Given an ARRAY_REF node REF, records its access functions. | |

Example: given A[i][3], record in ACCESS_FNS the opnd1 function, | |

i.e. the constant "3", then recursively call the function on opnd0, | |

i.e. the ARRAY_REF "A[i]". The function returns the base name: | |

"A". */ | |

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); | |

/* The detection of the evolution function for this data access is | |

postponed until the dependence test. This lazy strategy avoids | |

the computation of access functions that are of no interest for | |

the optimizers. */ | |

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); | |

/* Recursively record other array access functions. */ | |

if (TREE_CODE (opnd0) == ARRAY_REF) | |

return analyze_array_indexes (loop, access_fns, opnd0, stmt); | |

/* Return the base name of the data access. */ | |

else | |

return opnd0; | |

} | |

/* For a data reference REF contained in the statement STMT, initialize | |

a DATA_REFERENCE structure, and return it. IS_READ flag has to be | |

set to true when REF is in the right hand side of an | |

assignment. */ | |

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; | |

/* APPLE LOCAL mainline Radar 4382844 */ | |

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; | |

} | |

/* For a data reference REF contained in the statement STMT, initialize | |

a DATA_REFERENCE structure, and return it. */ | |

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; | |

/* APPLE LOCAL mainline Radar 4382844 */ | |

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; | |

} | |

/* Returns true when all the functions of a tree_vec CHREC are the | |

same. */ | |

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; | |

} | |

/* Determine for each subscript in the data dependence relation DDR | |

the distance. */ | |

/* APPLE LOCAL begin AV data dependence. -dpatel */ | |

/* Patch is waiting FSF review since mid Sep, 2004. | |

Make this function externally visible. */ | |

void | |

/* APPLE LOCAL end AV data dependence. -dpatel */ | |

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; | |

} | |

} | |

} | |

/* Initialize a ddr. */ | |

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; | |

/* When the dimensions of A and B differ, we directly initialize | |

the relation to "there is no dependence": chrec_known. */ | |

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; | |

} | |

/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap | |

description. */ | |

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)); | |

} | |

/* The dependence relation DDR cannot be represented by a distance | |

vector. */ | |

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; | |

} | |

/* This section contains the classic Banerjee tests. */ | |

/* Returns true iff CHREC_A and CHREC_B are not dependent on any index | |

variables, i.e., if the ZIV (Zero Index Variable) test is true. */ | |

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)); | |

} | |

/* Returns true iff CHREC_A and CHREC_B are dependent on an index | |

variable, i.e., if the SIV (Single Index Variable) test is true. */ | |

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; | |

} | |

/* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and | |

*OVERLAPS_B are initialized to the functions that describe the | |

relation between the elements accessed twice by CHREC_A and | |

CHREC_B. For k >= 0, the following property is verified: | |

CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |

static void | |

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)) | |

{ | |

/* The difference is equal to zero: the accessed index | |

overlaps for each iteration in the loop. */ | |

*overlaps_a = integer_zero_node; | |

*overlaps_b = integer_zero_node; | |

*last_conflicts = chrec_dont_know; | |

} | |

else | |

{ | |

/* The accesses do not overlap. */ | |

*overlaps_a = chrec_known; | |

*overlaps_b = chrec_known; | |

*last_conflicts = integer_zero_node; | |

} | |

break; | |

default: | |

/* We're not sure whether the indexes overlap. For the moment, | |

conservatively answer "don't know". */ | |

*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"); | |

} | |

/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a | |

constant, and CHREC_B is an affine function. *OVERLAPS_A and | |

*OVERLAPS_B are initialized to the functions that describe the | |

relation between the elements accessed twice by CHREC_A and | |

CHREC_B. For k >= 0, the following property is verified: | |

CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |

static void | |

analyze_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) | |

{ | |

/* Example: | |

chrec_a = 12 | |

chrec_b = {10, +, 1} | |

*/ | |

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; | |

} | |

/* When the step does not divides the difference, there are | |

no overlaps. */ | |

else | |

{ | |

*overlaps_a = chrec_known; | |

*overlaps_b = chrec_known; | |

*last_conflicts = integer_zero_node; | |

return; | |

} | |

} | |

else | |

{ | |

/* Example: | |

chrec_a = 12 | |

chrec_b = {10, +, -1} | |

In this case, chrec_a will not overlap with chrec_b. */ | |

*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) | |

{ | |

/* Example: | |

chrec_a = 3 | |

chrec_b = {10, +, -1} | |

*/ | |

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; | |

} | |

/* When the step does not divides the difference, there | |

are no overlaps. */ | |

else | |

{ | |

*overlaps_a = chrec_known; | |

*overlaps_b = chrec_known; | |

*last_conflicts = integer_zero_node; | |

return; | |

} | |

} | |

else | |

{ | |

/* Example: | |

chrec_a = 3 | |

chrec_b = {4, +, 1} | |

In this case, chrec_a will not overlap with chrec_b. */ | |

*overlaps_a = chrec_known; | |

*overlaps_b = chrec_known; | |

*last_conflicts = integer_zero_node; | |

return; | |

} | |

} | |

} | |

} | |

} | |

/* Helper recursive function for initializing the matrix A. Returns | |

the initial value of CHREC. */ | |

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)) | |

/* Solves the special case of the Diophantine equation: | |

| {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B) | |

Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the | |

number of iterations that loops X and Y run. The overlaps will be | |

constructed as evolutions in dimension DIM. */ | |

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; | |

} | |

} | |

/* Solves the special case of a Diophantine equation where CHREC_A is | |

an affine bivariate function, and CHREC_B is an affine univariate | |

function. For example, | |

| {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z | |

has the following overlapping functions: | |

| x (t, u, v) = {{0, +, 1336}_t, +, 1}_v | |

| y (t, u, v) = {{0, +, 1336}_u, +, 1}_v | |

| z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v | |

FORNOW: This is a specialized implementation for a case occurring in | |

a common benchmark. Implement the general algorithm. */ | |

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; | |

} | |

} | |

/* Determines the overlapping elements due to accesses CHREC_A and | |

CHREC_B, that are affine functions. This is a part of the | |

subscript analyzer. */ | |

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"); | |

/* For determining the initial intersection, we have to solve a | |

Diophantine equation. This is the most time consuming part. | |

For answering to the question: "Is there a dependence?" we have | |

to prove that there exists a solution to the Diophantine | |

equation, and that the solution is in the iteration domain, | |

i.e. the solution is positive or zero, and that the solution | |

happens before the upper bound loop.nb_iterations. Otherwise | |

there is no dependence. This function outputs a description of | |

the iterations that hold the intersections. */ | |

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; | |

/* Don't do all the hard work of solving the Diophantine equation | |

when we already know the solution: for example, | |

| {3, +, 1}_1 | |

| {3, +, 4}_2 | |

| gamma = 3 - 3 = 0. | |

Then the first overlap occurs during the first iterations: | |

| {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x) | |

*/ | |

if (gamma == 0) | |

{ | |

if (nb_vars_a == 1 && nb_vars_b == 1) | |

{ | |

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; | |

} | |

/* U.A = S */ | |

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]; | |

/* The classic "gcd-test". */ | |

if (!int_divides_p (gcd_alpha_beta, gamma)) | |

{ | |

/* The "gcd-test" has determined that there is no integer | |

solution, i.e. there is no dependence. */ | |

*overlaps_a = chrec_known; | |

*overlaps_b = chrec_known; | |

*last_conflicts = integer_zero_node; | |

} | |

/* Both access functions are univariate. This includes SIV and MIV cases. */ | |

else if (nb_vars_a == 1 && nb_vars_b == 1) | |

{ | |

/* Both functions should have the same evolution sign. */ | |

if (((A[0][0] > 0 && -A[1][0] > 0) | |

|| (A[0][0] < 0 && -A[1][0] < 0))) | |

{ | |

/* The solutions are given by: | |

| | |

| [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0] | |

| [u21 u22] [y0] | |

For a given integer t. Using the following variables, | |

| i0 = u11 * gamma / gcd_alpha_beta | |

| j0 = u12 * gamma / gcd_alpha_beta | |

| i1 = u21 | |

| j1 = u22 | |

the solutions are: | |

| x0 = i0 + i1 * t, | |

| y0 = j0 + j1 * t. */ | |

int i0, j0, i1, j1; | |

/* X0 and Y0 are the first iterations for which there is a | |

dependence. X0, Y0 are two solutions of the Diophantine | |

equation: chrec_a (X0) = chrec_b (Y0). */ | |

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)) | |

{ | |

/* There is no solution. | |

FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" | |

falls in here, but for the moment we don't look at the | |

upper bound of the iteration domain. */ | |

*overlaps_a = 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; | |

/* At this point (x0, y0) is one of the | |

solutions to the Diophantine equation. The | |

next step has to compute the smallest | |

positive solution: the first conflicts. */ | |

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 | |

{ | |

/* FIXME: For the moment, the upper bound of the | |

iteration domain for j is not checked. */ | |

*overlaps_a = chrec_dont_know; | |

*overlaps_b = chrec_dont_know; | |

*last_conflicts = chrec_dont_know; | |

} | |

} | |

else | |

{ | |

/* FIXME: For the moment, the upper bound of the | |

iteration domain for i is not checked. */ | |

*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"); | |

} | |

/* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and | |

*OVERLAPS_B are initialized to the functions that describe the | |

relation between the elements accessed twice by CHREC_A and | |

CHREC_B. For k >= 0, the following property is verified: | |

CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |

static void | |

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"); | |

} | |

/* Return true when the evolution steps of an affine CHREC divide the | |

constant CST. */ | |

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: | |

/* On the initial condition, return true. */ | |

return true; | |

} | |

} | |

/* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and | |

*OVERLAPS_B are initialized to the functions that describe the | |

relation between the elements accessed twice by CHREC_A and | |

CHREC_B. For k >= 0, the following property is verified: | |

CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |

static void | |

analyze_miv_subscript (tree chrec_a, | |

tree chrec_b, | |

tree *overlaps_a, | |

tree *overlaps_b, | |

tree *last_conflicts) | |

{ | |

/* FIXME: This is a MIV subscript, not yet handled. | |

Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from | |

(A[i] vs. A[j]). | |

In the SIV test we had to solve a Diophantine equation with two | |

variables. In the MIV case we have to solve a Diophantine | |

equation with 2*n variables (if the subscript uses n IVs). | |

*/ | |

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)) | |

{ | |

/* Access functions are the same: all the elements are accessed | |

in the same order. */ | |

*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) | |

/* For the moment, the following is verified: | |

evolution_function_is_affine_multivariate_p (chrec_a) */ | |

&& !chrec_steps_divide_constant_p (chrec_a, difference)) | |

{ | |

/* testsuite/.../ssa-chrec-33.c | |

{{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2 | |

The difference is 1, and the evolution steps are equal to 2, | |

consequently there are no overlapping elements. */ | |

*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)) | |

{ | |

/* testsuite/.../ssa-chrec-35.c | |

{0, +, 1}_2 vs. {0, +, 1}_3 | |

the overlapping elements are respectively located at iterations: | |

{0, +, 1}_x and {0, +, 1}_x, | |

in other words, we have the equality: | |

{0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x) | |

Other examples: | |

{{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = | |

{0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y) | |

{{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = | |

{{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) | |

*/ | |

analyze_subscript_affine_affine (chrec_a, chrec_b, | |

overlaps_a, overlaps_b, last_conflicts); | |

} | |

else | |

{ | |

/* When the analysis is too difficult, answer "don't know". */ | |

*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"); | |

} | |

/* Determines the iterations for which CHREC_A is equal to CHREC_B. | |

OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with | |

two functions that describe the iterations that contain conflicting | |

elements. | |

Remark: For an integer k >= 0, the following equality is true: | |

CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)). | |

*/ | |

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"); | |

} | |

} | |

/* This section contains the affine functions dependences detector. */ | |

/* Computes the conflicting iterations, and initialize DDR. */ | |

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"); | |

} | |

/* Compute the classic per loop distance vector. | |

DDR is the data dependence relation to build a vector from. | |

NB_LOOPS is the total number of loops we are considering. | |

FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed | |

loop nest. | |

Return FALSE if the dependence relation is outside of the loop nest | |

starting at FIRST_LOOP_DEPTH. | |

Return TRUE otherwise. */ | |

/* APPLE LOCAL begin AV data dependence. -dpatel */ | |

/* Patch is waiting FSF review since mid Sep, 2004. | |

Make this function externally visible. */ | |

bool | |

/* APPLE LOCAL end AV data dependence. -dpatel */ | |

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 the loop for either variable is at a lower depth than | |

the first_loop's depth, then we can't possibly have a | |

dependency at this level of the loop. */ | |

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)) | |

{ | |

/* Example: when there are two consecutive loops, | |

| loop_1 | |

| A[{0, +, 1}_1] | |

| endloop_1 | |

| loop_2 | |

| A[{0, +, 1}_2] | |

| endloop_2 | |

the dependence relation cannot be captured by the | |

distance abstraction. */ | |

non_affine_dependence_relation (ddr); | |

return true; | |

} | |

/* The dependence is carried by the outermost loop. Example: | |

| loop_1 | |

| A[{4, +, 1}_1] | |

| loop_2 | |

| A[{5, +, 1}_2] | |

| endloop_2 | |

| endloop_1 | |

In this case, the dependence is carried by loop_1. */ | |

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; | |

/* If the loop number is still greater than the number of | |

loops we've been asked to analyze, or negative, | |

something is borked. */ | |

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)); | |

/* This is the subscript coupling test. | |

| loop i = 0, N, 1 | |

| T[i+1][i] = ... | |

| ... = T[i][i] | |

| endloop | |

There is no dependence. */ | |

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; | |

} | |

} | |

/* There is a distance of 1 on all the outer loops: | |

Example: there is a dependence of distance 1 on loop_1 for the array A. | |

| loop_1 | |

| A[5] = ... | |

| endloop | |

*/ | |

{ | |

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)); | |

/* Get the common ancestor loop. */ | |

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); | |

/* For each outer loop where init_v is not set, the accesses are | |

in dependence of distance 1 in the loop. */ | |

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 we're considering just a sub-nest, then don't record | |

any information on the outer loops. */ | |

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; | |

} | |

/* Compute the classic per loop direction vector. | |

DDR is the data dependence relation to build a vector from. | |

NB_LOOPS is the total number of loops we are considering. | |

FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed | |

loop nest. | |

Return FALSE if the dependence relation is outside of the loop nest | |

at FIRST_LOOP_DEPTH. | |

Return TRUE otherwise. */ | |

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 the loop for either variable is at a lower depth than | |

the first_loop's depth, then we can't possibly have a | |

dependency at this level of the loop. */ | |

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)) | |

{ | |

/* Example: when there are two consecutive loops, | |

| loop_1 | |

| A[{0, +, 1}_1] | |

| endloop_1 | |

| loop_2 | |

| A[{0, +, 1}_2] | |

| endloop_2 | |

the dependence relation cannot be captured by the | |

distance abstraction. */ | |

non_affine_dependence_relation (ddr); | |

return true; | |

} | |

/* The dependence is carried by the outermost loop. Example: | |

| loop_1 | |

| A[{4, +, 1}_1] | |

| loop_2 | |

| A[{5, +, 1}_2] | |

| endloop_2 | |

| endloop_1 | |

In this case, the dependence is carried by loop_1. */ | |

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; | |

/* If the loop number is still greater than the number of | |

loops we've been asked to analyze, or negative, | |

something is borked. */ | |

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; | |

/* This is the subscript coupling test. | |

| loop i = 0, N, 1 | |

| T[i+1][i] = ... | |

| ... = T[i][i] | |

| endloop | |

There is no dependence. */ | |

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; | |

} | |

} | |

/* There is a distance of 1 on all the outer loops: | |

Example: there is a dependence of distance 1 on loop_1 for the array A. | |

| loop_1 | |

| A[5] = ... | |

| endloop | |

*/ | |

{ | |

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)); | |

/* Get the common ancestor loop. */ | |

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); | |

/* For each outer loop where init_v is not set, the accesses are | |

in dependence of distance 1 in the loop. */ | |

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 we're considering just a sub-nest, then don't record | |

any information on the outer loops. */ | |

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; | |

} | |

/* Returns true when all the access functions of A are affine or | |

constant. */ | |

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; | |

} | |

/* This computes the affine dependence relation between A and B. | |

CHREC_KNOWN is used for representing the independence between two | |

accesses, while CHREC_DONT_KNOW is used for representing the unknown | |

relation. | |

Note that it is possible to stop the computation of the dependence | |

relation the first time we detect a CHREC_KNOWN element for a given | |

subscript. */ | |

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"); | |

} | |

/* Analyze only when the dependence relation is not yet known. */ | |

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); | |

/* As a last case, if the dependence cannot be determined, or if | |

the dependence is considered too difficult to determine, answer | |

"don't know". */ | |

else | |

finalize_ddr_dependent (ddr, chrec_dont_know); | |

} | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

fprintf (dump_file, ")\n"); | |

} | |

/* Compute a subset of the data dependence relation graph. Don't | |

compute read-read relations, and avoid the computation of the | |

opposite relation, i.e. when AB has been computed, don't compute BA. | |

DATAREFS contains a list of data references, and the result is set | |

in DEPENDENCE_RELATIONS. */ | |

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); | |

} | |

} | |

/* Search the data references in LOOP, and record the information into | |

DATAREFS. Returns chrec_dont_know when failing to analyze a | |

difficult case, returns NULL_TREE otherwise. | |

TODO: This function should be made smarter so that it can handle address | |

arithmetic as if they were array accesses, etc. */ | |

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; | |

/* In the GIMPLE representation, a modify expression | |

contains a single load or store to memory. */ | |

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; | |

/* APPLE LOCAL mainline Radar 4382844 */ | |

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; | |

} | |

} | |

/* When there are no defs in the loop, the loop is parallel. */ | |

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; | |

} | |

/* This section contains all the entry points. */ | |

/* Given a loop nest LOOP, the following vectors are returned: | |

*DATAREFS is initialized to all the array elements contained in this loop, | |

*DEPENDENCE_RELATIONS contains the relations between the data references. */ | |

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 one of the data references is not computable, give up without | |

spending time to compute other dependences. */ | |

if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know) | |

{ | |

struct data_dependence_relation *ddr; | |

/* Insert a single relation into dependence_relations: | |

chrec_dont_know. */ | |

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); | |

} | |

} | |

} | |

/* Entry point (for testing only). Analyze all the data references | |

and the dependence relations. | |

The data references are computed first. | |

A relation on these nodes is represented by a complete graph. Some | |

of the relations could be of no interest, thus the relations can be | |

computed on demand. | |

In the following function we compute all the relations. This is | |

just a first implementation that is here for: | |

- for showing how to ask for the dependence relations, | |

- for the debugging the whole dependence graph, | |

- for the dejagnu testcases and maintenance. | |

It is possible to ask only for a part of the graph, avoiding to | |

compute the whole dependence graph. The computed dependences are | |

stored in a knowledge base (KB) such that later queries don't | |

recompute the same information. The implementation of this KB is | |

transparent to the optimizer, and thus the KB can be changed with a | |

more efficient implementation, or the KB could be disabled. */ | |

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 DDs on the whole function. */ | |

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); | |

} | |

/* Free the memory used by a data dependence relation DDR. */ | |

void | |

free_dependence_relation (struct data_dependence_relation *ddr) | |

{ | |

if (ddr == NULL) | |

return; | |

if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr)) | |

varray_clear (DDR_SUBSCRIPTS (ddr)); | |

free (ddr); | |

} | |

/* Free the memory used by the data dependence relations from | |

DEPENDENCE_RELATIONS. */ | |

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); | |

} | |

/* Free the memory used by the data references from DATAREFS. */ | |

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); | |

} | |