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