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 *pbqp);
53 static void apply_brute_force_reductions(pbqp *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 *pbqp, pbqp_node *node)
75 unsigned min_index = 0;
77 unsigned bucket_index;
81 node_vec = node->costs;
82 node_len = node_vec->len;
83 bucket_index = node->bucket_index;
85 for (node_index = 0; node_index < node_len; ++node_index) {
86 pbqp_node_bucket bucket_deg3;
88 unsigned bucket_0_length;
89 unsigned bucket_red_length;
91 char *tmp = obstack_finish(&pbqp->obstack);
93 node_bucket_init(&bucket_deg3);
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);
100 /* char *tmp = obstack_finish(&pbqp->obstack); */
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);
110 /* Select alternative and solve PBQP recursively. */
111 select_alternative(node_buckets[3][bucket_index], node_index);
112 apply_brute_force_reductions(pbqp);
114 value = determine_solution(pbqp);
118 min_index = node_index;
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);
126 /* Clear modified buckets... */
127 node_bucket_shrink(&node_buckets[3], 0);
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]);
136 /* obstack_free(&pbqp->obstack, tmp); */
137 node_bucket_free(&bucket_deg3);
139 obstack_free(&pbqp->obstack, tmp);
145 static void apply_Brute_Force(pbqp *pbqp)
147 pbqp_node *node = NULL;
148 unsigned min_index = 0;
152 /* We want to reduce a node with maximum degree. */
153 node = get_node_with_max_degree();
155 assert(pbqp_node_get_degree(node) > 2);
158 if (pbqp->dump_file) {
160 sprintf(txt, "BF-Reduction of Node n%d", node->index);
161 dump_section(pbqp->dump_file, 2, txt);
162 pbqp_dump_graph(pbqp);
170 min_index = get_minimal_alternative(pbqp, node);
171 node = pbqp->nodes[node->index];
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);
183 FILE *fh = fopen("solutions.pb", "a");
184 fprintf(fh, "[%u]", min_index);
190 /* Now that we found the minimum set all other costs to infinity. */
191 select_alternative(node, min_index);
196 static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
207 edge = node->edges[0];
209 is_src = edge->src == node;
216 /* Update pointer for brute force solver. */
217 other = pbqp->nodes[other->index];
219 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
224 /* Update pointer for brute force solver. */
225 other = pbqp->nodes[other->index];
227 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
231 if (pbqp->dump_file) {
232 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
237 static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
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;
255 src_node = src_edge->tgt;
257 src_node = src_edge->src;
261 tgt_node = tgt_edge->tgt;
263 tgt_node = tgt_edge->src;
266 /* Swap nodes if necessary. */
267 if (tgt_node->index < src_node->index) {
279 src_is_src = src_edge->src == node;
280 tgt_is_src = tgt_edge->src == node;
283 /* Update pointer for brute force solver. */
284 src_node = pbqp->nodes[src_node->index];
285 tgt_node = pbqp->nodes[tgt_node->index];
287 src_mat = src_edge->costs;
288 tgt_mat = tgt_edge->costs;
290 node_vec = node->costs;
292 row_index = src_node->solution;
293 col_index = tgt_node->solution;
295 vec = vector_copy(pbqp, node_vec);
298 vector_add_matrix_col(vec, src_mat, row_index);
300 vector_add_matrix_row(vec, src_mat, row_index);
304 vector_add_matrix_col(vec, tgt_mat, col_index);
306 vector_add_matrix_row(vec, tgt_mat, col_index);
309 node->solution = vector_get_min_index(vec);
312 if (pbqp->dump_file) {
313 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
317 obstack_free(&pbqp->obstack, vec);
320 static void back_propagate_brute_force(pbqp *pbqp)
323 unsigned node_len = node_bucket_get_length(reduced_bucket);
328 if (pbqp->dump_file) {
329 dump_section(pbqp->dump_file, 2, "Back Propagation");
333 for (node_index = node_len; node_index > 0; --node_index) {
334 pbqp_node *node = reduced_bucket[node_index - 1];
336 switch (pbqp_node_get_degree(node)) {
338 back_propagate_RI(pbqp, node);
341 back_propagate_RII(pbqp, node);
344 panic("Only nodes with degree one or two should be in this bucket");
350 void solve_pbqp_brute_force(pbqp *pbqp)
352 /* Reduce nodes degree ... */
353 initial_simplify_edges(pbqp);
355 /* ... and put node into bucket representing their degree. */
356 fill_node_buckets(pbqp);
359 FILE *fh = fopen("solutions.pb", "a");
360 fprintf(fh, "Solution");
364 apply_brute_force_reductions(pbqp);
366 pbqp->solution = determine_solution(pbqp);
369 fh = fopen("solutions.pb", "a");
370 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
371 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
376 /* Solve reduced nodes. */
377 back_propagate_brute_force(pbqp);