2 * This file is part of libFirm.
3 * Copyright (C) 2012 Karlsruhe Institute of Technology.
12 #include "heuristical_co_ld.h"
15 #include "html_dumper.h"
19 #include "pbqp_edge.h"
20 #include "pbqp_edge_t.h"
21 #include "pbqp_node.h"
22 #include "pbqp_node_t.h"
28 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
38 edge = node->edges[0];
40 is_src = edge->src == node;
45 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
48 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
52 if (pbqp->dump_file) {
53 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
58 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
60 pbqp_edge_t *src_edge = node->edges[0];
61 pbqp_edge_t *tgt_edge = node->edges[1];
62 int src_is_src = src_edge->src == node;
63 int tgt_is_src = tgt_edge->src == node;
64 pbqp_matrix_t *src_mat;
65 pbqp_matrix_t *tgt_mat;
66 pbqp_node_t *src_node;
67 pbqp_node_t *tgt_node;
76 src_node = src_edge->tgt;
78 src_node = src_edge->src;
82 tgt_node = tgt_edge->tgt;
84 tgt_node = tgt_edge->src;
87 /* Swap nodes if necessary. */
88 if (tgt_node->index < src_node->index) {
89 pbqp_node_t *tmp_node;
90 pbqp_edge_t *tmp_edge;
100 src_is_src = src_edge->src == node;
101 tgt_is_src = tgt_edge->src == node;
104 src_mat = src_edge->costs;
105 tgt_mat = tgt_edge->costs;
107 node_vec = node->costs;
109 row_index = src_node->solution;
110 col_index = tgt_node->solution;
112 vec = vector_copy(pbqp, node_vec);
115 vector_add_matrix_col(vec, src_mat, row_index);
117 vector_add_matrix_row(vec, src_mat, row_index);
121 vector_add_matrix_col(vec, tgt_mat, col_index);
123 vector_add_matrix_row(vec, tgt_mat, col_index);
126 node->solution = vector_get_min_index(vec);
129 if (pbqp->dump_file) {
130 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
134 obstack_free(&pbqp->obstack, vec);
137 static void back_propagate_RN(pbqp_t *pbqp, pbqp_node_t *node)
139 vector_t *vec = NULL;
140 pbqp_node_t *neighbor = NULL;
141 pbqp_edge_t *edge = NULL;
142 unsigned edge_index = 0;
146 vec = vector_copy(pbqp, node->costs);
148 for(edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
149 /* get neighbor node */
150 edge = node->edges[edge_index];
151 neighbor = edge->src == node ? edge->tgt : edge->src;
153 /* node is edge src node */
154 if(edge->src == node)
155 vector_add_matrix_col(vec, edge->costs, neighbor->solution);
156 /* node is edge tgt node */
158 vector_add_matrix_row(vec, edge->costs, neighbor->solution);
161 assert(vector_get_min(vec) != INF_COSTS);
162 node->solution = vector_get_min_index(vec);
165 if (pbqp->dump_file) {
166 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
170 obstack_free(&pbqp->obstack, vec);
173 static void back_propagate_ld(pbqp_t *pbqp)
176 unsigned node_len = node_bucket_get_length(reduced_bucket);
181 if (pbqp->dump_file) {
182 pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
186 for (node_index = node_len; node_index > 0; --node_index) {
187 pbqp_node_t *node = reduced_bucket[node_index - 1];
189 switch (pbqp_node_get_degree(node)) {
191 back_propagate_RI(pbqp, node);
194 back_propagate_RII(pbqp, node);
197 back_propagate_RN(pbqp, node);
203 static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo)
205 pbqp_node_t *node = NULL;
210 /* get last element from reverse perfect elimination order */
211 node = (pbqp_node_t*)plist_last(rpeo)->data;
212 /* remove element from reverse perfect elimination order */
213 plist_erase(rpeo, plist_last(rpeo));
214 /* insert node at the beginning of rpeo so the rpeo already exits after pbqp solving */
215 plist_insert_front(rpeo, node);
216 } while(node_is_reduced(node));
218 assert(pbqp_node_get_degree(node) > 2);
220 /* Check whether we can merge a neighbor into the current node. */
221 apply_RM(pbqp, node);
224 static void apply_RN_co_without_selection(pbqp_t *pbqp)
234 if (node_is_reduced(node))
238 if (pbqp->dump_file) {
240 sprintf(txt, "RN-Reduction of Node n%d", node->index);
241 pbqp_dump_section(pbqp->dump_file, 2, txt);
242 pbqp_dump_graph(pbqp);
246 /* Disconnect neighbor nodes */
247 for(edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
249 pbqp_node_t *neighbor;
251 /* get neighbor node */
252 edge = node->edges[edge_index];
254 neighbor = edge->src == node ? edge->tgt : edge->src;
256 assert(neighbor != node);
258 if(!is_connected(neighbor, edge))
261 disconnect_edge(neighbor, edge);
262 reorder_node_after_edge_deletion(neighbor);
265 /* Remove node from old bucket */
266 node_bucket_remove(&node_buckets[3], node);
268 /* Add node to back propagation list. */
269 node_bucket_insert(&reduced_bucket, node);
272 static void apply_heuristic_reductions_co(pbqp_t *pbqp, plist_t *rpeo)
276 ir_timer_t *t_edge = ir_timer_new();
277 ir_timer_t *t_r1 = ir_timer_new();
278 ir_timer_t *t_r2 = ir_timer_new();
279 ir_timer_t *t_rn = ir_timer_new();
283 if (edge_bucket_get_length(edge_bucket) > 0) {
285 ir_timer_start(t_edge);
291 ir_timer_stop(t_edge);
293 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
295 ir_timer_start(t_r1);
303 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
305 ir_timer_start(t_r2);
313 } else if (merged_node != NULL) {
315 ir_timer_start(t_rn);
318 apply_RN_co_without_selection(pbqp);
323 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
325 ir_timer_start(t_rn);
328 merge_into_RN_node(pbqp, rpeo);
335 printf("PBQP RE reductions: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_edge) / 1000.0);
336 printf("PBQP R1 reductions: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_r1) / 1000.0);
337 printf("PBQP R2 reductions: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_r2) / 1000.0);
338 printf("PBQP RN reductions: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_rn) / 1000.0);
346 void solve_pbqp_heuristical_co_ld(pbqp_t *pbqp, plist_t *rpeo)
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_heuristic_reductions_co(pbqp, rpeo);
362 pbqp->solution = determine_solution(pbqp);
365 fh = fopen("solutions.pb", "a");
366 #if KAPS_USE_UNSIGNED
367 fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
368 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
369 pbqp->num_rm, pbqp->num_rn);
371 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
372 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
373 pbqp->num_rm, pbqp->num_rn);
378 /* Solve reduced nodes. */
379 back_propagate_ld(pbqp);