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