This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[autovect] Make omega agree with existing dependence tester
- 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 22:16:02 +0100
- Subject: [autovect] Make omega agree with existing dependence tester
Hi,
I had some problems to access my email at cri.ensmp.fr for some time now,
and I won't get at it probably till the end of this month when returning back
in France, so please reply to this address instead.
This patch makes the omega dependence tester agree with the previous
analyzer while bootstrapping with BOOT_CFLAGS="-O2 -fcheck-data-deps".
I have modified both analyzers, and I will commit the changes to the existing
dependence analyzer also to trunk before proposing the omega test to review
for the trunk.
The patch bootstraps on amd64-linux and produces 2 fails that I think are not
important because I verified that the distance vectors are correct, and the
corresponding cases are vectorized, but it is safer to ask Dorit to
look at these:
FAIL: gcc.dg/vect/vect-104.c scan-tree-dump-times possible dependence
between data-refs 1
FAIL: gcc.dg/vect/vect-99.c scan-tree-dump-times dependence distance
modulo vf == 0 1
I will commit these changes to autovect-branch.
Sebastian
* omega.c: Add a link to David Wonnacott's thesis.
(debug_omega_problem): New.
(eliminateRedundantConstraints): Rename ELIMINATE_REDUNDANT_CONSTRAINTS.
* omega.h (debug_omega_problem): Declared.
* tree-ssa-loop.c (pass_check_data_deps): Renamed ckdd.
* 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.
Remove initialization of DDR_OMEGA and DDR_SIZE_VECT.
(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, lexico_pos_distv_p): New.
(subscript_dependence_tester): Handle the lexicographically negative
distance vectors by recomputing the dependence relation.
(loop_p): Moved...
(init_omega_eq_with_af): Pass a pointer to the DDR, not to the loop
nest. Call index_in_loop_nest.
(omega_extract_distance_vectors, omega_setup_subscript,
init_omega_for_ddr_1): New.
(init_omega_for_ddr): Add more documentation, use helper functions.
(omega_compute_classic_representations): Removed.
(omega_dependence_tester): Removed.
(check_ddr): Modify printing.
(compute_affine_dependence): Remove parameter loop_nest_depth.
Don't call omega_dependence_tester.
(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.
(free_dependence_relation): Remove DDR_OMEGA.
* tree-data-ref.h (loop_p): ...here.
(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, DDR_INNER_LOOP): New.
(DDR_OMEGA): Removed.
Index: omega.c
===================================================================
*** omega.c (revision 112238)
--- omega.c (working copy)
*************** along with GCC; see the file COPYING. I
*** 24,29 ****
--- 24,35 ----
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
+ /* For a detailed description, see "Constraint-Based Array Dependence
+ Analysis" William Pugh, David Wonnacott, TOPLAS'98 and David
+ Wonnacott's thesis:
+ ftp://ftp.cs.umd.edu/pub/omega/davewThesis/davewThesis.ps.gz
+ */
+
/* Options:
ELIMINATE_REDUNDANT_CONSTRAINTS
*************** omega_print_eqn (FILE *file, omega_pb pb
*** 286,292 ****
if (e->touched)
fprintf (file, "!");
! else if (!e->touched && e->key != 0)
fprintf (file, "%d: ", e->key);
}
--- 292,298 ----
if (e->touched)
fprintf (file, "!");
! else if (e->key != 0)
fprintf (file, "%d: ", e->key);
}
*************** omega_print_vars (FILE *file, omega_pb p
*** 366,372 ****
fprintf (file, "variables = ");
if (pb->safe_vars > 0)
! fprintf (file, "(");
for (i = 1; i <= pb->num_vars; i++)
{
--- 372,378 ----
fprintf (file, "variables = ");
if (pb->safe_vars > 0)
! fprintf (file, "protected (");
for (i = 1; i <= pb->num_vars; i++)
{
*************** omega_print_vars (FILE *file, omega_pb p
*** 382,387 ****
--- 388,401 ----
fprintf (file, "\n");
}
+ /* Debug problem PB. */
+
+ void
+ debug_omega_problem (omega_pb pb)
+ {
+ omega_print_problem (stderr, pb);
+ }
+
/* Print to FILE problem PB. */
void
*************** omega_problem_reduced (omega_pb pb)
*** 2751,2757 ****
}
/*
! #ifdef eliminateRedundantConstraints
if (!omega_eliminate_redundant (pb, 1))
return;
#endif
--- 2765,2771 ----
}
/*
! #ifdef ELIMINATE_REDUNDANT_CONSTRAINTS
if (!omega_eliminate_redundant (pb, 1))
return;
#endif
Index: omega.h
===================================================================
*** omega.h (revision 112238)
--- omega.h (working copy)
*************** typedef struct omega_pb
*** 102,108 ****
bool variables_freed;
/* Index or name of variables. Negative integers are reserved for
! wildcard variables. */
int *var;
/* */
--- 102,111 ----
bool variables_freed;
/* Index or name of variables. Negative integers are reserved for
! wildcard variables. Maps the index of variables in the original
! problem to the new index of the variable. The index for a
! variable in the coef array of an equation can change as some
! variables are eliminated. */
int *var;
/* */
*************** extern enum omega_result omega_simplify_
*** 129,134 ****
--- 132,138 ----
extern enum omega_result omega_constrain_variable_sign (omega_pb,
enum omega_eqn_color,
int, int);
+ extern void debug_omega_problem (omega_pb);
extern void omega_print_problem (FILE *, omega_pb);
extern void omega_print_red_equations (FILE *, omega_pb);
extern int omega_count_red_equations (omega_pb);
Index: tree-ssa-loop.c
===================================================================
*** tree-ssa-loop.c (revision 112238)
--- tree-ssa-loop.c (working copy)
*************** gate_check_data_deps (void)
*** 270,276 ****
struct tree_opt_pass pass_check_data_deps =
{
! "checkdd", /* name */
gate_check_data_deps, /* gate */
check_data_deps, /* execute */
NULL, /* sub */
--- 270,276 ----
struct tree_opt_pass pass_check_data_deps =
{
! "ckdd", /* name */
gate_check_data_deps, /* gate */
check_data_deps, /* execute */
NULL, /* sub */
Index: ChangeLog.autovect
===================================================================
*** ChangeLog.autovect (revision 112238)
--- ChangeLog.autovect (working copy)
***************
*** 1,3 ****
--- 1,55 ----
+ 2006-03-22 Sebastian Pop <pop@cri.ensmp.fr>
+
+ * omega.c: Add a link to David Wonnacott's thesis.
+ (debug_omega_problem): New.
+ (eliminateRedundantConstraints): Rename ELIMINATE_REDUNDANT_CONSTRAINTS.
+ * omega.h (debug_omega_problem): Declared.
+ * tree-ssa-loop.c (pass_check_data_deps): Renamed ckdd.
+ * 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.
+ Remove initialization of DDR_OMEGA and DDR_SIZE_VECT.
+ (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, lexico_pos_distv_p): New.
+ (subscript_dependence_tester): Handle the lexicographically negative
+ distance vectors by recomputing the dependence relation.
+ (loop_p): Moved...
+ (init_omega_eq_with_af): Pass a pointer to the DDR, not to the loop
+ nest. Call index_in_loop_nest.
+ (omega_extract_distance_vectors, omega_setup_subscript,
+ init_omega_for_ddr_1): New.
+ (init_omega_for_ddr): Add more documentation, use helper functions.
+ (omega_compute_classic_representations): Removed.
+ (omega_dependence_tester): Removed.
+ (check_ddr): Modify printing.
+ (compute_affine_dependence): Remove parameter loop_nest_depth.
+ Don't call omega_dependence_tester.
+ (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.
+ (free_dependence_relation): Remove DDR_OMEGA.
+ * tree-data-ref.h (loop_p): ...here.
+ (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, DDR_INNER_LOOP): New.
+ (DDR_OMEGA): Removed.
+
2006-02-20 Sebastian Pop <pop@cri.ensmp.fr>
* tree-data-ref.c: (base_addr_differ_p): Fix formatting.
Index: tree-data-ref.c
===================================================================
*** tree-data-ref.c (revision 112238)
--- tree-data-ref.c (working copy)
*************** static struct data_reference * init_data
*** 128,133 ****
--- 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 type memory tag for PTR.
*************** print_direction_vector (FILE *outf,
*** 652,657 ****
--- 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
*** 672,677 ****
--- 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
*** 682,699 ****
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,743 ----
dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
}
+ fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
+ 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
*** 763,769 ****
{
fprintf (file, "DISTANCE_V (");
print_lambda_vector (file, DDR_DIST_VECT (ddr, j),
! DDR_SIZE_VECT (ddr));
fprintf (file, ")\n");
}
--- 807,813 ----
{
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
*** 771,777 ****
{
fprintf (file, "DIRECTION_V (");
print_direction_vector (file, DDR_DIR_VECT (ddr, j),
! DDR_SIZE_VECT (ddr));
fprintf (file, ")\n");
}
}
--- 815,821 ----
{
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;
--- 2091,2097 ----
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
*** 2058,2064 ****
DDR_B (res) = b;
DDR_CSYS (res) = NULL;
DDR_POLYHEDRON (res) = NULL;
- DDR_OMEGA (res) = NULL;
if (a == NULL || b == NULL)
{
--- 2102,2107 ----
*************** initialize_data_dependence_relation (str
*** 2097,2103 ****
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;
--- 2140,2147 ----
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_INNER_LOOP (res) = 0;
DDR_DIR_VECTS (res) = NULL;
DDR_DIST_VECTS (res) = NULL;
*************** analyze_ziv_subscript (tree chrec_a,
*** 2231,2237 ****
*overlaps_b = integer_zero_node;
*last_conflicts = chrec_dont_know;
dependence_stats.num_ziv_dependent++;
-
}
else
{
--- 2275,2280 ----
*************** analyze_subscript_affine_affine (tree ch
*** 2770,2775 ****
--- 2813,2829 ----
}
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
*** 3302,3336 ****
}
}
!
! /* 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++)
{
--- 3356,3450 ----
}
}
! /* 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
*** 3340,3386 ****
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
--- 3454,3473 ----
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
*** 3390,3738 ****
| 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;
--- 3477,3803 ----
| 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
*** 3748,3754 ****
{
finalize_ddr_dependent (ddr, chrec_dont_know);
dependence_stats.num_dependence_undetermined++;
! goto subs_test_end;
}
else if (overlaps_a == chrec_known
--- 3813,3819 ----
{
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
*** 3756,3762 ****
{
finalize_ddr_dependent (ddr, chrec_known);
dependence_stats.num_dependence_independent++;
! goto subs_test_end;
}
else
--- 3821,3827 ----
{
finalize_ddr_dependent (ddr, chrec_known);
dependence_stats.num_dependence_independent++;
! return false;
}
else
*************** subscript_dependence_tester (struct data
*** 3767,3778 ****
}
}
! 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");
--- 3832,3855 ----
}
}
! 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_
*** 3796,3805 ****
return true;
}
- typedef struct loop *loop_p;
- DEF_VEC_P(loop_p);
- DEF_VEC_ALLOC_P (loop_p, heap);
-
/* Initializes an equation using the information contained in the ACCESS_FUN.
Returns true when the operation succeeded.
--- 3873,3878 ----
*************** init_csys_eq_with_af (csys cy, unsigned
*** 3869,3881 ****
EQ is the number of the equation to be initialized.
OFFSET is used for shifting the variables names in the constraints:
a constrain is composed of 2 * the number of variables surrounding
! dependence accesses (ie. VLOOPS). OFFSET is set either to 0 for
! the first n variables, then it is set to n.
ACCESS_FUN is expected to be an affine chrec. */
static bool
init_omega_eq_with_af (omega_pb pb, unsigned eq,
unsigned int offset, tree access_fun,
! VEC (loop_p, heap) *vloops)
{
switch (TREE_CODE (access_fun))
{
--- 3942,3955 ----
EQ is the number of the equation to be initialized.
OFFSET is used for shifting the variables names in the constraints:
a constrain is composed of 2 * the number of variables surrounding
! dependence accesses. OFFSET is set either to 0 for the first n variables,
! then it is set to n.
ACCESS_FUN is expected to be an affine chrec. */
+
static bool
init_omega_eq_with_af (omega_pb pb, unsigned eq,
unsigned int offset, tree access_fun,
! struct data_dependence_relation *ddr)
{
switch (TREE_CODE (access_fun))
{
*************** init_omega_eq_with_af (omega_pb pb, unsi
*** 3885,3911 ****
tree right = CHREC_RIGHT (access_fun);
int var = CHREC_VARIABLE (access_fun);
unsigned var_idx;
- struct loop *loopi;
if (TREE_CODE (right) != INTEGER_CST)
return false;
! /* Find the index of the current variable VAR_IDX in the
! VLOOPS array. */
! for (var_idx = 0; VEC_iterate (loop_p, vloops, var_idx, loopi);
! var_idx++)
! if (loopi->num == var)
! break;
!
pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
if (offset == 0)
! pb->eqs[eq].coef[var_idx + VEC_length (loop_p, vloops) + 1]
+= int_cst_value (right);
switch (TREE_CODE (left))
{
case POLYNOMIAL_CHREC:
! return init_omega_eq_with_af (pb, eq, offset, left, vloops);
case INTEGER_CST:
pb->eqs[eq].coef[0] += int_cst_value (left);
--- 3959,3982 ----
tree right = CHREC_RIGHT (access_fun);
int var = CHREC_VARIABLE (access_fun);
unsigned var_idx;
if (TREE_CODE (right) != INTEGER_CST)
return false;
! var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
+
+ /* Compute the innermost loop index. */
+ DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
+
if (offset == 0)
! pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
+= int_cst_value (right);
switch (TREE_CODE (left))
{
case POLYNOMIAL_CHREC:
! return init_omega_eq_with_af (pb, eq, offset, left, ddr);
case INTEGER_CST:
pb->eqs[eq].coef[0] += int_cst_value (left);
*************** init_csys_for_ddr (struct data_dependenc
*** 4114,4277 ****
return true;
}
! /* Sets up the Omega dependence problem for the data dependence
! relation DDR. Returns false when the constraint system cannot be
! built, ie. when the test answers "don't know". Returns true
! otherwise, and when independence has been proved (using one of the
! trivial dependence test), set MAYBE_DEPENDENT to false and the
! DDR_CSYS is not initialized, otherwise set MAYBE_DEPENDENT to true.
! Example: for setting up the dependence system corresponding to the
! conflicting accesses
! loop_x
! A[i] = ...
! ... A[i+M]
! endloop_x
!
! the following constraints come from the iteration domain:
! 0 <= i <= N
! 0 <= i + di <= N
! where di is the distance variable. The conflicting elements
! constraint inserted in the constraint system is:
! i = i + di + M
! that gets simplified into
!
! di + M = 0
! Finally the constraint system initialized by the following function
! looks like:
! di + M = 0
! 0 <= i <= N
! 0 <= i + di <= N
! The Omega solver expects the distance variables ("di" in the
! previous example) to come first in the constraint system (as
! variables to be protected, or "safe" variables), the constraint
! system is built using the following layout:
! "cst | distance vars | index vars".
! */
! static bool
! init_omega_for_ddr (struct data_dependence_relation *ddr, bool *maybe_dependent)
! {
! unsigned i;
! struct data_reference *dra = DDR_A (ddr);
! struct data_reference *drb = DDR_B (ddr);
! struct loop *loop_a, *loop_b, *common_loop;
! VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
! unsigned nb_eqs, nb_loops, dimension;
! unsigned eq, ineq;
! omega_pb pb;
! struct loop *loopi;
! *maybe_dependent = true;
! /* Compute the size of the constraint system.
! nb_loops = number of loops surrounding both references
! dimension = 2 * nb_loops
! nb_eqs = nb_subscripts
! nb_ineqs = nb_loops * 4
! */
! loop_a = bb_for_stmt (DR_STMT (dra))->loop_father;
! loop_b = bb_for_stmt (DR_STMT (dra))->loop_father;
! common_loop = find_common_loop (loop_a, loop_b);
! if (common_loop != loop_a || common_loop != loop_b)
{
! find_loops_surrounding (loop_a, common_loop, vloops);
! find_loops_surrounding (loop_b, common_loop, vloops);
}
- find_loops_surrounding (common_loop, NULL, vloops);
! nb_eqs = DDR_NUM_SUBSCRIPTS (ddr);
! nb_loops = VEC_length (loop_p, vloops);
! DDR_SIZE_VECT (ddr) = nb_loops;
! dimension = 2 * nb_loops;
!
! if (nb_loops == 0)
return false;
! /* Omega expects the protected variables (those that have to be kept
! after elimination) to appear first in the constraint system.
! These variables are the distance variables. In the following
! initialization we declare NB_LOOPS safe variables, and the total
! number of variables for the constraint system is DIMENSION. */
! pb = omega_alloc_problem (dimension, nb_loops);
! /* For each subscript, insert an equality for representing the
! conflicts. */
! for (eq = 0; eq < DDR_NUM_SUBSCRIPTS (ddr); eq++)
{
! tree access_fun_a = DR_ACCESS_FN (dra, eq);
! tree access_fun_b = DR_ACCESS_FN (drb, eq);
! /* ZIV test. */
! if (ziv_subscript_p (access_fun_a, access_fun_b))
! {
! tree difference = chrec_fold_minus (integer_type_node, access_fun_a,
! access_fun_b);
! if (TREE_CODE (difference) == INTEGER_CST
! && !integer_zerop (difference))
! {
! /* There is no dependence. */
! DDR_ARE_DEPENDENT (ddr) = chrec_known;
! *maybe_dependent = false;
! VEC_free (loop_p, heap, vloops);
! omega_free_problem (pb);
! return true;
! }
! }
! access_fun_b = chrec_fold_multiply (chrec_type (access_fun_b),
! access_fun_b, integer_minus_one_node);
! if (!init_omega_eq_with_af (pb, eq, nb_loops, access_fun_a, vloops)
! || !init_omega_eq_with_af (pb, eq, 0, access_fun_b, vloops))
! {
! /* There is probably a dependence, but the system of
! constraints cannot be built: answer "don't know". */
! VEC_free (loop_p, heap, vloops);
! omega_free_problem (pb);
! return false;
! }
! /* Quickly perform the GCD test. */
!
! if (dimension && pb->eqs[eq].coef[0] && !int_divides_p
! (lambda_vector_gcd ((lambda_vector) &(pb->eqs[eq].coef[1]),
! dimension), pb->eqs[eq].coef[0]))
{
/* There is no dependence. */
DDR_ARE_DEPENDENT (ddr) = chrec_known;
- *maybe_dependent = false;
- VEC_free (loop_p, heap, vloops);
- omega_free_problem (pb);
return true;
}
}
! /* Insert the constraints corresponding to the iteration domain:
! i.e. the loops surrounding the references "loop_x" and the
! distance variables "dx". */
! for (i = 0, ineq = 0; VEC_iterate (loop_p, vloops, i, loopi); i++)
{
tree nb_iters = get_number_of_iters_for_loop (loopi->num);
/* 0 <= loop_x */
pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
- ineq++;
/* 0 <= loop_x + dx */
pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
pb->geqs[ineq].coef[i + 1] = 1;
- ineq++;
if (nb_iters != NULL_TREE
&& TREE_CODE (nb_iters) == INTEGER_CST)
--- 4185,4401 ----
return true;
}
! /* As explained in the comments preceding init_omega_for_ddr, we have
! to set up a system for each loop level, setting outer loops
! variation to zero, and current loop variation to positive or zero.
! Save each lexico positive distance vector. */
! static void
! omega_extract_distance_vectors (omega_pb pb,
! struct data_dependence_relation *ddr)
! {
! int eq, geq;
! unsigned i, j;
! struct loop *loopi, *loopj;
! enum omega_result res;
! /* Set a new problem for each loop in the nest. The basis is the
! problem that we have initialized until now. On top of this we
! add new constraints. */
! for (i = 0; i <= DDR_INNER_LOOP (ddr)
! && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
! {
! int dist = 0;
! omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
! DDR_NB_LOOPS (ddr));
!
! omega_copy_problem (copy, pb);
!
! /* For all the outer loops "loop_j", add "dj = 0". */
! for (j = 0;
! j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
! {
! eq = omega_add_zero_eq (copy, omega_black);
! copy->eqs[eq].coef[j + 1] = 1;
! }
!
! /* For "loop_i", add "0 <= di". */
! geq = omega_add_zero_geq (copy, omega_black);
! copy->geqs[geq].coef[i + 1] = 1;
!
! /* Reduce the constraint system, and test that the current
! problem is feasible. */
! res = omega_simplify_problem (copy);
! if (res == omega_false
! || res == omega_unknown
! || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
! goto next_problem;
! for (eq = 0; eq < copy->num_subs; eq++)
! if (copy->subs[eq].key == (int) i + 1)
! {
! dist = copy->subs[eq].coef[0];
! goto found_dist;
! }
! if (dist == 0)
! {
! /* Reinitialize problem... */
! omega_copy_problem (copy, pb);
! for (j = 0;
! j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
! {
! eq = omega_add_zero_eq (copy, omega_black);
! copy->eqs[eq].coef[j + 1] = 1;
! }
! /* ..., but this time "di = 1". */
! eq = omega_add_zero_eq (copy, omega_black);
! copy->eqs[eq].coef[i + 1] = 1;
! copy->eqs[eq].coef[0] = -1;
!
! res = omega_simplify_problem (copy);
! if (res == omega_false
! || res == omega_unknown
! || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
! goto next_problem;
! for (eq = 0; eq < copy->num_subs; eq++)
! if (copy->subs[eq].key == (int) i + 1)
! {
! dist = copy->subs[eq].coef[0];
! goto found_dist;
! }
! }
! found_dist:;
! /* Save the lexicographically positive distance vector. */
! if (dist >= 0)
! {
! lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! dist_v[i] = dist;
! for (eq = 0; eq < copy->num_subs; eq++)
! if (copy->subs[eq].key > 0)
! {
! dist = copy->subs[eq].coef[0];
! dist_v[copy->subs[eq].key - 1] = dist;
! }
! for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
! dir_v[j] = dir_from_dist (dist_v[j]);
! save_dist_v (ddr, dist_v);
! save_dir_v (ddr, dir_v);
! }
! next_problem:;
! omega_free_problem (copy);
! }
! }
! /* This is called for each subscript of a tuple of data references:
! insert an equality for representing the conflicts. */
! static bool
! omega_setup_subscript (tree access_fun_a, tree access_fun_b,
! struct data_dependence_relation *ddr,
! omega_pb pb, bool *maybe_dependent)
! {
! tree difference;
! int eq;
!
! /* ZIV test. */
! if (ziv_subscript_p (access_fun_a, access_fun_b))
{
! tree difference = chrec_fold_minus (integer_type_node, access_fun_a,
! access_fun_b);
! if (TREE_CODE (difference) == INTEGER_CST
! && !integer_zerop (difference))
! {
! /* There is no dependence. */
! *maybe_dependent = false;
! return true;
! }
}
! /* When the fun_a - fun_b is not constant, the dependence is not
! captured by the classic distance vector representation. */
! difference = chrec_fold_minus (integer_type_node, access_fun_a,
! access_fun_b);
! if (TREE_CODE (difference) != INTEGER_CST)
return false;
! access_fun_b = chrec_fold_multiply (chrec_type (access_fun_b),
! access_fun_b, integer_minus_one_node);
! eq = omega_add_zero_eq (pb, omega_black);
! if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), access_fun_a, ddr)
! || !init_omega_eq_with_af (pb, eq, 0, access_fun_b, ddr))
! /* There is probably a dependence, but the system of
! constraints cannot be built: answer "don't know". */
! return false;
!
! /* Quickly perform the GCD test. */
! if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
! && !int_divides_p (lambda_vector_gcd
! ((lambda_vector) &(pb->eqs[eq].coef[1]),
! 2 * DDR_NB_LOOPS (ddr)),
! pb->eqs[eq].coef[0]))
{
! /* There is no dependence. */
! *maybe_dependent = false;
! return true;
! }
! return true;
! }
! /* Helper function, same as init_omega_for_ddr but specialized for
! data references A and B. */
! static bool
! init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
! struct data_dependence_relation *ddr,
! omega_pb pb, bool *maybe_dependent)
! {
! unsigned i;
! int ineq;
! struct loop *loopi;
! unsigned nb_loops = DDR_NB_LOOPS (ddr);
! /* Insert an equality per subscript. */
! for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
! {
! if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
! ddr, pb, maybe_dependent))
! return false;
! else if (*maybe_dependent == false)
{
/* There is no dependence. */
DDR_ARE_DEPENDENT (ddr) = chrec_known;
return true;
}
}
! /* Insert inequalities: constraints corresponding to the iteration
! domain, i.e. the loops surrounding the references "loop_x" and
! the distance variables "dx". */
! for (i = 0; i <= DDR_INNER_LOOP (ddr)
! && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
{
tree nb_iters = get_number_of_iters_for_loop (loopi->num);
/* 0 <= loop_x */
+ ineq = omega_add_zero_geq (pb, omega_black);
pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
/* 0 <= loop_x + dx */
+ ineq = omega_add_zero_geq (pb, omega_black);
pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
pb->geqs[ineq].coef[i + 1] = 1;
if (nb_iters != NULL_TREE
&& TREE_CODE (nb_iters) == INTEGER_CST)
*************** init_omega_for_ddr (struct data_dependen
*** 4279,4425 ****
int nbi = int_cst_value (nb_iters);
/* loop_x <= nb_iters */
pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
pb->geqs[ineq].coef[0] = nbi;
- ineq++;
/* loop_x + dx <= nb_iters */
pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
pb->geqs[ineq].coef[i + 1] = -1;
pb->geqs[ineq].coef[0] = nbi;
! ineq++;
}
}
! /* Attach the Omega problem to the data dependence relation. */
! DDR_OMEGA (ddr) = pb;
! VEC_free (loop_p, heap, vloops);
return true;
}
! /* Construct the constraint system for DDR, then solve it by polyhedra
! solver. */
!
! static void
! polyhedra_dependence_tester (struct data_dependence_relation *ddr)
! {
! /* Translate to generating system (gs) representation, then detect
! dep/indep. */
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, "(polyhedra_dependence_tester \n");
! dump_data_dependence_relation (dump_file, ddr);
! csys_print (dump_file, DDR_CSYS (ddr));
! }
! DDR_POLYHEDRON (ddr) = polyhedron_from_csys (DDR_CSYS (ddr));
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! gsys_print (dump_file, POLYH_GSYS (DDR_POLYHEDRON (ddr)));
! fprintf (dump_file, ") \n");
! }
! dependence_stats.num_dependence_undetermined++;
! finalize_ddr_dependent (ddr, chrec_dont_know);
! }
! /* Initialize DDR's distance and direction vectors from the omega
! problem. */
! static void
! omega_compute_classic_representations (struct data_dependence_relation *ddr)
{
! int i;
! lambda_vector dist_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
! lambda_vector dir_v = lambda_vector_new (DDR_SIZE_VECT (ddr));
! for (i = 0; i < DDR_SIZE_VECT (ddr); i++)
! {
! int dist = DDR_OMEGA (ddr)->eqs[i].coef[0];
! enum data_dependence_direction dir = dir_star;
! /* FIXME: Computing dir this way is suboptimal, since dir can
! catch cases that dist is unable to represent. */
! if (dist == 0)
! dir = dir_equal;
! else if (dist > 0)
! dir = dir_positive;
! else if (dist < 0)
! dir = dir_negative;
!
! #if 0
! if (0)
! {
! int dd_lt = 1, dd_eq = 2, dd_gt = 4;
!
! result = omega_query_variable_signs (DDR_OMEGA (ddr), i,
! dd_lt, dd_eq, dd_gt,
! lower_bound, upper_bound,
! &dist_known, dist);
! }
! #endif
! dist_v[i] = dist;
! dir_v[i] = dir;
}
! VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
! VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
}
! /* Construct the constraint system for DDR, then solve it using the
! OMEGA solver. */
static void
! omega_dependence_tester (struct data_dependence_relation *ddr)
{
! enum omega_result res;
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "(omega_dependence_tester \n");
dump_data_dependence_relation (dump_file, ddr);
! omega_pretty_print_problem (dump_file, DDR_OMEGA (ddr));
}
! res = omega_simplify_problem (DDR_OMEGA (ddr));
!
! /* FIXME: Seems like omega_simplify always returns omega_false, so
! RES is not a good criteria to be used for distinguish between
! dep/indep/unknown. Have to better document the return value for
! omega_solve_problem. For the moment systematically initialize
! dist/dir. */
!
! omega_compute_classic_representations (ddr);
! dependence_stats.num_dependence_dependent++;
- #if 0
- if (res == omega_false)
- {
- /* When there is no solution to the dependence problem, there is
- no dependence. */
- finalize_ddr_dependent (ddr, chrec_known);
- dependence_stats.num_dependence_independent++;
- }
- else if (res == omega_true)
- {
- omega_compute_classic_representations (ddr);
- dependence_stats.num_dependence_dependent++;
- }
- else
- {
- dependence_stats.num_dependence_undetermined++;
- finalize_ddr_dependent (ddr, chrec_dont_know);
- }
- #endif
-
if (dump_file && (dump_flags & TDF_DETAILS))
{
! dump_data_dependence_relation (dump_file, ddr);
! fprintf (dump_file, ")\n");
}
}
/* Check that DDR contains the same information as that stored in
--- 4403,4583 ----
int nbi = int_cst_value (nb_iters);
/* loop_x <= nb_iters */
+ ineq = omega_add_zero_geq (pb, omega_black);
pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
pb->geqs[ineq].coef[0] = nbi;
/* loop_x + dx <= nb_iters */
+ ineq = omega_add_zero_geq (pb, omega_black);
pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
pb->geqs[ineq].coef[i + 1] = -1;
pb->geqs[ineq].coef[0] = nbi;
!
! /* A step "dx" bigger than nb_iters is not feasible, so
! add "dx <= nb_iters". */
! ineq = omega_add_zero_geq (pb, omega_black);
! pb->geqs[ineq].coef[i + 1] = -1;
! pb->geqs[ineq].coef[0] = nbi;
}
}
! omega_extract_distance_vectors (pb, ddr);
!
return true;
}
! /* Sets up the Omega dependence problem for the data dependence
! relation DDR. Returns false when the constraint system cannot be
! built, ie. when the test answers "don't know". Returns true
! otherwise, and when independence has been proved (using one of the
! trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
! set MAYBE_DEPENDENT to true.
! Example: for setting up the dependence system corresponding to the
! conflicting accesses
! | loop_i
! | loop_j
! | A[i, i+1] = ...
! | ... A[2*j, 2*(i + j)]
! | endloop_j
! | endloop_i
!
! the following constraints come from the iteration domain:
! 0 <= i <= Ni
! 0 <= i + di <= Ni
! 0 <= j <= Nj
! 0 <= j + dj <= Nj
!
! where di, dj are the distance variables. The constraints
! representing the conflicting elements are:
!
! i = 2 * (j + dj)
! i + 1 = 2 * (i + di + j + dj)
!
! For asking that the resulting distance vector (di, dj) be
! lexicographically positive, we insert the constraint "di >= 0". If
! "di = 0" in the solution, we fix that component to zero, and we
! look at the inner loops: we set a new problem where all the outer
! loop distances are zero, and fix this inner component to be
! positive. When one of the components is positive, we save that
! distance, and set a new problem where the distance on this loop is
! zero, searching for other distances in the inner loops. Here is
! the classic example that illustrates that we have to set for each
! inner loop a new problem:
!
! | loop_1
! | loop_2
! | A[10]
! | endloop_2
! | endloop_1
!
! we have to save two distances (1, 0) and (0, 1).
!
! Given two array references, refA and refB, we have to set the
! dependence problem twice, refA vs. refB and refB vs. refA, and we
! cannot do a single test, as refB might occur before refA in the
! inner loops, and the contrary when considering outer loops: ex.
!
! | loop_0
! | loop_1
! | loop_2
! | T[{1,+,1}_2][{1,+,1}_1] // refA
! | T[{2,+,1}_2][{0,+,1}_1] // refB
! | endloop_2
! | endloop_1
! | endloop_0
!
! refB touches the elements in T before refA, and thus for the same
! loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
! but for successive loop_0 iterations, we have (1, -1, 1)
! The Omega solver expects the distance variables ("di" in the
! previous example) to come first in the constraint system (as
! variables to be protected, or "safe" variables), the constraint
! system is built using the following layout:
! "cst | distance vars | index vars".
! */
! static bool
! init_omega_for_ddr (struct data_dependence_relation *ddr,
! bool *maybe_dependent)
{
! omega_pb pb;
! bool res = false;
! *maybe_dependent = true;
! if (same_access_functions (ddr))
! {
! unsigned j;
! lambda_vector dir_v;
! /* Save the 0 vector. */
! save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
! dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
! for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
! dir_v[j] = dir_equal;
! save_dir_v (ddr, dir_v);
!
! /* Save the dependences carried by outer loops. */
! pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
! res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
! maybe_dependent);
! omega_free_problem (pb);
! return res;
}
! /* Omega expects the protected variables (those that have to be kept
! after elimination) to appear first in the constraint system.
! These variables are the distance variables. In the following
! initialization we declare NB_LOOPS safe variables, and the total
! number of variables for the constraint system is 2*NB_LOOPS. */
! pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
! res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
! maybe_dependent);
! omega_free_problem (pb);
!
! /* Stop computation if not decidable, or no dependence. */
! if (res == false || *maybe_dependent == false)
! return res;
!
! pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
! res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
! maybe_dependent);
! omega_free_problem (pb);
!
! return res;
}
! /* Construct the constraint system for DDR, then solve it by polyhedra
! solver. */
static void
! polyhedra_dependence_tester (struct data_dependence_relation *ddr)
{
! /* Translate to generating system (gs) representation, then detect
! dep/indep. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "(polyhedra_dependence_tester \n");
dump_data_dependence_relation (dump_file, ddr);
! csys_print (dump_file, DDR_CSYS (ddr));
}
! DDR_POLYHEDRON (ddr) = polyhedron_from_csys (DDR_CSYS (ddr));
if (dump_file && (dump_flags & TDF_DETAILS))
{
! gsys_print (dump_file, POLYH_GSYS (DDR_POLYHEDRON (ddr)));
! fprintf (dump_file, ") \n");
}
+
+ dependence_stats.num_dependence_undetermined++;
+ finalize_ddr_dependent (ddr, chrec_dont_know);
}
/* Check that DDR contains the same information as that stored in
*************** check_ddr (FILE *outf,
*** 4431,4437 ****
VEC (lambda_vector, heap) *dist_vects,
VEC (lambda_vector, heap) *dir_vects)
{
! unsigned int i;
/* If dump_file is set, output there. */
if (dump_file && (dump_flags & TDF_DETAILS))
--- 4589,4595 ----
VEC (lambda_vector, heap) *dist_vects,
VEC (lambda_vector, heap) *dir_vects)
{
! unsigned int i, j;
/* If dump_file is set, output there. */
if (dump_file && (dump_flags & TDF_DETAILS))
*************** check_ddr (FILE *outf,
*** 4439,4469 ****
if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
{
! lambda_vector a_dist_v, b_dist_v;
! fprintf (outf, "Number of distance vectors differ: %d != %d\n",
VEC_length (lambda_vector, dist_vects),
DDR_NUM_DIST_VECTS (ddr));
for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
! {
! fprintf (outf, "Banerjee dist vectors:\n");
! print_lambda_vector (outf, b_dist_v, VEC_length (lambda_vector,
! dist_vects));
! }
for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
! {
! a_dist_v = DDR_DIST_VECT (ddr, i);
! fprintf (outf, "Omega dist vectors:\n");
! print_lambda_vector (outf, a_dist_v, DDR_SIZE_VECT (ddr));
! }
return;
}
if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
{
! fprintf (outf, "Number of direction vectors differ: %d != %d.\n",
VEC_length (lambda_vector, dir_vects),
DDR_NUM_DIR_VECTS (ddr));
return;
--- 4597,4625 ----
if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
{
! lambda_vector b_dist_v;
! fprintf (outf, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
VEC_length (lambda_vector, dist_vects),
DDR_NUM_DIST_VECTS (ddr));
+ fprintf (outf, "Banerjee dist vectors:\n");
for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
! print_lambda_vector (outf, b_dist_v, DDR_NB_LOOPS (ddr));
+ fprintf (outf, "Omega dist vectors:\n");
for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
! print_lambda_vector (outf, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
+ fprintf (outf, "data dependence relation:\n");
+ dump_data_dependence_relation (outf, ddr);
+
+ fprintf (outf, ")\n");
return;
}
if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
{
! fprintf (outf, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
VEC_length (lambda_vector, dir_vects),
DDR_NUM_DIR_VECTS (ddr));
return;
*************** check_ddr (FILE *outf,
*** 4471,4503 ****
for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
{
! lambda_vector a_dist_v = DDR_DIST_VECT (ddr, i);
! lambda_vector b_dist_v = VEC_index (lambda_vector, dist_vects, i);
! if (!lambda_vector_equal (a_dist_v, b_dist_v, DDR_SIZE_VECT (ddr)))
{
! fprintf (outf, "Dist vectors from the first dependence analyzer:\n");
! print_lambda_vector (outf, a_dist_v, DDR_SIZE_VECT (ddr));
! fprintf (outf, "Omega dist vectors are not the same:\n");
! print_lambda_vector (outf, b_dist_v, DDR_SIZE_VECT (ddr));
! fprintf (outf, "Data dependence relation is:\n");
dump_data_dependence_relation (outf, ddr);
}
}
for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
{
! lambda_vector a_dir_v = DDR_DIR_VECT (ddr, i);
! lambda_vector b_dir_v = VEC_index (lambda_vector, dir_vects, i);
! if (!lambda_vector_equal (a_dir_v, b_dir_v, DDR_SIZE_VECT (ddr)))
{
! fprintf (outf, "Dir vectors from the first dependence analyzer:\n");
! print_lambda_vector (outf, a_dir_v, DDR_SIZE_VECT (ddr));
! fprintf (outf, "Omega dir vectors are not the same:\n");
! print_lambda_vector (outf, b_dir_v, DDR_SIZE_VECT (ddr));
! fprintf (outf, "Data dependence relation is:\n");
dump_data_dependence_relation (outf, ddr);
}
}
--- 4627,4669 ----
for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
{
! lambda_vector a_dist_v;
! lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
! for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
! if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
! break;
!
! if (j == VEC_length (lambda_vector, dist_vects))
{
! fprintf (outf, "\n(Dist vectors from the first dependence analyzer:\n");
! print_dist_vectors (outf, dist_vects, DDR_NB_LOOPS (ddr));
! fprintf (outf, "not found in Omega dist vectors:\n");
! print_dist_vectors (outf, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
! fprintf (outf, "data dependence relation:\n");
dump_data_dependence_relation (outf, ddr);
+ fprintf (outf, ")\n");
}
}
for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
{
! lambda_vector a_dir_v;
! lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
!
! for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
! if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
! break;
! if (j == VEC_length (lambda_vector, dist_vects))
{
! fprintf (outf, "\n(Dir vectors from the first dependence analyzer:\n");
! print_dir_vectors (outf, dir_vects, DDR_NB_LOOPS (ddr));
! fprintf (outf, "not found in Omega dir vectors:\n");
! print_dir_vectors (outf, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
! fprintf (outf, "data dependence relation:\n");
dump_data_dependence_relation (outf, ddr);
+ fprintf (outf, ")\n");
}
}
*************** check_ddr (FILE *outf,
*** 4514,4521 ****
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);
--- 4680,4686 ----
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
*** 4541,4547 ****
if (flag_check_data_deps)
{
/* Compute the dependences using the first algorithm. */
! subscript_dependence_tester (ddr, loop_nest_depth);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\n\nBanerjee Analyzer\n");
--- 4706,4713 ----
if (flag_check_data_deps)
{
/* Compute the dependences using the first algorithm. */
! subscript_dependence_tester (ddr);
!
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\n\nBanerjee Analyzer\n");
*************** compute_affine_dependence (struct data_d
*** 4554,4574 ****
VEC (lambda_vector, heap) *dir_vects, *dist_vects;
/* Save the result of the first DD analyzer. */
! dist_vects = ddr->dist_vects;
! dir_vects = ddr->dir_vects;
/* Reset the information. */
! ddr->dist_vects = NULL;
! ddr->dir_vects = NULL;
! /* Set up the problem for the second DD analyzer. */
if (!init_omega_for_ddr (ddr, &maybe_dependent))
goto csys_dont_know;
if (maybe_dependent)
{
- /* Compute the same information using Omega. */
- omega_dependence_tester (ddr);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Omega Analyzer\n");
--- 4720,4738 ----
VEC (lambda_vector, heap) *dir_vects, *dist_vects;
/* Save the result of the first DD analyzer. */
! dist_vects = DDR_DIST_VECTS (ddr);
! dir_vects = DDR_DIR_VECTS (ddr);
/* Reset the information. */
! DDR_DIST_VECTS (ddr) = NULL;
! DDR_DIR_VECTS (ddr) = NULL;
! /* Compute the same information using Omega. */
if (!init_omega_for_ddr (ddr, &maybe_dependent))
goto csys_dont_know;
if (maybe_dependent)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Omega Analyzer\n");
*************** compute_affine_dependence (struct data_d
*** 4600,4606 ****
}
else
! subscript_dependence_tester (ddr, loop_nest_depth);
}
/* As a last case, if the dependence cannot be determined, or if
--- 4764,4770 ----
}
else
! subscript_dependence_tester (ddr);
}
/* As a last case, if the dependence cannot be determined, or if
*************** static void
*** 4634,4640 ****
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++)
{
--- 4798,4803 ----
*************** compute_self_dependence (struct data_dep
*** 4647,4677 ****
}
/* 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. */
--- 4810,4831 ----
}
/* 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
*** 4689,4697 ****
&& !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)
--- 4843,4851 ----
&& !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
*** 4705,4711 ****
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);
}
--- 4859,4865 ----
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
*** 4849,4857 ****
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,
--- 5003,5049 ----
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
*** 4865,4903 ****
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))
{
--- 5057,5096 ----
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))
{
*************** compute_data_dependences_for_loop (struc
*** 4945,4951 ****
dependence_stats.num_miv_independent);
fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
dependence_stats.num_miv_unimplemented);
! }
}
/* Entry point (for testing only). Analyze all the data references
--- 5138,5144 ----
dependence_stats.num_miv_independent);
fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
dependence_stats.num_miv_unimplemented);
! }
}
/* Entry point (for testing only). Analyze all the data references
*************** free_dependence_relation (struct data_de
*** 5048,5056 ****
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
varray_clear (DDR_SUBSCRIPTS (ddr));
- if (DDR_OMEGA (ddr))
- omega_free_problem (DDR_OMEGA (ddr));
-
free (ddr);
}
--- 5241,5246 ----
Index: tree-data-ref.h
===================================================================
*** tree-data-ref.h (revision 112238)
--- tree-data-ref.h (working copy)
*************** struct subscript
*** 189,194 ****
--- 189,198 ----
#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
*** 220,228 ****
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;
--- 224,235 ----
the data_dependence_relation. */
varray_type subscripts;
! /* The analyzed loop nest. */
! VEC (loop_p, heap) *loop_nest;
!
! /* An index in loop_nest for the innermost loop that varies for
! this data dependence relation. */
! unsigned inner_loop;
/* The classic direction vector. */
VEC(lambda_vector,heap) *dir_vects;
*************** struct data_dependence_relation
*** 236,243 ****
/* Representation of the dependence as polyhedra. */
polyhedron dependence_polyhedron;
- /* Representation of the dependence as an Omega problem. */
- omega_pb omega_dependence;
};
typedef struct data_dependence_relation *ddr_p;
--- 243,248 ----
*************** DEF_VEC_ALLOC_P(ddr_p,heap);
*** 253,259 ****
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)
--- 258,269 ----
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_INNER_LOOP(DDR) DDR->inner_loop
#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
*************** DEF_VEC_ALLOC_P(ddr_p,heap);
*** 267,273 ****
VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
#define DDR_CSYS(DDR) DDR->dependence_constraint_system
#define DDR_POLYHEDRON(DDR) DDR->dependence_polyhedron
- #define DDR_OMEGA(DDR) DDR->omega_dependence
#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
--- 277,282 ----
*************** extern tree find_data_references_in_loop
*** 286,296 ****
--- 295,308 ----
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);