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

   1 /**
   2  * Chordal register allocation.
   3  * @author Sebastian Hack
   4  * @date 8.12.2004
   5  */
   6
   7 #include <ctype.h>
   8
   9 #include "obst.h"
  10 #include "list.h"
  11 #include "bitset.h"
  12 #include "iterator.h"
  13
  14 #include "irmode_t.h"
  15 #include "irprintf_t.h"
  16 #include "irgwalk.h"
  17 #include "irgraph.h"
  18 #include "irdump.h"
  19 #include "irdom.h"
  20 #include "debug.h"
  21 #include "xmalloc.h"
  22
  23 #include "beutil.h"
  24 #include "besched.h"
  25 #include "bera_t.h"
  26 #include "benumb_t.h"
  27 #include "besched_t.h"
  28 #include "belive_t.h"
  29
  30
  31
  32 #undef DUMP_INTERVALS
  33 #undef DUMP_PRESSURE
  34 #define DUMP_IFG
  35
  36 #define BUILD_GRAPH
  37
  38 #ifdef USE_OLD_PHI_INTERFERENCE
  39 #undef BUILD_GRAPH
  40 #define BUILD_GRAPH
  41 #endif
  42
  43
  44 #define TEST_COLORS 2048
  45
  46 static firm_dbg_module_t *dbg;
  47
  48 /** An interval border. */
  49 typedef struct _border_t {
  50         struct list_head list;          /**< list head for queuing. */
  51         const ir_node *irn;                             /**< The node. */
  52         unsigned step;                                          /**< The number equal to the interval border. */
  53         unsigned is_def : 1;                    /**< Does this border denote a use or a def. */
  54 } border_t;
  55
  56 typedef struct _env_t {
  57         struct obstack obst;    /**< An obstack for temporary storage. */
  58         set *graph;                                             /**< The interference graph. */
  59         bitset_t *live;                 /**< A live bitset to use in every block. */
  60         bitset_t *processed;    /**< A set marking processed blocks. */
  61         bitset_t *colors;                       /**< The color mask. */
  62         bitset_t *in_colors;    /**< Colors used by live in values. */
  63         int colors_n;                                   /**< The number of colors. */
  64 } env_t;
  65
  66 typedef struct _be_chordal_dump_params_t {
  67         int x_dist;
  68         int y_dist;
  69         double font_scale;
  70 } be_chordal_dump_params_t;
  71
  72 static const be_chordal_dump_params_t dump_params = {
  73         30,
  74         10,
  75         4
  76 };
  77
  78 static void draw_interval_graphs(ir_node *block,
  79                 struct list_head *border_head,
  80                 const be_chordal_dump_params_t *params)
  81 {
  82         int i;
  83         int x_dist = params->x_dist;
  84         int y_dist = params->y_dist;
  85         ir_graph *irg = get_irn_irg(block);
  86
  87         FILE *f;
  88         char buf[1024];
  89
  90         ir_snprintf(buf, sizeof(buf), "intv_%s_bl%N.eps",
  91                         get_entity_name(get_irg_entity(irg)), block);
  92
  93         if((f = fopen(buf, "wt")) != NULL) {
  94                 border_t *b;
  95                 int *seen = xcalloc(get_graph_node_count(irg), sizeof(seen[0]));
  96                 int last_pos = list_empty(border_head) ? 0 : list_entry(border_head->prev, border_t, list)->step;
  97                 int max_col = 0;
  98
  99                 list_for_each_entry_reverse(border_t, b, border_head, list) {
 100                         const ir_node *irn = b->irn;
 101                         int col = get_irn_color(irn);
 102                         max_col = max_col > col ? max_col : col;
 103                 }
 104
 105                 fprintf(f, "%%!PS-Adobe-2.0\n");
 106                 fprintf(f, "%%%%BoundingBox: -10 -10 %d %d\n",
 107                                 x_dist * last_pos + x_dist, y_dist * max_col + y_dist);
 108                 fprintf(f, "/mainfont /Courier findfont %f scalefont def\n", params->font_scale);
 109                 fprintf(f, "mainfont setfont\n");
 110                 fprintf(f, "0.2 setlinewidth\n");
 111
 112                 for(i = 0; i <= last_pos; ++i) {
 113                         fprintf(f, "0 0 0 setrgbcolor\n");
 114                         fprintf(f, "%d %d moveto\n", i * x_dist, -2);
 115                         fprintf(f, "%d %d lineto\n", i * x_dist, max_col * y_dist + 2);
 116                         fprintf(f, "stroke\n");
 117                 }
 118                 fprintf(f, "0.5 setlinewidth\n");
 119
 120                 list_for_each_entry_reverse(border_t, b, border_head, list) {
 121                         const ir_node *irn = b->irn;
 122                         int nr = get_irn_graph_nr(irn);
 123
 124                         if(b->is_def)
 125                                 seen[nr] = b->step;
 126                         else {
 127                                 int col = get_irn_color(irn);
 128
 129                                 int pos = last_pos - seen[nr];
 130                                 int end_pos = last_pos - b->step;
 131                                 int live_in = is_live_in(block, irn);
 132                                 int live_end = is_live_end(block, irn);
 133                                 int y_val = y_dist * col;
 134
 135                                 int red = 0;
 136                                 int green = live_end;
 137                                 int blue = live_in;
 138
 139                                 fprintf(f, "0 0 0 setrgbcolor\n");
 140                                 fprintf(f, "%d %d moveto\n", x_dist * pos + 2, y_val + 2);
 141                                 ir_fprintf(f, "(%n/%d%s) show\n", irn, nr, is_phi_operand(irn) ? "*" : "");
 142                                 fprintf(f, "%d %d %d setrgbcolor\n", red, green, blue);
 143                                 fprintf(f, "%d %d moveto\n", x_dist * pos, y_val);
 144                                 fprintf(f, "%d %d lineto\n", (x_dist * end_pos) - 5, y_val);
 145                                 fprintf(f, "stroke\n");
 146                         }
 147                 }
 148
 149                 free(seen);
 150                 fclose(f);
 151         }
 152 }
 153
 154 #ifdef BUILD_GRAPH
 155
 156 typedef struct _if_edge_t {
 157         int src, tgt;
 158 } if_edge_t;
 159
 160 #define IF_EDGE_HASH(e) ((e)->src)
 161
 162 static int if_edge_cmp(const void *p1, const void *p2, size_t size)
 163 {
 164         const if_edge_t *e1 = p1;
 165         const if_edge_t *e2 = p2;
 166
 167         return !(e1->src == e2->src && e1->tgt == e2->tgt);
 168 }
 169
 170 static INLINE if_edge_t *edge_init(if_edge_t *edge, int src, int tgt)
 171 {
 172         /* Bring the smaller entry to src. */
 173         if(src > tgt) {
 174                 edge->src = tgt;
 175                 edge->tgt = src;
 176         } else {
 177                 edge->src = src;
 178                 edge->tgt = tgt;
 179         }
 180
 181         return edge;
 182 }
 183
 184 static INLINE void add_if(const env_t *env, int src, int tgt)
 185 {
 186         if_edge_t edge;
 187         edge_init(&edge, src, tgt);
 188         set_insert(env->graph, &edge, sizeof(edge), IF_EDGE_HASH(&edge));
 189 }
 190
 191 static INLINE int are_connected(const env_t *env, int src, int tgt)
 192 {
 193         if_edge_t edge;
 194         edge_init(&edge, src, tgt);
 195         return set_find(env->graph, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL;
 196 }
 197
 198 static void dump_ifg(set *edges, const char *filename)
 199 {
 200         FILE *f;
 201
 202         if((f = fopen(filename, "wt")) != NULL) {
 203                 if_edge_t *edge;
 204
 205                 fprintf(f, "graph G {\n");
 206
 207                 for(edge = set_first(edges); edge; edge = set_next(edges)) {
 208                         fprintf(f, "i\tn%d -- n%d\n", edge->src, edge->tgt);
 209                 }
 210
 211                 fprintf(f, "}\n");
 212                 fclose(f);
 213         }
 214
 215 }
 216
 217 #endif /* USE_OLD_PHI_INTERFERENCE || BUILD_GRAPH */
 218
 219 static INLINE border_t *border_add(env_t *env, struct list_head *head,
 220                         const ir_node *irn, int step, int is_def)
 221 {
 222         border_t *b = obstack_alloc(&env->obst, sizeof(*b));
 223         b->is_def = is_def;
 224         b->irn = irn;
 225         b->step = step;
 226         list_add_tail(&b->list, head);
 227         return b;
 228 }
 229
 230 static void block_alloc(ir_node *block, void *env_ptr)
 231 {
 232         env_t *env = env_ptr;
 233         struct obstack *obst = &env->obst;
 234         void *obstack_level = obstack_base(obst);
 235         bitset_t *live = env->live;
 236         bitset_t *colors = env->colors;
 237         bitset_t *in_colors = env->in_colors;
 238         bitset_t *used_colors = bitset_malloc(env->colors_n);
 239         bitset_t *tmp_colors = bitset_obstack_alloc(obst, env->colors_n);
 240         ir_graph *irg = get_irn_irg(block);
 241
 242         int i, n;
 243         unsigned step = 0;
 244         int block_nr = get_block_graph_nr(block);
 245         const ir_node *irn;
 246         border_t *b;
 247         struct list_head head;
 248         pset *live_in = get_live_in(block);
 249         pset *live_end = get_live_end(block);
 250         ir_node *idom = get_Block_idom(block);
 251
 252         /*
 253          * Check, if this block has already been processed, if true, return
 254          * immediately.
 255          */
 256         if(bitset_is_set(env->processed, block_nr))
 257                 return;
 258
 259         /*
 260          * Ensure, that the immediate dominator of this block is allocated
 261          * before this block, since the values live in at this block are
 262          * defined in the dominators of this block. Coloring the dominators
 263          * thus is vital before coloring this block.
 264          */
 265         if(idom)
 266                 block_alloc(idom, env);
 267
 268         /* Clear the live and allocate the color bitset. */
 269         bitset_clear_all(live);
 270         bitset_clear_all(colors);
 271         bitset_clear_all(in_colors);
 272
 273         INIT_LIST_HEAD(&head);
 274
 275         /*
 276          * Make final uses of all values live out of the block.
 277          * They are neccessary to build up real intervals.
 278          */
 279         for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
 280                 DBG((dbg, LEVEL_3, "Making live: %n/%d\n", irn, get_irn_graph_nr(irn)));
 281                 bitset_set(live, get_irn_graph_nr(irn));
 282                 if(!is_Phi(irn) && is_allocatable_irn(irn))
 283                         border_add(env, &head, irn, step, 0);
 284         }
 285
 286         ++step;
 287
 288         /*
 289          * Determine the last uses of a value inside the block, since they are
 290          * relevant for the interval borders.
 291          */
 292         sched_foreach_reverse(block, irn) {
 293                 DBG((dbg, LEVEL_1, "insn: %n\n", irn));
 294                 DBG((dbg, LEVEL_2, "live: %b\n", live));
 295
 296                 set_irn_color(irn, NO_COLOR);
 297
 298                 /*
 299                  * If the node defines a datab value, i.e. something, registers must
 300                  * be allocated for, add a new def border to the border list.
 301                  */
 302                 if(is_allocatable_irn(irn)) {
 303                         int nr = get_irn_graph_nr(irn);
 304
 305                         bitset_clear(live, nr);
 306                         border_add(env, &head, irn, step, 1);
 307
 308 #ifdef BUILD_GRAPH
 309                         {
 310                                 unsigned long elm;
 311                                 bitset_foreach(live, elm) {
 312                                         int live_nr = (int) elm;
 313                                         ir_node *live_irn = get_irn_for_graph_nr(irg, live_nr);
 314                                         if(is_phi_operand(live_irn)) {
 315                                                 add_if(env, nr, live_nr);
 316                                         }
 317                                 }
 318                         }
 319 #endif
 320                 }
 321
 322                 /*
 323                  * If the node is no phi node we can examine the uses.
 324                  */
 325                 if(!is_Phi(irn)) {
 326                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 327                                 ir_node *op = get_irn_n(irn, i);
 328
 329                                 if(is_allocatable_irn(op)) {
 330                                         int nr = get_irn_graph_nr(op);
 331
 332                                         DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %n\n", i, op));
 333
 334                                         if(!bitset_is_set(live, nr)) {
 335                                                 border_add(env, &head, op, step, 0);
 336                                                 bitset_set(live, nr);
 337                                         }
 338                                 }
 339                         }
 340                 }
 341
 342                 ++step;
 343         }
 344
 345         bitset_clear_all(live);
 346
 347         /*
 348          * Add initial defs for all values live in.
 349          * Since their colors have already been assigned (The dominators were
 350          * allocated before), we have to mark their colors as used also.
 351          */
 352         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 353                 if(is_allocatable_irn(irn)) {
 354                         int col = get_irn_color(irn);
 355
 356                         /* Mark the color of the live in value as used. */
 357                         assert(is_color(col) && "Node must have been assigned a color.");
 358                         bitset_set(colors, col);
 359                         bitset_set(in_colors, col);
 360                         bitset_set(used_colors, col);
 361
 362                         /* Mark the value live in. */
 363                         bitset_set(live, get_irn_graph_nr(irn));
 364
 365                         /* Add the def */
 366                         border_add(env, &head, irn, step, 1);
 367                 }
 368         }
 369
 370         DBG((dbg, LEVEL_4, "usedef chain for block %n\n", block));
 371         list_for_each_entry(border_t, b, &head, list) {
 372                 DBG((dbg, LEVEL_4, "\t%s %n %d\n", b->is_def ? "def" : "use", b->irn, get_irn_graph_nr(b->irn)));
 373         }
 374
 375         /*
 376          * Mind that the sequence of defs from back to front defines a perfect
 377          * elimination order. So, coloring the definitions from first to last
 378          * will work.
 379          */
 380         list_for_each_entry_reverse(border_t, b, &head, list) {
 381                 const ir_node *irn = b->irn;
 382                 int nr = get_irn_graph_nr(irn);
 383
 384                 /*
 385                  * Assign a color, if it is a local def. Global defs already have a
 386                  * color.
 387                  */
 388                 if(b->is_def && !is_live_in(block, irn)) {
 389                         ra_node_info_t *ri = get_ra_node_info(irn);
 390                         int col = NO_COLOR;
 391
 392                         /*
 393                          * Try to assign live out values colors which are not used by live
 394                          * in values.
 395                          */
 396                         if(is_live_out(block, irn)) {
 397                                 bitset_copy(tmp_colors, colors);
 398                                 bitset_andnot(tmp_colors, in_colors);
 399                                 col = bitset_next_clear(tmp_colors, 0);
 400                         }
 401
 402                         /* If a color is not yet assigned, do it now. */
 403                         if(!is_color(col))
 404                                 col = bitset_next_clear(colors, 0);
 405
 406                         assert(!is_color(get_irn_color(irn)) && "Color must not have assigned");
 407                         assert(!bitset_is_set(live, nr) && "Value def must not have been encountered");
 408
 409                         bitset_set(colors, col);
 410                         bitset_set(used_colors, col);
 411                         bitset_set(live, nr);
 412
 413                         ri->color = col;
 414                         ri->pressure = bitset_popcnt(colors);
 415
 416                         DBG((dbg, LEVEL_1, "\tassigning color %d to %n\n", col, irn));
 417                 }
 418
 419                 /* Clear the color upon a use. */
 420                 else if(!b->is_def) {
 421                         int col = get_irn_color(irn);
 422
 423                         assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 424                         assert(is_color(col) && "A color must have been assigned");
 425
 426                         bitset_clear(colors, col);
 427                         bitset_clear(live, nr);
 428                 }
 429         }
 430
 431 #ifdef DUMP_INTERVALS
 432         draw_interval_graphs(block, &head, &dump_params);
 433 #endif
 434
 435 #ifdef DUMP_PRESSURE
 436         {
 437                 char buf[128];
 438                 FILE *f;
 439
 440                 ir_snprintf(buf, sizeof(buf), "pres_%s_bl_%N.txt",
 441                                 get_entity_name(get_irg_entity(irg)), block);
 442
 443                 if((f = fopen(buf, "wt")) != NULL) {
 444                         sched_foreach_reverse(block, irn) {
 445                                 if(is_allocatable_irn(irn))
 446                                         ir_fprintf(f, "\"%n\" %d %d\n", irn, sched_get_time_step(irn),
 447                                                         get_ra_node_info(irn)->pressure);
 448
 449                         }
 450                         fclose(f);
 451                 }
 452         }
 453 #endif
 454
 455
 456         /*
 457          * Allocate the used colors array in the blocks ra info structure and
 458          * fill it.
 459          */
 460         get_ra_block_info(block)->used_colors = used_colors;
 461
 462         /* Mark this block has processed. */
 463         bitset_set(env->processed, block_nr);
 464
 465         /* Reset the obstack to its initial level */
 466         obstack_free(obst, obstack_level);
 467 }
 468
 469 void be_ra_chordal_init(void)
 470 {
 471         dbg = firm_dbg_register(DBG_BERA);
 472         firm_dbg_set_mask(dbg, -1);
 473 }
 474
 475 void be_ra_chordal(ir_graph *irg)
 476 {
 477         int node_count = get_graph_node_count(irg);
 478         env_t *env = malloc(sizeof(*env));
 479
 480         if(get_irg_dom_state(irg) != dom_consistent)
 481                 compute_doms(irg);
 482
 483         obstack_init(&env->obst);
 484
 485 #ifdef BUILD_GRAPH
 486         env->graph = new_set(if_edge_cmp, node_count);
 487 #endif
 488
 489         env->live = bitset_obstack_alloc(&env->obst, node_count);
 490         env->processed = bitset_obstack_alloc(&env->obst, get_graph_block_count(irg));
 491         env->colors = bitset_obstack_alloc(&env->obst, TEST_COLORS);
 492         env->in_colors = bitset_obstack_alloc(&env->obst, TEST_COLORS);
 493         env->colors_n = TEST_COLORS;
 494
 495         irg_block_walk_graph(irg, block_alloc, NULL, env);
 496         obstack_free(&env->obst, NULL);
 497
 498 #ifdef DUMP_IFG
 499         {
 500                 char buf[128];
 501
 502                 ir_snprintf(buf, sizeof(buf), "ifg_%s.dot", get_entity_name(get_irg_entity(irg)));
 503                 dump_ifg(env->graph, buf);
 504         }
 505 #endif
 506
 507         set_irg_ra_link(irg, env);
 508 }
 509
 510 void be_ra_chordal_done(ir_graph *irg)
 511 {
 512         env_t *env = get_irg_ra_link(irg);
 513
 514 #ifdef BUILD_GRAPH
 515         free(env->graph);
 516 #endif
 517         free(env);
 518 }
 519
 520 int phi_ops_interfere(const ir_node *a, const ir_node *b)
 521 {
 522 #ifdef USE_OLD_PHI_INTERFERENCE
 523         ir_graph *irg = get_irn_irg(a);
 524         env_t *env = get_irg_ra_link(irg);
 525
 526         assert(irg == get_irn_irg(b) && "Both nodes must be in the same graph");
 527
 528         return are_connected(env, get_irn_graph_nr(a), get_irn_graph_nr(b));
 529 #else
 530         return values_interfere(a, b);
 531 #endif /* USE_OLD_PHI_INTERFERENCE */
 532 }