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 void print_lambda_loop (FILE *, lambda_loop, int, int, char);
 160
 161 lambda_matrix lambda_matrix_new (int, int, struct obstack *);
 162
 163 void lambda_matrix_id (lambda_matrix, int);
 164 bool lambda_matrix_id_p (lambda_matrix, int);
 165 void lambda_matrix_copy (lambda_matrix, lambda_matrix, int, int);
 166 void lambda_matrix_negate (lambda_matrix, lambda_matrix, int, int);
 167 void lambda_matrix_transpose (lambda_matrix, lambda_matrix, int, int);
 168 void lambda_matrix_add (lambda_matrix, lambda_matrix, lambda_matrix, int,
 169                         int);
 170 void lambda_matrix_add_mc (lambda_matrix, int, lambda_matrix, int,
 171                            lambda_matrix, int, int);
 172 void lambda_matrix_mult (lambda_matrix, lambda_matrix, lambda_matrix,
 173                          int, int, int);
 174 void lambda_matrix_delete_rows (lambda_matrix, int, int, int);
 175 void lambda_matrix_row_exchange (lambda_matrix, int, int);
 176 void lambda_matrix_row_add (lambda_matrix, int, int, int, int);
 177 void lambda_matrix_row_negate (lambda_matrix mat, int, int);
 178 void lambda_matrix_row_mc (lambda_matrix, int, int, int);
 179 void lambda_matrix_col_exchange (lambda_matrix, int, int, int);
 180 void lambda_matrix_col_add (lambda_matrix, int, int, int, int);
 181 void lambda_matrix_col_negate (lambda_matrix, int, int);
 182 void lambda_matrix_col_mc (lambda_matrix, int, int, int);
 183 int lambda_matrix_inverse (lambda_matrix, lambda_matrix, int, struct obstack *);
 184 void lambda_matrix_hermite (lambda_matrix, int, lambda_matrix, lambda_matrix);
 185 void lambda_matrix_left_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
 186 void lambda_matrix_right_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
 187 int lambda_matrix_first_nz_vec (lambda_matrix, int, int, int);
 188 void lambda_matrix_project_to_null (lambda_matrix, int, int, int,
 189                                     lambda_vector);
 190 void print_lambda_matrix (FILE *, lambda_matrix, int, int);
 191
 192 lambda_trans_matrix lambda_trans_matrix_new (int, int, struct obstack *);
 193 bool lambda_trans_matrix_nonsingular_p (lambda_trans_matrix);
 194 bool lambda_trans_matrix_fullrank_p (lambda_trans_matrix);
 195 int lambda_trans_matrix_rank (lambda_trans_matrix);
 196 lambda_trans_matrix lambda_trans_matrix_basis (lambda_trans_matrix);
 197 lambda_trans_matrix lambda_trans_matrix_padding (lambda_trans_matrix);
 198 lambda_trans_matrix lambda_trans_matrix_inverse (lambda_trans_matrix,
 199                                                  struct obstack *);
 200 void print_lambda_trans_matrix (FILE *, lambda_trans_matrix);
 201 void lambda_matrix_vector_mult (lambda_matrix, int, int, lambda_vector,
 202                                 lambda_vector);
 203 bool lambda_trans_matrix_id_p (lambda_trans_matrix);
 204
 205 lambda_body_vector lambda_body_vector_new (int, struct obstack *);
 206 lambda_body_vector lambda_body_vector_compute_new (lambda_trans_matrix,
 207                                                    lambda_body_vector,
 208                                                    struct obstack *);
 209 void print_lambda_body_vector (FILE *, lambda_body_vector);
 210 lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loop *,
 211                                                  VEC(tree,heap) **,
 212                                                  VEC(tree,heap) **,
 213                                                  struct obstack *);
 214 void lambda_loopnest_to_gcc_loopnest (struct loop *,
 215                                       VEC(tree,heap) *, VEC(tree,heap) *,
 216                                       VEC(gimple,heap) **,
 217                                       lambda_loopnest, lambda_trans_matrix,
 218                                       struct obstack *);
 219 void remove_iv (gimple);
 220 tree find_induction_var_from_exit_cond (struct loop *);
 221
 222 static inline void lambda_vector_negate (lambda_vector, lambda_vector, int);
 223 static inline void lambda_vector_mult_const (lambda_vector, lambda_vector, int, int);
 224 static inline void lambda_vector_add (lambda_vector, lambda_vector,
 225                                       lambda_vector, int);
 226 static inline void lambda_vector_add_mc (lambda_vector, int, lambda_vector, int,
 227                                          lambda_vector, int);
 228 static inline void lambda_vector_copy (lambda_vector, lambda_vector, int);
 229 static inline bool lambda_vector_zerop (lambda_vector, int);
 230 static inline void lambda_vector_clear (lambda_vector, int);
 231 static inline bool lambda_vector_equal (lambda_vector, lambda_vector, int);
 232 static inline int lambda_vector_min_nz (lambda_vector, int, int);
 233 static inline int lambda_vector_first_nz (lambda_vector, int, int);
 234 static inline void print_lambda_vector (FILE *, lambda_vector, int);
 235
 236 /* Allocate a new vector of given SIZE.  */
 237
 238 static inline lambda_vector
 239 lambda_vector_new (int size)
 240 {
 241   return GGC_CNEWVEC (int, size);
 242 }
 243
 244
 245
 246 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
 247    and store the result in VEC2.  */
 248
 249 static inline void
 250 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
 251                           int size, int const1)
 252 {
 253   int i;
 254
 255   if (const1 == 0)
 256     lambda_vector_clear (vec2, size);
 257   else
 258     for (i = 0; i < size; i++)
 259       vec2[i] = const1 * vec1[i];
 260 }
 261
 262 /* Negate vector VEC1 with length SIZE and store it in VEC2.  */
 263
 264 static inline void
 265 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
 266                       int size)
 267 {
 268   lambda_vector_mult_const (vec1, vec2, size, -1);
 269 }
 270
 271 /* VEC3 = VEC1+VEC2, where all three the vectors are of length SIZE.  */
 272
 273 static inline void
 274 lambda_vector_add (lambda_vector vec1, lambda_vector vec2,
 275                    lambda_vector vec3, int size)
 276 {
 277   int i;
 278   for (i = 0; i < size; i++)
 279     vec3[i] = vec1[i] + vec2[i];
 280 }
 281
 282 /* VEC3 = CONSTANT1*VEC1 + CONSTANT2*VEC2.  All vectors have length SIZE.  */
 283
 284 static inline void
 285 lambda_vector_add_mc (lambda_vector vec1, int const1,
 286                       lambda_vector vec2, int const2,
 287                       lambda_vector vec3, int size)
 288 {
 289   int i;
 290   for (i = 0; i < size; i++)
 291     vec3[i] = const1 * vec1[i] + const2 * vec2[i];
 292 }
 293
 294 /* Copy the elements of vector VEC1 with length SIZE to VEC2.  */
 295
 296 static inline void
 297 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
 298                     int size)
 299 {
 300   memcpy (vec2, vec1, size * sizeof (*vec1));
 301 }
 302
 303 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
 304
 305 static inline bool
 306 lambda_vector_zerop (lambda_vector vec1, int size)
 307 {
 308   int i;
 309   for (i = 0; i < size; i++)
 310     if (vec1[i] != 0)
 311       return false;
 312   return true;
 313 }
 314
 315 /* Clear out vector VEC1 of length SIZE.  */
 316
 317 static inline void
 318 lambda_vector_clear (lambda_vector vec1, int size)
 319 {
 320   memset (vec1, 0, size * sizeof (*vec1));
 321 }
 322
 323 /* Return true if two vectors are equal.  */
 324
 325 static inline bool
 326 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
 327 {
 328   int i;
 329   for (i = 0; i < size; i++)
 330     if (vec1[i] != vec2[i])
 331       return false;
 332   return true;
 333 }
 334
 335 /* Return the minimum nonzero element in vector VEC1 between START and N.
 336    We must have START <= N.  */
 337
 338 static inline int
 339 lambda_vector_min_nz (lambda_vector vec1, int n, int start)
 340 {
 341   int j;
 342   int min = -1;
 343
 344   gcc_assert (start <= n);
 345   for (j = start; j < n; j++)
 346     {
 347       if (vec1[j])
 348         if (min < 0 || vec1[j] < vec1[min])
 349           min = j;
 350     }
 351   gcc_assert (min >= 0);
 352
 353   return min;
 354 }
 355
 356 /* Return the first nonzero element of vector VEC1 between START and N.
 357    We must have START <= N.   Returns N if VEC1 is the zero vector.  */
 358
 359 static inline int
 360 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
 361 {
 362   int j = start;
 363   while (j < n && vec1[j] == 0)
 364     j++;
 365   return j;
 366 }
 367
 368
 369 /* Multiply a vector by a matrix.  */
 370
 371 static inline void
 372 lambda_vector_matrix_mult (lambda_vector vect, int m, lambda_matrix mat,
 373                            int n, lambda_vector dest)
 374 {
 375   int i, j;
 376   lambda_vector_clear (dest, n);
 377   for (i = 0; i < n; i++)
 378     for (j = 0; j < m; j++)
 379       dest[i] += mat[j][i] * vect[j];
 380 }
 381
 382 /* Compare two vectors returning an integer less than, equal to, or
 383    greater than zero if the first argument is considered to be respectively
 384    less than, equal to, or greater than the second.
 385    We use the lexicographic order.  */
 386
 387 static inline int
 388 lambda_vector_compare (lambda_vector vec1, int length1, lambda_vector vec2,
 389                        int length2)
 390 {
 391   int min_length;
 392   int i;
 393
 394   if (length1 < length2)
 395     min_length = length1;
 396   else
 397     min_length = length2;
 398
 399   for (i = 0; i < min_length; i++)
 400     if (vec1[i] < vec2[i])
 401       return -1;
 402     else if (vec1[i] > vec2[i])
 403       return 1;
 404     else
 405       continue;
 406
 407   return length1 - length2;
 408 }
 409
 410 /* Print out a vector VEC of length N to OUTFILE.  */
 411
 412 static inline void
 413 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
 414 {
 415   int i;
 416
 417   for (i = 0; i < n; i++)
 418     fprintf (outfile, "%3d ", vector[i]);
 419   fprintf (outfile, "\n");
 420 }
 421
 422 /* Compute the greatest common divisor of two numbers using
 423    Euclid's algorithm.  */
 424
 425 static inline int
 426 gcd (int a, int b)
 427 {
 428   int x, y, z;
 429
 430   x = abs (a);
 431   y = abs (b);
 432
 433   while (x > 0)
 434     {
 435       z = y % x;
 436       y = x;
 437       x = z;
 438     }
 439
 440   return y;
 441 }
 442
 443 /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
 444
 445 static inline int
 446 lambda_vector_gcd (lambda_vector vector, int size)
 447 {
 448   int i;
 449   int gcd1 = 0;
 450
 451   if (size > 0)
 452     {
 453       gcd1 = vector[0];
 454       for (i = 1; i < size; i++)
 455         gcd1 = gcd (gcd1, vector[i]);
 456     }
 457   return gcd1;
 458 }
 459
 460 /* Returns true when the vector V is lexicographically positive, in
 461    other words, when the first nonzero element is positive.  */
 462
 463 static inline bool
 464 lambda_vector_lexico_pos (lambda_vector v,
 465                           unsigned n)
 466 {
 467   unsigned i;
 468   for (i = 0; i < n; i++)
 469     {
 470       if (v[i] == 0)
 471         continue;
 472       if (v[i] < 0)
 473         return false;
 474       if (v[i] > 0)
 475         return true;
 476     }
 477   return true;
 478 }
 479
 480 /* Given a vector of induction variables IVS, and a vector of
 481    coefficients COEFS, build a tree that is a linear combination of
 482    the induction variables.  */
 483
 484 static inline tree
 485 build_linear_expr (tree type, lambda_vector coefs, VEC (tree, heap) *ivs)
 486 {
 487   unsigned i;
 488   tree iv;
 489   tree expr = fold_convert (type, integer_zero_node);
 490
 491   for (i = 0; VEC_iterate (tree, ivs, i, iv); i++)
 492     {
 493       int k = coefs[i];
 494
 495       if (k == 1)
 496         expr = fold_build2 (PLUS_EXPR, type, expr, iv);
 497
 498       else if (k != 0)
 499         expr = fold_build2 (PLUS_EXPR, type, expr,
 500                             fold_build2 (MULT_EXPR, type, iv,
 501                                          build_int_cst (type, k)));
 502     }
 503
 504   return expr;
 505 }
 506
 507 /* Returns the dependence level for a vector DIST of size LENGTH.
 508    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
 509    to the sequence of statements, not carried by any loop.  */
 510
 511
 512 static inline unsigned
 513 dependence_level (lambda_vector dist_vect, int length)
 514 {
 515   int i;
 516
 517   for (i = 0; i < length; i++)
 518     if (dist_vect[i] != 0)
 519       return i + 1;
 520
 521   return 0;
 522 }
 523
 524 #endif /* LAMBDA_H  */