nsz Git - libfirm/blob - matrix.c

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