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
32 #include "brute_force.h"
35 #include "html_dumper.h"
39 #include "pbqp_edge.h"
40 #include "pbqp_edge_t.h"
41 #include "pbqp_node.h"
42 #include "pbqp_node_t.h"
49 /* Forward declarations. */
50 static void apply_Brute_Force(pbqp_t *pbqp);
52 static void apply_brute_force_reductions(pbqp_t *pbqp)
55 if (edge_bucket_get_length(edge_bucket) > 0) {
57 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
59 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
61 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
62 apply_Brute_Force(pbqp);
69 static unsigned get_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
74 unsigned min_index = 0;
76 unsigned bucket_index;
79 node_vec = node->costs;
80 node_len = node_vec->len;
81 bucket_index = node->bucket_index;
83 for (node_index = 0; node_index < node_len; ++node_index) {
84 pbqp_node_bucket_t bucket_deg3;
86 unsigned bucket_0_length;
87 unsigned bucket_red_length;
89 char *tmp = (char*)obstack_finish(&pbqp->obstack);
91 node_bucket_init(&bucket_deg3);
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);
98 /* char *tmp = obstack_finish(&pbqp->obstack); */
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);
108 /* Select alternative and solve PBQP recursively. */
109 select_alternative(node_buckets[3][bucket_index], node_index);
110 apply_brute_force_reductions(pbqp);
112 value = determine_solution(pbqp);
116 min_index = node_index;
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);
124 /* Clear modified buckets... */
125 node_bucket_shrink(&node_buckets[3], 0);
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]);
134 /* obstack_free(&pbqp->obstack, tmp); */
135 node_bucket_free(&bucket_deg3);
137 obstack_free(&pbqp->obstack, tmp);
143 static void apply_Brute_Force(pbqp_t *pbqp)
145 pbqp_node_t *node = NULL;
146 unsigned min_index = 0;
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);
155 if (pbqp->dump_file) {
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);
167 min_index = get_minimal_alternative(pbqp, node);
168 node = pbqp->nodes[node->index];
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);
180 FILE *fh = fopen("solutions.pb", "a");
181 fprintf(fh, "[%u]", min_index);
187 /* Now that we found the minimum set all other costs to infinity. */
188 select_alternative(node, min_index);
193 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
203 edge = node->edges[0];
205 is_src = edge->src == node;
211 /* Update pointer for brute force solver. */
212 other = pbqp->nodes[other->index];
214 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
218 /* Update pointer for brute force solver. */
219 other = pbqp->nodes[other->index];
221 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
225 if (pbqp->dump_file) {
226 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
231 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
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;
249 src_node = src_edge->tgt;
251 src_node = src_edge->src;
255 tgt_node = tgt_edge->tgt;
257 tgt_node = tgt_edge->src;
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;
273 src_is_src = src_edge->src == node;
274 tgt_is_src = tgt_edge->src == node;
277 /* Update pointer for brute force solver. */
278 src_node = pbqp->nodes[src_node->index];
279 tgt_node = pbqp->nodes[tgt_node->index];
281 src_mat = src_edge->costs;
282 tgt_mat = tgt_edge->costs;
284 node_vec = node->costs;
286 row_index = src_node->solution;
287 col_index = tgt_node->solution;
289 vec = vector_copy(pbqp, node_vec);
292 vector_add_matrix_col(vec, src_mat, row_index);
294 vector_add_matrix_row(vec, src_mat, row_index);
298 vector_add_matrix_col(vec, tgt_mat, col_index);
300 vector_add_matrix_row(vec, tgt_mat, col_index);
303 node->solution = vector_get_min_index(vec);
306 if (pbqp->dump_file) {
307 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
311 obstack_free(&pbqp->obstack, vec);
314 static void back_propagate_brute_force(pbqp_t *pbqp)
317 unsigned node_len = node_bucket_get_length(reduced_bucket);
322 if (pbqp->dump_file) {
323 pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
327 for (node_index = node_len; node_index > 0; --node_index) {
328 pbqp_node_t *node = reduced_bucket[node_index - 1];
330 switch (pbqp_node_get_degree(node)) {
332 back_propagate_RI(pbqp, node);
335 back_propagate_RII(pbqp, node);
338 panic("Only nodes with degree one or two should be in this bucket");
343 void solve_pbqp_brute_force(pbqp_t *pbqp)
345 /* Reduce nodes degree ... */
346 initial_simplify_edges(pbqp);
348 /* ... and put node into bucket representing their degree. */
349 fill_node_buckets(pbqp);
352 FILE *fh = fopen("solutions.pb", "a");
353 fprintf(fh, "Solution");
357 apply_brute_force_reductions(pbqp);
359 pbqp->solution = determine_solution(pbqp);
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);
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);
375 /* Solve reduced nodes. */
376 back_propagate_brute_force(pbqp);