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