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                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
 595         } else {
 596                 other = edge->src;
 597                 assert(other);
 598
 599                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
 600         }
 601
 602 #if     KAPS_DUMP
 603         if (pbqp->dump_file) {
 604                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 605         }
 606 #endif
 607 }
 608
 609 static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
 610 {
 611         pbqp_edge   *src_edge   = node->edges[0];
 612         pbqp_edge   *tgt_edge   = node->edges[1];
 613         int          src_is_src = src_edge->src == node;
 614         int          tgt_is_src = tgt_edge->src == node;
 615         pbqp_matrix *src_mat;
 616         pbqp_matrix *tgt_mat;
 617         pbqp_node   *src_node;
 618         pbqp_node   *tgt_node;
 619         vector      *vec;
 620         vector      *node_vec;
 621         unsigned     col_index;
 622         unsigned     row_index;
 623
 624         assert(pbqp);
 625
 626         if (src_is_src) {
 627                 src_node = src_edge->tgt;
 628         } else {
 629                 src_node = src_edge->src;
 630         }
 631
 632         if (tgt_is_src) {
 633                 tgt_node = tgt_edge->tgt;
 634         } else {
 635                 tgt_node = tgt_edge->src;
 636         }
 637
 638         /* Swap nodes if necessary. */
 639         if (tgt_node->index < src_node->index) {
 640                 pbqp_node *tmp_node;
 641                 pbqp_edge *tmp_edge;
 642
 643                 tmp_node = src_node;
 644                 src_node = tgt_node;
 645                 tgt_node = tmp_node;
 646
 647                 tmp_edge = src_edge;
 648                 src_edge = tgt_edge;
 649                 tgt_edge = tmp_edge;
 650
 651                 src_is_src = src_edge->src == node;
 652                 tgt_is_src = tgt_edge->src == node;
 653         }
 654
 655         src_mat = src_edge->costs;
 656         tgt_mat = tgt_edge->costs;
 657
 658         node_vec = node->costs;
 659
 660         row_index = src_node->solution;
 661         col_index = tgt_node->solution;
 662
 663         vec = vector_copy(pbqp, node_vec);
 664
 665         if (src_is_src) {
 666                 vector_add_matrix_col(vec, src_mat, row_index);
 667         } else {
 668                 vector_add_matrix_row(vec, src_mat, row_index);
 669         }
 670
 671         if (tgt_is_src) {
 672                 vector_add_matrix_col(vec, tgt_mat, col_index);
 673         } else {
 674                 vector_add_matrix_row(vec, tgt_mat, col_index);
 675         }
 676
 677         node->solution = vector_get_min_index(vec);
 678
 679 #if     KAPS_DUMP
 680         if (pbqp->dump_file) {
 681                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 682         }
 683 #endif
 684
 685         obstack_free(&pbqp->obstack, vec);
 686 }
 687
 688 void back_propagate(pbqp *pbqp)
 689 {
 690         unsigned node_index;
 691         unsigned node_len   = node_bucket_get_length(reduced_bucket);
 692
 693         assert(pbqp);
 694
 695 #if     KAPS_DUMP
 696         if (pbqp->dump_file) {
 697                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 698         }
 699 #endif
 700
 701         for (node_index = node_len; node_index > 0; --node_index) {
 702                 pbqp_node *node = reduced_bucket[node_index - 1];
 703
 704                 switch (pbqp_node_get_degree(node)) {
 705                         case 1:
 706                                 back_propagate_RI(pbqp, node);
 707                                 break;
 708                         case 2:
 709                                 back_propagate_RII(pbqp, node);
 710                                 break;
 711                         default:
 712                                 panic("Only nodes with degree one or two should be in this bucket");
 713                                 break;
 714                 }
 715         }
 716 }
 717
 718 void apply_edge(pbqp *pbqp)
 719 {
 720         pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
 721
 722         simplify_edge(pbqp, edge);
 723 }
 724
 725 void apply_RI(pbqp *pbqp)
 726 {
 727         pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
 728         pbqp_edge   *edge       = node->edges[0];
 729         pbqp_matrix *mat        = edge->costs;
 730         int          is_src     = edge->src == node;
 731         pbqp_node   *other_node;
 732
 733         assert(pbqp_node_get_degree(node) == 1);
 734
 735         if (is_src) {
 736                 other_node = edge->tgt;
 737         } else {
 738                 other_node = edge->src;
 739         }
 740
 741 #if     KAPS_DUMP
 742         if (pbqp->dump_file) {
 743                 char     txt[100];
 744                 sprintf(txt, "RI-Reduction of Node n%d", node->index);
 745                 dump_section(pbqp->dump_file, 2, txt);
 746                 pbqp_dump_graph(pbqp);
 747                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 748                 dump_node(pbqp->dump_file, node);
 749                 dump_node(pbqp->dump_file, other_node);
 750                 dump_edge(pbqp->dump_file, edge);
 751         }
 752 #endif
 753
 754         if (is_src) {
 755                 pbqp_matrix_add_to_all_cols(mat, node->costs);
 756                 normalize_towards_target(pbqp, edge);
 757         } else {
 758                 pbqp_matrix_add_to_all_rows(mat, node->costs);
 759                 normalize_towards_source(pbqp, edge);
 760         }
 761         disconnect_edge(other_node, edge);
 762
 763 #if     KAPS_DUMP
 764         if (pbqp->dump_file) {
 765                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 766                 dump_node(pbqp->dump_file, other_node);
 767         }
 768 #endif
 769
 770         reorder_node(other_node);
 771
 772 #if KAPS_STATISTIC
 773         if (dump == 0) {
 774                 pbqp->num_r1++;
 775         }
 776 #endif
 777
 778         /* Add node to back propagation list. */
 779         node_bucket_insert(&reduced_bucket, node);
 780 }
 781
 782 void apply_RII(pbqp *pbqp)
 783 {
 784         pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
 785         pbqp_edge   *src_edge   = node->edges[0];
 786         pbqp_edge   *tgt_edge   = node->edges[1];
 787         int          src_is_src = src_edge->src == node;
 788         int          tgt_is_src = tgt_edge->src == node;
 789         pbqp_matrix *src_mat;
 790         pbqp_matrix *tgt_mat;
 791         pbqp_node   *src_node;
 792         pbqp_node   *tgt_node;
 793         pbqp_matrix *mat;
 794         vector      *vec;
 795         vector      *node_vec;
 796         vector      *src_vec;
 797         vector      *tgt_vec;
 798         unsigned     col_index;
 799         unsigned     col_len;
 800         unsigned     row_index;
 801         unsigned     row_len;
 802         unsigned     node_len;
 803
 804         assert(pbqp);
 805         assert(pbqp_node_get_degree(node) == 2);
 806
 807         if (src_is_src) {
 808                 src_node = src_edge->tgt;
 809         } else {
 810                 src_node = src_edge->src;
 811         }
 812
 813         if (tgt_is_src) {
 814                 tgt_node = tgt_edge->tgt;
 815         } else {
 816                 tgt_node = tgt_edge->src;
 817         }
 818
 819         /* Swap nodes if necessary. */
 820         if (tgt_node->index < src_node->index) {
 821                 pbqp_node *tmp_node;
 822                 pbqp_edge *tmp_edge;
 823
 824                 tmp_node = src_node;
 825                 src_node = tgt_node;
 826                 tgt_node = tmp_node;
 827
 828                 tmp_edge = src_edge;
 829                 src_edge = tgt_edge;
 830                 tgt_edge = tmp_edge;
 831
 832                 src_is_src = src_edge->src == node;
 833                 tgt_is_src = tgt_edge->src == node;
 834         }
 835
 836 #if     KAPS_DUMP
 837         if (pbqp->dump_file) {
 838                 char     txt[100];
 839                 sprintf(txt, "RII-Reduction of Node n%d", node->index);
 840                 dump_section(pbqp->dump_file, 2, txt);
 841                 pbqp_dump_graph(pbqp);
 842                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 843                 dump_node(pbqp->dump_file, src_node);
 844                 dump_edge(pbqp->dump_file, src_edge);
 845                 dump_node(pbqp->dump_file, node);
 846                 dump_edge(pbqp->dump_file, tgt_edge);
 847                 dump_node(pbqp->dump_file, tgt_node);
 848         }
 849 #endif
 850
 851         src_mat = src_edge->costs;
 852         tgt_mat = tgt_edge->costs;
 853
 854         src_vec  = src_node->costs;
 855         tgt_vec  = tgt_node->costs;
 856         node_vec = node->costs;
 857
 858         row_len  = src_vec->len;
 859         col_len  = tgt_vec->len;
 860         node_len = node_vec->len;
 861
 862         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
 863
 864         for (row_index = 0; row_index < row_len; ++row_index) {
 865                 for (col_index = 0; col_index < col_len; ++col_index) {
 866                         vec = vector_copy(pbqp, node_vec);
 867
 868                         if (src_is_src) {
 869                                 vector_add_matrix_col(vec, src_mat, row_index);
 870                         } else {
 871                                 vector_add_matrix_row(vec, src_mat, row_index);
 872                         }
 873
 874                         if (tgt_is_src) {
 875                                 vector_add_matrix_col(vec, tgt_mat, col_index);
 876                         } else {
 877                                 vector_add_matrix_row(vec, tgt_mat, col_index);
 878                         }
 879
 880                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
 881
 882                         obstack_free(&pbqp->obstack, vec);
 883                 }
 884         }
 885
 886         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
 887
 888         /* Disconnect node. */
 889         disconnect_edge(src_node, src_edge);
 890         disconnect_edge(tgt_node, tgt_edge);
 891
 892 #if KAPS_STATISTIC
 893         if (dump == 0) {
 894                 pbqp->num_r2++;
 895         }
 896 #endif
 897
 898         /* Add node to back propagation list. */
 899         node_bucket_insert(&reduced_bucket, node);
 900
 901         if (edge == NULL) {
 902                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
 903         } else {
 904                 // matrix
 905                 pbqp_matrix_add(edge->costs, mat);
 906
 907                 /* Free local matrix. */
 908                 obstack_free(&pbqp->obstack, mat);
 909
 910                 reorder_node(src_node);
 911                 reorder_node(tgt_node);
 912         }
 913
 914 #if     KAPS_DUMP
 915         if (pbqp->dump_file) {
 916                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 917                 dump_edge(pbqp->dump_file, edge);
 918         }
 919 #endif
 920
 921         /* Edge has changed so we simplify it. */
 922         simplify_edge(pbqp, edge);
 923 }
 924
 925 void select_alternative(pbqp_node *node, unsigned selected_index)
 926 {
 927         unsigned  edge_index;
 928         unsigned  node_index;
 929         unsigned  node_len;
 930         vector   *node_vec;
 931         unsigned  max_degree = pbqp_node_get_degree(node);
 932
 933         assert(node);
 934         node->solution = selected_index;
 935         node_vec = node->costs;
 936         node_len = node_vec->len;
 937         assert(selected_index < node_len);
 938
 939         /* Set all other costs to infinity. */
 940         for (node_index = 0; node_index < node_len; ++node_index) {
 941                 if (node_index != selected_index) {
 942                         node_vec->entries[node_index].data = INF_COSTS;
 943                 }
 944         }
 945
 946         /* Add all incident edges to edge bucket, since they are now independent. */
 947         for (edge_index = 0; edge_index < max_degree; ++edge_index) {
 948                 insert_into_edge_bucket(node->edges[edge_index]);
 949         }
 950 }
 951
 952 pbqp_node *get_node_with_max_degree(void)
 953 {
 954         pbqp_node  **bucket       = node_buckets[3];
 955         unsigned     bucket_len   = node_bucket_get_length(bucket);
 956         unsigned     bucket_index;
 957         unsigned     max_degree   = 0;
 958         pbqp_node   *result       = NULL;
 959
 960         for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
 961                 pbqp_node *candidate = bucket[bucket_index];
 962                 unsigned   degree    = pbqp_node_get_degree(candidate);
 963
 964                 if (degree > max_degree) {
 965                         result = candidate;
 966                         max_degree = degree;
 967                 }
 968         }
 969
 970         return result;
 971 }
 972
 973 unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node)
 974 {
 975         pbqp_edge   *edge;
 976         vector      *node_vec;
 977         vector      *vec;
 978         pbqp_matrix *mat;
 979         unsigned     edge_index;
 980         unsigned     max_degree   = 0;
 981         unsigned     node_index;
 982         unsigned     node_len;
 983         unsigned     min_index    = 0;
 984         num          min          = INF_COSTS;
 985         int          is_src;
 986
 987         assert(pbqp);
 988         assert(node);
 989         node_vec = node->costs;
 990         node_len = node_vec->len;
 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 }