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