gcc/lambda.h

   1 /* 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 DEF_VEC_P(lambda_vector);
  32 DEF_VEC_ALLOC_P(lambda_vector,heap);
  33
  34 typedef VEC(lambda_vector, heap) *lambda_vector_vec_p;
  35 DEF_VEC_P (lambda_vector_vec_p);
  36 DEF_VEC_ALLOC_P (lambda_vector_vec_p, heap);
  37
  38 /* An integer matrix.  A matrix consists of m vectors of length n (IE
  39    all vectors are the same length).  */
  40 typedef lambda_vector *lambda_matrix;
  41
  42 /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
  43    matrix.  Rather than use floats, we simply keep a single DENOMINATOR that
  44    represents the denominator for every element in the matrix.  */
  45 typedef struct lambda_trans_matrix_s
  46 {
  47   lambda_matrix matrix;
  48   int rowsize;
  49   int colsize;
  50   int denominator;
  51 } *lambda_trans_matrix;
  52 #define LTM_MATRIX(T) ((T)->matrix)
  53 #define LTM_ROWSIZE(T) ((T)->rowsize)
  54 #define LTM_COLSIZE(T) ((T)->colsize)
  55 #define LTM_DENOMINATOR(T) ((T)->denominator)
  56
  57 /* A vector representing a statement in the body of a loop.
  58    The COEFFICIENTS vector contains a coefficient for each induction variable
  59    in the loop nest containing the statement.
  60    The DENOMINATOR represents the denominator for each coefficient in the
  61    COEFFICIENT vector.
  62
  63    This structure is used during code generation in order to rewrite the old
  64    induction variable uses in a statement in terms of the newly created
  65    induction variables.  */
  66 typedef struct lambda_body_vector_s
  67 {
  68   lambda_vector coefficients;
  69   int size;
  70   int denominator;
  71 } *lambda_body_vector;
  72 #define LBV_COEFFICIENTS(T) ((T)->coefficients)
  73 #define LBV_SIZE(T) ((T)->size)
  74 #define LBV_DENOMINATOR(T) ((T)->denominator)
  75
  76 /* Piecewise linear expression.
  77    This structure represents a linear expression with terms for the invariants
  78    and induction variables of a loop.
  79    COEFFICIENTS is a vector of coefficients for the induction variables, one
  80    per loop in the loop nest.
  81    CONSTANT is the constant portion of the linear expression
  82    INVARIANT_COEFFICIENTS is a vector of coefficients for the loop invariants,
  83    one per invariant.
  84    DENOMINATOR is the denominator for all of the coefficients and constants in
  85    the expression.
  86    The linear expressions can be linked together using the NEXT field, in
  87    order to represent MAX or MIN of a group of linear expressions.  */
  88 typedef struct lambda_linear_expression_s
  89 {
  90   lambda_vector coefficients;
  91   int constant;
  92   lambda_vector invariant_coefficients;
  93   int denominator;
  94   struct lambda_linear_expression_s *next;
  95 } *lambda_linear_expression;
  96
  97 #define LLE_COEFFICIENTS(T) ((T)->coefficients)
  98 #define LLE_CONSTANT(T) ((T)->constant)
  99 #define LLE_INVARIANT_COEFFICIENTS(T) ((T)->invariant_coefficients)
 100 #define LLE_DENOMINATOR(T) ((T)->denominator)
 101 #define LLE_NEXT(T) ((T)->next)
 102
 103 struct obstack;
 104
 105 lambda_linear_expression lambda_linear_expression_new (int, int,
 106                                                        struct obstack *);
 107 void print_lambda_linear_expression (FILE *, lambda_linear_expression, int,
 108                                      int, char);
 109
 110 /* Loop structure.  Our loop structure consists of a constant representing the
 111    STEP of the loop, a set of linear expressions representing the LOWER_BOUND
 112    of the loop, a set of linear expressions representing the UPPER_BOUND of
 113    the loop, and a set of linear expressions representing the LINEAR_OFFSET of
 114    the loop.  The linear offset is a set of linear expressions that are
 115    applied to *both* the lower bound, and the upper bound.  */
 116 typedef struct lambda_loop_s
 117 {
 118   lambda_linear_expression lower_bound;
 119   lambda_linear_expression upper_bound;
 120   lambda_linear_expression linear_offset;
 121   int step;
 122 } *lambda_loop;
 123
 124 #define LL_LOWER_BOUND(T) ((T)->lower_bound)
 125 #define LL_UPPER_BOUND(T) ((T)->upper_bound)
 126 #define LL_LINEAR_OFFSET(T) ((T)->linear_offset)
 127 #define LL_STEP(T)   ((T)->step)
 128
 129 /* Loop nest structure.
 130    The loop nest structure consists of a set of loop structures (defined
 131    above) in LOOPS, along with an integer representing the DEPTH of the loop,
 132    and an integer representing the number of INVARIANTS in the loop.  Both of
 133    these integers are used to size the associated coefficient vectors in the
 134    linear expression structures.  */
 135 typedef struct lambda_loopnest_s
 136 {
 137   lambda_loop *loops;
 138   int depth;
 139   int invariants;
 140 } *lambda_loopnest;
 141
 142 #define LN_LOOPS(T) ((T)->loops)
 143 #define LN_DEPTH(T) ((T)->depth)
 144 #define LN_INVARIANTS(T) ((T)->invariants)
 145
 146 lambda_loopnest lambda_loopnest_new (int, int, struct obstack *);
 147 lambda_loopnest lambda_loopnest_transform (lambda_loopnest,
 148                                            lambda_trans_matrix,
 149                                            struct obstack *);
 150 struct loop;
 151 bool perfect_nest_p (struct loop *);
 152 void print_lambda_loopnest (FILE *, lambda_loopnest, char);
 153
 154 #define lambda_loop_new() (lambda_loop) ggc_alloc_cleared (sizeof (struct lambda_loop_s))
 155
 156 void print_lambda_loop (FILE *, lambda_loop, int, int, char);
 157
 158 lambda_matrix lambda_matrix_new (int, int);
 159
 160 void lambda_matrix_id (lambda_matrix, int);
 161 bool lambda_matrix_id_p (lambda_matrix, int);
 162 void lambda_matrix_copy (lambda_matrix, lambda_matrix, int, int);
 163 void lambda_matrix_negate (lambda_matrix, lambda_matrix, int, int);
 164 void lambda_matrix_transpose (lambda_matrix, lambda_matrix, int, int);
 165 void lambda_matrix_add (lambda_matrix, lambda_matrix, lambda_matrix, int,
 166                         int);
 167 void lambda_matrix_add_mc (lambda_matrix, int, lambda_matrix, int,
 168                            lambda_matrix, int, int);
 169 void lambda_matrix_mult (lambda_matrix, lambda_matrix, lambda_matrix,
 170                          int, int, int);
 171 void lambda_matrix_delete_rows (lambda_matrix, int, int, int);
 172 void lambda_matrix_row_exchange (lambda_matrix, int, int);
 173 void lambda_matrix_row_add (lambda_matrix, int, int, int, int);
 174 void lambda_matrix_row_negate (lambda_matrix mat, int, int);
 175 void lambda_matrix_row_mc (lambda_matrix, int, int, int);
 176 void lambda_matrix_col_exchange (lambda_matrix, int, int, int);
 177 void lambda_matrix_col_add (lambda_matrix, int, int, int, int);
 178 void lambda_matrix_col_negate (lambda_matrix, int, int);
 179 void lambda_matrix_col_mc (lambda_matrix, int, int, int);
 180 int lambda_matrix_inverse (lambda_matrix, lambda_matrix, int);
 181 void lambda_matrix_hermite (lambda_matrix, int, lambda_matrix, lambda_matrix);
 182 void lambda_matrix_left_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
 183 void lambda_matrix_right_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
 184 int lambda_matrix_first_nz_vec (lambda_matrix, int, int, int);
 185 void lambda_matrix_project_to_null (lambda_matrix, int, int, int,
 186                                     lambda_vector);
 187 void print_lambda_matrix (FILE *, lambda_matrix, int, int);
 188
 189 lambda_trans_matrix lambda_trans_matrix_new (int, int);
 190 bool lambda_trans_matrix_nonsingular_p (lambda_trans_matrix);
 191 bool lambda_trans_matrix_fullrank_p (lambda_trans_matrix);
 192 int lambda_trans_matrix_rank (lambda_trans_matrix);
 193 lambda_trans_matrix lambda_trans_matrix_basis (lambda_trans_matrix);
 194 lambda_trans_matrix lambda_trans_matrix_padding (lambda_trans_matrix);
 195 lambda_trans_matrix lambda_trans_matrix_inverse (lambda_trans_matrix);
 196 void print_lambda_trans_matrix (FILE *, lambda_trans_matrix);
 197 void lambda_matrix_vector_mult (lambda_matrix, int, int, lambda_vector,
 198                                 lambda_vector);
 199 bool lambda_trans_matrix_id_p (lambda_trans_matrix);
 200
 201 lambda_body_vector lambda_body_vector_new (int, struct obstack *);
 202 lambda_body_vector lambda_body_vector_compute_new (lambda_trans_matrix,
 203                                                    lambda_body_vector,
 204                                                    struct obstack *);
 205 void print_lambda_body_vector (FILE *, lambda_body_vector);
 206 lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loop *,
 207                                                  VEC(tree,heap) **,
 208                                                  VEC(tree,heap) **,
 209                                                  struct obstack *);
 210 void lambda_loopnest_to_gcc_loopnest (struct loop *,
 211                                       VEC(tree,heap) *, VEC(tree,heap) *,
 212                                       VEC(tree,heap) **,
 213                                       lambda_loopnest, lambda_trans_matrix,
 214                                       struct obstack *);
 215 void remove_iv (tree);
 216
 217 static inline void lambda_vector_negate (lambda_vector, lambda_vector, int);
 218 static inline void lambda_vector_mult_const (lambda_vector, lambda_vector, int, int);
 219 static inline void lambda_vector_add (lambda_vector, lambda_vector,
 220                                       lambda_vector, int);
 221 static inline void lambda_vector_add_mc (lambda_vector, int, lambda_vector, int,
 222                                          lambda_vector, int);
 223 static inline void lambda_vector_copy (lambda_vector, lambda_vector, int);
 224 static inline bool lambda_vector_zerop (lambda_vector, int);
 225 static inline void lambda_vector_clear (lambda_vector, int);
 226 static inline bool lambda_vector_equal (lambda_vector, lambda_vector, int);
 227 static inline int lambda_vector_min_nz (lambda_vector, int, int);
 228 static inline int lambda_vector_first_nz (lambda_vector, int, int);
 229 static inline void print_lambda_vector (FILE *, lambda_vector, int);
 230
 231 /* Allocate a new vector of given SIZE.  */
 232
 233 static inline lambda_vector
 234 lambda_vector_new (int size)
 235 {
 236   return GGC_CNEWVEC (int, size);
 237 }
 238
 239
 240
 241 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
 242    and store the result in VEC2.  */
 243
 244 static inline void
 245 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
 246                           int size, int const1)
 247 {
 248   int i;
 249
 250   if (const1 == 0)
 251     lambda_vector_clear (vec2, size);
 252   else
 253     for (i = 0; i < size; i++)
 254       vec2[i] = const1 * vec1[i];
 255 }
 256
 257 /* Negate vector VEC1 with length SIZE and store it in VEC2.  */
 258
 259 static inline void
 260 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
 261                       int size)
 262 {
 263   lambda_vector_mult_const (vec1, vec2, size, -1);
 264 }
 265
 266 /* VEC3 = VEC1+VEC2, where all three the vectors are of length SIZE.  */
 267
 268 static inline void
 269 lambda_vector_add (lambda_vector vec1, lambda_vector vec2,
 270                    lambda_vector vec3, int size)
 271 {
 272   int i;
 273   for (i = 0; i < size; i++)
 274     vec3[i] = vec1[i] + vec2[i];
 275 }
 276
 277 /* VEC3 = CONSTANT1*VEC1 + CONSTANT2*VEC2.  All vectors have length SIZE.  */
 278
 279 static inline void
 280 lambda_vector_add_mc (lambda_vector vec1, int const1,
 281                       lambda_vector vec2, int const2,
 282                       lambda_vector vec3, int size)
 283 {
 284   int i;
 285   for (i = 0; i < size; i++)
 286     vec3[i] = const1 * vec1[i] + const2 * vec2[i];
 287 }
 288
 289 /* Copy the elements of vector VEC1 with length SIZE to VEC2.  */
 290
 291 static inline void
 292 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
 293                     int size)
 294 {
 295   memcpy (vec2, vec1, size * sizeof (*vec1));
 296 }
 297
 298 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
 299
 300 static inline bool
 301 lambda_vector_zerop (lambda_vector vec1, int size)
 302 {
 303   int i;
 304   for (i = 0; i < size; i++)
 305     if (vec1[i] != 0)
 306       return false;
 307   return true;
 308 }
 309
 310 /* Clear out vector VEC1 of length SIZE.  */
 311
 312 static inline void
 313 lambda_vector_clear (lambda_vector vec1, int size)
 314 {
 315   memset (vec1, 0, size * sizeof (*vec1));
 316 }
 317
 318 /* Return true if two vectors are equal.  */
 319
 320 static inline bool
 321 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
 322 {
 323   int i;
 324   for (i = 0; i < size; i++)
 325     if (vec1[i] != vec2[i])
 326       return false;
 327   return true;
 328 }
 329
 330 /* Return the minimum nonzero element in vector VEC1 between START and N.
 331    We must have START <= N.  */
 332
 333 static inline int
 334 lambda_vector_min_nz (lambda_vector vec1, int n, int start)
 335 {
 336   int j;
 337   int min = -1;
 338
 339   gcc_assert (start <= n);
 340   for (j = start; j < n; j++)
 341     {
 342       if (vec1[j])
 343         if (min < 0 || vec1[j] < vec1[min])
 344           min = j;
 345     }
 346   gcc_assert (min >= 0);
 347
 348   return min;
 349 }
 350
 351 /* Return the first nonzero element of vector VEC1 between START and N.
 352    We must have START <= N.   Returns N if VEC1 is the zero vector.  */
 353
 354 static inline int
 355 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
 356 {
 357   int j = start;
 358   while (j < n && vec1[j] == 0)
 359     j++;
 360   return j;
 361 }
 362
 363
 364 /* Multiply a vector by a matrix.  */
 365
 366 static inline void
 367 lambda_vector_matrix_mult (lambda_vector vect, int m, lambda_matrix mat,
 368                            int n, lambda_vector dest)
 369 {
 370   int i, j;
 371   lambda_vector_clear (dest, n);
 372   for (i = 0; i < n; i++)
 373     for (j = 0; j < m; j++)
 374       dest[i] += mat[j][i] * vect[j];
 375 }
 376
 377
 378 /* Print out a vector VEC of length N to OUTFILE.  */
 379
 380 static inline void
 381 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
 382 {
 383   int i;
 384
 385   for (i = 0; i < n; i++)
 386     fprintf (outfile, "%3d ", vector[i]);
 387   fprintf (outfile, "\n");
 388 }
 389
 390 /* Compute the greatest common divisor of two numbers using
 391    Euclid's algorithm.  */
 392
 393 static inline int
 394 gcd (int a, int b)
 395 {
 396   int x, y, z;
 397
 398   x = abs (a);
 399   y = abs (b);
 400
 401   while (x > 0)
 402     {
 403       z = y % x;
 404       y = x;
 405       x = z;
 406     }
 407
 408   return y;
 409 }
 410
 411 /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
 412
 413 static inline int
 414 lambda_vector_gcd (lambda_vector vector, int size)
 415 {
 416   int i;
 417   int gcd1 = 0;
 418
 419   if (size > 0)
 420     {
 421       gcd1 = vector[0];
 422       for (i = 1; i < size; i++)
 423         gcd1 = gcd (gcd1, vector[i]);
 424     }
 425   return gcd1;
 426 }
 427
 428 /* Returns true when the vector V is lexicographically positive, in
 429    other words, when the first nonzero element is positive.  */
 430
 431 static inline bool
 432 lambda_vector_lexico_pos (lambda_vector v,
 433                           unsigned n)
 434 {
 435   unsigned i;
 436   for (i = 0; i < n; i++)
 437     {
 438       if (v[i] == 0)
 439         continue;
 440       if (v[i] < 0)
 441         return false;
 442       if (v[i] > 0)
 443         return true;
 444     }
 445   return true;
 446 }
 447
 448 /* Given a vector of induction variables IVS, and a vector of
 449    coefficients COEFS, build a tree that is a linear combination of
 450    the induction variables.  */
 451
 452 static inline tree
 453 build_linear_expr (tree type, lambda_vector coefs, VEC (tree, heap) *ivs)
 454 {
 455   unsigned i;
 456   tree iv;
 457   tree expr = fold_convert (type, integer_zero_node);
 458
 459   for (i = 0; VEC_iterate (tree, ivs, i, iv); i++)
 460     {
 461       int k = coefs[i];
 462
 463       if (k == 1)
 464         expr = fold_build2 (PLUS_EXPR, type, expr, iv);
 465
 466       else if (k != 0)
 467         expr = fold_build2 (PLUS_EXPR, type, expr,
 468                             fold_build2 (MULT_EXPR, type, iv,
 469                                          build_int_cst (type, k)));
 470     }
 471
 472   return expr;
 473 }
 474
 475 /* Returns the dependence level for a vector DIST of size LENGTH.
 476    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
 477    to the sequence of statements, not carried by any loop.  */
 478
 479
 480 static inline unsigned
 481 dependence_level (lambda_vector dist_vect, int length)
 482 {
 483   int i;
 484
 485   for (i = 0; i < length; i++)
 486     if (dist_vect[i] != 0)
 487       return i + 1;
 488
 489   return 0;
 490 }
 491
 492 #endif /* LAMBDA_H  */