gcc/lambda.h

   1 /* Lambda matrix and vector interface.
   2    Copyright (C) 2003, 2004, 2005 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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  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
  33 /* An integer matrix.  A matrix consists of m vectors of length n (IE
  34    all vectors are the same length).  */
  35 typedef lambda_vector *lambda_matrix;
  36
  37 /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
  38    matrix.  Rather than use floats, we simply keep a single DENOMINATOR that
  39    represents the denominator for every element in the matrix.  */
  40 typedef struct
  41 {
  42   lambda_matrix matrix;
  43   int rowsize;
  44   int colsize;
  45   int denominator;
  46 } *lambda_trans_matrix;
  47 #define LTM_MATRIX(T) ((T)->matrix)
  48 #define LTM_ROWSIZE(T) ((T)->rowsize)
  49 #define LTM_COLSIZE(T) ((T)->colsize)
  50 #define LTM_DENOMINATOR(T) ((T)->denominator)
  51
  52 /* A vector representing a statement in the body of a loop.
  53    The COEFFICIENTS vector contains a coefficient for each induction variable
  54    in the loop nest containing the statement.
  55    The DENOMINATOR represents the denominator for each coefficient in the
  56    COEFFICIENT vector.
  57
  58    This structure is used during code generation in order to rewrite the old
  59    induction variable uses in a statement in terms of the newly created
  60    induction variables.  */
  61 typedef struct
  62 {
  63   lambda_vector coefficients;
  64   int size;
  65   int denominator;
  66 } *lambda_body_vector;
  67 #define LBV_COEFFICIENTS(T) ((T)->coefficients)
  68 #define LBV_SIZE(T) ((T)->size)
  69 #define LBV_DENOMINATOR(T) ((T)->denominator)
  70
  71 /* Piecewise linear expression.
  72    This structure represents a linear expression with terms for the invariants
  73    and induction variables of a loop.
  74    COEFFICIENTS is a vector of coefficients for the induction variables, one
  75    per loop in the loop nest.
  76    CONSTANT is the constant portion of the linear expression
  77    INVARIANT_COEFFICIENTS is a vector of coefficients for the loop invariants,
  78    one per invariant.
  79    DENOMINATOR is the denominator for all of the coefficients and constants in
  80    the expression.
  81    The linear expressions can be linked together using the NEXT field, in
  82    order to represent MAX or MIN of a group of linear expressions.  */
  83 typedef struct lambda_linear_expression_s
  84 {
  85   lambda_vector coefficients;
  86   int constant;
  87   lambda_vector invariant_coefficients;
  88   int denominator;
  89   struct lambda_linear_expression_s *next;
  90 } *lambda_linear_expression;
  91
  92 #define LLE_COEFFICIENTS(T) ((T)->coefficients)
  93 #define LLE_CONSTANT(T) ((T)->constant)
  94 #define LLE_INVARIANT_COEFFICIENTS(T) ((T)->invariant_coefficients)
  95 #define LLE_DENOMINATOR(T) ((T)->denominator)
  96 #define LLE_NEXT(T) ((T)->next)
  97
  98 lambda_linear_expression lambda_linear_expression_new (int, int);
  99 void print_lambda_linear_expression (FILE *, lambda_linear_expression, int,
 100                                      int, char);
 101
 102 /* Loop structure.  Our loop structure consists of a constant representing the
 103    STEP of the loop, a set of linear expressions representing the LOWER_BOUND
 104    of the loop, a set of linear expressions representing the UPPER_BOUND of
 105    the loop, and a set of linear expressions representing the LINEAR_OFFSET of
 106    the loop.  The linear offset is a set of linear expressions that are
 107    applied to *both* the lower bound, and the upper bound.  */
 108 typedef struct lambda_loop_s
 109 {
 110   lambda_linear_expression lower_bound;
 111   lambda_linear_expression upper_bound;
 112   lambda_linear_expression linear_offset;
 113   int step;
 114 } *lambda_loop;
 115
 116 #define LL_LOWER_BOUND(T) ((T)->lower_bound)
 117 #define LL_UPPER_BOUND(T) ((T)->upper_bound)
 118 #define LL_LINEAR_OFFSET(T) ((T)->linear_offset)
 119 #define LL_STEP(T)   ((T)->step)
 120
 121 /* Loop nest structure.
 122    The loop nest structure consists of a set of loop structures (defined
 123    above) in LOOPS, along with an integer representing the DEPTH of the loop,
 124    and an integer representing the number of INVARIANTS in the loop.  Both of
 125    these integers are used to size the associated coefficient vectors in the
 126    linear expression structures.  */
 127 typedef struct
 128 {
 129   lambda_loop *loops;
 130   int depth;
 131   int invariants;
 132 } *lambda_loopnest;
 133
 134 #define LN_LOOPS(T) ((T)->loops)
 135 #define LN_DEPTH(T) ((T)->depth)
 136 #define LN_INVARIANTS(T) ((T)->invariants)
 137
 138 lambda_loopnest lambda_loopnest_new (int, int);
 139 lambda_loopnest lambda_loopnest_transform (lambda_loopnest, lambda_trans_matrix);
 140 struct loop;
 141 struct loops;
 142 bool perfect_nest_p (struct loop *);
 143 bool lambda_transform_legal_p (lambda_trans_matrix, int, varray_type);
 144 void print_lambda_loopnest (FILE *, lambda_loopnest, char);
 145
 146 #define lambda_loop_new() (lambda_loop) ggc_alloc_cleared (sizeof (struct lambda_loop_s))
 147
 148 void print_lambda_loop (FILE *, lambda_loop, int, int, char);
 149
 150 lambda_matrix lambda_matrix_new (int, int);
 151
 152 void lambda_matrix_id (lambda_matrix, int);
 153 bool lambda_matrix_id_p (lambda_matrix, int);
 154 void lambda_matrix_copy (lambda_matrix, lambda_matrix, int, int);
 155 void lambda_matrix_negate (lambda_matrix, lambda_matrix, int, int);
 156 void lambda_matrix_transpose (lambda_matrix, lambda_matrix, int, int);
 157 void lambda_matrix_add (lambda_matrix, lambda_matrix, lambda_matrix, int,
 158                         int);
 159 void lambda_matrix_add_mc (lambda_matrix, int, lambda_matrix, int,
 160                            lambda_matrix, int, int);
 161 void lambda_matrix_mult (lambda_matrix, lambda_matrix, lambda_matrix,
 162                          int, int, int);
 163 void lambda_matrix_delete_rows (lambda_matrix, int, int, int);
 164 void lambda_matrix_row_exchange (lambda_matrix, int, int);
 165 void lambda_matrix_row_add (lambda_matrix, int, int, int, int);
 166 void lambda_matrix_row_negate (lambda_matrix mat, int, int);
 167 void lambda_matrix_row_mc (lambda_matrix, int, int, int);
 168 void lambda_matrix_col_exchange (lambda_matrix, int, int, int);
 169 void lambda_matrix_col_add (lambda_matrix, int, int, int, int);
 170 void lambda_matrix_col_negate (lambda_matrix, int, int);
 171 void lambda_matrix_col_mc (lambda_matrix, int, int, int);
 172 int lambda_matrix_inverse (lambda_matrix, lambda_matrix, int);
 173 void lambda_matrix_hermite (lambda_matrix, int, lambda_matrix, lambda_matrix);
 174 void lambda_matrix_left_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
 175 void lambda_matrix_right_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
 176 int lambda_matrix_first_nz_vec (lambda_matrix, int, int, int);
 177 void lambda_matrix_project_to_null (lambda_matrix, int, int, int,
 178                                     lambda_vector);
 179 void print_lambda_matrix (FILE *, lambda_matrix, int, int);
 180
 181 lambda_trans_matrix lambda_trans_matrix_new (int, int);
 182 bool lambda_trans_matrix_nonsingular_p (lambda_trans_matrix);
 183 bool lambda_trans_matrix_fullrank_p (lambda_trans_matrix);
 184 int lambda_trans_matrix_rank (lambda_trans_matrix);
 185 lambda_trans_matrix lambda_trans_matrix_basis (lambda_trans_matrix);
 186 lambda_trans_matrix lambda_trans_matrix_padding (lambda_trans_matrix);
 187 lambda_trans_matrix lambda_trans_matrix_inverse (lambda_trans_matrix);
 188 void print_lambda_trans_matrix (FILE *, lambda_trans_matrix);
 189 void lambda_matrix_vector_mult (lambda_matrix, int, int, lambda_vector,
 190                                 lambda_vector);
 191 bool lambda_trans_matrix_id_p (lambda_trans_matrix);
 192
 193 lambda_body_vector lambda_body_vector_new (int);
 194 lambda_body_vector lambda_body_vector_compute_new (lambda_trans_matrix,
 195                                                    lambda_body_vector);
 196 void print_lambda_body_vector (FILE *, lambda_body_vector);
 197 lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *,
 198                                                  struct loop *,
 199                                                  VEC(tree,heap) **,
 200                                                  VEC(tree,heap) **,
 201                                                  bool);
 202 void lambda_loopnest_to_gcc_loopnest (struct loop *,
 203                                       VEC(tree,heap) *, VEC(tree,heap) *,
 204                                       lambda_loopnest, lambda_trans_matrix);
 205
 206
 207 static inline void lambda_vector_negate (lambda_vector, lambda_vector, int);
 208 static inline void lambda_vector_mult_const (lambda_vector, lambda_vector, int, int);
 209 static inline void lambda_vector_add (lambda_vector, lambda_vector,
 210                                       lambda_vector, int);
 211 static inline void lambda_vector_add_mc (lambda_vector, int, lambda_vector, int,
 212                                          lambda_vector, int);
 213 static inline void lambda_vector_copy (lambda_vector, lambda_vector, int);
 214 static inline bool lambda_vector_zerop (lambda_vector, int);
 215 static inline void lambda_vector_clear (lambda_vector, int);
 216 static inline bool lambda_vector_equal (lambda_vector, lambda_vector, int);
 217 static inline int lambda_vector_min_nz (lambda_vector, int, int);
 218 static inline int lambda_vector_first_nz (lambda_vector, int, int);
 219 static inline void print_lambda_vector (FILE *, lambda_vector, int);
 220
 221 /* Allocate a new vector of given SIZE.  */
 222
 223 static inline lambda_vector
 224 lambda_vector_new (int size)
 225 {
 226   return ggc_alloc_cleared (size * sizeof(int));
 227 }
 228
 229
 230
 231 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
 232    and store the result in VEC2.  */
 233
 234 static inline void
 235 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
 236                           int size, int const1)
 237 {
 238   int i;
 239
 240   if (const1 == 0)
 241     lambda_vector_clear (vec2, size);
 242   else
 243     for (i = 0; i < size; i++)
 244       vec2[i] = const1 * vec1[i];
 245 }
 246
 247 /* Negate vector VEC1 with length SIZE and store it in VEC2.  */
 248
 249 static inline void
 250 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
 251                       int size)
 252 {
 253   lambda_vector_mult_const (vec1, vec2, size, -1);
 254 }
 255
 256 /* VEC3 = VEC1+VEC2, where all three the vectors are of length SIZE.  */
 257
 258 static inline void
 259 lambda_vector_add (lambda_vector vec1, lambda_vector vec2,
 260                    lambda_vector vec3, int size)
 261 {
 262   int i;
 263   for (i = 0; i < size; i++)
 264     vec3[i] = vec1[i] + vec2[i];
 265 }
 266
 267 /* VEC3 = CONSTANT1*VEC1 + CONSTANT2*VEC2.  All vectors have length SIZE.  */
 268
 269 static inline void
 270 lambda_vector_add_mc (lambda_vector vec1, int const1,
 271                       lambda_vector vec2, int const2,
 272                       lambda_vector vec3, int size)
 273 {
 274   int i;
 275   for (i = 0; i < size; i++)
 276     vec3[i] = const1 * vec1[i] + const2 * vec2[i];
 277 }
 278
 279 /* Copy the elements of vector VEC1 with length SIZE to VEC2.  */
 280
 281 static inline void
 282 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
 283                     int size)
 284 {
 285   memcpy (vec2, vec1, size * sizeof (*vec1));
 286 }
 287
 288 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
 289
 290 static inline bool
 291 lambda_vector_zerop (lambda_vector vec1, int size)
 292 {
 293   int i;
 294   for (i = 0; i < size; i++)
 295     if (vec1[i] != 0)
 296       return false;
 297   return true;
 298 }
 299
 300 /* Clear out vector VEC1 of length SIZE.  */
 301
 302 static inline void
 303 lambda_vector_clear (lambda_vector vec1, int size)
 304 {
 305   memset (vec1, 0, size * sizeof (*vec1));
 306 }
 307
 308 /* Return true if two vectors are equal.  */
 309
 310 static inline bool
 311 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
 312 {
 313   int i;
 314   for (i = 0; i < size; i++)
 315     if (vec1[i] != vec2[i])
 316       return false;
 317   return true;
 318 }
 319
 320 /* Return the minimum nonzero element in vector VEC1 between START and N.
 321    We must have START <= N.  */
 322
 323 static inline int
 324 lambda_vector_min_nz (lambda_vector vec1, int n, int start)
 325 {
 326   int j;
 327   int min = -1;
 328
 329   gcc_assert (start <= n);
 330   for (j = start; j < n; j++)
 331     {
 332       if (vec1[j])
 333         if (min < 0 || vec1[j] < vec1[min])
 334           min = j;
 335     }
 336   gcc_assert (min >= 0);
 337
 338   return min;
 339 }
 340
 341 /* Return the first nonzero element of vector VEC1 between START and N.
 342    We must have START <= N.   Returns N if VEC1 is the zero vector.  */
 343
 344 static inline int
 345 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
 346 {
 347   int j = start;
 348   while (j < n && vec1[j] == 0)
 349     j++;
 350   return j;
 351 }
 352
 353
 354 /* Multiply a vector by a matrix.  */
 355
 356 static inline void
 357 lambda_vector_matrix_mult (lambda_vector vect, int m, lambda_matrix mat,
 358                            int n, lambda_vector dest)
 359 {
 360   int i, j;
 361   lambda_vector_clear (dest, n);
 362   for (i = 0; i < n; i++)
 363     for (j = 0; j < m; j++)
 364       dest[i] += mat[j][i] * vect[j];
 365 }
 366
 367
 368 /* Print out a vector VEC of length N to OUTFILE.  */
 369
 370 static inline void
 371 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
 372 {
 373   int i;
 374
 375   for (i = 0; i < n; i++)
 376     fprintf (outfile, "%3d ", vector[i]);
 377   fprintf (outfile, "\n");
 378 }
 379
 380 /* Returns true when the vector V is lexicographically positive, in
 381    other words, when the first nonzero element is positive.  */
 382
 383 static inline bool
 384 lambda_vector_lexico_pos (lambda_vector v,
 385                           unsigned n)
 386 {
 387   unsigned i;
 388   for (i = 0; i < n; i++)
 389     {
 390       if (v[i] == 0)
 391         continue;
 392       if (v[i] < 0)
 393         return false;
 394       if (v[i] > 0)
 395         return true;
 396     }
 397   return true;
 398 }
 399
 400 #endif /* LAMBDA_H  */
 401