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