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

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