2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24 * @author Sebastian Buchwald
36 pbqp_matrix *pbqp_matrix_alloc(pbqp *pbqp, unsigned rows, unsigned cols)
41 unsigned length = rows * cols;
43 pbqp_matrix *mat = obstack_alloc(&pbqp->obstack, sizeof(*mat) + sizeof(*mat->entries) * length);
48 memset(mat->entries, 0, sizeof(*mat->entries) * length);
53 pbqp_matrix *pbqp_matrix_copy(pbqp *pbqp, pbqp_matrix *m)
55 unsigned len = m->rows * m->cols;
56 pbqp_matrix *copy = obstack_copy(&pbqp->obstack, m, sizeof(*copy) + sizeof(*copy->entries) * len);
62 pbqp_matrix *pbqp_matrix_copy_and_transpose(pbqp *pbqp, pbqp_matrix *m)
66 unsigned cols = m->cols;
67 unsigned rows = m->rows;
68 unsigned len = rows * cols;
69 pbqp_matrix *copy = obstack_alloc(&pbqp->obstack, sizeof(*copy) + sizeof(*copy->entries) * len);
72 for (i = 0; i < rows; ++i) {
73 for (j = 0; j < cols; ++j) {
74 copy->entries[j*rows+i] = m->entries[i*cols+j];
84 void pbqp_matrix_transpose(pbqp *pbqp, pbqp_matrix *mat)
89 len = mat->rows * mat->cols;
91 pbqp_matrix *tmp = pbqp_matrix_copy_and_transpose(pbqp, mat);
93 memcpy(mat, tmp, sizeof(*mat) + sizeof(*mat->entries) * len);
95 obstack_free(&pbqp->obstack, tmp);
98 void pbqp_matrix_add(pbqp_matrix *sum, pbqp_matrix *summand)
105 assert(sum->cols == summand->cols);
106 assert(sum->rows == summand->rows);
108 len = sum->rows * sum->cols;
110 for (i = 0; i < len; ++i) {
111 sum->entries[i] = pbqp_add(sum->entries[i], summand->entries[i]);
115 void pbqp_matrix_set_col_value(pbqp_matrix *mat, unsigned col, num value)
121 assert(col < mat->cols);
125 for (row_index = 0; row_index < row_len; ++row_index) {
126 mat->entries[row_index * mat->cols + col] = value;
130 void pbqp_matrix_set_row_value(pbqp_matrix *mat, unsigned row, num value)
136 assert(row < mat->rows);
140 for (col_index = 0; col_index < col_len; ++col_index) {
141 mat->entries[row * mat->cols + col_index] = value;
145 void pbqp_matrix_set(pbqp_matrix *mat, unsigned row, unsigned col, num value)
148 assert(col < mat->cols);
149 assert(row < mat->rows);
151 mat->entries[row * mat->cols + col] = value;
154 num pbqp_matrix_get_col_min(pbqp_matrix *matrix, unsigned col_index, vector *flags)
161 assert(matrix->rows == flags->len);
163 unsigned col_len = matrix->cols;
164 unsigned row_len = matrix->rows;
166 for (row_index = 0; row_index < row_len; ++row_index) {
167 /* Ignore virtual deleted columns. */
168 if (flags->entries[row_index].data == INF_COSTS) continue;
170 num elem = matrix->entries[row_index * col_len + col_index];
180 unsigned pbqp_matrix_get_col_min_index(pbqp_matrix *matrix, unsigned col_index, vector *flags)
183 unsigned min_index = 0;
188 assert(matrix->rows == flags->len);
190 unsigned col_len = matrix->cols;
191 unsigned row_len = matrix->rows;
193 for (row_index = 0; row_index < row_len; ++row_index) {
194 /* Ignore virtual deleted columns. */
195 if (flags->entries[row_index].data == INF_COSTS) continue;
197 num elem = matrix->entries[row_index * col_len + col_index];
201 min_index = row_index;
208 void pbqp_matrix_sub_col_value(pbqp_matrix *matrix, unsigned col_index,
209 vector *flags, num value)
217 assert(matrix->rows == flags->len);
219 col_len = matrix->cols;
220 row_len = matrix->rows;
222 for (row_index = 0; row_index < row_len; ++row_index) {
223 if (flags->entries[row_index].data == INF_COSTS) {
224 matrix->entries[row_index * col_len + col_index] = 0;
227 /* inf - x = inf if x < inf */
228 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
231 matrix->entries[row_index * col_len + col_index] -= value;
235 num pbqp_matrix_get_row_min(pbqp_matrix *matrix, unsigned row_index, vector *flags)
242 assert(matrix->cols == flags->len);
244 unsigned len = flags->len;
246 for (col_index = 0; col_index < len; ++col_index) {
247 /* Ignore virtual deleted columns. */
248 if (flags->entries[col_index].data == INF_COSTS) continue;
250 num elem = matrix->entries[row_index * len + col_index];
260 unsigned pbqp_matrix_get_row_min_index(pbqp_matrix *matrix, unsigned row_index, vector *flags)
263 unsigned min_index = 0;
268 assert(matrix->cols == flags->len);
270 unsigned len = flags->len;
272 for (col_index = 0; col_index < len; ++col_index) {
273 /* Ignore virtual deleted columns. */
274 if (flags->entries[col_index].data == INF_COSTS) continue;
276 num elem = matrix->entries[row_index * len + col_index];
280 min_index = col_index;
287 void pbqp_matrix_sub_row_value(pbqp_matrix *matrix, unsigned row_index,
288 vector *flags, num value)
295 assert(matrix->cols == flags->len);
297 col_len = matrix->cols;
299 for (col_index = 0; col_index < col_len; ++col_index) {
300 if (flags->entries[col_index].data == INF_COSTS) {
301 matrix->entries[row_index * col_len + col_index] = 0;
304 /* inf - x = inf if x < inf */
305 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
308 matrix->entries[row_index * col_len + col_index] -= value;
312 int pbqp_matrix_is_zero(pbqp_matrix *mat, vector *src_vec, vector *tgt_vec)
322 assert(mat->cols = tgt_vec->len);
323 assert(mat->rows = src_vec->len);
328 for (row_index = 0; row_index < row_len; ++row_index) {
329 if (src_vec->entries[row_index].data == INF_COSTS) continue;
330 for (col_index = 0; col_index < col_len; ++col_index) {
331 if (tgt_vec->entries[col_index].data == INF_COSTS) continue;
333 if (mat->entries[row_index * col_len + col_index] != 0) {
342 void pbqp_matrix_add_to_all_cols(pbqp_matrix *mat, vector *vec)
351 assert(mat->rows == vec->len);
356 for (row_index = 0; row_index < row_len; ++row_index) {
357 num value = vec->entries[row_index].data;
358 for (col_index = 0; col_index < col_len; ++col_index) {
359 mat->entries[row_index * col_len + col_index] = pbqp_add(
360 mat->entries[row_index * col_len + col_index], value);
365 void pbqp_matrix_add_to_all_rows(pbqp_matrix *mat, vector *vec)
374 assert(mat->cols == vec->len);
379 for (row_index = 0; row_index < row_len; ++row_index) {
380 for (col_index = 0; col_index < col_len; ++col_index) {
381 num value = vec->entries[col_index].data;
383 mat->entries[row_index * col_len + col_index] = pbqp_add(mat->entries[row_index * col_len + col_index], value);