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