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