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