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 static int try_pre_color(be_chordal_env_t *env, ir_node *irn,
 169                                                  pset *pre_colored, bitset_t *colors_used)
 170 {
 171         arch_register_req_t req;
 172
 173         if(arch_get_register_req(env->main_env->arch_env, &req, irn, -1) && arch_register_req_is(&req, limited)) {
 174
 175                 bitset_t *bs          = bitset_alloca(env->cls->n_regs);
 176                 const arch_register_t *reg;
 177                 int col;
 178
 179                 req.limited(irn, -1, bs);
 180                 col = bitset_next_set(bs, 0);
 181                 reg = arch_register_for_index(env->cls, col);
 182
 183                 pset_insert_ptr(pre_colored, irn);
 184                 arch_set_irn_register(env->main_env->arch_env, irn, reg);
 185                 bitset_set(colors_used, col);
 186
 187                 DBG((env->dbg, LEVEL_2, "pre coloring %+F with %s\n", irn, reg->name));
 188
 189                 return 1;
 190         }
 191
 192         return 0;
 193 }
 194
 195 /**
 196  * Handle register targeting constraints signaled by a Perm.
 197  * @param alloc_env    Private data for the allocation phase.
 198  * @param perm         The Perm node guarding the constrained node.
 199  * @return             The constrained node.
 200
 201                 Pro-coloring works as follows:
 202
 203          +-----------------------------------+
 204          |            Perm                   |
 205          +---.-------.--------.---------.----+
 206              |       |        |         |
 207          +---+--+    |        |         |
 208          | Proj |    |        |         |
 209          +------+    |        |         |
 210                      |        |         |
 211                   +--+---+    |         |
 212                   | Proj |    |         |
 213                   +--.---+    |         |
 214                      |        |         |
 215                      |     +--+---+     |
 216                      |     | Proj |     |
 217                      |     +------+     |
 218                       |                 |
 219                       |             +---+--+
 220                        `-.          | Proj | Result:
 221                           `._       +---.--+ R1
 222                              `.         |
 223                                `-.      |
 224                                   `._   |
 225                                     +`.-+--+
 226                                     |Constr| Result:
 227                                     +------+ R2
 228
 229                 1) Look at all Projs of the Perm if they have output constraints.
 230                    If one has an output constraint, pre-color it, else record it
 231                    in the set leftover. Its color has to be chosen after all
 232                    constrained nodes are colored. Furthermore record all colors
 233                    used in the pre-coloring in the set colors_used.
 234
 235                 2) Look whether the first node not a Proj (this is the constrained
 236                    node due to which the Perm has been inserted) has an output
 237                    constraint. If yes, pre-color the node accordingly else do nothing
 238                    since the node's input constraints are modelled by the Proj's
 239                    output constraint.
 240
 241                    There's one subtle point here: If thenode has an output constraint
 242                    and the live range of some Proj ends at that node, we must give
 243                    that Proj the color of the constrained node. Otherwise the
 244                    available colors may not suffice for the rest of the projs.
 245
 246                 3) At last, color the Projs which have not been colored yet with the
 247                    left over colors.
 248
 249                    So afterwards, everything including the constrained node will
 250                    be colored and the assign() phase can complete this coloring.
 251                    Note that therefore, we put the pre-colored nodes in a set
 252                    called pre_colored().
 253
 254  */
 255 static ir_node *handle_constraints_at_perm(be_chordal_alloc_env_t *alloc_env, ir_node *perm)
 256 {
 257         be_chordal_env_t *env      = alloc_env->chordal_env;
 258         firm_dbg_module_t *dbg     = env->dbg;
 259         const arch_env_t *arch_env = env->main_env->arch_env;
 260
 261         pset *leftover        = pset_new_ptr(8);
 262         pset *pre_colored     = pset_new_ptr(8);
 263         bitset_t *colors_used = bitset_alloca(env->cls->n_regs);
 264         ir_node *irn, *cnstr, *last;
 265         int has_cnstr = 0;
 266
 267         assert(be_is_Perm(perm));
 268
 269         DBG((dbg, LEVEL_2, "Constraints on %+F\n", perm));
 270
 271         /*
 272          * Color constrained Projs first.
 273          */
 274         for(irn = sched_next(perm); is_Proj(irn); irn = sched_next(irn))
 275                 if(!try_pre_color(env, irn, pre_colored, colors_used))
 276                         pset_insert_ptr(leftover, irn);
 277
 278         cnstr = irn;
 279         last  = irn;
 280
 281         if(get_irn_mode(cnstr) == mode_T) {
 282                 for(irn = sched_next(cnstr); is_Proj(irn); irn = sched_next(irn))
 283                         if(!try_pre_color(env, irn, pre_colored, colors_used))
 284                                 pset_insert_ptr(leftover, irn);
 285
 286                 last = sched_prev(irn);
 287         }
 288
 289         else
 290                 try_pre_color(env, cnstr, pre_colored, colors_used);
 291
 292         pset_insert_pset_ptr(alloc_env->pre_colored, pre_colored);
 293
 294         for(irn = pset_first(leftover); irn; irn = pset_next(leftover)) {
 295                 const arch_register_t *reg;
 296                 ir_node *precol;
 297                 int colored = 0;
 298
 299                 for(precol = pset_first(pre_colored); precol; precol = pset_next(pre_colored)) {
 300                         const arch_register_t *pre_col_reg = arch_get_irn_register(arch_env, precol);
 301
 302                         if(!values_interfere(irn, precol)) {
 303                                 reg = arch_get_irn_register(arch_env, precol);
 304                                 pset_break(pre_colored);
 305                                 pset_remove_ptr(pre_colored, precol);
 306                                 DBG((dbg, LEVEL_2, "non-interfering %+F setting to %s\n", irn, reg->name));
 307                                 colored = 1;
 308                                 break;
 309                         }
 310                 }
 311
 312                 if(!colored) {
 313                         int col = bitset_next_clear(colors_used, 0);
 314
 315                         assert(col >= 0 && col < env->cls->n_regs && "There must be a register left");
 316                         reg = arch_register_for_index(env->cls, col);
 317
 318                         DBG((dbg, LEVEL_2, "coloring leftover %+F with %s\n", irn, reg->name));
 319                 }
 320
 321                 arch_set_irn_register(arch_env, irn, reg);
 322                 pset_insert_ptr(alloc_env->pre_colored, irn);
 323                 bitset_set(colors_used, reg->index);
 324         }
 325
 326         del_pset(leftover);
 327         del_pset(pre_colored);
 328
 329         return last;
 330 }
 331
 332 /**
 333  * Handle constraint nodes in each basic block.
 334  * be_insert_constr_perms() inserts Perm nodes which perm
 335  * over all values live at the constrained node right in front
 336  * of the constrained node. These Perms signal a constrained node.
 337  * For further comments, refer to handle_constraints_at_perm().
 338  */
 339 static void constraints(ir_node *bl, void *data)
 340 {
 341         be_chordal_alloc_env_t *env = data;
 342         arch_env_t *arch_env        = env->chordal_env->main_env->arch_env;
 343         ir_node *irn;
 344
 345         for(irn = sched_first(bl); !sched_is_end(irn); irn = sched_next(irn)) {
 346                 if(be_is_Perm(irn) && arch_irn_has_reg_class(arch_env, irn, 0, env->chordal_env->cls))
 347                         irn = handle_constraints_at_perm(env, irn);
 348         }
 349 }
 350
 351 /**
 352  * Annotate the register pressure to the nodes and compute
 353  * the liveness intervals.
 354  * @param block The block to do it for.
 355  * @param env_ptr The environment.
 356  */
 357 static void pressure(ir_node *block, void *env_ptr)
 358 {
 359 /* Convenience macro for a def */
 360 #define border_def(irn, step, real) \
 361         border_add(env, head, irn, step, pressure--, 1, real)
 362
 363 /* Convenience macro for a use */
 364 #define border_use(irn, step, real) \
 365         border_add(env, head, irn, step, ++pressure, 0, real)
 366
 367         be_chordal_alloc_env_t *alloc_env = env_ptr;
 368         be_chordal_env_t *env             = alloc_env->chordal_env;
 369         bitset_t *live                    = alloc_env->live;
 370         firm_dbg_module_t *dbg            = env->dbg;
 371         ir_node *irn;
 372
 373         int i, n;
 374         unsigned step = 0;
 375         unsigned pressure = 0;
 376         struct list_head *head;
 377         pset *live_in = put_live_in(block, pset_new_ptr_default());
 378         pset *live_end = put_live_end(block, pset_new_ptr_default());
 379
 380         DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
 381         bitset_clear_all(live);
 382
 383         /* Set up the border list in the block info */
 384         head = obstack_alloc(&env->obst, sizeof(*head));
 385         INIT_LIST_HEAD(head);
 386         assert(pmap_get(env->border_heads, block) == NULL);
 387         pmap_insert(env->border_heads, block, head);
 388
 389         /*
 390          * Make final uses of all values live out of the block.
 391          * They are necessary to build up real intervals.
 392          */
 393         for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
 394                 if(has_reg_class(env, irn)) {
 395                         DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
 396                         bitset_set(live, get_irn_graph_nr(irn));
 397                         border_use(irn, step, 0);
 398                 }
 399         }
 400         ++step;
 401
 402         /*
 403          * Determine the last uses of a value inside the block, since they are
 404          * relevant for the interval borders.
 405          */
 406         sched_foreach_reverse(block, irn) {
 407                 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
 408                 DBG((dbg, LEVEL_2, "\tlive: %b\n", live));
 409
 410                 /*
 411                  * If the node defines some value, which can put into a
 412                  * register of the current class, make a border for it.
 413                  */
 414                 if(has_reg_class(env, irn)) {
 415                         int nr = get_irn_graph_nr(irn);
 416
 417                         bitset_clear(live, nr);
 418                         border_def(irn, step, 1);
 419                 }
 420
 421                 /*
 422                  * If the node is no phi node we can examine the uses.
 423                  */
 424                 if(!is_Phi(irn)) {
 425                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 426                                 ir_node *op = get_irn_n(irn, i);
 427
 428                                 if(has_reg_class(env, op)) {
 429                                         int nr = get_irn_graph_nr(op);
 430
 431                                         DBG((dbg, LEVEL_4, "\t\tpos: %d, use: %+F\n", i, op));
 432
 433                                         if(!bitset_is_set(live, nr)) {
 434                                                 border_use(op, step, 1);
 435                                                 bitset_set(live, nr);
 436                                         }
 437                                 }
 438                         }
 439                 }
 440                 ++step;
 441         }
 442
 443         /*
 444          * Add initial defs for all values live in.
 445          */
 446         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 447                 if(has_reg_class(env, irn)) {
 448
 449                         /* Mark the value live in. */
 450                         bitset_set(live, get_irn_graph_nr(irn));
 451
 452                         /* Add the def */
 453                         border_def(irn, step, 0);
 454                 }
 455         }
 456
 457
 458   del_pset(live_in);
 459   del_pset(live_end);
 460 }
 461
 462 static void assign(ir_node *block, void *env_ptr)
 463 {
 464         be_chordal_alloc_env_t *alloc_env = env_ptr;
 465         be_chordal_env_t *env       = alloc_env->chordal_env;
 466         firm_dbg_module_t *dbg      = env->dbg;
 467         bitset_t *live              = alloc_env->live;
 468         bitset_t *colors            = alloc_env->colors;
 469         bitset_t *in_colors         = alloc_env->in_colors;
 470         const arch_env_t *arch_env  = env->main_env->arch_env;
 471
 472         const ir_node *irn;
 473         border_t *b;
 474         struct list_head *head = get_block_border_head(env, block);
 475         pset *live_in = put_live_in(block, pset_new_ptr_default());
 476
 477         bitset_clear_all(live);
 478         bitset_clear_all(colors);
 479         bitset_clear_all(in_colors);
 480
 481         DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
 482         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 483         list_for_each_entry(border_t, b, head, list) {
 484                 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
 485                                         b->irn, get_irn_graph_nr(b->irn)));
 486         }
 487
 488         /*
 489          * Add initial defs for all values live in.
 490          * Since their colors have already been assigned (The dominators were
 491          * allocated before), we have to mark their colors as used also.
 492          */
 493         for(irn = pset_first(live_in); irn; irn = pset_next(live_in)) {
 494                 if(has_reg_class(env, irn)) {
 495                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 496                         int col;
 497
 498                         assert(reg && "Node must have been assigned a register");
 499                         col = arch_register_get_index(reg);
 500
 501                         /* Mark the color of the live in value as used. */
 502                         bitset_set(colors, col);
 503                         bitset_set(in_colors, col);
 504
 505                         /* Mark the value live in. */
 506                         bitset_set(live, get_irn_graph_nr(irn));
 507                 }
 508         }
 509
 510         /*
 511          * Mind that the sequence of defs from back to front defines a perfect
 512          * elimination order. So, coloring the definitions from first to last
 513          * will work.
 514          */
 515         list_for_each_entry_reverse(border_t, b, head, list) {
 516                 ir_node *irn = b->irn;
 517                 int nr = get_irn_graph_nr(irn);
 518
 519                 /*
 520                  * Assign a color, if it is a local def. Global defs already have a
 521                  * color.
 522                  */
 523                 if(b->is_def && !is_live_in(block, irn)) {
 524                         const arch_register_t *reg;
 525                         int col = NO_COLOR;
 526
 527                         if(pset_find_ptr(alloc_env->pre_colored, irn)) {
 528                                 reg = arch_get_irn_register(arch_env, irn);
 529                                 col = reg->index;
 530                                 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
 531                         }
 532
 533                         else {
 534                                 col = bitset_next_clear(colors, 0);
 535                                 reg = arch_register_for_index(env->cls, col);
 536                                 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
 537                         }
 538
 539                         bitset_set(colors, col);
 540                         arch_set_irn_register(arch_env, irn, reg);
 541
 542                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n",
 543             arch_register_get_name(reg), col, irn));
 544
 545                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 546                         bitset_set(live, nr);
 547                 }
 548
 549                 /* Clear the color upon a use. */
 550                 else if(!b->is_def) {
 551                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 552                         int col;
 553
 554                         assert(reg && "Register must have been assigned");
 555
 556                         col = arch_register_get_index(reg);
 557                         assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 558
 559                         bitset_clear(colors, col);
 560                         bitset_clear(live, nr);
 561                 }
 562         }
 563
 564         del_pset(live_in);
 565 }
 566
 567 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
 568 {
 569         int node_count        = get_graph_node_count(chordal_env->irg);
 570         int colors_n          = arch_register_class_n_regs(chordal_env->cls);
 571         ir_graph *irg         = chordal_env->irg;
 572
 573         be_chordal_alloc_env_t env;
 574
 575         if(get_irg_dom_state(irg) != dom_consistent)
 576                 compute_doms(irg);
 577
 578         env.chordal_env  = chordal_env;
 579         env.live         = bitset_malloc(node_count);
 580         env.colors       = bitset_malloc(colors_n);
 581         env.in_colors    = bitset_malloc(colors_n);
 582         env.colors_n     = colors_n;
 583         env.pre_colored  = pset_new_ptr_default();
 584
 585         /* Handle register targeting constraints */
 586         dom_tree_walk_irg(irg, constraints, NULL, &env);
 587
 588         /* First, determine the pressure */
 589         dom_tree_walk_irg(irg, pressure, NULL, &env);
 590
 591         /* Assign the colors */
 592         dom_tree_walk_irg(irg, assign, NULL, &env);
 593
 594 #ifdef DUMP_INTERVALS
 595         {
 596                 char buf[128];
 597         plotter_t *plotter;
 598
 599                 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", cls->name, irg);
 600         plotter = new_plotter_ps(buf);
 601
 602         draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter, env->arch_env, cls);
 603         plotter_free(plotter);
 604         }
 605 #endif
 606
 607         free(env.live);
 608         free(env.colors);
 609         free(env.in_colors);
 610
 611         del_pset(env.pre_colored);
 612 }