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