This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno][PATCH]: Cleanup and add legality testing to linear looptransformer
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: gcc-patches at gcc dot gnu dot org
- Cc: stevenb at suse dot de
- Date: Mon, 28 Jun 2004 14:22:06 -0400
- Subject: [lno][PATCH]: Cleanup and add legality testing to linear looptransformer
Now it can tell what transforms are legal.
Steven, if you could check the dot product code in lambda-code.c for me,
i'd appreciate it.
I know it produces the results i want for the loops i want, but that
tells me nothing from a math standpoint. :)
--Dan
2004-06-28 Daniel Berlin <dberlin@dberlin.org>
* lambda-code.c (print_linear_expression): Rename a few variables,
simplify some code.
(print_lambda_loop): Ditto.
(lambda_compute_auxillary_space): Update a comment.
(gcc_loop_to_lambda_loop): Update code for chrec_dont_know change.
(struct dir_dist_pair): New.
(reverse_dep): Ditto.
(lambda_dep_mult_constant): New function.
(lambda_dep_add): Ditto.
(lambda_vec_distdirvec_mult): Ditto.
(lambda_vec_distdirmat_mult): Ditto.
(lambda_deps_positive): Ditto.
(lambda_transform_legal_p): Ditto.
* lambda-mat.c (lambda_matrix_mult): Cleanup
(lambda_matrix_delete_rows): Ditto.
(lambda_matrix_row_add): Ditto.
(lambda_matrix_col_exchange): Ditto.
(lambda_trans_matrix_is_nonsingular): Rename to standard gcc predicate
naming.
(lambda_trans_matrix_is_fullrank): Ditto.
(lambda_trans_matrix_base): Rename to reflect actual computation.
* lambda.h (lambda_transform_legal_p): Add prototype.
* tree-loop-linear.c (linear_transform_loops): Rewrite a bit, use legality
tester to test transforms.
Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-code.c,v
retrieving revision 1.1.2.12
diff -u -3 -p -r1.1.2.12 lambda-code.c
--- lambda-code.c 22 Jun 2004 16:03:43 -0000 1.1.2.12
+++ lambda-code.c 28 Jun 2004 18:12:43 -0000
@@ -164,22 +164,22 @@ print_linear_expression (FILE *outfile,
char start)
{
int i;
- bool starting = true;
+ bool first = true;
for (i = 0; i < size; i++)
{
if (expr[i] != 0)
{
- if (starting)
+ if (first)
{
if (expr[i] < 0)
fprintf (outfile, "-");
- starting = false;
+ first = false;
}
else if (expr[i] > 0)
fprintf (outfile, " + ");
else
fprintf (outfile, " - ");
- if (expr[i] == 1 || expr [i] == -1)
+ if (abs(expr[i]) == 1)
fprintf (outfile, "%c", start + i);
else
fprintf (outfile, "%d%c", abs(expr[i]), start + i);
@@ -225,13 +225,11 @@ print_lambda_loop (FILE *outfile, lambda
}
fprintf (outfile, " lower bound: \n");
- expr = LL_LOWER_BOUND (loop);
- for (; expr != NULL; expr = LLE_NEXT (expr))
+ for (expr = LL_LOWER_BOUND (loop); expr != NULL; expr = LLE_NEXT (expr))
print_lambda_linear_expression (outfile, expr, depth, invariants,
start);
fprintf (outfile, " upper bound: \n");
- expr = LL_UPPER_BOUND (loop);
- for (; expr != NULL; expr = LLE_NEXT (expr))
+ for (expr = LL_UPPER_BOUND (loop); expr != NULL; expr = LLE_NEXT (expr))
print_lambda_linear_expression (outfile, expr, depth, invariants,
start);
@@ -299,7 +297,7 @@ lambda_lattice_compute_base (lambda_loop
depth = LN_DEPTH (nest);
invariants = LN_INVARIANTS (nest);
-
+
ret = lambda_lattice_new (depth, invariants);
base = LATTICE_BASE (ret);
for (i = 0; i < depth; i++)
@@ -501,7 +499,7 @@ lambda_compute_auxillary_space (lambda_l
/* Ax <= a + B becomes ALy <= a+B - A*origin. L is the lattice base */
- /* A1 = AL */
+ /* A1 = A * L */
lambda_matrix_mult (A, LATTICE_BASE (lattice), A1, size, depth, depth);
/* a1 = a - A * origin constant. */
@@ -1111,8 +1109,6 @@ gcc_loop_to_lambda_loop (struct loop *lo
return NULL;
}
-
-
test = TREE_OPERAND (exit_cond, 0);
if (TREE_CODE (test) != LE_EXPR
&& TREE_CODE (test) != LT_EXPR
@@ -1127,14 +1123,14 @@ gcc_loop_to_lambda_loop (struct loop *lo
}
return NULL;
}
-#if 0
+#if 0
ev = analyze_scalar_evolution (loop, inductionvar);
if (!evolution_function_is_affine_or_constant_p (ev))
return NULL;
nb_iter = number_of_iterations_in_loop (loop);
- if (chrec_contains_undetermined (nb_iter))
+ if (nb_iter == chrec_dont_know)
return NULL;
nb_iter = chrec_fold_minus (chrec_type (nb_iter), nb_iter,
convert (chrec_type (nb_iter), integer_one_node));
@@ -1194,7 +1190,7 @@ gcc_loop_to_lambda_loop (struct loop *lo
}
step = evolution_part_in_loop_num (access_fn, loop_num (loop));
- if (!step)
+ if (!step || step == chrec_dont_know)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Unable to convert loop: Cannot determine step of loop.\n");
@@ -1765,3 +1761,212 @@ lambda_loopnest_to_gcc_loopnest (struct
}
}
+/* A data dependence direction and distance pair. */
+
+typedef struct dir_dist_pair
+{
+ enum data_dependence_direction dir;
+ int dist;
+} dd_pair;
+
+/* If a dependence direction is reversed, reverse_dep[old_direction]
+ gives the new direction. MUST BE KEPT IN SYNC WITH enum
+ data_dependence_dir.
+*/
+static const enum data_dependence_direction reverse_dep[] =
+ {
+ dir_negative,
+ dir_positive,
+ dir_equal,
+ dir_positive_or_negative,
+ dir_negative_or_equal,
+ dir_positive_or_equal,
+ dir_star,
+ dir_independent
+ };
+
+/* Multiply a dependence pair DEP by CONSTANT, return the new
+ dependence pair. */
+
+static dd_pair
+lambda_dep_mult_constant (dd_pair dep, int constant)
+{
+ dd_pair ret;
+ ret.dist = dep.dist * constant;
+
+ /* If the distance is now 0, the direction is now equal.
+ Otherwise, the direction only changes if the constant is < 0. */
+
+ if (ret.dist == 0)
+ {
+ ret.dir = dir_equal;
+ }
+ else if (constant < 0)
+ {
+ ret.dir = reverse_dep[dep.dir];
+ }
+ else
+ {
+ ret.dir = dep.dir;
+ }
+ return ret;
+}
+
+/* Add two dependence pairs, FIRST and SECOND, and return the new
+ dependence pair. */
+static dd_pair
+lambda_dep_add (dd_pair first, dd_pair second)
+{
+ dd_pair ret;
+ ret.dist = first.dist + second.dist;
+ switch (first.dir)
+ {
+ case dir_equal:
+ {
+ ret.dir = second.dir;
+ ret.dist = second.dist;
+ break;
+ }
+ case dir_positive_or_equal:
+ case dir_positive:
+ {
+ switch (second.dir)
+ {
+ case dir_negative:
+ case dir_negative_or_equal:
+ case dir_star:
+ ret.dir = dir_star;
+ ret.dist = 0;
+ break;
+ default:
+ ret.dir = first.dir;
+ break;
+ }
+ break;
+ }
+ case dir_negative_or_equal:
+ case dir_negative:
+ {
+ switch (second.dir)
+ {
+ case dir_positive:
+ case dir_positive_or_equal:
+ case dir_star:
+ ret.dir = dir_star;
+ ret.dist = 0;
+ break;
+ default:
+ ret.dir = first.dir;
+ break;
+ }
+ break;
+ }
+ case dir_star:
+ {
+ ret.dir = dir_star;
+ ret.dist = 0;
+ break;
+ }
+ default:
+ abort ();
+ }
+ return ret;
+}
+/* Compute the dot product of an integer vector VECTOR,
+ a vector containing dependence distance DISTANCE, and a vector containing
+ dependence direction DIRECTION. All vectors are of dimension SIZE.
+ Return the resulting distance/direction pair. */
+
+static dd_pair
+lambda_vec_distdirvec_mult (lambda_vector vector,
+ lambda_vector distance,
+ lambda_vector direction,
+ int size)
+{
+ int i;
+ dd_pair ret;
+ ret.dir = dir_equal;
+ ret.dist = 0;
+ for (i = 0; i < size; i++)
+ {
+ dd_pair elem;
+ elem.dist = distance[i];
+ elem.dir = direction[i];
+ elem = lambda_dep_mult_constant (elem, vector[i]);
+ ret = lambda_dep_add (ret, elem);
+ }
+ return ret;
+}
+
+/* Compute the dot product of an integer vector VECTOR, and a
+ dependence matrix represented by varrays of distance and direction
+ vectors, DISTS and DIRS.
+ All vectors are of dimension DIM. */
+
+static void
+lambda_vec_distdirmat_mult (lambda_vector vector,
+ int dim,
+ varray_type dirs,
+ varray_type dists,
+ lambda_vector dirres,
+ lambda_vector distres)
+{
+ size_t i;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dists); i++)
+ {
+ dd_pair result;
+ lambda_vector distance = VARRAY_GENERIC_PTR (dists, i);
+ lambda_vector direction = VARRAY_GENERIC_PTR (dirs, i);
+ result = lambda_vec_distdirvec_mult (vector, distance, direction, dim);
+ distres[i] = result.dist;
+ dirres[i] = result.dir;
+ }
+
+}
+
+/* Return true if the direction vector DIR is all positive or equal
+ elements. */
+static bool
+lambda_deps_positive (lambda_vector dir, int dirsize)
+{
+ int i;
+ for (i = 0; i < dirsize; i++)
+ {
+ switch (dir[i])
+ {
+ case dir_negative:
+ case dir_negative_or_equal:
+ case dir_star:
+ return false;
+ break;
+ }
+ }
+ return true;
+}
+
+
+
+/* Return true if TRANS is a legal transformation matrix that respects
+ the dependence vectors in DISTS and DIRS. */
+bool
+lambda_transform_legal_p (lambda_trans_matrix trans,
+ int nb_loops,
+ varray_type dirs,
+ varray_type dists)
+{
+ int i;
+ int distsize = VARRAY_ACTIVE_SIZE (dists);
+ int dirsize = VARRAY_ACTIVE_SIZE (dirs);
+ lambda_vector distres;
+ lambda_vector dirres;
+ distres = lambda_vector_new (distsize);
+ dirres = lambda_vector_new (dirsize);
+ for (i = 0; i < LTM_ROWSIZE (trans); i++)
+ {
+ lambda_vec_distdirmat_mult (LTM_MATRIX (trans)[i], nb_loops,
+ dirs, dists, dirres, distres);
+ if (!lambda_deps_positive (dirres, dirsize))
+ return false;
+ }
+ return true;
+}
Index: lambda-mat.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-mat.c,v
retrieving revision 1.1.2.2
diff -u -3 -p -r1.1.2.2 lambda-mat.c
--- lambda-mat.c 23 Mar 2004 20:13:27 -0000 1.1.2.2
+++ lambda-mat.c 28 Jun 2004 18:12:43 -0000
@@ -129,17 +129,14 @@ lambda_matrix_mult (lambda_matrix mat1,
{
int i, j, k;
- lambda_vector row1, row3;
for (i = 0; i < m; i++)
{
- row3 = mat3[i];
for (j = 0; j < n; j++)
{
- row1 = mat1[i];
- row3[j] = 0;
+ mat3[i][j] = 0;
for (k = 0; k < r; k++)
- row3[j] += row1[k] * mat2[k][j];
+ mat3[i][j] += mat1[i][k] * mat2[k][j];
}
}
}
@@ -157,18 +154,19 @@ lambda_matrix_get_column (lambda_matrix
vec[i] = mat[i][col];
}
-/* Delete rows r1 to r2 (not including r2). TODO */
+/* Delete rows r1 to r2 (not including r2). */
void
lambda_matrix_delete_rows (lambda_matrix mat, int rows, int from, int to)
{
- int i, d;
- d = to - from;
+ int i;
+ int dist;
+ dist = to - from;
for (i = to; i < rows; i++)
- mat[i - d] = mat[i];
+ mat[i - dist] = mat[i];
- for (i = rows - d; i < rows; i++)
+ for (i = rows - dist; i < rows; i++)
mat[i] = NULL;
}
@@ -191,16 +189,12 @@ void
lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1)
{
int i;
- lambda_vector row1, row2;
if (const1 == 0)
return;
- row1 = mat[r1];
- row2 = mat[r2];
-
for (i = 0; i < n; i++)
- row2[i] += const1 * row1[i];
+ mat[r2][i] += const1 * mat[r1][i];
}
/* Negate row R1 of matrix MAT which has N columns. */
@@ -227,15 +221,13 @@ lambda_matrix_row_mc (lambda_matrix mat,
void
lambda_matrix_col_exchange (lambda_matrix mat, int m, int col1, int col2)
{
- lambda_vector row;
int i;
int tmp;
for (i = 0; i < m; i++)
{
- row = mat[i];
- tmp = row[col1];
- row[col1] = row[col2];
- row[col2] = tmp;
+ tmp = mat[i][col1];
+ mat[i][col1] = mat[i][col2];
+ mat[i][col2] = tmp;
}
}
@@ -420,7 +412,7 @@ lambda_matrix_inverse_hard (lambda_matri
return determinant;
}
-/* Decompose mat to a product of a lower triangular H and a unimodular
+/* Decompose MAT to a product of a lower triangular H and a unimodular
U matrix. */
void
Index: lambda-trans.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-trans.c,v
retrieving revision 1.1.2.2
diff -u -3 -p -r1.1.2.2 lambda-trans.c
--- lambda-trans.c 29 May 2004 22:09:02 -0000 1.1.2.2
+++ lambda-trans.c 28 Jun 2004 18:12:43 -0000
@@ -28,16 +28,16 @@ lambda_trans_matrix_new (int colsize, in
/* Return true if the transformation matrix is nonsingular. */
bool
-lambda_trans_matrix_is_nonsingular (lambda_trans_matrix t)
+lambda_trans_matrix_nonsingular_p (lambda_trans_matrix t)
{
- return lambda_trans_matrix_is_fullrank (t);
+ return lambda_trans_matrix_fullrank_p (t);
}
/* Return true if the transformation matrix is full row rank. */
bool
-lambda_trans_matrix_is_fullrank (lambda_trans_matrix t)
+lambda_trans_matrix_fullrank_p (lambda_trans_matrix t)
{
return (lambda_trans_matrix_rank (t) == LTM_ROWSIZE (t));
}
@@ -118,10 +118,10 @@ lambda_trans_matrix_rank (lambda_trans_m
}
-/* Compute the base matrix. */
+/* Compute the basis matrix. */
lambda_trans_matrix
-lambda_trans_matrix_base (lambda_trans_matrix mat)
+lambda_trans_matrix_basis (lambda_trans_matrix mat)
{
int rowsize, colsize;
int i, j, nextrow;
@@ -129,12 +129,12 @@ lambda_trans_matrix_base (lambda_trans_m
lambda_vector row;
int minimum_column, factor;
- lambda_trans_matrix base;
+ lambda_trans_matrix basis;
rowsize = LTM_ROWSIZE (mat);
colsize = LTM_COLSIZE (mat);
- base = lambda_trans_matrix_new (rowsize, colsize);
- partial = LTM_MATRIX (base);
+ basis = lambda_trans_matrix_new (rowsize, colsize);
+ partial = LTM_MATRIX (basis);
lambda_matrix_copy (LTM_MATRIX (mat), partial, rowsize, colsize);
tempmatrix = lambda_matrix_new (rowsize, colsize);
lambda_matrix_copy (partial, tempmatrix, rowsize, colsize);
@@ -186,8 +186,8 @@ lambda_trans_matrix_base (lambda_trans_m
j++;
}
/* Store the rank. */
- LTM_ROWSIZE (base) = j;
- return base;
+ LTM_ROWSIZE (basis) = j;
+ return basis;
}
/* Pad the legal base matrix to an invertible matrix. */
Index: lambda.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda.h,v
retrieving revision 1.1.2.2
diff -u -3 -p -r1.1.2.2 lambda.h
--- lambda.h 23 Apr 2004 19:12:28 -0000 1.1.2.2
+++ lambda.h 28 Jun 2004 18:12:43 -0000
@@ -76,6 +76,7 @@ typedef struct
lambda_loopnest lambda_loopnest_new (int, int);
lambda_loopnest lambda_loopnest_transform (lambda_loopnest, lambda_trans_matrix);
+bool lambda_transform_legal_p (lambda_trans_matrix, int, varray_type, varray_type);
void print_lambda_loopnest (FILE *, lambda_loopnest, char);
#define lambda_loop_new() (lambda_loop) ggc_alloc_cleared (sizeof (struct lambda_loop_s))
@@ -113,10 +114,10 @@ void lambda_matrix_project_to_null (lamb
void print_lambda_matrix (FILE *, lambda_matrix, int, int);
lambda_trans_matrix lambda_trans_matrix_new (int, int);
-bool lambda_trans_matrix_is_nonsingular (lambda_trans_matrix);
-bool lambda_trans_matrix_is_fullrank (lambda_trans_matrix);
+bool lambda_trans_matrix_nonsingular_p (lambda_trans_matrix);
+bool lambda_trans_matrix_fullrank_p (lambda_trans_matrix);
int lambda_trans_matrix_rank (lambda_trans_matrix);
-lambda_trans_matrix lambda_trans_matrix_base (lambda_trans_matrix);
+lambda_trans_matrix lambda_trans_matrix_basis (lambda_trans_matrix);
lambda_trans_matrix lambda_trans_matrix_padding (lambda_trans_matrix);
lambda_trans_matrix lambda_trans_matrix_inverse (lambda_trans_matrix);
void print_lambda_trans_matrix (FILE *, lambda_trans_matrix);
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-loop-linear.c,v
retrieving revision 1.1.2.7
diff -u -3 -p -r1.1.2.7 tree-loop-linear.c
--- tree-loop-linear.c 22 Jun 2004 16:03:44 -0000 1.1.2.7
+++ tree-loop-linear.c 28 Jun 2004 18:12:44 -0000
@@ -53,9 +53,6 @@ Software Foundation, 59 Temple Place - S
TODO: Determine reuse vectors/matrix and use it to determine optimal
transform matrix for locality purposes.
- TODO: Add dependence matrix collection and appropriate matrix
- calculations so we can determine if a given transformation matrix
- is legal for a loop.
TODO: Completion of partial transforms. */
/* Perform a set of linear transforms on LOOPS. */
@@ -64,48 +61,88 @@ void
linear_transform_loops (struct loops *loops)
{
unsigned int i;
+ unsigned int depth = 0;
+ unsigned int j;
+ varray_type classic_dist;
+ varray_type classic_dir;
+ varray_type datarefs;
+ varray_type dependence_relations;
+
for (i = 1; i < loops->num; i++)
{
struct loop *loop_nest = loops->parray[i];
+ struct loop *temp;
varray_type oldivs;
varray_type invariants;
lambda_loopnest before, after;
lambda_trans_matrix trans;
-
+ bool problem = false;
/* If it's not a loop nest, we don't want it.
We also don't handle sibling loops properly,
which are loops of the following form:
- like
- for (i = 0; i < 50; i++)_
+ for (i = 0; i < 50; i++)
{
for (j = 0; j < 50; j++)
{
- ...
+ ...
}
for (j = 0; j < 50; j++)
{
...
}
} */
- if (!loop_nest->inner || loop_nest->inner->next != NULL )
+ if (!loop_nest->inner)
continue;
- flow_loop_scan (loop_nest, LOOP_ALL);
- flow_loop_scan (loop_nest->inner, LOOP_ALL);
- /* We also don't handle loops with multiple exit edges. */
- if (loop_nest->num_exits != 1
- || loop_nest->inner->num_exits != 1)
- continue;
- before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs, &invariants);
- if (!before)
+ for (temp = loop_nest; temp; temp = temp->inner)
+ {
+ flow_loop_scan (temp, LOOP_ALL);
+ /* If we have a sibling loop or multiple exit edges, jump ship. */
+ if (temp->next || temp->num_exits != 1)
+ {
+ problem = true;
+ break;
+ }
+ depth ++;
+ }
+ if (problem)
continue;
- if (dump_file)
+
+ /* Analyze data references and dependence relations using scev. */
+
+ VARRAY_GENERIC_PTR_INIT (classic_dist, 10, "classic_dist");
+ VARRAY_GENERIC_PTR_INIT (classic_dir, 10, "classic_dir");
+ VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
+ VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
+ "dependence_relations");
+
+
+ compute_data_dependences_for_loop (depth, loop_nest,
+ &datarefs, &dependence_relations,
+ &classic_dist, &classic_dir);
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "Before:\n");
- print_lambda_loopnest (dump_file, before, 'i');
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (classic_dist); j++)
+ {
+ fprintf (dump_file, "DISTANCE_V (");
+ print_lambda_vector (dump_file,
+ VARRAY_GENERIC_PTR (classic_dist, j),
+ depth);
+ fprintf (dump_file, ")\n");
+ }
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (classic_dir); j++)
+ {
+ fprintf (dump_file, "DIRECTION_V (");
+ print_lambda_vector (dump_file,
+ VARRAY_GENERIC_PTR (classic_dir, j),
+ depth);
+ fprintf (dump_file, ")\n");
+ }
+ fprintf (dump_file, "\n\n");
}
- trans = lambda_trans_matrix_new (LN_DEPTH (before), LN_DEPTH (before));
+ /* Build the transformation matrix. */
+ trans = lambda_trans_matrix_new (depth, depth);
#if 1
- lambda_matrix_id (LTM_MATRIX (trans), LN_DEPTH (before));
+ lambda_matrix_id (LTM_MATRIX (trans), depth);
#else
/* This is a 2x2 interchange matrix. */
LTM_MATRIX (trans)[0][0] = 0;
@@ -113,6 +150,23 @@ linear_transform_loops (struct loops *lo
LTM_MATRIX (trans)[1][0] = 1;
LTM_MATRIX (trans)[1][1] = 0;
#endif
+ /* Check whether the transformation is legal. */
+ if (!lambda_transform_legal_p (trans, depth, classic_dir, classic_dist))
+ {
+ if (dump_file)
+ fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
+ continue;
+ }
+ before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs, &invariants);
+ if (!before)
+ continue;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Before:\n");
+ print_lambda_loopnest (dump_file, before, 'i');
+ }
+
after = lambda_loopnest_transform (before, trans);
if (dump_file)
{