nsz Git - libfirm/blob - optimal.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   Optimal reductions and helper functions.
  23  * @date    28.12.2009
  24  * @author  Sebastian Buchwald
  25  * @version $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "adt/array.h"
  30 #include "assert.h"
  31 #include "error.h"
  32
  33 #include "bucket.h"
  34 #if     KAPS_DUMP
  35 #include "html_dumper.h"
  36 #endif
  37 #include "kaps.h"
  38 #include "matrix.h"
  39 #include "optimal.h"
  40 #include "pbqp_edge.h"
  41 #include "pbqp_edge_t.h"
  42 #include "pbqp_node.h"
  43 #include "pbqp_node_t.h"
  44 #include "vector.h"
  45
  46 #include "plist.h"
  47 #include "timing.h"
  48
  49 pbqp_edge **edge_bucket;
  50 pbqp_node **node_buckets[4];
  51 pbqp_node **reduced_bucket = NULL;
  52 static int         buckets_filled = 0;
  53
  54 static void insert_into_edge_bucket(pbqp_edge *edge)
  55 {
  56         if (edge_bucket_contains(edge_bucket, edge)) {
  57                 /* Edge is already inserted. */
  58                 return;
  59         }
  60
  61         edge_bucket_insert(&edge_bucket, edge);
  62 }
  63
  64 static void init_buckets(void)
  65 {
  66         int i;
  67
  68         edge_bucket_init(&edge_bucket);
  69         node_bucket_init(&reduced_bucket);
  70
  71         for (i = 0; i < 4; ++i) {
  72                 node_bucket_init(&node_buckets[i]);
  73         }
  74 }
  75
  76 void free_buckets(void)
  77 {
  78         int i;
  79
  80         for (i = 0; i < 4; ++i) {
  81                 node_bucket_free(&node_buckets[i]);
  82         }
  83
  84         edge_bucket_free(&edge_bucket);
  85         node_bucket_free(&reduced_bucket);
  86
  87         buckets_filled = 0;
  88 }
  89
  90 void fill_node_buckets(pbqp *pbqp)
  91 {
  92         unsigned node_index;
  93         unsigned node_len;
  94
  95         assert(pbqp);
  96         node_len = pbqp->num_nodes;
  97
  98         #if KAPS_TIMING
  99                 ir_timer_t *t_fill_buckets = ir_timer_register("be_pbqp_fill_buckets", "PBQP Fill Nodes into buckets");
 100                 ir_timer_reset_and_start(t_fill_buckets);
 101         #endif
 102
 103         for (node_index = 0; node_index < node_len; ++node_index) {
 104                 unsigned   degree;
 105                 pbqp_node *node = get_node(pbqp, node_index);
 106
 107                 if (!node) continue;
 108
 109                 degree = pbqp_node_get_degree(node);
 110
 111                 /* We have only one bucket for nodes with arity >= 3. */
 112                 if (degree > 3) {
 113                         degree = 3;
 114                 }
 115
 116                 node_bucket_insert(&node_buckets[degree], node);
 117         }
 118
 119         buckets_filled = 1;
 120
 121         #if KAPS_TIMING
 122                 ir_timer_stop(t_fill_buckets);
 123                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_fill_buckets), (double)ir_timer_elapsed_usec(t_fill_buckets) / 1000.0);
 124         #endif
 125 }
 126
 127 static void normalize_towards_source(pbqp_edge *edge)
 128 {
 129         pbqp_matrix    *mat;
 130         pbqp_node      *src_node;
 131         pbqp_node      *tgt_node;
 132         vector         *src_vec;
 133         vector         *tgt_vec;
 134         int             src_len;
 135         int             tgt_len;
 136         int             src_index;
 137
 138         assert(edge);
 139
 140         src_node = edge->src;
 141         tgt_node = edge->tgt;
 142         assert(src_node);
 143         assert(tgt_node);
 144
 145         src_vec = src_node->costs;
 146         tgt_vec = tgt_node->costs;
 147         assert(src_vec);
 148         assert(tgt_vec);
 149
 150         src_len = src_vec->len;
 151         tgt_len = tgt_vec->len;
 152         assert(src_len > 0);
 153         assert(tgt_len > 0);
 154
 155         mat = edge->costs;
 156         assert(mat);
 157
 158         /* Normalize towards source node. */
 159         for (src_index = 0; src_index < src_len; ++src_index) {
 160                 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
 161
 162                 if (min != 0) {
 163                         if (src_vec->entries[src_index].data == INF_COSTS) {
 164                                 pbqp_matrix_set_row_value(mat, src_index, 0);
 165                         } else {
 166                                 pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
 167                         }
 168                         src_vec->entries[src_index].data = pbqp_add(
 169                                         src_vec->entries[src_index].data, min);
 170
 171                         if (min == INF_COSTS) {
 172                                 unsigned edge_index;
 173                                 unsigned edge_len = pbqp_node_get_degree(src_node);
 174
 175                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 176                                         pbqp_edge *edge_candidate = src_node->edges[edge_index];
 177                                         if (edge_candidate != edge) {
 178                                                 insert_into_edge_bucket(edge_candidate);
 179                                         }
 180                                 }
 181                         }
 182                 }
 183         }
 184 }
 185
 186 static void normalize_towards_target(pbqp_edge *edge)
 187 {
 188         pbqp_matrix    *mat;
 189         pbqp_node      *src_node;
 190         pbqp_node      *tgt_node;
 191         vector         *src_vec;
 192         vector         *tgt_vec;
 193         int             src_len;
 194         int             tgt_len;
 195         int             tgt_index;
 196
 197         assert(edge);
 198
 199         src_node = edge->src;
 200         tgt_node = edge->tgt;
 201         assert(src_node);
 202         assert(tgt_node);
 203
 204         src_vec = src_node->costs;
 205         tgt_vec = tgt_node->costs;
 206         assert(src_vec);
 207         assert(tgt_vec);
 208
 209         src_len = src_vec->len;
 210         tgt_len = tgt_vec->len;
 211         assert(src_len > 0);
 212         assert(tgt_len > 0);
 213
 214         mat = edge->costs;
 215         assert(mat);
 216
 217         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 218                 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 219
 220                 if (min != 0) {
 221                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 222                                 pbqp_matrix_set_col_value(mat, tgt_index, 0);
 223                         } else {
 224                                 pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
 225                         }
 226                         tgt_vec->entries[tgt_index].data = pbqp_add(
 227                                         tgt_vec->entries[tgt_index].data, min);
 228
 229                         if (min == INF_COSTS) {
 230                                 unsigned edge_index;
 231                                 unsigned edge_len = pbqp_node_get_degree(tgt_node);
 232
 233                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 234                                         pbqp_edge *edge_candidate = tgt_node->edges[edge_index];
 235                                         if (edge_candidate != edge) {
 236                                                 insert_into_edge_bucket(edge_candidate);
 237                                         }
 238                                 }
 239                         }
 240                 }
 241         }
 242 }
 243
 244 /**
 245  * Tries to apply RM for the source node of the given edge.
 246  *
 247  * Checks whether the source node of edge can be merged into the target node of
 248  * edge, and performs the merge, if possible.
 249  */
 250 static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge)
 251 {
 252         pbqp_matrix    *mat;
 253         pbqp_node      *src_node;
 254         pbqp_node      *tgt_node;
 255         vector         *src_vec;
 256         vector         *tgt_vec;
 257         unsigned       *mapping;
 258         unsigned        src_len;
 259         unsigned        tgt_len;
 260         unsigned        src_index;
 261         unsigned        tgt_index;
 262         unsigned        edge_index;
 263         unsigned        edge_len;
 264
 265         assert(pbqp);
 266         assert(edge);
 267
 268         src_node = edge->src;
 269         tgt_node = edge->tgt;
 270         assert(src_node);
 271         assert(tgt_node);
 272
 273         src_vec = src_node->costs;
 274         tgt_vec = tgt_node->costs;
 275         assert(src_vec);
 276         assert(tgt_vec);
 277
 278         src_len = src_vec->len;
 279         tgt_len = tgt_vec->len;
 280
 281         /* Matrizes are normalized. */
 282         assert(src_len > 1);
 283         assert(tgt_len > 1);
 284
 285         mat = edge->costs;
 286         assert(mat);
 287
 288         mapping = NEW_ARR_F(unsigned, tgt_len);
 289
 290         /* Check that each column has at most one zero entry. */
 291         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 292                 unsigned onlyOneZero = 0;
 293
 294                 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
 295                         continue;
 296
 297                 for (src_index = 0; src_index < src_len; ++src_index) {
 298                         if (src_vec->entries[src_index].data == INF_COSTS)
 299                                 continue;
 300
 301                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS)
 302                                 continue;
 303
 304                         /* Matrix entry is finite. */
 305                         if (onlyOneZero) {
 306                                 DEL_ARR_F(mapping);
 307                                 return;
 308                         }
 309
 310                         onlyOneZero = 1;
 311                         mapping[tgt_index] = src_index;
 312                 }
 313         }
 314
 315         /* We know that we can merge the source node into the target node. */
 316         edge_len = pbqp_node_get_degree(src_node);
 317
 318 #if KAPS_STATISTIC
 319         pbqp->num_rm++;
 320 #endif
 321
 322         /* Reconnect the source's edges with the target node. */
 323         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 324                 pbqp_edge   *old_edge = src_node->edges[edge_index];
 325                 pbqp_matrix *old_matrix;
 326                 pbqp_matrix *new_matrix;
 327                 pbqp_node   *other_node;
 328                 unsigned     other_len;
 329                 unsigned     other_index;
 330                 unsigned     tgt_index;
 331
 332                 assert(old_edge);
 333
 334                 if (old_edge == edge)
 335                         continue;
 336
 337                 old_matrix = old_edge->costs;
 338                 assert(old_matrix);
 339
 340                 if (old_edge->tgt == src_node) {
 341                         other_node = edge->src;
 342                         other_len  = old_matrix->rows;
 343                 }
 344                 else {
 345                         other_node = edge->tgt;
 346                         other_len = old_matrix->cols;
 347                 }
 348                 assert(other_node);
 349
 350                 new_matrix = pbqp_matrix_alloc(pbqp, tgt_len, other_len);
 351
 352                 /* Source node selects the column of the old_matrix. */
 353                 if (old_edge->tgt == src_node) {
 354                         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 355                                 unsigned src_index = mapping[tgt_index];
 356
 357                                 for (other_index = 0; other_index < other_len; ++other_index) {
 358                                         new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[other_index*src_len+src_index];
 359                                 }
 360                         }
 361                 }
 362                 /* Source node selects the row of the old_matrix. */
 363                 else {
 364                         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 365                                 unsigned src_index = mapping[tgt_index];
 366
 367                                 for (other_index = 0; other_index < other_len; ++other_index) {
 368                                         new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[src_index*other_len+other_index];
 369                                 }
 370                         }
 371                 }
 372
 373                 add_edge_costs(pbqp, tgt_node->index, other_node->index, new_matrix);
 374
 375                 disconnect_edge(src_node, old_edge);
 376                 disconnect_edge(other_node, old_edge);
 377         }
 378
 379         /* Reduce the remaining source node via RI. */
 380         apply_RI(pbqp);
 381 }
 382
 383 /**
 384  * Tries to apply RM for the target node of the given edge.
 385  *
 386  * Checks whether the target node of edge can be merged into the source node of
 387  * edge, and performs the merge, if possible.
 388  */
 389 static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge)
 390 {
 391         pbqp_matrix    *mat;
 392         pbqp_node      *src_node;
 393         pbqp_node      *tgt_node;
 394         vector         *src_vec;
 395         vector         *tgt_vec;
 396         unsigned       *mapping;
 397         unsigned        src_len;
 398         unsigned        tgt_len;
 399         unsigned        src_index;
 400         unsigned        tgt_index;
 401         unsigned        edge_index;
 402         unsigned        edge_len;
 403
 404         assert(pbqp);
 405         assert(edge);
 406
 407         src_node = edge->src;
 408         tgt_node = edge->tgt;
 409         assert(src_node);
 410         assert(tgt_node);
 411
 412         src_vec = src_node->costs;
 413         tgt_vec = tgt_node->costs;
 414         assert(src_vec);
 415         assert(tgt_vec);
 416
 417         src_len = src_vec->len;
 418         tgt_len = tgt_vec->len;
 419
 420         /* Matrizes are normalized. */
 421         assert(src_len > 1);
 422         assert(tgt_len > 1);
 423
 424         mat = edge->costs;
 425         assert(mat);
 426
 427         mapping = NEW_ARR_F(unsigned, src_len);
 428
 429         /* Check that each row has at most one zero entry. */
 430         for (src_index = 0; src_index < src_len; ++src_index) {
 431                 unsigned onlyOneZero = 0;
 432
 433                 if (src_vec->entries[src_index].data == INF_COSTS)
 434                         continue;
 435
 436                 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 437                         if (tgt_vec->entries[tgt_index].data == INF_COSTS)
 438                                 continue;
 439
 440                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS)
 441                                 continue;
 442
 443                         /* Matrix entry is finite. */
 444                         if (onlyOneZero) {
 445                                 DEL_ARR_F(mapping);
 446                                 return;
 447
 448                         onlyOneZero = 1;
 449                         mapping[src_index] = tgt_index;
 450                 }
 451         }
 452
 453         /* We know that we can merge the target node into the source node. */
 454         edge_len = pbqp_node_get_degree(tgt_node);
 455
 456 #if KAPS_STATISTIC
 457         pbqp->num_rm++;
 458 #endif
 459
 460         /* Reconnect the target's edges with the source node. */
 461         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 462                 pbqp_edge   *old_edge = tgt_node->edges[edge_index];
 463                 pbqp_matrix *old_matrix;
 464                 pbqp_matrix *new_matrix;
 465                 pbqp_node   *other_node;
 466                 unsigned     other_len;
 467                 unsigned     other_index;
 468                 unsigned     src_index;
 469
 470                 assert(old_edge);
 471
 472                 if (old_edge == edge)
 473                         continue;
 474
 475                 old_matrix = old_edge->costs;
 476                 assert(old_matrix);
 477
 478                 if (old_edge->tgt == tgt_node) {
 479                         other_node = edge->src;
 480                         other_len  = old_matrix->rows;
 481                 }
 482                 else {
 483                         other_node = edge->tgt;
 484                         other_len = old_matrix->cols;
 485                 }
 486                 assert(other_node);
 487
 488                 new_matrix = pbqp_matrix_alloc(pbqp, src_len, other_len);
 489
 490                 /* Target node selects the column of the old_matrix. */
 491                 if (old_edge->tgt == tgt_node) {
 492                         for (src_index = 0; src_index < src_len; ++src_index) {
 493                                 unsigned tgt_index = mapping[src_index];
 494
 495                                 for (other_index = 0; other_index < other_len; ++other_index) {
 496                                         new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[other_index*tgt_len+tgt_index];
 497                                 }
 498                         }
 499                 }
 500                 /* Source node selects the row of the old_matrix. */
 501                 else {
 502                         for (src_index = 0; src_index < src_len; ++src_index) {
 503                                 unsigned tgt_index = mapping[src_index];
 504
 505                                 for (other_index = 0; other_index < other_len; ++other_index) {
 506                                         new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[tgt_index*other_len+other_index];
 507                                 }
 508                         }
 509                 }
 510
 511                 add_edge_costs(pbqp, src_node->index, other_node->index, new_matrix);
 512
 513                 disconnect_edge(tgt_node, old_edge);
 514                 disconnect_edge(other_node, old_edge);
 515         }
 516
 517         /* Reduce the remaining source node via RI. */
 518         apply_RI(pbqp);
 519 }
 520
 521 void reorder_node(pbqp_node *node)
 522 {
 523         unsigned    degree     = pbqp_node_get_degree(node);
 524         /* Assume node lost one incident edge. */
 525         unsigned    old_degree = degree + 1;
 526
 527         if (!buckets_filled) return;
 528
 529         /* Same bucket as before */
 530         if (degree > 2) return;
 531
 532         if (!node_bucket_contains(node_buckets[old_degree], node)) {
 533                 /* Old arity is new arity, so we have nothing to do. */
 534                 assert(node_bucket_contains(node_buckets[degree], node));
 535                 return;
 536         }
 537
 538         /* Delete node from old bucket... */
 539         node_bucket_remove(&node_buckets[old_degree], node);
 540
 541         /* ..and add to new one. */
 542         node_bucket_insert(&node_buckets[degree], node);
 543 }
 544
 545 #if KAPS_STATISTIC
 546 void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
 547 {
 548         pbqp_matrix    *mat;
 549         pbqp_node      *src_node;
 550         pbqp_node      *tgt_node;
 551         vector         *src_vec;
 552         vector         *tgt_vec;
 553         int             src_len;
 554         int             tgt_len;
 555         int             src_index;
 556         int             tgt_index;
 557
 558         assert(pbqp);
 559         assert(edge);
 560
 561         src_node = edge->src;
 562         tgt_node = edge->tgt;
 563         assert(src_node);
 564         assert(tgt_node);
 565
 566         src_vec = src_node->costs;
 567         tgt_vec = tgt_node->costs;
 568         assert(src_vec);
 569         assert(tgt_vec);
 570
 571         src_len = src_vec->len;
 572         tgt_len = tgt_vec->len;
 573         assert(src_len > 0);
 574         assert(tgt_len > 0);
 575
 576         mat = edge->costs;
 577         assert(mat);
 578
 579         if (src_len == 1 && tgt_len == 1) {
 580                 //panic("Something is wrong");
 581         }
 582
 583         int allRowsOk = 1;
 584         for (src_index = 0; src_index < src_len; ++src_index) {
 585                 int onlyOneZero = 0;
 586                 if (src_vec->entries[src_index].data == INF_COSTS) {
 587                         continue;
 588                 }
 589                 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 590                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 591                                 continue;
 592                         }
 593                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 594                                 if (onlyOneZero) {
 595                                         onlyOneZero = 0;
 596                                         break;
 597                                 } else {
 598                                         onlyOneZero = 1;
 599                                         continue;
 600                                 }
 601                         }
 602                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 603                                 continue;
 604                         }
 605                         onlyOneZero = 0;
 606                         break;
 607                 }
 608                 allRowsOk &= onlyOneZero;
 609         }
 610
 611         int allColsOk = 1;
 612         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 613                 int onlyOneZero = 0;
 614                 if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 615                         continue;
 616                 }
 617                 for (src_index = 0; src_index < src_len; ++src_index) {
 618                         if (src_vec->entries[src_index].data == INF_COSTS) {
 619                                 continue;
 620                         }
 621                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 622                                 if (onlyOneZero) {
 623                                         onlyOneZero = 0;
 624                                         break;
 625                                 } else {
 626                                         onlyOneZero = 1;
 627                                         continue;
 628                                 }
 629                         }
 630                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 631                                 continue;
 632                         }
 633                         onlyOneZero = 0;
 634                         break;
 635                 }
 636                 allColsOk &= onlyOneZero;
 637         }
 638
 639         if (allRowsOk || allColsOk) {
 640                 pbqp->num_rm++;
 641         }
 642 }
 643 #endif
 644
 645 void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 646 {
 647         pbqp_matrix    *mat;
 648         pbqp_node      *src_node;
 649         pbqp_node      *tgt_node;
 650         vector         *src_vec;
 651         vector         *tgt_vec;
 652         int             src_len;
 653         int             tgt_len;
 654
 655         assert(pbqp);
 656         assert(edge);
 657
 658         src_node = edge->src;
 659         tgt_node = edge->tgt;
 660         assert(src_node);
 661         assert(tgt_node);
 662
 663         /* If edge are already deleted, we have nothing to do. */
 664         if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
 665                 return;
 666
 667 #if     KAPS_DUMP
 668         if (pbqp->dump_file) {
 669                 char txt[100];
 670                 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
 671                 dump_section(pbqp->dump_file, 3, txt);
 672         }
 673 #endif
 674
 675         src_vec = src_node->costs;
 676         tgt_vec = tgt_node->costs;
 677         assert(src_vec);
 678         assert(tgt_vec);
 679
 680         src_len = src_vec->len;
 681         tgt_len = tgt_vec->len;
 682         assert(src_len > 0);
 683         assert(tgt_len > 0);
 684
 685         mat = edge->costs;
 686         assert(mat);
 687
 688 #if     KAPS_DUMP
 689         if (pbqp->dump_file) {
 690                 fputs("Input:<br>\n", pbqp->dump_file);
 691                 dump_simplifyedge(pbqp, edge);
 692         }
 693 #endif
 694
 695         normalize_towards_source(edge);
 696         normalize_towards_target(edge);
 697
 698 #if     KAPS_DUMP
 699         if (pbqp->dump_file) {
 700                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 701                 dump_simplifyedge(pbqp, edge);
 702         }
 703 #endif
 704
 705         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 706 #if     KAPS_DUMP
 707                 if (pbqp->dump_file) {
 708                         fputs("edge has been eliminated<br>\n", pbqp->dump_file);
 709                 }
 710 #endif
 711
 712 #if KAPS_STATISTIC
 713                 pbqp->num_edges++;
 714 #endif
 715
 716                 delete_edge(edge);
 717                 reorder_node(src_node);
 718                 reorder_node(tgt_node);
 719         }
 720 }
 721
 722 void initial_simplify_edges(pbqp *pbqp)
 723 {
 724         unsigned node_index;
 725         unsigned node_len;
 726
 727         assert(pbqp);
 728
 729         #if KAPS_TIMING
 730                 ir_timer_t *t_int_simpl = ir_timer_register("be_pbqp_init_simp", "PBQP Initial simplify edges");
 731                 ir_timer_reset_and_start(t_int_simpl);
 732         #endif
 733
 734 #if     KAPS_DUMP
 735         if (pbqp->dump_file) {
 736                 pbqp_dump_input(pbqp);
 737                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 738         }
 739 #endif
 740
 741         node_len = pbqp->num_nodes;
 742
 743         init_buckets();
 744
 745         /* First simplify all edges. */
 746         for (node_index = 0; node_index < node_len; ++node_index) {
 747                 unsigned    edge_index;
 748                 pbqp_node  *node = get_node(pbqp, node_index);
 749                 pbqp_edge **edges;
 750                 unsigned    edge_len;
 751
 752                 if (!node) continue;
 753
 754                 edges = node->edges;
 755                 edge_len = pbqp_node_get_degree(node);
 756
 757                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 758                         pbqp_edge *edge = edges[edge_index];
 759
 760                         /* Simplify only once per edge. */
 761                         if (node != edge->src) continue;
 762
 763                         simplify_edge(pbqp, edge);
 764                 }
 765         }
 766
 767         #if KAPS_TIMING
 768                 ir_timer_stop(t_int_simpl);
 769                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_int_simpl), (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
 770         #endif
 771 }
 772
 773 num determine_solution(pbqp *pbqp)
 774 {
 775         unsigned node_index;
 776         unsigned node_len;
 777         num      solution   = 0;
 778
 779         #if KAPS_TIMING
 780                 ir_timer_t *t_det_solution = ir_timer_register("be_det_solution", "PBQP Determine Solution");
 781                 ir_timer_reset_and_start(t_det_solution);
 782         #endif
 783
 784 #if     KAPS_DUMP
 785         FILE     *file;
 786 #endif
 787
 788         assert(pbqp);
 789
 790 #if     KAPS_DUMP
 791         file = pbqp->dump_file;
 792
 793         if (file) {
 794                 dump_section(file, 1, "4. Determine Solution/Minimum");
 795                 dump_section(file, 2, "4.1. Trivial Solution");
 796         }
 797 #endif
 798
 799         /* Solve trivial nodes and calculate solution. */
 800         node_len = node_bucket_get_length(node_buckets[0]);
 801
 802 #if KAPS_STATISTIC
 803         pbqp->num_r0 = node_len;
 804 #endif
 805
 806         for (node_index = 0; node_index < node_len; ++node_index) {
 807                 pbqp_node *node = node_buckets[0][node_index];
 808                 assert(node);
 809
 810                 node->solution = vector_get_min_index(node->costs);
 811                 solution       = pbqp_add(solution,
 812                                 node->costs->entries[node->solution].data);
 813
 814 #if     KAPS_DUMP
 815                 if (file) {
 816                         fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
 817                         dump_node(file, node);
 818                 }
 819 #endif
 820         }
 821
 822 #if     KAPS_DUMP
 823         if (file) {
 824                 dump_section(file, 2, "Minimum");
 825 #if KAPS_USE_UNSIGNED
 826                 fprintf(file, "Minimum is equal to %u.", solution);
 827 #else
 828                 fprintf(file, "Minimum is equal to %lld.", solution);
 829 #endif
 830         }
 831 #endif
 832
 833         #if KAPS_TIMING
 834                 ir_timer_stop(t_det_solution);
 835                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_det_solution), (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
 836         #endif
 837
 838         return solution;
 839 }
 840
 841 static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 842 {
 843         pbqp_edge   *edge;
 844         pbqp_node   *other;
 845         pbqp_matrix *mat;
 846         vector      *vec;
 847         int          is_src;
 848
 849         assert(pbqp);
 850         assert(node);
 851
 852         edge = node->edges[0];
 853         mat = edge->costs;
 854         is_src = edge->src == node;
 855         vec = node->costs;
 856
 857         if (is_src) {
 858                 other = edge->tgt;
 859                 assert(other);
 860
 861                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
 862         } else {
 863                 other = edge->src;
 864                 assert(other);
 865
 866                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
 867         }
 868
 869 #if     KAPS_DUMP
 870         if (pbqp->dump_file) {
 871                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 872         }
 873 #endif
 874 }
 875
 876 static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
 877 {
 878         pbqp_edge   *src_edge   = node->edges[0];
 879         pbqp_edge   *tgt_edge   = node->edges[1];
 880         int          src_is_src = src_edge->src == node;
 881         int          tgt_is_src = tgt_edge->src == node;
 882         pbqp_matrix *src_mat;
 883         pbqp_matrix *tgt_mat;
 884         pbqp_node   *src_node;
 885         pbqp_node   *tgt_node;
 886         vector      *vec;
 887         vector      *node_vec;
 888         unsigned     col_index;
 889         unsigned     row_index;
 890
 891         assert(pbqp);
 892
 893         if (src_is_src) {
 894                 src_node = src_edge->tgt;
 895         } else {
 896                 src_node = src_edge->src;
 897         }
 898
 899         if (tgt_is_src) {
 900                 tgt_node = tgt_edge->tgt;
 901         } else {
 902                 tgt_node = tgt_edge->src;
 903         }
 904
 905         /* Swap nodes if necessary. */
 906         if (tgt_node->index < src_node->index) {
 907                 pbqp_node *tmp_node;
 908                 pbqp_edge *tmp_edge;
 909
 910                 tmp_node = src_node;
 911                 src_node = tgt_node;
 912                 tgt_node = tmp_node;
 913
 914                 tmp_edge = src_edge;
 915                 src_edge = tgt_edge;
 916                 tgt_edge = tmp_edge;
 917
 918                 src_is_src = src_edge->src == node;
 919                 tgt_is_src = tgt_edge->src == node;
 920         }
 921
 922         src_mat = src_edge->costs;
 923         tgt_mat = tgt_edge->costs;
 924
 925         node_vec = node->costs;
 926
 927         row_index = src_node->solution;
 928         col_index = tgt_node->solution;
 929
 930         vec = vector_copy(pbqp, node_vec);
 931
 932         if (src_is_src) {
 933                 vector_add_matrix_col(vec, src_mat, row_index);
 934         } else {
 935                 vector_add_matrix_row(vec, src_mat, row_index);
 936         }
 937
 938         if (tgt_is_src) {
 939                 vector_add_matrix_col(vec, tgt_mat, col_index);
 940         } else {
 941                 vector_add_matrix_row(vec, tgt_mat, col_index);
 942         }
 943
 944         node->solution = vector_get_min_index(vec);
 945
 946 #if     KAPS_DUMP
 947         if (pbqp->dump_file) {
 948                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 949         }
 950 #endif
 951
 952         obstack_free(&pbqp->obstack, vec);
 953 }
 954
 955 void back_propagate(pbqp *pbqp)
 956 {
 957         unsigned node_index;
 958         unsigned node_len   = node_bucket_get_length(reduced_bucket);
 959
 960         assert(pbqp);
 961
 962 #if     KAPS_DUMP
 963         if (pbqp->dump_file) {
 964                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 965         }
 966 #endif
 967
 968         for (node_index = node_len; node_index > 0; --node_index) {
 969                 pbqp_node *node = reduced_bucket[node_index - 1];
 970
 971                 switch (pbqp_node_get_degree(node)) {
 972                         case 1:
 973                                 back_propagate_RI(pbqp, node);
 974                                 break;
 975                         case 2:
 976                                 back_propagate_RII(pbqp, node);
 977                                 break;
 978                         default:
 979                                 panic("Only nodes with degree one or two should be in this bucket");
 980                                 break;
 981                 }
 982         }
 983 }
 984
 985 void apply_edge(pbqp *pbqp)
 986 {
 987         pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
 988
 989         simplify_edge(pbqp, edge);
 990 }
 991
 992 void apply_RI(pbqp *pbqp)
 993 {
 994         pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
 995         pbqp_edge   *edge       = node->edges[0];
 996         pbqp_matrix *mat        = edge->costs;
 997         int          is_src     = edge->src == node;
 998         pbqp_node   *other_node;
 999
1000         (void ) pbqp;
1001         assert(pbqp_node_get_degree(node) == 1);
1002
1003         if (is_src) {
1004                 other_node = edge->tgt;
1005         } else {
1006                 other_node = edge->src;
1007         }
1008
1009 #if     KAPS_DUMP
1010         if (pbqp->dump_file) {
1011                 char     txt[100];
1012                 sprintf(txt, "RI-Reduction of Node n%d", node->index);
1013                 dump_section(pbqp->dump_file, 2, txt);
1014                 pbqp_dump_graph(pbqp);
1015                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
1016                 dump_node(pbqp->dump_file, node);
1017                 dump_node(pbqp->dump_file, other_node);
1018                 dump_edge(pbqp->dump_file, edge);
1019         }
1020 #endif
1021
1022         if (is_src) {
1023                 pbqp_matrix_add_to_all_cols(mat, node->costs);
1024                 normalize_towards_target(edge);
1025         } else {
1026                 pbqp_matrix_add_to_all_rows(mat, node->costs);
1027                 normalize_towards_source(edge);
1028         }
1029         disconnect_edge(other_node, edge);
1030
1031 #if     KAPS_DUMP
1032         if (pbqp->dump_file) {
1033                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1034                 dump_node(pbqp->dump_file, other_node);
1035         }
1036 #endif
1037
1038         reorder_node(other_node);
1039
1040 #if KAPS_STATISTIC
1041         pbqp->num_r1++;
1042 #endif
1043
1044         /* Add node to back propagation list. */
1045         node_bucket_insert(&reduced_bucket, node);
1046 }
1047
1048 void apply_RII(pbqp *pbqp)
1049 {
1050         pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
1051         pbqp_edge   *src_edge   = node->edges[0];
1052         pbqp_edge   *tgt_edge   = node->edges[1];
1053         int          src_is_src = src_edge->src == node;
1054         int          tgt_is_src = tgt_edge->src == node;
1055         pbqp_matrix *src_mat;
1056         pbqp_matrix *tgt_mat;
1057         pbqp_node   *src_node;
1058         pbqp_node   *tgt_node;
1059         pbqp_matrix *mat;
1060         vector      *vec;
1061         vector      *node_vec;
1062         vector      *src_vec;
1063         vector      *tgt_vec;
1064         unsigned     col_index;
1065         unsigned     col_len;
1066         unsigned     row_index;
1067         unsigned     row_len;
1068         unsigned     node_len;
1069
1070         assert(pbqp);
1071         assert(pbqp_node_get_degree(node) == 2);
1072
1073         if (src_is_src) {
1074                 src_node = src_edge->tgt;
1075         } else {
1076                 src_node = src_edge->src;
1077         }
1078
1079         if (tgt_is_src) {
1080                 tgt_node = tgt_edge->tgt;
1081         } else {
1082                 tgt_node = tgt_edge->src;
1083         }
1084
1085         /* Swap nodes if necessary. */
1086         if (tgt_node->index < src_node->index) {
1087                 pbqp_node *tmp_node;
1088                 pbqp_edge *tmp_edge;
1089
1090                 tmp_node = src_node;
1091                 src_node = tgt_node;
1092                 tgt_node = tmp_node;
1093
1094                 tmp_edge = src_edge;
1095                 src_edge = tgt_edge;
1096                 tgt_edge = tmp_edge;
1097
1098                 src_is_src = src_edge->src == node;
1099                 tgt_is_src = tgt_edge->src == node;
1100         }
1101
1102 #if     KAPS_DUMP
1103         if (pbqp->dump_file) {
1104                 char     txt[100];
1105                 sprintf(txt, "RII-Reduction of Node n%d", node->index);
1106                 dump_section(pbqp->dump_file, 2, txt);
1107                 pbqp_dump_graph(pbqp);
1108                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
1109                 dump_node(pbqp->dump_file, src_node);
1110                 dump_edge(pbqp->dump_file, src_edge);
1111                 dump_node(pbqp->dump_file, node);
1112                 dump_edge(pbqp->dump_file, tgt_edge);
1113                 dump_node(pbqp->dump_file, tgt_node);
1114         }
1115 #endif
1116
1117         src_mat = src_edge->costs;
1118         tgt_mat = tgt_edge->costs;
1119
1120         src_vec  = src_node->costs;
1121         tgt_vec  = tgt_node->costs;
1122         node_vec = node->costs;
1123
1124         row_len  = src_vec->len;
1125         col_len  = tgt_vec->len;
1126         node_len = node_vec->len;
1127
1128         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
1129
1130         for (row_index = 0; row_index < row_len; ++row_index) {
1131                 for (col_index = 0; col_index < col_len; ++col_index) {
1132                         vec = vector_copy(pbqp, node_vec);
1133
1134                         if (src_is_src) {
1135                                 vector_add_matrix_col(vec, src_mat, row_index);
1136                         } else {
1137                                 vector_add_matrix_row(vec, src_mat, row_index);
1138                         }
1139
1140                         if (tgt_is_src) {
1141                                 vector_add_matrix_col(vec, tgt_mat, col_index);
1142                         } else {
1143                                 vector_add_matrix_row(vec, tgt_mat, col_index);
1144                         }
1145
1146                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
1147
1148                         obstack_free(&pbqp->obstack, vec);
1149                 }
1150         }
1151
1152         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
1153
1154         /* Disconnect node. */
1155         disconnect_edge(src_node, src_edge);
1156         disconnect_edge(tgt_node, tgt_edge);
1157
1158 #if KAPS_STATISTIC
1159         pbqp->num_r2++;
1160 #endif
1161
1162         /* Add node to back propagation list. */
1163         node_bucket_insert(&reduced_bucket, node);
1164
1165         if (edge == NULL) {
1166                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
1167         } else {
1168                 // matrix
1169                 pbqp_matrix_add(edge->costs, mat);
1170
1171                 /* Free local matrix. */
1172                 obstack_free(&pbqp->obstack, mat);
1173
1174                 reorder_node(src_node);
1175                 reorder_node(tgt_node);
1176         }
1177
1178 #if     KAPS_DUMP
1179         if (pbqp->dump_file) {
1180                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1181                 dump_edge(pbqp->dump_file, edge);
1182         }
1183 #endif
1184
1185         /* Edge has changed so we simplify it. */
1186         simplify_edge(pbqp, edge);
1187 }
1188
1189 void select_alternative(pbqp_node *node, unsigned selected_index)
1190 {
1191         unsigned  edge_index;
1192         unsigned  node_index;
1193         unsigned  node_len;
1194         vector   *node_vec;
1195         unsigned  max_degree = pbqp_node_get_degree(node);
1196
1197         assert(node);
1198         node->solution = selected_index;
1199         node_vec = node->costs;
1200         node_len = node_vec->len;
1201         assert(selected_index < node_len);
1202
1203         /* Set all other costs to infinity. */
1204         for (node_index = 0; node_index < node_len; ++node_index) {
1205                 if (node_index != selected_index) {
1206                         node_vec->entries[node_index].data = INF_COSTS;
1207                 }
1208         }
1209
1210         /* Add all incident edges to edge bucket, since they are now independent. */
1211         for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1212                 insert_into_edge_bucket(node->edges[edge_index]);
1213         }
1214 }
1215
1216 pbqp_node *get_node_with_max_degree(void)
1217 {
1218         pbqp_node  **bucket       = node_buckets[3];
1219         unsigned     bucket_len   = node_bucket_get_length(bucket);
1220         unsigned     bucket_index;
1221         unsigned     max_degree   = 0;
1222         pbqp_node   *result       = NULL;
1223
1224         for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
1225                 pbqp_node *candidate = bucket[bucket_index];
1226                 unsigned   degree    = pbqp_node_get_degree(candidate);
1227
1228                 if (degree > max_degree) {
1229                         result = candidate;
1230                         max_degree = degree;
1231                 }
1232         }
1233
1234         return result;
1235 }
1236
1237 unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node)
1238 {
1239         pbqp_edge   *edge;
1240         vector      *node_vec;
1241         vector      *vec;
1242         pbqp_matrix *mat;
1243         unsigned     edge_index;
1244         unsigned     max_degree;
1245         unsigned     node_index;
1246         unsigned     node_len;
1247         unsigned     min_index    = 0;
1248         num          min          = INF_COSTS;
1249         int          is_src;
1250
1251         assert(pbqp);
1252         assert(node);
1253         node_vec   = node->costs;
1254         node_len   = node_vec->len;
1255         max_degree = pbqp_node_get_degree(node);
1256
1257         for (node_index = 0; node_index < node_len; ++node_index) {
1258                 num value = node_vec->entries[node_index].data;
1259
1260                 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1261                         edge   = node->edges[edge_index];
1262                         mat    = edge->costs;
1263                         is_src = edge->src == node;
1264
1265                         if (is_src) {
1266                                 vec = vector_copy(pbqp, edge->tgt->costs);
1267                                 vector_add_matrix_row(vec, mat, node_index);
1268                         } else {
1269                                 vec = vector_copy(pbqp, edge->src->costs);
1270                                 vector_add_matrix_col(vec, mat, node_index);
1271                         }
1272
1273                         value = pbqp_add(value, vector_get_min(vec));
1274
1275                         obstack_free(&pbqp->obstack, vec);
1276                 }
1277
1278                 if (value < min) {
1279                         min = value;
1280                         min_index = node_index;
1281                 }
1282         }
1283
1284         return min_index;
1285 }
1286
1287 int node_is_reduced(pbqp_node *node)
1288 {
1289         if (!reduced_bucket) return 0;
1290
1291         if (pbqp_node_get_degree(node) == 0) return 1;
1292
1293         return node_bucket_contains(reduced_bucket, node);
1294 }