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