nsz Git - libfirm/blob - optimal.c

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