This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[lno] Simple heuristics for loop interchange (call for twiddling)


Hi, 

In the distance vectors one finds the information about how often a
data reference is reused (how many iterations we have to wait until
the data referenced is used again).  This patch uses a very dumb
heuristic, maybe not very useful in the way it is in this patch, but
maybe with the help of experiments could be improved.  Basically the
function that computes the profitability is sum_distances_on_loop.
Using this function could be non profitable in some strange cases,
when some of the distances are huge, thus if somebody wants to play
with it and propose better heuristics, welcome!

Dan, could you verify that the comments that I've added or fixed are
correct?  Thanks.

Bootstrapped on i686-pc-linux-gnu with BOOT_CFLAGS="-O2 -g
-ftree-loop-linear".

Sebastian

	* lambda-code.c (lambda_transform_legal_p): Add more comments.
	* lambda-mat.c (lambda_matrix_col_add): Fix comment.
	(lambda_matrix_hermite): Add more comments.
	* tree-loop-linear.c (sum_distances_on_loop, 
	try_interchange_loops): New.
	(linear_transform_loops): Use try_interchange_loops.

Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-code.c,v
retrieving revision 1.1.2.14
diff -d -u -p -r1.1.2.14 lambda-code.c
--- lambda-code.c	6 Jul 2004 19:25:08 -0000	1.1.2.14
+++ lambda-code.c	24 Jul 2004 17:43:09 -0000
@@ -1947,7 +1947,17 @@ lambda_deps_positive (lambda_vector dir,
       
 	
 /* Return true if TRANS is a legal transformation matrix that respects
-   the dependence vectors in DISTS and DIRS.  */
+   the dependence vectors in DISTS and DIRS.  
+
+   "Wolfe proves that a unimodular transformation represented by the
+   matrix T is legal when applied to a loop nest with a set of
+   lexicographically non-negative distance vectors RDG if and only if
+   for each vector d in RDG, (T.d >= 0) is lexicographically positive.
+   ie.: if and only if it transforms the lexicographically positive
+   distance vectors to lexicographically positive vectors.  Note that
+   a unimodular matrix must transform the zero vector (and only it) to
+   the zero vector." S.Muchnick.  */
+
 bool
 lambda_transform_legal_p (lambda_trans_matrix trans, 
 			  int nb_loops,
Index: lambda-mat.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-mat.c,v
retrieving revision 1.1.2.3
diff -d -u -p -r1.1.2.3 lambda-mat.c
--- lambda-mat.c	28 Jun 2004 19:59:58 -0000	1.1.2.3
+++ lambda-mat.c	24 Jul 2004 17:43:09 -0000
@@ -232,7 +232,7 @@ lambda_matrix_col_exchange (lambda_matri
 }
 
 /* Add a multiple of column C1 of matrix MAT with M rows to column C2:
-   C2 = C1 + CONST1 * C2.  */
+   C2 = C2 + CONST1 * C1.  */
 
 void
 lambda_matrix_col_add (lambda_matrix mat, int m, int c1, int c2, int const1)
@@ -413,7 +413,7 @@ lambda_matrix_inverse_hard (lambda_matri
 }
 
 /* Decompose MAT to a product of a lower triangular H and a unimodular
-   U matrix.  */
+   U matrix such that MAT = H.U.  N is the size of the rows of MAT.  */
 
 void
 lambda_matrix_hermite (lambda_matrix mat, int n,
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-loop-linear.c,v
retrieving revision 1.1.2.8
diff -d -u -p -r1.1.2.8 tree-loop-linear.c
--- tree-loop-linear.c	28 Jun 2004 19:59:58 -0000	1.1.2.8
+++ tree-loop-linear.c	24 Jul 2004 17:43:12 -0000
@@ -55,6 +55,71 @@ Software Foundation, 59 Temple Place - S
    transform matrix for locality purposes.
    TODO: Completion of partial transforms.  */
 
+/* Returns the sum of all the data dependence distances carried by
+   loop COL.  */
+
+static int 
+sum_distances_on_loop (varray_type dists, 
+		       unsigned int loop_number)
+{
+  int res = 0;
+  unsigned int i;
+  
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (dists); i++)
+    {
+      lambda_vector distance = VARRAY_GENERIC_PTR (dists, i);
+      res += distance[loop_number];
+    }
+
+  return res;
+}
+
+/* Apply to TRANS any loop interchange that minimize inner loop steps.
+   Returns the new transform matrix.  The smaller the reuse vector
+   distances in the inner loops, the fewer the cache misses.  */
+
+static lambda_trans_matrix
+try_interchange_loops (lambda_trans_matrix trans, 
+		       unsigned int depth,		       
+		       varray_type classic_dir, 
+		       varray_type classic_dist)
+{
+  unsigned int loop_i, loop_j;
+  int sum_i, sum_j;
+
+  for (loop_i = 0; loop_i < depth; loop_i++)
+    for (loop_j = 0; loop_j < depth; loop_j++)
+      {
+	if (loop_i != loop_j)
+	  {
+	    /* Try to permute rows LOOP_I and LOOP_J.  The basic
+	       profitability model is the minimization of the steps in
+	       the inner loops.  */
+	    sum_i = sum_distances_on_loop (classic_dist, loop_i);
+	    sum_j = sum_distances_on_loop (classic_dist, loop_j);
+
+	    /* When LOOP_I contains smaller steps than LOOP_J, and
+	       LOOP_I is outer than LOOP_J, then interchange
+	       loops.  */
+	    if (sum_i < sum_j 
+		&& loop_i < loop_j)
+	      lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+	    
+	    /* Validate the resulting matrix.  When the transformation
+	       is not valid, reverse to the previous matrix.  
+	       
+	       FIXME: In this case of transformation it could be
+	       faster to verify the validity of the interchange
+	       without applying the transform to the matrix.  But for
+	       the moment do it cleanly: this is just a prototype.  */
+	    if (!lambda_transform_legal_p (trans, depth, classic_dir, classic_dist))
+	      lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+	  }
+      }
+  
+  return trans;
+}
+
 /* Perform a set of linear transforms on LOOPS.  */
 
 void
@@ -143,6 +208,7 @@ linear_transform_loops (struct loops *lo
       trans = lambda_trans_matrix_new (depth, depth);
 #if 1
       lambda_matrix_id (LTM_MATRIX (trans), depth);
+      trans = try_interchange_loops (trans, depth, classic_dir, classic_dist);
 #else
       /* This is a 2x2 interchange matrix.  */
       LTM_MATRIX (trans)[0][0] = 0;


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]