nsz Git - libfirm/blob - matrix.c

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