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 #undef DUMP_INTERVALS
  35 #undef DUMP_PRESSURE
  36 #undef DUMP_IFG
  37
  38
  39 #ifdef DEBUG_libfirm
  40 #include "fourcc.h"
  41
  42 /* Make a fourcc for border checking. */
  43 #define BORDER_FOURCC                           FOURCC('B', 'O', 'R', 'D')
  44
  45 #endif /* DEBUG_libfirm */
  46
  47 #define TEST_COLORS 2048
  48
  49 static firm_dbg_module_t *dbg;
  50
  51 /**
  52  * Environment for each of the chordal register allocator phases
  53  */
  54 typedef struct _env_t {
  55         struct obstack obst;    /**< An obstack for temporary storage. */
  56 #ifdef BUILD_GRAPH
  57         set *graph;                                             /**< The interference graph. */
  58 #endif
  59
  60         bitset_t *live;                         /**< A liveness bitset. */
  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
  67 typedef struct _be_chordal_dump_params_t {
  68         int x_dist;
  69         int y_dist;
  70         double font_scale;
  71 } be_chordal_dump_params_t;
  72
  73 static const be_chordal_dump_params_t dump_params = {
  74         30,
  75         10,
  76         4
  77 };
  78
  79 #ifdef DUMP_INTERVALS
  80 static void draw_interval_graphs(ir_node *block,
  81                 struct list_head *border_head,
  82                 const be_chordal_dump_params_t *params)
  83 {
  84         int i;
  85         int x_dist = params->x_dist;
  86         int y_dist = params->y_dist;
  87         ir_graph *irg = get_irn_irg(block);
  88
  89         FILE *f;
  90         char buf[1024];
  91
  92         ir_snprintf(buf, sizeof(buf), "intv_%s_bl%N.eps",
  93                         get_entity_name(get_irg_entity(irg)), block);
  94
  95         if((f = fopen(buf, "wt")) != NULL) {
  96                 border_t *b;
  97                 int *seen = xcalloc(get_graph_node_count(irg), sizeof(seen[0]));
  98                 int last_pos = list_empty(border_head) ? 0 : list_entry(border_head->prev, border_t, list)->step;
  99                 int max_col = 0;
 100
 101                 list_for_each_entry_reverse(border_t, b, border_head, list) {
 102                         const ir_node *irn = b->irn;
 103                         int col = get_irn_color(irn);
 104                         max_col = max_col > col ? max_col : col;
 105                 }
 106
 107                 fprintf(f, "%%!PS-Adobe-2.0\n");
 108                 fprintf(f, "%%%%BoundingBox: -10 -10 %d %d\n",
 109                                 x_dist * last_pos + x_dist, y_dist * max_col + y_dist);
 110                 fprintf(f, "/mainfont /Courier findfont %f scalefont def\n", params->font_scale);
 111                 fprintf(f, "mainfont setfont\n");
 112                 fprintf(f, "0.2 setlinewidth\n");
 113
 114                 for(i = 0; i <= last_pos; ++i) {
 115                         fprintf(f, "0 0 0 setrgbcolor\n");
 116                         fprintf(f, "%d %d moveto\n", i * x_dist, -2);
 117                         fprintf(f, "%d %d lineto\n", i * x_dist, max_col * y_dist + 2);
 118                         fprintf(f, "stroke\n");
 119                 }
 120                 fprintf(f, "0.5 setlinewidth\n");
 121
 122                 list_for_each_entry_reverse(border_t, b, border_head, list) {
 123                         const ir_node *irn = b->irn;
 124                         int nr = get_irn_graph_nr(irn);
 125
 126                         if(b->is_def)
 127                                 seen[nr] = b->step;
 128                         else {
 129                                 int col = get_irn_color(irn);
 130
 131                                 int pos = last_pos - seen[nr];
 132                                 int end_pos = last_pos - b->step;
 133                                 int live_in = is_live_in(block, irn);
 134                                 int live_end = is_live_end(block, irn);
 135                                 int y_val = y_dist * col;
 136
 137                                 int red = 0;
 138                                 int green = live_end;
 139                                 int blue = live_in;
 140
 141                                 fprintf(f, "0 0 0 setrgbcolor\n");
 142                                 fprintf(f, "%d %d moveto\n", x_dist * pos + 2, y_val + 2);
 143                                 ir_fprintf(f, "(%n/%d%s) show\n", irn, nr, is_phi_operand(irn) ? "*" : "");
 144                                 fprintf(f, "%d %d %d setrgbcolor\n", red, green, blue);
 145                                 fprintf(f, "%d %d moveto\n", x_dist * pos, y_val);
 146                                 fprintf(f, "%d %d lineto\n", (x_dist * end_pos) - 5, y_val);
 147                                 fprintf(f, "stroke\n");
 148                         }
 149                 }
 150
 151                 free(seen);
 152                 fclose(f);
 153         }
 154 }
 155 #endif
 156
 157 #if 0
 158 typedef struct _tree_layout_info_t {
 159         ir_node *block;
 160         int is_child;
 161         int child_slot;
 162         unsigned x;
 163         unsigned y;
 164         int steps;
 165 } tree_layout_info_t;
 166
 167 typedef struct _tree_layout_params_t {
 168         int interval_dist;
 169         int x_block_dist;
 170         int y_block_dist;
 171         int step_len;
 172 } tree_layout_params_t;
 173
 174 static const tree_layout_params_t tree_layout_params = {
 175         10, 20, 20, 5
 176 };
 177
 178 static void dump_tree_collect(ir_node *block, void *env)
 179 {
 180         ir_block *curr;
 181         struct list_head *border_head;
 182
 183         int pre_num = get_Block_dom_tree_pre_num(block);
 184         tree_layout_info_t *info = env;
 185         tree_layout_info_t *i = &info[pre_num];
 186
 187         i->block = block;
 188         i->child_slot = -1;
 189         i->steps = list_empty(border_head) ? 0 : list_entry(border_head->prev, border_t, list)->step;
 190         i->is_child = 1;
 191
 192         dominates_for_each(block, curr)
 193                 i->is_child = 0;
 194 }
 195
 196 static void dump_tree_assign_x(ir_node *block, void *env)
 197 {
 198         unsigned min_x = -1, max_x = 0;
 199         int n_childs = 0;
 200         ir_block *curr;
 201
 202         int pre_num = get_Block_dom_tree_pre_num(block);
 203         tree_layout_info_t *info = env;
 204         tree_layout_info_t *i = &info[pre_num];
 205
 206         if(i->is_child)
 207                 return;
 208
 209         dominates_for_each(block, curr) {
 210                 tree_layout_info_t *ci = &info[get_Block_dom_tree_pre_num(curr)];
 211                 max_x = MAX(max_x, ci->x);
 212                 min_x = MIN(min_x, ci->x);
 213                 n_childs++;
 214         }
 215
 216         i->x = (max_x - mix_x) / n_childs;
 217 }
 218
 219 static void dump_tree_assign_y(ir_node *block, void *env)
 220 {
 221         unsigned min_x = -1, max_x = 0;
 222         int n_childs = 0;
 223         ir_block *curr;
 224
 225         int pre_num = get_Block_dom_tree_pre_num(block);
 226         tree_layout_info_t *info = env;
 227         tree_layout_info_t *i = &info[pre_num];
 228         ir_block *idom = get_Block_idom(block);
 229
 230         i->y = 0;
 231         if(idom) {
 232                 tree_layout_info_t *idom_info = &info[get_Block_dom_tree_pre_num(idom)];
 233                 i->y = idom_info->y + idom_info->steps * params->step_len + params->y_dist;
 234         }
 235 }
 236
 237 static void draw_block(ir_block *bl, void *env)
 238 {
 239 }
 240
 241 static void dump_interval_tree(ir_graph *irg, const tree_layout_params_t *params)
 242 {
 243         int i, slot;
 244         int n_blocks = get_Block_dom_max_subtree_pre_num(get_irg_start_block(irg));
 245         tree_layout_info_t *info = malloc(sizeof(info[0]) * n_blocks);
 246
 247         /* Fill the info array. */
 248         dom_tree_walk_irg(irg, NULL, dump_tree_collect, info);
 249
 250         /* Assign the child slots. */
 251         for(i = 0, slot = 0; i < n_blocks; ++i) {
 252                 tree_layout_info_t *i = &info[i];
 253                 if(i->is_child) {
 254                         i->child_slot = slot++;
 255                         i->x = i->child_slot * params->max_color * params->interval_dist + params->block_dist;
 256                 }
 257         }
 258
 259         dom_tree_walk_irg(irg, NULL, dump_tree_assign_xy, info);
 260
 261         free(info);
 262 }
 263 #endif
 264
 265 #ifdef BUILD_GRAPH
 266
 267
 268 #define IF_EDGE_HASH(e) ((e)->src)
 269
 270 static int if_edge_cmp(const void *p1, const void *p2, size_t size)
 271 {
 272         const if_edge_t *e1 = p1;
 273         const if_edge_t *e2 = p2;
 274
 275         return !(e1->src == e2->src && e1->tgt == e2->tgt);
 276 }
 277
 278 static INLINE if_edge_t *edge_init(if_edge_t *edge, int src, int tgt)
 279 {
 280         /* Bring the smaller entry to src. */
 281         if(src > tgt) {
 282                 edge->src = tgt;
 283                 edge->tgt = src;
 284         } else {
 285                 edge->src = src;
 286                 edge->tgt = tgt;
 287         }
 288
 289         return edge;
 290 }
 291
 292 static INLINE void add_if(const env_t *env, int src, int tgt)
 293 {
 294         if_edge_t edge;
 295         edge_init(&edge, src, tgt);
 296         set_insert(env->graph, &edge, sizeof(edge), IF_EDGE_HASH(&edge));
 297 }
 298
 299 static INLINE int are_connected(const env_t *env, int src, int tgt)
 300 {
 301         if_edge_t edge;
 302         edge_init(&edge, src, tgt);
 303         return set_find(env->graph, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL;
 304 }
 305
 306 static void dump_ifg(ir_graph *irg, set *edges, const char *filename)
 307 {
 308         static const char *colors[] = {
 309                 "coral",
 310                 "azure",
 311                 "bisque",
 312                 "aliceblue",
 313                 "blanchedalmond",
 314                 "deeppink",
 315                 "cornsilk",
 316                 "blueviolet",
 317                 "floralwhite",
 318                 "hotpink",
 319                 "gainsboro",
 320                 "indianred",
 321                 "cornflowerblue",
 322                 "ghostwhite",
 323                 "lightpink",
 324                 "palegoldenrod",
 325                 "darkslateblue",
 326                 "honeydew",
 327                 "ivory",
 328                 "lavender",
 329                 "mediumvioletred",
 330                 "indigo",
 331                 "lavenderblush",
 332                 "lemonchiffon",
 333                 "linen",
 334                 "pink",
 335                 "mintcream",
 336                 "red",
 337                 "mediumblue",
 338                 "mistyrose",
 339                 "mediumslateblue",
 340                 "moccasin",
 341                 "tomato",
 342                 "forestgreen",
 343                 "midnightblue",
 344                 "navajowhite",
 345                 "navy",
 346                 "oldlace",
 347                 "greenyellow",
 348                 "navyblue",
 349                 "papayawhip",
 350                 "lawngreen",
 351                 "powderblue",
 352                 "peachpuff",
 353                 "seashell",
 354                 "snow",
 355                 "thistle",
 356                 "wheat",
 357                 "darkkhaki",
 358                 "mintcream",
 359                 "khaki",
 360                 "Magentas",
 361                 "whitesmoke",
 362                 "peru",
 363                 "palegreen",
 364                 "blueviolet",
 365                 "rosybrown",
 366                 "saddlebrown",
 367                 "springgreen",
 368                 "darkviolet",
 369                 "darkslategray",
 370                 "dimgray",
 371                 "sienna",
 372                 "gray",
 373                 "tan",
 374                 "gray",
 375                 "mediumvioletred",
 376                 "lightgray",
 377                 "Oranges",
 378                 "cyan",
 379                 "lightslategray",
 380                 "darkorange",
 381                 "slategray",
 382                 "orangered",
 383                 "mediumturquoise",
 384                 "violet",
 385                 "paleturquoise"
 386         };
 387
 388         static const int n_colors = sizeof(colors) / sizeof(colors[0]);
 389
 390         FILE *f;
 391
 392         if((f = fopen(filename, "wt")) != NULL) {
 393                 long pos;
 394                 int n_edges = 0;
 395                 if_edge_t *edge;
 396                 bitset_t *bs = bitset_malloc(get_graph_node_count(irg));
 397
 398                 ir_fprintf(f, "graph \"%F\" {\n", irg);
 399                 fprintf(f, "\tnode [shape=box,style=filled]\n");
 400
 401                 for(edge = set_first(edges); edge; edge = set_next(edges)) {
 402                         bitset_set(bs, edge->src);
 403                         bitset_set(bs, edge->tgt);
 404                         n_edges++;
 405                 }
 406
 407                 fprintf(f, "\tx [label=\"nodes: %lu, edges: %d\"]\n", bitset_popcnt(bs), n_edges);
 408
 409                 bitset_foreach(bs, pos) {
 410                         int nr = (int) pos;
 411                         ir_node *irn = get_irn_for_graph_nr(irg, nr);
 412                         int color = get_irn_color(irn);
 413
 414                         ir_fprintf(f, "\tn%d [label=\"%n\",color=\"%s\"]\n", nr, irn,
 415                                         color >= 0 && color < n_colors ? colors[color] : "black");
 416                 }
 417
 418                 for(edge = set_first(edges); edge; edge = set_next(edges)) {
 419                         fprintf(f, "\tn%d -- n%d [len=5]\n", edge->src, edge->tgt);
 420                 }
 421
 422                 fprintf(f, "}\n");
 423                 fclose(f);
 424
 425                 bitset_free(bs);
 426         }
 427
 428 }
 429
 430 #endif /* BUILD_GRAPH */
 431
 432 /**
 433  * Add an interval border to the list of a block's list
 434  * of interval border.
 435  * @note You always have to create the use before the def.
 436  * @param env The environment.
 437  * @param head The list head to enqueue the borders.
 438  * @param irn The node (value) the border belongs to.
 439  * @param pressure The pressure at this point in time.
 440  * @param step A time step for the border.
 441  * @param is_def Is the border a use or a def.
 442  * @return The created border.
 443  */
 444 static INLINE border_t *border_add(env_t *env, struct list_head *head,
 445                         ir_node *irn, unsigned step, unsigned pressure,
 446                         unsigned is_def, unsigned is_real)
 447 {
 448         border_t *b;
 449
 450         if(!is_def) {
 451                 border_t *def;
 452
 453                 b = obstack_alloc(&env->obst, sizeof(*b));
 454
 455                 /* also allocate the def and tie it to the use. */
 456                 def = obstack_alloc(&env->obst, sizeof(*def));
 457                 b->other_end = def;
 458                 def->other_end = b;
 459
 460                 /*
 461                  * Set the link field of the irn to the def.
 462                  * This strongly relies on the fact, that the use is always
 463                  * made before the def.
 464                  */
 465                 set_irn_link(irn, def);
 466
 467 #ifdef DEBUG_libfirm
 468                 b->magic = BORDER_FOURCC;
 469                 def->magic = BORDER_FOURCC;
 470 #endif
 471         }
 472
 473         /*
 474          * If the def is encountered, the use was made and so was the
 475          * the def node (see the code above). It was placed into the
 476          * link field of the irn, so we can get it there.
 477          */
 478         else {
 479                 b = get_irn_link(irn);
 480
 481 #ifdef DEBUG_libfirm
 482                 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
 483 #endif
 484         }
 485
 486         b->pressure = pressure;
 487         b->is_def = is_def;
 488         b->is_real = is_real;
 489         b->irn = irn;
 490         b->step = step;
 491         list_add_tail(&b->list, head);
 492         DBG((dbg, LEVEL_5, "\t\t%s adding %n, step: %d\n",
 493                                 is_def ? "def" : "use", irn, step));
 494
 495         return b;
 496 }
 497
 498 /**
 499  * Annotate the register pressure to the nodes and compute
 500  * the liveness intervals.
 501  * @param block The block to do it for.
 502  * @param env_ptr The environment.
 503  */
 504 static void pressure(ir_node *block, void *env_ptr)
 505 {
 506 /* Convenience macro for a def */
 507 #define border_def(irn, step, real) \
 508         border_add(env, head, irn, step, pressure--, 1, real)
 509
 510 /* Convenience macro for a use */
 511 #define border_use(irn, step, real) \
 512         border_add(env, head, irn, step, ++pressure, 0, real)
 513
 514         env_t *env = env_ptr;
 515         bitset_t *live = env->live;
 516         ir_node *irn;
 517
 518         int i, n;
 519         unsigned step = 0;
 520         unsigned pressure = 0;
 521         struct list_head *head;
 522         pset *live_in = get_live_in(block);
 523         pset *live_end = get_live_end(block);
 524
 525         DBG((dbg, LEVEL_1, "Computing pressure in block %n\n", block));
 526         bitset_clear_all(live);
 527
 528         /* Set up the border list in the block info */
 529         head = &get_ra_block_info(block)->border_head;
 530         INIT_LIST_HEAD(head);
 531
 532         /*
 533          * Make final uses of all values live out of the block.
 534          * They are neccessary to build up real intervals.
 535          */
 536         for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
 537                 DBG((dbg, LEVEL_3, "\tMaking live: %n/%d\n", irn, get_irn_graph_nr(irn)));
 538                 bitset_set(live, get_irn_graph_nr(irn));
 539                 if(is_allocatable_irn(irn))
 540                         border_use(irn, step, 0);
 541         }
 542
 543         ++step;
 544
 545         /*
 546          * Determine the last uses of a value inside the block, since they are
 547          * relevant for the interval borders.
 548          */
 549         sched_foreach_reverse(block, irn) {
 550                 DBG((dbg, LEVEL_1, "\tinsn: %n, pressure: %d\n", irn, pressure));
 551                 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
 552
 553                 /* Erase the color of each node encountered. */
 554                 set_irn_color(irn, NO_COLOR);
 555
 556                 /*
 557                  * If the node defines a datab value, i.e. something, registers must
 558                  * be allocated for, add a new def border to the border list.
 559                  */
 560                 if(is_allocatable_irn(irn)) {
 561                         int nr = get_irn_graph_nr(irn);
 562
 563                         bitset_clear(live, nr);
 564                         border_def(irn, step, 1);
 565
 566 #ifdef BUILD_GRAPH
 567                         {
 568                                 unsigned long elm;
 569                                 bitset_foreach(live, elm) {
 570                                         int live_nr = (int) elm;
 571                                         add_if(env, nr, live_nr);
 572                                 }
 573                         }
 574 #endif
 575                 }
 576
 577                 /*
 578                  * If the node is no phi node we can examine the uses.
 579                  */
 580                 if(!is_Phi(irn)) {
 581                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 582                                 ir_node *op = get_irn_n(irn, i);
 583
 584                                 if(is_allocatable_irn(op)) {
 585                                         int nr = get_irn_graph_nr(op);
 586
 587                                         DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %n\n", i, op));
 588
 589                                         if(!bitset_is_set(live, nr)) {
 590                                                 border_use(op, step, 1);
 591                                                 bitset_set(live, nr);
 592                                         }
 593                                 }
 594                         }
 595                 }
 596
 597                 ++step;
 598         }
 599
 600         /*
 601          * Add initial defs for all values live in.
 602          */
 603         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 604                 if(is_allocatable_irn(irn)) {
 605
 606                         /* Mark the value live in. */
 607                         bitset_set(live, get_irn_graph_nr(irn));
 608
 609                         /* Add the def */
 610                         border_def(irn, step, 0);
 611                 }
 612         }
 613 }
 614
 615 static void assign(ir_node *block, void *env_ptr)
 616 {
 617         env_t *env = env_ptr;
 618         struct obstack *obst = &env->obst;
 619         bitset_t *live = env->live;
 620         bitset_t *colors = env->colors;
 621         bitset_t *in_colors = env->in_colors;
 622
 623         /* The used colors will remain on the obstack. */
 624         bitset_t *used_colors = bitset_obstack_alloc(obst, env->colors_n);
 625
 626         /* Mark the obstack level and allocate the temporary tmp_colors */
 627         void *obstack_level = obstack_base(obst);
 628         /*bitset_t *tmp_colors = bitset_obstack_alloc(obst, env->colors_n);*/
 629
 630         const ir_node *irn;
 631         border_t *b;
 632         struct list_head *head = &get_ra_block_info(block)->border_head;
 633         pset *live_in = get_live_in(block);
 634
 635         bitset_clear_all(live);
 636         bitset_clear_all(colors);
 637         bitset_clear_all(in_colors);
 638
 639         DBG((dbg, LEVEL_4, "Assigning colors for block %n\n", block));
 640         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 641         list_for_each_entry(border_t, b, head, list) {
 642                 DBG((dbg, LEVEL_4, "\t%s %n/%d\n", b->is_def ? "def" : "use",
 643                                         b->irn, get_irn_graph_nr(b->irn)));
 644         }
 645
 646         /*
 647          * Add initial defs for all values live in.
 648          * Since their colors have already been assigned (The dominators were
 649          * allocated before), we have to mark their colors as used also.
 650          */
 651         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 652                 if(is_allocatable_irn(irn)) {
 653                         int col = get_irn_color(irn);
 654
 655                         /* Mark the color of the live in value as used. */
 656                         assert(is_color(col) && "Node must have been assigned a color.");
 657                         bitset_set(colors, col);
 658                         bitset_set(in_colors, col);
 659                         bitset_set(used_colors, col);
 660
 661                         /* Mark the value live in. */
 662                         bitset_set(live, get_irn_graph_nr(irn));
 663                 }
 664         }
 665
 666         /*
 667          * Mind that the sequence of defs from back to front defines a perfect
 668          * elimination order. So, coloring the definitions from first to last
 669          * will work.
 670          */
 671         list_for_each_entry_reverse(border_t, b, head, list) {
 672                 const ir_node *irn = b->irn;
 673                 int nr = get_irn_graph_nr(irn);
 674
 675                 /*
 676                  * Assign a color, if it is a local def. Global defs already have a
 677                  * color.
 678                  */
 679                 if(b->is_def && !is_live_in(block, irn)) {
 680                         ra_node_info_t *ri = get_ra_node_info(irn);
 681                         int col = NO_COLOR;
 682
 683                         DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors));
 684
 685                         /*
 686                          * Try to assign live out values colors which are not used by live
 687                          * in values.
 688                          */
 689 #if 0
 690                         if(is_live_out(block, irn)) {
 691                                 int next_clear;
 692
 693                                 bitset_copy(tmp_colors, colors);
 694                                 bitset_or(tmp_colors, in_colors);
 695                                 next_clear = bitset_next_clear(tmp_colors, 0);
 696                                 col = next_clear != -1 ? next_clear : NO_COLOR;
 697
 698                                 DBG((dbg, LEVEL_5, "next clear in only outs %b: %d\n", tmp_colors, col));
 699                         }
 700 #endif
 701
 702                         /* If a color is not yet assigned, do it now. */
 703                         if(!is_color(col))
 704                                 col = bitset_next_clear(colors, 0);
 705
 706                         assert(!is_color(get_irn_color(irn)) && "Color must not have assigned");
 707                         assert(!bitset_is_set(live, nr) && "Value def must not have been encountered");
 708
 709                         bitset_set(colors, col);
 710                         bitset_set(used_colors, col);
 711                         bitset_set(live, nr);
 712
 713                         ri->color = col;
 714
 715                         DBG((dbg, LEVEL_1, "\tassigning color %d to %n\n", col, irn));
 716                 }
 717
 718                 /* Clear the color upon a use. */
 719                 else if(!b->is_def) {
 720                         int col = get_irn_color(irn);
 721
 722                         assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 723                         assert(is_color(col) && "A color must have been assigned");
 724
 725                         bitset_clear(colors, col);
 726                         bitset_clear(live, nr);
 727                 }
 728         }
 729
 730 #ifdef DUMP_INTERVALS
 731         draw_interval_graphs(block, head, &dump_params);
 732 #endif
 733
 734 #ifdef DUMP_PRESSURE
 735         {
 736                 char buf[128];
 737                 FILE *f;
 738
 739                 ir_snprintf(buf, sizeof(buf), "pres_%s_bl_%N.txt",
 740                                 get_entity_name(get_irg_entity(irg)), block);
 741
 742                 if((f = fopen(buf, "wt")) != NULL) {
 743                         sched_foreach_reverse(block, irn) {
 744                                 if(is_allocatable_irn(irn))
 745                                         ir_fprintf(f, "\"%n\" %d %d\n", irn, sched_get_time_step(irn),
 746                                                         get_ra_node_info(irn)->pressure);
 747
 748                         }
 749                         fclose(f);
 750                 }
 751         }
 752 #endif
 753
 754
 755         /*
 756          * Allocate the used colors array in the blocks ra info structure and
 757          * fill it.
 758          */
 759         get_ra_block_info(block)->used_colors = used_colors;
 760
 761         /* Free the auxillary data on the obstack. */
 762         obstack_free(obst, obstack_level);
 763 }
 764
 765 void be_ra_chordal_init(void)
 766 {
 767         dbg = firm_dbg_register(DBG_BERA);
 768         firm_dbg_set_mask(dbg, 0);
 769 }
 770
 771 void be_ra_chordal(ir_graph *irg)
 772 {
 773         int node_count = get_graph_node_count(irg);
 774         env_t *env = malloc(sizeof(*env));
 775
 776         if(get_irg_dom_state(irg) != dom_consistent)
 777                 compute_doms(irg);
 778
 779         obstack_init(&env->obst);
 780
 781 #ifdef BUILD_GRAPH
 782         env->graph = new_set(if_edge_cmp, node_count);
 783 #endif
 784
 785         env->live = bitset_obstack_alloc(&env->obst, node_count);
 786         env->colors = bitset_obstack_alloc(&env->obst, TEST_COLORS);
 787         env->in_colors = bitset_obstack_alloc(&env->obst, TEST_COLORS);
 788         env->colors_n = TEST_COLORS;
 789
 790         /* First, determine the pressure */
 791         dom_tree_walk_irg(irg, pressure, NULL, env);
 792
 793         /* Insert probable spills */
 794         be_ra_chordal_spill(irg);
 795
 796         /* Assign the colors */
 797         dom_tree_walk_irg(irg, assign, NULL, env);
 798
 799 #ifdef DUMP_IFG
 800         {
 801                 char buf[128];
 802
 803                 ir_snprintf(buf, sizeof(buf), "ifg_%s.dot", get_entity_name(get_irg_entity(irg)));
 804                 dump_ifg(irg, env->graph, buf);
 805         }
 806 #endif
 807
 808         set_irg_ra_link(irg, env);
 809 }
 810
 811 void be_ra_chordal_done(ir_graph *irg)
 812 {
 813         env_t *env = get_irg_ra_link(irg);
 814
 815 #ifdef BUILD_GRAPH
 816         free(env->graph);
 817 #endif
 818
 819         obstack_free(&env->obst, NULL);
 820         free(env);
 821 }
 822
 823 int phi_ops_interfere(const ir_node *a, const ir_node *b)
 824 {
 825 #ifdef BUILD_GRAPH
 826         ir_graph *irg = get_irn_irg(a);
 827         env_t *env = get_irg_ra_link(irg);
 828
 829         assert(irg == get_irn_irg(b) && "Both nodes must be in the same graph");
 830
 831         return are_connected(env, get_irn_graph_nr(a), get_irn_graph_nr(b));
 832 #else
 833         return values_interfere(a, b);
 834 #endif /* BUILD_GRAPH */
 835 }
 836
 837 #ifdef BUILD_GRAPH
 838 set *be_ra_get_ifg(ir_graph *irg) {
 839         return ((env_t *)get_irg_ra_link(irg))->graph;
 840 }
 841 #endif