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