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"
46 /* Forward declarations. */
47 static void apply_Brute_Force(pbqp *pbqp);
49 static void apply_brute_force_reductions(pbqp *pbqp)
52 if (edge_bucket_get_length(edge_bucket) > 0) {
54 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
56 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
58 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
59 apply_Brute_Force(pbqp);
66 static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node)
71 unsigned min_index = 0;
73 unsigned bucket_index;
77 node_vec = node->costs;
78 node_len = node_vec->len;
79 bucket_index = node->bucket_index;
81 for (node_index = 0; node_index < node_len; ++node_index) {
82 pbqp_node_bucket bucket_deg3;
84 unsigned bucket_0_length;
85 unsigned bucket_red_length;
87 char *tmp = obstack_finish(&pbqp->obstack);
89 node_bucket_init(&bucket_deg3);
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);
96 /* char *tmp = obstack_finish(&pbqp->obstack); */
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);
106 /* Select alternative and solve PBQP recursively. */
107 select_alternative(node_buckets[3][bucket_index], node_index);
108 apply_brute_force_reductions(pbqp);
110 value = determine_solution(pbqp);
114 min_index = node_index;
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);
122 /* Clear modified buckets... */
123 node_bucket_shrink(&node_buckets[3], 0);
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]);
132 /* obstack_free(&pbqp->obstack, tmp); */
133 node_bucket_free(&bucket_deg3);
135 obstack_free(&pbqp->obstack, tmp);
141 static void apply_Brute_Force(pbqp *pbqp)
143 pbqp_node *node = NULL;
144 unsigned min_index = 0;
148 /* We want to reduce a node with maximum degree. */
149 node = get_node_with_max_degree();
151 assert(pbqp_node_get_degree(node) > 2);
154 if (pbqp->dump_file) {
156 sprintf(txt, "BF-Reduction of Node n%d", node->index);
157 dump_section(pbqp->dump_file, 2, txt);
158 pbqp_dump_graph(pbqp);
166 min_index = get_minimal_alternative(pbqp, node);
167 node = pbqp->nodes[node->index];
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);
179 FILE *fh = fopen("solutions.pb", "a");
180 fprintf(fh, "[%u]", min_index);
186 /* Now that we found the minimum set all other costs to infinity. */
187 select_alternative(node, min_index);
192 static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
203 edge = node->edges[0];
205 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);
220 /* Update pointer for brute force solver. */
221 other = pbqp->nodes[other->index];
223 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
227 if (pbqp->dump_file) {
228 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
233 static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
235 pbqp_edge *src_edge = node->edges[0];
236 pbqp_edge *tgt_edge = node->edges[1];
237 int src_is_src = src_edge->src == node;
238 int tgt_is_src = tgt_edge->src == node;
239 pbqp_matrix *src_mat;
240 pbqp_matrix *tgt_mat;
251 src_node = src_edge->tgt;
253 src_node = src_edge->src;
257 tgt_node = tgt_edge->tgt;
259 tgt_node = tgt_edge->src;
262 /* Swap nodes if necessary. */
263 if (tgt_node->index < src_node->index) {
275 src_is_src = src_edge->src == node;
276 tgt_is_src = tgt_edge->src == node;
279 /* Update pointer for brute force solver. */
280 src_node = pbqp->nodes[src_node->index];
281 tgt_node = pbqp->nodes[tgt_node->index];
283 src_mat = src_edge->costs;
284 tgt_mat = tgt_edge->costs;
286 node_vec = node->costs;
288 row_index = src_node->solution;
289 col_index = tgt_node->solution;
291 vec = vector_copy(pbqp, node_vec);
294 vector_add_matrix_col(vec, src_mat, row_index);
296 vector_add_matrix_row(vec, src_mat, row_index);
300 vector_add_matrix_col(vec, tgt_mat, col_index);
302 vector_add_matrix_row(vec, tgt_mat, col_index);
305 node->solution = vector_get_min_index(vec);
308 if (pbqp->dump_file) {
309 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
313 obstack_free(&pbqp->obstack, vec);
316 static void back_propagate_brute_force(pbqp *pbqp)
319 unsigned node_len = node_bucket_get_length(reduced_bucket);
324 if (pbqp->dump_file) {
325 dump_section(pbqp->dump_file, 2, "Back Propagation");
329 for (node_index = node_len; node_index > 0; --node_index) {
330 pbqp_node *node = reduced_bucket[node_index - 1];
332 switch (pbqp_node_get_degree(node)) {
334 back_propagate_RI(pbqp, node);
337 back_propagate_RII(pbqp, node);
340 panic("Only nodes with degree one or two should be in this bucket");
346 void solve_pbqp_brute_force(pbqp *pbqp)
348 /* Reduce nodes degree ... */
349 initial_simplify_edges(pbqp);
351 /* ... and put node into bucket representing their degree. */
352 fill_node_buckets(pbqp);
355 FILE *fh = fopen("solutions.pb", "a");
356 fprintf(fh, "Solution");
360 apply_brute_force_reductions(pbqp);
362 pbqp->solution = determine_solution(pbqp);
365 fh = fopen("solutions.pb", "a");
366 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
367 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
372 /* Solve reduced nodes. */
373 back_propagate_brute_force(pbqp);