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 "becopypbqp.h"
  12
  13 #include "kaps.h"
  14 #include "pbqp_t.h"
  15 #include "vector.h"
  16 #include "matrix.h"
  17 #include "html_dumper.h"
  18 #include "heuristical.h"
  19 #include "pbqp_node_t.h"
  20
  21 #include "becopyopt_t.h"
  22 #include "beifg.h"
  23 #include "beifg_t.h"
  24 #include "bemodule.h"
  25 #include "irprintf_t.h"
  26
  27 #include "error.h"
  28 #include "bitset.h"
  29 #include "pmap.h"
  30
  31 #include "irdom.h"
  32 #include "besched.h"
  33 #include "irgwalk.h"
  34 #include "plist.h"
  35 #include "pqueue.h"
  36
  37 #include "bearch.h"
  38 #include "iredges.h"
  39
  40
  41 #if KAPS_DUMP
  42 static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
  43 {
  44         FILE *result;
  45         char buf[1024];
  46         size_t i, n;
  47         char *tu_name;
  48
  49         n = strlen(env->birg->main_env->cup_name);
  50         tu_name = XMALLOCN(char, n + 1);
  51         strcpy(tu_name, env->birg->main_env->cup_name);
  52         for (i = 0; i < n; ++i)
  53                 if (tu_name[i] == '.')
  54                         tu_name[i] = '_';
  55
  56         ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
  57         xfree(tu_name);
  58         result = fopen(buf, "wt");
  59         if(result == NULL) {
  60                 panic("Couldn't open '%s' for writing.", buf);
  61         }
  62
  63         return result;
  64 }
  65 #endif
  66
  67 static void insert_into_reverse_peo(ir_node *block, void *data) {
  68         pbqp_co_t *pbqp_co = data;
  69         pqueue_t *queue = new_pqueue();
  70         ir_node   *irn;
  71
  72 //      int cnt = 0;
  73
  74         sched_foreach(block, irn) {
  75                 pbqp_node *node;
  76
  77                 if (get_irn_mode(irn) == mode_T) {
  78                         const ir_edge_t *edge;
  79
  80                         foreach_out_edge(irn, edge) {
  81                                 ir_node *proj = get_edge_src_irn(edge);
  82                                 if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, proj))
  83                                         continue;
  84
  85                                 // get related pbqp_node and insert into reverse peo
  86 //                              node = pmap_find(pbqp_co->map,proj)->value;
  87                                 assert(node && "No corresponding PBQP-Node found!");
  88
  89                                 // insert proj into ordered list
  90                                 pqueue_put(queue,proj, be_ifg_degree(pbqp_co->ifg,proj));
  91 //                              cnt++;
  92 //                              printf("(%d) Index: %d NodeNr: %ld\n", cnt, get_irn_idx(proj), proj->node_nr);
  93                         }
  94
  95                         while(!pqueue_empty(queue)) {
  96                                 // copy proj from ordered list (ordered by their node degree in ifg) into reverse perfect elimination order
  97                                 plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(pqueue_pop_front(queue))));
  98                         }
  99                 } else {
 100                         if (!arch_irn_consider_in_reg_alloc(pbqp_co->cls, irn))
 101                                 continue;
 102
 103                         // get related pbqp_node and insert into reverse peo
 104 //                      node = pmap_find(pbqp_co->map,irn)->value;
 105                         assert(node && "No corresponding PBQP-Node found!");
 106                         plist_insert_back(pbqp_co->rpeo, get_node(pbqp_co->pbqp, get_irn_idx(irn)));
 107 //                      cnt++;
 108 //                      printf("(%d) Index: %d NodeNr: %ld\n", cnt, get_irn_idx(irn), irn->node_nr);
 109                 }
 110         }
 111
 112 //      while(pqueue_length(queue) > 0) {
 113 //              ir_node *node = pqueue_pop_front(queue);
 114 //              printf("Node: %d IFG-Degree: %d\n", get_irn_idx(node), be_ifg_degree(pbqp_co->ifg,node));
 115 //      }
 116
 117         del_pqueue(queue);
 118 }
 119
 120 static int co_solve_heuristic_pbqp(copy_opt_t *co) {
 121         void *nodes_it  = be_ifg_nodes_iter_alloca(co->cenv->ifg);
 122         void *neigh_it  = be_ifg_neighbours_iter_alloca(co->cenv->ifg);
 123         ir_node *ifg_node;
 124         ir_node *if_neighb_node;
 125
 126         pbqp_co_t pbqp_co;
 127
 128         unsigned number_registers = co->cls->n_regs;
 129         unsigned number_nodes = get_irg_last_idx(co->irg);
 130 //      unsigned nodeIdx = 0;
 131
 132 //      // count nodes in ifg
 133 //      be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
 134 //              number_nodes++;
 135 //      }
 136
 137         // create and initialize data structure for pbqp copy min. optimization
 138         pbqp_co.cls = co->cls;
 139         pbqp_co.rpeo = plist_new();;
 140         pbqp_co.map = pmap_create_ex(number_nodes);
 141         pbqp_co.pbqp = alloc_pbqp(number_nodes);
 142         pbqp_co.ignore_reg = bitset_malloc(number_registers);
 143         pbqp_co.ifg = co->cenv->ifg;
 144
 145         // get ignored registers
 146         be_put_ignore_regs(co->cenv->birg, co->cls, pbqp_co.ignore_reg);
 147
 148         // add costs vector to nodes
 149 //      nodeIdx = 0;
 150         be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
 151                 // create costs vector
 152                 struct vector *costs_vector = vector_alloc(pbqp_co.pbqp, number_registers);
 153
 154                 // set costs
 155                 unsigned int cnt;
 156                 for(cnt = 0; cnt < costs_vector->len; cnt++) {
 157                         if (bitset_is_set(pbqp_co.ignore_reg,cnt)) {
 158                                 vector_set(costs_vector, cnt, INF_COSTS);
 159                         }
 160                         else {
 161                                 if (!arch_reg_out_is_allocatable(ifg_node, arch_register_for_index(co->cls, cnt)))
 162                                 {
 163                                         vector_set(costs_vector, cnt, INF_COSTS);
 164                                 }
 165                                 else {
 166                                         vector_set(costs_vector, cnt, 0);
 167                                 }
 168                         }
 169 #if KAPS_ENABLE_VECTOR_NAMES
 170                         // add description
 171                         vector_set_description(costs_vector, cnt, arch_register_for_index(co->cls, cnt)->name);
 172 #endif
 173                 }
 174
 175                 // add costs vector to node
 176                 add_node_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), costs_vector);
 177
 178                 // insert ir_node and pbqp_node into map
 179                 pmap_insert(pbqp_co.map, ifg_node, get_node(pbqp_co.pbqp, get_irn_idx(ifg_node)));
 180
 181 //              // increment nodeIndex
 182 //              nodeIdx++;
 183         }
 184
 185         // add pbqp edges and cost matrix
 186         be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
 187 //              pbqp_node *src_node = pmap_find(pbqp_co.map,ifg_node)->value;
 188 //              unsigned int srcNodeIdx = src_node->index;
 189
 190                 // add costs matrix between nodes (interference edge)
 191                 be_ifg_foreach_neighbour(co->cenv->ifg, neigh_it, ifg_node, if_neighb_node) {
 192 //                      pbqp_node *trg_node = pmap_find(pbqp_co.map,if_neighb_node)->value;
 193                         if(get_edge(pbqp_co.pbqp,get_irn_idx(ifg_node), get_irn_idx(if_neighb_node)) == NULL) {
 194                                 // create costs matrix
 195                                 struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers);
 196
 197                                 // set costs
 198                                 unsigned row, col;
 199                                 for(row = 0; row < number_registers; row++) {
 200                                         for(col = 0; col < number_registers; col++) {
 201                                                 if(row == col) {
 202                                                         pbqp_matrix_set(matrix, row, col, INF_COSTS);
 203                                                 }
 204                                                 else {
 205                                                         pbqp_matrix_set(matrix, row, col, 0);
 206                                                 }
 207                                         }
 208                                 }
 209
 210                                 // add costs matrix to interference edge
 211                                 add_edge_costs(pbqp_co.pbqp, get_irn_idx(ifg_node), get_irn_idx(if_neighb_node) , matrix);
 212                         }
 213                 }
 214
 215                 // add costs matrix between nodes (affinity edge)
 216                 affinity_node_t *aff_node = get_affinity_info(co, ifg_node);
 217                 neighb_t *aff_neighb_node;
 218                 if(aff_node != NULL) {
 219                         co_gs_foreach_neighb(aff_node, aff_neighb_node) {
 220                                 pmap_entry *ptr_pbqp_node = pmap_find(pbqp_co.map,aff_neighb_node->irn);
 221                                 // ignore Unknowns
 222                                 if(ptr_pbqp_node == NULL) {
 223                                         continue;
 224                                 }
 225 //                              pbqp_node *trg_node = ptr_pbqp_node->value;
 226                                 if(get_edge(pbqp_co.pbqp, get_irn_idx(aff_node->irn), get_irn_idx(aff_neighb_node->irn)) == NULL) {
 227                                         // create costs matrix
 228                                         struct pbqp_matrix *matrix = pbqp_matrix_alloc(pbqp_co.pbqp, number_registers, number_registers);
 229
 230                                         // set costs
 231                                         unsigned row, col;
 232                                         for(row = 0; row < number_registers; row++) {
 233                                                 for(col = 0; col < number_registers; col++) {
 234                                                         if(row == col) {
 235                                                                 pbqp_matrix_set(matrix, row, col, 0);
 236                                                         }
 237                                                         else {
 238                                                                 pbqp_matrix_set(matrix, row, col, 2);
 239                                                         }
 240                                                 }
 241                                         }
 242
 243                                         // add costs matrix to interference edge
 244                                         add_edge_costs(pbqp_co.pbqp, get_irn_idx(aff_node->irn), get_irn_idx(aff_neighb_node->irn) , matrix);
 245                                 }
 246                         }
 247                 }
 248         }
 249
 250
 251 //      printf("S %d ------- -------- %s ---------\n",pmap_count(pbqp_co.map), co->name);
 252
 253         // create reverse perfect elimination order
 254         assure_doms(co->irg);
 255         dom_tree_walk_irg(co->irg, insert_into_reverse_peo, NULL, &pbqp_co);
 256
 257 //      printf("E ------- -------- %s ---------\n", co->name);
 258
 259 #if KAPS_DUMP
 260         // dump graph before solving pbqp
 261         FILE *file_before = my_open(co->cenv, "", "-before.html");
 262         set_dumpfile(pbqp_co.pbqp, file_before);
 263         pbqp_dump_input(pbqp_co.pbqp);
 264 #endif
 265
 266
 267         // solve pbqp problem
 268         solve_pbqp_heuristical_co(pbqp_co.pbqp, pbqp_co.rpeo);
 269     num solution = get_solution(pbqp_co.pbqp);
 270
 271     assert(solution != INF_COSTS && "No PBQP solution found");
 272
 273
 274 #if KAPS_DUMP
 275         // dump graph after solving pbqp
 276         FILE *file_after = my_open(co->cenv, "", "-after.html");
 277         set_dumpfile(pbqp_co.pbqp, file_after);
 278         pbqp_dump_input(pbqp_co.pbqp);
 279 #endif
 280
 281         // coloring ifg
 282         be_ifg_foreach_node(co->cenv->ifg, nodes_it, ifg_node) {
 283 //              pbqp_node *node = pmap_find(pbqp_co.map,ifg_node)->value;
 284                 num index = get_node_solution(pbqp_co.pbqp, get_irn_idx(ifg_node));
 285                 const arch_register_t *reg = arch_register_for_index(co->cls, index);
 286                 arch_set_irn_register(ifg_node, reg);
 287         }
 288
 289         // free pbqp resources
 290 #if KAPS_DUMP
 291         fclose(file_before);
 292         fclose(file_after);
 293 #endif
 294         bitset_free(pbqp_co.ignore_reg);
 295         pmap_destroy(pbqp_co.map);
 296         plist_free(pbqp_co.rpeo);
 297         free_pbqp(pbqp_co.pbqp);
 298
 299         return 0;
 300 }
 301
 302 void be_init_copypbqp(void)
 303 {
 304         static co_algo_info copyheur = {
 305                 co_solve_heuristic_pbqp, 0
 306         };
 307
 308         be_register_copyopt("pbqp", &copyheur);
 309 }
 310
 311 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copypbqp);
 312
 313 #endif