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