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

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