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 necessary 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         ++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: %+F, 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: %+F\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                 ++step;
 424         }
 425
 426         /*
 427          * Add initial defs for all values live in.
 428          */
 429         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 430                 if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls)) {
 431
 432                         /* Mark the value live in. */
 433                         bitset_set(live, get_irn_graph_nr(irn));
 434
 435                         /* Add the def */
 436                         border_def(irn, step, 0);
 437                 }
 438         }
 439
 440     del_pset(live_in);
 441     del_pset(live_end);
 442 }
 443
 444 static void assign(ir_node *block, void *env_ptr)
 445 {
 446         be_chordal_env_t *env = env_ptr;
 447         struct obstack *obst = &env->obst;
 448         bitset_t *live = env->live;
 449         bitset_t *colors = env->colors;
 450         bitset_t *in_colors = env->in_colors;
 451         const arch_register_class_t *cls = env->cls;
 452
 453         /* Mark the obstack level and allocate the temporary tmp_colors */
 454         void *obstack_level = obstack_base(obst);
 455         /*bitset_t *tmp_colors = bitset_obstack_alloc(obst, env->colors_n);*/
 456
 457         const ir_node *irn;
 458         border_t *b;
 459         struct list_head *head = get_block_border_head(env, block);
 460         pset *live_in = put_live_in(block, pset_new_ptr_default());
 461
 462         bitset_clear_all(live);
 463         bitset_clear_all(colors);
 464         bitset_clear_all(in_colors);
 465
 466         DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
 467         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 468         list_for_each_entry(border_t, b, head, list) {
 469                 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
 470                                         b->irn, get_irn_graph_nr(b->irn)));
 471         }
 472
 473         /*
 474          * Add initial defs for all values live in.
 475          * Since their colors have already been assigned (The dominators were
 476          * allocated before), we have to mark their colors as used also.
 477          */
 478         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 479                 if(arch_irn_has_reg_class(env->arch_env, irn, 0, cls)) {
 480       const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn, 0);
 481       int col;
 482
 483       assert(reg && "Node must have been assigned a register");
 484                         col = arch_register_get_index(reg);
 485
 486                         /* Mark the color of the live in value as used. */
 487                         bitset_set(colors, col);
 488                         bitset_set(in_colors, col);
 489
 490                         /* Mark the value live in. */
 491                         bitset_set(live, get_irn_graph_nr(irn));
 492                 }
 493         }
 494
 495         /*
 496          * Mind that the sequence of defs from back to front defines a perfect
 497          * elimination order. So, coloring the definitions from first to last
 498          * will work.
 499          */
 500         list_for_each_entry_reverse(border_t, b, head, list) {
 501                 ir_node *irn = b->irn;
 502                 int nr = get_irn_graph_nr(irn);
 503
 504                 /*
 505                  * Assign a color, if it is a local def. Global defs already have a
 506                  * color.
 507                  */
 508                 if(b->is_def && !is_live_in(block, irn)) {
 509       const arch_register_t *reg;
 510                         int col = NO_COLOR;
 511
 512                         DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors));
 513
 514       col = bitset_next_clear(colors, 0);
 515       reg = arch_register_for_index(env->cls, col);
 516
 517       assert(arch_get_irn_register(env->arch_env, irn, 0) == NULL
 518           && "This node must not have been assigned a register yet");
 519                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 520
 521                         bitset_set(colors, col);
 522                         bitset_set(live, nr);
 523
 524                         arch_set_irn_register(env->arch_env, irn, 0, reg);
 525                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
 526             arch_register_get_name(reg), col, irn));
 527                 }
 528
 529                 /* Clear the color upon a use. */
 530                 else if(!b->is_def) {
 531       const arch_register_t *reg = arch_get_irn_register(env->arch_env, irn, 0);
 532                         int col;
 533
 534       assert(reg && "Register must have been assigned");
 535
 536       col = arch_register_get_index(reg);
 537                         assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 538
 539                         bitset_clear(colors, col);
 540                         bitset_clear(live, nr);
 541                 }
 542         }
 543
 544         /* Free the auxillary data on the obstack. */
 545         obstack_free(obst, obstack_level);
 546
 547   del_pset(live_in);
 548 }
 549
 550 void be_ra_chordal_init(void)
 551 {
 552         dbg = firm_dbg_register(DBG_CHORDAL);
 553         firm_dbg_set_mask(dbg, 0);
 554 }
 555
 556 be_chordal_env_t *be_ra_chordal(ir_graph *irg,
 557     const arch_env_t *arch_env,
 558     const arch_register_class_t *cls)
 559 {
 560         int node_count = get_graph_node_count(irg);
 561         int colors_n = arch_register_class_n_regs(cls);
 562         be_chordal_env_t *env = malloc(sizeof(*env));
 563
 564         if(get_irg_dom_state(irg) != dom_consistent)
 565                 compute_doms(irg);
 566
 567         obstack_init(&env->obst);
 568
 569 #ifdef BUILD_GRAPH
 570         env->edges = new_set(if_edge_cmp, node_count);
 571         env->nodes = new_set(if_node_cmp, node_count);
 572 #endif
 573
 574         env->live = bitset_obstack_alloc(&env->obst, node_count);
 575         env->colors = bitset_obstack_alloc(&env->obst, colors_n);
 576         env->in_colors = bitset_obstack_alloc(&env->obst, colors_n);
 577         env->colors_n = colors_n;
 578         env->cls = cls;
 579         env->arch_env = arch_env;
 580         env->irg = irg;
 581         env->border_heads = pmap_create();
 582
 583         /* First, determine the pressure */
 584         dom_tree_walk_irg(irg, pressure, NULL, env);
 585
 586         /* Insert probable spills */
 587         be_ra_chordal_spill(env);
 588
 589         /* Assign the colors */
 590         dom_tree_walk_irg(irg, assign, NULL, env);
 591
 592 #ifdef DUMP_IFG
 593         dump_ifg(env);
 594 #endif
 595
 596 #ifdef DUMP_INTERVALS
 597         {
 598                 char buf[128];
 599         plotter_t *plotter;
 600
 601                 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", cls->name, irg);
 602         plotter = new_plotter_ps(buf);
 603
 604         draw_interval_tree(&draw_chordal_def_opts, env, plotter, arch_env, cls);
 605         plotter_free(plotter);
 606         }
 607 #endif
 608         return env;
 609 }
 610
 611 void be_ra_chordal_done(be_chordal_env_t *env)
 612 {
 613 #ifdef BUILD_GRAPH
 614         {
 615                 if_node_t *ifn;
 616                 for(ifn = set_first(env->nodes); ifn; ifn = set_next(env->nodes))
 617                         free(ifn->neighb);
 618                 free(env->nodes);
 619                 free(env->edges);
 620         }
 621 #endif
 622
 623   pmap_destroy(env->border_heads);
 624         obstack_free(&env->obst, NULL);
 625         free(env);
 626 }
 627
 628 int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
 629 {
 630 #ifdef BUILD_GRAPH
 631         return are_connected(env, get_irn_graph_nr(a), get_irn_graph_nr(b));
 632 #else
 633         return values_interfere(a, b);
 634 #endif /* BUILD_GRAPH */
 635 }
 636
 637 #ifdef BUILD_GRAPH
 638
 639 set *be_ra_get_ifg_edges(const be_chordal_env_t *env) {
 640         return env->edges;
 641 }
 642
 643 set *be_ra_get_ifg_nodes(const be_chordal_env_t *env) {
 644         return env->nodes;
 645 }
 646
 647 #endif