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 #ifdef HAVE_MALLOC_H
  15 #include <malloc.h>
  16 #endif
  17
  18 #ifdef HAVE_ALLOCA_H
  19 #include <alloca.h>
  20 #endif
  21
  22 #include <ctype.h>
  23
  24 #include "obst.h"
  25 #include "pset.h"
  26 #include "list.h"
  27 #include "bitset.h"
  28 #include "iterator.h"
  29
  30 #include "irmode_t.h"
  31 #include "irgraph_t.h"
  32 #include "irprintf_t.h"
  33 #include "irgwalk.h"
  34 #include "irdump.h"
  35 #include "irdom.h"
  36 #include "debug.h"
  37 #include "xmalloc.h"
  38
  39 #include "beutil.h"
  40 #include "besched.h"
  41 #include "benumb_t.h"
  42 #include "besched_t.h"
  43 #include "belive_t.h"
  44 #include "benode_t.h"
  45 #include "bearch.h"
  46 #include "beifg.h"
  47
  48 #include "bechordal_t.h"
  49 #include "bechordal_draw.h"
  50
  51 #define DBG_LEVEL SET_LEVEL_0
  52 #define DBG_LEVEL_CHECK SET_LEVEL_0
  53
  54 #define NO_COLOR (-1)
  55
  56 #undef DUMP_INTERVALS
  57
  58 typedef struct _be_chordal_alloc_env_t {
  59         be_chordal_env_t *chordal_env;
  60
  61         pset *pre_colored;    /**< Set of precolored nodes. */
  62         bitset_t *live;                         /**< A liveness bitset. */
  63         bitset_t *colors;                       /**< The color mask. */
  64         bitset_t *in_colors;        /**< Colors used by live in values. */
  65         int colors_n;               /**< The number of colors. */
  66 } be_chordal_alloc_env_t;
  67
  68 #include "fourcc.h"
  69
  70 /* Make a fourcc for border checking. */
  71 #define BORDER_FOURCC                           FOURCC('B', 'O', 'R', 'D')
  72
  73 static void check_border_list(struct list_head *head)
  74 {
  75   border_t *x;
  76   list_for_each_entry(border_t, x, head, list) {
  77     assert(x->magic == BORDER_FOURCC);
  78   }
  79 }
  80
  81 static void check_heads(be_chordal_env_t *env)
  82 {
  83   pmap_entry *ent;
  84   for(ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
  85     /* ir_printf("checking border list of block %+F\n", ent->key); */
  86     check_border_list(ent->value);
  87   }
  88 }
  89
  90
  91 /**
  92  * Add an interval border to the list of a block's list
  93  * of interval border.
  94  * @note You always have to create the use before the def.
  95  * @param env The environment.
  96  * @param head The list head to enqueue the borders.
  97  * @param irn The node (value) the border belongs to.
  98  * @param pressure The pressure at this point in time.
  99  * @param step A time step for the border.
 100  * @param is_def Is the border a use or a def.
 101  * @return The created border.
 102  */
 103 static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head,
 104                         ir_node *irn, unsigned step, unsigned pressure,
 105                         unsigned is_def, unsigned is_real)
 106 {
 107         border_t *b;
 108
 109         if(!is_def) {
 110                 border_t *def;
 111
 112                 b = obstack_alloc(&env->obst, sizeof(*b));
 113
 114                 /* also allocate the def and tie it to the use. */
 115                 def = obstack_alloc(&env->obst, sizeof(*def));
 116                 memset(def, 0, sizeof(*def));
 117                 b->other_end = def;
 118                 def->other_end = b;
 119
 120                 /*
 121                  * Set the link field of the irn to the def.
 122                  * This strongly relies on the fact, that the use is always
 123                  * made before the def.
 124                  */
 125                 set_irn_link(irn, def);
 126
 127                 b->magic = BORDER_FOURCC;
 128                 def->magic = BORDER_FOURCC;
 129         }
 130
 131         /*
 132          * If the def is encountered, the use was made and so was the
 133          * the def node (see the code above). It was placed into the
 134          * link field of the irn, so we can get it there.
 135          */
 136         else {
 137                 b = get_irn_link(irn);
 138
 139                 assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered");
 140         }
 141
 142         b->pressure = pressure;
 143         b->is_def = is_def;
 144         b->is_real = is_real;
 145         b->irn = irn;
 146         b->step = step;
 147         list_add_tail(&b->list, head);
 148         DBG((env->dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
 149
 150
 151         return b;
 152 }
 153
 154 /**
 155  * Check, if an irn is of the register class currently under processing.
 156  * @param env The chordal environment.
 157  * @param irn The node.
 158  * @return 1, if the node is of that register class, 0 if not.
 159  */
 160 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
 161 {
 162   return arch_irn_has_reg_class(env->main_env->arch_env, irn, -1, env->cls);
 163 }
 164
 165 #define has_limited_constr(req, irn) \
 166         (arch_get_register_req(arch_env, (req), irn, -1) && (req)->type == arch_register_req_type_limited)
 167
 168 /**
 169  * Handle register targeting constraints signaled by a Perm.
 170  * @param alloc_env    Private data for the allocation phase.
 171  * @param perm         The Perm node guarding the constrained node.
 172  * @return             The constrained node.
 173
 174                 Pro-coloring works as follows:
 175
 176          +-----------------------------------+
 177          |            Perm                   |
 178          +---.-------.--------.---------.----+
 179              |       |        |         |
 180          +---+--+    |        |         |
 181          | Proj |    |        |         |
 182          +------+    |        |         |
 183                      |        |         |
 184                   +--+---+    |         |
 185                   | Proj |    |         |
 186                   +--.---+    |         |
 187                      |        |         |
 188                      |     +--+---+     |
 189                      |     | Proj |     |
 190                      |     +------+     |
 191                       |                 |
 192                       |             +---+--+
 193                        `-.          | Proj | Result:
 194                           `._       +---.--+ R1
 195                              `.         |
 196                                `-.      |
 197                                   `._   |
 198                                     +`.-+--+
 199                                     |Constr| Result:
 200                                     +------+ R2
 201
 202                 1) Look at all Projs of the Perm if they have output constraints.
 203                    If one has an output constraint, pre-color it, else record it
 204                    in the set leftover. Its color has to be chosen after all
 205                    constrained nodes are colored. Furthermore record all colors
 206                    used in the pre-coloring in the set colors_used.
 207
 208                 2) Look whether the first node not a Proj (this is the constrained
 209                    node due to which the Perm has been inserted) has an output
 210                    constraint. If yes, pre-color the node accordingly else do nothing
 211                    since the node's input constraints are modelled by the Proj's
 212                    output constraint.
 213
 214                    There's one subtle point here: If thenode has an output constraint
 215                    and the live range of some Proj ends at that node, we must give
 216                    that Proj the color of the constrained node. Otherwise the
 217                    available colors may not suffice for the rest of the projs.
 218
 219                 3) At last, color the Projs which have not been colored yet with the
 220                    left over colors.
 221
 222                    So afterwards, everything including the constrained node will
 223                    be colored and the assign() phase can complete this coloring.
 224                    Note that therefore, we put the pre-colored nodes in a set
 225                    called pre_colored().
 226
 227  */
 228 static ir_node *handle_constraints_at_perm(be_chordal_alloc_env_t *alloc_env, ir_node *perm)
 229 {
 230         be_chordal_env_t *env      = alloc_env->chordal_env;
 231         firm_dbg_module_t *dbg     = env->dbg;
 232         const arch_env_t *arch_env = env->main_env->arch_env;
 233
 234         pset *leftover        = pset_new_ptr(8);
 235         bitset_t *bs          = bitset_alloca(env->cls->n_regs);
 236         bitset_t *colors_used = bitset_alloca(env->cls->n_regs);
 237         ir_node *irn, *cnstr;
 238         int has_cnstr = 0;
 239         int col;
 240         arch_register_req_t req;
 241         const arch_register_t *reg, *cnstr_reg = NULL;
 242
 243         assert(be_is_Perm(perm));
 244
 245         DBG((dbg, LEVEL_2, "Constraints on %+F\n", perm));
 246
 247         /*
 248          * Color constrained Projs first.
 249          */
 250         for(irn = sched_next(perm); is_Proj(irn); irn = sched_next(irn)) {
 251                 arch_register_req_t req;
 252
 253                 if(has_limited_constr(&req, irn)) {
 254                         bitset_clear_all(bs);
 255                         req.data.limited(irn, -1, bs);
 256                         col = bitset_next_set(bs, 0);
 257                         reg = arch_register_for_index(env->cls, col);
 258
 259                         pset_insert_ptr(alloc_env->pre_colored, irn);
 260                         arch_set_irn_register(arch_env, irn, reg);
 261                         bitset_set(colors_used, col);
 262
 263                         DBG((dbg, LEVEL_2, "\tPerm Proj with constraints: %+F set to %s\n", irn, reg->name));
 264                 }
 265
 266                 else
 267                         pset_insert_ptr(leftover, irn);
 268
 269         }
 270         cnstr = irn;
 271
 272         if(has_limited_constr(&req, cnstr)) {
 273                 bitset_clear_all(bs);
 274                 req.data.limited(cnstr, -1, bs);
 275                 col = bitset_next_set(colors_used, 0);
 276                 reg = arch_register_for_index(env->cls, col);
 277
 278                 arch_set_irn_register(arch_env, cnstr, reg);
 279                 pset_insert_ptr(alloc_env->pre_colored, cnstr);
 280
 281                 DBG((dbg, LEVEL_2, "\tConstrained node: %+F set to %s\n", irn, reg->name));
 282
 283                 /*
 284                  * The color of the constrained node must not be used!
 285                  * The Proj which has been assigned that color might
 286                  * interfere with the constrained node which leads
 287                  * to an invalid register allocation.
 288                  */
 289                 assert(!bitset_is_set(colors_used, reg->index));
 290
 291                 /*
 292                  * Look for a Proj not interfering with the constrained node.
 293                  * This Proj can be safely set to the constrafined nodes
 294                  * color.
 295                  */
 296                 for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) {
 297                         if(!values_interfere(irn, cnstr)) {
 298
 299                                 DBG((dbg, LEVEL_2, "\tFound Proj not interfering with contr node %+F set to %s\n", irn, reg->name));
 300                                 pset_insert_ptr(alloc_env->pre_colored, irn);
 301                                 arch_set_irn_register(arch_env, irn, reg);
 302                                 bitset_set(colors_used, reg->index);
 303                                 pset_remove_ptr(leftover, irn);
 304                                 pset_break(leftover);
 305                                 break;
 306                         }
 307                 }
 308         }
 309
 310         /*
 311          * Color the leftover Projs with the leftover colors.
 312          */
 313         for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) {
 314                 col = bitset_next_clear(colors_used, 0);
 315                 reg = arch_register_for_index(env->cls, col);
 316
 317                 arch_set_irn_register(arch_env, irn, reg);
 318                 pset_insert_ptr(alloc_env->pre_colored, irn);
 319                 bitset_set(colors_used, col);
 320
 321                 DBG((dbg, LEVEL_2, "\tLeft over %+F set to %s\n", irn, reg->name));
 322         }
 323
 324         del_pset(leftover);
 325         return cnstr;
 326 }
 327
 328 /**
 329  * Handle constraint nodes in each basic block.
 330  * be_insert_constr_perms() inserts Perm nodes which perm
 331  * over all values live at the constrained node right in front
 332  * of the constrained node. These Perms signal a constrained node.
 333  * For further comments, refer to handle_constraints_at_perm().
 334  */
 335 static void constraints(ir_node *bl, void *data)
 336 {
 337         be_chordal_alloc_env_t *env = data;
 338         arch_env_t *arch_env        = env->chordal_env->main_env->arch_env;
 339         ir_node *irn;
 340
 341         for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) {
 342                 if(be_is_Perm(irn))
 343                         irn = handle_constraints_at_perm(env, irn);
 344         }
 345 }
 346
 347 /**
 348  * Annotate the register pressure to the nodes and compute
 349  * the liveness intervals.
 350  * @param block The block to do it for.
 351  * @param env_ptr The environment.
 352  */
 353 static void pressure(ir_node *block, void *env_ptr)
 354 {
 355 /* Convenience macro for a def */
 356 #define border_def(irn, step, real) \
 357         border_add(env, head, irn, step, pressure--, 1, real)
 358
 359 /* Convenience macro for a use */
 360 #define border_use(irn, step, real) \
 361         border_add(env, head, irn, step, ++pressure, 0, real)
 362
 363         be_chordal_alloc_env_t *alloc_env = env_ptr;
 364         be_chordal_env_t *env             = alloc_env->chordal_env;
 365         bitset_t *live                    = alloc_env->live;
 366         firm_dbg_module_t *dbg            = env->dbg;
 367         ir_node *irn;
 368
 369         int i, n;
 370         unsigned step = 0;
 371         unsigned pressure = 0;
 372         struct list_head *head;
 373         pset *live_in = put_live_in(block, pset_new_ptr_default());
 374         pset *live_end = put_live_end(block, pset_new_ptr_default());
 375
 376         DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
 377         bitset_clear_all(live);
 378
 379         /* Set up the border list in the block info */
 380         head = obstack_alloc(&env->obst, sizeof(*head));
 381         INIT_LIST_HEAD(head);
 382         assert(pmap_get(env->border_heads, block) == NULL);
 383         pmap_insert(env->border_heads, block, head);
 384
 385         /*
 386          * Make final uses of all values live out of the block.
 387          * They are necessary to build up real intervals.
 388          */
 389         for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
 390                 if(has_reg_class(env, irn)) {
 391                         DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
 392                         bitset_set(live, get_irn_graph_nr(irn));
 393                         border_use(irn, step, 0);
 394                 }
 395         }
 396         ++step;
 397
 398         /*
 399          * Determine the last uses of a value inside the block, since they are
 400          * relevant for the interval borders.
 401          */
 402         sched_foreach_reverse(block, irn) {
 403                 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
 404                 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
 405
 406                 /*
 407                  * If the node defines some value, which can put into a
 408                  * register of the current class, make a border for it.
 409                  */
 410                 if(has_reg_class(env, irn)) {
 411                         int nr = get_irn_graph_nr(irn);
 412
 413                         bitset_clear(live, nr);
 414                         border_def(irn, step, 1);
 415                 }
 416
 417                 /*
 418                  * If the node is no phi node we can examine the uses.
 419                  */
 420                 if(!is_Phi(irn)) {
 421                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 422                                 ir_node *op = get_irn_n(irn, i);
 423
 424                                 if(has_reg_class(env, op)) {
 425                                         int nr = get_irn_graph_nr(op);
 426
 427                                         DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
 428
 429                                         if(!bitset_is_set(live, nr)) {
 430                                                 border_use(op, step, 1);
 431                                                 bitset_set(live, nr);
 432                                         }
 433                                 }
 434                         }
 435                 }
 436                 ++step;
 437         }
 438
 439         /*
 440          * Add initial defs for all values live in.
 441          */
 442         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 443                 if(has_reg_class(env, irn)) {
 444
 445                         /* Mark the value live in. */
 446                         bitset_set(live, get_irn_graph_nr(irn));
 447
 448                         /* Add the def */
 449                         border_def(irn, step, 0);
 450                 }
 451         }
 452
 453
 454   del_pset(live_in);
 455   del_pset(live_end);
 456 }
 457
 458 static void assign(ir_node *block, void *env_ptr)
 459 {
 460         be_chordal_alloc_env_t *alloc_env = env_ptr;
 461         be_chordal_env_t *env       = alloc_env->chordal_env;
 462         firm_dbg_module_t *dbg      = env->dbg;
 463         bitset_t *live              = alloc_env->live;
 464         bitset_t *colors            = alloc_env->colors;
 465         bitset_t *in_colors         = alloc_env->in_colors;
 466         const arch_env_t *arch_env  = env->main_env->arch_env;
 467
 468         const ir_node *irn;
 469         border_t *b;
 470         struct list_head *head = get_block_border_head(env, block);
 471         pset *live_in = put_live_in(block, pset_new_ptr_default());
 472
 473         bitset_clear_all(live);
 474         bitset_clear_all(colors);
 475         bitset_clear_all(in_colors);
 476
 477         DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
 478         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 479         list_for_each_entry(border_t, b, head, list) {
 480                 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
 481                                         b->irn, get_irn_graph_nr(b->irn)));
 482         }
 483
 484         /*
 485          * Add initial defs for all values live in.
 486          * Since their colors have already been assigned (The dominators were
 487          * allocated before), we have to mark their colors as used also.
 488          */
 489         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 490                 if(has_reg_class(env, irn)) {
 491                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 492                         int col;
 493
 494                         assert(reg && "Node must have been assigned a register");
 495                         col = arch_register_get_index(reg);
 496
 497                         /* Mark the color of the live in value as used. */
 498                         bitset_set(colors, col);
 499                         bitset_set(in_colors, col);
 500
 501                         /* Mark the value live in. */
 502                         bitset_set(live, get_irn_graph_nr(irn));
 503                 }
 504         }
 505
 506         /*
 507          * Mind that the sequence of defs from back to front defines a perfect
 508          * elimination order. So, coloring the definitions from first to last
 509          * will work.
 510          */
 511         list_for_each_entry_reverse(border_t, b, head, list) {
 512                 ir_node *irn = b->irn;
 513                 int nr = get_irn_graph_nr(irn);
 514
 515                 /*
 516                  * Assign a color, if it is a local def. Global defs already have a
 517                  * color.
 518                  */
 519                 if(b->is_def && !is_live_in(block, irn)) {
 520                         const arch_register_t *reg;
 521                         int col = NO_COLOR;
 522
 523                         DBG((dbg, LEVEL_4, "\tcolors in use: %b\n", colors));
 524
 525                         if(pset_find_ptr(alloc_env->pre_colored, irn)) {
 526                                 reg = arch_get_irn_register(arch_env, irn);
 527                                 col = reg->index;
 528                                 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
 529                         }
 530
 531                         else {
 532                                 col = bitset_next_clear(colors, 0);
 533                                 reg = arch_register_for_index(env->cls, col);
 534                                 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
 535                         }
 536
 537                         bitset_set(colors, col);
 538                         arch_set_irn_register(arch_env, irn, reg);
 539
 540                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
 541             arch_register_get_name(reg), col, irn));
 542
 543                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 544                         bitset_set(live, nr);
 545                 }
 546
 547                 /* Clear the color upon a use. */
 548                 else if(!b->is_def) {
 549                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 550                         int col;
 551
 552                         assert(reg && "Register must have been assigned");
 553
 554                         col = arch_register_get_index(reg);
 555                         assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 556
 557                         bitset_clear(colors, col);
 558                         bitset_clear(live, nr);
 559                 }
 560         }
 561
 562         del_pset(live_in);
 563 }
 564
 565 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
 566 {
 567         int node_count        = get_graph_node_count(chordal_env->irg);
 568         int colors_n          = arch_register_class_n_regs(chordal_env->cls);
 569         ir_graph *irg         = chordal_env->irg;
 570
 571         be_chordal_alloc_env_t env;
 572
 573         if(get_irg_dom_state(irg) != dom_consistent)
 574                 compute_doms(irg);
 575
 576         env.chordal_env  = chordal_env;
 577         env.live         = bitset_malloc(node_count);
 578         env.colors       = bitset_malloc(colors_n);
 579         env.in_colors    = bitset_malloc(colors_n);
 580         env.colors_n     = colors_n;
 581         env.pre_colored  = pset_new_ptr_default();
 582
 583         /* Handle register targeting constraints */
 584         dom_tree_walk_irg(irg, constraints, NULL, &env);
 585
 586         /* First, determine the pressure */
 587         dom_tree_walk_irg(irg, pressure, NULL, &env);
 588
 589         /* Assign the colors */
 590         dom_tree_walk_irg(irg, assign, NULL, &env);
 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, chordal_env, plotter, env->arch_env, cls);
 601         plotter_free(plotter);
 602         }
 603 #endif
 604
 605         free(env.live);
 606         free(env.colors);
 607         free(env.in_colors);
 608
 609         del_pset(env.pre_colored);
 610 }