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                                       lambda_loopnest, lambda_trans_matrix,
 210                                       struct obstack *);
 211
 212 static inline void lambda_vector_negate (lambda_vector, lambda_vector, int);
 213 static inline void lambda_vector_mult_const (lambda_vector, lambda_vector, int, int);
 214 static inline void lambda_vector_add (lambda_vector, lambda_vector,
 215                                       lambda_vector, int);
 216 static inline void lambda_vector_add_mc (lambda_vector, int, lambda_vector, int,
 217                                          lambda_vector, int);
 218 static inline void lambda_vector_copy (lambda_vector, lambda_vector, int);
 219 static inline bool lambda_vector_zerop (lambda_vector, int);
 220 static inline void lambda_vector_clear (lambda_vector, int);
 221 static inline bool lambda_vector_equal (lambda_vector, lambda_vector, int);
 222 static inline int lambda_vector_min_nz (lambda_vector, int, int);
 223 static inline int lambda_vector_first_nz (lambda_vector, int, int);
 224 static inline void print_lambda_vector (FILE *, lambda_vector, int);
 225
 226 /* Allocate a new vector of given SIZE.  */
 227
 228 static inline lambda_vector
 229 lambda_vector_new (int size)
 230 {
 231   return GGC_CNEWVEC (int, size);
 232 }
 233
 234
 235
 236 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
 237    and store the result in VEC2.  */
 238
 239 static inline void
 240 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
 241                           int size, int const1)
 242 {
 243   int i;
 244
 245   if (const1 == 0)
 246     lambda_vector_clear (vec2, size);
 247   else
 248     for (i = 0; i < size; i++)
 249       vec2[i] = const1 * vec1[i];
 250 }
 251
 252 /* Negate vector VEC1 with length SIZE and store it in VEC2.  */
 253
 254 static inline void
 255 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
 256                       int size)
 257 {
 258   lambda_vector_mult_const (vec1, vec2, size, -1);
 259 }
 260
 261 /* VEC3 = VEC1+VEC2, where all three the vectors are of length SIZE.  */
 262
 263 static inline void
 264 lambda_vector_add (lambda_vector vec1, lambda_vector vec2,
 265                    lambda_vector vec3, int size)
 266 {
 267   int i;
 268   for (i = 0; i < size; i++)
 269     vec3[i] = vec1[i] + vec2[i];
 270 }
 271
 272 /* VEC3 = CONSTANT1*VEC1 + CONSTANT2*VEC2.  All vectors have length SIZE.  */
 273
 274 static inline void
 275 lambda_vector_add_mc (lambda_vector vec1, int const1,
 276                       lambda_vector vec2, int const2,
 277                       lambda_vector vec3, int size)
 278 {
 279   int i;
 280   for (i = 0; i < size; i++)
 281     vec3[i] = const1 * vec1[i] + const2 * vec2[i];
 282 }
 283
 284 /* Copy the elements of vector VEC1 with length SIZE to VEC2.  */
 285
 286 static inline void
 287 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
 288                     int size)
 289 {
 290   memcpy (vec2, vec1, size * sizeof (*vec1));
 291 }
 292
 293 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
 294
 295 static inline bool
 296 lambda_vector_zerop (lambda_vector vec1, int size)
 297 {
 298   int i;
 299   for (i = 0; i < size; i++)
 300     if (vec1[i] != 0)
 301       return false;
 302   return true;
 303 }
 304
 305 /* Clear out vector VEC1 of length SIZE.  */
 306
 307 static inline void
 308 lambda_vector_clear (lambda_vector vec1, int size)
 309 {
 310   memset (vec1, 0, size * sizeof (*vec1));
 311 }
 312
 313 /* Return true if two vectors are equal.  */
 314
 315 static inline bool
 316 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
 317 {
 318   int i;
 319   for (i = 0; i < size; i++)
 320     if (vec1[i] != vec2[i])
 321       return false;
 322   return true;
 323 }
 324
 325 /* Return the minimum nonzero element in vector VEC1 between START and N.
 326    We must have START <= N.  */
 327
 328 static inline int
 329 lambda_vector_min_nz (lambda_vector vec1, int n, int start)
 330 {
 331   int j;
 332   int min = -1;
 333
 334   gcc_assert (start <= n);
 335   for (j = start; j < n; j++)
 336     {
 337       if (vec1[j])
 338         if (min < 0 || vec1[j] < vec1[min])
 339           min = j;
 340     }
 341   gcc_assert (min >= 0);
 342
 343   return min;
 344 }
 345
 346 /* Return the first nonzero element of vector VEC1 between START and N.
 347    We must have START <= N.   Returns N if VEC1 is the zero vector.  */
 348
 349 static inline int
 350 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
 351 {
 352   int j = start;
 353   while (j < n && vec1[j] == 0)
 354     j++;
 355   return j;
 356 }
 357
 358
 359 /* Multiply a vector by a matrix.  */
 360
 361 static inline void
 362 lambda_vector_matrix_mult (lambda_vector vect, int m, lambda_matrix mat,
 363                            int n, lambda_vector dest)
 364 {
 365   int i, j;
 366   lambda_vector_clear (dest, n);
 367   for (i = 0; i < n; i++)
 368     for (j = 0; j < m; j++)
 369       dest[i] += mat[j][i] * vect[j];
 370 }
 371
 372
 373 /* Print out a vector VEC of length N to OUTFILE.  */
 374
 375 static inline void
 376 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
 377 {
 378   int i;
 379
 380   for (i = 0; i < n; i++)
 381     fprintf (outfile, "%3d ", vector[i]);
 382   fprintf (outfile, "\n");
 383 }
 384
 385 /* Compute the greatest common divisor of two numbers using
 386    Euclid's algorithm.  */
 387
 388 static inline int
 389 gcd (int a, int b)
 390 {
 391   int x, y, z;
 392
 393   x = abs (a);
 394   y = abs (b);
 395
 396   while (x > 0)
 397     {
 398       z = y % x;
 399       y = x;
 400       x = z;
 401     }
 402
 403   return y;
 404 }
 405
 406 /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
 407
 408 static inline int
 409 lambda_vector_gcd (lambda_vector vector, int size)
 410 {
 411   int i;
 412   int gcd1 = 0;
 413
 414   if (size > 0)
 415     {
 416       gcd1 = vector[0];
 417       for (i = 1; i < size; i++)
 418         gcd1 = gcd (gcd1, vector[i]);
 419     }
 420   return gcd1;
 421 }
 422
 423 /* Returns true when the vector V is lexicographically positive, in
 424    other words, when the first nonzero element is positive.  */
 425
 426 static inline bool
 427 lambda_vector_lexico_pos (lambda_vector v,
 428                           unsigned n)
 429 {
 430   unsigned i;
 431   for (i = 0; i < n; i++)
 432     {
 433       if (v[i] == 0)
 434         continue;
 435       if (v[i] < 0)
 436         return false;
 437       if (v[i] > 0)
 438         return true;
 439     }
 440   return true;
 441 }
 442
 443 /* Given a vector of induction variables IVS, and a vector of
 444    coefficients COEFS, build a tree that is a linear combination of
 445    the induction variables.  */
 446
 447 static inline tree
 448 build_linear_expr (tree type, lambda_vector coefs, VEC (tree, heap) *ivs)
 449 {
 450   unsigned i;
 451   tree iv;
 452   tree expr = fold_convert (type, integer_zero_node);
 453
 454   for (i = 0; VEC_iterate (tree, ivs, i, iv); i++)
 455     {
 456       int k = coefs[i];
 457
 458       if (k == 1)
 459         expr = fold_build2 (PLUS_EXPR, type, expr, iv);
 460
 461       else if (k != 0)
 462         expr = fold_build2 (PLUS_EXPR, type, expr,
 463                             fold_build2 (MULT_EXPR, type, iv,
 464                                          build_int_cst (type, k)));
 465     }
 466
 467   return expr;
 468 }
 469
 470 #endif /* LAMBDA_H  */
 471