nsz Git - libfirm/blob - optimal.c

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