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