OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [lambda.h] - Blame information for rev 841

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Lambda matrix and vector interface.
2
   Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3
   Contributed by Daniel Berlin <dberlin@dberlin.org>
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#ifndef LAMBDA_H
22
#define LAMBDA_H
23
 
24
#include "vec.h"
25
 
26
/* An integer vector.  A vector formally consists of an element of a vector
27
   space. A vector space is a set that is closed under vector addition
28
   and scalar multiplication.  In this vector space, an element is a list of
29
   integers.  */
30
typedef int *lambda_vector;
31
 
32
DEF_VEC_P(lambda_vector);
33
DEF_VEC_ALLOC_P(lambda_vector,heap);
34
 
35
/* An integer matrix.  A matrix consists of m vectors of length n (IE
36
   all vectors are the same length).  */
37
typedef lambda_vector *lambda_matrix;
38
 
39
/* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
40
   matrix.  Rather than use floats, we simply keep a single DENOMINATOR that
41
   represents the denominator for every element in the matrix.  */
42
typedef struct
43
{
44
  lambda_matrix matrix;
45
  int rowsize;
46
  int colsize;
47
  int denominator;
48
} *lambda_trans_matrix;
49
#define LTM_MATRIX(T) ((T)->matrix)
50
#define LTM_ROWSIZE(T) ((T)->rowsize)
51
#define LTM_COLSIZE(T) ((T)->colsize)
52
#define LTM_DENOMINATOR(T) ((T)->denominator)
53
 
54
/* A vector representing a statement in the body of a loop.
55
   The COEFFICIENTS vector contains a coefficient for each induction variable
56
   in the loop nest containing the statement.
57
   The DENOMINATOR represents the denominator for each coefficient in the
58
   COEFFICIENT vector.
59
 
60
   This structure is used during code generation in order to rewrite the old
61
   induction variable uses in a statement in terms of the newly created
62
   induction variables.  */
63
typedef struct
64
{
65
  lambda_vector coefficients;
66
  int size;
67
  int denominator;
68
} *lambda_body_vector;
69
#define LBV_COEFFICIENTS(T) ((T)->coefficients)
70
#define LBV_SIZE(T) ((T)->size)
71
#define LBV_DENOMINATOR(T) ((T)->denominator)
72
 
73
/* Piecewise linear expression.
74
   This structure represents a linear expression with terms for the invariants
75
   and induction variables of a loop.
76
   COEFFICIENTS is a vector of coefficients for the induction variables, one
77
   per loop in the loop nest.
78
   CONSTANT is the constant portion of the linear expression
79
   INVARIANT_COEFFICIENTS is a vector of coefficients for the loop invariants,
80
   one per invariant.
81
   DENOMINATOR is the denominator for all of the coefficients and constants in
82
   the expression.
83
   The linear expressions can be linked together using the NEXT field, in
84
   order to represent MAX or MIN of a group of linear expressions.  */
85
typedef struct lambda_linear_expression_s
86
{
87
  lambda_vector coefficients;
88
  int constant;
89
  lambda_vector invariant_coefficients;
90
  int denominator;
91
  struct lambda_linear_expression_s *next;
92
} *lambda_linear_expression;
93
 
94
#define LLE_COEFFICIENTS(T) ((T)->coefficients)
95
#define LLE_CONSTANT(T) ((T)->constant)
96
#define LLE_INVARIANT_COEFFICIENTS(T) ((T)->invariant_coefficients)
97
#define LLE_DENOMINATOR(T) ((T)->denominator)
98
#define LLE_NEXT(T) ((T)->next)
99
 
100
lambda_linear_expression lambda_linear_expression_new (int, int);
101
void print_lambda_linear_expression (FILE *, lambda_linear_expression, int,
102
                                     int, char);
103
 
104
/* Loop structure.  Our loop structure consists of a constant representing the
105
   STEP of the loop, a set of linear expressions representing the LOWER_BOUND
106
   of the loop, a set of linear expressions representing the UPPER_BOUND of
107
   the loop, and a set of linear expressions representing the LINEAR_OFFSET of
108
   the loop.  The linear offset is a set of linear expressions that are
109
   applied to *both* the lower bound, and the upper bound.  */
110
typedef struct lambda_loop_s
111
{
112
  lambda_linear_expression lower_bound;
113
  lambda_linear_expression upper_bound;
114
  lambda_linear_expression linear_offset;
115
  int step;
116
} *lambda_loop;
117
 
118
#define LL_LOWER_BOUND(T) ((T)->lower_bound)
119
#define LL_UPPER_BOUND(T) ((T)->upper_bound)
120
#define LL_LINEAR_OFFSET(T) ((T)->linear_offset)
121
#define LL_STEP(T)   ((T)->step)
122
 
123
/* Loop nest structure.
124
   The loop nest structure consists of a set of loop structures (defined
125
   above) in LOOPS, along with an integer representing the DEPTH of the loop,
126
   and an integer representing the number of INVARIANTS in the loop.  Both of
127
   these integers are used to size the associated coefficient vectors in the
128
   linear expression structures.  */
129
typedef struct
130
{
131
  lambda_loop *loops;
132
  int depth;
133
  int invariants;
134
} *lambda_loopnest;
135
 
136
#define LN_LOOPS(T) ((T)->loops)
137
#define LN_DEPTH(T) ((T)->depth)
138
#define LN_INVARIANTS(T) ((T)->invariants)
139
 
140
lambda_loopnest lambda_loopnest_new (int, int);
141
lambda_loopnest lambda_loopnest_transform (lambda_loopnest, lambda_trans_matrix);
142
struct loop;
143
struct loops;
144
bool perfect_nest_p (struct loop *);
145
void print_lambda_loopnest (FILE *, lambda_loopnest, char);
146
 
147
#define lambda_loop_new() (lambda_loop) ggc_alloc_cleared (sizeof (struct lambda_loop_s))
148
 
149
void print_lambda_loop (FILE *, lambda_loop, int, int, char);
150
 
151
lambda_matrix lambda_matrix_new (int, int);
152
 
153
void lambda_matrix_id (lambda_matrix, int);
154
bool lambda_matrix_id_p (lambda_matrix, int);
155
void lambda_matrix_copy (lambda_matrix, lambda_matrix, int, int);
156
void lambda_matrix_negate (lambda_matrix, lambda_matrix, int, int);
157
void lambda_matrix_transpose (lambda_matrix, lambda_matrix, int, int);
158
void lambda_matrix_add (lambda_matrix, lambda_matrix, lambda_matrix, int,
159
                        int);
160
void lambda_matrix_add_mc (lambda_matrix, int, lambda_matrix, int,
161
                           lambda_matrix, int, int);
162
void lambda_matrix_mult (lambda_matrix, lambda_matrix, lambda_matrix,
163
                         int, int, int);
164
void lambda_matrix_delete_rows (lambda_matrix, int, int, int);
165
void lambda_matrix_row_exchange (lambda_matrix, int, int);
166
void lambda_matrix_row_add (lambda_matrix, int, int, int, int);
167
void lambda_matrix_row_negate (lambda_matrix mat, int, int);
168
void lambda_matrix_row_mc (lambda_matrix, int, int, int);
169
void lambda_matrix_col_exchange (lambda_matrix, int, int, int);
170
void lambda_matrix_col_add (lambda_matrix, int, int, int, int);
171
void lambda_matrix_col_negate (lambda_matrix, int, int);
172
void lambda_matrix_col_mc (lambda_matrix, int, int, int);
173
int lambda_matrix_inverse (lambda_matrix, lambda_matrix, int);
174
void lambda_matrix_hermite (lambda_matrix, int, lambda_matrix, lambda_matrix);
175
void lambda_matrix_left_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
176
void lambda_matrix_right_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
177
int lambda_matrix_first_nz_vec (lambda_matrix, int, int, int);
178
void lambda_matrix_project_to_null (lambda_matrix, int, int, int,
179
                                    lambda_vector);
180
void print_lambda_matrix (FILE *, lambda_matrix, int, int);
181
 
182
lambda_trans_matrix lambda_trans_matrix_new (int, int);
183
bool lambda_trans_matrix_nonsingular_p (lambda_trans_matrix);
184
bool lambda_trans_matrix_fullrank_p (lambda_trans_matrix);
185
int lambda_trans_matrix_rank (lambda_trans_matrix);
186
lambda_trans_matrix lambda_trans_matrix_basis (lambda_trans_matrix);
187
lambda_trans_matrix lambda_trans_matrix_padding (lambda_trans_matrix);
188
lambda_trans_matrix lambda_trans_matrix_inverse (lambda_trans_matrix);
189
void print_lambda_trans_matrix (FILE *, lambda_trans_matrix);
190
void lambda_matrix_vector_mult (lambda_matrix, int, int, lambda_vector,
191
                                lambda_vector);
192
bool lambda_trans_matrix_id_p (lambda_trans_matrix);
193
 
194
lambda_body_vector lambda_body_vector_new (int);
195
lambda_body_vector lambda_body_vector_compute_new (lambda_trans_matrix,
196
                                                   lambda_body_vector);
197
void print_lambda_body_vector (FILE *, lambda_body_vector);
198
lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *,
199
                                                 struct loop *,
200
                                                 VEC(tree,heap) **,
201
                                                 VEC(tree,heap) **);
202
void lambda_loopnest_to_gcc_loopnest (struct loop *,
203
                                      VEC(tree,heap) *, VEC(tree,heap) *,
204
                                      lambda_loopnest, lambda_trans_matrix);
205
 
206
 
207
static inline void lambda_vector_negate (lambda_vector, lambda_vector, int);
208
static inline void lambda_vector_mult_const (lambda_vector, lambda_vector, int, int);
209
static inline void lambda_vector_add (lambda_vector, lambda_vector,
210
                                      lambda_vector, int);
211
static inline void lambda_vector_add_mc (lambda_vector, int, lambda_vector, int,
212
                                         lambda_vector, int);
213
static inline void lambda_vector_copy (lambda_vector, lambda_vector, int);
214
static inline bool lambda_vector_zerop (lambda_vector, int);
215
static inline void lambda_vector_clear (lambda_vector, int);
216
static inline bool lambda_vector_equal (lambda_vector, lambda_vector, int);
217
static inline int lambda_vector_min_nz (lambda_vector, int, int);
218
static inline int lambda_vector_first_nz (lambda_vector, int, int);
219
static inline void print_lambda_vector (FILE *, lambda_vector, int);
220
 
221
/* Allocate a new vector of given SIZE.  */
222
 
223
static inline lambda_vector
224
lambda_vector_new (int size)
225
{
226
  return GGC_CNEWVEC (int, size);
227
}
228
 
229
 
230
 
231
/* Multiply vector VEC1 of length SIZE by a constant CONST1,
232
   and store the result in VEC2.  */
233
 
234
static inline void
235
lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
236
                          int size, int const1)
237
{
238
  int i;
239
 
240
  if (const1 == 0)
241
    lambda_vector_clear (vec2, size);
242
  else
243
    for (i = 0; i < size; i++)
244
      vec2[i] = const1 * vec1[i];
245
}
246
 
247
/* Negate vector VEC1 with length SIZE and store it in VEC2.  */
248
 
249
static inline void
250
lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
251
                      int size)
252
{
253
  lambda_vector_mult_const (vec1, vec2, size, -1);
254
}
255
 
256
/* VEC3 = VEC1+VEC2, where all three the vectors are of length SIZE.  */
257
 
258
static inline void
259
lambda_vector_add (lambda_vector vec1, lambda_vector vec2,
260
                   lambda_vector vec3, int size)
261
{
262
  int i;
263
  for (i = 0; i < size; i++)
264
    vec3[i] = vec1[i] + vec2[i];
265
}
266
 
267
/* VEC3 = CONSTANT1*VEC1 + CONSTANT2*VEC2.  All vectors have length SIZE.  */
268
 
269
static inline void
270
lambda_vector_add_mc (lambda_vector vec1, int const1,
271
                      lambda_vector vec2, int const2,
272
                      lambda_vector vec3, int size)
273
{
274
  int i;
275
  for (i = 0; i < size; i++)
276
    vec3[i] = const1 * vec1[i] + const2 * vec2[i];
277
}
278
 
279
/* Copy the elements of vector VEC1 with length SIZE to VEC2.  */
280
 
281
static inline void
282
lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
283
                    int size)
284
{
285
  memcpy (vec2, vec1, size * sizeof (*vec1));
286
}
287
 
288
/* Return true if vector VEC1 of length SIZE is the zero vector.  */
289
 
290
static inline bool
291
lambda_vector_zerop (lambda_vector vec1, int size)
292
{
293
  int i;
294
  for (i = 0; i < size; i++)
295
    if (vec1[i] != 0)
296
      return false;
297
  return true;
298
}
299
 
300
/* Clear out vector VEC1 of length SIZE.  */
301
 
302
static inline void
303
lambda_vector_clear (lambda_vector vec1, int size)
304
{
305
  memset (vec1, 0, size * sizeof (*vec1));
306
}
307
 
308
/* Return true if two vectors are equal.  */
309
 
310
static inline bool
311
lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
312
{
313
  int i;
314
  for (i = 0; i < size; i++)
315
    if (vec1[i] != vec2[i])
316
      return false;
317
  return true;
318
}
319
 
320
/* Return the minimum nonzero element in vector VEC1 between START and N.
321
   We must have START <= N.  */
322
 
323
static inline int
324
lambda_vector_min_nz (lambda_vector vec1, int n, int start)
325
{
326
  int j;
327
  int min = -1;
328
 
329
  gcc_assert (start <= n);
330
  for (j = start; j < n; j++)
331
    {
332
      if (vec1[j])
333
        if (min < 0 || vec1[j] < vec1[min])
334
          min = j;
335
    }
336
  gcc_assert (min >= 0);
337
 
338
  return min;
339
}
340
 
341
/* Return the first nonzero element of vector VEC1 between START and N.
342
   We must have START <= N.   Returns N if VEC1 is the zero vector.  */
343
 
344
static inline int
345
lambda_vector_first_nz (lambda_vector vec1, int n, int start)
346
{
347
  int j = start;
348
  while (j < n && vec1[j] == 0)
349
    j++;
350
  return j;
351
}
352
 
353
 
354
/* Multiply a vector by a matrix.  */
355
 
356
static inline void
357
lambda_vector_matrix_mult (lambda_vector vect, int m, lambda_matrix mat,
358
                           int n, lambda_vector dest)
359
{
360
  int i, j;
361
  lambda_vector_clear (dest, n);
362
  for (i = 0; i < n; i++)
363
    for (j = 0; j < m; j++)
364
      dest[i] += mat[j][i] * vect[j];
365
}
366
 
367
 
368
/* Print out a vector VEC of length N to OUTFILE.  */
369
 
370
static inline void
371
print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
372
{
373
  int i;
374
 
375
  for (i = 0; i < n; i++)
376
    fprintf (outfile, "%3d ", vector[i]);
377
  fprintf (outfile, "\n");
378
}
379
 
380
/* Compute the greatest common divisor of two numbers using
381
   Euclid's algorithm.  */
382
 
383
static inline int
384
gcd (int a, int b)
385
{
386
  int x, y, z;
387
 
388
  x = abs (a);
389
  y = abs (b);
390
 
391
  while (x > 0)
392
    {
393
      z = y % x;
394
      y = x;
395
      x = z;
396
    }
397
 
398
  return y;
399
}
400
 
401
/* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
402
 
403
static inline int
404
lambda_vector_gcd (lambda_vector vector, int size)
405
{
406
  int i;
407
  int gcd1 = 0;
408
 
409
  if (size > 0)
410
    {
411
      gcd1 = vector[0];
412
      for (i = 1; i < size; i++)
413
        gcd1 = gcd (gcd1, vector[i]);
414
    }
415
  return gcd1;
416
}
417
 
418
/* Returns true when the vector V is lexicographically positive, in
419
   other words, when the first nonzero element is positive.  */
420
 
421
static inline bool
422
lambda_vector_lexico_pos (lambda_vector v,
423
                          unsigned n)
424
{
425
  unsigned i;
426
  for (i = 0; i < n; i++)
427
    {
428
      if (v[i] == 0)
429
        continue;
430
      if (v[i] < 0)
431
        return false;
432
      if (v[i] > 0)
433
        return true;
434
    }
435
  return true;
436
}
437
 
438
#endif /* LAMBDA_H  */
439
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.