2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Heuristic PBQP solver.
10 * @author Sebastian Buchwald
14 #include "adt/array.h"
19 #include "heuristical.h"
22 #include "html_dumper.h"
26 #include "pbqp_edge.h"
27 #include "pbqp_edge_t.h"
28 #include "pbqp_node.h"
29 #include "pbqp_node_t.h"
34 static void apply_RN(pbqp_t *pbqp)
36 pbqp_node_t *node = NULL;
37 unsigned min_index = 0;
41 /* We want to reduce a node with maximum degree. */
42 node = get_node_with_max_degree();
43 assert(pbqp_node_get_degree(node) > 2);
46 if (pbqp->dump_file) {
48 sprintf(txt, "RN-Reduction of Node n%d", node->index);
49 pbqp_dump_section(pbqp->dump_file, 2, txt);
50 pbqp_dump_graph(pbqp);
54 min_index = get_local_minimal_alternative(pbqp, node);
57 if (pbqp->dump_file) {
58 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
59 node->index, min_index);
64 FILE *fh = fopen("solutions.pb", "a");
65 fprintf(fh, "[%u]", min_index);
70 /* Now that we found the local minimum set all other costs to infinity. */
71 select_alternative(node, min_index);
74 static void apply_heuristic_reductions(pbqp_t *pbqp)
77 if (edge_bucket_get_length(edge_bucket) > 0) {
79 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
81 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
83 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
91 void solve_pbqp_heuristical(pbqp_t *pbqp)
93 /* Reduce nodes degree ... */
94 initial_simplify_edges(pbqp);
96 /* ... and put node into bucket representing their degree. */
97 fill_node_buckets(pbqp);
100 FILE *fh = fopen("solutions.pb", "a");
101 fprintf(fh, "Solution");
105 apply_heuristic_reductions(pbqp);
107 pbqp->solution = determine_solution(pbqp);
110 fh = fopen("solutions.pb", "a");
111 #if KAPS_USE_UNSIGNED
112 fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
113 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
114 pbqp->num_rm, pbqp->num_rn);
116 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
117 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
118 pbqp->num_rm, pbqp->num_rn);
123 /* Solve reduced nodes. */
124 back_propagate(pbqp);