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

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