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_t.h"
  54 #include "belive_t.h"
  55 #include "benode_t.h"
  56 #include "bearch_t.h"
  57 #include "beirgmod.h"
  58 #include "beifg.h"
  59 #include "beinsn_t.h"
  60 #include "bestatevent.h"
  61 #include "beirg_t.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 = obstack_alloc(env->obst, sizeof(*b));
 131
 132                 /* also allocate the def and tie it to the use. */
 133                 def = obstack_alloc(env->obst, sizeof(*def));
 134                 memset(def, 0, sizeof(*def));
 135                 b->other_end = def;
 136                 def->other_end = b;
 137
 138                 /*
 139                  * Set the link field of the irn to the def.
 140                  * This strongly relies on the fact, that the use is always
 141                  * made before the def.
 142                  */
 143                 set_irn_link(irn, def);
 144
 145                 DEBUG_ONLY(b->magic = BORDER_FOURCC);
 146                 DEBUG_ONLY(def->magic = BORDER_FOURCC);
 147         } else {
 148                 /*
 149                  * If the def is encountered, the use was made and so was the
 150                  * the def node (see the code above). It was placed into the
 151                  * link field of the irn, so we can get it there.
 152                  */
 153                 b = get_irn_link(irn);
 154
 155                 DEBUG_ONLY(assert(b && b->magic == BORDER_FOURCC && "Illegal border encountered"));
 156         }
 157
 158         b->pressure = pressure;
 159         b->is_def = is_def;
 160         b->is_real = is_real;
 161         b->irn = irn;
 162         b->step = step;
 163         list_add_tail(&b->list, head);
 164         DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));
 165
 166
 167         return b;
 168 }
 169
 170 /**
 171  * Check, if an irn is of the register class currently under processing.
 172  * @param env The chordal environment.
 173  * @param irn The node.
 174  * @return 1, if the node is of that register class, 0 if not.
 175  */
 176 static inline int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
 177 {
 178         return arch_irn_consider_in_reg_alloc(env->cls, irn);
 179 }
 180
 181 static int get_next_free_reg(const be_chordal_alloc_env_t *alloc_env, bitset_t *colors)
 182 {
 183         bitset_t *tmp = alloc_env->tmp_colors;
 184         bitset_copy(tmp, colors);
 185         bitset_or(tmp, alloc_env->chordal_env->ignore_colors);
 186         return bitset_next_clear(tmp, 0);
 187 }
 188
 189 static bitset_t *get_decisive_partner_regs(bitset_t *bs, const be_operand_t *o1, const be_operand_t *o2)
 190 {
 191         bitset_t *res = bs;
 192
 193         if (!o1) {
 194                 bitset_copy(bs, o2->regs);
 195                 return bs;
 196         }
 197
 198         if (!o2) {
 199                 bitset_copy(bs, o1->regs);
 200                 return bs;
 201         }
 202
 203         assert(o1->req->cls == o2->req->cls || ! o1->req->cls || ! o2->req->cls);
 204
 205         if (bitset_contains(o1->regs, o2->regs)) {
 206                 bitset_copy(bs, o1->regs);
 207         } else if (bitset_contains(o2->regs, o1->regs)) {
 208                 bitset_copy(bs, o2->regs);
 209         } else {
 210                 res = NULL;
 211         }
 212
 213         return res;
 214 }
 215
 216 static be_insn_t *chordal_scan_insn(be_chordal_env_t *env, ir_node *irn)
 217 {
 218         be_insn_env_t ie;
 219
 220         ie.ignore_colors = env->ignore_colors;
 221         ie.obst          = env->obst;
 222         ie.cls           = env->cls;
 223         return be_scan_insn(&ie, irn);
 224 }
 225
 226 static ir_node *prepare_constr_insn(be_chordal_env_t *env, ir_node *irn)
 227 {
 228         bitset_t *tmp          = bitset_alloca(env->cls->n_regs);
 229         bitset_t *def_constr   = bitset_alloca(env->cls->n_regs);
 230         ir_node *bl            = get_nodes_block(irn);
 231         const be_irg_t *birg   = env->birg;
 232         be_lv_t *lv            = birg->lv;
 233
 234         be_insn_t *insn;
 235         int i, j;
 236
 237         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 238                 ir_node *op = get_irn_n(irn, i);
 239                 ir_node *copy;
 240                 const arch_register_t *reg;
 241                 const arch_register_req_t *req;
 242
 243                 req = arch_get_register_req(irn, i);
 244                 if (req->cls != env->cls)
 245                         continue;
 246
 247                 reg = arch_get_irn_register(op);
 248
 249                 if (reg == NULL || !arch_register_type_is(reg, ignore))
 250                         continue;
 251                 if (arch_register_type_is(reg, joker))
 252                         continue;
 253
 254                 if (!arch_register_req_is(req, limited))
 255                         continue;
 256
 257                 if (rbitset_is_set(req->limited, reg->index))
 258                         continue;
 259
 260                 copy = be_new_Copy(env->cls, env->irg, bl, op);
 261                 be_stat_ev("constr_copy", 1);
 262
 263                 sched_add_before(irn, copy);
 264                 set_irn_n(irn, i, copy);
 265                 DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n", copy, irn, i));
 266         }
 267
 268         insn = chordal_scan_insn(env, irn);
 269
 270         if (!insn->has_constraints)
 271                 goto end;
 272
 273         /* insert copies for nodes that occur constrained more than once. */
 274         for (i = insn->use_start; i < insn->n_ops; ++i) {
 275                 be_operand_t *op = &insn->ops[i];
 276
 277                 if (!op->has_constraints)
 278                         continue;
 279
 280                 for (j = i + 1; j < insn->n_ops; ++j) {
 281                         ir_node *copy;
 282                         be_operand_t *a_op = &insn->ops[j];
 283
 284                         if (a_op->carrier != op->carrier || !a_op->has_constraints)
 285                                 continue;
 286
 287                         /* if the constraint is the same, no copy is necessary
 288                          * TODO generalise unequal but overlapping constraints */
 289                         if (a_op->req == op->req)
 290                                 continue;
 291
 292                         if (be_is_Copy(get_irn_n(insn->irn, a_op->pos)))
 293                                 continue;
 294
 295                         copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
 296                         be_stat_ev("constr_copy", 1);
 297
 298                         sched_add_before(insn->irn, copy);
 299                         set_irn_n(insn->irn, a_op->pos, copy);
 300                         DBG((dbg, LEVEL_3, "inserting multiple constr copy %+F for %+F pos %d\n", copy, insn->irn, a_op->pos));
 301                 }
 302         }
 303
 304         /* collect all registers occurring in out constraints. */
 305         for (i = 0; i < insn->use_start; ++i) {
 306                 be_operand_t *op = &insn->ops[i];
 307                 if (op->has_constraints)
 308                         bitset_or(def_constr, op->regs);
 309         }
 310
 311         /*
 312          * insert copies for all constrained arguments living through the node
 313          * and being constrained to a register which also occurs in out constraints.
 314          */
 315         for (i = insn->use_start; i < insn->n_ops; ++i) {
 316                 ir_node *copy;
 317                 be_operand_t *op = &insn->ops[i];
 318
 319                 bitset_copy(tmp, op->regs);
 320                 bitset_and(tmp, def_constr);
 321
 322                 /*
 323                  * Check, if
 324                  * 1) the operand is constrained.
 325                  * 2) lives through the node.
 326                  * 3) is constrained to a register occurring in out constraints.
 327                  */
 328                 if (!op->has_constraints ||
 329                    !values_interfere(birg, insn->irn, op->carrier) ||
 330                    bitset_is_empty(tmp))
 331                         continue;
 332
 333                 /*
 334                  * only create the copy if the operand is no copy.
 335                  * this is necessary since the assure constraints phase inserts
 336                  * Copies and Keeps for operands which must be different from the
 337                  * results. Additional copies here would destroy this.
 338                  */
 339                 if (be_is_Copy(get_irn_n(insn->irn, op->pos)))
 340                         continue;
 341
 342                 copy = be_new_Copy(env->cls, env->irg, bl, op->carrier);
 343
 344                 sched_add_before(insn->irn, copy);
 345                 set_irn_n(insn->irn, op->pos, copy);
 346                 DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n", copy, insn->irn, op->pos));
 347                 be_liveness_update(lv, op->carrier);
 348         }
 349
 350 end:
 351         obstack_free(env->obst, insn);
 352         return insn->next_insn;
 353 }
 354
 355 static void pre_spill_prepare_constr_walker(ir_node *bl, void *data)
 356 {
 357         be_chordal_env_t *env = data;
 358         ir_node *irn;
 359         for (irn = sched_first(bl); !sched_is_end(irn);) {
 360                 irn = prepare_constr_insn(env, irn);
 361         }
 362 }
 363
 364 void be_pre_spill_prepare_constr(be_chordal_env_t *cenv)
 365 {
 366         irg_block_walk_graph(cenv->irg, pre_spill_prepare_constr_walker, NULL, cenv);
 367 }
 368
 369 static void pair_up_operands(const be_chordal_alloc_env_t *alloc_env, be_insn_t *insn)
 370 {
 371         const be_chordal_env_t *env = alloc_env->chordal_env;
 372         bitset_t               *bs  = bitset_alloca(env->cls->n_regs);
 373         int                     i;
 374         int                     j;
 375
 376         /*
 377          * For each out operand, try to find an in operand which can be assigned the
 378          * same register as the out operand.
 379         */
 380         for (j = 0; j < insn->use_start; ++j) {
 381                 int smallest         = -1;
 382                 int smallest_n_regs  = 2 * env->cls->n_regs + 1;
 383                 be_operand_t *out_op = &insn->ops[j];
 384
 385                 /* Try to find an in operand which has ... */
 386                 for (i = insn->use_start; i < insn->n_ops; ++i) {
 387                         int n_total;
 388                         const be_operand_t *op = &insn->ops[i];
 389
 390                         if (op->partner != NULL)
 391                                 continue;
 392                         if (values_interfere(env->birg, op->irn, op->carrier))
 393                                 continue;
 394
 395                         bitset_clear_all(bs);
 396                         bitset_copy(bs, op->regs);
 397                         bitset_and(bs, out_op->regs);
 398                         n_total = bitset_popcnt(op->regs) + bitset_popcnt(out_op->regs);
 399
 400                         if (!bitset_is_empty(bs) && n_total < smallest_n_regs) {
 401                                 smallest = i;
 402                                 smallest_n_regs = n_total;
 403                         }
 404                 }
 405
 406                 if (smallest >= 0) {
 407                         be_operand_t *partner = &insn->ops[smallest];
 408                         for (i = insn->use_start; i < insn->n_ops; ++i) {
 409                                 if (insn->ops[i].carrier == partner->carrier)
 410                                         insn->ops[i].partner = out_op;
 411                         }
 412
 413                         out_op->partner  = partner;
 414                         partner->partner = out_op;
 415                 }
 416         }
 417 }
 418
 419
 420 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
 421                                         be_insn_t **the_insn)
 422 {
 423         be_chordal_env_t *env       = alloc_env->chordal_env;
 424         be_insn_t *insn             = *the_insn;
 425         ir_node *perm               = NULL;
 426         bitset_t *out_constr        = bitset_alloca(env->cls->n_regs);
 427         const ir_edge_t *edge;
 428         int i;
 429
 430         assert(insn->has_constraints && "only do this for constrained nodes");
 431
 432         /*
 433          * Collect all registers that occur in output constraints.
 434          * This is necessary, since if the insn has one of these as an input constraint
 435          * and the corresponding operand interferes with the insn, the operand must
 436          * be copied.
 437          */
 438         for (i = 0; i < insn->use_start; ++i) {
 439                 be_operand_t *op = &insn->ops[i];
 440                 if (op->has_constraints)
 441                         bitset_or(out_constr, op->regs);
 442         }
 443
 444         /*
 445          * Make the Perm, recompute liveness and re-scan the insn since the
 446          * in operands are now the Projs of the Perm.
 447          */
 448         perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
 449
 450         /* Registers are propagated by insert_Perm_after(). Clean them here! */
 451         if (perm == NULL)
 452                 return NULL;
 453
 454         be_stat_ev("constr_perm", get_irn_arity(perm));
 455         foreach_out_edge(perm, edge) {
 456                 ir_node *proj = get_edge_src_irn(edge);
 457                 arch_set_irn_register(proj, NULL);
 458         }
 459
 460         /*
 461          * We also have to re-build the insn since the input operands are now the Projs of
 462          * the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
 463          * the live sets may change.
 464          */
 465         obstack_free(env->obst, insn);
 466         *the_insn = insn = chordal_scan_insn(env, insn->irn);
 467
 468         /*
 469          * Copy the input constraints of the insn to the Perm as output
 470          * constraints. Succeeding phases (coalescing) will need that.
 471          */
 472         for (i = insn->use_start; i < insn->n_ops; ++i) {
 473                 be_operand_t *op = &insn->ops[i];
 474                 ir_node *proj = op->carrier;
 475                 /*
 476                  * Note that the predecessor must not be a Proj of the Perm,
 477                  * since ignore-nodes are not Perm'ed.
 478                  */
 479                 if (op->has_constraints &&  is_Proj(proj) && get_Proj_pred(proj) == perm) {
 480                         be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
 481                 }
 482         }
 483
 484         return perm;
 485 }
 486
 487 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 488                                    ir_node *irn, int *silent)
 489 {
 490         int n_regs;
 491         bitset_t *bs;
 492         ir_node **alloc_nodes;
 493         //hungarian_problem_t *bp;
 494         int *assignment;
 495         pmap *partners;
 496         int i, n_alloc;
 497         bitset_pos_t col;
 498         const ir_edge_t *edge;
 499         ir_node *perm = NULL;
 500         //int match_res, cost;
 501         be_chordal_env_t *env  = alloc_env->chordal_env;
 502         void *base             = obstack_base(env->obst);
 503         be_insn_t *insn        = chordal_scan_insn(env, irn);
 504         ir_node *res           = insn->next_insn;
 505         int be_silent          = *silent;
 506         be_irg_t *birg         = env->birg;
 507         bipartite_t *bp;
 508
 509         if (insn->pre_colored) {
 510                 int i;
 511                 for (i = 0; i < insn->use_start; ++i)
 512                         pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
 513         }
 514
 515         /*
 516          * If the current node is a barrier toggle the silent flag.
 517          * If we are in the start block, we are ought to be silent at the beginning,
 518          * so the toggling activates the constraint handling but skips the barrier.
 519          * If we are in the end block we handle the in requirements of the barrier
 520          * and set the rest to silent.
 521          */
 522         if (be_is_Barrier(irn))
 523                 *silent = !*silent;
 524
 525         if (be_silent)
 526                 goto end;
 527
 528         /*
 529          * Perms inserted before the constraint handling phase are considered to be
 530          * correctly precolored. These Perms arise during the ABI handling phase.
 531          */
 532         if (!insn->has_constraints)
 533                 goto end;
 534
 535         n_regs      = env->cls->n_regs;
 536         bs          = bitset_alloca(n_regs);
 537         alloc_nodes = ALLOCAN(ir_node*, n_regs);
 538         //bp          = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
 539         bp          = bipartite_new(n_regs, n_regs);
 540         assignment  = ALLOCAN(int, n_regs);
 541         partners    = pmap_create();
 542
 543         /*
 544          * prepare the constraint handling of this node.
 545          * Perms are constructed and Copies are created for constrained values
 546          * interfering with the instruction.
 547          */
 548         perm = pre_process_constraints(alloc_env, &insn);
 549
 550         /* find suitable in operands to the out operands of the node. */
 551         pair_up_operands(alloc_env, insn);
 552
 553         /*
 554          * look at the in/out operands and add each operand (and its possible partner)
 555          * to a bipartite graph (left: nodes with partners, right: admissible colors).
 556          */
 557         for (i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
 558                 be_operand_t *op = &insn->ops[i];
 559
 560                 /*
 561                  * If the operand has no partner or the partner has not been marked
 562                  * for allocation, determine the admissible registers and mark it
 563                  * for allocation by associating the node and its partner with the
 564                  * set of admissible registers via a bipartite graph.
 565                  */
 566                 if (!op->partner || !pmap_contains(partners, op->partner->carrier)) {
 567                         ir_node *partner = op->partner ? op->partner->carrier : NULL;
 568                         int i;
 569
 570                         pmap_insert(partners, op->carrier, partner);
 571                         if (partner != NULL)
 572                                 pmap_insert(partners, partner, op->carrier);
 573
 574                         /* don't insert a node twice */
 575                         for (i = 0; i < n_alloc; ++i) {
 576                                 if (alloc_nodes[i] == op->carrier) {
 577                                         break;
 578                                 }
 579                         }
 580                         if (i < n_alloc)
 581                                 continue;
 582
 583                         alloc_nodes[n_alloc] = op->carrier;
 584
 585                         DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
 586                              partner));
 587
 588                         bitset_clear_all(bs);
 589                         get_decisive_partner_regs(bs, op, op->partner);
 590
 591                         DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
 592                              bs));
 593
 594                         bitset_foreach(bs, col) {
 595                                 //hungarian_add(bp, n_alloc, col, 1);
 596                                 bipartite_add(bp, n_alloc, col);
 597                         }
 598
 599                         n_alloc++;
 600                 }
 601         }
 602
 603         /*
 604          * Put all nodes which live through the constrained instruction also to the
 605          * allocation bipartite graph. They are considered unconstrained.
 606          */
 607         if (perm != NULL) {
 608                 foreach_out_edge(perm, edge) {
 609                         int i;
 610                         ir_node *proj = get_edge_src_irn(edge);
 611
 612                         assert(is_Proj(proj));
 613
 614                         if (!values_interfere(birg, proj, irn) || pmap_contains(partners, proj))
 615                                 continue;
 616
 617                         /* don't insert a node twice */
 618                         for (i = 0; i < n_alloc; ++i) {
 619                                 if (alloc_nodes[i] == proj) {
 620                                         break;
 621                                 }
 622                         }
 623                         if (i < n_alloc)
 624                                 continue;
 625
 626
 627                         assert(n_alloc < n_regs);
 628
 629                         alloc_nodes[n_alloc] = proj;
 630                         pmap_insert(partners, proj, NULL);
 631
 632                         bitset_clear_all(bs);
 633                         arch_put_non_ignore_regs(env->cls, bs);
 634                         bitset_andnot(bs, env->ignore_colors);
 635                         bitset_foreach(bs, col) {
 636                                 //hungarian_add(bp, n_alloc, col, 1);
 637                                 bipartite_add(bp, n_alloc, col);
 638                         }
 639
 640                         n_alloc++;
 641                 }
 642         }
 643
 644         /* Compute a valid register allocation. */
 645 #if 0
 646         hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
 647         match_res = hungarian_solve(bp, assignment, &cost, 1);
 648         assert(match_res == 0 && "matching failed");
 649 #else
 650         bipartite_matching(bp, assignment);
 651 #endif
 652
 653         /* Assign colors obtained from the matching. */
 654         for (i = 0; i < n_alloc; ++i) {
 655                 const arch_register_t *reg;
 656                 ir_node *irn;
 657
 658                 assert(assignment[i] >= 0 && "there must have been a register assigned");
 659                 reg = arch_register_for_index(env->cls, assignment[i]);
 660                 assert(! (reg->type & arch_register_type_ignore));
 661
 662                 irn = alloc_nodes[i];
 663                 if (irn != NULL) {
 664                         arch_set_irn_register(irn, reg);
 665                         (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
 666                         DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
 667                 }
 668
 669                 irn = pmap_get(partners, alloc_nodes[i]);
 670                 if (irn != NULL) {
 671                         arch_set_irn_register(irn, reg);
 672                         (void) pset_hinsert_ptr(alloc_env->pre_colored, irn);
 673                         DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
 674                 }
 675         }
 676
 677         /* Allocate the non-constrained Projs of the Perm. */
 678         if (perm != NULL) {
 679                 bitset_clear_all(bs);
 680
 681                 /* Put the colors of all Projs in a bitset. */
 682                 foreach_out_edge(perm, edge) {
 683                         ir_node *proj              = get_edge_src_irn(edge);
 684                         const arch_register_t *reg = arch_get_irn_register(proj);
 685
 686                         if (reg != NULL)
 687                                 bitset_set(bs, reg->index);
 688                 }
 689
 690                 /* Assign the not yet assigned Projs of the Perm a suitable color. */
 691                 foreach_out_edge(perm, edge) {
 692                         ir_node *proj              = get_edge_src_irn(edge);
 693                         const arch_register_t *reg = arch_get_irn_register(proj);
 694
 695                         DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
 696
 697                         if (reg == NULL) {
 698                                 col = get_next_free_reg(alloc_env, bs);
 699                                 reg = arch_register_for_index(env->cls, col);
 700                                 bitset_set(bs, reg->index);
 701                                 arch_set_irn_register(proj, reg);
 702                                 pset_insert_ptr(alloc_env->pre_colored, proj);
 703                                 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
 704                         }
 705                 }
 706         }
 707
 708         bipartite_free(bp);
 709         //hungarian_free(bp);
 710         pmap_destroy(partners);
 711
 712 end:
 713         obstack_free(env->obst, base);
 714         return res;
 715 }
 716
 717 /**
 718  * Handle constraint nodes in each basic block.
 719  * handle_constraints() inserts Perm nodes which perm
 720  * over all values live at the constrained node right in front
 721  * of the constrained node. These Perms signal a constrained node.
 722  * For further comments, refer to handle_constraints().
 723  */
 724 static void constraints(ir_node *bl, void *data)
 725 {
 726         /*
 727          * Start silent in the start block.
 728          * The silence remains until the first barrier is seen.
 729          * Each other block is begun loud.
 730          */
 731         int                     silent = bl == get_irg_start_block(get_irn_irg(bl));
 732         be_chordal_alloc_env_t *env    = data;
 733         ir_node                *irn;
 734
 735         /*
 736          * If the block is the start block search the barrier and
 737          * start handling constraints from there.
 738          */
 739         for (irn = sched_first(bl); !sched_is_end(irn);) {
 740                 irn = handle_constraints(env, irn, &silent);
 741         }
 742 }
 743
 744 /**
 745  * Annotate the register pressure to the nodes and compute
 746  * the liveness intervals.
 747  * @param block The block to do it for.
 748  * @param env_ptr The environment.
 749  */
 750 static void pressure(ir_node *block, void *env_ptr)
 751 {
 752 /* Convenience macro for a def */
 753 #define border_def(irn, step, real) \
 754         border_add(env, head, irn, step, pressure--, 1, real)
 755
 756 /* Convenience macro for a use */
 757 #define border_use(irn, step, real) \
 758         border_add(env, head, irn, step, ++pressure, 0, real)
 759
 760         be_chordal_alloc_env_t *alloc_env = env_ptr;
 761         be_chordal_env_t *env             = alloc_env->chordal_env;
 762         bitset_t *live                    = alloc_env->live;
 763         ir_node *irn;
 764         be_lv_t *lv                       = env->birg->lv;
 765
 766         int i, n;
 767         bitset_pos_t elm;
 768         unsigned step = 0;
 769         unsigned pressure = 0;
 770         struct list_head *head;
 771
 772         DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
 773         bitset_clear_all(live);
 774
 775         /* Set up the border list in the block info */
 776         head = obstack_alloc(env->obst, sizeof(*head));
 777         INIT_LIST_HEAD(head);
 778         assert(pmap_get(env->border_heads, block) == NULL);
 779         pmap_insert(env->border_heads, block, head);
 780
 781         /*
 782          * Make final uses of all values live out of the block.
 783          * They are necessary to build up real intervals.
 784          */
 785         be_lv_foreach(lv, block, be_lv_state_end, i) {
 786                 ir_node *irn = be_lv_get_irn(lv, block, i);
 787                 if (has_reg_class(env, irn)) {
 788                         DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
 789                         bitset_set(live, get_irn_idx(irn));
 790                         border_use(irn, step, 0);
 791                 }
 792         }
 793         ++step;
 794
 795         /*
 796          * Determine the last uses of a value inside the block, since they are
 797          * relevant for the interval borders.
 798          */
 799         sched_foreach_reverse(block, irn) {
 800                 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
 801                 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
 802
 803                 if (get_irn_mode(irn) == mode_T) {
 804                         const ir_edge_t *edge;
 805
 806                         foreach_out_edge(irn, edge) {
 807                                 ir_node *proj = get_edge_src_irn(edge);
 808
 809                                 /*
 810                                  * If the node defines some value, which can put into a
 811                                  * register of the current class, make a border for it.
 812                                  */
 813                                 if (has_reg_class(env, proj)) {
 814                                         int nr = get_irn_idx(proj);
 815
 816                                         bitset_clear(live, nr);
 817                                         border_def(proj, step, 1);
 818                                 }
 819                         }
 820                 }
 821
 822                 /*
 823                  * If the node defines some value, which can put into a
 824                  * register of the current class, make a border for it.
 825                  */
 826                 if (has_reg_class(env, irn)) {
 827                         int nr = get_irn_idx(irn);
 828
 829                         bitset_clear(live, nr);
 830                         border_def(irn, step, 1);
 831                 }
 832
 833                 /*
 834                  * If the node is no phi node we can examine the uses.
 835                  */
 836                 if (!is_Phi(irn)) {
 837                         for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 838                                 ir_node *op = get_irn_n(irn, i);
 839
 840                                 if (has_reg_class(env, op)) {
 841                                         int nr = get_irn_idx(op);
 842                                         const char *msg = "-";
 843
 844                                         if (!bitset_is_set(live, nr)) {
 845                                                 border_use(op, step, 1);
 846                                                 bitset_set(live, nr);
 847                                                 msg = "X";
 848                                         }
 849
 850                                         DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
 851                                 }
 852                         }
 853                 }
 854                 ++step;
 855         }
 856
 857         bitset_foreach(live, elm) {
 858                 ir_node *irn = get_idx_irn(env->irg, elm);
 859                 if (be_is_live_in(lv, block, irn))
 860                         border_def(irn, step, 0);
 861         }
 862 }
 863
 864 static void assign(ir_node *block, void *env_ptr)
 865 {
 866         be_chordal_alloc_env_t *alloc_env = env_ptr;
 867         be_chordal_env_t *env       = alloc_env->chordal_env;
 868         bitset_t *live              = alloc_env->live;
 869         bitset_t *colors            = alloc_env->colors;
 870         bitset_t *in_colors         = alloc_env->in_colors;
 871         struct list_head *head      = get_block_border_head(env, block);
 872         be_lv_t *lv                 = env->birg->lv;
 873
 874         const ir_node *irn;
 875         border_t *b;
 876         int idx;
 877
 878         bitset_clear_all(colors);
 879         bitset_clear_all(live);
 880         bitset_clear_all(in_colors);
 881
 882         DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
 883         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 884         list_for_each_entry(border_t, b, head, list) {
 885                 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
 886                                         b->irn, get_irn_idx(b->irn)));
 887         }
 888
 889         /*
 890          * Add initial defs for all values live in.
 891          * Since their colors have already been assigned (The dominators were
 892          * allocated before), we have to mark their colors as used also.
 893          */
 894         be_lv_foreach(lv, block, be_lv_state_in, idx) {
 895                 irn = be_lv_get_irn(lv, block, idx);
 896                 if (has_reg_class(env, irn)) {
 897                         const arch_register_t *reg = arch_get_irn_register(irn);
 898                         int col;
 899
 900                         assert(reg && "Node must have been assigned a register");
 901                         col = arch_register_get_index(reg);
 902
 903                         DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
 904
 905                         /* Mark the color of the live in value as used. */
 906                         bitset_set(colors, col);
 907                         bitset_set(in_colors, col);
 908
 909                         /* Mark the value live in. */
 910                         bitset_set(live, get_irn_idx(irn));
 911                 }
 912         }
 913
 914         /*
 915          * Mind that the sequence of defs from back to front defines a perfect
 916          * elimination order. So, coloring the definitions from first to last
 917          * will work.
 918          */
 919         list_for_each_entry_reverse(border_t, b, head, list) {
 920                 ir_node *irn = b->irn;
 921                 int nr       = get_irn_idx(irn);
 922                 int ignore   = arch_irn_is_ignore(irn);
 923
 924                 /*
 925                  * Assign a color, if it is a local def. Global defs already have a
 926                  * color.
 927                  */
 928                 if (b->is_def && !be_is_live_in(lv, block, irn)) {
 929                         const arch_register_t *reg;
 930                         int col = NO_COLOR;
 931
 932                         if (ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
 933                                 reg = arch_get_irn_register(irn);
 934                                 col = reg->index;
 935                                 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
 936                         } else {
 937                                 col = get_next_free_reg(alloc_env, colors);
 938                                 reg = arch_register_for_index(env->cls, col);
 939                                 assert(arch_get_irn_register(irn) == NULL && "This node must not have been assigned a register yet");
 940                                 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
 941                         }
 942
 943                         bitset_set(colors, col);
 944                         arch_set_irn_register(irn, reg);
 945
 946                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
 947
 948                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 949                         bitset_set(live, nr);
 950                 } else if (!b->is_def) {
 951                         /* Clear the color upon a use. */
 952                         const arch_register_t *reg = arch_get_irn_register(irn);
 953                         int col;
 954
 955                         assert(reg && "Register must have been assigned");
 956
 957                         col = arch_register_get_index(reg);
 958 #ifndef NDEBUG
 959                         if (!arch_register_type_is(reg, ignore)) {
 960                                 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 961                         }
 962 #endif
 963
 964                         bitset_clear(colors, col);
 965                         bitset_clear(live, nr);
 966                 }
 967         }
 968 }
 969
 970 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
 971 {
 972         be_chordal_alloc_env_t env;
 973         char buf[256];
 974         be_lv_t *lv;
 975         be_irg_t *birg = chordal_env->birg;
 976         const arch_register_class_t *cls = chordal_env->cls;
 977
 978         int colors_n          = arch_register_class_n_regs(cls);
 979         ir_graph *irg         = chordal_env->irg;
 980
 981         lv = be_assure_liveness(birg);
 982         be_liveness_assure_sets(lv);
 983         be_liveness_assure_chk(lv);
 984
 985         assure_doms(irg);
 986
 987         env.chordal_env   = chordal_env;
 988         env.colors_n      = colors_n;
 989         env.colors        = bitset_alloca(colors_n);
 990         env.tmp_colors    = bitset_alloca(colors_n);
 991         env.in_colors     = bitset_alloca(colors_n);
 992         env.pre_colored   = pset_new_ptr_default();
 993
 994         BE_TIMER_PUSH(t_constr);
 995
 996         /* Handle register targeting constraints */
 997         dom_tree_walk_irg(irg, constraints, NULL, &env);
 998
 999         if (chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1000                 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1001                 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1002         }
1003
1004         BE_TIMER_POP(t_constr);
1005
1006         env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1007
1008         /* First, determine the pressure */
1009         dom_tree_walk_irg(irg, pressure, NULL, &env);
1010
1011         /* Assign the colors */
1012         dom_tree_walk_irg(irg, assign, NULL, &env);
1013
1014         if (chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1015                 plotter_t *plotter;
1016                 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1017                 plotter = new_plotter_ps(buf);
1018                 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1019                 plotter_free(plotter);
1020         }
1021
1022         bitset_free(env.live);
1023         del_pset(env.pre_colored);
1024 }
1025
1026 void be_init_chordal(void)
1027 {
1028         FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1029 }
1030
1031 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);