This is the mail archive of the 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]

[PATCH]: Update some comments in lambda.h, lambda-code.c, andtree-loop-linear.c

This patch adds some more comments to the lambda stuff and removes a bit of pointless code in tree-loop-linear.c (there was some *x += 0 in there :P).

I'll wait a few hours before committing this in case anyone wants to nitpick my grammar or anything :)

Bootstrapped and regtested on i686-pc-linux-gnu.

2004-11-02 Daniel Berlin <>

	* lambda-code.c (lambda_compute_auxillary_space): Update comments.
	(lambda_compute_target_space). Ditto.
	* lambda.h (lambda_trans_matrix): Ditto.
	(lambda_linear_expression): Ditto.
	(lambda_body_vector): Ditto.
	(lambda_loopnest): Ditto.
	* tree-loop-linear.c (gather_interchange_stats): Combine tests,
	update comments, and remove pointless addition of 0.
	(linear_transform_loops): Update comments.
Index: lambda-code.c
RCS file: /cvs/gcc/gcc/gcc/lambda-code.c,v
retrieving revision 2.17
diff -u -p -r2.17 lambda-code.c
--- lambda-code.c	1 Nov 2004 18:07:59 -0000	2.17
+++ lambda-code.c	2 Nov 2004 19:47:53 -0000
@@ -651,7 +651,19 @@ compute_nest_using_fourier_motzkin (int

/* Compute the loop bounds for the auxiliary space NEST.
- Input system used is Ax <= b. TRANS is the unimodular transformation. */
+ Input system used is Ax <= b. TRANS is the unimodular transformation. + Given the original nest, this function will + 1. Convert the nest into matrix form, which consists of a matrix for the
+ coefficients, a matrix for the + invariant coefficients, and a vector for the constants. + 2. Use the matrix form to calculate the lattice base for the nest (which is
+ a dense space) + 3. Compose the dense space transform with the user specified transform, to + get a transform we can easily calculate transformed bounds for.
+ 4. Multiply the composed transformation matrix times the matrix form of the
+ loop.
+ 5. Transform the newly created matrix (from step 4) back into a loop nest
+ using fourier motzkin elimination to figure out the bounds. */

 static lambda_loopnest
 lambda_compute_auxillary_space (lambda_loopnest nest,
@@ -786,9 +798,11 @@ lambda_compute_auxillary_space (lambda_l

/* Compute the loop bounds for the target space, using the bounds of
- the auxiliary nest AUXILLARY_NEST, and the triangular matrix H. This is
- done by matrix multiplication and then transformation of the new matrix
- back into linear expression form.
+ the auxiliary nest AUXILLARY_NEST, and the triangular matrix H. + The target space loop bounds are computed by multiplying the triangular
+ matrix H by the auxillary nest, to get the new loop bounds. The sign of
+ the loop steps (positive or negative) is then used to swap the bounds if
+ the loop counts downwards.
Return the target loopnest. */

 static lambda_loopnest
Index: lambda.h
RCS file: /cvs/gcc/gcc/gcc/lambda.h,v
retrieving revision 2.7
diff -u -p -r2.7 lambda.h
--- lambda.h	16 Sep 2004 16:16:14 -0000	2.7
+++ lambda.h	2 Nov 2004 19:47:53 -0000
@@ -29,11 +29,14 @@ Software Foundation, 59 Temple Place - S
    and scalar multiplication.  In this vector space, an element is a list of
    integers.  */
 typedef int *lambda_vector;
 /* An integer matrix.  A matrix consists of m vectors of length n (IE
    all vectors are the same length).  */
 typedef lambda_vector *lambda_matrix;

-/* A transformation matrix.  */
+/* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
+   matrix.  Rather than use floats, we simply keep a single DENOMINATOR that
+   represents the denominator for every element in the matrix.  */
 typedef struct
   lambda_matrix matrix;
@@ -46,7 +49,15 @@ typedef struct
 #define LTM_COLSIZE(T) ((T)->colsize)
 #define LTM_DENOMINATOR(T) ((T)->denominator)

-/* A vector representing a statement in the body of a loop.  */
+/* A vector representing a statement in the body of a loop.
+   The COEFFICIENTS vector contains a coefficient for each induction variable
+   in the loop nest containing the statement.
+   The DENOMINATOR represents the denominator for each coefficient in the
+   COEFFICIENT vector.
+   This structure is used during code generation in order to rewrite the old
+   induction variable uses in a statement in terms of the newly created
+   induction variables.  */
 typedef struct
   lambda_vector coefficients;
@@ -57,7 +68,18 @@ typedef struct
 #define LBV_SIZE(T) ((T)->size)
 #define LBV_DENOMINATOR(T) ((T)->denominator)

-/* Piecewise linear expression. */
+/* Piecewise linear expression. + This structure represents a linear expression with terms for the invariants
+ and induction variables of a loop. + COEFFICIENTS is a vector of coefficients for the induction variables, one
+ per loop in the loop nest.
+ CONSTANT is the constant portion of the linear expression
+ INVARIANT_COEFFICIENTS is a vector of coefficients for the loop invariants,
+ one per invariant.
+ DENOMINATOR is the denominator for all of the coefficients and constants in
+ the expression. + The linear expressions can be linked together using the NEXT field, in
+ order to represent MAX or MIN of a group of linear expressions. */
typedef struct lambda_linear_expression_s
lambda_vector coefficients;
@@ -77,7 +99,12 @@ lambda_linear_expression lambda_linear_e
void print_lambda_linear_expression (FILE *, lambda_linear_expression, int,
int, char);

-/* Loop structure.  */
+/* Loop structure.  Our loop structure consists of a constant representing the
+   STEP of the loop, a set of linear expressions representing the LOWER_BOUND
+   of the loop, a set of linear expressions representing the UPPER_BOUND of
+   the loop, and a set of linear expressions representing the LINEAR_OFFSET of
+   the loop.  The linear offset is a set of linear expressions that are
+   applied to *both* the lower bound, and the upper bound.  */
 typedef struct lambda_loop_s
   lambda_linear_expression lower_bound;
@@ -91,7 +118,12 @@ typedef struct lambda_loop_s
 #define LL_LINEAR_OFFSET(T) ((T)->linear_offset)
 #define LL_STEP(T)   ((T)->step)

-/* Loop nest structure. */
+/* Loop nest structure. + The loop nest structure consists of a set of loop structures (defined
+ above) in LOOPS, along with an integer representing the DEPTH of the loop,
+ and an integer representing the number of INVARIANTS in the loop. Both of
+ these integers are used to size the associated coefficient vectors in the
+ linear expression structures. */
typedef struct
lambda_loop *loops;
Index: tree-loop-linear.c
RCS file: /cvs/gcc/gcc/gcc/tree-loop-linear.c,v
retrieving revision 2.3
diff -u -p -r2.3 tree-loop-linear.c
--- tree-loop-linear.c 1 Nov 2004 18:08:00 -0000 2.3
+++ tree-loop-linear.c 2 Nov 2004 19:47:53 -0000
@@ -88,7 +88,7 @@ Software Foundation, 59 Temple Place - S
- */

static void
gather_interchange_stats (varray_type dependence_relations, @@ -112,21 +112,17 @@ gather_interchange_stats (varray_type de
(struct data_dependence_relation *)
VARRAY_GENERIC_PTR (dependence_relations, i);

-      /* Compute the dependence strides.  */
-      if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
-	{
-	  (*dependence_steps) += 0;
-	  continue;
-	}
+      /* If we don't know anything about this dependence, or the distance
+	 vector is NULL, or there is no dependence, then there is no reuse of
+	 data.  */
+      if (DDR_DIST_VECT (ddr) == NULL
+	  || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
+	  || DDR_ARE_DEPENDENT (ddr) == chrec_known)
+	continue;

-      /* When we know that there is no dependence, we know that there
-	 is no reuse of the data.  */
-      if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
-	{
-	  (*dependence_steps) += 0;
-	  continue;
-	}
       dist = DDR_DIST_VECT (ddr)[loop_number];
       if (dist == 0)
 	(*nb_deps_not_carried_by_loop) += 1;
@@ -164,7 +160,8 @@ gather_interchange_stats (varray_type de

-/* Apply to TRANS any loop interchange that minimize inner loop steps.
+/* Attempt to apply interchange transformations to TRANS to maximize the
+   spatial and temporal locality of the loop.
    Returns the new transform matrix.  The smaller the reuse vector
    distances in the inner loops, the fewer the cache misses.
    FIRST_LOOP is the loop->num of the first loop in the analyzed loop

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