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

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