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 /* Forward declarations. */
  47 static void apply_Brute_Force(pbqp *pbqp);
  48
  49 static void apply_brute_force_reductions(pbqp *pbqp)
  50 {
  51         for (;;) {
  52                 if (edge_bucket_get_length(edge_bucket) > 0) {
  53                         apply_edge(pbqp);
  54                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
  55                         apply_RI(pbqp);
  56                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
  57                         apply_RII(pbqp);
  58                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
  59                         apply_Brute_Force(pbqp);
  60                 } else {
  61                         return;
  62                 }
  63         }
  64 }
  65
  66 static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node)
  67 {
  68         vector      *node_vec;
  69         unsigned     node_index;
  70         unsigned     node_len;
  71         unsigned     min_index    = 0;
  72         num          min          = INF_COSTS;
  73         unsigned     bucket_index;
  74
  75         assert(pbqp);
  76         assert(node);
  77         node_vec     = node->costs;
  78         node_len     = node_vec->len;
  79         bucket_index = node->bucket_index;
  80
  81         for (node_index = 0; node_index < node_len; ++node_index) {
  82                 pbqp_node_bucket bucket_deg3;
  83                 num              value;
  84                 unsigned         bucket_0_length;
  85                 unsigned         bucket_red_length;
  86
  87                 char *tmp = obstack_finish(&pbqp->obstack);
  88
  89                 node_bucket_init(&bucket_deg3);
  90
  91                 /* Some node buckets and the edge bucket should be empty. */
  92                 assert(node_bucket_get_length(node_buckets[1]) == 0);
  93                 assert(node_bucket_get_length(node_buckets[2]) == 0);
  94                 assert(edge_bucket_get_length(edge_bucket)     == 0);
  95
  96                 /* char *tmp = obstack_finish(&pbqp->obstack); */
  97
  98                 /* Save current PBQP state. */
  99                 node_bucket_copy(&bucket_deg3, node_buckets[3]);
 100                 node_bucket_shrink(&node_buckets[3], 0);
 101                 node_bucket_deep_copy(pbqp, &node_buckets[3], bucket_deg3);
 102                 node_bucket_update(pbqp, node_buckets[3]);
 103                 bucket_0_length   = node_bucket_get_length(node_buckets[0]);
 104                 bucket_red_length = node_bucket_get_length(reduced_bucket);
 105
 106                 /* Select alternative and solve PBQP recursively. */
 107                 select_alternative(node_buckets[3][bucket_index], node_index);
 108                 apply_brute_force_reductions(pbqp);
 109
 110                 value = determine_solution(pbqp);
 111
 112                 if (value < min) {
 113                         min = value;
 114                         min_index = node_index;
 115                 }
 116
 117                 /* Some node buckets and the edge bucket should still be empty. */
 118                 assert(node_bucket_get_length(node_buckets[1]) == 0);
 119                 assert(node_bucket_get_length(node_buckets[2]) == 0);
 120                 assert(edge_bucket_get_length(edge_bucket)     == 0);
 121
 122                 /* Clear modified buckets... */
 123                 node_bucket_shrink(&node_buckets[3], 0);
 124
 125                 /* ... and restore old PBQP state. */
 126                 node_bucket_shrink(&node_buckets[0], bucket_0_length);
 127                 node_bucket_shrink(&reduced_bucket, bucket_red_length);
 128                 node_bucket_copy(&node_buckets[3], bucket_deg3);
 129                 node_bucket_update(pbqp, node_buckets[3]);
 130
 131                 /* Free copies. */
 132                 /* obstack_free(&pbqp->obstack, tmp); */
 133                 node_bucket_free(&bucket_deg3);
 134
 135                 obstack_free(&pbqp->obstack, tmp);
 136         }
 137
 138         return min_index;
 139 }
 140
 141 void apply_Brute_Force(pbqp *pbqp)
 142 {
 143         pbqp_node   *node         = NULL;
 144         unsigned     min_index    = 0;
 145
 146         assert(pbqp);
 147
 148         /* We want to reduce a node with maximum degree. */
 149         node = get_node_with_max_degree();
 150         assert(node);
 151         assert(pbqp_node_get_degree(node) > 2);
 152
 153 #if     KAPS_DUMP
 154         if (pbqp->dump_file) {
 155                 char     txt[100];
 156                 sprintf(txt, "BF-Reduction of Node n%d", node->index);
 157                 dump_section(pbqp->dump_file, 2, txt);
 158                 pbqp_dump_graph(pbqp);
 159         }
 160 #endif
 161
 162 #if KAPS_STATISTIC
 163         dump++;
 164 #endif
 165
 166         min_index = get_minimal_alternative(pbqp, node);
 167         node = pbqp->nodes[node->index];
 168
 169 #if     KAPS_DUMP
 170         if (pbqp->dump_file) {
 171                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
 172                                         node->index, min_index);
 173         }
 174 #endif
 175
 176 #if KAPS_STATISTIC
 177         dump--;
 178         if (dump == 0) {
 179                 FILE *fh = fopen("solutions.pb", "a");
 180                 fprintf(fh, "[%u]", min_index);
 181                 fclose(fh);
 182                 pbqp->num_bf++;
 183         }
 184 #endif
 185
 186         /* Now that we found the minimum set all other costs to infinity. */
 187         select_alternative(node, min_index);
 188 }
 189
 190 void solve_pbqp_brute_force(pbqp *pbqp)
 191 {
 192         /* Reduce nodes degree ... */
 193         initial_simplify_edges(pbqp);
 194
 195         /* ... and put node into bucket representing their degree. */
 196         fill_node_buckets(pbqp);
 197
 198 #if KAPS_STATISTIC
 199         FILE *fh = fopen("solutions.pb", "a");
 200         fprintf(fh, "Solution");
 201         fclose(fh);
 202 #endif
 203
 204         apply_brute_force_reductions(pbqp);
 205
 206         pbqp->solution = determine_solution(pbqp);
 207
 208 #if KAPS_STATISTIC
 209         fh = fopen("solutions.pb", "a");
 210         fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
 211                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 212                         pbqp->num_bf);
 213         fclose(fh);
 214 #endif
 215
 216         /* Solve reduced nodes. */
 217         back_propagate(pbqp);
 218
 219         free_buckets();
 220 }