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