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