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