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