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