nsz Git - libfirm/blob - optimal.c

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