This is the mail archive of the
mailing list for the GCC project.
[PATCH]: Update some comments in lambda.h, lambda-code.c, andtree-loop-linear.c
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 2 Nov 2004 14:56:54 -0500 (EST)
- Subject: [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
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 <firstname.lastname@example.org>
* lambda-code.c (lambda_compute_auxillary_space): Update comments.
* lambda.h (lambda_trans_matrix): Ditto.
* tree-loop-linear.c (gather_interchange_stats): Combine tests,
update comments, and remove pointless addition of 0.
(linear_transform_loops): Update comments.
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
+ 5. Transform the newly created matrix (from step 4) back into a loop nest
+ using fourier motzkin elimination to figure out the bounds. */
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. */
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
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. */
@@ -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. */
@@ -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
@@ -77,7 +99,12 @@ lambda_linear_expression lambda_linear_e
void print_lambda_linear_expression (FILE *, lambda_linear_expression, int,
-/* 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
@@ -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. */
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
DEPENDENCE_STEPS = 3000
NB_DEPS_NOT_CARRIED_BY_LOOP = 7
ACCESS_STRIDES = 8010
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;
+ /* 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)
- /* 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;
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