1169689Skan/* Lambda matrix and vector interface. 2169689Skan Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan Contributed by Daniel Berlin <dberlin@dberlin.org> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan#ifndef LAMBDA_H 23169689Skan#define LAMBDA_H 24169689Skan 25169689Skan#include "vec.h" 26169689Skan 27169689Skan/* An integer vector. A vector formally consists of an element of a vector 28169689Skan space. A vector space is a set that is closed under vector addition 29169689Skan and scalar multiplication. In this vector space, an element is a list of 30169689Skan integers. */ 31169689Skantypedef int *lambda_vector; 32169689Skan 33169689SkanDEF_VEC_P(lambda_vector); 34169689SkanDEF_VEC_ALLOC_P(lambda_vector,heap); 35169689Skan 36169689Skan/* An integer matrix. A matrix consists of m vectors of length n (IE 37169689Skan all vectors are the same length). */ 38169689Skantypedef lambda_vector *lambda_matrix; 39169689Skan 40169689Skan/* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE 41169689Skan matrix. Rather than use floats, we simply keep a single DENOMINATOR that 42169689Skan represents the denominator for every element in the matrix. */ 43169689Skantypedef struct 44169689Skan{ 45169689Skan lambda_matrix matrix; 46169689Skan int rowsize; 47169689Skan int colsize; 48169689Skan int denominator; 49169689Skan} *lambda_trans_matrix; 50169689Skan#define LTM_MATRIX(T) ((T)->matrix) 51169689Skan#define LTM_ROWSIZE(T) ((T)->rowsize) 52169689Skan#define LTM_COLSIZE(T) ((T)->colsize) 53169689Skan#define LTM_DENOMINATOR(T) ((T)->denominator) 54169689Skan 55169689Skan/* A vector representing a statement in the body of a loop. 56169689Skan The COEFFICIENTS vector contains a coefficient for each induction variable 57169689Skan in the loop nest containing the statement. 58169689Skan The DENOMINATOR represents the denominator for each coefficient in the 59169689Skan COEFFICIENT vector. 60169689Skan 61169689Skan This structure is used during code generation in order to rewrite the old 62169689Skan induction variable uses in a statement in terms of the newly created 63169689Skan induction variables. */ 64169689Skantypedef struct 65169689Skan{ 66169689Skan lambda_vector coefficients; 67169689Skan int size; 68169689Skan int denominator; 69169689Skan} *lambda_body_vector; 70169689Skan#define LBV_COEFFICIENTS(T) ((T)->coefficients) 71169689Skan#define LBV_SIZE(T) ((T)->size) 72169689Skan#define LBV_DENOMINATOR(T) ((T)->denominator) 73169689Skan 74169689Skan/* Piecewise linear expression. 75169689Skan This structure represents a linear expression with terms for the invariants 76169689Skan and induction variables of a loop. 77169689Skan COEFFICIENTS is a vector of coefficients for the induction variables, one 78169689Skan per loop in the loop nest. 79169689Skan CONSTANT is the constant portion of the linear expression 80169689Skan INVARIANT_COEFFICIENTS is a vector of coefficients for the loop invariants, 81169689Skan one per invariant. 82169689Skan DENOMINATOR is the denominator for all of the coefficients and constants in 83169689Skan the expression. 84169689Skan The linear expressions can be linked together using the NEXT field, in 85169689Skan order to represent MAX or MIN of a group of linear expressions. */ 86169689Skantypedef struct lambda_linear_expression_s 87169689Skan{ 88169689Skan lambda_vector coefficients; 89169689Skan int constant; 90169689Skan lambda_vector invariant_coefficients; 91169689Skan int denominator; 92169689Skan struct lambda_linear_expression_s *next; 93169689Skan} *lambda_linear_expression; 94169689Skan 95169689Skan#define LLE_COEFFICIENTS(T) ((T)->coefficients) 96169689Skan#define LLE_CONSTANT(T) ((T)->constant) 97169689Skan#define LLE_INVARIANT_COEFFICIENTS(T) ((T)->invariant_coefficients) 98169689Skan#define LLE_DENOMINATOR(T) ((T)->denominator) 99169689Skan#define LLE_NEXT(T) ((T)->next) 100169689Skan 101169689Skanlambda_linear_expression lambda_linear_expression_new (int, int); 102169689Skanvoid print_lambda_linear_expression (FILE *, lambda_linear_expression, int, 103169689Skan int, char); 104169689Skan 105169689Skan/* Loop structure. Our loop structure consists of a constant representing the 106169689Skan STEP of the loop, a set of linear expressions representing the LOWER_BOUND 107169689Skan of the loop, a set of linear expressions representing the UPPER_BOUND of 108169689Skan the loop, and a set of linear expressions representing the LINEAR_OFFSET of 109169689Skan the loop. The linear offset is a set of linear expressions that are 110169689Skan applied to *both* the lower bound, and the upper bound. */ 111169689Skantypedef struct lambda_loop_s 112169689Skan{ 113169689Skan lambda_linear_expression lower_bound; 114169689Skan lambda_linear_expression upper_bound; 115169689Skan lambda_linear_expression linear_offset; 116169689Skan int step; 117169689Skan} *lambda_loop; 118169689Skan 119169689Skan#define LL_LOWER_BOUND(T) ((T)->lower_bound) 120169689Skan#define LL_UPPER_BOUND(T) ((T)->upper_bound) 121169689Skan#define LL_LINEAR_OFFSET(T) ((T)->linear_offset) 122169689Skan#define LL_STEP(T) ((T)->step) 123169689Skan 124169689Skan/* Loop nest structure. 125169689Skan The loop nest structure consists of a set of loop structures (defined 126169689Skan above) in LOOPS, along with an integer representing the DEPTH of the loop, 127169689Skan and an integer representing the number of INVARIANTS in the loop. Both of 128169689Skan these integers are used to size the associated coefficient vectors in the 129169689Skan linear expression structures. */ 130169689Skantypedef struct 131169689Skan{ 132169689Skan lambda_loop *loops; 133169689Skan int depth; 134169689Skan int invariants; 135169689Skan} *lambda_loopnest; 136169689Skan 137169689Skan#define LN_LOOPS(T) ((T)->loops) 138169689Skan#define LN_DEPTH(T) ((T)->depth) 139169689Skan#define LN_INVARIANTS(T) ((T)->invariants) 140169689Skan 141169689Skanlambda_loopnest lambda_loopnest_new (int, int); 142169689Skanlambda_loopnest lambda_loopnest_transform (lambda_loopnest, lambda_trans_matrix); 143169689Skanstruct loop; 144169689Skanstruct loops; 145169689Skanbool perfect_nest_p (struct loop *); 146169689Skanvoid print_lambda_loopnest (FILE *, lambda_loopnest, char); 147169689Skan 148169689Skan#define lambda_loop_new() (lambda_loop) ggc_alloc_cleared (sizeof (struct lambda_loop_s)) 149169689Skan 150169689Skanvoid print_lambda_loop (FILE *, lambda_loop, int, int, char); 151169689Skan 152169689Skanlambda_matrix lambda_matrix_new (int, int); 153169689Skan 154169689Skanvoid lambda_matrix_id (lambda_matrix, int); 155169689Skanbool lambda_matrix_id_p (lambda_matrix, int); 156169689Skanvoid lambda_matrix_copy (lambda_matrix, lambda_matrix, int, int); 157169689Skanvoid lambda_matrix_negate (lambda_matrix, lambda_matrix, int, int); 158169689Skanvoid lambda_matrix_transpose (lambda_matrix, lambda_matrix, int, int); 159169689Skanvoid lambda_matrix_add (lambda_matrix, lambda_matrix, lambda_matrix, int, 160169689Skan int); 161169689Skanvoid lambda_matrix_add_mc (lambda_matrix, int, lambda_matrix, int, 162169689Skan lambda_matrix, int, int); 163169689Skanvoid lambda_matrix_mult (lambda_matrix, lambda_matrix, lambda_matrix, 164169689Skan int, int, int); 165169689Skanvoid lambda_matrix_delete_rows (lambda_matrix, int, int, int); 166169689Skanvoid lambda_matrix_row_exchange (lambda_matrix, int, int); 167169689Skanvoid lambda_matrix_row_add (lambda_matrix, int, int, int, int); 168169689Skanvoid lambda_matrix_row_negate (lambda_matrix mat, int, int); 169169689Skanvoid lambda_matrix_row_mc (lambda_matrix, int, int, int); 170169689Skanvoid lambda_matrix_col_exchange (lambda_matrix, int, int, int); 171169689Skanvoid lambda_matrix_col_add (lambda_matrix, int, int, int, int); 172169689Skanvoid lambda_matrix_col_negate (lambda_matrix, int, int); 173169689Skanvoid lambda_matrix_col_mc (lambda_matrix, int, int, int); 174169689Skanint lambda_matrix_inverse (lambda_matrix, lambda_matrix, int); 175169689Skanvoid lambda_matrix_hermite (lambda_matrix, int, lambda_matrix, lambda_matrix); 176169689Skanvoid lambda_matrix_left_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix); 177169689Skanvoid lambda_matrix_right_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix); 178169689Skanint lambda_matrix_first_nz_vec (lambda_matrix, int, int, int); 179169689Skanvoid lambda_matrix_project_to_null (lambda_matrix, int, int, int, 180169689Skan lambda_vector); 181169689Skanvoid print_lambda_matrix (FILE *, lambda_matrix, int, int); 182169689Skan 183169689Skanlambda_trans_matrix lambda_trans_matrix_new (int, int); 184169689Skanbool lambda_trans_matrix_nonsingular_p (lambda_trans_matrix); 185169689Skanbool lambda_trans_matrix_fullrank_p (lambda_trans_matrix); 186169689Skanint lambda_trans_matrix_rank (lambda_trans_matrix); 187169689Skanlambda_trans_matrix lambda_trans_matrix_basis (lambda_trans_matrix); 188169689Skanlambda_trans_matrix lambda_trans_matrix_padding (lambda_trans_matrix); 189169689Skanlambda_trans_matrix lambda_trans_matrix_inverse (lambda_trans_matrix); 190169689Skanvoid print_lambda_trans_matrix (FILE *, lambda_trans_matrix); 191169689Skanvoid lambda_matrix_vector_mult (lambda_matrix, int, int, lambda_vector, 192169689Skan lambda_vector); 193169689Skanbool lambda_trans_matrix_id_p (lambda_trans_matrix); 194169689Skan 195169689Skanlambda_body_vector lambda_body_vector_new (int); 196169689Skanlambda_body_vector lambda_body_vector_compute_new (lambda_trans_matrix, 197169689Skan lambda_body_vector); 198169689Skanvoid print_lambda_body_vector (FILE *, lambda_body_vector); 199169689Skanlambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *, 200169689Skan struct loop *, 201169689Skan VEC(tree,heap) **, 202169689Skan VEC(tree,heap) **); 203169689Skanvoid lambda_loopnest_to_gcc_loopnest (struct loop *, 204169689Skan VEC(tree,heap) *, VEC(tree,heap) *, 205169689Skan lambda_loopnest, lambda_trans_matrix); 206169689Skan 207169689Skan 208169689Skanstatic inline void lambda_vector_negate (lambda_vector, lambda_vector, int); 209169689Skanstatic inline void lambda_vector_mult_const (lambda_vector, lambda_vector, int, int); 210169689Skanstatic inline void lambda_vector_add (lambda_vector, lambda_vector, 211169689Skan lambda_vector, int); 212169689Skanstatic inline void lambda_vector_add_mc (lambda_vector, int, lambda_vector, int, 213169689Skan lambda_vector, int); 214169689Skanstatic inline void lambda_vector_copy (lambda_vector, lambda_vector, int); 215169689Skanstatic inline bool lambda_vector_zerop (lambda_vector, int); 216169689Skanstatic inline void lambda_vector_clear (lambda_vector, int); 217169689Skanstatic inline bool lambda_vector_equal (lambda_vector, lambda_vector, int); 218169689Skanstatic inline int lambda_vector_min_nz (lambda_vector, int, int); 219169689Skanstatic inline int lambda_vector_first_nz (lambda_vector, int, int); 220169689Skanstatic inline void print_lambda_vector (FILE *, lambda_vector, int); 221169689Skan 222169689Skan/* Allocate a new vector of given SIZE. */ 223169689Skan 224169689Skanstatic inline lambda_vector 225169689Skanlambda_vector_new (int size) 226169689Skan{ 227169689Skan return GGC_CNEWVEC (int, size); 228169689Skan} 229169689Skan 230169689Skan 231169689Skan 232169689Skan/* Multiply vector VEC1 of length SIZE by a constant CONST1, 233169689Skan and store the result in VEC2. */ 234169689Skan 235169689Skanstatic inline void 236169689Skanlambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2, 237169689Skan int size, int const1) 238169689Skan{ 239169689Skan int i; 240169689Skan 241169689Skan if (const1 == 0) 242169689Skan lambda_vector_clear (vec2, size); 243169689Skan else 244169689Skan for (i = 0; i < size; i++) 245169689Skan vec2[i] = const1 * vec1[i]; 246169689Skan} 247169689Skan 248169689Skan/* Negate vector VEC1 with length SIZE and store it in VEC2. */ 249169689Skan 250169689Skanstatic inline void 251169689Skanlambda_vector_negate (lambda_vector vec1, lambda_vector vec2, 252169689Skan int size) 253169689Skan{ 254169689Skan lambda_vector_mult_const (vec1, vec2, size, -1); 255169689Skan} 256169689Skan 257169689Skan/* VEC3 = VEC1+VEC2, where all three the vectors are of length SIZE. */ 258169689Skan 259169689Skanstatic inline void 260169689Skanlambda_vector_add (lambda_vector vec1, lambda_vector vec2, 261169689Skan lambda_vector vec3, int size) 262169689Skan{ 263169689Skan int i; 264169689Skan for (i = 0; i < size; i++) 265169689Skan vec3[i] = vec1[i] + vec2[i]; 266169689Skan} 267169689Skan 268169689Skan/* VEC3 = CONSTANT1*VEC1 + CONSTANT2*VEC2. All vectors have length SIZE. */ 269169689Skan 270169689Skanstatic inline void 271169689Skanlambda_vector_add_mc (lambda_vector vec1, int const1, 272169689Skan lambda_vector vec2, int const2, 273169689Skan lambda_vector vec3, int size) 274169689Skan{ 275169689Skan int i; 276169689Skan for (i = 0; i < size; i++) 277169689Skan vec3[i] = const1 * vec1[i] + const2 * vec2[i]; 278169689Skan} 279169689Skan 280169689Skan/* Copy the elements of vector VEC1 with length SIZE to VEC2. */ 281169689Skan 282169689Skanstatic inline void 283169689Skanlambda_vector_copy (lambda_vector vec1, lambda_vector vec2, 284169689Skan int size) 285169689Skan{ 286169689Skan memcpy (vec2, vec1, size * sizeof (*vec1)); 287169689Skan} 288169689Skan 289169689Skan/* Return true if vector VEC1 of length SIZE is the zero vector. */ 290169689Skan 291169689Skanstatic inline bool 292169689Skanlambda_vector_zerop (lambda_vector vec1, int size) 293169689Skan{ 294169689Skan int i; 295169689Skan for (i = 0; i < size; i++) 296169689Skan if (vec1[i] != 0) 297169689Skan return false; 298169689Skan return true; 299169689Skan} 300169689Skan 301169689Skan/* Clear out vector VEC1 of length SIZE. */ 302169689Skan 303169689Skanstatic inline void 304169689Skanlambda_vector_clear (lambda_vector vec1, int size) 305169689Skan{ 306169689Skan memset (vec1, 0, size * sizeof (*vec1)); 307169689Skan} 308169689Skan 309169689Skan/* Return true if two vectors are equal. */ 310169689Skan 311169689Skanstatic inline bool 312169689Skanlambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size) 313169689Skan{ 314169689Skan int i; 315169689Skan for (i = 0; i < size; i++) 316169689Skan if (vec1[i] != vec2[i]) 317169689Skan return false; 318169689Skan return true; 319169689Skan} 320169689Skan 321169689Skan/* Return the minimum nonzero element in vector VEC1 between START and N. 322169689Skan We must have START <= N. */ 323169689Skan 324169689Skanstatic inline int 325169689Skanlambda_vector_min_nz (lambda_vector vec1, int n, int start) 326169689Skan{ 327169689Skan int j; 328169689Skan int min = -1; 329169689Skan 330169689Skan gcc_assert (start <= n); 331169689Skan for (j = start; j < n; j++) 332169689Skan { 333169689Skan if (vec1[j]) 334169689Skan if (min < 0 || vec1[j] < vec1[min]) 335169689Skan min = j; 336169689Skan } 337169689Skan gcc_assert (min >= 0); 338169689Skan 339169689Skan return min; 340169689Skan} 341169689Skan 342169689Skan/* Return the first nonzero element of vector VEC1 between START and N. 343169689Skan We must have START <= N. Returns N if VEC1 is the zero vector. */ 344169689Skan 345169689Skanstatic inline int 346169689Skanlambda_vector_first_nz (lambda_vector vec1, int n, int start) 347169689Skan{ 348169689Skan int j = start; 349169689Skan while (j < n && vec1[j] == 0) 350169689Skan j++; 351169689Skan return j; 352169689Skan} 353169689Skan 354169689Skan 355169689Skan/* Multiply a vector by a matrix. */ 356169689Skan 357169689Skanstatic inline void 358169689Skanlambda_vector_matrix_mult (lambda_vector vect, int m, lambda_matrix mat, 359169689Skan int n, lambda_vector dest) 360169689Skan{ 361169689Skan int i, j; 362169689Skan lambda_vector_clear (dest, n); 363169689Skan for (i = 0; i < n; i++) 364169689Skan for (j = 0; j < m; j++) 365169689Skan dest[i] += mat[j][i] * vect[j]; 366169689Skan} 367169689Skan 368169689Skan 369169689Skan/* Print out a vector VEC of length N to OUTFILE. */ 370169689Skan 371169689Skanstatic inline void 372169689Skanprint_lambda_vector (FILE * outfile, lambda_vector vector, int n) 373169689Skan{ 374169689Skan int i; 375169689Skan 376169689Skan for (i = 0; i < n; i++) 377169689Skan fprintf (outfile, "%3d ", vector[i]); 378169689Skan fprintf (outfile, "\n"); 379169689Skan} 380169689Skan 381169689Skan/* Compute the greatest common divisor of two numbers using 382169689Skan Euclid's algorithm. */ 383169689Skan 384169689Skanstatic inline int 385169689Skangcd (int a, int b) 386169689Skan{ 387169689Skan int x, y, z; 388169689Skan 389169689Skan x = abs (a); 390169689Skan y = abs (b); 391169689Skan 392169689Skan while (x > 0) 393169689Skan { 394169689Skan z = y % x; 395169689Skan y = x; 396169689Skan x = z; 397169689Skan } 398169689Skan 399169689Skan return y; 400169689Skan} 401169689Skan 402169689Skan/* Compute the greatest common divisor of a VECTOR of SIZE numbers. */ 403169689Skan 404169689Skanstatic inline int 405169689Skanlambda_vector_gcd (lambda_vector vector, int size) 406169689Skan{ 407169689Skan int i; 408169689Skan int gcd1 = 0; 409169689Skan 410169689Skan if (size > 0) 411169689Skan { 412169689Skan gcd1 = vector[0]; 413169689Skan for (i = 1; i < size; i++) 414169689Skan gcd1 = gcd (gcd1, vector[i]); 415169689Skan } 416169689Skan return gcd1; 417169689Skan} 418169689Skan 419169689Skan/* Returns true when the vector V is lexicographically positive, in 420169689Skan other words, when the first nonzero element is positive. */ 421169689Skan 422169689Skanstatic inline bool 423169689Skanlambda_vector_lexico_pos (lambda_vector v, 424169689Skan unsigned n) 425169689Skan{ 426169689Skan unsigned i; 427169689Skan for (i = 0; i < n; i++) 428169689Skan { 429169689Skan if (v[i] == 0) 430169689Skan continue; 431169689Skan if (v[i] < 0) 432169689Skan return false; 433169689Skan if (v[i] > 0) 434169689Skan return true; 435169689Skan } 436169689Skan return true; 437169689Skan} 438169689Skan 439169689Skan#endif /* LAMBDA_H */ 440169689Skan 441