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, src_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                 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
 294                         continue;
 295
 296                 for (src_index = 0; src_index < src_len; ++src_index) {
 297                         if (src_vec->entries[src_index].data == INF_COSTS)
 298                                 continue;
 299
 300                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS)
 301                                 continue;
 302
 303                         /* Matrix entry is finite. */
 304                         if (onlyOneZero) {
 305                                 DEL_ARR_F(mapping);
 306                                 return;
 307                         }
 308
 309                         onlyOneZero = 1;
 310                         mapping[tgt_index] = src_index;
 311                 }
 312         }
 313
 314         /* We know that we can merge the source node into the target node. */
 315         edge_len = pbqp_node_get_degree(src_node);
 316
 317 #if KAPS_STATISTIC
 318         pbqp->num_rm++;
 319 #endif
 320
 321         /* Reconnect the source's edges with the target node. */
 322         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 323                 pbqp_edge   *old_edge = src_node->edges[edge_index];
 324                 pbqp_matrix *old_matrix;
 325                 pbqp_matrix *new_matrix;
 326                 pbqp_node   *other_node;
 327                 unsigned     other_len;
 328                 unsigned     other_index;
 329                 unsigned     tgt_index;
 330
 331                 assert(old_edge);
 332
 333                 if (old_edge == edge)
 334                         continue;
 335
 336                 old_matrix = old_edge->costs;
 337                 assert(old_matrix);
 338
 339                 if (old_edge->tgt == src_node) {
 340                         other_node = edge->src;
 341                         other_len  = old_matrix->rows;
 342                 }
 343                 else {
 344                         other_node = edge->tgt;
 345                         other_len = old_matrix->cols;
 346                 }
 347                 assert(other_node);
 348
 349                 new_matrix = pbqp_matrix_alloc(pbqp, tgt_len, other_len);
 350
 351                 /* Source node selects the column of the old_matrix. */
 352                 if (old_edge->tgt == src_node) {
 353                         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 354                                 unsigned old_index = mapping[tgt_index];
 355                                 for (other_index = 0; other_index < other_len; ++other_index) {
 356                                         new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[other_index*src_len+old_index];
 357                                 }
 358                         }
 359                 }
 360                 /* Source node selects the row of the old_matrix. */
 361                 else {
 362                         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 363                                 unsigned old_index = mapping[tgt_index];
 364                                 for (other_index = 0; other_index < other_len; ++other_index) {
 365                                         new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[old_index*other_len+other_index];
 366                                 }
 367                         }
 368                 }
 369
 370                 add_edge_costs(pbqp, tgt_node->index, other_node->index, new_matrix);
 371
 372                 disconnect_edge(src_node, old_edge);
 373                 disconnect_edge(other_node, old_edge);
 374         }
 375
 376         /* Reduce the remaining source node via RI. */
 377         apply_RI(pbqp);
 378 }
 379
 380
 381 void reorder_node(pbqp_node *node)
 382 {
 383         unsigned    degree     = pbqp_node_get_degree(node);
 384         /* Assume node lost one incident edge. */
 385         unsigned    old_degree = degree + 1;
 386
 387         if (!buckets_filled) return;
 388
 389         /* Same bucket as before */
 390         if (degree > 2) return;
 391
 392         if (!node_bucket_contains(node_buckets[old_degree], node)) {
 393                 /* Old arity is new arity, so we have nothing to do. */
 394                 assert(node_bucket_contains(node_buckets[degree], node));
 395                 return;
 396         }
 397
 398         /* Delete node from old bucket... */
 399         node_bucket_remove(&node_buckets[old_degree], node);
 400
 401         /* ..and add to new one. */
 402         node_bucket_insert(&node_buckets[degree], node);
 403 }
 404
 405 #if KAPS_STATISTIC
 406 void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
 407 {
 408         pbqp_matrix    *mat;
 409         pbqp_node      *src_node;
 410         pbqp_node      *tgt_node;
 411         vector         *src_vec;
 412         vector         *tgt_vec;
 413         int             src_len;
 414         int             tgt_len;
 415         int             src_index;
 416         int             tgt_index;
 417
 418         assert(pbqp);
 419         assert(edge);
 420
 421         src_node = edge->src;
 422         tgt_node = edge->tgt;
 423         assert(src_node);
 424         assert(tgt_node);
 425
 426         src_vec = src_node->costs;
 427         tgt_vec = tgt_node->costs;
 428         assert(src_vec);
 429         assert(tgt_vec);
 430
 431         src_len = src_vec->len;
 432         tgt_len = tgt_vec->len;
 433         assert(src_len > 0);
 434         assert(tgt_len > 0);
 435
 436         mat = edge->costs;
 437         assert(mat);
 438
 439         if (src_len == 1 && tgt_len == 1) {
 440                 //panic("Something is wrong");
 441         }
 442
 443         int allRowsOk = 1;
 444         for (src_index = 0; src_index < src_len; ++src_index) {
 445                 int onlyOneZero = 0;
 446                 if (src_vec->entries[src_index].data == INF_COSTS) {
 447                         continue;
 448                 }
 449                 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 450                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 451                                 continue;
 452                         }
 453                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 454                                 if (onlyOneZero) {
 455                                         onlyOneZero = 0;
 456                                         break;
 457                                 } else {
 458                                         onlyOneZero = 1;
 459                                         continue;
 460                                 }
 461                         }
 462                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 463                                 continue;
 464                         }
 465                         onlyOneZero = 0;
 466                         break;
 467                 }
 468                 allRowsOk &= onlyOneZero;
 469         }
 470
 471         int allColsOk = 1;
 472         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 473                 int onlyOneZero = 0;
 474                 if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 475                         continue;
 476                 }
 477                 for (src_index = 0; src_index < src_len; ++src_index) {
 478                         if (src_vec->entries[src_index].data == INF_COSTS) {
 479                                 continue;
 480                         }
 481                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 482                                 if (onlyOneZero) {
 483                                         onlyOneZero = 0;
 484                                         break;
 485                                 } else {
 486                                         onlyOneZero = 1;
 487                                         continue;
 488                                 }
 489                         }
 490                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 491                                 continue;
 492                         }
 493                         onlyOneZero = 0;
 494                         break;
 495                 }
 496                 allColsOk &= onlyOneZero;
 497         }
 498
 499         if (allRowsOk || allColsOk) {
 500                 pbqp->num_rm++;
 501         }
 502 }
 503 #endif
 504
 505 void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 506 {
 507         pbqp_matrix    *mat;
 508         pbqp_node      *src_node;
 509         pbqp_node      *tgt_node;
 510         vector         *src_vec;
 511         vector         *tgt_vec;
 512         int             src_len;
 513         int             tgt_len;
 514
 515         assert(pbqp);
 516         assert(edge);
 517
 518         src_node = edge->src;
 519         tgt_node = edge->tgt;
 520         assert(src_node);
 521         assert(tgt_node);
 522
 523         /* If edge are already deleted, we have nothing to do. */
 524         if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
 525                 return;
 526
 527 #if     KAPS_DUMP
 528         if (pbqp->dump_file) {
 529                 char txt[100];
 530                 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
 531                 dump_section(pbqp->dump_file, 3, txt);
 532         }
 533 #endif
 534
 535         src_vec = src_node->costs;
 536         tgt_vec = tgt_node->costs;
 537         assert(src_vec);
 538         assert(tgt_vec);
 539
 540         src_len = src_vec->len;
 541         tgt_len = tgt_vec->len;
 542         assert(src_len > 0);
 543         assert(tgt_len > 0);
 544
 545         mat = edge->costs;
 546         assert(mat);
 547
 548 #if     KAPS_DUMP
 549         if (pbqp->dump_file) {
 550                 fputs("Input:<br>\n", pbqp->dump_file);
 551                 dump_simplifyedge(pbqp, edge);
 552         }
 553 #endif
 554
 555         normalize_towards_source(edge);
 556         normalize_towards_target(edge);
 557
 558 #if     KAPS_DUMP
 559         if (pbqp->dump_file) {
 560                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 561                 dump_simplifyedge(pbqp, edge);
 562         }
 563 #endif
 564
 565         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 566 #if     KAPS_DUMP
 567                 if (pbqp->dump_file) {
 568                         fputs("edge has been eliminated<br>\n", pbqp->dump_file);
 569                 }
 570 #endif
 571
 572 #if KAPS_STATISTIC
 573                 pbqp->num_edges++;
 574 #endif
 575
 576                 delete_edge(edge);
 577                 reorder_node(src_node);
 578                 reorder_node(tgt_node);
 579         }
 580 }
 581
 582 void initial_simplify_edges(pbqp *pbqp)
 583 {
 584         unsigned node_index;
 585         unsigned node_len;
 586
 587         assert(pbqp);
 588
 589         #if KAPS_TIMING
 590                 ir_timer_t *t_int_simpl = ir_timer_register("be_pbqp_init_simp", "PBQP Initial simplify edges");
 591                 ir_timer_reset_and_start(t_int_simpl);
 592         #endif
 593
 594 #if     KAPS_DUMP
 595         if (pbqp->dump_file) {
 596                 pbqp_dump_input(pbqp);
 597                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 598         }
 599 #endif
 600
 601         node_len = pbqp->num_nodes;
 602
 603         init_buckets();
 604
 605         /* First simplify all edges. */
 606         for (node_index = 0; node_index < node_len; ++node_index) {
 607                 unsigned    edge_index;
 608                 pbqp_node  *node = get_node(pbqp, node_index);
 609                 pbqp_edge **edges;
 610                 unsigned    edge_len;
 611
 612                 if (!node) continue;
 613
 614                 edges = node->edges;
 615                 edge_len = pbqp_node_get_degree(node);
 616
 617                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 618                         pbqp_edge *edge = edges[edge_index];
 619
 620                         /* Simplify only once per edge. */
 621                         if (node != edge->src) continue;
 622
 623                         simplify_edge(pbqp, edge);
 624                 }
 625         }
 626
 627         #if KAPS_TIMING
 628                 ir_timer_stop(t_int_simpl);
 629                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_int_simpl), (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
 630         #endif
 631 }
 632
 633 num determine_solution(pbqp *pbqp)
 634 {
 635         unsigned node_index;
 636         unsigned node_len;
 637         num      solution   = 0;
 638
 639         #if KAPS_TIMING
 640                 ir_timer_t *t_det_solution = ir_timer_register("be_det_solution", "PBQP Determine Solution");
 641                 ir_timer_reset_and_start(t_det_solution);
 642         #endif
 643
 644 #if     KAPS_DUMP
 645         FILE     *file;
 646 #endif
 647
 648         assert(pbqp);
 649
 650 #if     KAPS_DUMP
 651         file = pbqp->dump_file;
 652
 653         if (file) {
 654                 dump_section(file, 1, "4. Determine Solution/Minimum");
 655                 dump_section(file, 2, "4.1. Trivial Solution");
 656         }
 657 #endif
 658
 659         /* Solve trivial nodes and calculate solution. */
 660         node_len = node_bucket_get_length(node_buckets[0]);
 661
 662 #if KAPS_STATISTIC
 663         pbqp->num_r0 = node_len;
 664 #endif
 665
 666         for (node_index = 0; node_index < node_len; ++node_index) {
 667                 pbqp_node *node = node_buckets[0][node_index];
 668                 assert(node);
 669
 670                 node->solution = vector_get_min_index(node->costs);
 671                 solution       = pbqp_add(solution,
 672                                 node->costs->entries[node->solution].data);
 673
 674 #if     KAPS_DUMP
 675                 if (file) {
 676                         fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
 677                         dump_node(file, node);
 678                 }
 679 #endif
 680         }
 681
 682 #if     KAPS_DUMP
 683         if (file) {
 684                 dump_section(file, 2, "Minimum");
 685 #if KAPS_USE_UNSIGNED
 686                 fprintf(file, "Minimum is equal to %u.", solution);
 687 #else
 688                 fprintf(file, "Minimum is equal to %lld.", solution);
 689 #endif
 690         }
 691 #endif
 692
 693         #if KAPS_TIMING
 694                 ir_timer_stop(t_det_solution);
 695                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_det_solution), (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
 696         #endif
 697
 698         return solution;
 699 }
 700
 701 static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 702 {
 703         pbqp_edge   *edge;
 704         pbqp_node   *other;
 705         pbqp_matrix *mat;
 706         vector      *vec;
 707         int          is_src;
 708
 709         assert(pbqp);
 710         assert(node);
 711
 712         edge = node->edges[0];
 713         mat = edge->costs;
 714         is_src = edge->src == node;
 715         vec = node->costs;
 716
 717         if (is_src) {
 718                 other = edge->tgt;
 719                 assert(other);
 720
 721                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
 722         } else {
 723                 other = edge->src;
 724                 assert(other);
 725
 726                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
 727         }
 728
 729 #if     KAPS_DUMP
 730         if (pbqp->dump_file) {
 731                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 732         }
 733 #endif
 734 }
 735
 736 static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
 737 {
 738         pbqp_edge   *src_edge   = node->edges[0];
 739         pbqp_edge   *tgt_edge   = node->edges[1];
 740         int          src_is_src = src_edge->src == node;
 741         int          tgt_is_src = tgt_edge->src == node;
 742         pbqp_matrix *src_mat;
 743         pbqp_matrix *tgt_mat;
 744         pbqp_node   *src_node;
 745         pbqp_node   *tgt_node;
 746         vector      *vec;
 747         vector      *node_vec;
 748         unsigned     col_index;
 749         unsigned     row_index;
 750
 751         assert(pbqp);
 752
 753         if (src_is_src) {
 754                 src_node = src_edge->tgt;
 755         } else {
 756                 src_node = src_edge->src;
 757         }
 758
 759         if (tgt_is_src) {
 760                 tgt_node = tgt_edge->tgt;
 761         } else {
 762                 tgt_node = tgt_edge->src;
 763         }
 764
 765         /* Swap nodes if necessary. */
 766         if (tgt_node->index < src_node->index) {
 767                 pbqp_node *tmp_node;
 768                 pbqp_edge *tmp_edge;
 769
 770                 tmp_node = src_node;
 771                 src_node = tgt_node;
 772                 tgt_node = tmp_node;
 773
 774                 tmp_edge = src_edge;
 775                 src_edge = tgt_edge;
 776                 tgt_edge = tmp_edge;
 777
 778                 src_is_src = src_edge->src == node;
 779                 tgt_is_src = tgt_edge->src == node;
 780         }
 781
 782         src_mat = src_edge->costs;
 783         tgt_mat = tgt_edge->costs;
 784
 785         node_vec = node->costs;
 786
 787         row_index = src_node->solution;
 788         col_index = tgt_node->solution;
 789
 790         vec = vector_copy(pbqp, node_vec);
 791
 792         if (src_is_src) {
 793                 vector_add_matrix_col(vec, src_mat, row_index);
 794         } else {
 795                 vector_add_matrix_row(vec, src_mat, row_index);
 796         }
 797
 798         if (tgt_is_src) {
 799                 vector_add_matrix_col(vec, tgt_mat, col_index);
 800         } else {
 801                 vector_add_matrix_row(vec, tgt_mat, col_index);
 802         }
 803
 804         node->solution = vector_get_min_index(vec);
 805
 806 #if     KAPS_DUMP
 807         if (pbqp->dump_file) {
 808                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 809         }
 810 #endif
 811
 812         obstack_free(&pbqp->obstack, vec);
 813 }
 814
 815 void back_propagate(pbqp *pbqp)
 816 {
 817         unsigned node_index;
 818         unsigned node_len   = node_bucket_get_length(reduced_bucket);
 819
 820         assert(pbqp);
 821
 822 #if     KAPS_DUMP
 823         if (pbqp->dump_file) {
 824                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 825         }
 826 #endif
 827
 828         for (node_index = node_len; node_index > 0; --node_index) {
 829                 pbqp_node *node = reduced_bucket[node_index - 1];
 830
 831                 switch (pbqp_node_get_degree(node)) {
 832                         case 1:
 833                                 back_propagate_RI(pbqp, node);
 834                                 break;
 835                         case 2:
 836                                 back_propagate_RII(pbqp, node);
 837                                 break;
 838                         default:
 839                                 panic("Only nodes with degree one or two should be in this bucket");
 840                                 break;
 841                 }
 842         }
 843 }
 844
 845 void apply_edge(pbqp *pbqp)
 846 {
 847         pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
 848
 849         simplify_edge(pbqp, edge);
 850 }
 851
 852 void apply_RI(pbqp *pbqp)
 853 {
 854         pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
 855         pbqp_edge   *edge       = node->edges[0];
 856         pbqp_matrix *mat        = edge->costs;
 857         int          is_src     = edge->src == node;
 858         pbqp_node   *other_node;
 859
 860         (void ) pbqp;
 861         assert(pbqp_node_get_degree(node) == 1);
 862
 863         if (is_src) {
 864                 other_node = edge->tgt;
 865         } else {
 866                 other_node = edge->src;
 867         }
 868
 869 #if     KAPS_DUMP
 870         if (pbqp->dump_file) {
 871                 char     txt[100];
 872                 sprintf(txt, "RI-Reduction of Node n%d", node->index);
 873                 dump_section(pbqp->dump_file, 2, txt);
 874                 pbqp_dump_graph(pbqp);
 875                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 876                 dump_node(pbqp->dump_file, node);
 877                 dump_node(pbqp->dump_file, other_node);
 878                 dump_edge(pbqp->dump_file, edge);
 879         }
 880 #endif
 881
 882         if (is_src) {
 883                 pbqp_matrix_add_to_all_cols(mat, node->costs);
 884                 normalize_towards_target(edge);
 885         } else {
 886                 pbqp_matrix_add_to_all_rows(mat, node->costs);
 887                 normalize_towards_source(edge);
 888         }
 889         disconnect_edge(other_node, edge);
 890
 891 #if     KAPS_DUMP
 892         if (pbqp->dump_file) {
 893                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 894                 dump_node(pbqp->dump_file, other_node);
 895         }
 896 #endif
 897
 898         reorder_node(other_node);
 899
 900 #if KAPS_STATISTIC
 901         pbqp->num_r1++;
 902 #endif
 903
 904         /* Add node to back propagation list. */
 905         node_bucket_insert(&reduced_bucket, node);
 906 }
 907
 908 void apply_RII(pbqp *pbqp)
 909 {
 910         pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
 911         pbqp_edge   *src_edge   = node->edges[0];
 912         pbqp_edge   *tgt_edge   = node->edges[1];
 913         int          src_is_src = src_edge->src == node;
 914         int          tgt_is_src = tgt_edge->src == node;
 915         pbqp_matrix *src_mat;
 916         pbqp_matrix *tgt_mat;
 917         pbqp_node   *src_node;
 918         pbqp_node   *tgt_node;
 919         pbqp_matrix *mat;
 920         vector      *vec;
 921         vector      *node_vec;
 922         vector      *src_vec;
 923         vector      *tgt_vec;
 924         unsigned     col_index;
 925         unsigned     col_len;
 926         unsigned     row_index;
 927         unsigned     row_len;
 928         unsigned     node_len;
 929
 930         assert(pbqp);
 931         assert(pbqp_node_get_degree(node) == 2);
 932
 933         if (src_is_src) {
 934                 src_node = src_edge->tgt;
 935         } else {
 936                 src_node = src_edge->src;
 937         }
 938
 939         if (tgt_is_src) {
 940                 tgt_node = tgt_edge->tgt;
 941         } else {
 942                 tgt_node = tgt_edge->src;
 943         }
 944
 945         /* Swap nodes if necessary. */
 946         if (tgt_node->index < src_node->index) {
 947                 pbqp_node *tmp_node;
 948                 pbqp_edge *tmp_edge;
 949
 950                 tmp_node = src_node;
 951                 src_node = tgt_node;
 952                 tgt_node = tmp_node;
 953
 954                 tmp_edge = src_edge;
 955                 src_edge = tgt_edge;
 956                 tgt_edge = tmp_edge;
 957
 958                 src_is_src = src_edge->src == node;
 959                 tgt_is_src = tgt_edge->src == node;
 960         }
 961
 962 #if     KAPS_DUMP
 963         if (pbqp->dump_file) {
 964                 char     txt[100];
 965                 sprintf(txt, "RII-Reduction of Node n%d", node->index);
 966                 dump_section(pbqp->dump_file, 2, txt);
 967                 pbqp_dump_graph(pbqp);
 968                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 969                 dump_node(pbqp->dump_file, src_node);
 970                 dump_edge(pbqp->dump_file, src_edge);
 971                 dump_node(pbqp->dump_file, node);
 972                 dump_edge(pbqp->dump_file, tgt_edge);
 973                 dump_node(pbqp->dump_file, tgt_node);
 974         }
 975 #endif
 976
 977         src_mat = src_edge->costs;
 978         tgt_mat = tgt_edge->costs;
 979
 980         src_vec  = src_node->costs;
 981         tgt_vec  = tgt_node->costs;
 982         node_vec = node->costs;
 983
 984         row_len  = src_vec->len;
 985         col_len  = tgt_vec->len;
 986         node_len = node_vec->len;
 987
 988         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
 989
 990         for (row_index = 0; row_index < row_len; ++row_index) {
 991                 for (col_index = 0; col_index < col_len; ++col_index) {
 992                         vec = vector_copy(pbqp, node_vec);
 993
 994                         if (src_is_src) {
 995                                 vector_add_matrix_col(vec, src_mat, row_index);
 996                         } else {
 997                                 vector_add_matrix_row(vec, src_mat, row_index);
 998                         }
 999
1000                         if (tgt_is_src) {
1001                                 vector_add_matrix_col(vec, tgt_mat, col_index);
1002                         } else {
1003                                 vector_add_matrix_row(vec, tgt_mat, col_index);
1004                         }
1005
1006                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
1007
1008                         obstack_free(&pbqp->obstack, vec);
1009                 }
1010         }
1011
1012         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
1013
1014         /* Disconnect node. */
1015         disconnect_edge(src_node, src_edge);
1016         disconnect_edge(tgt_node, tgt_edge);
1017
1018 #if KAPS_STATISTIC
1019         pbqp->num_r2++;
1020 #endif
1021
1022         /* Add node to back propagation list. */
1023         node_bucket_insert(&reduced_bucket, node);
1024
1025         if (edge == NULL) {
1026                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
1027         } else {
1028                 // matrix
1029                 pbqp_matrix_add(edge->costs, mat);
1030
1031                 /* Free local matrix. */
1032                 obstack_free(&pbqp->obstack, mat);
1033
1034                 reorder_node(src_node);
1035                 reorder_node(tgt_node);
1036         }
1037
1038 #if     KAPS_DUMP
1039         if (pbqp->dump_file) {
1040                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1041                 dump_edge(pbqp->dump_file, edge);
1042         }
1043 #endif
1044
1045         /* Edge has changed so we simplify it. */
1046         simplify_edge(pbqp, edge);
1047 }
1048
1049 void select_alternative(pbqp_node *node, unsigned selected_index)
1050 {
1051         unsigned  edge_index;
1052         unsigned  node_index;
1053         unsigned  node_len;
1054         vector   *node_vec;
1055         unsigned  max_degree = pbqp_node_get_degree(node);
1056
1057         assert(node);
1058         node->solution = selected_index;
1059         node_vec = node->costs;
1060         node_len = node_vec->len;
1061         assert(selected_index < node_len);
1062
1063         /* Set all other costs to infinity. */
1064         for (node_index = 0; node_index < node_len; ++node_index) {
1065                 if (node_index != selected_index) {
1066                         node_vec->entries[node_index].data = INF_COSTS;
1067                 }
1068         }
1069
1070         /* Add all incident edges to edge bucket, since they are now independent. */
1071         for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1072                 insert_into_edge_bucket(node->edges[edge_index]);
1073         }
1074 }
1075
1076 pbqp_node *get_node_with_max_degree(void)
1077 {
1078         pbqp_node  **bucket       = node_buckets[3];
1079         unsigned     bucket_len   = node_bucket_get_length(bucket);
1080         unsigned     bucket_index;
1081         unsigned     max_degree   = 0;
1082         pbqp_node   *result       = NULL;
1083
1084         for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
1085                 pbqp_node *candidate = bucket[bucket_index];
1086                 unsigned   degree    = pbqp_node_get_degree(candidate);
1087
1088                 if (degree > max_degree) {
1089                         result = candidate;
1090                         max_degree = degree;
1091                 }
1092         }
1093
1094         return result;
1095 }
1096
1097 unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node)
1098 {
1099         pbqp_edge   *edge;
1100         vector      *node_vec;
1101         vector      *vec;
1102         pbqp_matrix *mat;
1103         unsigned     edge_index;
1104         unsigned     max_degree;
1105         unsigned     node_index;
1106         unsigned     node_len;
1107         unsigned     min_index    = 0;
1108         num          min          = INF_COSTS;
1109         int          is_src;
1110
1111         assert(pbqp);
1112         assert(node);
1113         node_vec   = node->costs;
1114         node_len   = node_vec->len;
1115         max_degree = pbqp_node_get_degree(node);
1116
1117         for (node_index = 0; node_index < node_len; ++node_index) {
1118                 num value = node_vec->entries[node_index].data;
1119
1120                 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1121                         edge   = node->edges[edge_index];
1122                         mat    = edge->costs;
1123                         is_src = edge->src == node;
1124
1125                         if (is_src) {
1126                                 vec = vector_copy(pbqp, edge->tgt->costs);
1127                                 vector_add_matrix_row(vec, mat, node_index);
1128                         } else {
1129                                 vec = vector_copy(pbqp, edge->src->costs);
1130                                 vector_add_matrix_col(vec, mat, node_index);
1131                         }
1132
1133                         value = pbqp_add(value, vector_get_min(vec));
1134
1135                         obstack_free(&pbqp->obstack, vec);
1136                 }
1137
1138                 if (value < min) {
1139                         min = value;
1140                         min_index = node_index;
1141                 }
1142         }
1143
1144         return min_index;
1145 }
1146
1147 int node_is_reduced(pbqp_node *node)
1148 {
1149         if (!reduced_bucket) return 0;
1150
1151         if (pbqp_node_get_degree(node) == 0) return 1;
1152
1153         return node_bucket_contains(reduced_bucket, node);
1154 }