nsz Git - libfirm/blob - heuristical.c

   1 #include "adt/array.h"
   2 #include "assert.h"
   3 #include "error.h"
   4
   5 #include "bucket.h"
   6 #include "heuristical.h"
   7 #if     KAPS_DUMP
   8 #include "html_dumper.h"
   9 #endif
  10 #include "kaps.h"
  11 #include "matrix.h"
  12 #include "pbqp_edge.h"
  13 #include "pbqp_edge_t.h"
  14 #include "pbqp_node.h"
  15 #include "pbqp_node_t.h"
  16 #include "vector.h"
  17
  18 #include "plist.h"
  19
  20 static pbqp_edge **edge_bucket;
  21 static pbqp_node **node_buckets[4];
  22 static pbqp_node **reduced_bucket = NULL;
  23 static int         buckets_filled = 0;
  24
  25 #if KAPS_STATISTIC
  26 static int dump = 0;
  27 #endif
  28
  29 /* Forward declarations. */
  30 static void apply_Brute_Force(pbqp *pbqp);
  31
  32 static void insert_into_edge_bucket(pbqp_edge *edge)
  33 {
  34         if (edge_bucket_contains(edge_bucket, edge)) {
  35                 /* Edge is already inserted. */
  36                 return;
  37         }
  38
  39         edge_bucket_insert(&edge_bucket, edge);
  40 }
  41
  42 static void init_buckets(void)
  43 {
  44         int i;
  45
  46         edge_bucket_init(&edge_bucket);
  47         node_bucket_init(&reduced_bucket);
  48
  49         for (i = 0; i < 4; ++i) {
  50                 node_bucket_init(&node_buckets[i]);
  51         }
  52 }
  53
  54 static void free_buckets(void)
  55 {
  56         int i;
  57
  58         for (i = 0; i < 4; ++i) {
  59                 node_bucket_free(&node_buckets[i]);
  60         }
  61
  62         edge_bucket_free(&edge_bucket);
  63         node_bucket_free(&reduced_bucket);
  64
  65         buckets_filled = 0;
  66 }
  67
  68 static void fill_node_buckets(pbqp *pbqp)
  69 {
  70         unsigned node_index;
  71         unsigned node_len;
  72
  73         assert(pbqp);
  74         node_len = pbqp->num_nodes;
  75
  76         for (node_index = 0; node_index < node_len; ++node_index) {
  77                 unsigned   degree;
  78                 pbqp_node *node = get_node(pbqp, node_index);
  79
  80                 if (!node) continue;
  81
  82                 degree = pbqp_node_get_degree(node);
  83
  84                 /* We have only one bucket for nodes with arity >= 3. */
  85                 if (degree > 3) {
  86                         degree = 3;
  87                 }
  88
  89                 node_bucket_insert(&node_buckets[degree], node);
  90         }
  91
  92         buckets_filled = 1;
  93 }
  94
  95 static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge)
  96 {
  97         pbqp_matrix    *mat;
  98         pbqp_node      *src_node;
  99         pbqp_node      *tgt_node;
 100         vector         *src_vec;
 101         vector         *tgt_vec;
 102         int             src_len;
 103         int             tgt_len;
 104         int             src_index;
 105
 106         assert(pbqp);
 107         assert(edge);
 108
 109         src_node = edge->src;
 110         tgt_node = edge->tgt;
 111         assert(src_node);
 112         assert(tgt_node);
 113
 114         src_vec = src_node->costs;
 115         tgt_vec = tgt_node->costs;
 116         assert(src_vec);
 117         assert(tgt_vec);
 118
 119         src_len = src_vec->len;
 120         tgt_len = tgt_vec->len;
 121         assert(src_len > 0);
 122         assert(tgt_len > 0);
 123
 124         mat = edge->costs;
 125         assert(mat);
 126
 127         /* Normalize towards source node. */
 128         for (src_index = 0; src_index < src_len; ++src_index) {
 129                 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
 130
 131                 if (min != 0) {
 132                         if (src_vec->entries[src_index].data == INF_COSTS) {
 133                                 pbqp_matrix_set_row_value(mat, src_index, 0);
 134                         } else {
 135                                 pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
 136                         }
 137                         src_vec->entries[src_index].data = pbqp_add(
 138                                         src_vec->entries[src_index].data, min);
 139
 140                         if (min == INF_COSTS) {
 141                                 unsigned edge_index;
 142                                 unsigned edge_len = pbqp_node_get_degree(src_node);
 143
 144                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 145                                         pbqp_edge *edge_candidate = src_node->edges[edge_index];
 146                                         if (edge_candidate != edge) {
 147                                                 insert_into_edge_bucket(edge_candidate);
 148                                         }
 149                                 }
 150                         }
 151                 }
 152         }
 153 }
 154
 155 static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge)
 156 {
 157         pbqp_matrix    *mat;
 158         pbqp_node      *src_node;
 159         pbqp_node      *tgt_node;
 160         vector         *src_vec;
 161         vector         *tgt_vec;
 162         int             src_len;
 163         int             tgt_len;
 164         int             tgt_index;
 165
 166         assert(pbqp);
 167         assert(edge);
 168
 169         src_node = edge->src;
 170         tgt_node = edge->tgt;
 171         assert(src_node);
 172         assert(tgt_node);
 173
 174         src_vec = src_node->costs;
 175         tgt_vec = tgt_node->costs;
 176         assert(src_vec);
 177         assert(tgt_vec);
 178
 179         src_len = src_vec->len;
 180         tgt_len = tgt_vec->len;
 181         assert(src_len > 0);
 182         assert(tgt_len > 0);
 183
 184         mat = edge->costs;
 185         assert(mat);
 186
 187         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 188                 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 189
 190                 if (min != 0) {
 191                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 192                                 pbqp_matrix_set_col_value(mat, tgt_index, 0);
 193                         } else {
 194                                 pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
 195                         }
 196                         tgt_vec->entries[tgt_index].data = pbqp_add(
 197                                         tgt_vec->entries[tgt_index].data, min);
 198
 199                         if (min == INF_COSTS) {
 200                                 unsigned edge_index;
 201                                 unsigned edge_len = pbqp_node_get_degree(tgt_node);
 202
 203                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 204                                         pbqp_edge *edge_candidate = tgt_node->edges[edge_index];
 205                                         if (edge_candidate != edge) {
 206                                                 insert_into_edge_bucket(edge_candidate);
 207                                         }
 208                                 }
 209                         }
 210                 }
 211         }
 212 }
 213
 214 static void reorder_node(pbqp_node *node)
 215 {
 216         unsigned    degree     = pbqp_node_get_degree(node);
 217         /* Assume node lost one incident edge. */
 218         unsigned    old_degree = degree + 1;
 219
 220         if (!buckets_filled) return;
 221
 222         /* Same bucket as before */
 223         if (degree > 2) return;
 224
 225         if (!node_bucket_contains(node_buckets[old_degree], node)) {
 226                 /* Old arity is new arity, so we have nothing to do. */
 227                 assert(node_bucket_contains(node_buckets[degree], node));
 228                 return;
 229         }
 230
 231         /* Delete node from old bucket... */
 232         node_bucket_remove(&node_buckets[old_degree], node);
 233
 234         /* ..and add to new one. */
 235         node_bucket_insert(&node_buckets[degree], node);
 236 }
 237
 238 #if 0
 239 static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
 240 {
 241         pbqp_matrix    *mat;
 242         pbqp_node      *src_node;
 243         pbqp_node      *tgt_node;
 244         vector         *src_vec;
 245         vector         *tgt_vec;
 246         int             src_len;
 247         int             tgt_len;
 248         int             src_index;
 249         int             tgt_index;
 250
 251         assert(pbqp);
 252         assert(edge);
 253
 254         src_node = edge->src;
 255         tgt_node = edge->tgt;
 256         assert(src_node);
 257         assert(tgt_node);
 258
 259         src_vec = src_node->costs;
 260         tgt_vec = tgt_node->costs;
 261         assert(src_vec);
 262         assert(tgt_vec);
 263
 264         src_len = src_vec->len;
 265         tgt_len = tgt_vec->len;
 266         assert(src_len > 0);
 267         assert(tgt_len > 0);
 268
 269         mat = edge->costs;
 270         assert(mat);
 271
 272         if (src_len == 1 && tgt_len == 1) {
 273                 //panic("Something is wrong");
 274         }
 275
 276         int allRowsOk = 1;
 277         for (src_index = 0; src_index < src_len; ++src_index) {
 278                 int onlyOneZero = 0;
 279                 if (src_vec->entries[src_index].data == INF_COSTS) {
 280                         continue;
 281                 }
 282                 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 283                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 284                                 continue;
 285                         }
 286                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 287                                 if (onlyOneZero) {
 288                                         onlyOneZero = 0;
 289                                         break;
 290                                 } else {
 291                                         onlyOneZero = 1;
 292                                         continue;
 293                                 }
 294                         }
 295                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 296                                 continue;
 297                         }
 298                         onlyOneZero = 0;
 299                         break;
 300                 }
 301                 allRowsOk &= onlyOneZero;
 302         }
 303
 304         int allColsOk = 1;
 305         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 306                 int onlyOneZero = 0;
 307                 if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 308                         continue;
 309                 }
 310                 for (src_index = 0; src_index < src_len; ++src_index) {
 311                         if (src_vec->entries[src_index].data == INF_COSTS) {
 312                                 continue;
 313                         }
 314                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 315                                 if (onlyOneZero) {
 316                                         onlyOneZero = 0;
 317                                         break;
 318                                 } else {
 319                                         onlyOneZero = 1;
 320                                         continue;
 321                                 }
 322                         }
 323                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 324                                 continue;
 325                         }
 326                         onlyOneZero = 0;
 327                         break;
 328                 }
 329                 allColsOk &= onlyOneZero;
 330         }
 331
 332         if (allRowsOk && allColsOk) {
 333                 panic("Hurray");
 334         }
 335 }
 336 #endif
 337
 338 static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 339 {
 340         pbqp_matrix    *mat;
 341         pbqp_node      *src_node;
 342         pbqp_node      *tgt_node;
 343         vector         *src_vec;
 344         vector         *tgt_vec;
 345         int             src_len;
 346         int             tgt_len;
 347
 348         assert(pbqp);
 349         assert(edge);
 350
 351         src_node = edge->src;
 352         tgt_node = edge->tgt;
 353         assert(src_node);
 354         assert(tgt_node);
 355
 356         /* If edge are already deleted, we have nothing to do. */
 357         if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
 358                 return;
 359
 360 #if     KAPS_DUMP
 361         if (pbqp->dump_file) {
 362                 char txt[100];
 363                 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
 364                 dump_section(pbqp->dump_file, 3, txt);
 365         }
 366 #endif
 367
 368         src_vec = src_node->costs;
 369         tgt_vec = tgt_node->costs;
 370         assert(src_vec);
 371         assert(tgt_vec);
 372
 373         src_len = src_vec->len;
 374         tgt_len = tgt_vec->len;
 375         assert(src_len > 0);
 376         assert(tgt_len > 0);
 377
 378         mat = edge->costs;
 379         assert(mat);
 380
 381 #if     KAPS_DUMP
 382         if (pbqp->dump_file) {
 383                 fputs("Input:<br>\n", pbqp->dump_file);
 384                 dump_simplifyedge(pbqp, edge);
 385         }
 386 #endif
 387
 388         normalize_towards_source(pbqp, edge);
 389         normalize_towards_target(pbqp, edge);
 390
 391 #if     KAPS_DUMP
 392         if (pbqp->dump_file) {
 393                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 394                 dump_simplifyedge(pbqp, edge);
 395         }
 396 #endif
 397
 398         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 399 #if     KAPS_DUMP
 400                 if (pbqp->dump_file) {
 401                         fputs("edge has been eliminated<br>\n", pbqp->dump_file);
 402                 }
 403 #endif
 404
 405 #if KAPS_STATISTIC
 406                 if (dump == 0) {
 407                         pbqp->num_edges++;
 408                 }
 409 #endif
 410
 411                 delete_edge(edge);
 412                 reorder_node(src_node);
 413                 reorder_node(tgt_node);
 414         }
 415 }
 416
 417 static void initial_simplify_edges(pbqp *pbqp)
 418 {
 419         unsigned node_index;
 420         unsigned node_len;
 421
 422         assert(pbqp);
 423
 424 #if     KAPS_DUMP
 425         if (pbqp->dump_file) {
 426                 pbqp_dump_input(pbqp);
 427                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 428         }
 429 #endif
 430
 431         node_len = pbqp->num_nodes;
 432
 433         init_buckets();
 434
 435         /* First simplify all edges. */
 436         for (node_index = 0; node_index < node_len; ++node_index) {
 437                 unsigned    edge_index;
 438                 pbqp_node  *node = get_node(pbqp, node_index);
 439                 pbqp_edge **edges;
 440                 unsigned    edge_len;
 441
 442                 if (!node) continue;
 443
 444                 edges = node->edges;
 445                 edge_len = pbqp_node_get_degree(node);
 446
 447                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 448                         pbqp_edge *edge = edges[edge_index];
 449
 450                         /* Simplify only once per edge. */
 451                         if (node != edge->src) continue;
 452
 453                         simplify_edge(pbqp, edge);
 454                 }
 455         }
 456 }
 457
 458 static num determine_solution(pbqp *pbqp)
 459 {
 460         unsigned node_index;
 461         unsigned node_len;
 462         num      solution   = 0;
 463 #if     KAPS_DUMP
 464         FILE     *file;
 465 #endif
 466
 467         assert(pbqp);
 468
 469 #if     KAPS_DUMP
 470         file = pbqp->dump_file;
 471
 472         if (file) {
 473                 dump_section(file, 1, "4. Determine Solution/Minimum");
 474                 dump_section(file, 2, "4.1. Trivial Solution");
 475         }
 476 #endif
 477
 478         /* Solve trivial nodes and calculate solution. */
 479         node_len = node_bucket_get_length(node_buckets[0]);
 480
 481 #if KAPS_STATISTIC
 482         if (dump == 0) {
 483                 pbqp->num_r0 = node_len;
 484         }
 485 #endif
 486
 487         for (node_index = 0; node_index < node_len; ++node_index) {
 488                 pbqp_node *node = node_buckets[0][node_index];
 489                 assert(node);
 490
 491                 node->solution = vector_get_min_index(node->costs);
 492                 solution       = pbqp_add(solution,
 493                                 node->costs->entries[node->solution].data);
 494
 495 #if     KAPS_DUMP
 496                 if (file) {
 497                         fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
 498                         dump_node(file, node);
 499                 }
 500 #endif
 501         }
 502
 503 #if     KAPS_DUMP
 504         if (file) {
 505                 dump_section(file, 2, "Minimum");
 506                 fprintf(file, "Minimum is equal to %lld.", solution);
 507         }
 508 #endif
 509
 510         return solution;
 511 }
 512
 513 static void back_propagate(pbqp *pbqp)
 514 {
 515         unsigned node_index;
 516         unsigned node_len   = node_bucket_get_length(reduced_bucket);
 517
 518         assert(pbqp);
 519
 520 #if     KAPS_DUMP
 521         if (pbqp->dump_file) {
 522                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 523         }
 524 #endif
 525
 526         for (node_index = node_len; node_index > 0; --node_index) {
 527                 pbqp_node *node = reduced_bucket[node_index - 1];
 528
 529                 switch (pbqp_node_get_degree(node)) {
 530                         case 1:
 531                                 back_propagate_RI(pbqp, node);
 532                                 break;
 533                         case 2:
 534                                 back_propagate_RII(pbqp, node);
 535                                 break;
 536                         default:
 537                                 panic("Only nodes with degree one or two should be in this bucket");
 538                                 break;
 539                 }
 540         }
 541 }
 542
 543 static void apply_heuristic_reductions(pbqp *pbqp)
 544 {
 545         for (;;) {
 546                 if (edge_bucket_get_length(edge_bucket) > 0) {
 547                         apply_edge(pbqp);
 548                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
 549                         apply_RI(pbqp);
 550                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
 551                         apply_RII(pbqp);
 552                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
 553                         apply_RN(pbqp);
 554                 } else {
 555                         return;
 556                 }
 557         }
 558 }
 559
 560 static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo)
 561 {
 562         for (;;) {
 563                 if (edge_bucket_get_length(edge_bucket) > 0) {
 564                         apply_edge(pbqp);
 565                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
 566                         apply_RI(pbqp);
 567 //                      apply_RN_co(pbqp, rpeo);
 568                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
 569                         apply_RII(pbqp);
 570 //                      apply_RN_co(pbqp, rpeo);
 571                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
 572                         apply_RN_co(pbqp, rpeo);
 573                 } else {
 574                         return;
 575                 }
 576         }
 577 }
 578
 579 void solve_pbqp_heuristical(pbqp *pbqp)
 580 {
 581         /* Reduce nodes degree ... */
 582         initial_simplify_edges(pbqp);
 583
 584         /* ... and put node into bucket representing their degree. */
 585         fill_node_buckets(pbqp);
 586
 587 #if KAPS_STATISTIC
 588         FILE *fh = fopen("solutions.pb", "a");
 589         fprintf(fh, "Solution");
 590         fclose(fh);
 591 #endif
 592
 593         apply_heuristic_reductions(pbqp);
 594
 595         pbqp->solution = determine_solution(pbqp);
 596
 597 #if KAPS_STATISTIC
 598         fh = fopen("solutions.pb", "a");
 599         fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
 600                                 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 601                                 pbqp->num_rn);
 602         fclose(fh);
 603 #endif
 604
 605         /* Solve reduced nodes. */
 606         back_propagate(pbqp);
 607
 608         free_buckets();
 609 }
 610
 611 void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo) {
 612         /* Reduce nodes degree ... */
 613                 initial_simplify_edges(pbqp);
 614
 615                 /* ... and put node into bucket representing their degree. */
 616                 fill_node_buckets(pbqp);
 617
 618         #if KAPS_STATISTIC
 619                 FILE *fh = fopen("solutions.pb", "a");
 620                 fprintf(fh, "Solution");
 621                 fclose(fh);
 622         #endif
 623
 624                 apply_heuristic_reductions_co(pbqp, rpeo);
 625
 626                 pbqp->solution = determine_solution(pbqp);
 627
 628         #if KAPS_STATISTIC
 629                 fh = fopen("solutions.pb", "a");
 630                 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
 631                                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 632                                         pbqp->num_rn);
 633                 fclose(fh);
 634         #endif
 635
 636                 /* Solve reduced nodes. */
 637                 back_propagate(pbqp);
 638
 639                 free_buckets();
 640 }
 641
 642 void apply_edge(pbqp *pbqp)
 643 {
 644         pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
 645
 646         simplify_edge(pbqp, edge);
 647 }
 648
 649 void apply_RI(pbqp *pbqp)
 650 {
 651         pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
 652         pbqp_edge   *edge       = node->edges[0];
 653         pbqp_matrix *mat        = edge->costs;
 654         int          is_src     = edge->src == node;
 655         pbqp_node   *other_node;
 656
 657         assert(pbqp_node_get_degree(node) == 1);
 658
 659         if (is_src) {
 660                 other_node = edge->tgt;
 661         } else {
 662                 other_node = edge->src;
 663         }
 664
 665 #if     KAPS_DUMP
 666         if (pbqp->dump_file) {
 667                 char     txt[100];
 668                 sprintf(txt, "RI-Reduction of Node n%d", node->index);
 669                 dump_section(pbqp->dump_file, 2, txt);
 670                 pbqp_dump_graph(pbqp);
 671                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 672                 dump_node(pbqp->dump_file, node);
 673                 dump_node(pbqp->dump_file, other_node);
 674                 dump_edge(pbqp->dump_file, edge);
 675         }
 676 #endif
 677
 678         if (is_src) {
 679                 pbqp_matrix_add_to_all_cols(mat, node->costs);
 680                 normalize_towards_target(pbqp, edge);
 681         } else {
 682                 pbqp_matrix_add_to_all_rows(mat, node->costs);
 683                 normalize_towards_source(pbqp, edge);
 684         }
 685         disconnect_edge(other_node, edge);
 686
 687 #if     KAPS_DUMP
 688         if (pbqp->dump_file) {
 689                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 690                 dump_node(pbqp->dump_file, other_node);
 691         }
 692 #endif
 693
 694         reorder_node(other_node);
 695
 696 #if KAPS_STATISTIC
 697         if (dump == 0) {
 698                 pbqp->num_r1++;
 699         }
 700 #endif
 701
 702         /* Add node to back propagation list. */
 703         node_bucket_insert(&reduced_bucket, node);
 704 }
 705
 706 void apply_RII(pbqp *pbqp)
 707 {
 708         pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
 709         pbqp_edge   *src_edge   = node->edges[0];
 710         pbqp_edge   *tgt_edge   = node->edges[1];
 711         int          src_is_src = src_edge->src == node;
 712         int          tgt_is_src = tgt_edge->src == node;
 713         pbqp_matrix *src_mat;
 714         pbqp_matrix *tgt_mat;
 715         pbqp_node   *src_node;
 716         pbqp_node   *tgt_node;
 717         pbqp_matrix *mat;
 718         vector      *vec;
 719         vector      *node_vec;
 720         vector      *src_vec;
 721         vector      *tgt_vec;
 722         unsigned     col_index;
 723         unsigned     col_len;
 724         unsigned     row_index;
 725         unsigned     row_len;
 726         unsigned     node_len;
 727
 728         assert(pbqp);
 729         assert(pbqp_node_get_degree(node) == 2);
 730
 731         if (src_is_src) {
 732                 src_node = src_edge->tgt;
 733         } else {
 734                 src_node = src_edge->src;
 735         }
 736
 737         if (tgt_is_src) {
 738                 tgt_node = tgt_edge->tgt;
 739         } else {
 740                 tgt_node = tgt_edge->src;
 741         }
 742
 743         /* Swap nodes if necessary. */
 744         if (tgt_node->index < src_node->index) {
 745                 pbqp_node *tmp_node;
 746                 pbqp_edge *tmp_edge;
 747
 748                 tmp_node = src_node;
 749                 src_node = tgt_node;
 750                 tgt_node = tmp_node;
 751
 752                 tmp_edge = src_edge;
 753                 src_edge = tgt_edge;
 754                 tgt_edge = tmp_edge;
 755
 756                 src_is_src = src_edge->src == node;
 757                 tgt_is_src = tgt_edge->src == node;
 758         }
 759
 760 #if     KAPS_DUMP
 761         if (pbqp->dump_file) {
 762                 char     txt[100];
 763                 sprintf(txt, "RII-Reduction of Node n%d", node->index);
 764                 dump_section(pbqp->dump_file, 2, txt);
 765                 pbqp_dump_graph(pbqp);
 766                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 767                 dump_node(pbqp->dump_file, src_node);
 768                 dump_edge(pbqp->dump_file, src_edge);
 769                 dump_node(pbqp->dump_file, node);
 770                 dump_edge(pbqp->dump_file, tgt_edge);
 771                 dump_node(pbqp->dump_file, tgt_node);
 772         }
 773 #endif
 774
 775         src_mat = src_edge->costs;
 776         tgt_mat = tgt_edge->costs;
 777
 778         src_vec  = src_node->costs;
 779         tgt_vec  = tgt_node->costs;
 780         node_vec = node->costs;
 781
 782         row_len  = src_vec->len;
 783         col_len  = tgt_vec->len;
 784         node_len = node_vec->len;
 785
 786         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
 787
 788         for (row_index = 0; row_index < row_len; ++row_index) {
 789                 for (col_index = 0; col_index < col_len; ++col_index) {
 790                         vec = vector_copy(pbqp, node_vec);
 791
 792                         if (src_is_src) {
 793                                 vector_add_matrix_col(vec, src_mat, row_index);
 794                         } else {
 795                                 vector_add_matrix_row(vec, src_mat, row_index);
 796                         }
 797
 798                         if (tgt_is_src) {
 799                                 vector_add_matrix_col(vec, tgt_mat, col_index);
 800                         } else {
 801                                 vector_add_matrix_row(vec, tgt_mat, col_index);
 802                         }
 803
 804                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
 805
 806                         obstack_free(&pbqp->obstack, vec);
 807                 }
 808         }
 809
 810         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
 811
 812         /* Disconnect node. */
 813         disconnect_edge(src_node, src_edge);
 814         disconnect_edge(tgt_node, tgt_edge);
 815
 816 #if KAPS_STATISTIC
 817         if (dump == 0) {
 818                 pbqp->num_r2++;
 819         }
 820 #endif
 821
 822         /* Add node to back propagation list. */
 823         node_bucket_insert(&reduced_bucket, node);
 824
 825         if (edge == NULL) {
 826                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
 827         } else {
 828                 pbqp_matrix_add(edge->costs, mat);
 829
 830                 /* Free local matrix. */
 831                 obstack_free(&pbqp->obstack, mat);
 832
 833                 reorder_node(src_node);
 834                 reorder_node(tgt_node);
 835         }
 836
 837 #if     KAPS_DUMP
 838         if (pbqp->dump_file) {
 839                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 840                 dump_edge(pbqp->dump_file, edge);
 841         }
 842 #endif
 843
 844         /* Edge has changed so we simplify it. */
 845         simplify_edge(pbqp, edge);
 846 }
 847
 848 static void select_alternative(pbqp_node *node, unsigned selected_index)
 849 {
 850         unsigned  edge_index;
 851         unsigned  node_index;
 852         unsigned  node_len;
 853         vector   *node_vec;
 854         unsigned  max_degree = pbqp_node_get_degree(node);
 855
 856         assert(node);
 857         node->solution = selected_index;
 858         node_vec = node->costs;
 859         node_len = node_vec->len;
 860         assert(selected_index < node_len);
 861
 862         /* Set all other costs to infinity. */
 863         for (node_index = 0; node_index < node_len; ++node_index) {
 864                 if (node_index != selected_index) {
 865                         node_vec->entries[node_index].data = INF_COSTS;
 866                 }
 867         }
 868
 869         /* Add all incident edges to edge bucket, since they are now independent. */
 870         for (edge_index = 0; edge_index < max_degree; ++edge_index) {
 871                 insert_into_edge_bucket(node->edges[edge_index]);
 872         }
 873 }
 874
 875 static pbqp_node *get_node_with_max_degree(void)
 876 {
 877         pbqp_node  **bucket       = node_buckets[3];
 878         unsigned     bucket_len   = node_bucket_get_length(bucket);
 879         unsigned     bucket_index;
 880         unsigned     max_degree   = 0;
 881         pbqp_node   *result       = NULL;
 882
 883         for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
 884                 pbqp_node *candidate = bucket[bucket_index];
 885                 unsigned   degree    = pbqp_node_get_degree(candidate);
 886
 887                 if (degree > max_degree) {
 888                         result = candidate;
 889                         max_degree = degree;
 890                 }
 891         }
 892
 893         return result;
 894 }
 895
 896 static unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node)
 897 {
 898         pbqp_edge   *edge;
 899         vector      *node_vec;
 900         vector      *vec;
 901         pbqp_matrix *mat;
 902         unsigned     edge_index;
 903         unsigned     max_degree   = 0;
 904         unsigned     node_index;
 905         unsigned     node_len;
 906         unsigned     min_index    = 0;
 907         num          min          = INF_COSTS;
 908         int          is_src;
 909
 910         assert(pbqp);
 911         assert(node);
 912         node_vec = node->costs;
 913         node_len = node_vec->len;
 914
 915         for (node_index = 0; node_index < node_len; ++node_index) {
 916                 num value = node_vec->entries[node_index].data;
 917
 918                 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
 919                         edge   = node->edges[edge_index];
 920                         mat    = edge->costs;
 921                         is_src = edge->src == node;
 922
 923                         if (is_src) {
 924                                 vec = vector_copy(pbqp, edge->tgt->costs);
 925                                 vector_add_matrix_row(vec, mat, node_index);
 926                         } else {
 927                                 vec = vector_copy(pbqp, edge->src->costs);
 928                                 vector_add_matrix_col(vec, mat, node_index);
 929                         }
 930
 931                         value = pbqp_add(value, vector_get_min(vec));
 932
 933                         obstack_free(&pbqp->obstack, vec);
 934                 }
 935
 936                 if (value < min) {
 937                         min = value;
 938                         min_index = node_index;
 939                 }
 940         }
 941
 942         return min_index;
 943 }
 944
 945 void apply_RN(pbqp *pbqp)
 946 {
 947 //      printf("### ---- RN\n");
 948
 949         pbqp_node   *node         = NULL;
 950         unsigned     min_index    = 0;
 951
 952         assert(pbqp);
 953
 954         /* We want to reduce a node with maximum degree. */
 955         node = get_node_with_max_degree();
 956         assert(node);
 957         assert(pbqp_node_get_degree(node) > 2);
 958
 959 #if     KAPS_DUMP
 960         if (pbqp->dump_file) {
 961                 char     txt[100];
 962                 sprintf(txt, "RN-Reduction of Node n%d", node->index);
 963                 dump_section(pbqp->dump_file, 2, txt);
 964                 pbqp_dump_graph(pbqp);
 965         }
 966 #endif
 967
 968         min_index = get_local_minimal_alternative(pbqp, node);
 969
 970 #if     KAPS_DUMP
 971         if (pbqp->dump_file) {
 972                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
 973                                         node->index, min_index);
 974         }
 975 #endif
 976
 977 #if KAPS_STATISTIC
 978         if (dump == 0) {
 979                 FILE *fh = fopen("solutions.pb", "a");
 980                 fprintf(fh, "[%u]", min_index);
 981                 fclose(fh);
 982                 pbqp->num_rn++;
 983         }
 984 #endif
 985
 986         /* Now that we found the local minimum set all other costs to infinity. */
 987         select_alternative(node, min_index);
 988 }
 989
 990 void apply_RN_co(pbqp *pbqp, plist_t *rpeo)
 991 {
 992 //      printf("### ---- RN\n");
 993
 994         pbqp_node   *node         = NULL;
 995         unsigned     min_index    = 0;
 996
 997         assert(pbqp);
 998
 999         /* We want to reduce the first node in reverse perfect elimination order. */
1000         do {
1001                 /* get first element from reverse perfect elimination order */
1002                 node = plist_first(rpeo)->data;
1003                 /* remove element from reverse perfect elimination order */
1004                 plist_erase(rpeo, plist_first(rpeo));
1005         } while(node_is_reduced(node));
1006
1007 //      node = plist_first(rpeo)->data;
1008 //      plist_erase(rpeo, plist_first(rpeo));
1009
1010         assert(node);
1011         assert(pbqp_node_get_degree(node) > 2);
1012
1013 #if     KAPS_DUMP
1014         if (pbqp->dump_file) {
1015                 char     txt[100];
1016                 sprintf(txt, "RN-Reduction of Node n%d", node->index);
1017                 dump_section(pbqp->dump_file, 2, txt);
1018                 pbqp_dump_graph(pbqp);
1019         }
1020 #endif
1021
1022         min_index = get_local_minimal_alternative(pbqp, node);
1023
1024 #if     KAPS_DUMP
1025         if (pbqp->dump_file) {
1026                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
1027                                         node->index, min_index);
1028         }
1029 #endif
1030
1031 #if KAPS_STATISTIC
1032         if (dump == 0) {
1033                 FILE *fh = fopen("solutions.pb", "a");
1034                 fprintf(fh, "[%u]", min_index);
1035                 fclose(fh);
1036                 pbqp->num_rn++;
1037         }
1038 #endif
1039
1040         /* Now that we found the local minimum set all other costs to infinity. */
1041         select_alternative(node, min_index);
1042
1043
1044 }
1045
1046 static void apply_brute_force_reductions(pbqp *pbqp)
1047 {
1048         for (;;) {
1049                 if (edge_bucket_get_length(edge_bucket) > 0) {
1050                         apply_edge(pbqp);
1051                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
1052                         apply_RI(pbqp);
1053                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
1054                         apply_RII(pbqp);
1055                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
1056                         apply_Brute_Force(pbqp);
1057                 } else {
1058                         return;
1059                 }
1060         }
1061 }
1062
1063 static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node)
1064 {
1065         vector      *node_vec;
1066         unsigned     node_index;
1067         unsigned     node_len;
1068         unsigned     min_index    = 0;
1069         num          min          = INF_COSTS;
1070         unsigned     bucket_index;
1071
1072         assert(pbqp);
1073         assert(node);
1074         node_vec     = node->costs;
1075         node_len     = node_vec->len;
1076         bucket_index = node->bucket_index;
1077
1078         for (node_index = 0; node_index < node_len; ++node_index) {
1079                 pbqp_node_bucket bucket_deg3;
1080                 num              value;
1081                 unsigned         bucket_0_length;
1082                 unsigned         bucket_red_length;
1083
1084                 char *tmp = obstack_finish(&pbqp->obstack);
1085
1086                 node_bucket_init(&bucket_deg3);
1087
1088                 /* Some node buckets and the edge bucket should be empty. */
1089                 assert(node_bucket_get_length(node_buckets[1]) == 0);
1090                 assert(node_bucket_get_length(node_buckets[2]) == 0);
1091                 assert(edge_bucket_get_length(edge_bucket)     == 0);
1092
1093                 /* char *tmp = obstack_finish(&pbqp->obstack); */
1094
1095                 /* Save current PBQP state. */
1096                 node_bucket_copy(&bucket_deg3, node_buckets[3]);
1097                 node_bucket_shrink(&node_buckets[3], 0);
1098                 node_bucket_deep_copy(pbqp, &node_buckets[3], bucket_deg3);
1099                 node_bucket_update(pbqp, node_buckets[3]);
1100                 bucket_0_length   = node_bucket_get_length(node_buckets[0]);
1101                 bucket_red_length = node_bucket_get_length(reduced_bucket);
1102
1103                 /* Select alternative and solve PBQP recursively. */
1104                 select_alternative(node_buckets[3][bucket_index], node_index);
1105                 apply_brute_force_reductions(pbqp);
1106
1107                 value = determine_solution(pbqp);
1108
1109                 if (value < min) {
1110                         min = value;
1111                         min_index = node_index;
1112                 }
1113
1114                 /* Some node buckets and the edge bucket should still be empty. */
1115                 assert(node_bucket_get_length(node_buckets[1]) == 0);
1116                 assert(node_bucket_get_length(node_buckets[2]) == 0);
1117                 assert(edge_bucket_get_length(edge_bucket)     == 0);
1118
1119                 /* Clear modified buckets... */
1120                 node_bucket_shrink(&node_buckets[3], 0);
1121
1122                 /* ... and restore old PBQP state. */
1123                 node_bucket_shrink(&node_buckets[0], bucket_0_length);
1124                 node_bucket_shrink(&reduced_bucket, bucket_red_length);
1125                 node_bucket_copy(&node_buckets[3], bucket_deg3);
1126                 node_bucket_update(pbqp, node_buckets[3]);
1127
1128                 /* Free copies. */
1129                 /* obstack_free(&pbqp->obstack, tmp); */
1130                 node_bucket_free(&bucket_deg3);
1131
1132                 obstack_free(&pbqp->obstack, tmp);
1133         }
1134
1135         return min_index;
1136 }
1137
1138 void apply_Brute_Force(pbqp *pbqp)
1139 {
1140         pbqp_node   *node         = NULL;
1141         unsigned     min_index    = 0;
1142
1143         assert(pbqp);
1144
1145         /* We want to reduce a node with maximum degree. */
1146         node = get_node_with_max_degree();
1147         assert(node);
1148         assert(pbqp_node_get_degree(node) > 2);
1149
1150 #if     KAPS_DUMP
1151         if (pbqp->dump_file) {
1152                 char     txt[100];
1153                 sprintf(txt, "BF-Reduction of Node n%d", node->index);
1154                 dump_section(pbqp->dump_file, 2, txt);
1155                 pbqp_dump_graph(pbqp);
1156         }
1157 #endif
1158
1159 #if KAPS_STATISTIC
1160         dump++;
1161 #endif
1162
1163         min_index = get_minimal_alternative(pbqp, node);
1164         node = pbqp->nodes[node->index];
1165
1166 #if     KAPS_DUMP
1167         if (pbqp->dump_file) {
1168                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
1169                                         node->index, min_index);
1170         }
1171 #endif
1172
1173 #if KAPS_STATISTIC
1174         dump--;
1175         if (dump == 0) {
1176                 FILE *fh = fopen("solutions.pb", "a");
1177                 fprintf(fh, "[%u]", min_index);
1178                 fclose(fh);
1179                 pbqp->num_bf++;
1180         }
1181 #endif
1182
1183         /* Now that we found the minimum set all other costs to infinity. */
1184         select_alternative(node, min_index);
1185 }
1186
1187 void solve_pbqp_brute_force(pbqp *pbqp)
1188 {
1189         /* Reduce nodes degree ... */
1190         initial_simplify_edges(pbqp);
1191
1192         /* ... and put node into bucket representing their degree. */
1193         fill_node_buckets(pbqp);
1194
1195 #if KAPS_STATISTIC
1196         FILE *fh = fopen("solutions.pb", "a");
1197         fprintf(fh, "Solution");
1198         fclose(fh);
1199 #endif
1200
1201         apply_brute_force_reductions(pbqp);
1202
1203         pbqp->solution = determine_solution(pbqp);
1204
1205 #if KAPS_STATISTIC
1206         fh = fopen("solutions.pb", "a");
1207         fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
1208                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
1209                         pbqp->num_bf);
1210         fclose(fh);
1211 #endif
1212
1213         /* Solve reduced nodes. */
1214         back_propagate(pbqp);
1215
1216         free_buckets();
1217 }
1218
1219 void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
1220 {
1221         pbqp_edge   *edge;
1222         pbqp_node   *other;
1223         pbqp_matrix *mat;
1224         vector      *vec;
1225         int          is_src;
1226
1227         assert(pbqp);
1228         assert(node);
1229
1230         edge = node->edges[0];
1231         mat = edge->costs;
1232         is_src = edge->src == node;
1233         vec = node->costs;
1234
1235         if (is_src) {
1236                 other = edge->tgt;
1237                 assert(other);
1238
1239                 /* Update pointer for brute force solver. */
1240                 other = pbqp->nodes[other->index];
1241
1242                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
1243         } else {
1244                 other = edge->src;
1245                 assert(other);
1246
1247                 /* Update pointer for brute force solver. */
1248                 other = pbqp->nodes[other->index];
1249
1250                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
1251         }
1252
1253 #if     KAPS_DUMP
1254         if (pbqp->dump_file) {
1255                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
1256         }
1257 #endif
1258 }
1259
1260 void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
1261 {
1262         pbqp_edge   *src_edge   = node->edges[0];
1263         pbqp_edge   *tgt_edge   = node->edges[1];
1264         int          src_is_src = src_edge->src == node;
1265         int          tgt_is_src = tgt_edge->src == node;
1266         pbqp_matrix *src_mat;
1267         pbqp_matrix *tgt_mat;
1268         pbqp_node   *src_node;
1269         pbqp_node   *tgt_node;
1270         vector      *vec;
1271         vector      *node_vec;
1272         unsigned     col_index;
1273         unsigned     row_index;
1274
1275         assert(pbqp);
1276
1277         if (src_is_src) {
1278                 src_node = src_edge->tgt;
1279         } else {
1280                 src_node = src_edge->src;
1281         }
1282
1283         if (tgt_is_src) {
1284                 tgt_node = tgt_edge->tgt;
1285         } else {
1286                 tgt_node = tgt_edge->src;
1287         }
1288
1289         /* Swap nodes if necessary. */
1290         if (tgt_node->index < src_node->index) {
1291                 pbqp_node *tmp_node;
1292                 pbqp_edge *tmp_edge;
1293
1294                 tmp_node = src_node;
1295                 src_node = tgt_node;
1296                 tgt_node = tmp_node;
1297
1298                 tmp_edge = src_edge;
1299                 src_edge = tgt_edge;
1300                 tgt_edge = tmp_edge;
1301
1302                 src_is_src = src_edge->src == node;
1303                 tgt_is_src = tgt_edge->src == node;
1304         }
1305
1306         /* Update pointer for brute force solver. */
1307         src_node = pbqp->nodes[src_node->index];
1308         tgt_node = pbqp->nodes[tgt_node->index];
1309
1310         src_mat = src_edge->costs;
1311         tgt_mat = tgt_edge->costs;
1312
1313         node_vec = node->costs;
1314
1315         row_index = src_node->solution;
1316         col_index = tgt_node->solution;
1317
1318         vec = vector_copy(pbqp, node_vec);
1319
1320         if (src_is_src) {
1321                 vector_add_matrix_col(vec, src_mat, row_index);
1322         } else {
1323                 vector_add_matrix_row(vec, src_mat, row_index);
1324         }
1325
1326         if (tgt_is_src) {
1327                 vector_add_matrix_col(vec, tgt_mat, col_index);
1328         } else {
1329                 vector_add_matrix_row(vec, tgt_mat, col_index);
1330         }
1331
1332         node->solution = vector_get_min_index(vec);
1333
1334 #if     KAPS_DUMP
1335         if (pbqp->dump_file) {
1336                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
1337         }
1338 #endif
1339
1340         obstack_free(&pbqp->obstack, vec);
1341 }
1342
1343 int node_is_reduced(pbqp_node *node)
1344 {
1345         if (!reduced_bucket) return 0;
1346
1347         if (pbqp_node_get_degree(node) == 0) return 1;
1348
1349         return node_bucket_contains(reduced_bucket, node);
1350 }