This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] cleanups for data-ref.c
- From: Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 19 Aug 2004 22:53:04 +0200
- Subject: [lno] cleanups for data-ref.c
Hi,
Working on adding support for the multivariate dependence relations,
here are some cleanups for the data dependence analysis.
Sebastian
Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.252
diff -d -u -p -r1.1.2.252 ChangeLog.lno
--- ChangeLog.lno 15 Aug 2004 21:37:34 -0000 1.1.2.252
+++ ChangeLog.lno 19 Aug 2004 20:45:18 -0000
@@ -1,3 +1,37 @@
+2004-08-19 Sebastian Pop <pop@cri.ensmp.fr>
+
+ * Makefile.in (tree-ssa-loop-manip.o): Depend on $(SCEV_H)
+ instead of tree-scalar-evolution.h.
+ * tree-data-ref.c (array_base_name_differ_p): Remove useless
+ initialization.
+ (tree_fold_bezout): Removed.
+ (dump_subscript): New.
+ (dump_data_dependence_relation): Use dump_subscript.
+ (dump_dist_dir_vectors): New.
+ (initialize_data_dependence_relation): Initialize DDR_AFFINE_P.
+ (non_affine_dependence_relation): New.
+ (analyze_subscript_affine_affine): Use lambda_matrix_right_hermite
+ instead of tree_fold_bezout. Add some more comments.
+ (analyze_siv_subscript): Pass to analyze_subscript_affine_affine not
+ only univariate dependence relations, but also multivariate ones.
+ (analyze_miv_subscript): Same. Add more comments.
+ (undetermined_conflicts_p, no_conflicts_p): New; in use...
+ (subscript_dependence_tester): ...here.
+ (build_classic_dist_vector, build_classic_dir_vector): Use
+ non_affine_dependence_relation for classifying relations that
+ cannot be represented as distance vectors.
+ (analyze_all_data_dependences): Use dump_dist_dir_vectors.
+ Restructure the dumping.
+ * tree-data-ref.h (data_dependence_relation): Add a boolean
+ field affine_p.
+ (DDR_AFFINE_P): And its accessor.
+ (dump_subscript, dump_dist_dir_vectors): Declared here.
+ * tree-loop-linear.c (linear_transform_loops): Use
+ dump_dist_dir_vectors.
+ * tree-scalar-evolution.h: Include tree-chrec.h.
+ * tree.c (tree_fold_gcd): Use TRUNC_MOD_EXPR for computing the
+ modulo operation with C semantics.
+
2004-08-15 Ira Rosen <irar@il.ibm.com>
* tree-vectorizer.h (stmt_vec_info): Add vect_dr_base field.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.158.2.45
diff -d -u -p -r1.903.2.158.2.45 Makefile.in
--- Makefile.in 28 Jul 2004 01:18:15 -0000 1.903.2.158.2.45
+++ Makefile.in 19 Aug 2004 20:45:18 -0000
@@ -1707,7 +1707,7 @@ tree-ssa-loop-ivopts.o : tree-ssa-loop-i
tree-ssa-loop-manip.o : tree-ssa-loop-manip.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
- tree-pass.h $(FLAGS_H) cfglayout.h tree-scalar-evolution.h
+ tree-pass.h $(FLAGS_H) cfglayout.h $(SCEV_H)
tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h $(PARAMS_H) tree-inline.h \
output.h diagnostic.h $(TM_H) coretypes.h $(TREE_DUMP_H) flags.h \
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 1.1.2.33
diff -d -u -p -r1.1.2.33 tree-data-ref.c
--- tree-data-ref.c 15 Aug 2004 21:37:35 -0000 1.1.2.33
+++ tree-data-ref.c 19 Aug 2004 20:45:18 -0000
@@ -196,7 +196,6 @@ array_base_name_differ_p (struct data_re
return true;
}
- *differ_p = false; /* Don't know, but be conservative. */
return false;
}
@@ -215,105 +214,6 @@ tree_fold_divides_p (tree type,
(fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
}
-/* Bezout: Let A1 and A2 be two integers; there exist two integers U11
- and U12 such that,
-
- | U11 * A1 + U12 * A2 = gcd (A1, A2).
-
- This function computes the greatest common divisor using the
- Blankinship algorithm. The gcd is returned, and the coefficients
- of the unimodular matrix U are (U11, U12, U21, U22) such that,
-
- | U.A = S
-
- | (U11 U12) (A1) = (gcd)
- | (U21 U22) (A2) (0)
-
- FIXME: Use lambda_..._hermite for implementing this function.
-*/
-
-static tree
-tree_fold_bezout (tree a1,
- tree a2,
- tree *u11, tree *u12,
- tree *u21, tree *u22)
-{
- tree s1, s2;
-
- /* Initialize S with the coefficients of A. */
- s1 = a1;
- s2 = a2;
-
- /* Initialize the U matrix */
- *u11 = integer_one_node;
- *u12 = integer_zero_node;
- *u21 = integer_zero_node;
- *u22 = integer_one_node;
-
- if (integer_zerop (a1)
- || integer_zerop (a2))
- return integer_zero_node;
-
- while (!integer_zerop (s2))
- {
- int sign;
- tree z, zu21, zu22, zs2;
-
- sign = tree_int_cst_sgn (s1) * tree_int_cst_sgn (s2);
- z = fold (build (FLOOR_DIV_EXPR, integer_type_node,
- fold (build1 (ABS_EXPR, integer_type_node, s1)),
- fold (build1 (ABS_EXPR, integer_type_node, s2))));
- zu21 = fold (build (MULT_EXPR, integer_type_node, z, *u21));
- zu22 = fold (build (MULT_EXPR, integer_type_node, z, *u22));
- zs2 = fold (build (MULT_EXPR, integer_type_node, z, s2));
-
- /* row1 -= z * row2. */
- if (sign < 0)
- {
- *u11 = fold (build (PLUS_EXPR, integer_type_node, *u11, zu21));
- *u12 = fold (build (PLUS_EXPR, integer_type_node, *u12, zu22));
- s1 = fold (build (PLUS_EXPR, integer_type_node, s1, zs2));
- }
- else if (sign > 0)
- {
- *u11 = fold (build (MINUS_EXPR, integer_type_node, *u11, zu21));
- *u12 = fold (build (MINUS_EXPR, integer_type_node, *u12, zu22));
- s1 = fold (build (MINUS_EXPR, integer_type_node, s1, zs2));
- }
- else
- /* Should not happen. */
- abort ();
-
- /* Interchange row1 and row2. */
- {
- tree flip;
-
- flip = *u11;
- *u11 = *u21;
- *u21 = flip;
-
- flip = *u12;
- *u12 = *u22;
- *u22 = flip;
-
- flip = s1;
- s1 = s2;
- s2 = flip;
- }
- }
-
- if (tree_int_cst_sgn (s1) < 0)
- {
- *u11 = fold (build (MULT_EXPR, integer_type_node, *u11,
- integer_minus_one_node));
- *u12 = fold (build (MULT_EXPR, integer_type_node, *u12,
- integer_minus_one_node));
- s1 = fold (build (MULT_EXPR, integer_type_node, s1, integer_minus_one_node));
- }
-
- return s1;
-}
-
/* Dump into FILE all the data references from DATAREFS. */
@@ -363,6 +263,45 @@ dump_data_reference (FILE *outf,
fprintf (outf, ")\n");
}
+void
+dump_subscript (FILE *outf, struct subscript *subscript)
+{
+ tree chrec = SUB_CONFLICTS_IN_A (subscript);
+
+ fprintf (outf, "\n (subscript \n");
+ fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
+ print_generic_stmt (outf, chrec, 0);
+ if (chrec == chrec_known)
+ fprintf (outf, " (no dependence)\n");
+ else if (chrec_contains_undetermined (chrec))
+ fprintf (outf, " (don't know)\n");
+ else
+ {
+ tree last_iteration = SUB_LAST_CONFLICT_IN_A (subscript);
+ fprintf (outf, " last_iteration_that_access_an_element_twice_in_A: ");
+ print_generic_stmt (outf, last_iteration, 0);
+ }
+
+ chrec = SUB_CONFLICTS_IN_B (subscript);
+ fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
+ print_generic_stmt (outf, chrec, 0);
+ if (chrec == chrec_known)
+ fprintf (outf, " (no dependence)\n");
+ else if (chrec_contains_undetermined (chrec))
+ fprintf (outf, " (don't know)\n");
+ else
+ {
+ tree last_iteration = SUB_LAST_CONFLICT_IN_B (subscript);
+ fprintf (outf, " last_iteration_that_access_an_element_twice_in_B: ");
+ print_generic_stmt (outf, last_iteration, 0);
+ }
+
+ fprintf (outf, " (Subscript distance: ");
+ print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
+ fprintf (outf, " )\n");
+ fprintf (outf, " )\n");
+}
+
/* Dump function for a DATA_DEPENDENCE_RELATION structure. */
void
@@ -375,10 +314,14 @@ dump_data_dependence_relation (FILE *out
dra = DDR_A (ddr);
drb = DDR_B (ddr);
+ fprintf (outf, "(Data Dep: \n");
if (dra && drb)
- fprintf (outf, "(Data Dep:");
- else
- fprintf (outf, "(Data Dep:");
+ {
+ fprintf (outf, " access_fn_A: ");
+ print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
+ fprintf (outf, " access_fn_B: ");
+ print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
+ }
if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
fprintf (outf, " (don't know)\n");
@@ -389,57 +332,7 @@ dump_data_dependence_relation (FILE *out
else
{
for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree chrec;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
-
- fprintf (outf, "\n (subscript %d:\n", i);
- fprintf (outf, " access_fn_A: ");
- print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
- fprintf (outf, " access_fn_B: ");
- print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
-
- chrec = SUB_CONFLICTS_IN_A (subscript);
- fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
- print_generic_stmt (outf, chrec, 0);
- if (chrec == chrec_known)
- fprintf (outf, " (no dependence)\n");
- else if (chrec_contains_undetermined (chrec))
- fprintf (outf, " (don't know)\n");
- else
- {
- tree last_iteration = SUB_LAST_CONFLICT_IN_A (subscript);
- fprintf (outf, " last_iteration_that_access_an_element_twice_in_A: ");
- print_generic_stmt (outf, last_iteration, 0);
- }
-
- chrec = SUB_CONFLICTS_IN_B (subscript);
- fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
- print_generic_stmt (outf, chrec, 0);
- if (chrec == chrec_known)
- fprintf (outf, " (no dependence)\n");
- else if (chrec_contains_undetermined (chrec))
- fprintf (outf, " (don't know)\n");
- else
- {
- tree last_iteration = SUB_LAST_CONFLICT_IN_B (subscript);
- fprintf (outf, " last_iteration_that_access_an_element_twice_in_B: ");
- print_generic_stmt (outf, last_iteration, 0);
- }
-
- fprintf (outf, " )\n");
- }
-
- fprintf (outf, " (Distance Vector: \n");
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
-
- fprintf (outf, "(");
- print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
- fprintf (outf, ")\n");
- }
- fprintf (outf, " )\n");
+ dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
}
fprintf (outf, ")\n");
@@ -488,6 +381,35 @@ dump_data_dependence_direction (FILE *fi
}
}
+/* Dumps the distance and direction vectors in FILE. DDRS contains
+ the dependence relations, and VECT_SIZE is the size of the
+ dependence vectors, or in other words the number of loops in the
+ considered nest. */
+
+void
+dump_dist_dir_vectors (FILE *file, varray_type ddrs, unsigned int vect_size)
+{
+ unsigned int i;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
+ {
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (ddrs, i);
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
+ && DDR_AFFINE_P (ddr))
+ {
+ fprintf (file, "DISTANCE_V (");
+ print_lambda_vector (file, DDR_DIST_VECT (ddr), vect_size);
+ fprintf (file, ")\n");
+ fprintf (file, "DIRECTION_V (");
+ print_lambda_vector (file, DDR_DIR_VECT (ddr), vect_size);
+ fprintf (file, ")\n");
+ }
+ }
+ fprintf (file, "\n\n");
+}
+
/* Given an ARRAY_REF node REF, records its access functions.
@@ -652,6 +574,7 @@ initialize_data_dependence_relation (str
else
{
unsigned int i;
+ DDR_AFFINE_P (res) = true;
DDR_ARE_DEPENDENT (res) = NULL_TREE;
DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
@@ -690,6 +613,18 @@ finalize_ddr_dependent (struct data_depe
varray_clear (DDR_SUBSCRIPTS (ddr));
}
+/* The dependence relation DDR cannot be represented by a distance
+ vector. */
+
+static inline void
+non_affine_dependence_relation (struct data_dependence_relation *ddr)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
+
+ DDR_AFFINE_P (ddr) = false;
+}
+
/* This section contains the classic Banerjee tests. */
@@ -1006,45 +941,26 @@ analyze_subscript_affine_affine (tree ch
(ALPHA, BETA) divides GAMMA. This is commonly known under
the name of the "gcd-test".
*/
- tree alpha, beta, gamma;
- tree la, lb;
+ tree gamma;
tree gcd_alpha_beta;
- tree u11, u12, u21, u22;
+ lambda_matrix A, U, S;
- /* Both alpha and beta have to be integer_type_node. The gcd
- function does not work correctly otherwise. */
- alpha = copy_node (right_a);
- beta = copy_node (right_b);
- la = copy_node (left_a);
- lb = copy_node (left_b);
- TREE_TYPE (alpha) = integer_type_node;
- TREE_TYPE (beta) = integer_type_node;
- TREE_TYPE (la) = integer_type_node;
- TREE_TYPE (lb) = integer_type_node;
-
- gamma = fold (build (MINUS_EXPR, integer_type_node, lb, la));
-
- /* FIXME: Use lambda_*_Hermite for implementing Bezout. */
- gcd_alpha_beta = tree_fold_bezout
- (alpha,
- fold (build (MULT_EXPR, integer_type_node, beta,
- integer_minus_one_node)),
- &u11, &u12,
- &u21, &u22);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " (alpha = ");
- print_generic_expr (dump_file, alpha, 0);
- fprintf (dump_file, ")\n (beta = ");
- print_generic_expr (dump_file, beta, 0);
- fprintf (dump_file, ")\n (gamma = ");
- print_generic_expr (dump_file, gamma, 0);
- fprintf (dump_file, ")\n (gcd_alpha_beta = ");
- print_generic_expr (dump_file, gcd_alpha_beta, 0);
- fprintf (dump_file, ")\n");
- }
+ A = lambda_matrix_new (2, 1);
+ U = lambda_matrix_new (2, 2);
+ S = lambda_matrix_new (2, 1);
+ A[0][0] = int_cst_value (right_a);
+ A[1][0] = -1 * int_cst_value (right_b);
+
+ /* U.A = S */
+ lambda_matrix_right_hermite (A, 2, 1, S, U);
+
+ gcd_alpha_beta = build_int_2 (S[0][0] < 0 ? -1 * S[0][0] : S[0][0], 0);
+ gamma = fold (build (MINUS_EXPR, integer_type_node, left_b, left_a));
+ if (tree_int_cst_sgn (gamma) < 0)
+ gamma = fold (build (MULT_EXPR, integer_type_node,
+ integer_minus_one_node, gamma));
+
/* The classic "gcd-test". */
if (!tree_fold_divides_p (integer_type_node, gcd_alpha_beta, gamma))
{
@@ -1063,8 +979,9 @@ analyze_subscript_affine_affine (tree ch
For a given integer t. Using the following variables,
- | i0 = u11 * gamma / gcd_alpha_beta
- | j0 = u12 * gamma / gcd_alpha_beta
+ | gamma_gcd = gamma / gcd_alpha_beta
+ | i0 = u11 * gamma_gcd
+ | j0 = u12 * gamma_gcd
| i1 = u21
| j1 = u22
@@ -1085,10 +1002,12 @@ analyze_subscript_affine_affine (tree ch
gamma. */
gamma_gcd = fold (build (EXACT_DIV_EXPR, integer_type_node, gamma,
gcd_alpha_beta));
- i0 = fold (build (MULT_EXPR, integer_type_node, u11, gamma_gcd));
- j0 = fold (build (MULT_EXPR, integer_type_node, u12, gamma_gcd));
- i1 = u21;
- j1 = u22;
+ i0 = fold (build (MULT_EXPR, integer_type_node,
+ build_int_2 (U[0][0], 0), gamma_gcd));
+ j0 = fold (build (MULT_EXPR, integer_type_node,
+ build_int_2 (U[0][1], 0), gamma_gcd));
+ i1 = build_int_2 (U[1][0], 0);
+ j1 = build_int_2 (U[1][1], 0);
if ((tree_int_cst_sgn (i1) == 0
&& tree_int_cst_sgn (i0) < 0)
@@ -1123,7 +1042,8 @@ analyze_subscript_affine_affine (tree ch
integer_type_node, j0,
integer_minus_one_node)),
j1))));
-
+
+ /* At this point, t = max (-i0/i1, -j0/j1) */
x0 = fold
(build (PLUS_EXPR, integer_type_node, i0,
fold (build
@@ -1134,9 +1054,9 @@ analyze_subscript_affine_affine (tree ch
(MULT_EXPR, integer_type_node, j1, t))));
*overlaps_a = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_b), x0, u21);
+ (CHREC_VARIABLE (chrec_b), x0, i1);
*overlaps_b = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_a), y0, u22);
+ (CHREC_VARIABLE (chrec_a), y0, j1);
}
else
{
@@ -1205,8 +1125,7 @@ analyze_siv_subscript (tree chrec_a,
overlaps_a, overlaps_b);
else if (evolution_function_is_affine_p (chrec_a)
- && evolution_function_is_affine_p (chrec_b)
- && (CHREC_VARIABLE (chrec_a) == CHREC_VARIABLE (chrec_b)))
+ && evolution_function_is_affine_p (chrec_b))
analyze_subscript_affine_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b);
else
@@ -1288,23 +1207,25 @@ analyze_miv_subscript (tree chrec_a,
*overlaps_b = chrec_known;
}
- else if (evolution_function_is_univariate_p (chrec_a)
- && evolution_function_is_univariate_p (chrec_b))
+ else if (evolution_function_is_affine_multivariate_p (chrec_a)
+ && evolution_function_is_affine_multivariate_p (chrec_b))
{
/* testsuite/.../ssa-chrec-35.c
{0, +, 1}_2 vs. {0, +, 1}_3
the overlapping elements are respectively located at iterations:
- {0, +, 1}_3 and {0, +, 1}_2.
+ {0, +, 1}_x and {0, +, 1}_x,
+ in other words, we have the equality:
+ {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
+
+ Other examples:
+ {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
+ {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
+
+ {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
+ {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
*/
- if (evolution_function_is_affine_p (chrec_a)
- && evolution_function_is_affine_p (chrec_b))
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b);
- else
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- }
+ analyze_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b);
}
else
@@ -1381,6 +1302,30 @@ analyze_overlapping_iterations (tree chr
/* This section contains the affine functions dependences detector. */
+/* Returns true when OVERLAPS contains undetermined description of
+ conflicting elements. */
+
+static bool
+undetermined_conflicts_p (tree overlaps)
+{
+ if (chrec_contains_undetermined (overlaps))
+ return true;
+ else
+ return false;
+}
+
+/* Returns true when OVERLAPS contains the information that there is
+ no conflicting elements. */
+
+static bool
+no_conflicts_p (tree overlaps)
+{
+ if (chrec_contains_undetermined (overlaps))
+ return true;
+ else
+ return false;
+}
+
/* Computes the conflicting iterations, and initialize DDR. */
static void
@@ -1402,15 +1347,15 @@ subscript_dependence_tester (struct data
DR_ACCESS_FN (drb, i),
&overlaps_a, &overlaps_b);
- if (chrec_contains_undetermined (overlaps_a)
- || chrec_contains_undetermined (overlaps_b))
+ if (undetermined_conflicts_p (overlaps_a)
+ || undetermined_conflicts_p (overlaps_b))
{
finalize_ddr_dependent (ddr, chrec_dont_know);
break;
}
- else if (overlaps_a == chrec_known
- || overlaps_b == chrec_known)
+ else if (no_conflicts_p (overlaps_a)
+ || no_conflicts_p (overlaps_b))
{
finalize_ddr_dependent (ddr, chrec_known);
break;
@@ -1453,7 +1398,10 @@ build_classic_dist_vector (struct data_d
struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
- return;
+ {
+ non_affine_dependence_relation (ddr);
+ return;
+ }
if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC)
{
@@ -1561,6 +1509,12 @@ build_classic_dir_vector (struct data_de
{
struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
+ if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ {
+ non_affine_dependence_relation (ddr);
+ return;
+ }
+
if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC
&& TREE_CODE (SUB_CONFLICTS_IN_B (subscript)) == POLYNOMIAL_CHREC)
{
@@ -1888,63 +1842,44 @@ analyze_all_data_dependences (struct loo
{
dump_data_dependence_relations (dump_file, dependence_relations);
fprintf (dump_file, "\n\n");
- }
- /* Don't dump distances in order to avoid to update the
- testsuite. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
- {
- struct data_dependence_relation *ddr =
- (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (dependence_relations, i);
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- {
- fprintf (dump_file, "DISTANCE_V (");
- print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), loops->num);
- fprintf (dump_file, ")\n");
- fprintf (dump_file, "DIRECTION_V (");
- print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), loops->num);
- fprintf (dump_file, ")\n");
- }
- }
- fprintf (dump_file, "\n\n");
- }
-
- if (dump_file && (dump_flags & TDF_STATS))
- {
- unsigned nb_top_relations = 0;
- unsigned nb_bot_relations = 0;
- unsigned nb_basename_differ = 0;
- unsigned nb_chrec_relations = 0;
+ if (dump_flags & TDF_DETAILS)
+ dump_dist_dir_vectors (dump_file, dependence_relations, loops->num);
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ if (dump_flags & TDF_STATS)
{
- struct data_dependence_relation *ddr;
- ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
+ unsigned nb_top_relations = 0;
+ unsigned nb_bot_relations = 0;
+ unsigned nb_basename_differ = 0;
+ unsigned nb_chrec_relations = 0;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ {
+ struct data_dependence_relation *ddr;
+ ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
- if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
- nb_top_relations++;
+ if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
+ nb_top_relations++;
- else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
- {
- struct data_reference *a = DDR_A (ddr);
- struct data_reference *b = DDR_B (ddr);
- bool differ_p;
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ {
+ struct data_reference *a = DDR_A (ddr);
+ struct data_reference *b = DDR_B (ddr);
+ bool differ_p;
- if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
- || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
- nb_basename_differ++;
- else
- nb_bot_relations++;
- }
+ if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
+ || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
+ nb_basename_differ++;
+ else
+ nb_bot_relations++;
+ }
- else
- nb_chrec_relations++;
- }
+ else
+ nb_chrec_relations++;
+ }
- gather_stats_on_scev_database ();
+ gather_stats_on_scev_database ();
+ }
}
free_dependence_relations (dependence_relations);
Index: tree-data-ref.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.h,v
retrieving revision 1.1.2.19
diff -d -u -p -r1.1.2.19 tree-data-ref.h
--- tree-data-ref.h 29 Jul 2004 22:54:22 -0000 1.1.2.19
+++ tree-data-ref.h 19 Aug 2004 20:45:18 -0000
@@ -106,6 +106,10 @@ struct data_dependence_relation
struct data_reference *a;
struct data_reference *b;
+ /* When the dependence relation is affine, it can be represented by
+ a distance vector. */
+ bool affine_p;
+
/* A "yes/no/maybe" field for the dependence relation:
- when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
@@ -133,6 +137,7 @@ struct data_dependence_relation
#define DDR_A(DDR) DDR->a
#define DDR_B(DDR) DDR->b
+#define DDR_AFFINE_P(DDR) DDR->affine_p
#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
#define DDR_SUBSCRIPTS(DDR) DDR->subscripts
#define DDR_SUBSCRIPTS_VECTOR_INIT(DDR, N) \
@@ -153,6 +158,8 @@ extern void compute_data_dependences_for
extern struct data_reference * init_data_ref (tree, tree, tree, tree, bool);
extern struct data_reference *analyze_array (tree, tree, bool);
+extern void dump_subscript (FILE *, struct subscript *);
+extern void dump_dist_dir_vectors (FILE *, varray_type, unsigned int);
extern void dump_data_reference (FILE *, struct data_reference *);
extern void dump_data_references (FILE *, varray_type);
extern void dump_data_dependence_relation (FILE *,
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-loop-linear.c,v
retrieving revision 1.1.2.12
diff -d -u -p -r1.1.2.12 tree-loop-linear.c
--- tree-loop-linear.c 29 Jul 2004 22:54:22 -0000 1.1.2.12
+++ tree-loop-linear.c 19 Aug 2004 20:45:18 -0000
@@ -220,26 +220,8 @@ linear_transform_loops (struct loops *lo
compute_data_dependences_for_loop (depth, loop_nest,
&datarefs, &dependence_relations);
if (dump_file && (dump_flags & TDF_DETAILS))
- {
- unsigned int j;
- for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
- {
- struct data_dependence_relation *ddr =
- (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (dependence_relations, j);
+ dump_dist_dir_vectors (dump_file, dependence_relations, loops->num);
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- {
- fprintf (dump_file, "DISTANCE_V (");
- print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), loops->num);
- fprintf (dump_file, ")\n");
- fprintf (dump_file, "DIRECTION_V (");
- print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), loops->num);
- fprintf (dump_file, ")\n");
- }
- }
- fprintf (dump_file, "\n\n");
- }
/* Build the transformation matrix. */
trans = lambda_trans_matrix_new (depth, depth);
#if 1
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.h,v
retrieving revision 1.1.2.16
diff -d -u -p -r1.1.2.16 tree-scalar-evolution.h
--- tree-scalar-evolution.h 12 Jul 2004 21:18:08 -0000 1.1.2.16
+++ tree-scalar-evolution.h 19 Aug 2004 20:45:18 -0000
@@ -22,6 +22,8 @@ Software Foundation, 59 Temple Place - S
#ifndef GCC_TREE_SCALAR_EVOLUTION_H
#define GCC_TREE_SCALAR_EVOLUTION_H
+#include "tree-chrec.h"
+
extern tree number_of_iterations_in_loop (struct loop *);
extern tree get_loop_exit_condition (struct loop *);
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.263.2.75.2.13
diff -d -u -p -r1.263.2.75.2.13 tree.c
--- tree.c 18 Jul 2004 23:13:39 -0000 1.263.2.75.2.13
+++ tree.c 19 Aug 2004 20:45:18 -0000
@@ -5807,7 +5807,6 @@ int_cst_value (tree x)
tree
tree_fold_gcd (tree a, tree b)
{
- tree a_mod_b;
tree type = TREE_TYPE (a);
#if defined ENABLE_CHECKING
@@ -5832,7 +5831,7 @@ tree_fold_gcd (tree a, tree b)
while (1)
{
- a_mod_b = fold (build (CEIL_MOD_EXPR, type, a, b));
+ tree a_mod_b = fold (build (TRUNC_MOD_EXPR, type, a, b));
if (!TREE_INT_CST_LOW (a_mod_b)
&& !TREE_INT_CST_HIGH (a_mod_b))