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