2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
10 * @author Sebastian Buchwald
21 pbqp_matrix_t *pbqp_matrix_alloc(pbqp_t *pbqp, unsigned rows, unsigned cols)
23 unsigned length = rows * cols;
24 pbqp_matrix_t *mat = (pbqp_matrix_t*)obstack_alloc(&pbqp->obstack, sizeof(*mat) + sizeof(*mat->entries) * length);
31 memset(mat->entries, 0, sizeof(*mat->entries) * length);
36 pbqp_matrix_t *pbqp_matrix_copy(pbqp_t *pbqp, pbqp_matrix_t *m)
38 unsigned len = m->rows * m->cols;
39 pbqp_matrix_t *copy = (pbqp_matrix_t*)obstack_copy(&pbqp->obstack, m, sizeof(*copy) + sizeof(*copy->entries) * len);
45 pbqp_matrix_t *pbqp_matrix_copy_and_transpose(pbqp_t *pbqp, pbqp_matrix_t *m)
49 unsigned cols = m->cols;
50 unsigned rows = m->rows;
51 unsigned len = rows * cols;
52 pbqp_matrix_t *copy = (pbqp_matrix_t*)obstack_alloc(&pbqp->obstack, sizeof(*copy) + sizeof(*copy->entries) * len);
54 for (i = 0; i < rows; ++i) {
55 for (j = 0; j < cols; ++j) {
56 copy->entries[j*rows+i] = m->entries[i*cols+j];
66 void pbqp_matrix_transpose(pbqp_t *pbqp, pbqp_matrix_t *mat)
71 len = mat->rows * mat->cols;
73 tmp = pbqp_matrix_copy_and_transpose(pbqp, mat);
75 memcpy(mat, tmp, sizeof(*mat) + sizeof(*mat->entries) * len);
77 obstack_free(&pbqp->obstack, tmp);
80 void pbqp_matrix_add(pbqp_matrix_t *sum, pbqp_matrix_t *summand)
85 assert(sum->cols == summand->cols);
86 assert(sum->rows == summand->rows);
88 len = sum->rows * sum->cols;
90 for (i = 0; i < len; ++i) {
91 sum->entries[i] = pbqp_add(sum->entries[i], summand->entries[i]);
95 void pbqp_matrix_set_col_value(pbqp_matrix_t *mat, unsigned col, num value)
100 assert(col < mat->cols);
104 for (row_index = 0; row_index < row_len; ++row_index) {
105 mat->entries[row_index * mat->cols + col] = value;
109 void pbqp_matrix_set_row_value(pbqp_matrix_t *mat, unsigned row, num value)
114 assert(row < mat->rows);
118 for (col_index = 0; col_index < col_len; ++col_index) {
119 mat->entries[row * mat->cols + col_index] = value;
123 void pbqp_matrix_set(pbqp_matrix_t *mat, unsigned row, unsigned col, num value)
125 assert(col < mat->cols);
126 assert(row < mat->rows);
128 mat->entries[row * mat->cols + col] = value;
131 num pbqp_matrix_get_col_min(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags)
136 unsigned col_len = matrix->cols;
137 unsigned row_len = matrix->rows;
139 assert(matrix->rows == flags->len);
141 for (row_index = 0; row_index < row_len; ++row_index) {
144 /* Ignore virtual deleted columns. */
145 if (flags->entries[row_index].data == INF_COSTS) continue;
147 elem = matrix->entries[row_index * col_len + col_index];
157 unsigned pbqp_matrix_get_col_min_index(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags)
160 unsigned min_index = 0;
163 unsigned col_len = matrix->cols;
164 unsigned row_len = matrix->rows;
166 assert(matrix->rows == flags->len);
168 for (row_index = 0; row_index < row_len; ++row_index) {
171 /* Ignore virtual deleted columns. */
172 if (flags->entries[row_index].data == INF_COSTS) continue;
174 elem = matrix->entries[row_index * col_len + col_index];
178 min_index = row_index;
185 void pbqp_matrix_sub_col_value(pbqp_matrix_t *matrix, unsigned col_index,
186 vector_t *flags, num value)
192 assert(matrix->rows == flags->len);
194 col_len = matrix->cols;
195 row_len = matrix->rows;
197 for (row_index = 0; row_index < row_len; ++row_index) {
198 if (flags->entries[row_index].data == INF_COSTS) {
199 matrix->entries[row_index * col_len + col_index] = 0;
202 /* inf - x = inf if x < inf */
203 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
206 matrix->entries[row_index * col_len + col_index] -= value;
210 num pbqp_matrix_get_row_min(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags)
215 unsigned len = flags->len;
217 assert(matrix->cols == len);
219 for (col_index = 0; col_index < len; ++col_index) {
222 /* Ignore virtual deleted columns. */
223 if (flags->entries[col_index].data == INF_COSTS) continue;
225 elem = matrix->entries[row_index * len + col_index];
235 unsigned pbqp_matrix_get_row_min_index(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags)
238 unsigned min_index = 0;
241 unsigned len = flags->len;
243 assert(matrix->cols == len);
245 for (col_index = 0; col_index < len; ++col_index) {
248 /* Ignore virtual deleted columns. */
249 if (flags->entries[col_index].data == INF_COSTS) continue;
251 elem = matrix->entries[row_index * len + col_index];
255 min_index = col_index;
262 void pbqp_matrix_sub_row_value(pbqp_matrix_t *matrix, unsigned row_index,
263 vector_t *flags, num value)
268 assert(matrix->cols == flags->len);
270 col_len = matrix->cols;
272 for (col_index = 0; col_index < col_len; ++col_index) {
273 if (flags->entries[col_index].data == INF_COSTS) {
274 matrix->entries[row_index * col_len + col_index] = 0;
277 /* inf - x = inf if x < inf */
278 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
281 matrix->entries[row_index * col_len + col_index] -= value;
285 int pbqp_matrix_is_zero(pbqp_matrix_t *mat, vector_t *src_vec, vector_t *tgt_vec)
292 assert(mat->cols = tgt_vec->len);
293 assert(mat->rows = src_vec->len);
298 for (row_index = 0; row_index < row_len; ++row_index) {
299 if (src_vec->entries[row_index].data == INF_COSTS) continue;
300 for (col_index = 0; col_index < col_len; ++col_index) {
301 if (tgt_vec->entries[col_index].data == INF_COSTS) continue;
303 if (mat->entries[row_index * col_len + col_index] != 0) {
312 void pbqp_matrix_add_to_all_cols(pbqp_matrix_t *mat, vector_t *vec)
319 assert(mat->rows == vec->len);
324 for (row_index = 0; row_index < row_len; ++row_index) {
325 num value = vec->entries[row_index].data;
326 for (col_index = 0; col_index < col_len; ++col_index) {
327 mat->entries[row_index * col_len + col_index] = pbqp_add(
328 mat->entries[row_index * col_len + col_index], value);
333 void pbqp_matrix_add_to_all_rows(pbqp_matrix_t *mat, vector_t *vec)
340 assert(mat->cols == vec->len);
345 for (row_index = 0; row_index < row_len; ++row_index) {
346 for (col_index = 0; col_index < col_len; ++col_index) {
347 num value = vec->entries[col_index].data;
349 mat->entries[row_index * col_len + col_index] = pbqp_add(mat->entries[row_index * col_len + col_index], value);