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

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