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->nnr != n2->nnr;
 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 int ifg_has_edge(const ir_graph *irg, if_node_t *n1, if_node_t* n2) {
 297         return are_connected(get_irg_ra_link(irg), n1->nnr, n2->nnr);
 298 }
 299
 300 static void dump_ifg(ir_graph *irg, set *edges, const char *filename)
 301 {
 302         static const char *colors[] = {
 303                 "coral",
 304                 "azure",
 305                 "bisque",
 306                 "aliceblue",
 307                 "blanchedalmond",
 308                 "deeppink",
 309                 "cornsilk",
 310                 "blueviolet",
 311                 "floralwhite",
 312                 "hotpink",
 313                 "gainsboro",
 314                 "indianred",
 315                 "cornflowerblue",
 316                 "ghostwhite",
 317                 "lightpink",
 318                 "palegoldenrod",
 319                 "darkslateblue",
 320                 "honeydew",
 321                 "ivory",
 322                 "lavender",
 323                 "mediumvioletred",
 324                 "indigo",
 325                 "lavenderblush",
 326                 "lemonchiffon",
 327                 "linen",
 328                 "pink",
 329                 "mintcream",
 330                 "red",
 331                 "mediumblue",
 332                 "mistyrose",
 333                 "mediumslateblue",
 334                 "moccasin",
 335                 "tomato",
 336                 "forestgreen",
 337                 "midnightblue",
 338                 "navajowhite",
 339                 "navy",
 340                 "oldlace",
 341                 "greenyellow",
 342                 "navyblue",
 343                 "papayawhip",
 344                 "lawngreen",
 345                 "powderblue",
 346                 "peachpuff",
 347                 "seashell",
 348                 "snow",
 349                 "thistle",
 350                 "wheat",
 351                 "darkkhaki",
 352                 "mintcream",
 353                 "khaki",
 354                 "Magentas",
 355                 "whitesmoke",
 356                 "peru",
 357                 "palegreen",
 358                 "blueviolet",
 359                 "rosybrown",
 360                 "saddlebrown",
 361                 "springgreen",
 362                 "darkviolet",
 363                 "darkslategray",
 364                 "dimgray",
 365                 "sienna",
 366                 "gray",
 367                 "tan",
 368                 "gray",
 369                 "mediumvioletred",
 370                 "lightgray",
 371                 "Oranges",
 372                 "cyan",
 373                 "lightslategray",
 374                 "darkorange",
 375                 "slategray",
 376                 "orangered",
 377                 "mediumturquoise",
 378                 "violet",
 379                 "paleturquoise"
 380         };
 381
 382         static const int n_colors = sizeof(colors) / sizeof(colors[0]);
 383
 384         FILE *f;
 385
 386         if((f = fopen(filename, "wt")) != NULL) {
 387                 bitset_pos_t pos;
 388                 int n_edges = 0;
 389                 if_edge_t *edge;
 390                 bitset_t *bs = bitset_malloc(get_graph_node_count(irg));
 391
 392                 ir_fprintf(f, "graph \"%F\" {\n", irg);
 393                 fprintf(f, "\tnode [shape=box,style=filled]\n");
 394
 395                 for(edge = set_first(edges); edge; edge = set_next(edges)) {
 396                         bitset_set(bs, edge->src);
 397                         bitset_set(bs, edge->tgt);
 398                         n_edges++;
 399                 }
 400
 401                 fprintf(f, "\tx [label=\"nodes: %u, edges: %d\"]\n", bitset_popcnt(bs), n_edges);
 402
 403                 bitset_foreach(bs, pos) {
 404                         int nr = (int) pos;
 405                         ir_node *irn = get_irn_for_graph_nr(irg, nr);
 406                         int color = get_irn_color(irn);
 407
 408                         ir_fprintf(f, "\tn%d [label=\"%n\",color=\"%s\"]\n", nr, irn,
 409                                         color >= 0 && color < n_colors ? colors[color] : "black");
 410                 }
 411
 412                 for(edge = set_first(edges); edge; edge = set_next(edges)) {
 413                         fprintf(f, "\tn%d -- n%d [len=5]\n", edge->src, edge->tgt);
 414                 }
 415
 416                 fprintf(f, "}\n");
 417                 fclose(f);
 418
 419                 bitset_free(bs);
 420         }
 421
 422 }
 423
 424 #endif /* BUILD_GRAPH */
 425
 426 /**
 427  * Add an interval border to the list of a block's list
 428  * of interval border.
 429  * @note You always have to create the use before the def.
 430  * @param env The environment.
 431  * @param head The list head to enqueue the borders.
 432  * @param irn The node (value) the border belongs to.
 433  * @param pressure The pressure at this point in time.
 434  * @param step A time step for the border.
 435  * @param is_def Is the border a use or a def.
 436  * @return The created border.
 437  */
 438 static INLINE border_t *border_add(env_t *env, struct list_head *head,
 439                         ir_node *irn, unsigned step, unsigned pressure,
 440                         unsigned is_def, unsigned is_real)
 441 {
 442         border_t *b;
 443
 444         if(!is_def) {
 445                 border_t *def;
 446
 447                 b = obstack_alloc(&env->obst, sizeof(*b));
 448
 449                 /* also allocate the def and tie it to the use. */
 450                 def = obstack_alloc(&env->obst, sizeof(*def));
 451                 b->other_end = def;
 452                 def->other_end = b;
 453
 454                 /*
 455                  * Set the link field of the irn to the def.
 456                  * This strongly relies on the fact, that the use is always
 457                  * made before the def.
 458                  */
 459                 set_irn_link(irn, def);
 460
 461 #ifdef DEBUG_libfirm
 462                 b->magic = BORDER_FOURCC;
 463                 def->magic = BORDER_FOURCC;
 464 #endif
 465         }
 466
 467         /*
 468          * If the def is encountered, the use was made and so was the
 469          * the def node (see the code above). It was placed into the
 470          * link field of the irn, so we can get it there.
 471          */
 472         else {
 473                 b = get_irn_link(irn);
 474
 475 #ifdef DEBUG_libfirm
 476                 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
 477 #endif
 478         }
 479
 480         b->pressure = pressure;
 481         b->is_def = is_def;
 482         b->is_real = is_real;
 483         b->irn = irn;
 484         b->step = step;
 485         list_add_tail(&b->list, head);
 486         DBG((dbg, LEVEL_5, "\t\t%s adding %n, step: %d\n",
 487                                 is_def ? "def" : "use", irn, step));
 488
 489         return b;
 490 }
 491
 492 /**
 493  * Annotate the register pressure to the nodes and compute
 494  * the liveness intervals.
 495  * @param block The block to do it for.
 496  * @param env_ptr The environment.
 497  */
 498 static void pressure(ir_node *block, void *env_ptr)
 499 {
 500 /* Convenience macro for a def */
 501 #define border_def(irn, step, real) \
 502         border_add(env, head, irn, step, pressure--, 1, real)
 503
 504 /* Convenience macro for a use */
 505 #define border_use(irn, step, real) \
 506         border_add(env, head, irn, step, ++pressure, 0, real)
 507
 508         env_t *env = env_ptr;
 509         bitset_t *live = env->live;
 510         ir_node *irn;
 511
 512         int i, n;
 513         unsigned step = 0;
 514         unsigned pressure = 0;
 515         struct list_head *head;
 516         pset *live_in = get_live_in(block);
 517         pset *live_end = get_live_end(block);
 518   const arch_register_class_t *cls = env->cls;
 519   const arch_isa_if_t *isa = env->isa;
 520
 521         DBG((dbg, LEVEL_1, "Computing pressure in block %n\n", block));
 522         bitset_clear_all(live);
 523
 524         /* Set up the border list in the block info */
 525         head = &get_ra_block_info(block)->border_head;
 526         INIT_LIST_HEAD(head);
 527
 528         /*
 529          * Make final uses of all values live out of the block.
 530          * They are neccessary to build up real intervals.
 531          */
 532         for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
 533                 DBG((dbg, LEVEL_3, "\tMaking live: %n/%d\n", irn, get_irn_graph_nr(irn)));
 534                 bitset_set(live, get_irn_graph_nr(irn));
 535     if(arch_isa_irn_has_reg_class(isa, irn, cls))
 536       border_use(irn, step, 0);
 537         }
 538
 539         ++step;
 540
 541         /*
 542          * Determine the last uses of a value inside the block, since they are
 543          * relevant for the interval borders.
 544          */
 545         sched_foreach_reverse(block, irn) {
 546                 DBG((dbg, LEVEL_1, "\tinsn: %n, pressure: %d\n", irn, pressure));
 547                 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
 548
 549                 /* Erase the color of each node encountered. */
 550                 set_irn_color(irn, NO_COLOR);
 551
 552     /*
 553      * If the node defines some value, which can put into a
 554      * register of the current class, make a border for it.
 555      */
 556                 if(arch_isa_irn_has_reg_class(isa, irn, cls)) {
 557       bitset_pos_t elm;
 558                         int nr = get_irn_graph_nr(irn);
 559
 560                         bitset_clear(live, nr);
 561                         border_def(irn, step, 1);
 562
 563 #ifdef BUILD_GRAPH
 564       bitset_foreach(live, elm)
 565         add_if(env, nr, (int) elm);
 566 #endif
 567                 }
 568
 569                 /*
 570                  * If the node is no phi node we can examine the uses.
 571                  */
 572                 if(!is_Phi(irn)) {
 573                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 574                                 ir_node *op = get_irn_n(irn, i);
 575
 576                                 if(arch_isa_irn_has_reg_class(isa, op, cls)) {
 577                                         int nr = get_irn_graph_nr(op);
 578
 579                                         DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %n\n", i, op));
 580
 581                                         if(!bitset_is_set(live, nr)) {
 582                                                 border_use(op, step, 1);
 583                                                 bitset_set(live, nr);
 584                                         }
 585                                 }
 586                         }
 587                 }
 588
 589                 ++step;
 590         }
 591
 592         /*
 593          * Add initial defs for all values live in.
 594          */
 595         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 596                 if(arch_isa_irn_has_reg_class(isa, irn, cls)) {
 597
 598                         /* Mark the value live in. */
 599                         bitset_set(live, get_irn_graph_nr(irn));
 600
 601                         /* Add the def */
 602                         border_def(irn, step, 0);
 603                 }
 604         }
 605 }
 606
 607 static void assign(ir_node *block, void *env_ptr)
 608 {
 609         env_t *env = env_ptr;
 610         struct obstack *obst = &env->obst;
 611         bitset_t *live = env->live;
 612         bitset_t *colors = env->colors;
 613         bitset_t *in_colors = env->in_colors;
 614   const arch_isa_if_t *isa = env->isa;
 615   const arch_register_class_t *cls = env->cls;
 616
 617         /* The used colors will remain on the obstack. */
 618         bitset_t *used_colors = bitset_obstack_alloc(obst, env->colors_n);
 619
 620         /* Mark the obstack level and allocate the temporary tmp_colors */
 621         void *obstack_level = obstack_base(obst);
 622         /*bitset_t *tmp_colors = bitset_obstack_alloc(obst, env->colors_n);*/
 623
 624         const ir_node *irn;
 625         border_t *b;
 626         struct list_head *head = &get_ra_block_info(block)->border_head;
 627         pset *live_in = get_live_in(block);
 628
 629         bitset_clear_all(live);
 630         bitset_clear_all(colors);
 631         bitset_clear_all(in_colors);
 632
 633         DBG((dbg, LEVEL_4, "Assigning colors for block %n\n", block));
 634         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 635         list_for_each_entry(border_t, b, head, list) {
 636                 DBG((dbg, LEVEL_4, "\t%s %n/%d\n", b->is_def ? "def" : "use",
 637                                         b->irn, get_irn_graph_nr(b->irn)));
 638         }
 639
 640         /*
 641          * Add initial defs for all values live in.
 642          * Since their colors have already been assigned (The dominators were
 643          * allocated before), we have to mark their colors as used also.
 644          */
 645         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 646                 if(arch_isa_irn_has_reg_class(isa, irn, cls)) {
 647                         int col = get_irn_color(irn);
 648
 649                         /* Mark the color of the live in value as used. */
 650                         assert(is_color(col) && "Node must have been assigned a color.");
 651                         bitset_set(colors, col);
 652                         bitset_set(in_colors, col);
 653                         bitset_set(used_colors, col);
 654
 655                         /* Mark the value live in. */
 656                         bitset_set(live, get_irn_graph_nr(irn));
 657                 }
 658         }
 659
 660         /*
 661          * Mind that the sequence of defs from back to front defines a perfect
 662          * elimination order. So, coloring the definitions from first to last
 663          * will work.
 664          */
 665         list_for_each_entry_reverse(border_t, b, head, list) {
 666                 const ir_node *irn = b->irn;
 667                 int nr = get_irn_graph_nr(irn);
 668
 669                 /*
 670                  * Assign a color, if it is a local def. Global defs already have a
 671                  * color.
 672                  */
 673                 if(b->is_def && !is_live_in(block, irn)) {
 674                         ra_node_info_t *ri = get_ra_node_info(irn);
 675                         int col = NO_COLOR;
 676
 677                         DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors));
 678
 679                         /*
 680                          * Try to assign live out values colors which are not used by live
 681                          * in values.
 682                          */
 683 #if 0
 684                         if(is_live_out(block, irn)) {
 685                                 int next_clear;
 686
 687                                 bitset_copy(tmp_colors, colors);
 688                                 bitset_or(tmp_colors, in_colors);
 689                                 next_clear = bitset_next_clear(tmp_colors, 0);
 690                                 col = next_clear != -1 ? next_clear : NO_COLOR;
 691
 692                                 DBG((dbg, LEVEL_5, "next clear in only outs %b: %d\n", tmp_colors, col));
 693                         }
 694 #endif
 695
 696                         /* If a color is not yet assigned, do it now. */
 697                         if(!is_color(col))
 698                                 col = bitset_next_clear(colors, 0);
 699
 700                         assert(!is_color(get_irn_color(irn)) && "Color must not have assigned");
 701                         assert(!bitset_is_set(live, nr) && "Value def must not have been encountered");
 702
 703                         bitset_set(colors, col);
 704                         bitset_set(used_colors, col);
 705                         bitset_set(live, nr);
 706
 707                         ri->color = col;
 708
 709                         DBG((dbg, LEVEL_1, "\tassigning color %d to %n\n", col, irn));
 710                 }
 711
 712                 /* Clear the color upon a use. */
 713                 else if(!b->is_def) {
 714                         int col = get_irn_color(irn);
 715
 716                         assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 717                         assert(is_color(col) && "A color must have been assigned");
 718
 719                         bitset_clear(colors, col);
 720                         bitset_clear(live, nr);
 721                 }
 722         }
 723
 724 #ifdef DUMP_PRESSURE
 725         {
 726                 char buf[128];
 727                 FILE *f;
 728
 729                 ir_snprintf(buf, sizeof(buf), "pres_%s_bl_%N.txt",
 730                                 get_entity_name(get_irg_entity(irg)), block);
 731
 732                 if((f = fopen(buf, "wt")) != NULL) {
 733                         sched_foreach_reverse(block, irn) {
 734                                 if(arch_isa_irn_has_reg_class(isa, irn, cls))
 735                                         ir_fprintf(f, "\"%n\" %d %d\n", irn, sched_get_time_step(irn),
 736                                                         get_ra_node_info(irn)->pressure);
 737
 738                         }
 739                         fclose(f);
 740                 }
 741         }
 742 #endif
 743
 744
 745         /*
 746          * Allocate the used colors array in the blocks ra info structure and
 747          * fill it.
 748          */
 749         get_ra_block_info(block)->used_colors = used_colors;
 750
 751         /* Free the auxillary data on the obstack. */
 752         obstack_free(obst, obstack_level);
 753 }
 754
 755 void be_ra_chordal_init(void)
 756 {
 757         dbg = firm_dbg_register(DBG_BERA);
 758         firm_dbg_set_mask(dbg, 0);
 759 }
 760
 761 void be_ra_chordal(ir_graph *irg,
 762     const arch_isa_if_t *isa,
 763     const arch_register_class_t *cls)
 764 {
 765         int node_count = get_graph_node_count(irg);
 766   int colors_n = arch_register_class_n_regs(cls);
 767         env_t *env = malloc(sizeof(*env));
 768
 769         if(get_irg_dom_state(irg) != dom_consistent)
 770                 compute_doms(irg);
 771
 772         obstack_init(&env->obst);
 773
 774 #ifdef BUILD_GRAPH
 775         env->edges = new_set(if_edge_cmp, node_count);
 776         env->nodes = new_set(if_node_cmp, node_count);
 777 #endif
 778
 779         env->live = bitset_obstack_alloc(&env->obst, node_count);
 780         env->colors = bitset_obstack_alloc(&env->obst, colors_n);
 781         env->in_colors = bitset_obstack_alloc(&env->obst, colors_n);
 782         env->colors_n = colors_n;
 783   env->cls = cls;
 784   env->isa = isa;
 785   env->irg = irg;
 786
 787         /* First, determine the pressure */
 788         dom_tree_walk_irg(irg, pressure, NULL, env);
 789
 790         /* Insert probable spills */
 791         be_ra_chordal_spill(irg);
 792
 793         /* Assign the colors */
 794         dom_tree_walk_irg(irg, assign, NULL, env);
 795
 796 #ifdef DUMP_IFG
 797         {
 798                 char buf[128];
 799
 800                 ir_snprintf(buf, sizeof(buf), "ifg_%F.dot", irg);
 801                 dump_ifg(irg, env->edges, buf);
 802         }
 803 #endif
 804
 805 #ifdef DUMP_INTERVALS
 806   dump_intv_cfg(env);
 807 #endif
 808
 809         set_irg_ra_link(irg, env);
 810 }
 811
 812 void be_ra_chordal_done(ir_graph *irg)
 813 {
 814         env_t *env = get_irg_ra_link(irg);
 815
 816 #ifdef BUILD_GRAPH
 817         {
 818                 if_node_t *ifn;
 819                 for(ifn = set_first(env->nodes); ifn; ifn = set_next(env->nodes))
 820                         free(ifn->neighb);
 821                 free(env->nodes);
 822                 free(env->edges);
 823         }
 824 #endif
 825
 826         obstack_free(&env->obst, NULL);
 827         free(env);
 828 }
 829
 830 int phi_ops_interfere(const ir_node *a, const ir_node *b)
 831 {
 832 #ifdef BUILD_GRAPH
 833         ir_graph *irg = get_irn_irg(a);
 834         env_t *env = get_irg_ra_link(irg);
 835
 836         assert(irg == get_irn_irg(b) && "Both nodes must be in the same graph");
 837
 838         return are_connected(env, get_irn_graph_nr(a), get_irn_graph_nr(b));
 839 #else
 840         return values_interfere(a, b);
 841 #endif /* BUILD_GRAPH */
 842 }
 843
 844 #ifdef BUILD_GRAPH
 845 /** TODO remove this
 846  * Deprecated. Use be_ra_get_ifg_edges instead.
 847  */
 848 set *be_ra_get_ifg(ir_graph *irg) {
 849         return ((env_t *)get_irg_ra_link(irg))->edges;
 850 }
 851
 852 set *be_ra_get_ifg_edges(ir_graph *irg) {
 853         return ((env_t *)get_irg_ra_link(irg))->edges;
 854 }
 855
 856 set *be_ra_get_ifg_nodes(ir_graph *irg) {
 857         return ((env_t *)get_irg_ra_link(irg))->nodes;
 858 }
 859
 860 #endif