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