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