This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Corrections for the data dependence analyzer
- From: "Sebastian Pop" <sebpop at gmail dot com>
- To: gcc-patches at gcc dot gnu dot org, "Dorit Nuzman" <DORIT at il dot ibm dot com>
- Cc: sebastian dot pop at cri dot ensmp dot fr
- Date: Wed, 22 Mar 2006 23:38:41 +0100
- Subject: Corrections for the data dependence analyzer
Hi,
This patch corrects and cleans up the data dependence analyzer based on
the improvements from the autovect branch.
Bootstrapped and tested on amd64-linux. There is a new fail:
FAIL: gcc.dg/vect/vect-104.c scan-tree-dump-times possible dependence
between data-refs 1
that is probably only some noise. I will wait to see how to fix this regression
before committing this patch.
Sebastian
* tree-data-ref.c: Rename DDR_SIZE_VECT to DDR_NB_LOOPS.
(subscript_dependence_tester_1): Declared.
(print_dir_vectors, print_dist_vectors): New.
(debug_data_dependence_relation): New.
(dump_data_dependence_relation): Print more details.
(initialize_data_dependence_relation): Initialize DDR_LOOP_NEST.
(analyze_subscript_affine_affine): Don't ICE when gcd_alpha_beta is 0.
(save_dist_v, save_dir_v, index_in_loop_nest, add_outer_distances,
build_classic_dist_vector_1): New.
(build_classic_dist_vector): Rewrite to work on DDR_LOOP_NEST.
Don't test for lambda_vector_lexico_pos.
(same_access_functions, add_multivariate_self_dist,
add_other_self_distances, dir_from_dist): New.
(build_classic_dir_vector): Replace implementation almost identical to
build_classic_dist_vector with a walk of DDR_DIST_VECTS with a call to
dir_from_dist.
(subscript_dependence_tester_1): New.
(subscript_dependence_tester): Handle the lexicographically negative
distance vectors by recomputing the dependence relation.
(compute_affine_dependence): Remove parameter loop_nest_depth.
(compute_self_dependence): Don't call compute_subscript_distance.
(compute_all_dependences): Remove parameters nb_loops, loop_nest_depth.
Add a parameter for the loop_nest.
(find_loop_nest_1, find_loop_nest): New.
(compute_data_dependences_for_loop): Compute the loop nest, and give
up if the nest is not well formed.
* tree-data-ref.h (loop_p): New.
(struct data_dependence_relation): Replace size_vect field with
loop_nest, a vec of loops. Remove omega_dependence field.
(DDR_SIZE_VECT): Renamed DDR_NB_LOOPS.
(DDR_LOOP_NEST): New.
(DDR_OMEGA): Removed.
Index: ChangeLog
===================================================================
*** ChangeLog (revision 112293)
--- ChangeLog (working copy)
***************
*** 1,3 ****
--- 1,38 ----
+ 2006-03-22 Sebastian Pop <pop@cri.ensmp.fr>
+
+ * tree-data-ref.c: Rename DDR_SIZE_VECT to DDR_NB_LOOPS.
+ (subscript_dependence_tester_1): Declared.
+ (print_dir_vectors, print_dist_vectors): New.
+ (debug_data_dependence_relation): New.
+ (dump_data_dependence_relation): Print more details.
+ (initialize_data_dependence_relation): Initialize DDR_LOOP_NEST.
+ (analyze_subscript_affine_affine): Don't ICE when gcd_alpha_beta is 0.
+ (save_dist_v, save_dir_v, index_in_loop_nest, add_outer_distances,
+ build_classic_dist_vector_1): New.
+ (build_classic_dist_vector): Rewrite to work on DDR_LOOP_NEST.
+ Don't test for lambda_vector_lexico_pos.
+ (same_access_functions, add_multivariate_self_dist,
+ add_other_self_distances, dir_from_dist): New.
+ (build_classic_dir_vector): Replace implementation almost identical to
+ build_classic_dist_vector with a walk of DDR_DIST_VECTS with a call to
+ dir_from_dist.
+ (subscript_dependence_tester_1): New.
+ (subscript_dependence_tester): Handle the lexicographically negative
+ distance vectors by recomputing the dependence relation.
+ (compute_affine_dependence): Remove parameter loop_nest_depth.
+ (compute_self_dependence): Don't call compute_subscript_distance.
+ (compute_all_dependences): Remove parameters nb_loops, loop_nest_depth.
+ Add a parameter for the loop_nest.
+ (find_loop_nest_1, find_loop_nest): New.
+ (compute_data_dependences_for_loop): Compute the loop nest, and give
+ up if the nest is not well formed.
+ * tree-data-ref.h (loop_p): New.
+ (struct data_dependence_relation): Replace size_vect field with
+ loop_nest, a vec of loops. Remove omega_dependence field.
+ (DDR_SIZE_VECT): Renamed DDR_NB_LOOPS.
+ (DDR_LOOP_NEST): New.
+ (DDR_OMEGA): Removed.
+
2006-03-22 Volker Reichelt <reichelt@igpm.rwth-aachen.de>
PR driver/22600
Index: tree-data-ref.c
===================================================================
*** tree-data-ref.c (revision 112293)
--- tree-data-ref.c (working copy)
*************** static struct data_reference * init_data
*** 128,134 ****
tree, tree, tree, tree, tree,
struct ptr_info_def *,
enum data_ref_type);
!
/* Determine if PTR and DECL may alias, the result is put in ALIASED.
Return FALSE if there is no symbol memory tag for PTR. */
--- 128,136 ----
tree, tree, tree, tree, tree,
struct ptr_info_def *,
enum data_ref_type);
! static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
! struct data_reference *,
! struct data_reference *);
/* Determine if PTR and DECL may alias, the result is put in ALIASED.
Return FALSE if there is no symbol memory tag for PTR. */
*************** print_direction_vector (FILE *outf,
*** 653,658 ****
--- 655,694 ----
fprintf (outf, "\n");
}
+ /* Print a vector of direction vectors. */
+
+ void
+ print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
+ int length)
+ {
+ unsigned j;
+ lambda_vector v;
+
+ for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
+ print_direction_vector (outf, v, length);
+ }
+
+ /* Print a vector of distance vectors. */
+
+ void
+ print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
+ int length)
+ {
+ unsigned j;
+ lambda_vector v;
+
+ for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
+ print_lambda_vector (outf, v, length);
+ }
+
+ /* Debug version. */
+
+ void
+ debug_data_dependence_relation (struct data_dependence_relation *ddr)
+ {
+ dump_data_dependence_relation (stderr, ddr);
+ }
+
/* Dump function for a DATA_DEPENDENCE_RELATION structure. */
void
*************** dump_data_dependence_relation (FILE *out
*** 673,678 ****
--- 709,715 ----
else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
unsigned int i;
+ struct loop *loopi;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
*************** dump_data_dependence_relation (FILE *out
*** 683,700 ****
dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
}
for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
{
fprintf (outf, " distance_vector: ");
print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
! DDR_SIZE_VECT (ddr));
}
for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
{
fprintf (outf, " direction_vector: ");
print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
! DDR_SIZE_VECT (ddr));
}
}
--- 720,742 ----
dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
}
+ fprintf (outf, " loop nest: (");
+ for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
+ fprintf (outf, "%d ", loopi->num);
+ fprintf (outf, ")\n");
+
for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
{
fprintf (outf, " distance_vector: ");
print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
! DDR_NB_LOOPS (ddr));
}
for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
{
fprintf (outf, " direction_vector: ");
print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
! DDR_NB_LOOPS (ddr));
}
}
*************** dump_dist_dir_vectors (FILE *file, varra
*** 764,770 ****
{
fprintf (file, "DISTANCE_V (");
print_lambda_vector (file, DDR_DIST_VECT (ddr, j),
! DDR_SIZE_VECT (ddr));
fprintf (file, ")\n");
}
--- 806,812 ----
{
fprintf (file, "DISTANCE_V (");
print_lambda_vector (file, DDR_DIST_VECT (ddr, j),
! DDR_NB_LOOPS (ddr));
fprintf (file, ")\n");
}
*************** dump_dist_dir_vectors (FILE *file, varra
*** 772,778 ****
{
fprintf (file, "DIRECTION_V (");
print_direction_vector (file, DDR_DIR_VECT (ddr, j),
! DDR_SIZE_VECT (ddr));
fprintf (file, ")\n");
}
}
--- 814,820 ----
{
fprintf (file, "DIRECTION_V (");
print_direction_vector (file, DDR_DIR_VECT (ddr, j),
! DDR_NB_LOOPS (ddr));
fprintf (file, ")\n");
}
}
*************** compute_subscript_distance (struct data_
*** 2047,2053 ****
static struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
struct data_reference *b,
! int nb_loops)
{
struct data_dependence_relation *res;
bool differ_p, known_dependence;
--- 2089,2095 ----
static struct data_dependence_relation *
initialize_data_dependence_relation (struct data_reference *a,
struct data_reference *b,
! VEC (loop_p, heap) *loop_nest)
{
struct data_dependence_relation *res;
bool differ_p, known_dependence;
*************** initialize_data_dependence_relation (str
*** 2090,2100 ****
DDR_ARE_DEPENDENT (res) = chrec_known;
return res;
}
!
DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
! DDR_SIZE_VECT (res) = nb_loops;
DDR_DIR_VECTS (res) = NULL;
DDR_DIST_VECTS (res) = NULL;
--- 2132,2142 ----
DDR_ARE_DEPENDENT (res) = chrec_known;
return res;
}
!
DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
! DDR_LOOP_NEST (res) = loop_nest;
DDR_DIR_VECTS (res) = NULL;
DDR_DIST_VECTS (res) = NULL;
*************** analyze_subscript_affine_affine (tree ch
*** 2766,2771 ****
--- 2808,2824 ----
}
gcd_alpha_beta = S[0][0];
+ /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
+ but that is a quite strange case. Instead of ICEing, answer
+ don't know. */
+ if (gcd_alpha_beta == 0)
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ goto end_analyze_subs_aa;
+ }
+
/* The classic "gcd-test". */
if (!int_divides_p (gcd_alpha_beta, gamma))
{
*************** analyze_overlapping_iterations (tree chr
*** 3298,3332 ****
}
}
!
! /* This section contains the affine functions dependences detector. */
! /* 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 when fail to represent the data dependence as a distance
! vector.
! Return TRUE otherwise. */
static bool
! build_classic_dist_vector (struct data_dependence_relation *ddr,
! int first_loop_depth)
{
unsigned i;
! lambda_vector dist_v, init_v;
! int nb_loops = DDR_SIZE_VECT (ddr);
! bool init_b = false;
!
! DDR_SIZE_VECT (ddr) = nb_loops;
! dist_v = lambda_vector_new (nb_loops);
! init_v = lambda_vector_new (nb_loops);
!
! if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
! return true;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
--- 3351,3445 ----
}
}
! /* Helper function for uniquely inserting distance vectors. */
!
! static void
! save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
! {
! unsigned i;
! lambda_vector v;
!
! for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
! if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
! return;
!
! VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
! }
!
! /* Helper function for uniquely inserting direction vectors. */
!
! static void
! save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
! {
! unsigned i;
! lambda_vector v;
!
! for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
! if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
! return;
!
! VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
! }
!
! /* Return the index of the variable VAR in the LOOP_NEST array. */
!
! static int
! index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
! {
! struct loop *loopi;
! int var_index;
! for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
! var_index++)
! if (loopi->num == var)
! break;
! return var_index;
! }
! /* Add a distance of 1 on all the loops outer than INDEX. If we
! haven't yet determined a distance for this outer loop, push a new
! distance vector composed of the previous distance, and a distance
! of 1 for this outer loop. Example:
!
! | loop_1
! | loop_2
! | A[10]
! | endloop_2
! | endloop_1
!
! Saved vectors are of the form (dist_in_1, dist_in_2). First, we
! save (0, 1), then we have to save (1, 0). */
!
! static void
! add_outer_distances (struct data_dependence_relation *ddr,
! lambda_vector dist_v, int index)
! {
! /* For each outer loop where init_v is not set, the accesses are
! in dependence of distance 1 in the loop. */
! while (--index >= 0)
! {
! lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
! save_v[index] = 1;
! save_dist_v (ddr, save_v);
! }
! }
!
! /* Return false when fail to represent the data dependence as a
! distance vector. INIT_B is set to true when a component has been
! added to the distance vector DIST_V. INDEX_CARRY is then set to
! the index in DIST_V that carries the dependence. */
static bool
! build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
! struct data_reference *ddr_a,
! struct data_reference *ddr_b,
! lambda_vector dist_v, bool *init_b,
! int *index_carry)
{
unsigned i;
! lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
*************** build_classic_dist_vector (struct data_d
*** 3336,3382 ****
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
--- 3449,3468 ----
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
! return false;
}
! access_fn_a = DR_ACCESS_FN (ddr_a, i);
! access_fn_b = DR_ACCESS_FN (ddr_b, i);
if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
&& TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
{
! int dist, index;
! int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
! DDR_LOOP_NEST (ddr));
! int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
! DDR_LOOP_NEST (ddr));
/* The dependence is carried by the outermost loop. Example:
| loop_1
*************** build_classic_dist_vector (struct data_d
*** 3386,3734 ****
| 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;
! init_b = true;
}
}
! /* Save the distance vector if we initialized one. */
! if (init_b)
! {
! lambda_vector save_v;
! /* Verify a basic constraint: classic distance vectors should always
! be lexicographically positive. */
! if (!lambda_vector_lexico_pos (dist_v, DDR_SIZE_VECT (ddr)))
! {
! if (DDR_SIZE_VECT (ddr) == 1)
! /* This one is simple to fix, and can be fixed.
! Multidimensional arrays cannot be fixed that simply. */
! lambda_vector_negate (dist_v, dist_v, DDR_SIZE_VECT (ddr));
! else
! /* This is not valid: we need the delta test for properly
! fixing all this. */
! return false;
! }
! save_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
! lambda_vector_copy (dist_v, save_v, DDR_SIZE_VECT (ddr));
! VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), save_v);
! /* There is nothing more to do when there are no outer loops. */
! if (DDR_SIZE_VECT (ddr) == 1)
! goto classic_dist_done;
}
! /* 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. */
! 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 we haven't yet determined a distance for this outer
! loop, push a new distance vector composed of the previous
! distance, and a distance of 1 for this outer loop.
! Example:
!
! | loop_1
! | loop_2
! | A[10]
! | endloop_2
! | endloop_1
!
! Saved vectors are of the form (dist_in_1, dist_in_2).
! First, we save (0, 1), then we have to save (1, 0). */
! if (init_v[lca_depth] == 0)
! {
! lambda_vector save_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
!
! lambda_vector_copy (dist_v, save_v, DDR_SIZE_VECT (ddr));
! save_v[lca_depth] = 1;
! VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), save_v);
! }
! lca = lca->outer;
! lca_depth = lca->depth - first_loop_depth;
! }
! }
! classic_dist_done:;
! if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "(build_classic_dist_vector\n");
! for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
{
! fprintf (dump_file, " dist_vector = (");
! print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
! DDR_SIZE_VECT (ddr));
! fprintf (dump_file, " )\n");
}
- fprintf (dump_file, ")\n");
}
! 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 first_loop_depth)
{
- unsigned i;
- lambda_vector dir_v, init_v;
- int nb_loops = DDR_SIZE_VECT (ddr);
bool init_b = false;
!
! dir_v = lambda_vector_new (nb_loops);
! init_v = lambda_vector_new (nb_loops);
- DDR_SIZE_VECT (ddr) = 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;
- init_b = true;
}
}
! /* Save the direction vector if we initialized one. */
! if (init_b)
{
! lambda_vector save_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
! lambda_vector_copy (dir_v, save_v, DDR_SIZE_VECT (ddr));
! VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), save_v);
}
! /* 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);
! 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)
! {
! lambda_vector save_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
!
! lambda_vector_copy (dir_v, save_v, DDR_SIZE_VECT (ddr));
! save_v[lca_depth] = dir_positive;
! VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), save_v);
! }
! lca = lca->outer;
! lca_depth = lca->depth - first_loop_depth;
! }
! }
! return true;
}
! /* Computes the conflicting iterations, and initialize DDR. */
! static void
! subscript_dependence_tester (struct data_dependence_relation *ddr,
! int loop_nest_depth)
{
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;
--- 3472,3798 ----
| endloop_2
| endloop_1
In this case, the dependence is carried by loop_1. */
! index = index_a < index_b ? index_a : index_b;
! *index_carry = MIN (index, *index_carry);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
! return false;
}
dist = int_cst_value (SUB_DISTANCE (subscript));
! /* This is the subscript coupling test. If we have already
! recorded a distance for this loop (a distance coming from
! another subscript), it should be the same. For example,
! in the following code, there is no dependence:
!
| loop i = 0, N, 1
| T[i+1][i] = ...
| ... = T[i][i]
| endloop
! */
! if (init_v[index] != 0 && dist_v[index] != dist)
{
finalize_ddr_dependent (ddr, chrec_known);
! return false;
}
! dist_v[index] = dist;
! init_v[index] = 1;
! *init_b = true;
! }
! else
! {
! /* This can be for example an affine vs. constant dependence
! (T[i] vs. T[3]) that is not an affine dependence and is
! not representable as a distance vector. */
! non_affine_dependence_relation (ddr);
! return false;
}
}
! return true;
! }
! /* Return true when the DDR contains two data references that have the
! same access functions. */
! static bool
! same_access_functions (struct data_dependence_relation *ddr)
! {
! unsigned i;
! for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
! {
! tree access_fun_a = DR_ACCESS_FN (DDR_A (ddr), i);
! tree access_fun_b = DR_ACCESS_FN (DDR_B (ddr), i);
! tree difference = chrec_fold_minus (integer_type_node, access_fun_a,
! access_fun_b);
! if (TREE_CODE (difference) != INTEGER_CST
! || !integer_zerop (difference))
! return false;
}
! return true;
! }
! /* Helper function for the case where DDR_A and DDR_B are the same
! multivariate access function. */
! static void
! add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
! {
! int x_1, x_2;
! tree c_1 = CHREC_LEFT (c_2);
! tree c_0 = CHREC_LEFT (c_1);
! lambda_vector dist_v;
! /* Polynomials with more than 2 variables are not handled yet. */
! if (TREE_CODE (c_0) != INTEGER_CST)
! {
! DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
! return;
! }
! x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
! x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
! /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
! dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
! dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
! save_dist_v (ddr, dist_v);
! add_outer_distances (ddr, dist_v, x_1);
! }
!
! /* Helper function for the case where DDR_A and DDR_B are the same
! access functions. */
!
! static void
! add_other_self_distances (struct data_dependence_relation *ddr)
! {
! lambda_vector dist_v;
! unsigned i;
! int index_carry = DDR_NB_LOOPS (ddr);
!
! for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
! tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
! if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
{
! if (!evolution_function_is_univariate_p (access_fun))
! {
! if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
! {
! DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
! return;
! }
!
! add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
! return;
! }
!
! index_carry = MIN (index_carry,
! index_in_loop_nest (CHREC_VARIABLE (access_fun),
! DDR_LOOP_NEST (ddr)));
}
}
! dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! add_outer_distances (ddr, dist_v, index_carry);
}
! /* Compute the classic per loop distance vector. DDR is the data
! dependence relation to build a vector from. Return false when fail
! to represent the data dependence as a distance vector. */
static bool
! build_classic_dist_vector (struct data_dependence_relation *ddr)
{
bool init_b = false;
! int index_carry = DDR_NB_LOOPS (ddr);
! lambda_vector dist_v;
if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
return true;
! if (same_access_functions (ddr))
! {
! /* Save the 0 vector. */
! dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! save_dist_v (ddr, dist_v);
! if (DDR_NB_LOOPS (ddr) > 1)
! add_other_self_distances (ddr);
! return true;
! }
! dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
! dist_v, &init_b, &index_carry))
! return false;
! /* Save the distance vector if we initialized one. */
! if (init_b)
! {
! /* Verify a basic constraint: classic distance vectors should
! always be lexicographically positive.
! Data references are collected in the order of execution of
! the program, thus for the following loop
! | for (i = 1; i < 100; i++)
! | for (j = 1; j < 100; j++)
! | {
! | t = T[j+1][i-1]; // A
! | T[j][i] = t + 2; // B
! | }
!
! references are collected following the direction of the wind:
! A then B. The data dependence tests are performed also
! following this order, such that we're looking at the distance
! separating the elements accessed by A from the elements later
! accessed by B. But in this example, the distance returned by
! test_dep (A, B) is lexicographically negative (-1, 1), that
! means that the access A occurs later than B with respect to
! the outer loop, ie. we're actually looking upwind. In this
! case we solve test_dep (B, A) looking downwind to the
! lexicographically positive solution, that returns the
! distance vector (1, -1). */
! if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
! {
! lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
! compute_subscript_distance (ddr);
! build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
! save_v, &init_b, &index_carry);
! save_dist_v (ddr, save_v);
!
! /* In this case there is a dependence forward for all the
! outer loops:
!
! | for (k = 1; k < 100; k++)
! | for (i = 1; i < 100; i++)
! | for (j = 1; j < 100; j++)
! | {
! | t = T[j+1][i-1]; // A
! | T[j][i] = t + 2; // B
! | }
!
! the vectors are:
! (0, 1, -1)
! (1, 1, -1)
! (1, -1, 1)
! */
! if (DDR_NB_LOOPS (ddr) > 1)
{
! add_outer_distances (ddr, save_v, index_carry);
! add_outer_distances (ddr, dist_v, index_carry);
}
+ }
+ else
+ {
+ lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+ lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
+ save_dist_v (ddr, save_v);
! if (DDR_NB_LOOPS (ddr) > 1)
{
! lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
!
! subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
! compute_subscript_distance (ddr);
! build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
! opposite_v, &init_b, &index_carry);
!
! add_outer_distances (ddr, dist_v, index_carry);
! add_outer_distances (ddr, opposite_v, index_carry);
}
}
}
+ else
+ {
+ /* 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
! */
! add_outer_distances (ddr, dist_v,
! lambda_vector_first_nz (dist_v,
! DDR_NB_LOOPS (ddr), 0));
! }
!
! if (dump_file && (dump_flags & TDF_DETAILS))
{
! unsigned i;
! fprintf (dump_file, "(build_classic_dist_vector\n");
! for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
! {
! fprintf (dump_file, " dist_vector = (");
! print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
! DDR_NB_LOOPS (ddr));
! fprintf (dump_file, " )\n");
! }
! fprintf (dump_file, ")\n");
}
! return true;
! }
! /* Return the direction for a given distance.
! FIXME: Computing dir this way is suboptimal, since dir can catch
! cases that dist is unable to represent. */
!
! static inline enum data_dependence_direction
! dir_from_dist (int dist)
! {
! if (dist > 0)
! return dir_positive;
! else if (dist < 0)
! return dir_negative;
! else
! return dir_equal;
! }
! /* Compute the classic per loop direction vector. DDR is the data
! dependence relation to build a vector from. */
! static void
! build_classic_dir_vector (struct data_dependence_relation *ddr)
! {
! unsigned i, j;
! lambda_vector dist_v;
! for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
! {
! lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
! dir_v[j] = dir_from_dist (dist_v[j]);
! save_dir_v (ddr, dir_v);
! }
}
! /* Helper function. Returns true when there is a dependence between
! data references DRA and DRB. */
! static bool
! subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
! struct data_reference *dra,
! struct data_reference *drb)
{
unsigned int i;
tree last_conflicts;
!
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
tree overlaps_a, overlaps_b;
*************** subscript_dependence_tester (struct data
*** 3744,3750 ****
{
finalize_ddr_dependent (ddr, chrec_dont_know);
dependence_stats.num_dependence_undetermined++;
! goto subs_test_end;
}
else if (overlaps_a == chrec_known
--- 3808,3814 ----
{
finalize_ddr_dependent (ddr, chrec_dont_know);
dependence_stats.num_dependence_undetermined++;
! return false;
}
else if (overlaps_a == chrec_known
*************** subscript_dependence_tester (struct data
*** 3752,3758 ****
{
finalize_ddr_dependent (ddr, chrec_known);
dependence_stats.num_dependence_independent++;
! goto subs_test_end;
}
else
--- 3816,3822 ----
{
finalize_ddr_dependent (ddr, chrec_known);
dependence_stats.num_dependence_independent++;
! return false;
}
else
*************** subscript_dependence_tester (struct data
*** 3763,3774 ****
}
}
! dependence_stats.num_dependence_dependent++;
- subs_test_end:;
compute_subscript_distance (ddr);
! if (build_classic_dist_vector (ddr, loop_nest_depth))
! build_classic_dir_vector (ddr, loop_nest_depth);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
--- 3827,3850 ----
}
}
! return true;
! }
!
! /* Computes the conflicting iterations, and initialize DDR. */
!
! static void
! subscript_dependence_tester (struct data_dependence_relation *ddr)
! {
!
! if (dump_file && (dump_flags & TDF_DETAILS))
! fprintf (dump_file, "(subscript_dependence_tester \n");
!
! if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
! dependence_stats.num_dependence_dependent++;
compute_subscript_distance (ddr);
! if (build_classic_dist_vector (ddr))
! build_classic_dir_vector (ddr);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
*************** access_functions_are_affine_or_constant_
*** 3802,3809 ****
subscript. */
static void
! compute_affine_dependence (struct data_dependence_relation *ddr,
! int loop_nest_depth)
{
struct data_reference *dra = DDR_A (ddr);
struct data_reference *drb = DDR_B (ddr);
--- 3878,3884 ----
subscript. */
static void
! compute_affine_dependence (struct data_dependence_relation *ddr)
{
struct data_reference *dra = DDR_A (ddr);
struct data_reference *drb = DDR_B (ddr);
*************** compute_affine_dependence (struct data_d
*** 3825,3839 ****
if (access_functions_are_affine_or_constant_p (dra)
&& access_functions_are_affine_or_constant_p (drb))
! subscript_dependence_tester (ddr, loop_nest_depth);
!
/* 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
{
dependence_stats.num_dependence_undetermined++;
!
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Data ref a:\n");
--- 3900,3914 ----
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
{
dependence_stats.num_dependence_undetermined++;
!
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Data ref a:\n");
*************** static void
*** 3857,3863 ****
compute_self_dependence (struct data_dependence_relation *ddr)
{
unsigned int i;
- lambda_vector dir_v, dist_v;
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
{
--- 3932,3937 ----
*************** compute_self_dependence (struct data_dep
*** 3870,3900 ****
}
/* The distance vector is the zero vector. */
! dist_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
! dir_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
!
! VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
! VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
!
! compute_subscript_distance (ddr);
}
! /* Compute a subset of the data dependence relation graph. Don't
! compute read-read and self relations if
! COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, 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,
VEC(ddr_p,heap) **dependence_relations,
! bool compute_self_and_read_read_dependences,
! unsigned nb_loops, unsigned loop_nest_depth)
{
! unsigned int i, j, N;
!
! N = VARRAY_ACTIVE_SIZE (datarefs);
/* Note that we specifically skip i == j because it's a self dependence, and
use compute_self_dependence below. */
--- 3944,3965 ----
}
/* The distance vector is the zero vector. */
! save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
! save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
}
! /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
! the data references in DATAREFS, in the LOOP_NEST. When
! COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, don't compute
! read-read and self relations. */
static void
compute_all_dependences (varray_type datarefs,
VEC(ddr_p,heap) **dependence_relations,
! VEC (loop_p, heap) *loop_nest,
! bool compute_self_and_read_read_dependences)
{
! unsigned int i, j, N = VARRAY_ACTIVE_SIZE (datarefs);
/* Note that we specifically skip i == j because it's a self dependence, and
use compute_self_dependence below. */
*************** compute_all_dependences (varray_type dat
*** 3912,3920 ****
&& !compute_self_and_read_read_dependences)
continue;
! ddr = initialize_data_dependence_relation (a, b, nb_loops);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
! compute_affine_dependence (ddr, loop_nest_depth);
}
if (!compute_self_and_read_read_dependences)
--- 3977,3985 ----
&& !compute_self_and_read_read_dependences)
continue;
! ddr = initialize_data_dependence_relation (a, b, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
! compute_affine_dependence (ddr);
}
if (!compute_self_and_read_read_dependences)
*************** compute_all_dependences (varray_type dat
*** 3928,3934 ****
a = VARRAY_GENERIC_PTR (datarefs, i);
b = VARRAY_GENERIC_PTR (datarefs, i);
! ddr = initialize_data_dependence_relation (a, b, nb_loops);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
compute_self_dependence (ddr);
}
--- 3993,3999 ----
a = VARRAY_GENERIC_PTR (datarefs, i);
b = VARRAY_GENERIC_PTR (datarefs, i);
! ddr = initialize_data_dependence_relation (a, b, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
compute_self_dependence (ddr);
}
*************** find_data_references_in_loop (struct loo
*** 4072,4080 ****
return NULL_TREE;
}
!
! /* 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,
--- 4137,4183 ----
return NULL_TREE;
}
! /* Recursive helper function. */
! static bool
! find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) *loop_nest)
! {
! /* Inner loops of the nest should not contain siblings. Example:
! when there are two consecutive loops,
!
! | loop_0
! | loop_1
! | A[{0, +, 1}_1]
! | endloop_1
! | loop_2
! | A[{0, +, 1}_2]
! | endloop_2
! | endloop_0
!
! the dependence relation cannot be captured by the distance
! abstraction. */
! if (loop->next)
! return false;
!
! VEC_safe_push (loop_p, heap, loop_nest, loop);
! if (loop->inner)
! return find_loop_nest_1 (loop->inner, loop_nest);
! return true;
! }
!
! /* Return false when the LOOP is not well nested. Otherwise return
! true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
! contain the loops from the outermost to the innermost, as they will
! appear in the classic distance vector. */
!
! static bool
! find_loop_nest (struct loop *loop, VEC (loop_p, heap) *loop_nest)
! {
! VEC_safe_push (loop_p, heap, loop_nest, loop);
! if (loop->inner)
! return find_loop_nest_1 (loop->inner, loop_nest);
! return true;
! }
/* Given a loop nest LOOP, the following vectors are returned:
*DATAREFS is initialized to all the array elements contained in this loop,
*************** compute_data_dependences_for_loop (struc
*** 4088,4126 ****
varray_type *datarefs,
varray_type *dependence_relations)
{
! unsigned int i, nb_loops;
VEC(ddr_p,heap) *allrelations;
struct data_dependence_relation *ddr;
struct loop *loop_nest = loop;
- while (loop_nest && loop_nest->outer && loop_nest->outer->outer)
- loop_nest = loop_nest->outer;
-
- nb_loops = loop_nest->level;
memset (&dependence_stats, 0, sizeof (dependence_stats));
! /* 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, nb_loops);
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- return;
}
!
! allrelations = NULL;
! compute_all_dependences (*datarefs, &allrelations,
! compute_self_and_read_read_dependences,
! nb_loops, loop_nest->depth);
!
! /* FIXME: We copy the contents of allrelations back to a VARRAY
! because the vectorizer has not yet been converted to use VECs. */
! for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
! VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
if (dump_file && (dump_flags & TDF_STATS))
{
--- 4191,4230 ----
varray_type *datarefs,
varray_type *dependence_relations)
{
! unsigned int i;
VEC(ddr_p,heap) *allrelations;
struct data_dependence_relation *ddr;
struct loop *loop_nest = loop;
+ VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
memset (&dependence_stats, 0, sizeof (dependence_stats));
! /* If the loop nest is not well formed, or one of the data references
! is not computable, give up without spending time to compute other
! dependences. */
! if (!loop_nest
! || !find_loop_nest (loop_nest, vloops)
! || 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, vloops);
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
}
! else
! {
! allrelations = NULL;
! compute_all_dependences (*datarefs, &allrelations, vloops,
! compute_self_and_read_read_dependences);
!
!
! /* FIXME: We copy the contents of allrelations back to a VARRAY
! because the vectorizer has not yet been converted to use VECs. */
! for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
! VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
! }
if (dump_file && (dump_flags & TDF_STATS))
{
Index: tree-data-ref.h
===================================================================
*** tree-data-ref.h (revision 112293)
--- tree-data-ref.h (working copy)
*************** struct subscript
*** 186,191 ****
--- 186,195 ----
#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
#define SUB_DISTANCE(SUB) SUB->distance
+ typedef struct loop *loop_p;
+ DEF_VEC_P(loop_p);
+ DEF_VEC_ALLOC_P (loop_p, heap);
+
/* A data_dependence_relation represents a relation between two
data_references A and B. */
*************** struct data_dependence_relation
*** 217,225 ****
the data_dependence_relation. */
varray_type subscripts;
! /* The size of the direction/distance vectors: the depth of the
! analyzed loop nest. */
! int size_vect;
/* The classic direction vector. */
VEC(lambda_vector,heap) *dir_vects;
--- 221,228 ----
the data_dependence_relation. */
varray_type subscripts;
! /* The analyzed loop nest. */
! VEC (loop_p, heap) *loop_nest;
/* The classic direction vector. */
VEC(lambda_vector,heap) *dir_vects;
*************** DEF_VEC_ALLOC_P(ddr_p,heap);
*** 241,247 ****
VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
#define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
#define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
! #define DDR_SIZE_VECT(DDR) DDR->size_vect
#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
--- 244,265 ----
VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
#define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
#define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
!
! #define DDR_LOOP_NEST(DDR) DDR->loop_nest
! /* The size of the direction/distance vectors: the number of loops in
! the loop nest. */
! #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
!
! #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
! #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
! #define DDR_NUM_DIST_VECTS(DDR) \
! (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
! #define DDR_NUM_DIR_VECTS(DDR) \
! (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
! #define DDR_DIR_VECT(DDR, I) \
! VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
! #define DDR_DIST_VECT(DDR, I) \
! VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
*************** extern tree find_data_references_in_loop
*** 260,270 ****
--- 278,291 ----
extern void compute_data_dependences_for_loop (struct loop *, bool,
varray_type *, varray_type *);
extern void print_direction_vector (FILE *, lambda_vector, int);
+ extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
+ extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
extern void dump_subscript (FILE *, struct subscript *);
extern void dump_ddrs (FILE *, varray_type);
extern void dump_dist_dir_vectors (FILE *, varray_type);
extern void dump_data_reference (FILE *, struct data_reference *);
extern void dump_data_references (FILE *, varray_type);
+ extern void debug_data_dependence_relation (struct data_dependence_relation *);
extern void dump_data_dependence_relation (FILE *,
struct data_dependence_relation *);
extern void dump_data_dependence_relations (FILE *, varray_type);