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