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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Chordal register allocation.
  23  * @author      Sebastian Hack
  24  * @date        08.12.2004
  25  * @version     $Id$
  26  */
  27 #include "config.h"
  28
  29 #include <ctype.h>
  30
  31 #include "obst.h"
  32 #include "pset.h"
  33 #include "list.h"
  34 #include "bitset.h"
  35 #include "raw_bitset.h"
  36 #include "iterator.h"
  37 #include "bipartite.h"
  38 #include "hungarian.h"
  39
  40 #include "irmode_t.h"
  41 #include "irgraph_t.h"
  42 #include "irprintf_t.h"
  43 #include "irgwalk.h"
  44 #include "irdump.h"
  45 #include "irdom.h"
  46 #include "irtools.h"
  47 #include "irbitset.h"
  48 #include "debug.h"
  49 #include "iredges.h"
  50
  51 #include "beutil.h"
  52 #include "besched.h"
  53 #include "besched.h"
  54 #include "belive_t.h"
  55 #include "benode.h"
  56 #include "bearch.h"
  57 #include "beirgmod.h"
  58 #include "beifg.h"
  59 #include "beinsn_t.h"
  60 #include "bestatevent.h"
  61 #include "beirg.h"
  62 #include "beintlive_t.h"
  63 #include "bera.h"
  64 #include "bechordal_t.h"
  65 #include "bechordal_draw.h"
  66 #include "bemodule.h"
  67
  68 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  69
  70 #define NO_COLOR (-1)
  71
  72 #define DUMP_INTERVALS
  73
  74 typedef struct _be_chordal_alloc_env_t {
  75         be_chordal_env_t *chordal_env;
  76
  77         pset *pre_colored;     /**< Set of precolored nodes. */
  78         bitset_t *live;            /**< A liveness bitset. */
  79         bitset_t *tmp_colors;  /**< An auxiliary bitset which is as long as the number of colors in the class. */
  80         bitset_t *colors;          /**< The color mask. */
  81         bitset_t *in_colors;   /**< Colors used by live in values. */
  82         int colors_n;          /**< The number of colors. */
  83 } be_chordal_alloc_env_t;
  84
  85 #include "fourcc.h"
  86
  87 /* Make a fourcc for border checking. */
  88 #define BORDER_FOURCC                           FOURCC('B', 'O', 'R', 'D')
  89
  90 #if 0
  91 static void check_border_list(struct list_head *head)
  92 {
  93         border_t *x;
  94         list_for_each_entry(border_t, x, head, list) {
  95                 assert(x->magic == BORDER_FOURCC);
  96         }
  97 }
  98
  99 static void check_heads(be_chordal_env_t *env)
 100 {
 101         pmap_entry *ent;
 102         for (ent = pmap_first(env->border_heads); ent; ent = pmap_next(env->border_heads)) {
 103                 /* ir_printf("checking border list of block %+F\n", ent->key); */
 104                 check_border_list(ent->value);
 105         }
 106 }
 107 #endif
 108
 109 /**
 110  * Add an interval border to the list of a block's list
 111  * of interval border.
 112  * @note You always have to create the use before the def.
 113  * @param env The environment.
 114  * @param head The list head to enqueue the borders.
 115  * @param irn The node (value) the border belongs to.
 116  * @param pressure The pressure at this point in time.
 117  * @param step A time step for the border.
 118  * @param is_def Is the border a use or a def.
 119  * @return The created border.
 120  */
 121 static inline border_t *border_add(be_chordal_env_t *env, struct list_head *head,
 122                         ir_node *irn, unsigned step, unsigned pressure,
 123                         unsigned is_def, unsigned is_real)
 124 {
 125         border_t *b;
 126
 127         if (!is_def) {
 128                 border_t *def;
 129
 130                 b = OALLOC(env->obst, border_t);
 131
 132                 /* also allocate the def and tie it to the use. */
 133                 def = OALLOCZ(env->obst, border_t);
 134                 b->other_end = def;
 135                 def->other_end = b;
 136
 137                 /*
 138                  * Set the link field of the irn to the def.
 139                  * This strongly relies on the fact, that the use is always
 140                  * made before the def.
 141                  */
 142                 set_irn_link(irn, def);
 143
 144                 DEBUG_ONLY(b->magic = BORDER_FOURCC);
 145                 DEBUG_ONLY(def->magic = BORDER_FOURCC);
 146         } else {
 147                 /*
 148                  * If the def is encountered, the use was made and so was the
 149                  * the def node (see the code above). It was placed into the
 150                  * link field of the irn, so we can get it there.
 151                  */
 152                 b = get_irn_link(irn);
 153
 154                 DEBUG_ONLY(assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered"));
 155         }
 156
 157         b->pressure = pressure;
 158         b->is_def = is_def;
 159         b->is_real = is_real;
 160         b->irn = irn;
 161         b->step = step;
 162         list_add_tail(&b->list, head);
 163         DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
 164
 165
 166         return b;
 167 }
 168
 169 /**
 170  * Check, if an irn is of the register class currently under processing.
 171  * @param env The chordal environment.
 172  * @param irn The node.
 173  * @return 1, if the node is of that register class, 0 if not.
 174  */
 175 static inline int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
 176 {
 177         return arch_irn_consider_in_reg_alloc(env->cls, irn);
 178 }
 179
 180 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
 181 {
 182         bitset_t *tmp = alloc_env->tmp_colors;
 183         bitset_copy(tmp, colors);
 184         bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
 185         return bitset_next_clear(tmp, 0);
 186 }
 187
 188 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
 189 {
 190         bitset_t *res = bs;
 191
 192         if (!o1) {
 193                 bitset_copy(bs, o2->regs);
 194                 return bs;
 195         }
 196
 197         if (!o2) {
 198                 bitset_copy(bs, o1->regs);
 199                 return bs;
 200         }
 201
 202         assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
 203
 204         if (bitset_contains(o1->regs, o2->regs)) {
 205                 bitset_copy(bs, o1->regs);
 206         } else if (bitset_contains(o2->regs, o1->regs)) {
 207                 bitset_copy(bs, o2->regs);
 208         } else {
 209                 res = NULL;
 210         }
 211
 212         return res;
 213 }
 214
 215 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
 216 {
 217         be_insn_env_t ie;
 218
 219         ie.ignore_colors = env->ignore_colors;
 220         ie.obst          = env->obst;
 221         ie.cls           = env->cls;
 222         return be_scan_insn(&ie, irn);
 223 }
 224
 225 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
 226 {
 227         const be_chordal_env_t *env = alloc_env->chordal_env;
 228         bitset_t               *bs  = bitset_alloca(env->cls->n_regs);
 229         int                     i;
 230         int                     j;
 231
 232         /*
 233          * For each out operand, try to find an in operand which can be assigned the
 234          * same register as the out operand.
 235         */
 236         for (j = 0; j < insn->use_start; ++j) {
 237                 int smallest         = -1;
 238                 int smallest_n_regs  = 2 * env->cls->n_regs + 1;
 239                 be_operand_t *out_op = &insn->ops[j];
 240
 241                 /* Try to find an in operand which has ... */
 242                 for (i = insn->use_start; i < insn->n_ops; ++i) {
 243                         int n_total;
 244                         const be_operand_t *op = &insn->ops[i];
 245
 246                         if (op->partner != NULL)
 247                                 continue;
 248                         if (be_values_interfere(env->birg->lv, op->irn, op->carrier))
 249                                 continue;
 250
 251                         bitset_clear_all(bs);
 252                         bitset_copy(bs, op->regs);
 253                         bitset_and(bs, out_op->regs);
 254                         n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
 255
 256                         if (!bitset_is_empty(bs) && n_total < smallest_n_regs) {
 257                                 smallest = i;
 258                                 smallest_n_regs = n_total;
 259                         }
 260                 }
 261
 262                 if (smallest >= 0) {
 263                         be_operand_t *partner = &insn->ops[smallest];
 264                         for (i = insn->use_start; i < insn->n_ops; ++i) {
 265                                 if (insn->ops[i].carrier == partner->carrier)
 266                                         insn->ops[i].partner = out_op;
 267                         }
 268
 269                         out_op->partner  = partner;
 270                         partner->partner = out_op;
 271                 }
 272         }
 273 }
 274
 275
 276 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
 277                                         be_insn_t **the_insn)
 278 {
 279         be_chordal_env_t *env       = alloc_env->chordal_env;
 280         be_insn_t *insn             = *the_insn;
 281         ir_node *perm               = NULL;
 282         bitset_t *out_constr        = bitset_alloca(env->cls->n_regs);
 283         const ir_edge_t *edge;
 284         int i;
 285
 286         assert(insn->has_constraints && "only do this for constrained nodes");
 287
 288         /*
 289          * Collect all registers that occur in output constraints.
 290          * This is necessary, since if the insn has one of these as an input constraint
 291          * and the corresponding operand interferes with the insn, the operand must
 292          * be copied.
 293          */
 294         for (i = 0; i < insn->use_start; ++i) {
 295                 be_operand_t *op = &insn->ops[i];
 296                 if (op->has_constraints)
 297                         bitset_or(out_constr, op->regs);
 298         }
 299
 300         /*
 301          * Make the Perm, recompute liveness and re-scan the insn since the
 302          * in operands are now the Projs of the Perm.
 303          */
 304         perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
 305
 306         /* Registers are propagated by insert_Perm_after(). Clean them here! */
 307         if (perm == NULL)
 308                 return NULL;
 309
 310         be_stat_ev("constr_perm", get_irn_arity(perm));
 311         foreach_out_edge(perm, edge) {
 312                 ir_node *proj = get_edge_src_irn(edge);
 313                 arch_set_irn_register(proj, NULL);
 314         }
 315
 316         /*
 317          * We also have to re-build the insn since the input operands are now the Projs of
 318          * the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
 319          * the live sets may change.
 320          */
 321         obstack_free(env->obst, insn);
 322         *the_insn = insn = chordal_scan_insn(env, insn->irn);
 323
 324         /*
 325          * Copy the input constraints of the insn to the Perm as output
 326          * constraints. Succeeding phases (coalescing) will need that.
 327          */
 328         for (i = insn->use_start; i < insn->n_ops; ++i) {
 329                 be_operand_t *op = &insn->ops[i];
 330                 ir_node *proj = op->carrier;
 331                 /*
 332                  * Note that the predecessor must not be a Proj of the Perm,
 333                  * since ignore-nodes are not Perm'ed.
 334                  */
 335                 if (op->has_constraints &&  is_Proj(proj) && get_Proj_pred(proj) == perm) {
 336                         be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
 337                 }
 338         }
 339
 340         return perm;
 341 }
 342
 343 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 344                                    ir_node *irn, int *silent)
 345 {
 346         int n_regs;
 347         bitset_t *bs;
 348         ir_node **alloc_nodes;
 349         //hungarian_problem_t *bp;
 350         int *assignment;
 351         pmap *partners;
 352         int i, n_alloc;
 353         bitset_pos_t col;
 354         const ir_edge_t *edge;
 355         ir_node *perm = NULL;
 356         //int match_res, cost;
 357         be_chordal_env_t *env  = alloc_env->chordal_env;
 358         void *base             = obstack_base(env->obst);
 359         be_insn_t *insn        = chordal_scan_insn(env, irn);
 360         ir_node *res           = insn->next_insn;
 361         int be_silent          = *silent;
 362         bipartite_t *bp;
 363
 364         if (insn->pre_colored) {
 365                 int i;
 366                 for (i = 0; i < insn->use_start; ++i)
 367                         pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
 368         }
 369
 370         /*
 371          * If the current node is a barrier toggle the silent flag.
 372          * If we are in the start block, we are ought to be silent at the beginning,
 373          * so the toggling activates the constraint handling but skips the barrier.
 374          * If we are in the end block we handle the in requirements of the barrier
 375          * and set the rest to silent.
 376          */
 377         if (be_is_Barrier(irn))
 378                 *silent = !*silent;
 379
 380         if (be_silent)
 381                 goto end;
 382
 383         /*
 384          * Perms inserted before the constraint handling phase are considered to be
 385          * correctly precolored. These Perms arise during the ABI handling phase.
 386          */
 387         if (!insn->has_constraints)
 388                 goto end;
 389
 390         n_regs      = env->cls->n_regs;
 391         bs          = bitset_alloca(n_regs);
 392         alloc_nodes = ALLOCAN(ir_node*, n_regs);
 393         //bp          = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
 394         bp          = bipartite_new(n_regs, n_regs);
 395         assignment  = ALLOCAN(int, n_regs);
 396         partners    = pmap_create();
 397
 398         /*
 399          * prepare the constraint handling of this node.
 400          * Perms are constructed and Copies are created for constrained values
 401          * interfering with the instruction.
 402          */
 403         perm = pre_process_constraints(alloc_env, &insn);
 404
 405         /* find suitable in operands to the out operands of the node. */
 406         pair_up_operands(alloc_env, insn);
 407
 408         /*
 409          * look at the in/out operands and add each operand (and its possible partner)
 410          * to a bipartite graph (left: nodes with partners, right: admissible colors).
 411          */
 412         for (i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
 413                 be_operand_t *op = &insn->ops[i];
 414
 415                 /*
 416                  * If the operand has no partner or the partner has not been marked
 417                  * for allocation, determine the admissible registers and mark it
 418                  * for allocation by associating the node and its partner with the
 419                  * set of admissible registers via a bipartite graph.
 420                  */
 421                 if (!op->partner || !pmap_contains(partners, op->partner->carrier)) {
 422                         ir_node *partner = op->partner ? op->partner->carrier : NULL;
 423                         int i;
 424
 425                         pmap_insert(partners, op->carrier, partner);
 426                         if (partner != NULL)
 427                                 pmap_insert(partners, partner, op->carrier);
 428
 429                         /* don't insert a node twice */
 430                         for (i = 0; i < n_alloc; ++i) {
 431                                 if (alloc_nodes[i] == op->carrier) {
 432                                         break;
 433                                 }
 434                         }
 435                         if (i < n_alloc)
 436                                 continue;
 437
 438                         alloc_nodes[n_alloc] = op->carrier;
 439
 440                         DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
 441                              partner));
 442
 443                         bitset_clear_all(bs);
 444                         get_decisive_partner_regs(bs, op, op->partner);
 445
 446                         DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
 447                              bs));
 448
 449                         bitset_foreach(bs, col) {
 450                                 //hungarian_add(bp, n_alloc, col, 1);
 451                                 bipartite_add(bp, n_alloc, col);
 452                         }
 453
 454                         n_alloc++;
 455                 }
 456         }
 457
 458         /*
 459          * Put all nodes which live through the constrained instruction also to the
 460          * allocation bipartite graph. They are considered unconstrained.
 461          */
 462         if (perm != NULL) {
 463                 foreach_out_edge(perm, edge) {
 464                         int i;
 465                         ir_node *proj = get_edge_src_irn(edge);
 466
 467                         assert(is_Proj(proj));
 468
 469                         if (!be_values_interfere(env->birg->lv, proj, irn)
 470                                         || pmap_contains(partners, proj))
 471                                 continue;
 472
 473                         /* don't insert a node twice */
 474                         for (i = 0; i < n_alloc; ++i) {
 475                                 if (alloc_nodes[i] == proj) {
 476                                         break;
 477                                 }
 478                         }
 479                         if (i < n_alloc)
 480                                 continue;
 481
 482
 483                         assert(n_alloc < n_regs);
 484
 485                         alloc_nodes[n_alloc] = proj;
 486                         pmap_insert(partners, proj, NULL);
 487
 488                         bitset_clear_all(bs);
 489                         arch_put_non_ignore_regs(env->cls, bs);
 490                         bitset_andnot(bs, env->ignore_colors);
 491                         bitset_foreach(bs, col) {
 492                                 //hungarian_add(bp, n_alloc, col, 1);
 493                                 bipartite_add(bp, n_alloc, col);
 494                         }
 495
 496                         n_alloc++;
 497                 }
 498         }
 499
 500         /* Compute a valid register allocation. */
 501 #if 0
 502         hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
 503         match_res = hungarian_solve(bp, assignment, &cost, 1);
 504         assert(match_res == 0 && "matching failed");
 505 #else
 506         bipartite_matching(bp, assignment);
 507 #endif
 508
 509         /* Assign colors obtained from the matching. */
 510         for (i = 0; i < n_alloc; ++i) {
 511                 const arch_register_t *reg;
 512                 ir_node *irn;
 513
 514                 assert(assignment[i] >= 0 && "there must have been a register assigned");
 515                 reg = arch_register_for_index(env->cls, assignment[i]);
 516                 assert(! (reg->type & arch_register_type_ignore));
 517
 518                 irn = alloc_nodes[i];
 519                 if (irn != NULL) {
 520                         arch_set_irn_register(irn, reg);
 521                         (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
 522                         DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
 523                 }
 524
 525                 irn = pmap_get(partners, alloc_nodes[i]);
 526                 if (irn != NULL) {
 527                         arch_set_irn_register(irn, reg);
 528                         (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
 529                         DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
 530                 }
 531         }
 532
 533         /* Allocate the non-constrained Projs of the Perm. */
 534         if (perm != NULL) {
 535                 bitset_clear_all(bs);
 536
 537                 /* Put the colors of all Projs in a bitset. */
 538                 foreach_out_edge(perm, edge) {
 539                         ir_node *proj              = get_edge_src_irn(edge);
 540                         const arch_register_t *reg = arch_get_irn_register(proj);
 541
 542                         if (reg != NULL)
 543                                 bitset_set(bs, reg->index);
 544                 }
 545
 546                 /* Assign the not yet assigned Projs of the Perm a suitable color. */
 547                 foreach_out_edge(perm, edge) {
 548                         ir_node *proj              = get_edge_src_irn(edge);
 549                         const arch_register_t *reg = arch_get_irn_register(proj);
 550
 551                         DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
 552
 553                         if (reg == NULL) {
 554                                 col = get_next_free_reg(alloc_env, bs);
 555                                 reg = arch_register_for_index(env->cls, col);
 556                                 bitset_set(bs, reg->index);
 557                                 arch_set_irn_register(proj, reg);
 558                                 pset_insert_ptr(alloc_env->pre_colored, proj);
 559                                 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
 560                         }
 561                 }
 562         }
 563
 564         bipartite_free(bp);
 565         //hungarian_free(bp);
 566         pmap_destroy(partners);
 567
 568 end:
 569         obstack_free(env->obst, base);
 570         return res;
 571 }
 572
 573 /**
 574  * Handle constraint nodes in each basic block.
 575  * handle_constraints() inserts Perm nodes which perm
 576  * over all values live at the constrained node right in front
 577  * of the constrained node. These Perms signal a constrained node.
 578  * For further comments, refer to handle_constraints().
 579  */
 580 static void constraints(ir_node *bl, void *data)
 581 {
 582         /*
 583          * Start silent in the start block.
 584          * The silence remains until the first barrier is seen.
 585          * Each other block is begun loud.
 586          */
 587         int                     silent = bl == get_irg_start_block(get_irn_irg(bl));
 588         be_chordal_alloc_env_t *env    = data;
 589         ir_node                *irn;
 590
 591         /*
 592          * If the block is the start block search the barrier and
 593          * start handling constraints from there.
 594          */
 595         for (irn = sched_first(bl); !sched_is_end(irn);) {
 596                 irn = handle_constraints(env, irn, &silent);
 597         }
 598 }
 599
 600 /**
 601  * Annotate the register pressure to the nodes and compute
 602  * the liveness intervals.
 603  * @param block The block to do it for.
 604  * @param env_ptr The environment.
 605  */
 606 static void pressure(ir_node *block, void *env_ptr)
 607 {
 608 /* Convenience macro for a def */
 609 #define border_def(irn, step, real) \
 610         border_add(env, head, irn, step, pressure--, 1, real)
 611
 612 /* Convenience macro for a use */
 613 #define border_use(irn, step, real) \
 614         border_add(env, head, irn, step, ++pressure, 0, real)
 615
 616         be_chordal_alloc_env_t *alloc_env = env_ptr;
 617         be_chordal_env_t *env             = alloc_env->chordal_env;
 618         bitset_t *live                    = alloc_env->live;
 619         ir_node *irn;
 620         be_lv_t *lv                       = env->birg->lv;
 621
 622         int i, n;
 623         bitset_pos_t elm;
 624         unsigned step = 0;
 625         unsigned pressure = 0;
 626         struct list_head *head;
 627
 628         DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
 629         bitset_clear_all(live);
 630
 631         /* Set up the border list in the block info */
 632         head = OALLOC(env->obst, struct list_head);
 633         INIT_LIST_HEAD(head);
 634         assert(pmap_get(env->border_heads, block) == NULL);
 635         pmap_insert(env->border_heads, block, head);
 636
 637         /*
 638          * Make final uses of all values live out of the block.
 639          * They are necessary to build up real intervals.
 640          */
 641         be_lv_foreach(lv, block, be_lv_state_end, i) {
 642                 ir_node *irn = be_lv_get_irn(lv, block, i);
 643                 if (has_reg_class(env, irn)) {
 644                         DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
 645                         bitset_set(live, get_irn_idx(irn));
 646                         border_use(irn, step, 0);
 647                 }
 648         }
 649         ++step;
 650
 651         /*
 652          * Determine the last uses of a value inside the block, since they are
 653          * relevant for the interval borders.
 654          */
 655         sched_foreach_reverse(block, irn) {
 656                 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
 657                 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
 658
 659                 if (get_irn_mode(irn) == mode_T) {
 660                         const ir_edge_t *edge;
 661
 662                         foreach_out_edge(irn, edge) {
 663                                 ir_node *proj = get_edge_src_irn(edge);
 664
 665                                 /*
 666                                  * If the node defines some value, which can put into a
 667                                  * register of the current class, make a border for it.
 668                                  */
 669                                 if (has_reg_class(env, proj)) {
 670                                         int nr = get_irn_idx(proj);
 671
 672                                         bitset_clear(live, nr);
 673                                         border_def(proj, step, 1);
 674                                 }
 675                         }
 676                 } else {
 677                         /*
 678                          * If the node defines some value, which can put into a
 679                          * register of the current class, make a border for it.
 680                          */
 681                         if (has_reg_class(env, irn)) {
 682                                 int nr = get_irn_idx(irn);
 683
 684                                 bitset_clear(live, nr);
 685                                 border_def(irn, step, 1);
 686                         }
 687                 }
 688
 689                 /*
 690                  * If the node is no phi node we can examine the uses.
 691                  */
 692                 if (!is_Phi(irn)) {
 693                         for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 694                                 ir_node *op = get_irn_n(irn, i);
 695
 696                                 if (has_reg_class(env, op)) {
 697                                         int nr = get_irn_idx(op);
 698                                         const char *msg = "-";
 699
 700                                         if (!bitset_is_set(live, nr)) {
 701                                                 border_use(op, step, 1);
 702                                                 bitset_set(live, nr);
 703                                                 msg = "X";
 704                                         }
 705
 706                                         DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
 707                                 }
 708                         }
 709                 }
 710                 ++step;
 711         }
 712
 713         bitset_foreach(live, elm) {
 714                 ir_node *irn = get_idx_irn(env->irg, elm);
 715                 if (be_is_live_in(lv, block, irn))
 716                         border_def(irn, step, 0);
 717         }
 718 }
 719
 720 static void assign(ir_node *block, void *env_ptr)
 721 {
 722         be_chordal_alloc_env_t *alloc_env = env_ptr;
 723         be_chordal_env_t *env       = alloc_env->chordal_env;
 724         bitset_t *live              = alloc_env->live;
 725         bitset_t *colors            = alloc_env->colors;
 726         bitset_t *in_colors         = alloc_env->in_colors;
 727         struct list_head *head      = get_block_border_head(env, block);
 728         be_lv_t *lv                 = env->birg->lv;
 729
 730         const ir_node *irn;
 731         border_t *b;
 732         int idx;
 733
 734         bitset_clear_all(colors);
 735         bitset_clear_all(live);
 736         bitset_clear_all(in_colors);
 737
 738         DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
 739         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 740         list_for_each_entry(border_t, b, head, list) {
 741                 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
 742                                         b->irn, get_irn_idx(b->irn)));
 743         }
 744
 745         /*
 746          * Add initial defs for all values live in.
 747          * Since their colors have already been assigned (The dominators were
 748          * allocated before), we have to mark their colors as used also.
 749          */
 750         be_lv_foreach(lv, block, be_lv_state_in, idx) {
 751                 irn = be_lv_get_irn(lv, block, idx);
 752                 if (has_reg_class(env, irn)) {
 753                         const arch_register_t *reg = arch_get_irn_register(irn);
 754                         int col;
 755
 756                         assert(reg && "Node must have been assigned a register");
 757                         col = arch_register_get_index(reg);
 758
 759                         DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
 760
 761                         /* Mark the color of the live in value as used. */
 762                         bitset_set(colors, col);
 763                         bitset_set(in_colors, col);
 764
 765                         /* Mark the value live in. */
 766                         bitset_set(live, get_irn_idx(irn));
 767                 }
 768         }
 769
 770         /*
 771          * Mind that the sequence of defs from back to front defines a perfect
 772          * elimination order. So, coloring the definitions from first to last
 773          * will work.
 774          */
 775         list_for_each_entry_reverse(border_t, b, head, list) {
 776                 ir_node *irn = b->irn;
 777                 int nr       = get_irn_idx(irn);
 778                 int ignore   = arch_irn_is_ignore(irn);
 779
 780                 /*
 781                  * Assign a color, if it is a local def. Global defs already have a
 782                  * color.
 783                  */
 784                 if (b->is_def && !be_is_live_in(lv, block, irn)) {
 785                         const arch_register_t *reg;
 786                         int col = NO_COLOR;
 787
 788                         if (ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
 789                                 reg = arch_get_irn_register(irn);
 790                                 col = reg->index;
 791                                 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
 792                         } else {
 793                                 col = get_next_free_reg(alloc_env, colors);
 794                                 reg = arch_register_for_index(env->cls, col);
 795                                 assert(arch_get_irn_register(irn) == NULL && "This node must not have been assigned a register yet");
 796                                 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
 797                         }
 798
 799                         bitset_set(colors, col);
 800                         arch_set_irn_register(irn, reg);
 801
 802                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
 803
 804                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 805                         bitset_set(live, nr);
 806                 } else if (!b->is_def) {
 807                         /* Clear the color upon a use. */
 808                         const arch_register_t *reg = arch_get_irn_register(irn);
 809                         int col;
 810
 811                         assert(reg && "Register must have been assigned");
 812
 813                         col = arch_register_get_index(reg);
 814 #ifndef NDEBUG
 815                         if (!arch_register_type_is(reg, ignore)) {
 816                                 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 817                         }
 818 #endif
 819
 820                         bitset_clear(colors, col);
 821                         bitset_clear(live, nr);
 822                 }
 823         }
 824 }
 825
 826 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
 827 {
 828         be_chordal_alloc_env_t env;
 829         char buf[256];
 830         be_lv_t *lv;
 831         be_irg_t *birg = chordal_env->birg;
 832         const arch_register_class_t *cls = chordal_env->cls;
 833
 834         int colors_n          = arch_register_class_n_regs(cls);
 835         ir_graph *irg         = chordal_env->irg;
 836
 837         lv = be_assure_liveness(birg);
 838         be_liveness_assure_sets(lv);
 839         be_liveness_assure_chk(lv);
 840
 841         assure_doms(irg);
 842
 843         env.chordal_env   = chordal_env;
 844         env.colors_n      = colors_n;
 845         env.colors        = bitset_alloca(colors_n);
 846         env.tmp_colors    = bitset_alloca(colors_n);
 847         env.in_colors     = bitset_alloca(colors_n);
 848         env.pre_colored   = pset_new_ptr_default();
 849
 850         BE_TIMER_PUSH(t_constr);
 851
 852         /* Handle register targeting constraints */
 853         dom_tree_walk_irg(irg, constraints, NULL, &env);
 854
 855         if (chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
 856                 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
 857                 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
 858         }
 859
 860         BE_TIMER_POP(t_constr);
 861
 862         env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
 863
 864         /* First, determine the pressure */
 865         dom_tree_walk_irg(irg, pressure, NULL, &env);
 866
 867         /* Assign the colors */
 868         dom_tree_walk_irg(irg, assign, NULL, &env);
 869
 870         if (chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
 871                 plotter_t *plotter;
 872                 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
 873                 plotter = new_plotter_ps(buf);
 874                 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
 875                 plotter_free(plotter);
 876         }
 877
 878         bitset_free(env.live);
 879         del_pset(env.pre_colored);
 880 }
 881
 882 void be_init_chordal(void)
 883 {
 884         FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
 885 }
 886
 887 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);