nsz Git - libfirm/blob - ir/be/becopypbqp.c

   1 /*
   2  * becopypbqp.c
   3  *
   4  *  Created on: Aug 28, 2009
   5  *      Author: bersch
   6  */
   7 #include "config.h"
   8
   9 #ifdef FIRM_KAPS
  10
  11 #include "kaps.h"
  12 #include "pbqp_t.h"
  13 #include "vector.h"
  14 #include "matrix.h"
  15 #include "html_dumper.h"
  16 #include "heuristical.h"
  17 #include "pbqp_node_t.h"
  18
  19 #include "becopyopt_t.h"
  20 #include "beifg.h"
  21 #include "beifg_t.h"
  22 #include "bemodule.h"
  23 #include "irprintf_t.h"
  24
  25 #include "error.h"
  26 #include "bitset.h"
  27 #include "pmap.h"
  28
  29 static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
  30 {
  31         FILE *result;
  32         char buf[1024];
  33         size_t i, n;
  34         char *tu_name;
  35
  36         n = strlen(env->birg->main_env->cup_name);
  37         tu_name = XMALLOCN(char, n + 1);
  38         strcpy(tu_name, env->birg->main_env->cup_name);
  39         for (i = 0; i < n; ++i)
  40                 if (tu_name[i] == '.')
  41                         tu_name[i] = '_';
  42
  43         ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
  44         xfree(tu_name);
  45         result = fopen(buf, "wt");
  46         if(result == NULL) {
  47                 panic("Couldn't open '%s' for writing.", buf);
  48         }
  49
  50         return result;
  51 }
  52
  53 static int co_solve_heuristic_pbqp(copy_opt_t *co) {
  54         void *nodes_it  = be_ifg_nodes_iter_alloca(co->cenv->ifg);
  55         void *neigh_it  = be_ifg_neighbours_iter_alloca(co->cenv->ifg);
  56         ir_node *ifg_node, *if_neighb_node;
  57
  58         pbqp *pbqp_problem;
  59         unsigned number_registers = co->cls->n_regs;
  60         unsigned number_nodes = 0;
  61         unsigned int nodeIdx = 0;
  62
  63         bitset_t *ignore_registers;
  64         pmap *map;
  65
  66         // count nodes in ifg
  67         be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
  68                 number_nodes++;
  69         }
  70
  71         // create empty PBQP instance
  72         pbqp_problem = alloc_pbqp(number_nodes);
  73
  74         //
  75         ignore_registers = bitset_malloc(number_registers);
  76         be_put_ignore_regs(co->cenv->birg, co->cls, ignore_registers);
  77
  78         // create map
  79         map = pmap_create_ex(number_nodes);
  80
  81         // add costs vector to nodes
  82         nodeIdx = 0;
  83         be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
  84                 // create costs vector
  85                 struct vector *costs_vector = vector_alloc(pbqp_problem, number_registers);
  86
  87                 // set costs
  88                 unsigned int cnt;
  89                 for(cnt = 0; cnt < costs_vector->len; cnt++) {
  90                         if (bitset_is_set(ignore_registers,cnt)) {
  91                                 vector_set(costs_vector, cnt, INF_COSTS);
  92                         }
  93                         else {
  94                                 if (!arch_reg_out_is_allocatable(ifg_node, arch_register_for_index(co->cls, cnt)))
  95                                 {
  96                                         vector_set(costs_vector, cnt, INF_COSTS);
  97                                 }
  98                                 else {
  99                                         vector_set(costs_vector, cnt, 0);
 100                                 }
 101                         }
 102
 103                         // add description
 104                         vector_set_description(costs_vector, cnt, arch_register_for_index(co->cls, cnt)->name);
 105                 }
 106
 107                 // add costs vector to node
 108                 add_node_costs(pbqp_problem, nodeIdx, costs_vector);
 109
 110                 // insert ir_node and pbqp_node into map
 111                 pmap_insert(map, ifg_node, get_node(pbqp_problem,nodeIdx));
 112
 113                 // increment nodeIndex
 114                 nodeIdx++;
 115         }
 116
 117         be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
 118                 pbqp_node *src_node = pmap_find(map,ifg_node)->value;
 119                 unsigned int srcNodeIdx = src_node->index;
 120
 121                 // add costs matrix between nodes (interference edge)
 122                 be_ifg_foreach_neighbour(co->cenv->ifg, neigh_it, ifg_node, if_neighb_node) {
 123                         pbqp_node *trg_node = pmap_find(map,if_neighb_node)->value;
 124                         if(get_edge(pbqp_problem, srcNodeIdx, trg_node->index) == NULL) {
 125                                 // create costs matrix
 126                                 struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_problem, number_registers, number_registers);
 127
 128                                 // set costs
 129                                 unsigned row, col;
 130                                 for(row = 0; row < number_registers; row++) {
 131                                         for(col = 0; col < number_registers; col++) {
 132                                                 if(row == col) {
 133                                                         pbqp_matrix_set(matrix, row, col, INF_COSTS);
 134                                                 }
 135                                                 else {
 136                                                         pbqp_matrix_set(matrix, row, col, 2);
 137                                                 }
 138                                         }
 139                                 }
 140
 141                                 // add costs matrix to interference edge
 142                                 add_edge_costs(pbqp_problem, srcNodeIdx, trg_node->index , matrix);
 143                         }
 144                 }
 145
 146                 // add costs matrix between nodes (affinety edge)
 147                 affinity_node_t *aff_node = get_affinity_info(co, ifg_node);
 148                 neighb_t *aff_neighb_node;
 149                 if(aff_node != NULL) {
 150                         co_gs_foreach_neighb(aff_node, aff_neighb_node) {
 151                                 pbqp_node *trg_node = pmap_find(map,aff_neighb_node->irn)->value;
 152                                 if(get_edge(pbqp_problem, srcNodeIdx, trg_node->index) == NULL) {
 153                                         // create costs matrix
 154                                         struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_problem, number_registers, number_registers);
 155
 156                                         // set costs
 157                                         unsigned row, col;
 158                                         for(row = 0; row < number_registers; row++) {
 159                                                 for(col = 0; col < number_registers; col++) {
 160                                                         if(row == col) {
 161                                                                 pbqp_matrix_set(matrix, row, col, 0);
 162                                                         }
 163                                                         else {
 164                                                                 pbqp_matrix_set(matrix, row, col, 2);
 165                                                         }
 166                                                 }
 167                                         }
 168
 169                                         // add costs matrix to interference edge
 170                                         add_edge_costs(pbqp_problem, srcNodeIdx, trg_node->index , matrix);
 171                                 }
 172                         }
 173                 }
 174         }
 175
 176 #if KAPS_DUMP
 177         // dump graph before solving pbqp
 178         FILE *file_before = my_open(co->cenv, "", "-before.html");
 179         set_dumpfile(pbqp_problem, file_before);
 180         pbqp_dump_input(pbqp_problem);
 181 #endif
 182
 183
 184         // solve pbqp problem
 185         solve_pbqp_heuristical(pbqp_problem);
 186         //solve_pbqp_brute_force(pbqp_problem);
 187         num solution = get_solution(pbqp_problem);
 188
 189         assert(solution != INF_COSTS && "No PBQP solution found");
 190
 191         // printf("Solution (%s): %d\n",co->name, (int)solution);
 192
 193         // coloring ifg
 194         be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
 195                 pbqp_node *node = pmap_find(map,ifg_node)->value;
 196                 num index = get_node_solution(pbqp_problem, node->index);
 197                 const arch_register_t *reg = arch_register_for_index(co->cls, index);
 198                 arch_set_irn_register(ifg_node, reg);
 199         }
 200
 201 #if KAPS_DUMP
 202         // dump graph after solving pbqp
 203         FILE *file_after = my_open(co->cenv, "", "-after.html");
 204         set_dumpfile(pbqp_problem, file_after);
 205         pbqp_dump_input(pbqp_problem);
 206 #endif
 207
 208
 209         // free pbqp resources
 210 #if KAPS_DUMP
 211         fclose(file_before);
 212         fclose(file_after);
 213 #endif
 214         bitset_free(ignore_registers);
 215         pmap_destroy(map);
 216         free_pbqp(pbqp_problem);
 217
 218         return 0;
 219 }
 220
 221 void be_init_copypbqp(void)
 222 {
 223         static co_algo_info copyheur = {
 224                 co_solve_heuristic_pbqp, 0
 225         };
 226
 227         be_register_copyopt("pbqp", &copyheur);
 228 }
 229
 230 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copypbqp);
 231
 232 #endif