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