1 /* Lambda matrix and vector interface.
2 Copyright (C) 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
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
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
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, 59 Temple Place - Suite 330, Boston, MA
25 /* An integer vector. A vector formally consists of an element of a vector
26 space. A vector space is a set that is closed under vector addition
27 and scalar multiplication. In this vector space, an element is a list of
29 typedef int *lambda_vector;
30 /* An integer matrix. A matrix consists of m vectors of length n (IE
31 all vectors are the same length). */
32 typedef lambda_vector *lambda_matrix;
34 lambda_matrix lambda_matrix_new (int, int);
36 void lambda_matrix_id (lambda_matrix, int);
37 void lambda_matrix_copy (lambda_matrix, lambda_matrix, int, int);
38 void lambda_matrix_negate (lambda_matrix, lambda_matrix, int, int);
39 void lambda_matrix_transpose (lambda_matrix, lambda_matrix, int, int);
40 void lambda_matrix_add (lambda_matrix, lambda_matrix, lambda_matrix, int,
42 void lambda_matrix_add_mc (lambda_matrix, int, lambda_matrix, int,
43 lambda_matrix, int, int);
44 void lambda_matrix_mult (lambda_matrix, lambda_matrix, lambda_matrix,
46 void lambda_matrix_delete_rows (lambda_matrix, int, int, int);
47 void lambda_matrix_row_exchange (lambda_matrix, int, int);
48 void lambda_matrix_row_add (lambda_matrix, int, int, int, int);
49 void lambda_matrix_row_negate (lambda_matrix mat, int, int);
50 void lambda_matrix_row_mc (lambda_matrix, int, int, int);
51 void lambda_matrix_col_exchange (lambda_matrix, int, int, int);
52 void lambda_matrix_col_add (lambda_matrix, int, int, int, int);
53 void lambda_matrix_col_negate (lambda_matrix, int, int);
54 void lambda_matrix_col_mc (lambda_matrix, int, int, int);
55 int lambda_matrix_inverse (lambda_matrix, lambda_matrix, int);
56 void lambda_matrix_hermite (lambda_matrix, int, lambda_matrix, lambda_matrix);
57 void lambda_matrix_left_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
58 void lambda_matrix_right_hermite (lambda_matrix, int, int, lambda_matrix, lambda_matrix);
59 int lambda_matrix_first_nz_vec (lambda_matrix, int, int, int);
60 void lambda_matrix_project_to_null (lambda_matrix, int, int, int,
62 void print_lambda_matrix (FILE *, lambda_matrix, int, int);
64 void lambda_matrix_vector_mult (lambda_matrix, int, int, lambda_vector,
67 static inline void lambda_vector_negate (lambda_vector, lambda_vector, int);
68 static inline void lambda_vector_mult_const (lambda_vector, lambda_vector, int, int);
69 static inline void lambda_vector_add (lambda_vector, lambda_vector,
71 static inline void lambda_vector_add_mc (lambda_vector, int, lambda_vector, int,
73 static inline void lambda_vector_copy (lambda_vector, lambda_vector, int);
74 static inline bool lambda_vector_zerop (lambda_vector, int);
75 static inline void lambda_vector_clear (lambda_vector, int);
76 static inline bool lambda_vector_equal (lambda_vector, lambda_vector, int);
77 static inline int lambda_vector_min_nz (lambda_vector, int, int);
78 static inline int lambda_vector_first_nz (lambda_vector, int, int);
79 static inline void print_lambda_vector (FILE *, lambda_vector, int);
81 /* Allocate a new vector of given SIZE. */
83 static inline lambda_vector
84 lambda_vector_new (int size)
86 return ggc_alloc_cleared (size * sizeof(int));
91 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
92 and store the result in VEC2. */
95 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
101 lambda_vector_clear (vec2, size);
103 for (i = 0; i < size; i++)
104 vec2[i] = const1 * vec1[i];
107 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
110 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
113 lambda_vector_mult_const (vec1, vec2, size, -1);
116 /* VEC3 = VEC1+VEC2, where all three the vectors are of length SIZE. */
119 lambda_vector_add (lambda_vector vec1, lambda_vector vec2,
120 lambda_vector vec3, int size)
123 for (i = 0; i < size; i++)
124 vec3[i] = vec1[i] + vec2[i];
127 /* VEC3 = CONSTANT1*VEC1 + CONSTANT2*VEC2. All vectors have length SIZE. */
130 lambda_vector_add_mc (lambda_vector vec1, int const1,
131 lambda_vector vec2, int const2,
132 lambda_vector vec3, int size)
135 for (i = 0; i < size; i++)
136 vec3[i] = const1 * vec1[i] + const2 * vec2[i];
139 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
142 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
145 memcpy (vec2, vec1, size * sizeof (*vec1));
148 /* Return true if vector VEC1 of length SIZE is the zero vector. */
151 lambda_vector_zerop (lambda_vector vec1, int size)
154 for (i = 0; i < size; i++)
160 /* Clear out vector VEC1 of length SIZE. */
163 lambda_vector_clear (lambda_vector vec1, int size)
165 memset (vec1, 0, size * sizeof (*vec1));
168 /* Return true if two vectors are equal. */
171 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
174 for (i = 0; i < size; i++)
175 if (vec1[i] != vec2[i])
180 /* Return the minimum non-zero element in vector VEC1 between START and N.
181 We must have START <= N. */
184 lambda_vector_min_nz (lambda_vector vec1, int n, int start)
188 #ifdef ENABLE_CHECKING
192 for (j = start; j < n; j++)
195 if (min < 0 || vec1[j] < vec1[min])
205 /* Return the first nonzero element of vector VEC1 between START and N.
206 We must have START <= N. Returns N if VEC1 is the zero vector. */
209 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
212 while (j < n && vec1[j] == 0)
218 /* Multiply a vector by a matrix. */
221 lambda_vector_matrix_mult (lambda_vector vect, int m, lambda_matrix mat,
222 int n, lambda_vector dest)
225 lambda_vector_clear (dest, n);
226 for (i = 0; i < n; i++)
227 for (j = 0; j < m; j++)
228 dest[i] += mat[j][i] * vect[j];
232 /* Print out a vector VEC of length N to OUTFILE. */
235 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
239 for (i = 0; i < n; i++)
240 fprintf (outfile, "%3d ", vector[i]);
241 fprintf (outfile, "\n");
243 #endif /* LAMBDA_H */