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