gcc/lambda.h

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