nsz Git - libfirm/blob - ir/be/bechordal.c

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