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;
  18
  19 static void init_buckets(void)
  20 {
  21         int i;
  22
  23         edge_bucket = NEW_ARR_F(pbqp_edge *, 0);
  24         reduced_bucket = NEW_ARR_F(pbqp_node *, 0);
  25
  26         for (i = 0; i < 4; ++i) {
  27                 node_buckets[i] = NEW_ARR_F(pbqp_node *, 0);
  28         }
  29 }
  30
  31 static void fill_node_buckets(pbqp *pbqp)
  32 {
  33         unsigned node_index;
  34         unsigned node_len;
  35
  36         assert(pbqp);
  37         node_len = pbqp->num_nodes;
  38
  39         for (node_index = 0; node_index < node_len; ++node_index) {
  40                 unsigned   arity;
  41                 pbqp_node *node = get_node(pbqp, node_index);
  42
  43                 if (!node) continue;
  44
  45                 arity = ARR_LEN(node->edges);
  46
  47                 /* We have only one bucket for nodes with arity >= 3. */
  48                 if (arity > 3) {
  49                         arity = 3;
  50                 }
  51
  52                 node->bucket_index = ARR_LEN(node_buckets[arity]);
  53
  54                 ARR_APP1(pbqp_node *, node_buckets[arity], node);
  55         }
  56 }
  57
  58 static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge)
  59 {
  60         pbqp_matrix    *mat;
  61         pbqp_node      *src_node;
  62         pbqp_node      *tgt_node;
  63         vector         *src_vec;
  64         vector         *tgt_vec;
  65         int             src_len;
  66         int             tgt_len;
  67         int             src_index;
  68
  69         assert(pbqp);
  70         assert(edge);
  71
  72         src_node = edge->src;
  73         tgt_node = edge->tgt;
  74         assert(src_node);
  75         assert(tgt_node);
  76
  77         src_vec = src_node->costs;
  78         tgt_vec = tgt_node->costs;
  79         assert(src_vec);
  80         assert(tgt_vec);
  81
  82         src_len = src_vec->len;
  83         tgt_len = tgt_vec->len;
  84         assert(src_len > 0);
  85         assert(tgt_len > 0);
  86
  87         mat = edge->costs;
  88         assert(mat);
  89
  90         /* Normalize towards source node. */
  91         for (src_index = 0; src_index < src_len; ++src_index) {
  92                 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
  93
  94                 if (min != 0) {
  95                         pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
  96                         src_vec->entries[src_index].data += min;
  97
  98                         // TODO add to edge_list if inf
  99                 }
 100         }
 101 }
 102
 103 static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge)
 104 {
 105         pbqp_matrix    *mat;
 106         pbqp_node      *src_node;
 107         pbqp_node      *tgt_node;
 108         vector         *src_vec;
 109         vector         *tgt_vec;
 110         int             src_len;
 111         int             tgt_len;
 112         int             tgt_index;
 113
 114         assert(pbqp);
 115         assert(edge);
 116
 117         src_node = edge->src;
 118         tgt_node = edge->tgt;
 119         assert(src_node);
 120         assert(tgt_node);
 121
 122         src_vec = src_node->costs;
 123         tgt_vec = tgt_node->costs;
 124         assert(src_vec);
 125         assert(tgt_vec);
 126
 127         src_len = src_vec->len;
 128         tgt_len = tgt_vec->len;
 129         assert(src_len > 0);
 130         assert(tgt_len > 0);
 131
 132         mat = edge->costs;
 133         assert(mat);
 134
 135         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 136                 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 137
 138                 if (min != 0) {
 139                         pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
 140                         tgt_vec->entries[tgt_index].data += min;
 141
 142                         // TODO add to edge_list if inf
 143                 }
 144         }
 145 }
 146
 147 static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 148 {
 149         pbqp_matrix    *mat;
 150         pbqp_node      *src_node;
 151         pbqp_node      *tgt_node;
 152         vector         *src_vec;
 153         vector         *tgt_vec;
 154         int             src_len;
 155         int             tgt_len;
 156
 157         assert(pbqp);
 158         assert(edge);
 159
 160         src_node = edge->src;
 161         tgt_node = edge->tgt;
 162         assert(src_node);
 163         assert(tgt_node);
 164
 165         if(pbqp->dump_file) {
 166                 char txt[100];
 167                 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
 168                 dump_section(pbqp->dump_file, 3, txt);
 169         }
 170
 171         src_vec = src_node->costs;
 172         tgt_vec = tgt_node->costs;
 173         assert(src_vec);
 174         assert(tgt_vec);
 175
 176         src_len = src_vec->len;
 177         tgt_len = tgt_vec->len;
 178         assert(src_len > 0);
 179         assert(tgt_len > 0);
 180
 181         mat = edge->costs;
 182         assert(mat);
 183
 184         if (pbqp->dump_file) {
 185                 fputs("Input:<br>\n", pbqp->dump_file);
 186                 dump_simplifyedge(pbqp, edge);
 187         }
 188
 189         normalize_towards_source(pbqp, edge);
 190         normalize_towards_target(pbqp, edge);
 191
 192         if (pbqp->dump_file) {
 193                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 194                 dump_simplifyedge(pbqp, edge);
 195         }
 196
 197         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 198                 if (pbqp->dump_file) {
 199                         fputs("edge has been eliminated", pbqp->dump_file);
 200
 201                         delete_edge(edge);
 202                 }
 203         }
 204 }
 205
 206 static void reorder_node(pbqp_node *node)
 207 {
 208         unsigned arity;
 209         unsigned old_arity;
 210         unsigned old_bucket_len;
 211
 212         assert(node);
 213
 214         arity = ARR_LEN(node->edges);
 215
 216         /* Equal bucket as before */
 217         if (arity > 2) return;
 218
 219         /* Assume node lost one incident edge. */
 220         old_arity = arity + 1;
 221
 222         if (ARR_LEN(node_buckets[old_arity]) <= (int)node->bucket_index
 223                         || node_buckets[old_arity][node->bucket_index] != node) {
 224                 /* Old arity is new arity, so we have nothing to do. */
 225                 return;
 226         }
 227
 228         old_bucket_len = ARR_LEN(node_buckets[old_arity]);
 229         assert (node_buckets[old_arity][node->bucket_index] == node);
 230
 231         /* Delete node from old bucket... */
 232         node_buckets[old_arity][node->bucket_index]
 233                         = node_buckets[old_arity][old_bucket_len - 1];
 234         ARR_SHRINKLEN(node_buckets[old_arity], (int)old_bucket_len - 1);
 235
 236         /* ..and add to new one. */
 237         node->bucket_index = ARR_LEN(node_buckets[arity]);
 238         ARR_APP1(pbqp_node *, node_buckets[arity], node);
 239 }
 240
 241 void solve_pbqp_heuristical(pbqp *pbqp)
 242 {
 243         unsigned node_index;
 244         unsigned node_len;
 245
 246         assert(pbqp);
 247
 248         if (pbqp->dump_file) {
 249                 pbqp_dump_input(pbqp);
 250                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 251         }
 252
 253         node_len = pbqp->num_nodes;
 254
 255         init_buckets();
 256
 257         /* First simplify all edges. */
 258         for (node_index = 0; node_index < node_len; ++node_index) {
 259                 unsigned    edge_index;
 260                 pbqp_node  *node = get_node(pbqp, node_index);
 261                 pbqp_edge **edges;
 262                 unsigned    edge_len;
 263
 264                 if (!node) continue;
 265
 266                 edges = node->edges;
 267                 edge_len = ARR_LEN(edges);
 268
 269                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 270                         pbqp_edge *edge = edges[edge_index];
 271
 272                         /* Simplify only once per edge. */
 273                         if (node_index != edge->src->index) continue;
 274
 275                         simplify_edge(pbqp, edge);
 276                 }
 277         }
 278
 279         /* Put node into bucket representing their arity. */
 280         fill_node_buckets(pbqp);
 281
 282         for (;;) {
 283                 if (ARR_LEN(edge_bucket) > 0) {
 284                         panic("Please implement edge simplification");
 285                 } else if (ARR_LEN(node_buckets[1]) > 0) {
 286                         applyRI(pbqp);
 287                 } else if (ARR_LEN(node_buckets[2]) > 0) {
 288                         panic("Please implement RII simplification");
 289                 } else if (ARR_LEN(node_buckets[3]) > 0) {
 290                         panic("Please implement RN simplification");
 291                 } else {
 292                         break;
 293                 }
 294         }
 295
 296         if (pbqp->dump_file) {
 297                 dump_section(pbqp->dump_file, 1, "4. Determine Solution/Minimum");
 298                 dump_section(pbqp->dump_file, 2, "4.1. Trivial Solution");
 299         }
 300
 301         /* Solve trivial nodes and calculate solution. */
 302         node_len = ARR_LEN(node_buckets[0]);
 303         for (node_index = 0; node_index < node_len; ++node_index) {
 304                 pbqp_node *node = node_buckets[0][node_index];
 305                 assert(node);
 306
 307                 node->solution = vector_get_min_index(node->costs);
 308                 pbqp->solution += node->costs->entries[node->solution].data;
 309                 if (pbqp->dump_file) {
 310                         fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 311                         dump_node(pbqp, node);
 312                 }
 313         }
 314
 315         if (pbqp->dump_file) {
 316                 dump_section(pbqp->dump_file, 2, "Minimum");
 317                 fprintf(pbqp->dump_file, "Minimum is equal to %d.", pbqp->solution);
 318                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 319         }
 320
 321         /* Solve reduced nodes. */
 322         node_len = ARR_LEN(reduced_bucket);
 323         for (node_index = node_len; node_index > 0; --node_index) {
 324                 pbqp_node *node = reduced_bucket[node_index - 1];
 325                 assert(node);
 326
 327                 switch (ARR_LEN(node->edges)) {
 328                         case 1:
 329                                 back_propagate_RI(pbqp, node);
 330                                 break;
 331                         case 2:
 332                                 panic("Please implement back propagation for RII");
 333                                 break;
 334                         default:
 335                                 panic("Only nodes with degree one or two should be in this bucket");
 336                                 break;
 337                 }
 338         }
 339 }
 340
 341 void applyRI(pbqp *pbqp)
 342 {
 343         pbqp_node  **bucket     = node_buckets[1];
 344         unsigned     bucket_len = ARR_LEN(bucket);
 345         pbqp_node   *node       = bucket[bucket_len - 1];
 346         pbqp_edge   *edge       = node->edges[0];
 347         pbqp_matrix *mat        = edge->costs;
 348         int          is_src     = edge->src == node;
 349         pbqp_node   *other_node;
 350
 351         if (is_src) {
 352                 other_node = edge->tgt;
 353         } else {
 354                 other_node = edge->src;
 355         }
 356
 357         if (pbqp->dump_file) {
 358                 char     txt[100];
 359                 sprintf(txt, "RI-Reduktion of Node n%d", node->index);
 360                 dump_section(pbqp->dump_file, 2, txt);
 361                 pbqp_dump_graph(pbqp);
 362                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 363                 dump_node(pbqp, node);
 364                 dump_node(pbqp, other_node);
 365                 dump_edge(pbqp, edge);
 366         }
 367
 368         if (is_src) {
 369                 pbqp_matrix_add_to_all_cols(mat, node->costs);
 370                 normalize_towards_target(pbqp, edge);
 371         } else {
 372                 pbqp_matrix_add_to_all_rows(mat, node->costs);
 373                 normalize_towards_source(pbqp, edge);
 374         }
 375         disconnect_edge(other_node, edge);
 376
 377         if (pbqp->dump_file) {
 378                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 379                 dump_node(pbqp, other_node);
 380         }
 381
 382         /* Remove node from bucket... */
 383         ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
 384         reorder_node(other_node);
 385
 386         /* ...and add it to back propagation list. */
 387         ARR_APP1(pbqp_node *, reduced_bucket, node);
 388 }
 389
 390 void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 391 {
 392         pbqp_edge   *edge;
 393         pbqp_node   *other;
 394         pbqp_matrix *mat;
 395         vector      *vec;
 396         int          is_src;
 397
 398         assert(pbqp);
 399         assert(node);
 400
 401         edge = node->edges[0];
 402         mat = edge->costs;
 403         is_src = edge->src == node;
 404         vec = node->costs;
 405
 406         if (is_src) {
 407                 other = edge->tgt;
 408                 assert(other);
 409                 vector_add_matrix_col(vec, mat, other->solution);
 410         } else {
 411                 other = edge->src;
 412                 assert(other);
 413                 vector_add_matrix_row(vec, mat, other->solution);
 414         }
 415
 416         node->solution = vector_get_min_index(vec);
 417         if (pbqp->dump_file) {
 418                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 419         }
 420 }