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 #if KAPS_STATISTIC
  55 static int dump = 0;
  56 #endif
  57
  58 static void insert_into_edge_bucket(pbqp_edge *edge)
  59 {
  60         if (edge_bucket_contains(edge_bucket, edge)) {
  61                 /* Edge is already inserted. */
  62                 return;
  63         }
  64
  65         edge_bucket_insert(&edge_bucket, edge);
  66 }
  67
  68 static void init_buckets(void)
  69 {
  70         int i;
  71
  72         edge_bucket_init(&edge_bucket);
  73         node_bucket_init(&reduced_bucket);
  74
  75         for (i = 0; i < 4; ++i) {
  76                 node_bucket_init(&node_buckets[i]);
  77         }
  78 }
  79
  80 void free_buckets(void)
  81 {
  82         int i;
  83
  84         for (i = 0; i < 4; ++i) {
  85                 node_bucket_free(&node_buckets[i]);
  86         }
  87
  88         edge_bucket_free(&edge_bucket);
  89         node_bucket_free(&reduced_bucket);
  90
  91         buckets_filled = 0;
  92 }
  93
  94 void fill_node_buckets(pbqp *pbqp)
  95 {
  96         unsigned node_index;
  97         unsigned node_len;
  98
  99         assert(pbqp);
 100         node_len = pbqp->num_nodes;
 101
 102         #if KAPS_TIMING
 103                 ir_timer_t *t_fill_buckets = ir_timer_register("be_pbqp_fill_buckets", "PBQP Fill Nodes into buckets");
 104                 ir_timer_reset_and_start(t_fill_buckets);
 105         #endif
 106
 107         for (node_index = 0; node_index < node_len; ++node_index) {
 108                 unsigned   degree;
 109                 pbqp_node *node = get_node(pbqp, node_index);
 110
 111                 if (!node) continue;
 112
 113                 degree = pbqp_node_get_degree(node);
 114
 115                 /* We have only one bucket for nodes with arity >= 3. */
 116                 if (degree > 3) {
 117                         degree = 3;
 118                 }
 119
 120                 node_bucket_insert(&node_buckets[degree], node);
 121         }
 122
 123         buckets_filled = 1;
 124
 125         #if KAPS_TIMING
 126                 ir_timer_stop(t_fill_buckets);
 127                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_fill_buckets), (double)ir_timer_elapsed_usec(t_fill_buckets) / 1000.0);
 128         #endif
 129 }
 130
 131 static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge)
 132 {
 133         pbqp_matrix    *mat;
 134         pbqp_node      *src_node;
 135         pbqp_node      *tgt_node;
 136         vector         *src_vec;
 137         vector         *tgt_vec;
 138         int             src_len;
 139         int             tgt_len;
 140         int             src_index;
 141
 142         assert(pbqp);
 143         assert(edge);
 144
 145         src_node = edge->src;
 146         tgt_node = edge->tgt;
 147         assert(src_node);
 148         assert(tgt_node);
 149
 150         src_vec = src_node->costs;
 151         tgt_vec = tgt_node->costs;
 152         assert(src_vec);
 153         assert(tgt_vec);
 154
 155         src_len = src_vec->len;
 156         tgt_len = tgt_vec->len;
 157         assert(src_len > 0);
 158         assert(tgt_len > 0);
 159
 160         mat = edge->costs;
 161         assert(mat);
 162
 163         /* Normalize towards source node. */
 164         for (src_index = 0; src_index < src_len; ++src_index) {
 165                 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
 166
 167                 if (min != 0) {
 168                         if (src_vec->entries[src_index].data == INF_COSTS) {
 169                                 pbqp_matrix_set_row_value(mat, src_index, 0);
 170                         } else {
 171                                 pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
 172                         }
 173                         src_vec->entries[src_index].data = pbqp_add(
 174                                         src_vec->entries[src_index].data, min);
 175
 176                         if (min == INF_COSTS) {
 177                                 unsigned edge_index;
 178                                 unsigned edge_len = pbqp_node_get_degree(src_node);
 179
 180                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 181                                         pbqp_edge *edge_candidate = src_node->edges[edge_index];
 182                                         if (edge_candidate != edge) {
 183                                                 insert_into_edge_bucket(edge_candidate);
 184                                         }
 185                                 }
 186                         }
 187                 }
 188         }
 189 }
 190
 191 static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge)
 192 {
 193         pbqp_matrix    *mat;
 194         pbqp_node      *src_node;
 195         pbqp_node      *tgt_node;
 196         vector         *src_vec;
 197         vector         *tgt_vec;
 198         int             src_len;
 199         int             tgt_len;
 200         int             tgt_index;
 201
 202         assert(pbqp);
 203         assert(edge);
 204
 205         src_node = edge->src;
 206         tgt_node = edge->tgt;
 207         assert(src_node);
 208         assert(tgt_node);
 209
 210         src_vec = src_node->costs;
 211         tgt_vec = tgt_node->costs;
 212         assert(src_vec);
 213         assert(tgt_vec);
 214
 215         src_len = src_vec->len;
 216         tgt_len = tgt_vec->len;
 217         assert(src_len > 0);
 218         assert(tgt_len > 0);
 219
 220         mat = edge->costs;
 221         assert(mat);
 222
 223         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 224                 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 225
 226                 if (min != 0) {
 227                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 228                                 pbqp_matrix_set_col_value(mat, tgt_index, 0);
 229                         } else {
 230                                 pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
 231                         }
 232                         tgt_vec->entries[tgt_index].data = pbqp_add(
 233                                         tgt_vec->entries[tgt_index].data, min);
 234
 235                         if (min == INF_COSTS) {
 236                                 unsigned edge_index;
 237                                 unsigned edge_len = pbqp_node_get_degree(tgt_node);
 238
 239                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 240                                         pbqp_edge *edge_candidate = tgt_node->edges[edge_index];
 241                                         if (edge_candidate != edge) {
 242                                                 insert_into_edge_bucket(edge_candidate);
 243                                         }
 244                                 }
 245                         }
 246                 }
 247         }
 248 }
 249
 250 static void reorder_node(pbqp_node *node)
 251 {
 252         unsigned    degree     = pbqp_node_get_degree(node);
 253         /* Assume node lost one incident edge. */
 254         unsigned    old_degree = degree + 1;
 255
 256         if (!buckets_filled) return;
 257
 258         /* Same bucket as before */
 259         if (degree > 2) return;
 260
 261         if (!node_bucket_contains(node_buckets[old_degree], node)) {
 262                 /* Old arity is new arity, so we have nothing to do. */
 263                 assert(node_bucket_contains(node_buckets[degree], node));
 264                 return;
 265         }
 266
 267         /* Delete node from old bucket... */
 268         node_bucket_remove(&node_buckets[old_degree], node);
 269
 270         /* ..and add to new one. */
 271         node_bucket_insert(&node_buckets[degree], node);
 272 }
 273
 274 #if 0
 275 static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
 276 {
 277         pbqp_matrix    *mat;
 278         pbqp_node      *src_node;
 279         pbqp_node      *tgt_node;
 280         vector         *src_vec;
 281         vector         *tgt_vec;
 282         int             src_len;
 283         int             tgt_len;
 284         int             src_index;
 285         int             tgt_index;
 286
 287         assert(pbqp);
 288         assert(edge);
 289
 290         src_node = edge->src;
 291         tgt_node = edge->tgt;
 292         assert(src_node);
 293         assert(tgt_node);
 294
 295         src_vec = src_node->costs;
 296         tgt_vec = tgt_node->costs;
 297         assert(src_vec);
 298         assert(tgt_vec);
 299
 300         src_len = src_vec->len;
 301         tgt_len = tgt_vec->len;
 302         assert(src_len > 0);
 303         assert(tgt_len > 0);
 304
 305         mat = edge->costs;
 306         assert(mat);
 307
 308         if (src_len == 1 && tgt_len == 1) {
 309                 //panic("Something is wrong");
 310         }
 311
 312         int allRowsOk = 1;
 313         for (src_index = 0; src_index < src_len; ++src_index) {
 314                 int onlyOneZero = 0;
 315                 if (src_vec->entries[src_index].data == INF_COSTS) {
 316                         continue;
 317                 }
 318                 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 319                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 320                                 continue;
 321                         }
 322                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 323                                 if (onlyOneZero) {
 324                                         onlyOneZero = 0;
 325                                         break;
 326                                 } else {
 327                                         onlyOneZero = 1;
 328                                         continue;
 329                                 }
 330                         }
 331                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 332                                 continue;
 333                         }
 334                         onlyOneZero = 0;
 335                         break;
 336                 }
 337                 allRowsOk &= onlyOneZero;
 338         }
 339
 340         int allColsOk = 1;
 341         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 342                 int onlyOneZero = 0;
 343                 if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 344                         continue;
 345                 }
 346                 for (src_index = 0; src_index < src_len; ++src_index) {
 347                         if (src_vec->entries[src_index].data == INF_COSTS) {
 348                                 continue;
 349                         }
 350                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 351                                 if (onlyOneZero) {
 352                                         onlyOneZero = 0;
 353                                         break;
 354                                 } else {
 355                                         onlyOneZero = 1;
 356                                         continue;
 357                                 }
 358                         }
 359                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 360                                 continue;
 361                         }
 362                         onlyOneZero = 0;
 363                         break;
 364                 }
 365                 allColsOk &= onlyOneZero;
 366         }
 367
 368         if (allRowsOk && allColsOk) {
 369                 panic("Hurray");
 370         }
 371 }
 372 #endif
 373
 374 void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 375 {
 376         pbqp_matrix    *mat;
 377         pbqp_node      *src_node;
 378         pbqp_node      *tgt_node;
 379         vector         *src_vec;
 380         vector         *tgt_vec;
 381         int             src_len;
 382         int             tgt_len;
 383
 384         assert(pbqp);
 385         assert(edge);
 386
 387         src_node = edge->src;
 388         tgt_node = edge->tgt;
 389         assert(src_node);
 390         assert(tgt_node);
 391
 392         /* If edge are already deleted, we have nothing to do. */
 393         if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
 394                 return;
 395
 396 #if     KAPS_DUMP
 397         if (pbqp->dump_file) {
 398                 char txt[100];
 399                 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
 400                 dump_section(pbqp->dump_file, 3, txt);
 401         }
 402 #endif
 403
 404         src_vec = src_node->costs;
 405         tgt_vec = tgt_node->costs;
 406         assert(src_vec);
 407         assert(tgt_vec);
 408
 409         src_len = src_vec->len;
 410         tgt_len = tgt_vec->len;
 411         assert(src_len > 0);
 412         assert(tgt_len > 0);
 413
 414         mat = edge->costs;
 415         assert(mat);
 416
 417 #if     KAPS_DUMP
 418         if (pbqp->dump_file) {
 419                 fputs("Input:<br>\n", pbqp->dump_file);
 420                 dump_simplifyedge(pbqp, edge);
 421         }
 422 #endif
 423
 424         normalize_towards_source(pbqp, edge);
 425         normalize_towards_target(pbqp, edge);
 426
 427 #if     KAPS_DUMP
 428         if (pbqp->dump_file) {
 429                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 430                 dump_simplifyedge(pbqp, edge);
 431         }
 432 #endif
 433
 434         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 435 #if     KAPS_DUMP
 436                 if (pbqp->dump_file) {
 437                         fputs("edge has been eliminated<br>\n", pbqp->dump_file);
 438                 }
 439 #endif
 440
 441 #if KAPS_STATISTIC
 442                 if (dump == 0) {
 443                         pbqp->num_edges++;
 444                 }
 445 #endif
 446
 447                 delete_edge(edge);
 448                 reorder_node(src_node);
 449                 reorder_node(tgt_node);
 450         }
 451 }
 452
 453 void initial_simplify_edges(pbqp *pbqp)
 454 {
 455         unsigned node_index;
 456         unsigned node_len;
 457
 458         assert(pbqp);
 459
 460         #if KAPS_TIMING
 461                 ir_timer_t *t_int_simpl = ir_timer_register("be_pbqp_init_simp", "PBQP Initial simplify edges");
 462                 ir_timer_reset_and_start(t_int_simpl);
 463         #endif
 464
 465 #if     KAPS_DUMP
 466         if (pbqp->dump_file) {
 467                 pbqp_dump_input(pbqp);
 468                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 469         }
 470 #endif
 471
 472         node_len = pbqp->num_nodes;
 473
 474         init_buckets();
 475
 476         /* First simplify all edges. */
 477         for (node_index = 0; node_index < node_len; ++node_index) {
 478                 unsigned    edge_index;
 479                 pbqp_node  *node = get_node(pbqp, node_index);
 480                 pbqp_edge **edges;
 481                 unsigned    edge_len;
 482
 483                 if (!node) continue;
 484
 485                 edges = node->edges;
 486                 edge_len = pbqp_node_get_degree(node);
 487
 488                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 489                         pbqp_edge *edge = edges[edge_index];
 490
 491                         /* Simplify only once per edge. */
 492                         if (node != edge->src) continue;
 493
 494                         simplify_edge(pbqp, edge);
 495                 }
 496         }
 497
 498         #if KAPS_TIMING
 499                 ir_timer_stop(t_int_simpl);
 500                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_int_simpl), (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
 501         #endif
 502 }
 503
 504 num determine_solution(pbqp *pbqp)
 505 {
 506         unsigned node_index;
 507         unsigned node_len;
 508         num      solution   = 0;
 509
 510         #if KAPS_TIMING
 511                 ir_timer_t *t_det_solution = ir_timer_register("be_det_solution", "PBQP Determine Solution");
 512                 ir_timer_reset_and_start(t_det_solution);
 513         #endif
 514
 515 #if     KAPS_DUMP
 516         FILE     *file;
 517 #endif
 518
 519         assert(pbqp);
 520
 521 #if     KAPS_DUMP
 522         file = pbqp->dump_file;
 523
 524         if (file) {
 525                 dump_section(file, 1, "4. Determine Solution/Minimum");
 526                 dump_section(file, 2, "4.1. Trivial Solution");
 527         }
 528 #endif
 529
 530         /* Solve trivial nodes and calculate solution. */
 531         node_len = node_bucket_get_length(node_buckets[0]);
 532
 533 #if KAPS_STATISTIC
 534         if (dump == 0) {
 535                 pbqp->num_r0 = node_len;
 536         }
 537 #endif
 538
 539         for (node_index = 0; node_index < node_len; ++node_index) {
 540                 pbqp_node *node = node_buckets[0][node_index];
 541                 assert(node);
 542
 543                 node->solution = vector_get_min_index(node->costs);
 544                 solution       = pbqp_add(solution,
 545                                 node->costs->entries[node->solution].data);
 546
 547 #if     KAPS_DUMP
 548                 if (file) {
 549                         fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
 550                         dump_node(file, node);
 551                 }
 552 #endif
 553         }
 554
 555 #if     KAPS_DUMP
 556         if (file) {
 557                 dump_section(file, 2, "Minimum");
 558 #if KAPS_USE_UNSIGNED
 559                 fprintf(file, "Minimum is equal to %u.", solution);
 560 #else
 561                 fprintf(file, "Minimum is equal to %lld.", solution);
 562 #endif
 563         }
 564 #endif
 565
 566         #if KAPS_TIMING
 567                 ir_timer_stop(t_det_solution);
 568                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_det_solution), (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
 569         #endif
 570
 571         return solution;
 572 }
 573
 574 static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 575 {
 576         pbqp_edge   *edge;
 577         pbqp_node   *other;
 578         pbqp_matrix *mat;
 579         vector      *vec;
 580         int          is_src;
 581
 582         assert(pbqp);
 583         assert(node);
 584
 585         edge = node->edges[0];
 586         mat = edge->costs;
 587         is_src = edge->src == node;
 588         vec = node->costs;
 589
 590         if (is_src) {
 591                 other = edge->tgt;
 592                 assert(other);
 593
 594                 /* Update pointer for brute force solver. */
 595                 other = pbqp->nodes[other->index];
 596
 597                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
 598         } else {
 599                 other = edge->src;
 600                 assert(other);
 601
 602                 /* Update pointer for brute force solver. */
 603                 other = pbqp->nodes[other->index];
 604
 605                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
 606         }
 607
 608 #if     KAPS_DUMP
 609         if (pbqp->dump_file) {
 610                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 611         }
 612 #endif
 613 }
 614
 615 static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
 616 {
 617         pbqp_edge   *src_edge   = node->edges[0];
 618         pbqp_edge   *tgt_edge   = node->edges[1];
 619         int          src_is_src = src_edge->src == node;
 620         int          tgt_is_src = tgt_edge->src == node;
 621         pbqp_matrix *src_mat;
 622         pbqp_matrix *tgt_mat;
 623         pbqp_node   *src_node;
 624         pbqp_node   *tgt_node;
 625         vector      *vec;
 626         vector      *node_vec;
 627         unsigned     col_index;
 628         unsigned     row_index;
 629
 630         assert(pbqp);
 631
 632         if (src_is_src) {
 633                 src_node = src_edge->tgt;
 634         } else {
 635                 src_node = src_edge->src;
 636         }
 637
 638         if (tgt_is_src) {
 639                 tgt_node = tgt_edge->tgt;
 640         } else {
 641                 tgt_node = tgt_edge->src;
 642         }
 643
 644         /* Swap nodes if necessary. */
 645         if (tgt_node->index < src_node->index) {
 646                 pbqp_node *tmp_node;
 647                 pbqp_edge *tmp_edge;
 648
 649                 tmp_node = src_node;
 650                 src_node = tgt_node;
 651                 tgt_node = tmp_node;
 652
 653                 tmp_edge = src_edge;
 654                 src_edge = tgt_edge;
 655                 tgt_edge = tmp_edge;
 656
 657                 src_is_src = src_edge->src == node;
 658                 tgt_is_src = tgt_edge->src == node;
 659         }
 660
 661         /* Update pointer for brute force solver. */
 662         src_node = pbqp->nodes[src_node->index];
 663         tgt_node = pbqp->nodes[tgt_node->index];
 664
 665         src_mat = src_edge->costs;
 666         tgt_mat = tgt_edge->costs;
 667
 668         node_vec = node->costs;
 669
 670         row_index = src_node->solution;
 671         col_index = tgt_node->solution;
 672
 673         vec = vector_copy(pbqp, node_vec);
 674
 675         if (src_is_src) {
 676                 vector_add_matrix_col(vec, src_mat, row_index);
 677         } else {
 678                 vector_add_matrix_row(vec, src_mat, row_index);
 679         }
 680
 681         if (tgt_is_src) {
 682                 vector_add_matrix_col(vec, tgt_mat, col_index);
 683         } else {
 684                 vector_add_matrix_row(vec, tgt_mat, col_index);
 685         }
 686
 687         node->solution = vector_get_min_index(vec);
 688
 689 #if     KAPS_DUMP
 690         if (pbqp->dump_file) {
 691                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 692         }
 693 #endif
 694
 695         obstack_free(&pbqp->obstack, vec);
 696 }
 697
 698 void back_propagate(pbqp *pbqp)
 699 {
 700         unsigned node_index;
 701         unsigned node_len   = node_bucket_get_length(reduced_bucket);
 702
 703         assert(pbqp);
 704
 705 #if     KAPS_DUMP
 706         if (pbqp->dump_file) {
 707                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 708         }
 709 #endif
 710
 711         for (node_index = node_len; node_index > 0; --node_index) {
 712                 pbqp_node *node = reduced_bucket[node_index - 1];
 713
 714                 switch (pbqp_node_get_degree(node)) {
 715                         case 1:
 716                                 back_propagate_RI(pbqp, node);
 717                                 break;
 718                         case 2:
 719                                 back_propagate_RII(pbqp, node);
 720                                 break;
 721                         default:
 722                                 panic("Only nodes with degree one or two should be in this bucket");
 723                                 break;
 724                 }
 725         }
 726 }
 727
 728 void apply_edge(pbqp *pbqp)
 729 {
 730         pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
 731
 732         simplify_edge(pbqp, edge);
 733 }
 734
 735 void apply_RI(pbqp *pbqp)
 736 {
 737         pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
 738         pbqp_edge   *edge       = node->edges[0];
 739         pbqp_matrix *mat        = edge->costs;
 740         int          is_src     = edge->src == node;
 741         pbqp_node   *other_node;
 742
 743         assert(pbqp_node_get_degree(node) == 1);
 744
 745         if (is_src) {
 746                 other_node = edge->tgt;
 747         } else {
 748                 other_node = edge->src;
 749         }
 750
 751 #if     KAPS_DUMP
 752         if (pbqp->dump_file) {
 753                 char     txt[100];
 754                 sprintf(txt, "RI-Reduction of Node n%d", node->index);
 755                 dump_section(pbqp->dump_file, 2, txt);
 756                 pbqp_dump_graph(pbqp);
 757                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 758                 dump_node(pbqp->dump_file, node);
 759                 dump_node(pbqp->dump_file, other_node);
 760                 dump_edge(pbqp->dump_file, edge);
 761         }
 762 #endif
 763
 764         if (is_src) {
 765                 pbqp_matrix_add_to_all_cols(mat, node->costs);
 766                 normalize_towards_target(pbqp, edge);
 767         } else {
 768                 pbqp_matrix_add_to_all_rows(mat, node->costs);
 769                 normalize_towards_source(pbqp, edge);
 770         }
 771         disconnect_edge(other_node, edge);
 772
 773 #if     KAPS_DUMP
 774         if (pbqp->dump_file) {
 775                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 776                 dump_node(pbqp->dump_file, other_node);
 777         }
 778 #endif
 779
 780         reorder_node(other_node);
 781
 782 #if KAPS_STATISTIC
 783         if (dump == 0) {
 784                 pbqp->num_r1++;
 785         }
 786 #endif
 787
 788         /* Add node to back propagation list. */
 789         node_bucket_insert(&reduced_bucket, node);
 790 }
 791
 792 void apply_RII(pbqp *pbqp)
 793 {
 794         pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
 795         pbqp_edge   *src_edge   = node->edges[0];
 796         pbqp_edge   *tgt_edge   = node->edges[1];
 797         int          src_is_src = src_edge->src == node;
 798         int          tgt_is_src = tgt_edge->src == node;
 799         pbqp_matrix *src_mat;
 800         pbqp_matrix *tgt_mat;
 801         pbqp_node   *src_node;
 802         pbqp_node   *tgt_node;
 803         pbqp_matrix *mat;
 804         vector      *vec;
 805         vector      *node_vec;
 806         vector      *src_vec;
 807         vector      *tgt_vec;
 808         unsigned     col_index;
 809         unsigned     col_len;
 810         unsigned     row_index;
 811         unsigned     row_len;
 812         unsigned     node_len;
 813
 814         assert(pbqp);
 815         assert(pbqp_node_get_degree(node) == 2);
 816
 817         if (src_is_src) {
 818                 src_node = src_edge->tgt;
 819         } else {
 820                 src_node = src_edge->src;
 821         }
 822
 823         if (tgt_is_src) {
 824                 tgt_node = tgt_edge->tgt;
 825         } else {
 826                 tgt_node = tgt_edge->src;
 827         }
 828
 829         /* Swap nodes if necessary. */
 830         if (tgt_node->index < src_node->index) {
 831                 pbqp_node *tmp_node;
 832                 pbqp_edge *tmp_edge;
 833
 834                 tmp_node = src_node;
 835                 src_node = tgt_node;
 836                 tgt_node = tmp_node;
 837
 838                 tmp_edge = src_edge;
 839                 src_edge = tgt_edge;
 840                 tgt_edge = tmp_edge;
 841
 842                 src_is_src = src_edge->src == node;
 843                 tgt_is_src = tgt_edge->src == node;
 844         }
 845
 846 #if     KAPS_DUMP
 847         if (pbqp->dump_file) {
 848                 char     txt[100];
 849                 sprintf(txt, "RII-Reduction of Node n%d", node->index);
 850                 dump_section(pbqp->dump_file, 2, txt);
 851                 pbqp_dump_graph(pbqp);
 852                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 853                 dump_node(pbqp->dump_file, src_node);
 854                 dump_edge(pbqp->dump_file, src_edge);
 855                 dump_node(pbqp->dump_file, node);
 856                 dump_edge(pbqp->dump_file, tgt_edge);
 857                 dump_node(pbqp->dump_file, tgt_node);
 858         }
 859 #endif
 860
 861         src_mat = src_edge->costs;
 862         tgt_mat = tgt_edge->costs;
 863
 864         src_vec  = src_node->costs;
 865         tgt_vec  = tgt_node->costs;
 866         node_vec = node->costs;
 867
 868         row_len  = src_vec->len;
 869         col_len  = tgt_vec->len;
 870         node_len = node_vec->len;
 871
 872         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
 873
 874         for (row_index = 0; row_index < row_len; ++row_index) {
 875                 for (col_index = 0; col_index < col_len; ++col_index) {
 876                         vec = vector_copy(pbqp, node_vec);
 877
 878                         if (src_is_src) {
 879                                 vector_add_matrix_col(vec, src_mat, row_index);
 880                         } else {
 881                                 vector_add_matrix_row(vec, src_mat, row_index);
 882                         }
 883
 884                         if (tgt_is_src) {
 885                                 vector_add_matrix_col(vec, tgt_mat, col_index);
 886                         } else {
 887                                 vector_add_matrix_row(vec, tgt_mat, col_index);
 888                         }
 889
 890                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
 891
 892                         obstack_free(&pbqp->obstack, vec);
 893                 }
 894         }
 895
 896         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
 897
 898         /* Disconnect node. */
 899         disconnect_edge(src_node, src_edge);
 900         disconnect_edge(tgt_node, tgt_edge);
 901
 902 #if KAPS_STATISTIC
 903         if (dump == 0) {
 904                 pbqp->num_r2++;
 905         }
 906 #endif
 907
 908         /* Add node to back propagation list. */
 909         node_bucket_insert(&reduced_bucket, node);
 910
 911         if (edge == NULL) {
 912                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
 913         } else {
 914                 // matrix
 915                 pbqp_matrix_add(edge->costs, mat);
 916
 917                 /* Free local matrix. */
 918                 obstack_free(&pbqp->obstack, mat);
 919
 920                 reorder_node(src_node);
 921                 reorder_node(tgt_node);
 922         }
 923
 924 #if     KAPS_DUMP
 925         if (pbqp->dump_file) {
 926                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 927                 dump_edge(pbqp->dump_file, edge);
 928         }
 929 #endif
 930
 931         /* Edge has changed so we simplify it. */
 932         simplify_edge(pbqp, edge);
 933 }
 934
 935 void select_alternative(pbqp_node *node, unsigned selected_index)
 936 {
 937         unsigned  edge_index;
 938         unsigned  node_index;
 939         unsigned  node_len;
 940         vector   *node_vec;
 941         unsigned  max_degree = pbqp_node_get_degree(node);
 942
 943         assert(node);
 944         node->solution = selected_index;
 945         node_vec = node->costs;
 946         node_len = node_vec->len;
 947         assert(selected_index < node_len);
 948
 949         /* Set all other costs to infinity. */
 950         for (node_index = 0; node_index < node_len; ++node_index) {
 951                 if (node_index != selected_index) {
 952                         node_vec->entries[node_index].data = INF_COSTS;
 953                 }
 954         }
 955
 956         /* Add all incident edges to edge bucket, since they are now independent. */
 957         for (edge_index = 0; edge_index < max_degree; ++edge_index) {
 958                 insert_into_edge_bucket(node->edges[edge_index]);
 959         }
 960 }
 961
 962 pbqp_node *get_node_with_max_degree(void)
 963 {
 964         pbqp_node  **bucket       = node_buckets[3];
 965         unsigned     bucket_len   = node_bucket_get_length(bucket);
 966         unsigned     bucket_index;
 967         unsigned     max_degree   = 0;
 968         pbqp_node   *result       = NULL;
 969
 970         for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
 971                 pbqp_node *candidate = bucket[bucket_index];
 972                 unsigned   degree    = pbqp_node_get_degree(candidate);
 973
 974                 if (degree > max_degree) {
 975                         result = candidate;
 976                         max_degree = degree;
 977                 }
 978         }
 979
 980         return result;
 981 }
 982
 983 unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node)
 984 {
 985         pbqp_edge   *edge;
 986         vector      *node_vec;
 987         vector      *vec;
 988         pbqp_matrix *mat;
 989         unsigned     edge_index;
 990         unsigned     max_degree   = 0;
 991         unsigned     node_index;
 992         unsigned     node_len;
 993         unsigned     min_index    = 0;
 994         num          min          = INF_COSTS;
 995         int          is_src;
 996
 997         assert(pbqp);
 998         assert(node);
 999         node_vec = node->costs;
1000         node_len = node_vec->len;
1001
1002         for (node_index = 0; node_index < node_len; ++node_index) {
1003                 num value = node_vec->entries[node_index].data;
1004
1005                 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1006                         edge   = node->edges[edge_index];
1007                         mat    = edge->costs;
1008                         is_src = edge->src == node;
1009
1010                         if (is_src) {
1011                                 vec = vector_copy(pbqp, edge->tgt->costs);
1012                                 vector_add_matrix_row(vec, mat, node_index);
1013                         } else {
1014                                 vec = vector_copy(pbqp, edge->src->costs);
1015                                 vector_add_matrix_col(vec, mat, node_index);
1016                         }
1017
1018                         value = pbqp_add(value, vector_get_min(vec));
1019
1020                         obstack_free(&pbqp->obstack, vec);
1021                 }
1022
1023                 if (value < min) {
1024                         min = value;
1025                         min_index = node_index;
1026                 }
1027         }
1028
1029         return min_index;
1030 }
1031
1032 int node_is_reduced(pbqp_node *node)
1033 {
1034         if (!reduced_bucket) return 0;
1035
1036         if (pbqp_node_get_degree(node) == 0) return 1;
1037
1038         return node_bucket_contains(reduced_bucket, node);
1039 }