X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=heuristical_co.c;h=d5eb0f40171918bfe6bc2fd993e780cc96951dd7;hb=9d8563f82cf2569c101282d893bf912ceaea97c0;hp=f05bdb91a7151c5f185f03df2123e424f2cfe541;hpb=f723e9a536df09b809a7e860c152cc6e3435cc05;p=libfirm
diff --git a/heuristical_co.c b/heuristical_co.c
index f05bdb91a..d5eb0f401 100644
--- a/heuristical_co.c
+++ b/heuristical_co.c
@@ -47,22 +47,70 @@
#include "plist.h"
#include "timing.h"
+static void apply_RN_co(pbqp *pbqp, plist_t *rpeo)
+{
+ pbqp_node *node = NULL;
+ unsigned min_index = 0;
+
+ assert(pbqp);
+
+ /* We want to reduce the first node in reverse perfect elimination order. */
+ do {
+ /* get first element from reverse perfect elimination order */
+ node = plist_first(rpeo)->data;
+ /* remove element from reverse perfect elimination order */
+ plist_erase(rpeo, plist_first(rpeo));
+ /* insert node at the end of rpeo so the rpeo already exits after pbqp solving */
+ plist_insert_back(rpeo, node);
+ } while(node_is_reduced(node));
+
+ assert(node);
+ assert(pbqp_node_get_degree(node) > 2);
+
+#if KAPS_DUMP
+ if (pbqp->dump_file) {
+ char txt[100];
+ sprintf(txt, "RN-Reduction of Node n%d", node->index);
+ dump_section(pbqp->dump_file, 2, txt);
+ pbqp_dump_graph(pbqp);
+ }
+#endif
+#if KAPS_STATISTIC
+ /* Check whether we can merge a neighbor into the current node. */
+ for (min_index = 0; min_index < pbqp_node_get_degree(node); ++min_index) {
+ check_melting_possibility(pbqp, node->edges[min_index]);
+ }
+#endif
+
+ min_index = get_local_minimal_alternative(pbqp, node);
+
+#if KAPS_DUMP
+ if (pbqp->dump_file) {
+ fprintf(pbqp->dump_file, "node n%d is set to %d
\n",
+ node->index, min_index);
+ }
+#endif
+
+#if KAPS_STATISTIC
+ FILE *fh = fopen("solutions.pb", "a");
+ fprintf(fh, "[%u]", min_index);
+ fclose(fh);
+ pbqp->num_rn++;
+#endif
+
+ /* Now that we found the local minimum set all other costs to infinity. */
+ select_alternative(node, min_index);
+}
+
static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo)
{
#if KAPS_TIMING
/* create timers */
- ir_timer_t *t_edge = ir_timer_register("be_pbqp_edges", "pbqp reduce independent edges");
- ir_timer_t *t_r0 = ir_timer_register("be_pbqp_r0", "pbqp R0 reductions");
- ir_timer_t *t_r1 = ir_timer_register("be_pbqp_r1", "pbqp R1 reductions");
- ir_timer_t *t_r2 = ir_timer_register("be_pbqp_r2", "pbqp R2 reductions");
- ir_timer_t *t_rn = ir_timer_register("be_pbqp_rN", "pbqp RN reductions");
-
- /* reset timers */
- ir_timer_reset(t_edge);
- ir_timer_reset(t_r0);
- ir_timer_reset(t_r1);
- ir_timer_reset(t_r2);
- ir_timer_reset(t_rn);
+ ir_timer_t *t_edge = ir_timer_new();
+ ir_timer_t *t_r0 = ir_timer_new();
+ ir_timer_t *t_r1 = ir_timer_new();
+ ir_timer_t *t_r2 = ir_timer_new();
+ ir_timer_t *t_rn = ir_timer_new();
#endif
for (;;) {
@@ -108,11 +156,11 @@ static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo)
#endif
} else {
#if KAPS_TIMING
- printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_edge), (double)ir_timer_elapsed_usec(t_edge) / 1000.0);
- printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r0), (double)ir_timer_elapsed_usec(t_r0) / 1000.0);
- printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r1), (double)ir_timer_elapsed_usec(t_r1) / 1000.0);
- printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r2), (double)ir_timer_elapsed_usec(t_r2) / 1000.0);
- printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_rn), (double)ir_timer_elapsed_usec(t_rn) / 1000.0);
+ printf("pbqp reduce independent edges: %8.3lf msec\n", (double)ir_timer_elapsed_usec(t_edge) / 1000.0);
+ printf("pbqp R0 reductions: %8.3lf msec\n", (double)ir_timer_elapsed_usec(t_r0) / 1000.0);
+ printf("pbqp R1 reductions: %8.3lf msec\n", (double)ir_timer_elapsed_usec(t_r1) / 1000.0);
+ printf("pbqp R2 reductions: %8.3lf msec\n", (double)ir_timer_elapsed_usec(t_r2) / 1000.0);
+ printf("pbqp RN reductions: %8.3lf msec\n", (double)ir_timer_elapsed_usec(t_rn) / 1000.0);
#endif
return;
@@ -140,9 +188,14 @@ void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo)
#if KAPS_STATISTIC
fh = fopen("solutions.pb", "a");
- fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
+ #if KAPS_USE_UNSIGNED
+ fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
- pbqp->num_rn);
+ pbqp->num_rm, pbqp->num_rn);
+ #else
+ fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
+ pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
+ #endif
fclose(fh);
#endif
@@ -151,54 +204,3 @@ void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo)
free_buckets();
}
-
-void apply_RN_co(pbqp *pbqp, plist_t *rpeo)
-{
- pbqp_node *node = NULL;
- unsigned min_index = 0;
-
- assert(pbqp);
-
- /* We want to reduce the first node in reverse perfect elimination order. */
- do {
- /* get first element from reverse perfect elimination order */
- node = plist_first(rpeo)->data;
- /* remove element from reverse perfect elimination order */
- plist_erase(rpeo, plist_first(rpeo));
- /* insert node at the end of rpeo so the rpeo already exits after pbqp solving */
- plist_insert_back(rpeo, node);
- } while(node_is_reduced(node));
-
- assert(node);
- assert(pbqp_node_get_degree(node) > 2);
-
-#if KAPS_DUMP
- if (pbqp->dump_file) {
- char txt[100];
- sprintf(txt, "RN-Reduction of Node n%d", node->index);
- dump_section(pbqp->dump_file, 2, txt);
- pbqp_dump_graph(pbqp);
- }
-#endif
-
- min_index = get_local_minimal_alternative(pbqp, node);
-
-#if KAPS_DUMP
- if (pbqp->dump_file) {
- fprintf(pbqp->dump_file, "node n%d is set to %d
\n",
- node->index, min_index);
- }
-#endif
-
-#if KAPS_STATISTIC
- if (dump == 0) {
- FILE *fh = fopen("solutions.pb", "a");
- fprintf(fh, "[%u]", min_index);
- fclose(fh);
- pbqp->num_rn++;
- }
-#endif
-
- /* Now that we found the local minimum set all other costs to infinity. */
- select_alternative(node, min_index);
-}