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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Brute force PBQP solver.
   9  * @date    02.12.2008
  10  * @author  Sebastian Buchwald
  11  */
  12 #include "config.h"
  13
  14 #include "assert.h"
  15 #include "error.h"
  16
  17 #include "bucket.h"
  18 #include "brute_force.h"
  19 #include "optimal.h"
  20 #if KAPS_DUMP
  21 #include "html_dumper.h"
  22 #endif
  23 #include "kaps.h"
  24 #include "matrix.h"
  25 #include "pbqp_edge.h"
  26 #include "pbqp_edge_t.h"
  27 #include "pbqp_node.h"
  28 #include "pbqp_node_t.h"
  29 #include "vector.h"
  30
  31 #if KAPS_STATISTIC
  32 static int dump = 0;
  33 #endif
  34
  35 /* Forward declarations. */
  36 static void apply_Brute_Force(pbqp_t *pbqp);
  37
  38 static void apply_brute_force_reductions(pbqp_t *pbqp)
  39 {
  40         for (;;) {
  41                 if (edge_bucket_get_length(edge_bucket) > 0) {
  42                         apply_edge(pbqp);
  43                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
  44                         apply_RI(pbqp);
  45                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
  46                         apply_RII(pbqp);
  47                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
  48                         apply_Brute_Force(pbqp);
  49                 } else {
  50                         return;
  51                 }
  52         }
  53 }
  54
  55 static unsigned get_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
  56 {
  57         vector_t *node_vec;
  58         unsigned  node_index;
  59         unsigned  node_len;
  60         unsigned  min_index    = 0;
  61         num       min          = INF_COSTS;
  62         unsigned  bucket_index;
  63
  64         assert(pbqp);
  65         node_vec     = node->costs;
  66         node_len     = node_vec->len;
  67         bucket_index = node->bucket_index;
  68
  69         for (node_index = 0; node_index < node_len; ++node_index) {
  70                 pbqp_node_bucket_t bucket_deg3;
  71                 num                value;
  72                 unsigned           bucket_0_length;
  73                 unsigned           bucket_red_length;
  74
  75                 char *tmp = (char*)obstack_finish(&pbqp->obstack);
  76
  77                 node_bucket_init(&bucket_deg3);
  78
  79                 /* Some node buckets and the edge bucket should be empty. */
  80                 assert(node_bucket_get_length(node_buckets[1]) == 0);
  81                 assert(node_bucket_get_length(node_buckets[2]) == 0);
  82                 assert(edge_bucket_get_length(edge_bucket)     == 0);
  83
  84                 /* char *tmp = obstack_finish(&pbqp->obstack); */
  85
  86                 /* Save current PBQP state. */
  87                 node_bucket_copy(&bucket_deg3, node_buckets[3]);
  88                 node_bucket_shrink(&node_buckets[3], 0);
  89                 node_bucket_deep_copy(pbqp, &node_buckets[3], bucket_deg3);
  90                 node_bucket_update(pbqp, node_buckets[3]);
  91                 bucket_0_length   = node_bucket_get_length(node_buckets[0]);
  92                 bucket_red_length = node_bucket_get_length(reduced_bucket);
  93
  94                 /* Select alternative and solve PBQP recursively. */
  95                 select_alternative(node_buckets[3][bucket_index], node_index);
  96                 apply_brute_force_reductions(pbqp);
  97
  98                 value = determine_solution(pbqp);
  99
 100                 if (value < min) {
 101                         min = value;
 102                         min_index = node_index;
 103                 }
 104
 105                 /* Some node buckets and the edge bucket should still be empty. */
 106                 assert(node_bucket_get_length(node_buckets[1]) == 0);
 107                 assert(node_bucket_get_length(node_buckets[2]) == 0);
 108                 assert(edge_bucket_get_length(edge_bucket)     == 0);
 109
 110                 /* Clear modified buckets... */
 111                 node_bucket_shrink(&node_buckets[3], 0);
 112
 113                 /* ... and restore old PBQP state. */
 114                 node_bucket_shrink(&node_buckets[0], bucket_0_length);
 115                 node_bucket_shrink(&reduced_bucket, bucket_red_length);
 116                 node_bucket_copy(&node_buckets[3], bucket_deg3);
 117                 node_bucket_update(pbqp, node_buckets[3]);
 118
 119                 /* Free copies. */
 120                 /* obstack_free(&pbqp->obstack, tmp); */
 121                 node_bucket_free(&bucket_deg3);
 122
 123                 obstack_free(&pbqp->obstack, tmp);
 124         }
 125
 126         return min_index;
 127 }
 128
 129 static void apply_Brute_Force(pbqp_t *pbqp)
 130 {
 131         pbqp_node_t *node         = NULL;
 132         unsigned     min_index    = 0;
 133
 134         assert(pbqp);
 135
 136         /* We want to reduce a node with maximum degree. */
 137         node = get_node_with_max_degree();
 138         assert(pbqp_node_get_degree(node) > 2);
 139
 140 #if KAPS_DUMP
 141         if (pbqp->dump_file) {
 142                 char     txt[100];
 143                 sprintf(txt, "BF-Reduction of Node n%d", node->index);
 144                 pbqp_dump_section(pbqp->dump_file, 2, txt);
 145                 pbqp_dump_graph(pbqp);
 146         }
 147 #endif
 148
 149 #if KAPS_STATISTIC
 150         dump++;
 151 #endif
 152
 153         min_index = get_minimal_alternative(pbqp, node);
 154         node = pbqp->nodes[node->index];
 155
 156 #if KAPS_DUMP
 157         if (pbqp->dump_file) {
 158                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
 159                                         node->index, min_index);
 160         }
 161 #endif
 162
 163 #if KAPS_STATISTIC
 164         dump--;
 165         if (dump == 0) {
 166                 FILE *fh = fopen("solutions.pb", "a");
 167                 fprintf(fh, "[%u]", min_index);
 168                 fclose(fh);
 169                 pbqp->num_bf++;
 170         }
 171 #endif
 172
 173         /* Now that we found the minimum set all other costs to infinity. */
 174         select_alternative(node, min_index);
 175 }
 176
 177
 178
 179 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
 180 {
 181         pbqp_edge_t   *edge;
 182         pbqp_node_t   *other;
 183         pbqp_matrix_t *mat;
 184         vector_t      *vec;
 185         int            is_src;
 186
 187         assert(pbqp);
 188
 189         edge = node->edges[0];
 190         mat = edge->costs;
 191         is_src = edge->src == node;
 192         vec = node->costs;
 193
 194         if (is_src) {
 195                 other = edge->tgt;
 196
 197                 /* Update pointer for brute force solver. */
 198                 other = pbqp->nodes[other->index];
 199
 200                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
 201         } else {
 202                 other = edge->src;
 203
 204                 /* Update pointer for brute force solver. */
 205                 other = pbqp->nodes[other->index];
 206
 207                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
 208         }
 209
 210 #if KAPS_DUMP
 211         if (pbqp->dump_file) {
 212                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 213         }
 214 #endif
 215 }
 216
 217 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
 218 {
 219         pbqp_edge_t   *src_edge   = node->edges[0];
 220         pbqp_edge_t   *tgt_edge   = node->edges[1];
 221         int            src_is_src = src_edge->src == node;
 222         int            tgt_is_src = tgt_edge->src == node;
 223         pbqp_matrix_t *src_mat;
 224         pbqp_matrix_t *tgt_mat;
 225         pbqp_node_t   *src_node;
 226         pbqp_node_t   *tgt_node;
 227         vector_t      *vec;
 228         vector_t      *node_vec;
 229         unsigned       col_index;
 230         unsigned       row_index;
 231
 232         assert(pbqp);
 233
 234         if (src_is_src) {
 235                 src_node = src_edge->tgt;
 236         } else {
 237                 src_node = src_edge->src;
 238         }
 239
 240         if (tgt_is_src) {
 241                 tgt_node = tgt_edge->tgt;
 242         } else {
 243                 tgt_node = tgt_edge->src;
 244         }
 245
 246         /* Swap nodes if necessary. */
 247         if (tgt_node->index < src_node->index) {
 248                 pbqp_node_t *tmp_node;
 249                 pbqp_edge_t *tmp_edge;
 250
 251                 tmp_node = src_node;
 252                 src_node = tgt_node;
 253                 tgt_node = tmp_node;
 254
 255                 tmp_edge = src_edge;
 256                 src_edge = tgt_edge;
 257                 tgt_edge = tmp_edge;
 258
 259                 src_is_src = src_edge->src == node;
 260                 tgt_is_src = tgt_edge->src == node;
 261         }
 262
 263         /* Update pointer for brute force solver. */
 264         src_node = pbqp->nodes[src_node->index];
 265         tgt_node = pbqp->nodes[tgt_node->index];
 266
 267         src_mat = src_edge->costs;
 268         tgt_mat = tgt_edge->costs;
 269
 270         node_vec = node->costs;
 271
 272         row_index = src_node->solution;
 273         col_index = tgt_node->solution;
 274
 275         vec = vector_copy(pbqp, node_vec);
 276
 277         if (src_is_src) {
 278                 vector_add_matrix_col(vec, src_mat, row_index);
 279         } else {
 280                 vector_add_matrix_row(vec, src_mat, row_index);
 281         }
 282
 283         if (tgt_is_src) {
 284                 vector_add_matrix_col(vec, tgt_mat, col_index);
 285         } else {
 286                 vector_add_matrix_row(vec, tgt_mat, col_index);
 287         }
 288
 289         node->solution = vector_get_min_index(vec);
 290
 291 #if KAPS_DUMP
 292         if (pbqp->dump_file) {
 293                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 294         }
 295 #endif
 296
 297         obstack_free(&pbqp->obstack, vec);
 298 }
 299
 300 static void back_propagate_brute_force(pbqp_t *pbqp)
 301 {
 302         unsigned node_index;
 303         unsigned node_len = node_bucket_get_length(reduced_bucket);
 304
 305         assert(pbqp);
 306
 307 #if KAPS_DUMP
 308         if (pbqp->dump_file) {
 309                 pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
 310         }
 311 #endif
 312
 313         for (node_index = node_len; node_index > 0; --node_index) {
 314                 pbqp_node_t *node = reduced_bucket[node_index - 1];
 315
 316                 switch (pbqp_node_get_degree(node)) {
 317                         case 1:
 318                                 back_propagate_RI(pbqp, node);
 319                                 break;
 320                         case 2:
 321                                 back_propagate_RII(pbqp, node);
 322                                 break;
 323                         default:
 324                                 panic("Only nodes with degree one or two should be in this bucket");
 325                 }
 326         }
 327 }
 328
 329 void solve_pbqp_brute_force(pbqp_t *pbqp)
 330 {
 331         /* Reduce nodes degree ... */
 332         initial_simplify_edges(pbqp);
 333
 334         /* ... and put node into bucket representing their degree. */
 335         fill_node_buckets(pbqp);
 336
 337 #if KAPS_STATISTIC
 338         FILE *fh = fopen("solutions.pb", "a");
 339         fprintf(fh, "Solution");
 340         fclose(fh);
 341 #endif
 342
 343         apply_brute_force_reductions(pbqp);
 344
 345         pbqp->solution = determine_solution(pbqp);
 346
 347 #if KAPS_STATISTIC
 348         fh = fopen("solutions.pb", "a");
 349         #if KAPS_USE_UNSIGNED
 350                 fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
 351                                 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 352                                 pbqp->num_rm, pbqp->num_rn);
 353         #else
 354                 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
 355                                 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 356                                 pbqp->num_rm, pbqp->num_bf);
 357         #endif
 358         fclose(fh);
 359 #endif
 360
 361         /* Solve reduced nodes. */
 362         back_propagate_brute_force(pbqp);
 363
 364         free_buckets();
 365 }