2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Brute force PBQP solver.
24 * @author Sebastian Buchwald
33 #include "brute_force.h"
36 #include "html_dumper.h"
40 #include "pbqp_edge.h"
41 #include "pbqp_edge_t.h"
42 #include "pbqp_node.h"
43 #include "pbqp_node_t.h"
50 /* Forward declarations. */
51 static void apply_Brute_Force(pbqp_t *pbqp);
53 static void apply_brute_force_reductions(pbqp_t *pbqp)
56 if (edge_bucket_get_length(edge_bucket) > 0) {
58 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
60 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
62 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
63 apply_Brute_Force(pbqp);
70 static unsigned get_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
75 unsigned min_index = 0;
77 unsigned bucket_index;
80 node_vec = node->costs;
81 node_len = node_vec->len;
82 bucket_index = node->bucket_index;
84 for (node_index = 0; node_index < node_len; ++node_index) {
85 pbqp_node_bucket_t bucket_deg3;
87 unsigned bucket_0_length;
88 unsigned bucket_red_length;
90 char *tmp = (char*)obstack_finish(&pbqp->obstack);
92 node_bucket_init(&bucket_deg3);
94 /* Some node buckets and the edge bucket should be empty. */
95 assert(node_bucket_get_length(node_buckets[1]) == 0);
96 assert(node_bucket_get_length(node_buckets[2]) == 0);
97 assert(edge_bucket_get_length(edge_bucket) == 0);
99 /* char *tmp = obstack_finish(&pbqp->obstack); */
101 /* Save current PBQP state. */
102 node_bucket_copy(&bucket_deg3, node_buckets[3]);
103 node_bucket_shrink(&node_buckets[3], 0);
104 node_bucket_deep_copy(pbqp, &node_buckets[3], bucket_deg3);
105 node_bucket_update(pbqp, node_buckets[3]);
106 bucket_0_length = node_bucket_get_length(node_buckets[0]);
107 bucket_red_length = node_bucket_get_length(reduced_bucket);
109 /* Select alternative and solve PBQP recursively. */
110 select_alternative(node_buckets[3][bucket_index], node_index);
111 apply_brute_force_reductions(pbqp);
113 value = determine_solution(pbqp);
117 min_index = node_index;
120 /* Some node buckets and the edge bucket should still be empty. */
121 assert(node_bucket_get_length(node_buckets[1]) == 0);
122 assert(node_bucket_get_length(node_buckets[2]) == 0);
123 assert(edge_bucket_get_length(edge_bucket) == 0);
125 /* Clear modified buckets... */
126 node_bucket_shrink(&node_buckets[3], 0);
128 /* ... and restore old PBQP state. */
129 node_bucket_shrink(&node_buckets[0], bucket_0_length);
130 node_bucket_shrink(&reduced_bucket, bucket_red_length);
131 node_bucket_copy(&node_buckets[3], bucket_deg3);
132 node_bucket_update(pbqp, node_buckets[3]);
135 /* obstack_free(&pbqp->obstack, tmp); */
136 node_bucket_free(&bucket_deg3);
138 obstack_free(&pbqp->obstack, tmp);
144 static void apply_Brute_Force(pbqp_t *pbqp)
146 pbqp_node_t *node = NULL;
147 unsigned min_index = 0;
151 /* We want to reduce a node with maximum degree. */
152 node = get_node_with_max_degree();
153 assert(pbqp_node_get_degree(node) > 2);
156 if (pbqp->dump_file) {
158 sprintf(txt, "BF-Reduction of Node n%d", node->index);
159 dump_section(pbqp->dump_file, 2, txt);
160 pbqp_dump_graph(pbqp);
168 min_index = get_minimal_alternative(pbqp, node);
169 node = pbqp->nodes[node->index];
172 if (pbqp->dump_file) {
173 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
174 node->index, min_index);
181 FILE *fh = fopen("solutions.pb", "a");
182 fprintf(fh, "[%u]", min_index);
188 /* Now that we found the minimum set all other costs to infinity. */
189 select_alternative(node, min_index);
194 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
204 edge = node->edges[0];
206 is_src = edge->src == node;
212 /* Update pointer for brute force solver. */
213 other = pbqp->nodes[other->index];
215 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
219 /* Update pointer for brute force solver. */
220 other = pbqp->nodes[other->index];
222 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
226 if (pbqp->dump_file) {
227 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
232 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
234 pbqp_edge_t *src_edge = node->edges[0];
235 pbqp_edge_t *tgt_edge = node->edges[1];
236 int src_is_src = src_edge->src == node;
237 int tgt_is_src = tgt_edge->src == node;
238 pbqp_matrix_t *src_mat;
239 pbqp_matrix_t *tgt_mat;
240 pbqp_node_t *src_node;
241 pbqp_node_t *tgt_node;
250 src_node = src_edge->tgt;
252 src_node = src_edge->src;
256 tgt_node = tgt_edge->tgt;
258 tgt_node = tgt_edge->src;
261 /* Swap nodes if necessary. */
262 if (tgt_node->index < src_node->index) {
263 pbqp_node_t *tmp_node;
264 pbqp_edge_t *tmp_edge;
274 src_is_src = src_edge->src == node;
275 tgt_is_src = tgt_edge->src == node;
278 /* Update pointer for brute force solver. */
279 src_node = pbqp->nodes[src_node->index];
280 tgt_node = pbqp->nodes[tgt_node->index];
282 src_mat = src_edge->costs;
283 tgt_mat = tgt_edge->costs;
285 node_vec = node->costs;
287 row_index = src_node->solution;
288 col_index = tgt_node->solution;
290 vec = vector_copy(pbqp, node_vec);
293 vector_add_matrix_col(vec, src_mat, row_index);
295 vector_add_matrix_row(vec, src_mat, row_index);
299 vector_add_matrix_col(vec, tgt_mat, col_index);
301 vector_add_matrix_row(vec, tgt_mat, col_index);
304 node->solution = vector_get_min_index(vec);
307 if (pbqp->dump_file) {
308 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
312 obstack_free(&pbqp->obstack, vec);
315 static void back_propagate_brute_force(pbqp_t *pbqp)
318 unsigned node_len = node_bucket_get_length(reduced_bucket);
323 if (pbqp->dump_file) {
324 dump_section(pbqp->dump_file, 2, "Back Propagation");
328 for (node_index = node_len; node_index > 0; --node_index) {
329 pbqp_node_t *node = reduced_bucket[node_index - 1];
331 switch (pbqp_node_get_degree(node)) {
333 back_propagate_RI(pbqp, node);
336 back_propagate_RII(pbqp, node);
339 panic("Only nodes with degree one or two should be in this bucket");
345 void solve_pbqp_brute_force(pbqp_t *pbqp)
347 /* Reduce nodes degree ... */
348 initial_simplify_edges(pbqp);
350 /* ... and put node into bucket representing their degree. */
351 fill_node_buckets(pbqp);
354 FILE *fh = fopen("solutions.pb", "a");
355 fprintf(fh, "Solution");
359 apply_brute_force_reductions(pbqp);
361 pbqp->solution = determine_solution(pbqp);
364 fh = fopen("solutions.pb", "a");
365 #if KAPS_USE_UNSIGNED
366 fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
367 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
368 pbqp->num_rm, pbqp->num_rn);
370 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
371 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
372 pbqp->num_rm, pbqp->num_bf);
377 /* Solve reduced nodes. */
378 back_propagate_brute_force(pbqp);