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