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