nsz Git - libfirm/blob - ir/kaps/matrix.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   PBQP matrix.
   9  * @date    02.10.2008
  10  * @author  Sebastian Buchwald
  11  */
  12 #include "config.h"
  13
  14 #include <assert.h>
  15 #include <string.h>
  16
  17 #include "pbqp_t.h"
  18 #include "vector.h"
  19 #include "matrix.h"
  20
  21 pbqp_matrix_t *pbqp_matrix_alloc(pbqp_t *pbqp, unsigned rows, unsigned cols)
  22 {
  23         unsigned length = rows * cols;
  24         pbqp_matrix_t *mat = (pbqp_matrix_t*)obstack_alloc(&pbqp->obstack, sizeof(*mat) + sizeof(*mat->entries) * length);
  25
  26         assert(cols > 0);
  27         assert(rows > 0);
  28
  29         mat->cols = cols;
  30         mat->rows = rows;
  31         memset(mat->entries, 0, sizeof(*mat->entries) * length);
  32
  33         return mat;
  34 }
  35
  36 pbqp_matrix_t *pbqp_matrix_copy(pbqp_t *pbqp, pbqp_matrix_t *m)
  37 {
  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);
  40         assert(copy);
  41
  42         return copy;
  43 }
  44
  45 pbqp_matrix_t *pbqp_matrix_copy_and_transpose(pbqp_t *pbqp, pbqp_matrix_t *m)
  46 {
  47         unsigned       i;
  48         unsigned       j;
  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);
  53
  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];
  57                 }
  58         }
  59
  60         copy->cols = rows;
  61         copy->rows = cols;
  62
  63         return copy;
  64 }
  65
  66 void pbqp_matrix_transpose(pbqp_t *pbqp, pbqp_matrix_t *mat)
  67 {
  68         unsigned len;
  69         pbqp_matrix_t *tmp;
  70
  71         len = mat->rows * mat->cols;
  72
  73         tmp = pbqp_matrix_copy_and_transpose(pbqp, mat);
  74
  75         memcpy(mat, tmp, sizeof(*mat) + sizeof(*mat->entries) * len);
  76
  77         obstack_free(&pbqp->obstack, tmp);
  78 }
  79
  80 void pbqp_matrix_add(pbqp_matrix_t *sum, pbqp_matrix_t *summand)
  81 {
  82         int i;
  83         int len;
  84
  85         assert(sum->cols == summand->cols);
  86         assert(sum->rows == summand->rows);
  87
  88         len = sum->rows * sum->cols;
  89
  90         for (i = 0; i < len; ++i) {
  91                 sum->entries[i] = pbqp_add(sum->entries[i], summand->entries[i]);
  92         }
  93 }
  94
  95 void pbqp_matrix_set_col_value(pbqp_matrix_t *mat, unsigned col, num value)
  96 {
  97         unsigned row_index;
  98         unsigned row_len;
  99
 100         assert(col < mat->cols);
 101
 102         row_len = mat->rows;
 103
 104         for (row_index = 0; row_index < row_len; ++row_index) {
 105                 mat->entries[row_index * mat->cols + col] = value;
 106         }
 107 }
 108
 109 void pbqp_matrix_set_row_value(pbqp_matrix_t *mat, unsigned row, num value)
 110 {
 111         unsigned col_index;
 112         unsigned col_len;
 113
 114         assert(row < mat->rows);
 115
 116         col_len = mat->cols;
 117
 118         for (col_index = 0; col_index < col_len; ++col_index) {
 119                 mat->entries[row * mat->cols + col_index] = value;
 120         }
 121 }
 122
 123 void pbqp_matrix_set(pbqp_matrix_t *mat, unsigned row, unsigned col, num value)
 124 {
 125         assert(col < mat->cols);
 126         assert(row < mat->rows);
 127
 128         mat->entries[row * mat->cols + col] = value;
 129 }
 130
 131 num pbqp_matrix_get_col_min(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags)
 132 {
 133         unsigned row_index;
 134         num min = INF_COSTS;
 135
 136         unsigned col_len = matrix->cols;
 137         unsigned row_len = matrix->rows;
 138
 139         assert(matrix->rows == flags->len);
 140
 141         for (row_index = 0; row_index < row_len; ++row_index) {
 142                 num elem;
 143
 144                 /* Ignore virtual deleted columns. */
 145                 if (flags->entries[row_index].data == INF_COSTS) continue;
 146
 147                 elem = matrix->entries[row_index * col_len + col_index];
 148
 149                 if (elem < min) {
 150                         min = elem;
 151                 }
 152         }
 153
 154         return min;
 155 }
 156
 157 unsigned pbqp_matrix_get_col_min_index(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags)
 158 {
 159         unsigned row_index;
 160         unsigned min_index = 0;
 161         num      min       = INF_COSTS;
 162
 163         unsigned col_len = matrix->cols;
 164         unsigned row_len = matrix->rows;
 165
 166         assert(matrix->rows == flags->len);
 167
 168         for (row_index = 0; row_index < row_len; ++row_index) {
 169                 num elem;
 170
 171                 /* Ignore virtual deleted columns. */
 172                 if (flags->entries[row_index].data == INF_COSTS) continue;
 173
 174                 elem = matrix->entries[row_index * col_len + col_index];
 175
 176                 if (elem < min) {
 177                         min = elem;
 178                         min_index = row_index;
 179                 }
 180         }
 181
 182         return min_index;
 183 }
 184
 185 void pbqp_matrix_sub_col_value(pbqp_matrix_t *matrix, unsigned col_index,
 186                 vector_t *flags, num value)
 187 {
 188         unsigned col_len;
 189         unsigned row_index;
 190         unsigned row_len;
 191
 192         assert(matrix->rows == flags->len);
 193
 194         col_len = matrix->cols;
 195         row_len = matrix->rows;
 196
 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;
 200                         continue;
 201                 }
 202                 /* inf - x = inf if x < inf */
 203                 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
 204                                 != INF_COSTS)
 205                         continue;
 206                 matrix->entries[row_index * col_len + col_index] -= value;
 207         }
 208 }
 209
 210 num pbqp_matrix_get_row_min(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags)
 211 {
 212         unsigned col_index;
 213         num min = INF_COSTS;
 214
 215         unsigned len = flags->len;
 216
 217         assert(matrix->cols == len);
 218
 219         for (col_index = 0; col_index < len; ++col_index) {
 220                 num elem;
 221
 222                 /* Ignore virtual deleted columns. */
 223                 if (flags->entries[col_index].data == INF_COSTS) continue;
 224
 225                 elem = matrix->entries[row_index * len + col_index];
 226
 227                 if (elem < min) {
 228                         min = elem;
 229                 }
 230         }
 231
 232         return min;
 233 }
 234
 235 unsigned pbqp_matrix_get_row_min_index(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags)
 236 {
 237         unsigned col_index;
 238         unsigned min_index = 0;
 239         num      min       = INF_COSTS;
 240
 241         unsigned len = flags->len;
 242
 243         assert(matrix->cols == len);
 244
 245         for (col_index = 0; col_index < len; ++col_index) {
 246                 num elem;
 247
 248                 /* Ignore virtual deleted columns. */
 249                 if (flags->entries[col_index].data == INF_COSTS) continue;
 250
 251                 elem = matrix->entries[row_index * len + col_index];
 252
 253                 if (elem < min) {
 254                         min = elem;
 255                         min_index = col_index;
 256                 }
 257         }
 258
 259         return min_index;
 260 }
 261
 262 void pbqp_matrix_sub_row_value(pbqp_matrix_t *matrix, unsigned row_index,
 263                 vector_t *flags, num value)
 264 {
 265         unsigned col_index;
 266         unsigned col_len;
 267
 268         assert(matrix->cols == flags->len);
 269
 270         col_len = matrix->cols;
 271
 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;
 275                         continue;
 276                 }
 277                 /* inf - x = inf if x < inf */
 278                 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
 279                                 != INF_COSTS)
 280                         continue;
 281                 matrix->entries[row_index * col_len + col_index] -= value;
 282         }
 283 }
 284
 285 int pbqp_matrix_is_zero(pbqp_matrix_t *mat, vector_t *src_vec, vector_t *tgt_vec)
 286 {
 287         unsigned col_index;
 288         unsigned col_len;
 289         unsigned row_index;
 290         unsigned row_len;
 291
 292         assert(mat->cols = tgt_vec->len);
 293         assert(mat->rows = src_vec->len);
 294
 295         col_len = mat->cols;
 296         row_len = mat->rows;
 297
 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;
 302
 303                         if (mat->entries[row_index * col_len + col_index] != 0) {
 304                                 return 0;
 305                         }
 306                 }
 307         }
 308
 309         return 1;
 310 }
 311
 312 void pbqp_matrix_add_to_all_cols(pbqp_matrix_t *mat, vector_t *vec)
 313 {
 314         unsigned col_index;
 315         unsigned col_len;
 316         unsigned row_index;
 317         unsigned row_len;
 318
 319         assert(mat->rows == vec->len);
 320
 321         col_len = mat->cols;
 322         row_len = mat->rows;
 323
 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);
 329                 }
 330         }
 331 }
 332
 333 void pbqp_matrix_add_to_all_rows(pbqp_matrix_t *mat, vector_t *vec)
 334 {
 335         unsigned col_index;
 336         unsigned col_len;
 337         unsigned row_index;
 338         unsigned row_len;
 339
 340         assert(mat->cols == vec->len);
 341
 342         col_len = mat->cols;
 343         row_len = mat->rows;
 344
 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;
 348
 349                         mat->entries[row_index * col_len + col_index] = pbqp_add(mat->entries[row_index * col_len + col_index], value);
 350                 }
 351         }
 352 }