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