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