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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Heuristic PBQP solver.
  23  * @date    02.10.2008
  24  * @author  Sebastian Buchwald
  25  * @version $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "adt/array.h"
  30 #include "assert.h"
  31 #include "error.h"
  32
  33 #include "bucket.h"
  34 #include "heuristical.h"
  35 #include "optimal.h"
  36 #if KAPS_DUMP
  37 #include "html_dumper.h"
  38 #endif
  39 #include "kaps.h"
  40 #include "matrix.h"
  41 #include "pbqp_edge.h"
  42 #include "pbqp_edge_t.h"
  43 #include "pbqp_node.h"
  44 #include "pbqp_node_t.h"
  45 #include "vector.h"
  46
  47 #include "timing.h"
  48
  49 static void apply_RN(pbqp_t *pbqp)
  50 {
  51         pbqp_node_t *node      = NULL;
  52         unsigned     min_index = 0;
  53
  54         assert(pbqp);
  55
  56         /* We want to reduce a node with maximum degree. */
  57         node = get_node_with_max_degree();
  58         assert(pbqp_node_get_degree(node) > 2);
  59
  60 #if KAPS_DUMP
  61         if (pbqp->dump_file) {
  62                 char     txt[100];
  63                 sprintf(txt, "RN-Reduction of Node n%d", node->index);
  64                 dump_section(pbqp->dump_file, 2, txt);
  65                 pbqp_dump_graph(pbqp);
  66         }
  67 #endif
  68
  69         min_index = get_local_minimal_alternative(pbqp, node);
  70
  71 #if KAPS_DUMP
  72         if (pbqp->dump_file) {
  73                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
  74                                         node->index, min_index);
  75         }
  76 #endif
  77
  78 #if KAPS_STATISTIC
  79         FILE *fh = fopen("solutions.pb", "a");
  80         fprintf(fh, "[%u]", min_index);
  81         fclose(fh);
  82         pbqp->num_rn++;
  83 #endif
  84
  85         /* Now that we found the local minimum set all other costs to infinity. */
  86         select_alternative(node, min_index);
  87 }
  88
  89 static void apply_heuristic_reductions(pbqp_t *pbqp)
  90 {
  91         for (;;) {
  92                 if (edge_bucket_get_length(edge_bucket) > 0) {
  93                         apply_edge(pbqp);
  94                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
  95                         apply_RI(pbqp);
  96                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
  97                         apply_RII(pbqp);
  98                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
  99                         apply_RN(pbqp);
 100                 } else {
 101                         return;
 102                 }
 103         }
 104 }
 105
 106 void solve_pbqp_heuristical(pbqp_t *pbqp)
 107 {
 108         /* Reduce nodes degree ... */
 109         initial_simplify_edges(pbqp);
 110
 111         /* ... and put node into bucket representing their degree. */
 112         fill_node_buckets(pbqp);
 113
 114 #if KAPS_STATISTIC
 115         FILE *fh = fopen("solutions.pb", "a");
 116         fprintf(fh, "Solution");
 117         fclose(fh);
 118 #endif
 119
 120         apply_heuristic_reductions(pbqp);
 121
 122         pbqp->solution = determine_solution(pbqp);
 123
 124 #if KAPS_STATISTIC
 125         fh = fopen("solutions.pb", "a");
 126         #if KAPS_USE_UNSIGNED
 127                 fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
 128                                 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 129                                 pbqp->num_rm, pbqp->num_rn);
 130         #else
 131                 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
 132                                 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 133                                 pbqp->num_rm, pbqp->num_rn);
 134         #endif
 135         fclose(fh);
 136 #endif
 137
 138         /* Solve reduced nodes. */
 139         back_propagate(pbqp);
 140
 141         free_buckets();
 142 }