nsz Git - libfirm/blob - ir/kaps/heuristical_co_ld.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 Karlsruhe Institute of Technology.
   4  */
   5 #include "config.h"
   6
   7 #include "adt/array.h"
   8 #include "assert.h"
   9 #include "error.h"
  10
  11 #include "bucket.h"
  12 #include "heuristical_co_ld.h"
  13 #include "optimal.h"
  14 #if KAPS_DUMP
  15 #include "html_dumper.h"
  16 #endif
  17 #include "kaps.h"
  18 #include "matrix.h"
  19 #include "pbqp_edge.h"
  20 #include "pbqp_edge_t.h"
  21 #include "pbqp_node.h"
  22 #include "pbqp_node_t.h"
  23 #include "vector.h"
  24
  25 #include "plist.h"
  26 #include "timing.h"
  27
  28 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
  29 {
  30         pbqp_edge_t   *edge;
  31         pbqp_node_t   *other;
  32         pbqp_matrix_t *mat;
  33         vector_t      *vec;
  34         int            is_src;
  35
  36         (void) pbqp;
  37
  38         edge = node->edges[0];
  39         mat = edge->costs;
  40         is_src = edge->src == node;
  41         vec = node->costs;
  42
  43         if (is_src) {
  44                 other = edge->tgt;
  45                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
  46         } else {
  47                 other = edge->src;
  48                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
  49         }
  50
  51 #if KAPS_DUMP
  52         if (pbqp->dump_file) {
  53                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
  54         }
  55 #endif
  56 }
  57
  58 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
  59 {
  60         pbqp_edge_t   *src_edge   = node->edges[0];
  61         pbqp_edge_t   *tgt_edge   = node->edges[1];
  62         int            src_is_src = src_edge->src == node;
  63         int            tgt_is_src = tgt_edge->src == node;
  64         pbqp_matrix_t *src_mat;
  65         pbqp_matrix_t *tgt_mat;
  66         pbqp_node_t   *src_node;
  67         pbqp_node_t   *tgt_node;
  68         vector_t      *vec;
  69         vector_t      *node_vec;
  70         unsigned       col_index;
  71         unsigned       row_index;
  72
  73         assert(pbqp);
  74
  75         if (src_is_src) {
  76                 src_node = src_edge->tgt;
  77         } else {
  78                 src_node = src_edge->src;
  79         }
  80
  81         if (tgt_is_src) {
  82                 tgt_node = tgt_edge->tgt;
  83         } else {
  84                 tgt_node = tgt_edge->src;
  85         }
  86
  87         /* Swap nodes if necessary. */
  88         if (tgt_node->index < src_node->index) {
  89                 pbqp_node_t *tmp_node;
  90                 pbqp_edge_t *tmp_edge;
  91
  92                 tmp_node = src_node;
  93                 src_node = tgt_node;
  94                 tgt_node = tmp_node;
  95
  96                 tmp_edge = src_edge;
  97                 src_edge = tgt_edge;
  98                 tgt_edge = tmp_edge;
  99
 100                 src_is_src = src_edge->src == node;
 101                 tgt_is_src = tgt_edge->src == node;
 102         }
 103
 104         src_mat = src_edge->costs;
 105         tgt_mat = tgt_edge->costs;
 106
 107         node_vec = node->costs;
 108
 109         row_index = src_node->solution;
 110         col_index = tgt_node->solution;
 111
 112         vec = vector_copy(pbqp, node_vec);
 113
 114         if (src_is_src) {
 115                 vector_add_matrix_col(vec, src_mat, row_index);
 116         } else {
 117                 vector_add_matrix_row(vec, src_mat, row_index);
 118         }
 119
 120         if (tgt_is_src) {
 121                 vector_add_matrix_col(vec, tgt_mat, col_index);
 122         } else {
 123                 vector_add_matrix_row(vec, tgt_mat, col_index);
 124         }
 125
 126         node->solution = vector_get_min_index(vec);
 127
 128 #if KAPS_DUMP
 129         if (pbqp->dump_file) {
 130                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 131         }
 132 #endif
 133
 134         obstack_free(&pbqp->obstack, vec);
 135 }
 136
 137 static void back_propagate_RN(pbqp_t *pbqp, pbqp_node_t *node)
 138 {
 139         vector_t    *vec        = NULL;
 140         pbqp_node_t *neighbor   = NULL;
 141         pbqp_edge_t *edge       = NULL;
 142         unsigned     edge_index = 0;
 143
 144         assert(pbqp);
 145
 146         vec = vector_copy(pbqp, node->costs);
 147
 148         for(edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
 149                 /* get neighbor node */
 150                 edge = node->edges[edge_index];
 151                 neighbor = edge->src == node ? edge->tgt : edge->src;
 152
 153                 /* node is edge src node */
 154                 if(edge->src == node)
 155                         vector_add_matrix_col(vec, edge->costs, neighbor->solution);
 156                 /* node is edge tgt node */
 157                 else
 158                         vector_add_matrix_row(vec, edge->costs, neighbor->solution);
 159         }
 160
 161         assert(vector_get_min(vec) != INF_COSTS);
 162         node->solution = vector_get_min_index(vec);
 163
 164 #if KAPS_DUMP
 165         if (pbqp->dump_file) {
 166                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 167         }
 168 #endif
 169
 170         obstack_free(&pbqp->obstack, vec);
 171 }
 172
 173 static void back_propagate_ld(pbqp_t *pbqp)
 174 {
 175         unsigned node_index;
 176         unsigned node_len   = node_bucket_get_length(reduced_bucket);
 177
 178         assert(pbqp);
 179
 180 #if KAPS_DUMP
 181         if (pbqp->dump_file) {
 182                 pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
 183         }
 184 #endif
 185
 186         for (node_index = node_len; node_index > 0; --node_index) {
 187                 pbqp_node_t *node = reduced_bucket[node_index - 1];
 188
 189                 switch (pbqp_node_get_degree(node)) {
 190                         case 1:
 191                                 back_propagate_RI(pbqp, node);
 192                                 break;
 193                         case 2:
 194                                 back_propagate_RII(pbqp, node);
 195                                 break;
 196                         default:
 197                                 back_propagate_RN(pbqp, node);
 198                                 break;
 199                 }
 200         }
 201 }
 202
 203 static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo)
 204 {
 205         pbqp_node_t *node = NULL;
 206
 207         assert(pbqp);
 208
 209         do {
 210                 /* get last element from reverse perfect elimination order */
 211                 node = (pbqp_node_t*)plist_last(rpeo)->data;
 212                 /* remove element from reverse perfect elimination order */
 213                 plist_erase(rpeo, plist_last(rpeo));
 214                 /* insert node at the beginning of rpeo so the rpeo already exits after pbqp solving */
 215                 plist_insert_front(rpeo, node);
 216         } while(node_is_reduced(node));
 217
 218         assert(pbqp_node_get_degree(node) > 2);
 219
 220         /* Check whether we can merge a neighbor into the current node. */
 221         apply_RM(pbqp, node);
 222 }
 223
 224 static void apply_RN_co_without_selection(pbqp_t *pbqp)
 225 {
 226         pbqp_node_t *node;
 227         unsigned     edge_index;
 228
 229         assert(pbqp);
 230
 231         node        = merged_node;
 232         merged_node = NULL;
 233
 234         if (node_is_reduced(node))
 235                 return;
 236
 237 #if KAPS_DUMP
 238         if (pbqp->dump_file) {
 239                 char     txt[100];
 240                 sprintf(txt, "RN-Reduction of Node n%d", node->index);
 241                 pbqp_dump_section(pbqp->dump_file, 2, txt);
 242                 pbqp_dump_graph(pbqp);
 243         }
 244 #endif
 245
 246         /* Disconnect neighbor nodes */
 247         for(edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
 248                 pbqp_edge_t *edge;
 249                 pbqp_node_t *neighbor;
 250
 251                 /* get neighbor node */
 252                 edge = node->edges[edge_index];
 253
 254                 neighbor = edge->src == node ? edge->tgt : edge->src;
 255
 256                 assert(neighbor != node);
 257
 258                 if(!is_connected(neighbor, edge))
 259                         continue;
 260
 261                 disconnect_edge(neighbor, edge);
 262                 reorder_node_after_edge_deletion(neighbor);
 263         }
 264
 265         /* Remove node from old bucket */
 266         node_bucket_remove(&node_buckets[3], node);
 267
 268         /* Add node to back propagation list. */
 269         node_bucket_insert(&reduced_bucket, node);
 270 }
 271
 272 static void apply_heuristic_reductions_co(pbqp_t *pbqp, plist_t *rpeo)
 273 {
 274         #if KAPS_TIMING
 275                 /* create timers */
 276                 ir_timer_t *t_edge = ir_timer_new();
 277                 ir_timer_t *t_r1   = ir_timer_new();
 278                 ir_timer_t *t_r2   = ir_timer_new();
 279                 ir_timer_t *t_rn   = ir_timer_new();
 280         #endif
 281
 282         for (;;) {
 283                 if (edge_bucket_get_length(edge_bucket) > 0) {
 284                         #if KAPS_TIMING
 285                                 ir_timer_start(t_edge);
 286                         #endif
 287
 288                         apply_edge(pbqp);
 289
 290                         #if KAPS_TIMING
 291                                 ir_timer_stop(t_edge);
 292                         #endif
 293                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
 294                         #if KAPS_TIMING
 295                                 ir_timer_start(t_r1);
 296                         #endif
 297
 298                         apply_RI(pbqp);
 299
 300                         #if KAPS_TIMING
 301                                 ir_timer_stop(t_r1);
 302                         #endif
 303                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
 304                         #if KAPS_TIMING
 305                                 ir_timer_start(t_r2);
 306                         #endif
 307
 308                         apply_RII(pbqp);
 309
 310                         #if KAPS_TIMING
 311                                 ir_timer_stop(t_r2);
 312                         #endif
 313                 } else if (merged_node != NULL) {
 314                         #if KAPS_TIMING
 315                                 ir_timer_start(t_rn);
 316                         #endif
 317
 318                         apply_RN_co_without_selection(pbqp);
 319
 320                         #if KAPS_TIMING
 321                                 ir_timer_stop(t_rn);
 322                         #endif
 323                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
 324                         #if KAPS_TIMING
 325                                 ir_timer_start(t_rn);
 326                         #endif
 327
 328                         merge_into_RN_node(pbqp, rpeo);
 329
 330                         #if KAPS_TIMING
 331                                 ir_timer_stop(t_rn);
 332                         #endif
 333                 } else {
 334                         #if KAPS_TIMING
 335                                 printf("PBQP RE reductions:           %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_edge) / 1000.0);
 336                                 printf("PBQP R1 reductions:           %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_r1) / 1000.0);
 337                                 printf("PBQP R2 reductions:           %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_r2) / 1000.0);
 338                                 printf("PBQP RN reductions:           %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_rn) / 1000.0);
 339                         #endif
 340
 341                         return;
 342                 }
 343         }
 344 }
 345
 346 void solve_pbqp_heuristical_co_ld(pbqp_t *pbqp, plist_t *rpeo)
 347 {
 348         /* Reduce nodes degree ... */
 349         initial_simplify_edges(pbqp);
 350
 351         /* ... and put node into bucket representing their degree. */
 352         fill_node_buckets(pbqp);
 353
 354         #if KAPS_STATISTIC
 355                 FILE *fh = fopen("solutions.pb", "a");
 356                 fprintf(fh, "Solution");
 357                 fclose(fh);
 358         #endif
 359
 360         apply_heuristic_reductions_co(pbqp, rpeo);
 361
 362         pbqp->solution = determine_solution(pbqp);
 363
 364         #if KAPS_STATISTIC
 365                 fh = fopen("solutions.pb", "a");
 366                 #if KAPS_USE_UNSIGNED
 367                         fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
 368                                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 369                                         pbqp->num_rm, pbqp->num_rn);
 370                 #else
 371                         fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
 372                                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 373                                         pbqp->num_rm, pbqp->num_rn);
 374                 #endif
 375                 fclose(fh);
 376         #endif
 377
 378         /* Solve reduced nodes. */
 379         back_propagate_ld(pbqp);
 380
 381         free_buckets();
 382 }