nsz Git - libfirm/blob - optimal.c

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