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 1
 273 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 #if 0
 450         else {
 451                 check_melting_possibility(pbqp, edge);
 452         }
 453 #endif
 454 }
 455
 456 void initial_simplify_edges(pbqp *pbqp)
 457 {
 458         unsigned node_index;
 459         unsigned node_len;
 460
 461         assert(pbqp);
 462
 463         #if KAPS_TIMING
 464                 ir_timer_t *t_int_simpl = ir_timer_register("be_pbqp_init_simp", "PBQP Initial simplify edges");
 465                 ir_timer_reset_and_start(t_int_simpl);
 466         #endif
 467
 468 #if     KAPS_DUMP
 469         if (pbqp->dump_file) {
 470                 pbqp_dump_input(pbqp);
 471                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 472         }
 473 #endif
 474
 475         node_len = pbqp->num_nodes;
 476
 477         init_buckets();
 478
 479         /* First simplify all edges. */
 480         for (node_index = 0; node_index < node_len; ++node_index) {
 481                 unsigned    edge_index;
 482                 pbqp_node  *node = get_node(pbqp, node_index);
 483                 pbqp_edge **edges;
 484                 unsigned    edge_len;
 485
 486                 if (!node) continue;
 487
 488                 edges = node->edges;
 489                 edge_len = pbqp_node_get_degree(node);
 490
 491                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 492                         pbqp_edge *edge = edges[edge_index];
 493
 494                         /* Simplify only once per edge. */
 495                         if (node != edge->src) continue;
 496
 497                         simplify_edge(pbqp, edge);
 498                 }
 499         }
 500
 501         #if KAPS_TIMING
 502                 ir_timer_stop(t_int_simpl);
 503                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_int_simpl), (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
 504         #endif
 505 }
 506
 507 num determine_solution(pbqp *pbqp)
 508 {
 509         unsigned node_index;
 510         unsigned node_len;
 511         num      solution   = 0;
 512
 513         #if KAPS_TIMING
 514                 ir_timer_t *t_det_solution = ir_timer_register("be_det_solution", "PBQP Determine Solution");
 515                 ir_timer_reset_and_start(t_det_solution);
 516         #endif
 517
 518 #if     KAPS_DUMP
 519         FILE     *file;
 520 #endif
 521
 522         assert(pbqp);
 523
 524 #if     KAPS_DUMP
 525         file = pbqp->dump_file;
 526
 527         if (file) {
 528                 dump_section(file, 1, "4. Determine Solution/Minimum");
 529                 dump_section(file, 2, "4.1. Trivial Solution");
 530         }
 531 #endif
 532
 533         /* Solve trivial nodes and calculate solution. */
 534         node_len = node_bucket_get_length(node_buckets[0]);
 535
 536 #if KAPS_STATISTIC
 537         if (dump == 0) {
 538                 pbqp->num_r0 = node_len;
 539         }
 540 #endif
 541
 542         for (node_index = 0; node_index < node_len; ++node_index) {
 543                 pbqp_node *node = node_buckets[0][node_index];
 544                 assert(node);
 545
 546                 node->solution = vector_get_min_index(node->costs);
 547                 solution       = pbqp_add(solution,
 548                                 node->costs->entries[node->solution].data);
 549
 550 #if     KAPS_DUMP
 551                 if (file) {
 552                         fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
 553                         dump_node(file, node);
 554                 }
 555 #endif
 556         }
 557
 558 #if     KAPS_DUMP
 559         if (file) {
 560                 dump_section(file, 2, "Minimum");
 561 #if KAPS_USE_UNSIGNED
 562                 fprintf(file, "Minimum is equal to %u.", solution);
 563 #else
 564                 fprintf(file, "Minimum is equal to %lld.", solution);
 565 #endif
 566         }
 567 #endif
 568
 569         #if KAPS_TIMING
 570                 ir_timer_stop(t_det_solution);
 571                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_det_solution), (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
 572         #endif
 573
 574         return solution;
 575 }
 576
 577 static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 578 {
 579         pbqp_edge   *edge;
 580         pbqp_node   *other;
 581         pbqp_matrix *mat;
 582         vector      *vec;
 583         int          is_src;
 584
 585         assert(pbqp);
 586         assert(node);
 587
 588         edge = node->edges[0];
 589         mat = edge->costs;
 590         is_src = edge->src == node;
 591         vec = node->costs;
 592
 593         if (is_src) {
 594                 other = edge->tgt;
 595                 assert(other);
 596
 597                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
 598         } else {
 599                 other = edge->src;
 600                 assert(other);
 601
 602                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
 603         }
 604
 605 #if     KAPS_DUMP
 606         if (pbqp->dump_file) {
 607                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 608         }
 609 #endif
 610 }
 611
 612 static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
 613 {
 614         pbqp_edge   *src_edge   = node->edges[0];
 615         pbqp_edge   *tgt_edge   = node->edges[1];
 616         int          src_is_src = src_edge->src == node;
 617         int          tgt_is_src = tgt_edge->src == node;
 618         pbqp_matrix *src_mat;
 619         pbqp_matrix *tgt_mat;
 620         pbqp_node   *src_node;
 621         pbqp_node   *tgt_node;
 622         vector      *vec;
 623         vector      *node_vec;
 624         unsigned     col_index;
 625         unsigned     row_index;
 626
 627         assert(pbqp);
 628
 629         if (src_is_src) {
 630                 src_node = src_edge->tgt;
 631         } else {
 632                 src_node = src_edge->src;
 633         }
 634
 635         if (tgt_is_src) {
 636                 tgt_node = tgt_edge->tgt;
 637         } else {
 638                 tgt_node = tgt_edge->src;
 639         }
 640
 641         /* Swap nodes if necessary. */
 642         if (tgt_node->index < src_node->index) {
 643                 pbqp_node *tmp_node;
 644                 pbqp_edge *tmp_edge;
 645
 646                 tmp_node = src_node;
 647                 src_node = tgt_node;
 648                 tgt_node = tmp_node;
 649
 650                 tmp_edge = src_edge;
 651                 src_edge = tgt_edge;
 652                 tgt_edge = tmp_edge;
 653
 654                 src_is_src = src_edge->src == node;
 655                 tgt_is_src = tgt_edge->src == node;
 656         }
 657
 658         src_mat = src_edge->costs;
 659         tgt_mat = tgt_edge->costs;
 660
 661         node_vec = node->costs;
 662
 663         row_index = src_node->solution;
 664         col_index = tgt_node->solution;
 665
 666         vec = vector_copy(pbqp, node_vec);
 667
 668         if (src_is_src) {
 669                 vector_add_matrix_col(vec, src_mat, row_index);
 670         } else {
 671                 vector_add_matrix_row(vec, src_mat, row_index);
 672         }
 673
 674         if (tgt_is_src) {
 675                 vector_add_matrix_col(vec, tgt_mat, col_index);
 676         } else {
 677                 vector_add_matrix_row(vec, tgt_mat, col_index);
 678         }
 679
 680         node->solution = vector_get_min_index(vec);
 681
 682 #if     KAPS_DUMP
 683         if (pbqp->dump_file) {
 684                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 685         }
 686 #endif
 687
 688         obstack_free(&pbqp->obstack, vec);
 689 }
 690
 691 void back_propagate(pbqp *pbqp)
 692 {
 693         unsigned node_index;
 694         unsigned node_len   = node_bucket_get_length(reduced_bucket);
 695
 696         assert(pbqp);
 697
 698 #if     KAPS_DUMP
 699         if (pbqp->dump_file) {
 700                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 701         }
 702 #endif
 703
 704         for (node_index = node_len; node_index > 0; --node_index) {
 705                 pbqp_node *node = reduced_bucket[node_index - 1];
 706
 707                 switch (pbqp_node_get_degree(node)) {
 708                         case 1:
 709                                 back_propagate_RI(pbqp, node);
 710                                 break;
 711                         case 2:
 712                                 back_propagate_RII(pbqp, node);
 713                                 break;
 714                         default:
 715                                 panic("Only nodes with degree one or two should be in this bucket");
 716                                 break;
 717                 }
 718         }
 719 }
 720
 721 void apply_edge(pbqp *pbqp)
 722 {
 723         pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
 724
 725         simplify_edge(pbqp, edge);
 726 }
 727
 728 void apply_RI(pbqp *pbqp)
 729 {
 730         pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
 731         pbqp_edge   *edge       = node->edges[0];
 732         pbqp_matrix *mat        = edge->costs;
 733         int          is_src     = edge->src == node;
 734         pbqp_node   *other_node;
 735
 736         (void ) pbqp;
 737         assert(pbqp_node_get_degree(node) == 1);
 738
 739         if (is_src) {
 740                 other_node = edge->tgt;
 741         } else {
 742                 other_node = edge->src;
 743         }
 744
 745 #if     KAPS_DUMP
 746         if (pbqp->dump_file) {
 747                 char     txt[100];
 748                 sprintf(txt, "RI-Reduction of Node n%d", node->index);
 749                 dump_section(pbqp->dump_file, 2, txt);
 750                 pbqp_dump_graph(pbqp);
 751                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 752                 dump_node(pbqp->dump_file, node);
 753                 dump_node(pbqp->dump_file, other_node);
 754                 dump_edge(pbqp->dump_file, edge);
 755         }
 756 #endif
 757
 758         if (is_src) {
 759                 pbqp_matrix_add_to_all_cols(mat, node->costs);
 760                 normalize_towards_target(edge);
 761         } else {
 762                 pbqp_matrix_add_to_all_rows(mat, node->costs);
 763                 normalize_towards_source(edge);
 764         }
 765         disconnect_edge(other_node, edge);
 766
 767 #if     KAPS_DUMP
 768         if (pbqp->dump_file) {
 769                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 770                 dump_node(pbqp->dump_file, other_node);
 771         }
 772 #endif
 773
 774         reorder_node(other_node);
 775
 776 #if KAPS_STATISTIC
 777         if (dump == 0) {
 778                 pbqp->num_r1++;
 779         }
 780 #endif
 781
 782         /* Add node to back propagation list. */
 783         node_bucket_insert(&reduced_bucket, node);
 784 }
 785
 786 void apply_RII(pbqp *pbqp)
 787 {
 788         pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
 789         pbqp_edge   *src_edge   = node->edges[0];
 790         pbqp_edge   *tgt_edge   = node->edges[1];
 791         int          src_is_src = src_edge->src == node;
 792         int          tgt_is_src = tgt_edge->src == node;
 793         pbqp_matrix *src_mat;
 794         pbqp_matrix *tgt_mat;
 795         pbqp_node   *src_node;
 796         pbqp_node   *tgt_node;
 797         pbqp_matrix *mat;
 798         vector      *vec;
 799         vector      *node_vec;
 800         vector      *src_vec;
 801         vector      *tgt_vec;
 802         unsigned     col_index;
 803         unsigned     col_len;
 804         unsigned     row_index;
 805         unsigned     row_len;
 806         unsigned     node_len;
 807
 808         assert(pbqp);
 809         assert(pbqp_node_get_degree(node) == 2);
 810
 811         if (src_is_src) {
 812                 src_node = src_edge->tgt;
 813         } else {
 814                 src_node = src_edge->src;
 815         }
 816
 817         if (tgt_is_src) {
 818                 tgt_node = tgt_edge->tgt;
 819         } else {
 820                 tgt_node = tgt_edge->src;
 821         }
 822
 823         /* Swap nodes if necessary. */
 824         if (tgt_node->index < src_node->index) {
 825                 pbqp_node *tmp_node;
 826                 pbqp_edge *tmp_edge;
 827
 828                 tmp_node = src_node;
 829                 src_node = tgt_node;
 830                 tgt_node = tmp_node;
 831
 832                 tmp_edge = src_edge;
 833                 src_edge = tgt_edge;
 834                 tgt_edge = tmp_edge;
 835
 836                 src_is_src = src_edge->src == node;
 837                 tgt_is_src = tgt_edge->src == node;
 838         }
 839
 840 #if     KAPS_DUMP
 841         if (pbqp->dump_file) {
 842                 char     txt[100];
 843                 sprintf(txt, "RII-Reduction of Node n%d", node->index);
 844                 dump_section(pbqp->dump_file, 2, txt);
 845                 pbqp_dump_graph(pbqp);
 846                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 847                 dump_node(pbqp->dump_file, src_node);
 848                 dump_edge(pbqp->dump_file, src_edge);
 849                 dump_node(pbqp->dump_file, node);
 850                 dump_edge(pbqp->dump_file, tgt_edge);
 851                 dump_node(pbqp->dump_file, tgt_node);
 852         }
 853 #endif
 854
 855         src_mat = src_edge->costs;
 856         tgt_mat = tgt_edge->costs;
 857
 858         src_vec  = src_node->costs;
 859         tgt_vec  = tgt_node->costs;
 860         node_vec = node->costs;
 861
 862         row_len  = src_vec->len;
 863         col_len  = tgt_vec->len;
 864         node_len = node_vec->len;
 865
 866         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
 867
 868         for (row_index = 0; row_index < row_len; ++row_index) {
 869                 for (col_index = 0; col_index < col_len; ++col_index) {
 870                         vec = vector_copy(pbqp, node_vec);
 871
 872                         if (src_is_src) {
 873                                 vector_add_matrix_col(vec, src_mat, row_index);
 874                         } else {
 875                                 vector_add_matrix_row(vec, src_mat, row_index);
 876                         }
 877
 878                         if (tgt_is_src) {
 879                                 vector_add_matrix_col(vec, tgt_mat, col_index);
 880                         } else {
 881                                 vector_add_matrix_row(vec, tgt_mat, col_index);
 882                         }
 883
 884                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
 885
 886                         obstack_free(&pbqp->obstack, vec);
 887                 }
 888         }
 889
 890         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
 891
 892         /* Disconnect node. */
 893         disconnect_edge(src_node, src_edge);
 894         disconnect_edge(tgt_node, tgt_edge);
 895
 896 #if KAPS_STATISTIC
 897         if (dump == 0) {
 898                 pbqp->num_r2++;
 899         }
 900 #endif
 901
 902         /* Add node to back propagation list. */
 903         node_bucket_insert(&reduced_bucket, node);
 904
 905         if (edge == NULL) {
 906                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
 907         } else {
 908                 // matrix
 909                 pbqp_matrix_add(edge->costs, mat);
 910
 911                 /* Free local matrix. */
 912                 obstack_free(&pbqp->obstack, mat);
 913
 914                 reorder_node(src_node);
 915                 reorder_node(tgt_node);
 916         }
 917
 918 #if     KAPS_DUMP
 919         if (pbqp->dump_file) {
 920                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 921                 dump_edge(pbqp->dump_file, edge);
 922         }
 923 #endif
 924
 925         /* Edge has changed so we simplify it. */
 926         simplify_edge(pbqp, edge);
 927 }
 928
 929 void select_alternative(pbqp_node *node, unsigned selected_index)
 930 {
 931         unsigned  edge_index;
 932         unsigned  node_index;
 933         unsigned  node_len;
 934         vector   *node_vec;
 935         unsigned  max_degree = pbqp_node_get_degree(node);
 936
 937         assert(node);
 938         node->solution = selected_index;
 939         node_vec = node->costs;
 940         node_len = node_vec->len;
 941         assert(selected_index < node_len);
 942
 943         /* Set all other costs to infinity. */
 944         for (node_index = 0; node_index < node_len; ++node_index) {
 945                 if (node_index != selected_index) {
 946                         node_vec->entries[node_index].data = INF_COSTS;
 947                 }
 948         }
 949
 950         /* Add all incident edges to edge bucket, since they are now independent. */
 951         for (edge_index = 0; edge_index < max_degree; ++edge_index) {
 952                 insert_into_edge_bucket(node->edges[edge_index]);
 953         }
 954 }
 955
 956 pbqp_node *get_node_with_max_degree(void)
 957 {
 958         pbqp_node  **bucket       = node_buckets[3];
 959         unsigned     bucket_len   = node_bucket_get_length(bucket);
 960         unsigned     bucket_index;
 961         unsigned     max_degree   = 0;
 962         pbqp_node   *result       = NULL;
 963
 964         for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
 965                 pbqp_node *candidate = bucket[bucket_index];
 966                 unsigned   degree    = pbqp_node_get_degree(candidate);
 967
 968                 if (degree > max_degree) {
 969                         result = candidate;
 970                         max_degree = degree;
 971                 }
 972         }
 973
 974         return result;
 975 }
 976
 977 unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node)
 978 {
 979         pbqp_edge   *edge;
 980         vector      *node_vec;
 981         vector      *vec;
 982         pbqp_matrix *mat;
 983         unsigned     edge_index;
 984         unsigned     max_degree;
 985         unsigned     node_index;
 986         unsigned     node_len;
 987         unsigned     min_index    = 0;
 988         num          min          = INF_COSTS;
 989         int          is_src;
 990
 991         assert(pbqp);
 992         assert(node);
 993         node_vec   = node->costs;
 994         node_len   = node_vec->len;
 995         max_degree = pbqp_node_get_degree(node);
 996
 997         for (node_index = 0; node_index < node_len; ++node_index) {
 998                 num value = node_vec->entries[node_index].data;
 999
1000                 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1001                         edge   = node->edges[edge_index];
1002                         mat    = edge->costs;
1003                         is_src = edge->src == node;
1004
1005                         if (is_src) {
1006                                 vec = vector_copy(pbqp, edge->tgt->costs);
1007                                 vector_add_matrix_row(vec, mat, node_index);
1008                         } else {
1009                                 vec = vector_copy(pbqp, edge->src->costs);
1010                                 vector_add_matrix_col(vec, mat, node_index);
1011                         }
1012
1013                         value = pbqp_add(value, vector_get_min(vec));
1014
1015                         obstack_free(&pbqp->obstack, vec);
1016                 }
1017
1018                 if (value < min) {
1019                         min = value;
1020                         min_index = node_index;
1021                 }
1022         }
1023
1024         return min_index;
1025 }
1026
1027 int node_is_reduced(pbqp_node *node)
1028 {
1029         if (!reduced_bucket) return 0;
1030
1031         if (pbqp_node_get_degree(node) == 0) return 1;
1032
1033         return node_bucket_contains(reduced_bucket, node);
1034 }