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