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_add(pbqp_matrix *sum, pbqp_matrix *summand)
  56 {
  57         int i;
  58         int len;
  59
  60         assert(sum);
  61         assert(summand);
  62         assert(sum->cols == summand->cols);
  63         assert(sum->rows == summand->rows);
  64
  65         len = sum->rows * sum->cols;
  66
  67         for (i = 0; i < len; ++i) {
  68                 sum->entries[i] = pbqp_add(sum->entries[i], summand->entries[i]);
  69         }
  70 }
  71
  72 void pbqp_matrix_set(pbqp_matrix *mat, unsigned row, unsigned col, num value)
  73 {
  74         assert(mat);
  75         assert(col < mat->cols);
  76         assert(row < mat->rows);
  77
  78         mat->entries[row * mat->cols + col] = value;
  79 }
  80
  81 num pbqp_matrix_get_col_min(pbqp_matrix *matrix, unsigned col_index, vector *flags)
  82 {
  83         unsigned row_index;
  84         num min = INF_COSTS;
  85
  86         assert(matrix);
  87         assert(flags);
  88         assert(matrix->rows == flags->len);
  89
  90         unsigned col_len = matrix->cols;
  91         unsigned row_len = matrix->rows;
  92
  93         for (row_index = 0; row_index < row_len; ++row_index) {
  94                 /* Ignore virtual deleted columns. */
  95                 if (flags->entries[row_index].data == INF_COSTS) continue;
  96
  97                 num elem = matrix->entries[row_index * col_len + col_index];
  98
  99                 if (elem < min) {
 100                         min = elem;
 101                 }
 102         }
 103
 104         return min;
 105 }
 106
 107 void pbqp_matrix_sub_col_value(pbqp_matrix *matrix, unsigned col_index,
 108                 vector *flags, num value)
 109 {
 110         unsigned row_index;
 111
 112         assert(matrix);
 113         assert(flags);
 114         assert(matrix->rows == flags->len);
 115
 116         unsigned col_len = matrix->cols;
 117         unsigned row_len = matrix->rows;
 118
 119         for (row_index = 0; row_index < row_len; ++row_index) {
 120                 /* inf - x = inf if x < inf */
 121                 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
 122                                 != INF_COSTS)
 123                         continue;
 124                 matrix->entries[row_index * col_len + col_index] -= value;
 125         }
 126 }
 127
 128 num pbqp_matrix_get_row_min(pbqp_matrix *matrix, unsigned row_index, vector *flags)
 129 {
 130         unsigned col_index;
 131         num min = INF_COSTS;
 132
 133         assert(matrix);
 134         assert(flags);
 135         assert(matrix->cols == flags->len);
 136
 137         unsigned len = flags->len;
 138
 139         for (col_index = 0; col_index < len; ++col_index) {
 140                 /* Ignore virtual deleted columns. */
 141                 if (flags->entries[col_index].data == INF_COSTS) continue;
 142
 143                 num elem = matrix->entries[row_index * len + col_index];
 144
 145                 if (elem < min) {
 146                         min = elem;
 147                 }
 148         }
 149
 150         return min;
 151 }
 152
 153 void pbqp_matrix_sub_row_value(pbqp_matrix *matrix, unsigned row_index,
 154                 vector *flags, num value)
 155 {
 156         unsigned col_index;
 157
 158         assert(matrix);
 159         assert(flags);
 160         assert(matrix->cols == flags->len);
 161
 162         unsigned len = flags->len;
 163
 164         for (col_index = 0; col_index < len; ++col_index) {
 165                 /* inf - x = inf if x < inf */
 166                 if (matrix->entries[row_index * len + col_index] == INF_COSTS && value
 167                                 != INF_COSTS)
 168                         continue;
 169                 matrix->entries[row_index * len + col_index] -= value;
 170         }
 171 }
 172
 173 int pbqp_matrix_is_zero(pbqp_matrix *mat, vector *src_vec, vector *tgt_vec)
 174 {
 175         unsigned col_index;
 176         unsigned col_len;
 177         unsigned row_index;
 178         unsigned row_len;
 179
 180         assert(mat);
 181         assert(src_vec);
 182         assert(tgt_vec);
 183         assert(mat->cols = tgt_vec->len);
 184         assert(mat->rows = src_vec->len);
 185
 186         col_len = mat->cols;
 187         row_len = mat->rows;
 188
 189         for (row_index = 0; row_index < row_len; ++row_index) {
 190                 if (src_vec->entries[row_index].data == INF_COSTS) continue;
 191                 for (col_index = 0; col_index < col_len; ++col_index) {
 192                         if (tgt_vec->entries[col_index].data == INF_COSTS) continue;
 193
 194                         if (mat->entries[row_index * col_len + col_index] != 0) {
 195                                 return 0;
 196                         }
 197                 }
 198         }
 199
 200         return 1;
 201 }
 202
 203 void pbqp_matrix_add_to_all_cols(pbqp_matrix *mat, vector *vec)
 204 {
 205         unsigned col_index;
 206         unsigned col_len;
 207         unsigned row_index;
 208         unsigned row_len;
 209
 210         assert(mat);
 211         assert(vec);
 212         assert(mat->rows == vec->len);
 213
 214         col_len = mat->cols;
 215         row_len = mat->rows;
 216
 217         for (row_index = 0; row_index < row_len; ++row_index) {
 218                 num value = vec->entries[row_index].data;
 219                 for (col_index = 0; col_index < col_len; ++col_index) {
 220                         mat->entries[row_index * col_len + col_index] = pbqp_add(
 221                                         mat->entries[row_index * col_len + col_index], value);
 222                 }
 223         }
 224 }
 225
 226 void pbqp_matrix_add_to_all_rows(pbqp_matrix *mat, vector *vec)
 227 {
 228         unsigned col_index;
 229         unsigned col_len;
 230         unsigned row_index;
 231         unsigned row_len;
 232
 233         assert(mat);
 234         assert(vec);
 235         assert(mat->cols == vec->len);
 236
 237         col_len = mat->cols;
 238         row_len = mat->rows;
 239
 240         for (row_index = 0; row_index < row_len; ++row_index) {
 241                 for (col_index = 0; col_index < col_len; ++col_index) {
 242                         num value = vec->entries[col_index].data;
 243
 244                         mat->entries[row_index * col_len + col_index] = pbqp_add(mat->entries[row_index * col_len + col_index], value);
 245                 }
 246         }
 247 }