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         unsigned length = rows * cols;
  39         pbqp_matrix_t *mat = (pbqp_matrix_t*)obstack_alloc(&pbqp->obstack, sizeof(*mat) + sizeof(*mat->entries) * length);
  40
  41         assert(cols > 0);
  42         assert(rows > 0);
  43
  44         mat->cols = cols;
  45         mat->rows = rows;
  46         memset(mat->entries, 0, sizeof(*mat->entries) * length);
  47
  48         return mat;
  49 }
  50
  51 pbqp_matrix_t *pbqp_matrix_copy(pbqp_t *pbqp, pbqp_matrix_t *m)
  52 {
  53         unsigned       len  = m->rows * m->cols;
  54         pbqp_matrix_t *copy = (pbqp_matrix_t*)obstack_copy(&pbqp->obstack, m, sizeof(*copy) + sizeof(*copy->entries) * len);
  55         assert(copy);
  56
  57         return copy;
  58 }
  59
  60 pbqp_matrix_t *pbqp_matrix_copy_and_transpose(pbqp_t *pbqp, pbqp_matrix_t *m)
  61 {
  62         unsigned       i;
  63         unsigned       j;
  64         unsigned       cols = m->cols;
  65         unsigned       rows = m->rows;
  66         unsigned       len  = rows * cols;
  67         pbqp_matrix_t *copy = (pbqp_matrix_t*)obstack_alloc(&pbqp->obstack, sizeof(*copy) + sizeof(*copy->entries) * len);
  68
  69         for (i = 0; i < rows; ++i) {
  70                 for (j = 0; j < cols; ++j) {
  71                         copy->entries[j*rows+i] = m->entries[i*cols+j];
  72                 }
  73         }
  74
  75         copy->cols = rows;
  76         copy->rows = cols;
  77
  78         return copy;
  79 }
  80
  81 void pbqp_matrix_transpose(pbqp_t *pbqp, pbqp_matrix_t *mat)
  82 {
  83         unsigned len;
  84         pbqp_matrix_t *tmp;
  85
  86         len = mat->rows * mat->cols;
  87
  88         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         unsigned col_len = matrix->cols;
 152         unsigned row_len = matrix->rows;
 153
 154         assert(matrix->rows == flags->len);
 155
 156         for (row_index = 0; row_index < row_len; ++row_index) {
 157                 num elem;
 158
 159                 /* Ignore virtual deleted columns. */
 160                 if (flags->entries[row_index].data == INF_COSTS) continue;
 161
 162                 elem = matrix->entries[row_index * col_len + col_index];
 163
 164                 if (elem < min) {
 165                         min = elem;
 166                 }
 167         }
 168
 169         return min;
 170 }
 171
 172 unsigned pbqp_matrix_get_col_min_index(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags)
 173 {
 174         unsigned row_index;
 175         unsigned min_index = 0;
 176         num      min       = INF_COSTS;
 177
 178         unsigned col_len = matrix->cols;
 179         unsigned row_len = matrix->rows;
 180
 181         assert(matrix->rows == flags->len);
 182
 183         for (row_index = 0; row_index < row_len; ++row_index) {
 184                 num elem;
 185
 186                 /* Ignore virtual deleted columns. */
 187                 if (flags->entries[row_index].data == INF_COSTS) continue;
 188
 189                 elem = matrix->entries[row_index * col_len + col_index];
 190
 191                 if (elem < min) {
 192                         min = elem;
 193                         min_index = row_index;
 194                 }
 195         }
 196
 197         return min_index;
 198 }
 199
 200 void pbqp_matrix_sub_col_value(pbqp_matrix_t *matrix, unsigned col_index,
 201                 vector_t *flags, num value)
 202 {
 203         unsigned col_len;
 204         unsigned row_index;
 205         unsigned row_len;
 206
 207         assert(matrix->rows == flags->len);
 208
 209         col_len = matrix->cols;
 210         row_len = matrix->rows;
 211
 212         for (row_index = 0; row_index < row_len; ++row_index) {
 213                 if (flags->entries[row_index].data == INF_COSTS) {
 214                         matrix->entries[row_index * col_len + col_index] = 0;
 215                         continue;
 216                 }
 217                 /* inf - x = inf if x < inf */
 218                 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
 219                                 != INF_COSTS)
 220                         continue;
 221                 matrix->entries[row_index * col_len + col_index] -= value;
 222         }
 223 }
 224
 225 num pbqp_matrix_get_row_min(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags)
 226 {
 227         unsigned col_index;
 228         num min = INF_COSTS;
 229
 230         unsigned len = flags->len;
 231
 232         assert(matrix->cols == len);
 233
 234         for (col_index = 0; col_index < len; ++col_index) {
 235                 num elem;
 236
 237                 /* Ignore virtual deleted columns. */
 238                 if (flags->entries[col_index].data == INF_COSTS) continue;
 239
 240                 elem = matrix->entries[row_index * len + col_index];
 241
 242                 if (elem < min) {
 243                         min = elem;
 244                 }
 245         }
 246
 247         return min;
 248 }
 249
 250 unsigned pbqp_matrix_get_row_min_index(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags)
 251 {
 252         unsigned col_index;
 253         unsigned min_index = 0;
 254         num      min       = INF_COSTS;
 255
 256         unsigned len = flags->len;
 257
 258         assert(matrix->cols == len);
 259
 260         for (col_index = 0; col_index < len; ++col_index) {
 261                 num elem;
 262
 263                 /* Ignore virtual deleted columns. */
 264                 if (flags->entries[col_index].data == INF_COSTS) continue;
 265
 266                 elem = matrix->entries[row_index * len + col_index];
 267
 268                 if (elem < min) {
 269                         min = elem;
 270                         min_index = col_index;
 271                 }
 272         }
 273
 274         return min_index;
 275 }
 276
 277 void pbqp_matrix_sub_row_value(pbqp_matrix_t *matrix, unsigned row_index,
 278                 vector_t *flags, num value)
 279 {
 280         unsigned col_index;
 281         unsigned col_len;
 282
 283         assert(matrix->cols == flags->len);
 284
 285         col_len = matrix->cols;
 286
 287         for (col_index = 0; col_index < col_len; ++col_index) {
 288                 if (flags->entries[col_index].data == INF_COSTS) {
 289                         matrix->entries[row_index * col_len + col_index] = 0;
 290                         continue;
 291                 }
 292                 /* inf - x = inf if x < inf */
 293                 if (matrix->entries[row_index * col_len + col_index] == INF_COSTS && value
 294                                 != INF_COSTS)
 295                         continue;
 296                 matrix->entries[row_index * col_len + col_index] -= value;
 297         }
 298 }
 299
 300 int pbqp_matrix_is_zero(pbqp_matrix_t *mat, vector_t *src_vec, vector_t *tgt_vec)
 301 {
 302         unsigned col_index;
 303         unsigned col_len;
 304         unsigned row_index;
 305         unsigned row_len;
 306
 307         assert(mat->cols = tgt_vec->len);
 308         assert(mat->rows = src_vec->len);
 309
 310         col_len = mat->cols;
 311         row_len = mat->rows;
 312
 313         for (row_index = 0; row_index < row_len; ++row_index) {
 314                 if (src_vec->entries[row_index].data == INF_COSTS) continue;
 315                 for (col_index = 0; col_index < col_len; ++col_index) {
 316                         if (tgt_vec->entries[col_index].data == INF_COSTS) continue;
 317
 318                         if (mat->entries[row_index * col_len + col_index] != 0) {
 319                                 return 0;
 320                         }
 321                 }
 322         }
 323
 324         return 1;
 325 }
 326
 327 void pbqp_matrix_add_to_all_cols(pbqp_matrix_t *mat, vector_t *vec)
 328 {
 329         unsigned col_index;
 330         unsigned col_len;
 331         unsigned row_index;
 332         unsigned row_len;
 333
 334         assert(mat->rows == vec->len);
 335
 336         col_len = mat->cols;
 337         row_len = mat->rows;
 338
 339         for (row_index = 0; row_index < row_len; ++row_index) {
 340                 num value = vec->entries[row_index].data;
 341                 for (col_index = 0; col_index < col_len; ++col_index) {
 342                         mat->entries[row_index * col_len + col_index] = pbqp_add(
 343                                         mat->entries[row_index * col_len + col_index], value);
 344                 }
 345         }
 346 }
 347
 348 void pbqp_matrix_add_to_all_rows(pbqp_matrix_t *mat, vector_t *vec)
 349 {
 350         unsigned col_index;
 351         unsigned col_len;
 352         unsigned row_index;
 353         unsigned row_len;
 354
 355         assert(mat->cols == vec->len);
 356
 357         col_len = mat->cols;
 358         row_len = mat->rows;
 359
 360         for (row_index = 0; row_index < row_len; ++row_index) {
 361                 for (col_index = 0; col_index < col_len; ++col_index) {
 362                         num value = vec->entries[col_index].data;
 363
 364                         mat->entries[row_index * col_len + col_index] = pbqp_add(mat->entries[row_index * col_len + col_index], value);
 365                 }
 366         }
 367 }