nsz Git - libfirm/blob - ir/kaps/optimal.c

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