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

   1 /**
   2  * Chordal register allocation.
   3  * @author Sebastian Hack
   4  * @date 8.12.2004
   5  *
   6  * Copyright (C) Universitaet Karlsruhe
   7  * Released under the GPL
   8  */
   9
  10 #ifdef HAVE_CONFIG_H
  11 #include "config.h"
  12 #endif
  13
  14 #include <ctype.h>
  15
  16 #include "obst.h"
  17 #include "list.h"
  18 #include "bitset.h"
  19 #include "iterator.h"
  20
  21 #include "irmode_t.h"
  22 #include "irgraph_t.h"
  23 #include "irprintf_t.h"
  24 #include "irgwalk.h"
  25 #include "irdump.h"
  26 #include "irdom.h"
  27 #include "debug.h"
  28 #include "xmalloc.h"
  29
  30 #include "beutil.h"
  31 #include "besched.h"
  32 #include "benumb_t.h"
  33 #include "besched_t.h"
  34 #include "belive_t.h"
  35 #include "bearch.h"
  36
  37 #include "bechordal_t.h"
  38 #include "bechordal_draw.h"
  39
  40 #define NO_COLOR (-1)
  41
  42 #define DUMP_INTERVALS
  43 #undef DUMP_PRESSURE
  44 #undef DUMP_IFG
  45
  46 #if defined(DUMP_IFG) && !defined(BUILD_GRAPH)
  47 #error Must define BUILD_GRAPH to be able to dump it.
  48 #endif
  49
  50
  51 #ifdef DEBUG_libfirm
  52 #include "fourcc.h"
  53
  54 /* Make a fourcc for border checking. */
  55 #define BORDER_FOURCC                           FOURCC('B', 'O', 'R', 'D')
  56
  57 #endif /* DEBUG_libfirm */
  58
  59 static firm_dbg_module_t *dbg;
  60
  61 #ifdef BUILD_GRAPH
  62
  63 #define IF_EDGE_HASH(e) ((e)->src)
  64 #define IF_NODE_HASH(n) ((n)->nnr)
  65
  66 static int if_edge_cmp(const void *p1, const void *p2, size_t size)
  67 {
  68         const if_edge_t *e1 = p1;
  69         const if_edge_t *e2 = p2;
  70
  71         return !(e1->src == e2->src && e1->tgt == e2->tgt);
  72 }
  73
  74 static int if_node_cmp(const void *p1, const void *p2, size_t size)
  75 {
  76         const if_node_t *n1 = p1;
  77         const if_node_t *n2 = p2;
  78
  79         return n1->nnr != n2->nnr;
  80 }
  81
  82 static INLINE if_edge_t *edge_init(if_edge_t *edge, int src, int tgt)
  83 {
  84         /* Bring the smaller entry to src. */
  85         if(src > tgt) {
  86                 edge->src = tgt;
  87                 edge->tgt = src;
  88         } else {
  89                 edge->src = src;
  90                 edge->tgt = tgt;
  91         }
  92
  93         return edge;
  94 }
  95
  96 static INLINE void add_if(const be_chordal_env_t *env, int src, int tgt)
  97 {
  98         if_edge_t edge;
  99         if_node_t node, *src_node, *tgt_node;
 100         /* insert edge */
 101         edge_init(&edge, src, tgt);
 102         set_insert(env->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge));
 103
 104         /* insert nodes */
 105         node.nnr = src;
 106         node.neighb = pset_new_ptr(8);
 107         src_node = set_insert(env->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
 108         node.nnr = tgt;
 109         node.neighb = pset_new_ptr(8);
 110         tgt_node = set_insert(env->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
 111
 112         /* insert neighbors into nodes */
 113         pset_insert_ptr(src_node->neighb, tgt_node);
 114         pset_insert_ptr(tgt_node->neighb, src_node);
 115 }
 116
 117 static INLINE int are_connected(const be_chordal_env_t *env, int src, int tgt)
 118 {
 119         if_edge_t edge;
 120         edge_init(&edge, src, tgt);
 121         return set_find(env->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL;
 122 }
 123
 124 int ifg_has_edge(const be_chordal_env_t *env, const if_node_t *n1, const if_node_t* n2) {
 125         return are_connected(env, n1->nnr, n2->nnr);
 126 }
 127
 128 #ifdef DUMP_IFG
 129
 130 static void dump_ifg(const be_chordal_env_t *env)
 131 {
 132         static const char *colors[] = {
 133                 "coral",
 134                 "azure",
 135                 "bisque",
 136                 "aliceblue",
 137                 "blanchedalmond",
 138                 "deeppink",
 139                 "cornsilk",
 140                 "blueviolet",
 141                 "floralwhite",
 142                 "hotpink",
 143                 "gainsboro",
 144                 "indianred",
 145                 "cornflowerblue",
 146                 "ghostwhite",
 147                 "lightpink",
 148                 "palegoldenrod",
 149                 "darkslateblue",
 150                 "honeydew",
 151                 "ivory",
 152                 "lavender",
 153                 "mediumvioletred",
 154                 "indigo",
 155                 "lavenderblush",
 156                 "lemonchiffon",
 157                 "linen",
 158                 "pink",
 159                 "mintcream",
 160                 "red",
 161                 "mediumblue",
 162                 "mistyrose",
 163                 "mediumslateblue",
 164                 "moccasin",
 165                 "tomato",
 166                 "forestgreen",
 167                 "midnightblue",
 168                 "navajowhite",
 169                 "navy",
 170                 "oldlace",
 171                 "greenyellow",
 172                 "navyblue",
 173                 "papayawhip",
 174                 "lawngreen",
 175                 "powderblue",
 176                 "peachpuff",
 177                 "seashell",
 178                 "snow",
 179                 "thistle",
 180                 "wheat",
 181                 "darkkhaki",
 182                 "mintcream",
 183                 "khaki",
 184                 "Magentas",
 185                 "whitesmoke",
 186                 "peru",
 187                 "palegreen",
 188                 "blueviolet",
 189                 "rosybrown",
 190                 "saddlebrown",
 191                 "springgreen",
 192                 "darkviolet",
 193                 "darkslategray",
 194                 "dimgray",
 195                 "sienna",
 196                 "gray",
 197                 "tan",
 198                 "gray",
 199                 "mediumvioletred",
 200                 "lightgray",
 201                 "Oranges",
 202                 "cyan",
 203                 "lightslategray",
 204                 "darkorange",
 205                 "slategray",
 206                 "orangered",
 207                 "mediumturquoise",
 208                 "violet",
 209                 "paleturquoise"
 210         };
 211
 212         static const int n_colors = sizeof(colors) / sizeof(colors[0]);
 213
 214         FILE *f;
 215   set *edges = env->edges;
 216   ir_graph *irg = env->irg;
 217   char filename[128];
 218
 219   ir_snprintf(filename, sizeof(filename), "ifg_%s_%F.dot", env->cls->name, irg);
 220
 221         if((f = fopen(filename, "wt")) != NULL) {
 222                 bitset_pos_t pos;
 223                 int n_edges = 0;
 224                 if_edge_t *edge;
 225                 bitset_t *bs = bitset_malloc(get_graph_node_count(irg));
 226
 227                 ir_fprintf(f, "graph \"%F\" {\n", irg);
 228                 fprintf(f, "\tnode [shape=box,style=filled]\n");
 229
 230                 for(edge = set_first(edges); edge; edge = set_next(edges)) {
 231                         bitset_set(bs, edge->src);
 232                         bitset_set(bs, edge->tgt);
 233                         n_edges++;
 234                 }
 235
 236                 fprintf(f, "\tx [label=\"nodes: %u, edges: %d\"]\n", bitset_popcnt(bs), n_edges);
 237
 238                 bitset_foreach(bs, pos) {
 239                         int nr = (int) pos;
 240                         ir_node *irn = get_irn_for_graph_nr(irg, nr);
 241                         int color = get_irn_color(irn);
 242
 243                         ir_fprintf(f, "\tn%d [label=\"%n\",color=\"%s\"]\n", nr, irn,
 244                                         color >= 0 && color < n_colors ? colors[color] : "black");
 245                 }
 246
 247                 for(edge = set_first(edges); edge; edge = set_next(edges)) {
 248                         fprintf(f, "\tn%d -- n%d [len=5]\n", edge->src, edge->tgt);
 249                 }
 250
 251                 fprintf(f, "}\n");
 252                 fclose(f);
 253
 254                 bitset_free(bs);
 255         }
 256
 257 }
 258
 259 #endif /* DUMP_IFG */
 260
 261 #endif /* BUILD_GRAPH */
 262
 263
 264 /**
 265  * Add an interval border to the list of a block's list
 266  * of interval border.
 267  * @note You always have to create the use before the def.
 268  * @param env The environment.
 269  * @param head The list head to enqueue the borders.
 270  * @param irn The node (value) the border belongs to.
 271  * @param pressure The pressure at this point in time.
 272  * @param step A time step for the border.
 273  * @param is_def Is the border a use or a def.
 274  * @return The created border.
 275  */
 276 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
 277                         ir_node *irn, unsigned step, unsigned pressure,
 278                         unsigned is_def, unsigned is_real)
 279 {
 280         border_t *b;
 281
 282         if(!is_def) {
 283                 border_t *def;
 284
 285                 b = obstack_alloc(&env->obst, sizeof(*b));
 286
 287                 /* also allocate the def and tie it to the use. */
 288                 def = obstack_alloc(&env->obst, sizeof(*def));
 289                 b->other_end = def;
 290                 def->other_end = b;
 291
 292                 /*
 293                  * Set the link field of the irn to the def.
 294                  * This strongly relies on the fact, that the use is always
 295                  * made before the def.
 296                  */
 297                 set_irn_link(irn, def);
 298
 299 #ifdef DEBUG_libfirm
 300                 b->magic = BORDER_FOURCC;
 301                 def->magic = BORDER_FOURCC;
 302 #endif
 303         }
 304
 305         /*
 306          * If the def is encountered, the use was made and so was the
 307          * the def node (see the code above). It was placed into the
 308          * link field of the irn, so we can get it there.
 309          */
 310         else {
 311                 b = get_irn_link(irn);
 312
 313 #ifdef DEBUG_libfirm
 314                 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
 315 #endif
 316         }
 317
 318         b->pressure = pressure;
 319         b->is_def = is_def;
 320         b->is_real = is_real;
 321         b->irn = irn;
 322         b->step = step;
 323         list_add_tail(&b->list, head);
 324         DBG((dbg, LEVEL_5, "\t\t%s adding %n, step: %d\n",
 325                                 is_def ? "def" : "use", irn, step));
 326
 327         return b;
 328 }
 329
 330 /**
 331  * Annotate the register pressure to the nodes and compute
 332  * the liveness intervals.
 333  * @param block The block to do it for.
 334  * @param env_ptr The environment.
 335  */
 336 static void pressure(ir_node *block, void *env_ptr)
 337 {
 338 /* Convenience macro for a def */
 339 #define border_def(irn, step, real) \
 340         border_add(env, head, irn, step, pressure--, 1, real)
 341
 342 /* Convenience macro for a use */
 343 #define border_use(irn, step, real) \
 344         border_add(env, head, irn, step, ++pressure, 0, real)
 345
 346         be_chordal_env_t *env = env_ptr;
 347         bitset_t *live = env->live;
 348         ir_node *irn;
 349
 350         int i, n;
 351         unsigned step = 0;
 352         unsigned pressure = 0;
 353         struct list_head *head;
 354         pset *live_in = get_live_in(block);
 355         pset *live_end = get_live_end(block);
 356   const arch_register_class_t *cls = env->cls;
 357
 358         DBG((dbg, LEVEL_1, "Computing pressure in block %n\n", block));
 359         bitset_clear_all(live);
 360
 361         /* Set up the border list in the block info */
 362   head = obstack_alloc(&env->obst, sizeof(*head));
 363         INIT_LIST_HEAD(head);
 364   pmap_insert(env->border_heads, block, head);
 365
 366         /*
 367          * Make final uses of all values live out of the block.
 368          * They are neccessary to build up real intervals.
 369          */
 370         for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
 371                 DBG((dbg, LEVEL_3, "\tMaking live: %n/%d\n", irn, get_irn_graph_nr(irn)));
 372                 bitset_set(live, get_irn_graph_nr(irn));
 373     if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls))
 374       border_use(irn, step, 0);
 375         }
 376
 377         ++step;
 378
 379         /*
 380          * Determine the last uses of a value inside the block, since they are
 381          * relevant for the interval borders.
 382          */
 383         sched_foreach_reverse(block, irn) {
 384                 DBG((dbg, LEVEL_1, "\tinsn: %n, pressure: %d\n", irn, pressure));
 385                 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
 386
 387     /*
 388      * If the node defines some value, which can put into a
 389      * register of the current class, make a border for it.
 390      */
 391                 if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls)) {
 392       bitset_pos_t elm;
 393                         int nr = get_irn_graph_nr(irn);
 394
 395                         bitset_clear(live, nr);
 396                         border_def(irn, step, 1);
 397
 398 #ifdef BUILD_GRAPH
 399       bitset_foreach(live, elm)
 400         add_if(env, nr, (int) elm);
 401 #endif
 402                 }
 403
 404                 /*
 405                  * If the node is no phi node we can examine the uses.
 406                  */
 407                 if(!is_Phi(irn)) {
 408                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 409                                 ir_node *op = get_irn_n(irn, i);
 410
 411                                 if(arch_irn_has_reg_class(env->arch_env, op, 0, cls)) {
 412                                         int nr = get_irn_graph_nr(op);
 413
 414                                         DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %n\n", i, op));
 415
 416                                         if(!bitset_is_set(live, nr)) {
 417                                                 border_use(op, step, 1);
 418                                                 bitset_set(live, nr);
 419                                         }
 420                                 }
 421                         }
 422                 }
 423
 424                 ++step;
 425         }
 426
 427         /*
 428          * Add initial defs for all values live in.
 429          */
 430         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 431                 if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls)) {
 432
 433                         /* Mark the value live in. */
 434                         bitset_set(live, get_irn_graph_nr(irn));
 435
 436                         /* Add the def */
 437                         border_def(irn, step, 0);
 438                 }
 439         }
 440 }
 441
 442 static void assign(ir_node *block, void *env_ptr)
 443 {
 444         be_chordal_env_t *env = env_ptr;
 445         struct obstack *obst = &env->obst;
 446         bitset_t *live = env->live;
 447         bitset_t *colors = env->colors;
 448         bitset_t *in_colors = env->in_colors;
 449   const arch_register_class_t *cls = env->cls;
 450
 451         /* Mark the obstack level and allocate the temporary tmp_colors */
 452         void *obstack_level = obstack_base(obst);
 453         /*bitset_t *tmp_colors = bitset_obstack_alloc(obst, env->colors_n);*/
 454
 455         const ir_node *irn;
 456         border_t *b;
 457         struct list_head *head = get_block_border_head(env, block);
 458         pset *live_in = get_live_in(block);
 459
 460         bitset_clear_all(live);
 461         bitset_clear_all(colors);
 462         bitset_clear_all(in_colors);
 463
 464         DBG((dbg, LEVEL_4, "Assigning colors for block %n\n", block));
 465         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 466         list_for_each_entry(border_t, b, head, list) {
 467                 DBG((dbg, LEVEL_4, "\t%s %n/%d\n", b->is_def ? "def" : "use",
 468                                         b->irn, get_irn_graph_nr(b->irn)));
 469         }
 470
 471         /*
 472          * Add initial defs for all values live in.
 473          * Since their colors have already been assigned (The dominators were
 474          * allocated before), we have to mark their colors as used also.
 475          */
 476         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 477                 if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls)) {
 478       const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn, 0);
 479       int col;
 480
 481       assert(reg && "Nodfe must have been assigned a register");
 482                         col = arch_register_get_index(reg);
 483
 484                         /* Mark the color of the live in value as used. */
 485                         bitset_set(colors, col);
 486                         bitset_set(in_colors, col);
 487
 488                         /* Mark the value live in. */
 489                         bitset_set(live, get_irn_graph_nr(irn));
 490                 }
 491         }
 492
 493         /*
 494          * Mind that the sequence of defs from back to front defines a perfect
 495          * elimination order. So, coloring the definitions from first to last
 496          * will work.
 497          */
 498         list_for_each_entry_reverse(border_t, b, head, list) {
 499                 ir_node *irn = b->irn;
 500                 int nr = get_irn_graph_nr(irn);
 501
 502                 /*
 503                  * Assign a color, if it is a local def. Global defs already have a
 504                  * color.
 505                  */
 506                 if(b->is_def && !is_live_in(block, irn)) {
 507       const arch_register_t *reg;
 508                         int col = NO_COLOR;
 509
 510                         DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors));
 511
 512       col = bitset_next_clear(colors, 0);
 513       reg = arch_register_for_index(env->cls, col);
 514
 515       assert(arch_get_irn_register(env->arch_env, irn, 0) == NULL
 516           && "This node must not have been assigned a register yet");
 517                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 518
 519                         bitset_set(colors, col);
 520                         bitset_set(live, nr);
 521
 522                         arch_set_irn_register(env->arch_env, irn, 0, reg);
 523                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %n\n",
 524             arch_register_get_name(reg), col, irn));
 525                 }
 526
 527                 /* Clear the color upon a use. */
 528                 else if(!b->is_def) {
 529       const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn, 0);
 530                         int col;
 531
 532       assert(reg && "Register must have been assigned");
 533
 534       col = arch_register_get_index(reg);
 535                         assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 536
 537                         bitset_clear(colors, col);
 538                         bitset_clear(live, nr);
 539                 }
 540         }
 541
 542         /* Free the auxillary data on the obstack. */
 543         obstack_free(obst, obstack_level);
 544 }
 545
 546 void be_ra_chordal_init(void)
 547 {
 548         dbg = firm_dbg_register(DBG_CHORDAL);
 549         firm_dbg_set_mask(dbg, 0);
 550 }
 551
 552 be_chordal_env_t *be_ra_chordal(ir_graph *irg,
 553     const arch_env_t *arch_env,
 554     const arch_register_class_t *cls)
 555 {
 556         int node_count = get_graph_node_count(irg);
 557   int colors_n = arch_register_class_n_regs(cls);
 558         be_chordal_env_t *env = malloc(sizeof(*env));
 559
 560         if(get_irg_dom_state(irg) != dom_consistent)
 561                 compute_doms(irg);
 562
 563         obstack_init(&env->obst);
 564
 565 #ifdef BUILD_GRAPH
 566         env->edges = new_set(if_edge_cmp, node_count);
 567         env->nodes = new_set(if_node_cmp, node_count);
 568 #endif
 569
 570         env->live = bitset_obstack_alloc(&env->obst, node_count);
 571         env->colors = bitset_obstack_alloc(&env->obst, colors_n);
 572         env->in_colors = bitset_obstack_alloc(&env->obst, colors_n);
 573         env->colors_n = colors_n;
 574   env->cls = cls;
 575   env->arch_env = arch_env;
 576   env->irg = irg;
 577   env->border_heads = pmap_create();
 578
 579         /* First, determine the pressure */
 580         dom_tree_walk_irg(irg, pressure, NULL, env);
 581
 582         /* Insert probable spills */
 583         be_ra_chordal_spill(env);
 584
 585         /* Assign the colors */
 586         dom_tree_walk_irg(irg, assign, NULL, env);
 587
 588 #ifdef DUMP_IFG
 589   dump_ifg(env);
 590 #endif
 591
 592 #ifdef DUMP_INTERVALS
 593         {
 594                 char buf[128];
 595     plotter_t *plotter;
 596
 597                 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", cls->name, irg);
 598     plotter = new_plotter_ps(buf);
 599
 600     draw_interval_tree(&draw_chordal_def_opts, env, plotter, arch_env, cls);
 601     plotter_free(plotter);
 602         }
 603 #endif
 604
 605   return env;
 606 }
 607
 608 void be_ra_chordal_done(be_chordal_env_t *env)
 609 {
 610 #ifdef BUILD_GRAPH
 611         {
 612                 if_node_t *ifn;
 613                 for(ifn = set_first(env->nodes); ifn; ifn = set_next(env->nodes))
 614                         free(ifn->neighb);
 615                 free(env->nodes);
 616                 free(env->edges);
 617         }
 618 #endif
 619
 620   pmap_destroy(env->border_heads);
 621         obstack_free(&env->obst, NULL);
 622         free(env);
 623 }
 624
 625 int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
 626 {
 627 #ifdef BUILD_GRAPH
 628         return are_connected(env, get_irn_graph_nr(a), get_irn_graph_nr(b));
 629 #else
 630         return values_interfere(a, b);
 631 #endif /* BUILD_GRAPH */
 632 }
 633
 634 #ifdef BUILD_GRAPH
 635
 636 set *be_ra_get_ifg_edges(const be_chordal_env_t *env) {
 637         return env->edges;
 638 }
 639
 640 set *be_ra_get_ifg_nodes(const be_chordal_env_t *env) {
 641         return env->nodes;
 642 }
 643
 644 #endif