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] |

*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

* 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 }

- 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 }

- 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. + 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. + 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

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; - 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] |