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_after_edge_deletion(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         /* Delete node from old bucket... */
 635         node_bucket_remove(&node_buckets[old_degree], node);
 636
 637         /* ..and add to new one. */
 638         node_bucket_insert(&node_buckets[degree], node);
 639 }
 640
 641 void reorder_node_after_edge_insertion(pbqp_node *node)
 642 {
 643         unsigned    degree     = pbqp_node_get_degree(node);
 644         /* Assume node lost one incident edge. */
 645         unsigned    old_degree = degree - 1;
 646
 647         if (!buckets_filled) return;
 648
 649         /* Same bucket as before */
 650         if (old_degree > 2) return;
 651
 652         /* Delete node from old bucket... */
 653         node_bucket_remove(&node_buckets[old_degree], node);
 654
 655         /* ..and add to new one. */
 656         node_bucket_insert(&node_buckets[degree], node);
 657 }
 658
 659 void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 660 {
 661         pbqp_matrix    *mat;
 662         pbqp_node      *src_node;
 663         pbqp_node      *tgt_node;
 664         vector         *src_vec;
 665         vector         *tgt_vec;
 666         int             src_len;
 667         int             tgt_len;
 668
 669         assert(pbqp);
 670         assert(edge);
 671
 672         (void) pbqp;
 673
 674         src_node = edge->src;
 675         tgt_node = edge->tgt;
 676         assert(src_node);
 677         assert(tgt_node);
 678
 679         /* If edge are already deleted, we have nothing to do. */
 680         if (is_deleted(edge))
 681                 return;
 682
 683 #if     KAPS_DUMP
 684         if (pbqp->dump_file) {
 685                 char txt[100];
 686                 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
 687                 dump_section(pbqp->dump_file, 3, txt);
 688         }
 689 #endif
 690
 691         src_vec = src_node->costs;
 692         tgt_vec = tgt_node->costs;
 693         assert(src_vec);
 694         assert(tgt_vec);
 695
 696         src_len = src_vec->len;
 697         tgt_len = tgt_vec->len;
 698         assert(src_len > 0);
 699         assert(tgt_len > 0);
 700
 701         mat = edge->costs;
 702         assert(mat);
 703
 704 #if     KAPS_DUMP
 705         if (pbqp->dump_file) {
 706                 fputs("Input:<br>\n", pbqp->dump_file);
 707                 dump_simplifyedge(pbqp, edge);
 708         }
 709 #endif
 710
 711         normalize_towards_source(edge);
 712         normalize_towards_target(edge);
 713
 714 #if     KAPS_DUMP
 715         if (pbqp->dump_file) {
 716                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 717                 dump_simplifyedge(pbqp, edge);
 718         }
 719 #endif
 720
 721         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 722 #if     KAPS_DUMP
 723                 if (pbqp->dump_file) {
 724                         fputs("edge has been eliminated<br>\n", pbqp->dump_file);
 725                 }
 726 #endif
 727
 728 #if KAPS_STATISTIC
 729                 pbqp->num_edges++;
 730 #endif
 731
 732                 delete_edge(edge);
 733         }
 734 }
 735
 736 void initial_simplify_edges(pbqp *pbqp)
 737 {
 738         unsigned node_index;
 739         unsigned node_len;
 740
 741         assert(pbqp);
 742
 743         #if KAPS_TIMING
 744                 ir_timer_t *t_int_simpl = ir_timer_new();
 745                 ir_timer_start(t_int_simpl);
 746         #endif
 747
 748 #if     KAPS_DUMP
 749         if (pbqp->dump_file) {
 750                 pbqp_dump_input(pbqp);
 751                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 752         }
 753 #endif
 754
 755         node_len = pbqp->num_nodes;
 756
 757         init_buckets();
 758
 759         /* First simplify all edges. */
 760         for (node_index = 0; node_index < node_len; ++node_index) {
 761                 unsigned    edge_index;
 762                 pbqp_node  *node = get_node(pbqp, node_index);
 763                 pbqp_edge **edges;
 764                 unsigned    edge_len;
 765
 766                 if (!node) continue;
 767
 768                 edges = node->edges;
 769                 edge_len = pbqp_node_get_degree(node);
 770
 771                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 772                         pbqp_edge *edge = edges[edge_index];
 773
 774                         /* Simplify only once per edge. */
 775                         if (node != edge->src) continue;
 776
 777                         simplify_edge(pbqp, edge);
 778                 }
 779         }
 780
 781         #if KAPS_TIMING
 782                 ir_timer_stop(t_int_simpl);
 783                 printf("PBQP Initial simplify edges:  %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
 784         #endif
 785 }
 786
 787 num determine_solution(pbqp *pbqp)
 788 {
 789         unsigned node_index;
 790         unsigned node_len;
 791         num      solution   = 0;
 792
 793         #if KAPS_TIMING
 794                 ir_timer_t *t_det_solution = ir_timer_new();
 795                 ir_timer_reset_and_start(t_det_solution);
 796         #endif
 797
 798 #if     KAPS_DUMP
 799         FILE     *file;
 800 #endif
 801
 802         assert(pbqp);
 803
 804         (void) pbqp;
 805
 806 #if     KAPS_DUMP
 807         file = pbqp->dump_file;
 808
 809         if (file) {
 810                 dump_section(file, 1, "4. Determine Solution/Minimum");
 811                 dump_section(file, 2, "4.1. Trivial Solution");
 812         }
 813 #endif
 814
 815         /* Solve trivial nodes and calculate solution. */
 816         node_len = node_bucket_get_length(node_buckets[0]);
 817
 818 #if KAPS_STATISTIC
 819         pbqp->num_r0 = node_len;
 820 #endif
 821
 822         for (node_index = 0; node_index < node_len; ++node_index) {
 823                 pbqp_node *node = node_buckets[0][node_index];
 824                 assert(node);
 825
 826                 node->solution = vector_get_min_index(node->costs);
 827                 solution       = pbqp_add(solution,
 828                                 node->costs->entries[node->solution].data);
 829
 830 #if     KAPS_DUMP
 831                 if (file) {
 832                         fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
 833                         dump_node(file, node);
 834                 }
 835 #endif
 836         }
 837
 838 #if     KAPS_DUMP
 839         if (file) {
 840                 dump_section(file, 2, "Minimum");
 841 #if KAPS_USE_UNSIGNED
 842                 fprintf(file, "Minimum is equal to %u.", solution);
 843 #else
 844                 fprintf(file, "Minimum is equal to %lld.", solution);
 845 #endif
 846         }
 847 #endif
 848
 849         #if KAPS_TIMING
 850                 ir_timer_stop(t_det_solution);
 851                 printf("PBQP Determine Solution:      %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
 852         #endif
 853
 854         return solution;
 855 }
 856
 857 static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 858 {
 859         pbqp_edge   *edge;
 860         pbqp_node   *other;
 861         pbqp_matrix *mat;
 862         vector      *vec;
 863         int          is_src;
 864
 865         assert(pbqp);
 866         assert(node);
 867
 868         (void) pbqp;
 869
 870         edge = node->edges[0];
 871         mat = edge->costs;
 872         is_src = edge->src == node;
 873         vec = node->costs;
 874
 875         if (is_src) {
 876                 other = edge->tgt;
 877                 assert(other);
 878
 879                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
 880         } else {
 881                 other = edge->src;
 882                 assert(other);
 883
 884                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
 885         }
 886
 887 #if     KAPS_DUMP
 888         if (pbqp->dump_file) {
 889                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 890         }
 891 #endif
 892 }
 893
 894 static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
 895 {
 896         pbqp_edge   *src_edge   = node->edges[0];
 897         pbqp_edge   *tgt_edge   = node->edges[1];
 898         int          src_is_src = src_edge->src == node;
 899         int          tgt_is_src = tgt_edge->src == node;
 900         pbqp_matrix *src_mat;
 901         pbqp_matrix *tgt_mat;
 902         pbqp_node   *src_node;
 903         pbqp_node   *tgt_node;
 904         vector      *vec;
 905         vector      *node_vec;
 906         unsigned     col_index;
 907         unsigned     row_index;
 908
 909         assert(pbqp);
 910
 911         if (src_is_src) {
 912                 src_node = src_edge->tgt;
 913         } else {
 914                 src_node = src_edge->src;
 915         }
 916
 917         if (tgt_is_src) {
 918                 tgt_node = tgt_edge->tgt;
 919         } else {
 920                 tgt_node = tgt_edge->src;
 921         }
 922
 923         /* Swap nodes if necessary. */
 924         if (tgt_node->index < src_node->index) {
 925                 pbqp_node *tmp_node;
 926                 pbqp_edge *tmp_edge;
 927
 928                 tmp_node = src_node;
 929                 src_node = tgt_node;
 930                 tgt_node = tmp_node;
 931
 932                 tmp_edge = src_edge;
 933                 src_edge = tgt_edge;
 934                 tgt_edge = tmp_edge;
 935
 936                 src_is_src = src_edge->src == node;
 937                 tgt_is_src = tgt_edge->src == node;
 938         }
 939
 940         src_mat = src_edge->costs;
 941         tgt_mat = tgt_edge->costs;
 942
 943         node_vec = node->costs;
 944
 945         row_index = src_node->solution;
 946         col_index = tgt_node->solution;
 947
 948         vec = vector_copy(pbqp, node_vec);
 949
 950         if (src_is_src) {
 951                 vector_add_matrix_col(vec, src_mat, row_index);
 952         } else {
 953                 vector_add_matrix_row(vec, src_mat, row_index);
 954         }
 955
 956         if (tgt_is_src) {
 957                 vector_add_matrix_col(vec, tgt_mat, col_index);
 958         } else {
 959                 vector_add_matrix_row(vec, tgt_mat, col_index);
 960         }
 961
 962         node->solution = vector_get_min_index(vec);
 963
 964 #if     KAPS_DUMP
 965         if (pbqp->dump_file) {
 966                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 967         }
 968 #endif
 969
 970         obstack_free(&pbqp->obstack, vec);
 971 }
 972
 973 void back_propagate(pbqp *pbqp)
 974 {
 975         unsigned node_index;
 976         unsigned node_len   = node_bucket_get_length(reduced_bucket);
 977
 978         assert(pbqp);
 979
 980 #if     KAPS_DUMP
 981         if (pbqp->dump_file) {
 982                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 983         }
 984 #endif
 985
 986         for (node_index = node_len; node_index > 0; --node_index) {
 987                 pbqp_node *node = reduced_bucket[node_index - 1];
 988
 989                 switch (pbqp_node_get_degree(node)) {
 990                         case 1:
 991                                 back_propagate_RI(pbqp, node);
 992                                 break;
 993                         case 2:
 994                                 back_propagate_RII(pbqp, node);
 995                                 break;
 996                         default:
 997                                 panic("Only nodes with degree one or two should be in this bucket");
 998                                 break;
 999                 }
1000         }
1001 }
1002
1003 void apply_edge(pbqp *pbqp)
1004 {
1005         pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
1006
1007         simplify_edge(pbqp, edge);
1008 }
1009
1010 void apply_RI(pbqp *pbqp)
1011 {
1012         pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
1013         pbqp_edge   *edge       = node->edges[0];
1014         pbqp_matrix *mat        = edge->costs;
1015         int          is_src     = edge->src == node;
1016         pbqp_node   *other_node;
1017
1018         (void ) pbqp;
1019         assert(pbqp_node_get_degree(node) == 1);
1020
1021         if (is_src) {
1022                 other_node = edge->tgt;
1023         } else {
1024                 other_node = edge->src;
1025         }
1026
1027 #if     KAPS_DUMP
1028         if (pbqp->dump_file) {
1029                 char     txt[100];
1030                 sprintf(txt, "RI-Reduction of Node n%d", node->index);
1031                 dump_section(pbqp->dump_file, 2, txt);
1032                 pbqp_dump_graph(pbqp);
1033                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
1034                 dump_node(pbqp->dump_file, node);
1035                 dump_node(pbqp->dump_file, other_node);
1036                 dump_edge(pbqp->dump_file, edge);
1037         }
1038 #endif
1039
1040         if (is_src) {
1041                 pbqp_matrix_add_to_all_cols(mat, node->costs);
1042                 normalize_towards_target(edge);
1043         } else {
1044                 pbqp_matrix_add_to_all_rows(mat, node->costs);
1045                 normalize_towards_source(edge);
1046         }
1047         disconnect_edge(other_node, edge);
1048
1049 #if     KAPS_DUMP
1050         if (pbqp->dump_file) {
1051                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1052                 dump_node(pbqp->dump_file, other_node);
1053         }
1054 #endif
1055
1056         reorder_node_after_edge_deletion(other_node);
1057
1058 #if KAPS_STATISTIC
1059         pbqp->num_r1++;
1060 #endif
1061
1062         /* Add node to back propagation list. */
1063         node_bucket_insert(&reduced_bucket, node);
1064 }
1065
1066 void apply_RII(pbqp *pbqp)
1067 {
1068         pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
1069         pbqp_edge   *src_edge   = node->edges[0];
1070         pbqp_edge   *tgt_edge   = node->edges[1];
1071         int          src_is_src = src_edge->src == node;
1072         int          tgt_is_src = tgt_edge->src == node;
1073         pbqp_matrix *src_mat;
1074         pbqp_matrix *tgt_mat;
1075         pbqp_node   *src_node;
1076         pbqp_node   *tgt_node;
1077         pbqp_matrix *mat;
1078         vector      *vec;
1079         vector      *node_vec;
1080         vector      *src_vec;
1081         vector      *tgt_vec;
1082         unsigned     col_index;
1083         unsigned     col_len;
1084         unsigned     row_index;
1085         unsigned     row_len;
1086         unsigned     node_len;
1087
1088         assert(pbqp);
1089         assert(pbqp_node_get_degree(node) == 2);
1090
1091         if (src_is_src) {
1092                 src_node = src_edge->tgt;
1093         } else {
1094                 src_node = src_edge->src;
1095         }
1096
1097         if (tgt_is_src) {
1098                 tgt_node = tgt_edge->tgt;
1099         } else {
1100                 tgt_node = tgt_edge->src;
1101         }
1102
1103         /* Swap nodes if necessary. */
1104         if (tgt_node->index < src_node->index) {
1105                 pbqp_node *tmp_node;
1106                 pbqp_edge *tmp_edge;
1107
1108                 tmp_node = src_node;
1109                 src_node = tgt_node;
1110                 tgt_node = tmp_node;
1111
1112                 tmp_edge = src_edge;
1113                 src_edge = tgt_edge;
1114                 tgt_edge = tmp_edge;
1115
1116                 src_is_src = src_edge->src == node;
1117                 tgt_is_src = tgt_edge->src == node;
1118         }
1119
1120 #if     KAPS_DUMP
1121         if (pbqp->dump_file) {
1122                 char     txt[100];
1123                 sprintf(txt, "RII-Reduction of Node n%d", node->index);
1124                 dump_section(pbqp->dump_file, 2, txt);
1125                 pbqp_dump_graph(pbqp);
1126                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
1127                 dump_node(pbqp->dump_file, src_node);
1128                 dump_edge(pbqp->dump_file, src_edge);
1129                 dump_node(pbqp->dump_file, node);
1130                 dump_edge(pbqp->dump_file, tgt_edge);
1131                 dump_node(pbqp->dump_file, tgt_node);
1132         }
1133 #endif
1134
1135         src_mat = src_edge->costs;
1136         tgt_mat = tgt_edge->costs;
1137
1138         src_vec  = src_node->costs;
1139         tgt_vec  = tgt_node->costs;
1140         node_vec = node->costs;
1141
1142         row_len  = src_vec->len;
1143         col_len  = tgt_vec->len;
1144         node_len = node_vec->len;
1145
1146         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
1147
1148         for (row_index = 0; row_index < row_len; ++row_index) {
1149                 for (col_index = 0; col_index < col_len; ++col_index) {
1150                         vec = vector_copy(pbqp, node_vec);
1151
1152                         if (src_is_src) {
1153                                 vector_add_matrix_col(vec, src_mat, row_index);
1154                         } else {
1155                                 vector_add_matrix_row(vec, src_mat, row_index);
1156                         }
1157
1158                         if (tgt_is_src) {
1159                                 vector_add_matrix_col(vec, tgt_mat, col_index);
1160                         } else {
1161                                 vector_add_matrix_row(vec, tgt_mat, col_index);
1162                         }
1163
1164                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
1165
1166                         obstack_free(&pbqp->obstack, vec);
1167                 }
1168         }
1169
1170         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
1171
1172         /* Disconnect node. */
1173         disconnect_edge(src_node, src_edge);
1174         disconnect_edge(tgt_node, tgt_edge);
1175
1176 #if KAPS_STATISTIC
1177         pbqp->num_r2++;
1178 #endif
1179
1180         /* Add node to back propagation list. */
1181         node_bucket_insert(&reduced_bucket, node);
1182
1183         if (edge == NULL) {
1184                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
1185         } else {
1186                 // matrix
1187                 pbqp_matrix_add(edge->costs, mat);
1188
1189                 /* Free local matrix. */
1190                 obstack_free(&pbqp->obstack, mat);
1191
1192                 reorder_node_after_edge_deletion(src_node);
1193                 reorder_node_after_edge_deletion(tgt_node);
1194         }
1195
1196 #if     KAPS_DUMP
1197         if (pbqp->dump_file) {
1198                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1199                 dump_edge(pbqp->dump_file, edge);
1200         }
1201 #endif
1202
1203         /* Edge has changed so we simplify it. */
1204         simplify_edge(pbqp, edge);
1205 }
1206
1207 static void select_column(pbqp_edge *edge, unsigned col_index)
1208 {
1209         pbqp_matrix    *mat;
1210         pbqp_node      *src_node;
1211         pbqp_node      *tgt_node;
1212         vector         *src_vec;
1213         vector         *tgt_vec;
1214         unsigned        src_len;
1215         unsigned        tgt_len;
1216         unsigned        src_index;
1217         unsigned        new_infinity = 0;
1218
1219         assert(edge);
1220
1221         src_node = edge->src;
1222         tgt_node = edge->tgt;
1223         assert(src_node);
1224         assert(tgt_node);
1225
1226         src_vec = src_node->costs;
1227         tgt_vec = tgt_node->costs;
1228         assert(src_vec);
1229         assert(tgt_vec);
1230
1231         src_len = src_vec->len;
1232         tgt_len = tgt_vec->len;
1233         assert(src_len > 0);
1234         assert(tgt_len > 0);
1235
1236         mat = edge->costs;
1237         assert(mat);
1238
1239         for (src_index = 0; src_index < src_len; ++src_index) {
1240                 num elem = mat->entries[src_index * tgt_len + col_index];
1241
1242                 if (elem != 0) {
1243                         if (elem == INF_COSTS && src_vec->entries[src_index].data != INF_COSTS)
1244                                 new_infinity = 1;
1245
1246                         src_vec->entries[src_index].data = pbqp_add(
1247                                         src_vec->entries[src_index].data, elem);
1248                 }
1249         }
1250
1251         if (new_infinity) {
1252                 unsigned edge_index;
1253                 unsigned edge_len = pbqp_node_get_degree(src_node);
1254
1255                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
1256                         pbqp_edge *edge_candidate = src_node->edges[edge_index];
1257
1258                         if (edge_candidate != edge) {
1259                                 insert_into_edge_bucket(edge_candidate);
1260                         }
1261                 }
1262         }
1263
1264         delete_edge(edge);
1265 }
1266
1267 static void select_row(pbqp_edge *edge, unsigned row_index)
1268 {
1269         pbqp_matrix    *mat;
1270         pbqp_node      *src_node;
1271         pbqp_node      *tgt_node;
1272         vector         *tgt_vec;
1273         unsigned        tgt_len;
1274         unsigned        tgt_index;
1275         unsigned        new_infinity = 0;
1276
1277         assert(edge);
1278
1279         src_node = edge->src;
1280         tgt_node = edge->tgt;
1281         assert(tgt_node);
1282
1283         tgt_vec = tgt_node->costs;
1284         assert(tgt_vec);
1285
1286         tgt_len = tgt_vec->len;
1287         assert(tgt_len > 0);
1288
1289         mat = edge->costs;
1290         assert(mat);
1291
1292         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
1293                 num elem = mat->entries[row_index * tgt_len + tgt_index];
1294
1295                 if (elem != 0) {
1296                         if (elem == INF_COSTS && tgt_vec->entries[tgt_index].data != INF_COSTS)
1297                                 new_infinity = 1;
1298
1299                         tgt_vec->entries[tgt_index].data = pbqp_add(
1300                                         tgt_vec->entries[tgt_index].data, elem);
1301                 }
1302         }
1303
1304         if (new_infinity) {
1305                 unsigned edge_index;
1306                 unsigned edge_len = pbqp_node_get_degree(tgt_node);
1307
1308                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
1309                         pbqp_edge *edge_candidate = tgt_node->edges[edge_index];
1310
1311                         if (edge_candidate != edge) {
1312                                 insert_into_edge_bucket(edge_candidate);
1313                         }
1314                 }
1315         }
1316
1317         delete_edge(edge);
1318 }
1319
1320 void select_alternative(pbqp_node *node, unsigned selected_index)
1321 {
1322         unsigned  edge_index;
1323         unsigned  node_index;
1324         unsigned  node_len;
1325         vector   *node_vec;
1326         unsigned  max_degree = pbqp_node_get_degree(node);
1327
1328         assert(node);
1329         node->solution = selected_index;
1330         node_vec = node->costs;
1331         node_len = node_vec->len;
1332         assert(selected_index < node_len);
1333
1334         /* Set all other costs to infinity. */
1335         for (node_index = 0; node_index < node_len; ++node_index) {
1336                 if (node_index != selected_index) {
1337                         node_vec->entries[node_index].data = INF_COSTS;
1338                 }
1339         }
1340
1341         /* Select corresponding row/column for incident edges. */
1342         for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1343                 pbqp_edge *edge = node->edges[edge_index];
1344
1345                 if (edge->src == node)
1346                         select_row(edge, selected_index);
1347                 else
1348                         select_column(edge, selected_index);
1349         }
1350 }
1351
1352 pbqp_node *get_node_with_max_degree(void)
1353 {
1354         pbqp_node  **bucket       = node_buckets[3];
1355         unsigned     bucket_len   = node_bucket_get_length(bucket);
1356         unsigned     bucket_index;
1357         unsigned     max_degree   = 0;
1358         pbqp_node   *result       = NULL;
1359
1360         for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
1361                 pbqp_node *candidate = bucket[bucket_index];
1362                 unsigned   degree    = pbqp_node_get_degree(candidate);
1363
1364                 if (degree > max_degree) {
1365                         result = candidate;
1366                         max_degree = degree;
1367                 }
1368         }
1369
1370         return result;
1371 }
1372
1373 unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node)
1374 {
1375         pbqp_edge   *edge;
1376         vector      *node_vec;
1377         vector      *vec;
1378         pbqp_matrix *mat;
1379         unsigned     edge_index;
1380         unsigned     max_degree;
1381         unsigned     node_index;
1382         unsigned     node_len;
1383         unsigned     min_index    = 0;
1384         num          min          = INF_COSTS;
1385         int          is_src;
1386
1387         assert(pbqp);
1388         assert(node);
1389         node_vec   = node->costs;
1390         node_len   = node_vec->len;
1391         max_degree = pbqp_node_get_degree(node);
1392
1393         for (node_index = 0; node_index < node_len; ++node_index) {
1394                 num value = node_vec->entries[node_index].data;
1395
1396                 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1397                         edge   = node->edges[edge_index];
1398                         mat    = edge->costs;
1399                         is_src = edge->src == node;
1400
1401                         if (is_src) {
1402                                 vec = vector_copy(pbqp, edge->tgt->costs);
1403                                 vector_add_matrix_row(vec, mat, node_index);
1404                         } else {
1405                                 vec = vector_copy(pbqp, edge->src->costs);
1406                                 vector_add_matrix_col(vec, mat, node_index);
1407                         }
1408
1409                         value = pbqp_add(value, vector_get_min(vec));
1410
1411                         obstack_free(&pbqp->obstack, vec);
1412                 }
1413
1414                 if (value < min) {
1415                         min = value;
1416                         min_index = node_index;
1417                 }
1418         }
1419
1420         return min_index;
1421 }
1422
1423 int node_is_reduced(pbqp_node *node)
1424 {
1425         if (!reduced_bucket) return 0;
1426
1427         if (pbqp_node_get_degree(node) == 0) return 1;
1428
1429         return node_bucket_contains(reduced_bucket, node);
1430 }