nsz Git - libfirm/blob - 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  * @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_co.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 "plist.h"
  48 #include "timing.h"
  49
  50 static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo)
  51 {
  52         #if KAPS_TIMING
  53                 /* create timers */
  54                 ir_timer_t *t_edge = ir_timer_register("be_pbqp_edges", "pbqp reduce independent edges");
  55                 ir_timer_t *t_r0 = ir_timer_register("be_pbqp_r0", "pbqp R0 reductions");
  56                 ir_timer_t *t_r1 = ir_timer_register("be_pbqp_r1", "pbqp R1 reductions");
  57                 ir_timer_t *t_r2 = ir_timer_register("be_pbqp_r2", "pbqp R2 reductions");
  58                 ir_timer_t *t_rn = ir_timer_register("be_pbqp_rN", "pbqp RN reductions");
  59
  60                 /* reset timers */
  61                 ir_timer_reset(t_edge);
  62                 ir_timer_reset(t_r0);
  63                 ir_timer_reset(t_r1);
  64                 ir_timer_reset(t_r2);
  65                 ir_timer_reset(t_rn);
  66         #endif
  67
  68         for (;;) {
  69                 if (edge_bucket_get_length(edge_bucket) > 0) {
  70                         #if KAPS_TIMING
  71                                 ir_timer_start(t_r0);
  72                         #endif
  73
  74                         apply_edge(pbqp);
  75
  76                         #if KAPS_TIMING
  77                                 ir_timer_stop(t_r0);
  78                         #endif
  79                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
  80                         #if KAPS_TIMING
  81                                 ir_timer_start(t_r1);
  82                         #endif
  83
  84                         apply_RI(pbqp);
  85
  86                         #if KAPS_TIMING
  87                                 ir_timer_stop(t_r1);
  88                         #endif
  89                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
  90                         #if KAPS_TIMING
  91                                 ir_timer_start(t_r2);
  92                         #endif
  93
  94                         apply_RII(pbqp);
  95
  96                         #if KAPS_TIMING
  97                                 ir_timer_stop(t_r2);
  98                         #endif
  99                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
 100                         #if KAPS_TIMING
 101                                 ir_timer_start(t_rn);
 102                         #endif
 103
 104                         apply_RN_co(pbqp, rpeo);
 105
 106                         #if KAPS_TIMING
 107                                 ir_timer_stop(t_rn);
 108                         #endif
 109                 } else {
 110                         #if KAPS_TIMING
 111                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_edge), (double)ir_timer_elapsed_usec(t_edge) / 1000.0);
 112                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r0), (double)ir_timer_elapsed_usec(t_r0) / 1000.0);
 113                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r1), (double)ir_timer_elapsed_usec(t_r1) / 1000.0);
 114                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r2), (double)ir_timer_elapsed_usec(t_r2) / 1000.0);
 115                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_rn), (double)ir_timer_elapsed_usec(t_rn) / 1000.0);
 116                         #endif
 117
 118                         return;
 119                 }
 120         }
 121 }
 122
 123 void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo)
 124 {
 125         /* Reduce nodes degree ... */
 126         initial_simplify_edges(pbqp);
 127
 128         /* ... and put node into bucket representing their degree. */
 129         fill_node_buckets(pbqp);
 130
 131         #if KAPS_STATISTIC
 132                 FILE *fh = fopen("solutions.pb", "a");
 133                 fprintf(fh, "Solution");
 134                 fclose(fh);
 135         #endif
 136
 137         apply_heuristic_reductions_co(pbqp, rpeo);
 138
 139         pbqp->solution = determine_solution(pbqp);
 140
 141         #if KAPS_STATISTIC
 142                 fh = fopen("solutions.pb", "a");
 143                 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
 144                                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 145                                         pbqp->num_rn);
 146                 fclose(fh);
 147         #endif
 148
 149         /* Solve reduced nodes. */
 150         back_propagate(pbqp);
 151
 152         free_buckets();
 153 }
 154
 155 void apply_RN_co(pbqp *pbqp, plist_t *rpeo)
 156 {
 157         pbqp_node   *node         = NULL;
 158         unsigned     min_index    = 0;
 159
 160         assert(pbqp);
 161
 162         /* We want to reduce the first node in reverse perfect elimination order. */
 163         do {
 164                 /* get first element from reverse perfect elimination order */
 165                 node = plist_first(rpeo)->data;
 166                 /* remove element from reverse perfect elimination order */
 167                 plist_erase(rpeo, plist_first(rpeo));
 168                 /* insert node at the end of rpeo so the rpeo already exits after pbqp solving */
 169                 plist_insert_back(rpeo, node);
 170         } while(node_is_reduced(node));
 171
 172         assert(node);
 173         assert(pbqp_node_get_degree(node) > 2);
 174
 175 #if     KAPS_DUMP
 176         if (pbqp->dump_file) {
 177                 char     txt[100];
 178                 sprintf(txt, "RN-Reduction of Node n%d", node->index);
 179                 dump_section(pbqp->dump_file, 2, txt);
 180                 pbqp_dump_graph(pbqp);
 181         }
 182 #endif
 183
 184         min_index = get_local_minimal_alternative(pbqp, node);
 185
 186 #if     KAPS_DUMP
 187         if (pbqp->dump_file) {
 188                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
 189                                         node->index, min_index);
 190         }
 191 #endif
 192
 193 #if KAPS_STATISTIC
 194         if (dump == 0) {
 195                 FILE *fh = fopen("solutions.pb", "a");
 196                 fprintf(fh, "[%u]", min_index);
 197                 fclose(fh);
 198                 pbqp->num_rn++;
 199         }
 200 #endif
 201
 202         /* Now that we found the local minimum set all other costs to infinity. */
 203         select_alternative(node, min_index);
 204 }