2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Brute force PBQP solver.
10 * @author Sebastian Buchwald
18 #include "brute_force.h"
21 #include "html_dumper.h"
25 #include "pbqp_edge.h"
26 #include "pbqp_edge_t.h"
27 #include "pbqp_node.h"
28 #include "pbqp_node_t.h"
35 /* Forward declarations. */
36 static void apply_Brute_Force(pbqp_t *pbqp);
38 static void apply_brute_force_reductions(pbqp_t *pbqp)
41 if (edge_bucket_get_length(edge_bucket) > 0) {
43 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
45 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
47 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
48 apply_Brute_Force(pbqp);
55 static unsigned get_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
60 unsigned min_index = 0;
62 unsigned bucket_index;
65 node_vec = node->costs;
66 node_len = node_vec->len;
67 bucket_index = node->bucket_index;
69 for (node_index = 0; node_index < node_len; ++node_index) {
70 pbqp_node_bucket_t bucket_deg3;
72 unsigned bucket_0_length;
73 unsigned bucket_red_length;
75 char *tmp = (char*)obstack_finish(&pbqp->obstack);
77 node_bucket_init(&bucket_deg3);
79 /* Some node buckets and the edge bucket should be empty. */
80 assert(node_bucket_get_length(node_buckets[1]) == 0);
81 assert(node_bucket_get_length(node_buckets[2]) == 0);
82 assert(edge_bucket_get_length(edge_bucket) == 0);
84 /* char *tmp = obstack_finish(&pbqp->obstack); */
86 /* Save current PBQP state. */
87 node_bucket_copy(&bucket_deg3, node_buckets[3]);
88 node_bucket_shrink(&node_buckets[3], 0);
89 node_bucket_deep_copy(pbqp, &node_buckets[3], bucket_deg3);
90 node_bucket_update(pbqp, node_buckets[3]);
91 bucket_0_length = node_bucket_get_length(node_buckets[0]);
92 bucket_red_length = node_bucket_get_length(reduced_bucket);
94 /* Select alternative and solve PBQP recursively. */
95 select_alternative(node_buckets[3][bucket_index], node_index);
96 apply_brute_force_reductions(pbqp);
98 value = determine_solution(pbqp);
102 min_index = node_index;
105 /* Some node buckets and the edge bucket should still be empty. */
106 assert(node_bucket_get_length(node_buckets[1]) == 0);
107 assert(node_bucket_get_length(node_buckets[2]) == 0);
108 assert(edge_bucket_get_length(edge_bucket) == 0);
110 /* Clear modified buckets... */
111 node_bucket_shrink(&node_buckets[3], 0);
113 /* ... and restore old PBQP state. */
114 node_bucket_shrink(&node_buckets[0], bucket_0_length);
115 node_bucket_shrink(&reduced_bucket, bucket_red_length);
116 node_bucket_copy(&node_buckets[3], bucket_deg3);
117 node_bucket_update(pbqp, node_buckets[3]);
120 /* obstack_free(&pbqp->obstack, tmp); */
121 node_bucket_free(&bucket_deg3);
123 obstack_free(&pbqp->obstack, tmp);
129 static void apply_Brute_Force(pbqp_t *pbqp)
131 pbqp_node_t *node = NULL;
132 unsigned min_index = 0;
136 /* We want to reduce a node with maximum degree. */
137 node = get_node_with_max_degree();
138 assert(pbqp_node_get_degree(node) > 2);
141 if (pbqp->dump_file) {
143 sprintf(txt, "BF-Reduction of Node n%d", node->index);
144 pbqp_dump_section(pbqp->dump_file, 2, txt);
145 pbqp_dump_graph(pbqp);
153 min_index = get_minimal_alternative(pbqp, node);
154 node = pbqp->nodes[node->index];
157 if (pbqp->dump_file) {
158 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
159 node->index, min_index);
166 FILE *fh = fopen("solutions.pb", "a");
167 fprintf(fh, "[%u]", min_index);
173 /* Now that we found the minimum set all other costs to infinity. */
174 select_alternative(node, min_index);
179 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
189 edge = node->edges[0];
191 is_src = edge->src == node;
197 /* Update pointer for brute force solver. */
198 other = pbqp->nodes[other->index];
200 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
204 /* Update pointer for brute force solver. */
205 other = pbqp->nodes[other->index];
207 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
211 if (pbqp->dump_file) {
212 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
217 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
219 pbqp_edge_t *src_edge = node->edges[0];
220 pbqp_edge_t *tgt_edge = node->edges[1];
221 int src_is_src = src_edge->src == node;
222 int tgt_is_src = tgt_edge->src == node;
223 pbqp_matrix_t *src_mat;
224 pbqp_matrix_t *tgt_mat;
225 pbqp_node_t *src_node;
226 pbqp_node_t *tgt_node;
235 src_node = src_edge->tgt;
237 src_node = src_edge->src;
241 tgt_node = tgt_edge->tgt;
243 tgt_node = tgt_edge->src;
246 /* Swap nodes if necessary. */
247 if (tgt_node->index < src_node->index) {
248 pbqp_node_t *tmp_node;
249 pbqp_edge_t *tmp_edge;
259 src_is_src = src_edge->src == node;
260 tgt_is_src = tgt_edge->src == node;
263 /* Update pointer for brute force solver. */
264 src_node = pbqp->nodes[src_node->index];
265 tgt_node = pbqp->nodes[tgt_node->index];
267 src_mat = src_edge->costs;
268 tgt_mat = tgt_edge->costs;
270 node_vec = node->costs;
272 row_index = src_node->solution;
273 col_index = tgt_node->solution;
275 vec = vector_copy(pbqp, node_vec);
278 vector_add_matrix_col(vec, src_mat, row_index);
280 vector_add_matrix_row(vec, src_mat, row_index);
284 vector_add_matrix_col(vec, tgt_mat, col_index);
286 vector_add_matrix_row(vec, tgt_mat, col_index);
289 node->solution = vector_get_min_index(vec);
292 if (pbqp->dump_file) {
293 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
297 obstack_free(&pbqp->obstack, vec);
300 static void back_propagate_brute_force(pbqp_t *pbqp)
303 unsigned node_len = node_bucket_get_length(reduced_bucket);
308 if (pbqp->dump_file) {
309 pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
313 for (node_index = node_len; node_index > 0; --node_index) {
314 pbqp_node_t *node = reduced_bucket[node_index - 1];
316 switch (pbqp_node_get_degree(node)) {
318 back_propagate_RI(pbqp, node);
321 back_propagate_RII(pbqp, node);
324 panic("Only nodes with degree one or two should be in this bucket");
329 void solve_pbqp_brute_force(pbqp_t *pbqp)
331 /* Reduce nodes degree ... */
332 initial_simplify_edges(pbqp);
334 /* ... and put node into bucket representing their degree. */
335 fill_node_buckets(pbqp);
338 FILE *fh = fopen("solutions.pb", "a");
339 fprintf(fh, "Solution");
343 apply_brute_force_reductions(pbqp);
345 pbqp->solution = determine_solution(pbqp);
348 fh = fopen("solutions.pb", "a");
349 #if KAPS_USE_UNSIGNED
350 fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
351 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
352 pbqp->num_rm, pbqp->num_rn);
354 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
355 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
356 pbqp->num_rm, pbqp->num_bf);
361 /* Solve reduced nodes. */
362 back_propagate_brute_force(pbqp);