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