nsz Git - libfirm/blob - ir/kaps/heuristical_co.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 for SSA-based register allocation.
  23  * @date    18.09.2009
  24  * @author  Thomas Bersch
  25  */
  26 #include "config.h"
  27
  28 #include "adt/array.h"
  29 #include "assert.h"
  30 #include "error.h"
  31
  32 #include "bucket.h"
  33 #include "heuristical_co.h"
  34 #include "optimal.h"
  35 #if KAPS_DUMP
  36 #include "html_dumper.h"
  37 #endif
  38 #include "kaps.h"
  39 #include "matrix.h"
  40 #include "pbqp_edge.h"
  41 #include "pbqp_edge_t.h"
  42 #include "pbqp_node.h"
  43 #include "pbqp_node_t.h"
  44 #include "vector.h"
  45
  46 #include "plist.h"
  47 #include "timing.h"
  48
  49 static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo)
  50 {
  51         pbqp_node_t *node = NULL;
  52
  53         assert(pbqp);
  54
  55         /* We want to reduce the first node in reverse perfect elimination order. */
  56         do {
  57                 /* get first element from reverse perfect elimination order */
  58                 node = (pbqp_node_t*)plist_first(rpeo)->data;
  59                 /* remove element from reverse perfect elimination order */
  60                 plist_erase(rpeo, plist_first(rpeo));
  61                 /* insert node at the end of rpeo so the rpeo already exits after pbqp solving */
  62                 plist_insert_back(rpeo, node);
  63         } while(node_is_reduced(node));
  64
  65         assert(pbqp_node_get_degree(node) > 2);
  66
  67         /* Check whether we can merge a neighbor into the current node. */
  68         apply_RM(pbqp, node);
  69 }
  70
  71 static void apply_RN_co(pbqp_t *pbqp)
  72 {
  73         pbqp_node_t *node;
  74         unsigned     min_index;
  75
  76         assert(pbqp);
  77
  78         node        = merged_node;
  79         merged_node = NULL;
  80
  81         if (node_is_reduced(node))
  82                 return;
  83
  84 #if KAPS_DUMP
  85         if (pbqp->dump_file) {
  86                 char     txt[100];
  87                 sprintf(txt, "RN-Reduction of Node n%d", node->index);
  88                 pbqp_dump_section(pbqp->dump_file, 2, txt);
  89                 pbqp_dump_graph(pbqp);
  90         }
  91 #endif
  92
  93         min_index = get_local_minimal_alternative(pbqp, node);
  94
  95 #if KAPS_DUMP
  96         if (pbqp->dump_file) {
  97                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
  98                                         node->index, min_index);
  99         }
 100 #endif
 101
 102 #if KAPS_STATISTIC
 103                 FILE *fh = fopen("solutions.pb", "a");
 104                 fprintf(fh, "[%u]", min_index);
 105                 fclose(fh);
 106                 pbqp->num_rn++;
 107 #endif
 108
 109         /* Now that we found the local minimum set all other costs to infinity. */
 110         select_alternative(node, min_index);
 111 }
 112
 113 static void apply_heuristic_reductions_co(pbqp_t *pbqp, plist_t *rpeo)
 114 {
 115         #if KAPS_TIMING
 116                 /* create timers */
 117                 ir_timer_t *t_edge = ir_timer_new();
 118                 ir_timer_t *t_r1   = ir_timer_new();
 119                 ir_timer_t *t_r2   = ir_timer_new();
 120                 ir_timer_t *t_rn   = ir_timer_new();
 121         #endif
 122
 123         for (;;) {
 124                 if (edge_bucket_get_length(edge_bucket) > 0) {
 125                         #if KAPS_TIMING
 126                                 ir_timer_start(t_edge);
 127                         #endif
 128
 129                         apply_edge(pbqp);
 130
 131                         #if KAPS_TIMING
 132                                 ir_timer_stop(t_edge);
 133                         #endif
 134                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
 135                         #if KAPS_TIMING
 136                                 ir_timer_start(t_r1);
 137                         #endif
 138
 139                         apply_RI(pbqp);
 140
 141                         #if KAPS_TIMING
 142                                 ir_timer_stop(t_r1);
 143                         #endif
 144                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
 145                         #if KAPS_TIMING
 146                                 ir_timer_start(t_r2);
 147                         #endif
 148
 149                         apply_RII(pbqp);
 150
 151                         #if KAPS_TIMING
 152                                 ir_timer_stop(t_r2);
 153                         #endif
 154                 } else if (merged_node != NULL) {
 155                         #if KAPS_TIMING
 156                                 ir_timer_start(t_rn);
 157                         #endif
 158
 159                         apply_RN_co(pbqp);
 160
 161                         #if KAPS_TIMING
 162                                 ir_timer_stop(t_rn);
 163                         #endif
 164                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
 165                         #if KAPS_TIMING
 166                                 ir_timer_start(t_rn);
 167                         #endif
 168
 169                         merge_into_RN_node(pbqp, rpeo);
 170
 171                         #if KAPS_TIMING
 172                                 ir_timer_stop(t_rn);
 173                         #endif
 174                 } else {
 175                         #if KAPS_TIMING
 176                                 printf("PBQP RE reductions:           %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_edge) / 1000.0);
 177                                 printf("PBQP R1 reductions:           %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_r1) / 1000.0);
 178                                 printf("PBQP R2 reductions:           %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_r2) / 1000.0);
 179                                 printf("PBQP RN reductions:           %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_rn) / 1000.0);
 180                         #endif
 181
 182                         return;
 183                 }
 184         }
 185 }
 186
 187 void solve_pbqp_heuristical_co(pbqp_t *pbqp, plist_t *rpeo)
 188 {
 189         /* Reduce nodes degree ... */
 190         initial_simplify_edges(pbqp);
 191
 192         /* ... and put node into bucket representing their degree. */
 193         fill_node_buckets(pbqp);
 194
 195         #if KAPS_STATISTIC
 196                 FILE *fh = fopen("solutions.pb", "a");
 197                 fprintf(fh, "Solution");
 198                 fclose(fh);
 199         #endif
 200
 201         apply_heuristic_reductions_co(pbqp, rpeo);
 202
 203         pbqp->solution = determine_solution(pbqp);
 204
 205         #if KAPS_STATISTIC
 206                 fh = fopen("solutions.pb", "a");
 207                 #if KAPS_USE_UNSIGNED
 208                         fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
 209                                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 210                                         pbqp->num_rm, pbqp->num_rn);
 211                 #else
 212                         fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
 213                                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 214                 #endif
 215                 fclose(fh);
 216         #endif
 217
 218         /* Solve reduced nodes. */
 219         back_propagate(pbqp);
 220
 221         free_buckets();
 222 }