nsz Git - libfirm/blob - ir/kaps/heuristical.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Heuristic PBQP solver.
   9  * @date    02.10.2008
  10  * @author  Sebastian Buchwald
  11  */
  12 #include "config.h"
  13
  14 #include "adt/array.h"
  15 #include "assert.h"
  16 #include "error.h"
  17
  18 #include "bucket.h"
  19 #include "heuristical.h"
  20 #include "optimal.h"
  21 #if KAPS_DUMP
  22 #include "html_dumper.h"
  23 #endif
  24 #include "kaps.h"
  25 #include "matrix.h"
  26 #include "pbqp_edge.h"
  27 #include "pbqp_edge_t.h"
  28 #include "pbqp_node.h"
  29 #include "pbqp_node_t.h"
  30 #include "vector.h"
  31
  32 #include "timing.h"
  33
  34 static void apply_RN(pbqp_t *pbqp)
  35 {
  36         pbqp_node_t *node      = NULL;
  37         unsigned     min_index = 0;
  38
  39         assert(pbqp);
  40
  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);
  44
  45 #if KAPS_DUMP
  46         if (pbqp->dump_file) {
  47                 char     txt[100];
  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);
  51         }
  52 #endif
  53
  54         min_index = get_local_minimal_alternative(pbqp, node);
  55
  56 #if KAPS_DUMP
  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);
  60         }
  61 #endif
  62
  63 #if KAPS_STATISTIC
  64         FILE *fh = fopen("solutions.pb", "a");
  65         fprintf(fh, "[%u]", min_index);
  66         fclose(fh);
  67         pbqp->num_rn++;
  68 #endif
  69
  70         /* Now that we found the local minimum set all other costs to infinity. */
  71         select_alternative(node, min_index);
  72 }
  73
  74 static void apply_heuristic_reductions(pbqp_t *pbqp)
  75 {
  76         for (;;) {
  77                 if (edge_bucket_get_length(edge_bucket) > 0) {
  78                         apply_edge(pbqp);
  79                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
  80                         apply_RI(pbqp);
  81                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
  82                         apply_RII(pbqp);
  83                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
  84                         apply_RN(pbqp);
  85                 } else {
  86                         return;
  87                 }
  88         }
  89 }
  90
  91 void solve_pbqp_heuristical(pbqp_t *pbqp)
  92 {
  93         /* Reduce nodes degree ... */
  94         initial_simplify_edges(pbqp);
  95
  96         /* ... and put node into bucket representing their degree. */
  97         fill_node_buckets(pbqp);
  98
  99 #if KAPS_STATISTIC
 100         FILE *fh = fopen("solutions.pb", "a");
 101         fprintf(fh, "Solution");
 102         fclose(fh);
 103 #endif
 104
 105         apply_heuristic_reductions(pbqp);
 106
 107         pbqp->solution = determine_solution(pbqp);
 108
 109 #if KAPS_STATISTIC
 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);
 115         #else
 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);
 119         #endif
 120         fclose(fh);
 121 #endif
 122
 123         /* Solve reduced nodes. */
 124         back_propagate(pbqp);
 125
 126         free_buckets();
 127 }