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