nsz Git - libfirm/blob - heuristical.c

   1 #include "adt/array.h"
   2 #include "assert.h"
   3 #include "error.h"
   4
   5 #include "heuristical.h"
   6 #include "html_dumper.h"
   7 #include "kaps.h"
   8 #include "matrix.h"
   9 #include "pbqp_edge.h"
  10 #include "pbqp_edge_t.h"
  11 #include "pbqp_node.h"
  12 #include "pbqp_node_t.h"
  13 #include "vector.h"
  14
  15 static pbqp_edge **edge_bucket;
  16 static pbqp_node **node_buckets[4];
  17 static pbqp_node **reduced_bucket = NULL;
  18 static int         buckets_filled = 0;
  19
  20 static void init_buckets(void)
  21 {
  22         int i;
  23
  24         edge_bucket = NEW_ARR_F(pbqp_edge *, 0);
  25         reduced_bucket = NEW_ARR_F(pbqp_node *, 0);
  26
  27         for (i = 0; i < 4; ++i) {
  28                 node_buckets[i] = NEW_ARR_F(pbqp_node *, 0);
  29         }
  30 }
  31
  32 static void free_buckets(void)
  33 {
  34         int i;
  35
  36         for (i = 0; i < 4; ++i) {
  37                 DEL_ARR_F(node_buckets[i]);
  38         }
  39
  40         DEL_ARR_F(edge_bucket);
  41         DEL_ARR_F(reduced_bucket);
  42
  43         buckets_filled = 0;
  44 }
  45
  46 static void fill_node_buckets(pbqp *pbqp)
  47 {
  48         unsigned node_index;
  49         unsigned node_len;
  50
  51         assert(pbqp);
  52         node_len = pbqp->num_nodes;
  53
  54         for (node_index = 0; node_index < node_len; ++node_index) {
  55                 unsigned   arity;
  56                 pbqp_node *node = get_node(pbqp, node_index);
  57
  58                 if (!node) continue;
  59
  60                 arity = ARR_LEN(node->edges);
  61
  62                 /* We have only one bucket for nodes with arity >= 3. */
  63                 if (arity > 3) {
  64                         arity = 3;
  65                 }
  66
  67                 node->bucket_index = ARR_LEN(node_buckets[arity]);
  68
  69                 ARR_APP1(pbqp_node *, node_buckets[arity], node);
  70         }
  71
  72         buckets_filled = 1;
  73 }
  74
  75 static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge)
  76 {
  77         pbqp_matrix    *mat;
  78         pbqp_node      *src_node;
  79         pbqp_node      *tgt_node;
  80         vector         *src_vec;
  81         vector         *tgt_vec;
  82         int             src_len;
  83         int             tgt_len;
  84         int             src_index;
  85
  86         assert(pbqp);
  87         assert(edge);
  88
  89         src_node = edge->src;
  90         tgt_node = edge->tgt;
  91         assert(src_node);
  92         assert(tgt_node);
  93
  94         src_vec = src_node->costs;
  95         tgt_vec = tgt_node->costs;
  96         assert(src_vec);
  97         assert(tgt_vec);
  98
  99         src_len = src_vec->len;
 100         tgt_len = tgt_vec->len;
 101         assert(src_len > 0);
 102         assert(tgt_len > 0);
 103
 104         mat = edge->costs;
 105         assert(mat);
 106
 107         /* Normalize towards source node. */
 108         for (src_index = 0; src_index < src_len; ++src_index) {
 109                 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
 110
 111                 if (min != 0) {
 112                         pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
 113                         src_vec->entries[src_index].data = pbqp_add(
 114                                         src_vec->entries[src_index].data, min);
 115
 116                         // TODO add to edge_list if inf
 117                 }
 118         }
 119 }
 120
 121 static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge)
 122 {
 123         pbqp_matrix    *mat;
 124         pbqp_node      *src_node;
 125         pbqp_node      *tgt_node;
 126         vector         *src_vec;
 127         vector         *tgt_vec;
 128         int             src_len;
 129         int             tgt_len;
 130         int             tgt_index;
 131
 132         assert(pbqp);
 133         assert(edge);
 134
 135         src_node = edge->src;
 136         tgt_node = edge->tgt;
 137         assert(src_node);
 138         assert(tgt_node);
 139
 140         src_vec = src_node->costs;
 141         tgt_vec = tgt_node->costs;
 142         assert(src_vec);
 143         assert(tgt_vec);
 144
 145         src_len = src_vec->len;
 146         tgt_len = tgt_vec->len;
 147         assert(src_len > 0);
 148         assert(tgt_len > 0);
 149
 150         mat = edge->costs;
 151         assert(mat);
 152
 153         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 154                 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 155
 156                 if (min != 0) {
 157                         pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
 158                         tgt_vec->entries[tgt_index].data = pbqp_add(
 159                                         tgt_vec->entries[tgt_index].data, min);
 160
 161                         // TODO add to edge_list if inf
 162                 }
 163         }
 164 }
 165
 166 static void reorder_node(pbqp_node *node)
 167 {
 168         unsigned    arity;
 169         unsigned    old_arity;
 170         unsigned    old_bucket_len;
 171         unsigned    old_bucket_index;
 172         pbqp_node **old_bucket;
 173         pbqp_node  *other;
 174
 175         if (!buckets_filled) return;
 176
 177         assert(node);
 178
 179         arity = ARR_LEN(node->edges);
 180
 181         /* Same bucket as before */
 182         if (arity > 2) return;
 183
 184         /* Assume node lost one incident edge. */
 185         old_arity        = arity + 1;
 186         old_bucket       = node_buckets[old_arity];
 187         old_bucket_len   = ARR_LEN(old_bucket);
 188         old_bucket_index = node->bucket_index;
 189
 190         if (old_bucket_len <= old_bucket_index ||
 191             old_bucket[old_bucket_index] != node) {
 192                 /* Old arity is new arity, so we have nothing to do. */
 193                 assert(old_bucket_index < ARR_LEN(node_buckets[arity]) &&
 194                        node_buckets[arity][old_bucket_index] == node);
 195                 return;
 196         }
 197
 198         assert(old_bucket[old_bucket_index] == node);
 199
 200         /* Delete node from old bucket... */
 201         other                        = old_bucket[old_bucket_len - 1];
 202         other->bucket_index          = old_bucket_index;
 203         old_bucket[old_bucket_index] = other;
 204         ARR_SHRINKLEN(node_buckets[old_arity], old_bucket_len - 1);
 205
 206         /* ..and add to new one. */
 207         node->bucket_index = ARR_LEN(node_buckets[arity]);
 208         ARR_APP1(pbqp_node*, node_buckets[arity], node);
 209 }
 210
 211 static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 212 {
 213         pbqp_matrix    *mat;
 214         pbqp_node      *src_node;
 215         pbqp_node      *tgt_node;
 216         vector         *src_vec;
 217         vector         *tgt_vec;
 218         int             src_len;
 219         int             tgt_len;
 220
 221         assert(pbqp);
 222         assert(edge);
 223
 224         src_node = edge->src;
 225         tgt_node = edge->tgt;
 226         assert(src_node);
 227         assert(tgt_node);
 228
 229         if (pbqp->dump_file) {
 230                 char txt[100];
 231                 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
 232                 dump_section(pbqp->dump_file, 3, txt);
 233         }
 234
 235         src_vec = src_node->costs;
 236         tgt_vec = tgt_node->costs;
 237         assert(src_vec);
 238         assert(tgt_vec);
 239
 240         src_len = src_vec->len;
 241         tgt_len = tgt_vec->len;
 242         assert(src_len > 0);
 243         assert(tgt_len > 0);
 244
 245         mat = edge->costs;
 246         assert(mat);
 247
 248         if (pbqp->dump_file) {
 249                 fputs("Input:<br>\n", pbqp->dump_file);
 250                 dump_simplifyedge(pbqp, edge);
 251         }
 252
 253         normalize_towards_source(pbqp, edge);
 254         normalize_towards_target(pbqp, edge);
 255
 256         if (pbqp->dump_file) {
 257                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 258                 dump_simplifyedge(pbqp, edge);
 259         }
 260
 261         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 262                 if (pbqp->dump_file) {
 263                         fputs("edge has been eliminated<br>\n", pbqp->dump_file);
 264                 }
 265
 266                 delete_edge(edge);
 267                 reorder_node(src_node);
 268                 reorder_node(tgt_node);
 269         }
 270 }
 271
 272 void solve_pbqp_heuristical(pbqp *pbqp)
 273 {
 274         unsigned node_index;
 275         unsigned node_len;
 276
 277         assert(pbqp);
 278
 279         if (pbqp->dump_file) {
 280                 pbqp_dump_input(pbqp);
 281                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 282         }
 283
 284         node_len = pbqp->num_nodes;
 285
 286         init_buckets();
 287
 288         /* First simplify all edges. */
 289         for (node_index = 0; node_index < node_len; ++node_index) {
 290                 unsigned    edge_index;
 291                 pbqp_node  *node = get_node(pbqp, node_index);
 292                 pbqp_edge **edges;
 293                 unsigned    edge_len;
 294
 295                 if (!node) continue;
 296
 297                 edges = node->edges;
 298                 edge_len = ARR_LEN(edges);
 299
 300                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 301                         pbqp_edge *edge = edges[edge_index];
 302
 303                         /* Simplify only once per edge. */
 304                         if (node != edge->src) continue;
 305
 306                         simplify_edge(pbqp, edge);
 307                 }
 308         }
 309
 310         /* Put node into bucket representing their arity. */
 311         fill_node_buckets(pbqp);
 312
 313         for (;;) {
 314                 if (ARR_LEN(edge_bucket) > 0) {
 315                         panic("Please implement edge simplification");
 316                 } else if (ARR_LEN(node_buckets[1]) > 0) {
 317                         apply_RI(pbqp);
 318                 } else if (ARR_LEN(node_buckets[2]) > 0) {
 319                         apply_RII(pbqp);
 320                 } else if (ARR_LEN(node_buckets[3]) > 0) {
 321                         panic("Please implement RN simplification");
 322                 } else {
 323                         break;
 324                 }
 325         }
 326
 327         if (pbqp->dump_file) {
 328                 dump_section(pbqp->dump_file, 1, "4. Determine Solution/Minimum");
 329                 dump_section(pbqp->dump_file, 2, "4.1. Trivial Solution");
 330         }
 331
 332         /* Solve trivial nodes and calculate solution. */
 333         node_len = ARR_LEN(node_buckets[0]);
 334         for (node_index = 0; node_index < node_len; ++node_index) {
 335                 pbqp_node *node = node_buckets[0][node_index];
 336                 assert(node);
 337
 338                 node->solution = vector_get_min_index(node->costs);
 339                 pbqp->solution = pbqp_add(pbqp->solution,
 340                                 node->costs->entries[node->solution].data);
 341                 if (pbqp->dump_file) {
 342                         fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 343                         dump_node(pbqp, node);
 344                 }
 345         }
 346
 347         if (pbqp->dump_file) {
 348                 dump_section(pbqp->dump_file, 2, "Minimum");
 349                 fprintf(pbqp->dump_file, "Minimum is equal to %d.", pbqp->solution);
 350                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 351         }
 352
 353         /* Solve reduced nodes. */
 354         node_len = ARR_LEN(reduced_bucket);
 355         for (node_index = node_len; node_index > 0; --node_index) {
 356                 pbqp_node *node = reduced_bucket[node_index - 1];
 357                 assert(node);
 358
 359                 switch (ARR_LEN(node->edges)) {
 360                         case 1:
 361                                 back_propagate_RI(pbqp, node);
 362                                 break;
 363                         case 2:
 364                                 back_propagate_RII(pbqp, node);
 365                                 break;
 366                         default:
 367                                 panic("Only nodes with degree one or two should be in this bucket");
 368                                 break;
 369                 }
 370         }
 371
 372         free_buckets();
 373 }
 374
 375 void apply_RI(pbqp *pbqp)
 376 {
 377         pbqp_node  **bucket     = node_buckets[1];
 378         unsigned     bucket_len = ARR_LEN(bucket);
 379         pbqp_node   *node       = bucket[bucket_len - 1];
 380         pbqp_edge   *edge       = node->edges[0];
 381         pbqp_matrix *mat        = edge->costs;
 382         int          is_src     = edge->src == node;
 383         pbqp_node   *other_node;
 384
 385         if (is_src) {
 386                 other_node = edge->tgt;
 387         } else {
 388                 other_node = edge->src;
 389         }
 390
 391         if (pbqp->dump_file) {
 392                 char     txt[100];
 393                 sprintf(txt, "RI-Reduktion of Node n%d", node->index);
 394                 dump_section(pbqp->dump_file, 2, txt);
 395                 pbqp_dump_graph(pbqp);
 396                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 397                 dump_node(pbqp, node);
 398                 dump_node(pbqp, other_node);
 399                 dump_edge(pbqp, edge);
 400         }
 401
 402         if (is_src) {
 403                 pbqp_matrix_add_to_all_cols(mat, node->costs);
 404                 normalize_towards_target(pbqp, edge);
 405         } else {
 406                 pbqp_matrix_add_to_all_rows(mat, node->costs);
 407                 normalize_towards_source(pbqp, edge);
 408         }
 409         disconnect_edge(other_node, edge);
 410
 411         if (pbqp->dump_file) {
 412                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 413                 dump_node(pbqp, other_node);
 414         }
 415
 416         /* Remove node from bucket... */
 417         ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
 418         reorder_node(other_node);
 419
 420         /* ...and add it to back propagation list. */
 421         node->bucket_index = ARR_LEN(reduced_bucket);
 422         ARR_APP1(pbqp_node *, reduced_bucket, node);
 423 }
 424
 425 void apply_RII(pbqp *pbqp)
 426 {
 427         pbqp_node  **bucket     = node_buckets[2];
 428         unsigned     bucket_len = ARR_LEN(bucket);
 429         pbqp_node   *node       = bucket[bucket_len - 1];
 430         pbqp_edge   *src_edge   = node->edges[0];
 431         pbqp_edge   *tgt_edge   = node->edges[1];
 432         int          src_is_src = src_edge->src == node;
 433         int          tgt_is_src = tgt_edge->src == node;
 434         pbqp_matrix *src_mat;
 435         pbqp_matrix *tgt_mat;
 436         pbqp_node   *src_node;
 437         pbqp_node   *tgt_node;
 438         pbqp_matrix *mat;
 439         vector      *vec;
 440         vector      *node_vec;
 441         vector      *src_vec;
 442         vector      *tgt_vec;
 443         unsigned     col_index;
 444         unsigned     col_len;
 445         unsigned     row_index;
 446         unsigned     row_len;
 447         unsigned     node_len;
 448
 449         assert(pbqp);
 450
 451         if (src_is_src) {
 452                 src_node = src_edge->tgt;
 453         } else {
 454                 src_node = src_edge->src;
 455         }
 456
 457         if (tgt_is_src) {
 458                 tgt_node = tgt_edge->tgt;
 459         } else {
 460                 tgt_node = tgt_edge->src;
 461         }
 462
 463         /* Swap nodes if necessary. */
 464         if (tgt_node->index < src_node->index) {
 465                 pbqp_node *tmp_node;
 466                 pbqp_edge *tmp_edge;
 467
 468                 tmp_node = src_node;
 469                 src_node = tgt_node;
 470                 tgt_node = tmp_node;
 471
 472                 tmp_edge = src_edge;
 473                 src_edge = tgt_edge;
 474                 tgt_edge = tmp_edge;
 475
 476                 src_is_src = src_edge->src == node;
 477                 tgt_is_src = tgt_edge->src == node;
 478         }
 479
 480         if (pbqp->dump_file) {
 481                 char     txt[100];
 482                 sprintf(txt, "RII-Reduktion of Node n%d", node->index);
 483                 dump_section(pbqp->dump_file, 2, txt);
 484                 pbqp_dump_graph(pbqp);
 485                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 486                 dump_node(pbqp, src_node);
 487                 dump_edge(pbqp, src_edge);
 488                 dump_node(pbqp, node);
 489                 dump_edge(pbqp, tgt_edge);
 490                 dump_node(pbqp, tgt_node);
 491         }
 492
 493         src_mat = src_edge->costs;
 494         tgt_mat = tgt_edge->costs;
 495
 496         src_vec  = src_node->costs;
 497         tgt_vec  = tgt_node->costs;
 498         node_vec = node->costs;
 499
 500         row_len  = src_vec->len;
 501         col_len  = tgt_vec->len;
 502         node_len = node_vec->len;
 503
 504         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
 505
 506         for (row_index = 0; row_index < row_len; ++row_index) {
 507                 for (col_index = 0; col_index < col_len; ++col_index) {
 508                         vec = vector_copy(pbqp, node_vec);
 509
 510                         if (src_is_src) {
 511                                 vector_add_matrix_col(vec, src_mat, row_index);
 512                         } else {
 513                                 vector_add_matrix_row(vec, src_mat, row_index);
 514                         }
 515
 516                         if (tgt_is_src) {
 517                                 vector_add_matrix_col(vec, tgt_mat, col_index);
 518                         } else {
 519                                 vector_add_matrix_row(vec, tgt_mat, col_index);
 520                         }
 521
 522                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
 523
 524                         obstack_free(&pbqp->obstack, vec);
 525                 }
 526         }
 527
 528         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
 529
 530         /* Disconnect node. */
 531         disconnect_edge(src_node, src_edge);
 532         disconnect_edge(tgt_node, tgt_edge);
 533
 534         /* Remove node from bucket... */
 535         ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
 536
 537         /* ...and add it to back propagation list. */
 538         node->bucket_index = ARR_LEN(reduced_bucket);
 539         ARR_APP1(pbqp_node *, reduced_bucket, node);
 540
 541         if (edge == NULL) {
 542                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
 543         } else {
 544                 pbqp_matrix_add(edge->costs, mat);
 545
 546                 /* Free local matrix. */
 547                 obstack_free(&pbqp->obstack, mat);
 548
 549                 reorder_node(src_node);
 550                 reorder_node(tgt_node);
 551         }
 552
 553         if (pbqp->dump_file) {
 554                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 555                 dump_edge(pbqp, edge);
 556         }
 557
 558         /* Edge has changed so we simplify it. */
 559         simplify_edge(pbqp, edge);
 560 }
 561
 562 void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 563 {
 564         pbqp_edge   *edge;
 565         pbqp_node   *other;
 566         pbqp_matrix *mat;
 567         vector      *vec;
 568         int          is_src;
 569
 570         assert(pbqp);
 571         assert(node);
 572
 573         edge = node->edges[0];
 574         mat = edge->costs;
 575         is_src = edge->src == node;
 576         vec = node->costs;
 577
 578         if (is_src) {
 579                 other = edge->tgt;
 580                 assert(other);
 581                 vector_add_matrix_col(vec, mat, other->solution);
 582         } else {
 583                 other = edge->src;
 584                 assert(other);
 585                 vector_add_matrix_row(vec, mat, other->solution);
 586         }
 587
 588         node->solution = vector_get_min_index(vec);
 589         if (pbqp->dump_file) {
 590                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 591         }
 592 }
 593
 594 void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
 595 {
 596         pbqp_edge   *src_edge   = node->edges[0];
 597         pbqp_edge   *tgt_edge   = node->edges[1];
 598         int          src_is_src = src_edge->src == node;
 599         int          tgt_is_src = tgt_edge->src == node;
 600         pbqp_matrix *src_mat;
 601         pbqp_matrix *tgt_mat;
 602         pbqp_node   *src_node;
 603         pbqp_node   *tgt_node;
 604         vector      *vec;
 605         vector      *node_vec;
 606         unsigned     col_index;
 607         unsigned     row_index;
 608
 609         assert(pbqp);
 610
 611         if (src_is_src) {
 612                 src_node = src_edge->tgt;
 613         } else {
 614                 src_node = src_edge->src;
 615         }
 616
 617         if (tgt_is_src) {
 618                 tgt_node = tgt_edge->tgt;
 619         } else {
 620                 tgt_node = tgt_edge->src;
 621         }
 622
 623         /* Swap nodes if necessary. */
 624         if (tgt_node->index < src_node->index) {
 625                 pbqp_node *tmp_node;
 626                 pbqp_edge *tmp_edge;
 627
 628                 tmp_node = src_node;
 629                 src_node = tgt_node;
 630                 tgt_node = tmp_node;
 631
 632                 tmp_edge = src_edge;
 633                 src_edge = tgt_edge;
 634                 tgt_edge = tmp_edge;
 635
 636                 src_is_src = src_edge->src == node;
 637                 tgt_is_src = tgt_edge->src == node;
 638         }
 639
 640         src_mat = src_edge->costs;
 641         tgt_mat = tgt_edge->costs;
 642
 643         node_vec = node->costs;
 644
 645         row_index = src_node->solution;
 646         col_index = tgt_node->solution;
 647
 648         vec = vector_copy(pbqp, node_vec);
 649
 650         if (src_is_src) {
 651                 vector_add_matrix_col(vec, src_mat, row_index);
 652         } else {
 653                 vector_add_matrix_row(vec, src_mat, row_index);
 654         }
 655
 656         if (tgt_is_src) {
 657                 vector_add_matrix_col(vec, tgt_mat, col_index);
 658         } else {
 659                 vector_add_matrix_row(vec, tgt_mat, col_index);
 660         }
 661
 662         node->solution = vector_get_min_index(vec);
 663         if (pbqp->dump_file) {
 664                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 665         }
 666
 667         obstack_free(&pbqp->obstack, vec);
 668 }
 669
 670 int node_is_reduced(pbqp_node *node)
 671 {
 672         if (!reduced_bucket) return 0;
 673
 674         assert(node);
 675         if (ARR_LEN(node->edges) == 0) return 1;
 676
 677         unsigned bucket_length = ARR_LEN(reduced_bucket);
 678         unsigned bucket_index  = node->bucket_index;
 679
 680         return bucket_index < bucket_length && reduced_bucket[bucket_index] == node;
 681 }