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
 419                         for(i = insn->use_start; i < insn->n_ops; ++i) {
 420                                 if(insn->ops[i].carrier == partner->carrier)
 421                                         insn->ops[i].partner = out_op;
 422                         }
 423
 424                         out_op->partner  = partner;
 425                         partner->partner = out_op;
 426                 }
 427         }
 428 }
 429
 430
 431 static ir_node *pre_process_constraints(be_chordal_alloc_env_t *alloc_env,
 432                                         be_insn_t **the_insn)
 433 {
 434         be_chordal_env_t *env       = alloc_env->chordal_env;
 435         const arch_env_t *aenv      = env->birg->main_env->arch_env;
 436         be_insn_t *insn             = *the_insn;
 437         ir_node *perm               = NULL;
 438         bitset_t *out_constr        = bitset_alloca(env->cls->n_regs);
 439         const ir_edge_t *edge;
 440         int i;
 441
 442         assert(insn->has_constraints && "only do this for constrained nodes");
 443
 444         /*
 445                 Collect all registers that occur in output constraints.
 446                 This is necessary, since if the insn has one of these as an input constraint
 447                 and the corresponding operand interferes with the insn, the operand must
 448                 be copied.
 449         */
 450         for(i = 0; i < insn->use_start; ++i) {
 451                 be_operand_t *op = &insn->ops[i];
 452                 if(op->has_constraints)
 453                         bitset_or(out_constr, op->regs);
 454         }
 455
 456         /*
 457                 Make the Perm, recompute liveness and re-scan the insn since the
 458                 in operands are now the Projs of the Perm.
 459         */
 460         perm = insert_Perm_after(env->birg, env->cls, sched_prev(insn->irn));
 461
 462         /* Registers are propagated by insert_Perm_after(). Clean them here! */
 463         if(perm == NULL)
 464                 return NULL;
 465
 466         be_stat_ev("constr_perm", get_irn_arity(perm));
 467         foreach_out_edge(perm, edge) {
 468                 ir_node *proj = get_edge_src_irn(edge);
 469                 arch_set_irn_register(aenv, proj, NULL);
 470         }
 471
 472         /*
 473                 We also have to re-build the insn since the input operands are now the Projs of
 474                 the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
 475                 the live sets may change.
 476         */
 477         // be_liveness_recompute(lv);
 478         obstack_free(env->obst, insn);
 479         *the_insn = insn = chordal_scan_insn(env, insn->irn);
 480
 481         /*
 482                 Copy the input constraints of the insn to the Perm as output
 483                 constraints. Succeeding phases (coalescing) will need that.
 484         */
 485         for(i = insn->use_start; i < insn->n_ops; ++i) {
 486                 be_operand_t *op = &insn->ops[i];
 487                 ir_node *proj = op->carrier;
 488                 /*
 489                         Note that the predecessor must not be a Proj of the Perm,
 490                         since ignore-nodes are not Perm'ed.
 491                 */
 492                 if(op->has_constraints &&  is_Proj(proj) && get_Proj_pred(proj) == perm) {
 493                         be_set_constr_limited(perm, BE_OUT_POS(get_Proj_proj(proj)), op->req);
 494                 }
 495         }
 496
 497         return perm;
 498 }
 499
 500 static ir_node *handle_constraints(be_chordal_alloc_env_t *alloc_env,
 501                                    ir_node *irn, int *silent)
 502 {
 503         const arch_env_t *aenv;
 504         int n_regs;
 505         bitset_t *bs;
 506         ir_node **alloc_nodes;
 507         hungarian_problem_t *bp;
 508         int *assignment;
 509         pmap *partners;
 510         int i, n_alloc;
 511         bitset_pos_t col;
 512         const ir_edge_t *edge;
 513         ir_node *perm = NULL;
 514         int match_res, cost;
 515         be_chordal_env_t *env  = alloc_env->chordal_env;
 516         void *base             = obstack_base(env->obst);
 517         be_insn_t *insn        = chordal_scan_insn(env, irn);
 518         ir_node *res           = insn->next_insn;
 519         int be_silent          = *silent;
 520         be_irg_t *birg         = env->birg;
 521
 522         if(insn->pre_colored) {
 523                 int i;
 524                 for(i = 0; i < insn->use_start; ++i)
 525                         pset_insert_ptr(alloc_env->pre_colored, insn->ops[i].carrier);
 526         }
 527
 528         /*
 529                 If the current node is a barrier toggle the silent flag.
 530                 If we are in the start block, we are ought to be silent at the beginning,
 531                 so the toggling activates the constraint handling but skips the barrier.
 532                 If we are in the end block we handle the in requirements of the barrier
 533                 and set the rest to silent.
 534         */
 535         if(be_is_Barrier(irn))
 536                 *silent = !*silent;
 537
 538         if(be_silent)
 539                 goto end;
 540
 541         /*
 542                 Perms inserted before the constraint handling phase are considered to be
 543                 correctly precolored. These Perms arise during the ABI handling phase.
 544         */
 545         if(!insn->has_constraints)
 546                 goto end;
 547
 548         aenv        = env->birg->main_env->arch_env;
 549         n_regs      = env->cls->n_regs;
 550         bs          = bitset_alloca(n_regs);
 551         alloc_nodes = alloca(n_regs * sizeof(alloc_nodes[0]));
 552         bp          = hungarian_new(n_regs, n_regs, 2, HUNGARIAN_MATCH_PERFECT);
 553         // bipartite_t *bp        = bipartite_new(n_regs, n_regs);
 554         assignment  = alloca(n_regs * sizeof(assignment[0]));
 555         partners    = pmap_create();
 556
 557         /*
 558                 prepare the constraint handling of this node.
 559                 Perms are constructed and Copies are created for constrained values
 560                 interfering with the instruction.
 561         */
 562         perm = pre_process_constraints(alloc_env, &insn);
 563
 564         /* find suitable in operands to the out operands of the node. */
 565         pair_up_operands(alloc_env, insn);
 566
 567         /*
 568                 look at the in/out operands and add each operand (and its possible partner)
 569                 to a bipartite graph (left: nodes with partners, right: admissible colors).
 570         */
 571         for(i = 0, n_alloc = 0; i < insn->n_ops; ++i) {
 572                 be_operand_t *op = &insn->ops[i];
 573
 574                 /*
 575                         If the operand has no partner or the partner has not been marked
 576                         for allocation, determine the admissible registers and mark it
 577                         for allocation by associating the node and its partner with the
 578                         set of admissible registers via a bipartite graph.
 579                 */
 580                 if(!op->partner || !pmap_contains(partners, op->partner->carrier)) {
 581                         ir_node *partner = op->partner ? op->partner->carrier : NULL;
 582                         int i;
 583
 584                         pmap_insert(partners, op->carrier, partner);
 585                         if(partner != NULL)
 586                                 pmap_insert(partners, partner, op->carrier);
 587
 588                         /* don't insert a node twice */
 589                         for(i = 0; i < n_alloc; ++i) {
 590                                 if(alloc_nodes[i] == op->carrier) {
 591                                         break;
 592                                 }
 593                         }
 594                         if(i < n_alloc)
 595                                 continue;
 596
 597                         alloc_nodes[n_alloc] = op->carrier;
 598
 599                         DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
 600                              partner));
 601
 602                         bitset_clear_all(bs);
 603                         get_decisive_partner_regs(bs, op, op->partner);
 604
 605                         DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
 606                              bs));
 607
 608                         bitset_foreach(bs, col) {
 609                                 hungarian_add(bp, n_alloc, col, 1);
 610                                 // bipartite_add(bp, n_alloc, col);
 611                         }
 612
 613                         n_alloc++;
 614                 }
 615         }
 616
 617         /*
 618                 Put all nodes which live through the constrained instruction also to the
 619                 allocation bipartite graph. They are considered unconstrained.
 620         */
 621         if(perm != NULL) {
 622                 foreach_out_edge(perm, edge) {
 623                         int i;
 624                         ir_node *proj = get_edge_src_irn(edge);
 625
 626                         assert(is_Proj(proj));
 627
 628                         if(!values_interfere(birg, proj, irn) || pmap_contains(partners, proj))
 629                                 continue;
 630
 631                         /* don't insert a node twice */
 632                         for(i = 0; i < n_alloc; ++i) {
 633                                 if(alloc_nodes[i] == proj) {
 634                                         break;
 635                                 }
 636                         }
 637                         if(i < n_alloc)
 638                                 continue;
 639
 640
 641                         assert(n_alloc < n_regs);
 642
 643                         alloc_nodes[n_alloc] = proj;
 644                         pmap_insert(partners, proj, NULL);
 645
 646                         bitset_clear_all(bs);
 647                         arch_put_non_ignore_regs(aenv, env->cls, bs);
 648                         bitset_andnot(bs, env->ignore_colors);
 649                         bitset_foreach(bs, col) {
 650                                 hungarian_add(bp, n_alloc, col, 1);
 651                                 // bipartite_add(bp, n_alloc, col);
 652                         }
 653
 654                         n_alloc++;
 655                 }
 656         }
 657
 658         /* Compute a valid register allocation. */
 659         hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
 660         match_res = hungarian_solve(bp, assignment, &cost, 1);
 661         assert(match_res == 0 && "matching failed");
 662         //bipartite_matching(bp, assignment);
 663
 664         /* Assign colors obtained from the matching. */
 665         for(i = 0; i < n_alloc; ++i) {
 666                 const arch_register_t *reg;
 667                 ir_node *nodes[2];
 668                 int j;
 669
 670                 assert(assignment[i] >= 0 && "there must have been a register assigned");
 671                 reg = arch_register_for_index(env->cls, assignment[i]);
 672
 673                 nodes[0] = alloc_nodes[i];
 674                 nodes[1] = pmap_get(partners, alloc_nodes[i]);
 675
 676                 for(j = 0; j < 2; ++j) {
 677                         if(!nodes[j])
 678                                 continue;
 679
 680                         assert(! (reg->type & arch_register_type_ignore));
 681                         arch_set_irn_register(aenv, nodes[j], reg);
 682                         (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
 683                         DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
 684                 }
 685         }
 686
 687         /* Allocate the non-constrained Projs of the Perm. */
 688         if(perm != NULL) {
 689                 bitset_clear_all(bs);
 690
 691                 /* Put the colors of all Projs in a bitset. */
 692                 foreach_out_edge(perm, edge) {
 693                         ir_node *proj              = get_edge_src_irn(edge);
 694                         const arch_register_t *reg = arch_get_irn_register(aenv, proj);
 695
 696                         if(reg != NULL)
 697                                 bitset_set(bs, reg->index);
 698                 }
 699
 700                 /* Assign the not yet assigned Projs of the Perm a suitable color. */
 701                 foreach_out_edge(perm, edge) {
 702                         ir_node *proj              = get_edge_src_irn(edge);
 703                         const arch_register_t *reg = arch_get_irn_register(aenv, proj);
 704
 705                         DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
 706
 707                         if(reg == NULL) {
 708                                 col = get_next_free_reg(alloc_env, bs);
 709                                 reg = arch_register_for_index(env->cls, col);
 710                                 bitset_set(bs, reg->index);
 711                                 arch_set_irn_register(aenv, proj, reg);
 712                                 pset_insert_ptr(alloc_env->pre_colored, proj);
 713                                 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
 714                         }
 715                 }
 716         }
 717
 718         //bipartite_free(bp);
 719         hungarian_free(bp);
 720         pmap_destroy(partners);
 721
 722 end:
 723         obstack_free(env->obst, base);
 724         return res;
 725 }
 726
 727 /**
 728  * Handle constraint nodes in each basic block.
 729  * handle_constraints() inserts Perm nodes which perm
 730  * over all values live at the constrained node right in front
 731  * of the constrained node. These Perms signal a constrained node.
 732  * For further comments, refer to handle_constraints().
 733  */
 734 static void constraints(ir_node *bl, void *data)
 735 {
 736         be_chordal_alloc_env_t *env = data;
 737
 738         /*
 739                 Start silent in the start block.
 740                 The silence remains until the first barrier is seen.
 741                 Each other block is begun loud.
 742         */
 743         int silent                  = bl == get_irg_start_block(get_irn_irg(bl));
 744         ir_node *irn;
 745
 746         /*
 747                 If the block is the start block search the barrier and
 748                 start handling constraints from there.
 749         */
 750
 751         for(irn = sched_first(bl); !sched_is_end(irn);) {
 752                 irn = handle_constraints(env, irn, &silent);
 753         }
 754 }
 755
 756 /**
 757  * Annotate the register pressure to the nodes and compute
 758  * the liveness intervals.
 759  * @param block The block to do it for.
 760  * @param env_ptr The environment.
 761  */
 762 static void pressure(ir_node *block, void *env_ptr)
 763 {
 764 /* Convenience macro for a def */
 765 #define border_def(irn, step, real) \
 766         border_add(env, head, irn, step, pressure--, 1, real)
 767
 768 /* Convenience macro for a use */
 769 #define border_use(irn, step, real) \
 770         border_add(env, head, irn, step, ++pressure, 0, real)
 771
 772         be_chordal_alloc_env_t *alloc_env = env_ptr;
 773         be_chordal_env_t *env             = alloc_env->chordal_env;
 774         bitset_t *live                    = alloc_env->live;
 775         ir_node *irn;
 776         be_lv_t *lv                       = env->birg->lv;
 777
 778         int i, n;
 779         bitset_pos_t elm;
 780         unsigned step = 0;
 781         unsigned pressure = 0;
 782         struct list_head *head;
 783
 784         DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
 785         bitset_clear_all(live);
 786
 787         /* Set up the border list in the block info */
 788         head = obstack_alloc(env->obst, sizeof(*head));
 789         INIT_LIST_HEAD(head);
 790         assert(pmap_get(env->border_heads, block) == NULL);
 791         pmap_insert(env->border_heads, block, head);
 792
 793         /*
 794          * Make final uses of all values live out of the block.
 795          * They are necessary to build up real intervals.
 796          */
 797         be_lv_foreach(lv, block, be_lv_state_end, i) {
 798                 ir_node *irn = be_lv_get_irn(lv, block, i);
 799                 if(has_reg_class(env, irn)) {
 800                         DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
 801                         bitset_set(live, get_irn_idx(irn));
 802                         border_use(irn, step, 0);
 803                 }
 804         }
 805         ++step;
 806
 807         /*
 808          * Determine the last uses of a value inside the block, since they are
 809          * relevant for the interval borders.
 810          */
 811         sched_foreach_reverse(block, irn) {
 812                 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
 813                 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
 814
 815 #ifndef SCHEDULE_PROJS
 816                 if (get_irn_mode(irn) == mode_T) {
 817                         const ir_edge_t *edge;
 818
 819                         foreach_out_edge(irn, edge) {
 820                                 ir_node *proj = get_edge_src_irn(edge);
 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, proj)) {
 827                                         int nr = get_irn_idx(proj);
 828
 829                                         bitset_clear(live, nr);
 830                                         border_def(proj, step, 1);
 831                                 }
 832                         }
 833                 }
 834 #endif
 835                 /*
 836                  * If the node defines some value, which can put into a
 837                  * register of the current class, make a border for it.
 838                  */
 839                 if(has_reg_class(env, irn)) {
 840                         int nr = get_irn_idx(irn);
 841
 842                         bitset_clear(live, nr);
 843                         border_def(irn, step, 1);
 844                 }
 845
 846                 /*
 847                  * If the node is no phi node we can examine the uses.
 848                  */
 849                 if(!is_Phi(irn)) {
 850                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 851                                 ir_node *op = get_irn_n(irn, i);
 852
 853                                 if(has_reg_class(env, op)) {
 854                                         int nr = get_irn_idx(op);
 855                                         const char *msg = "-";
 856
 857                                         if(!bitset_is_set(live, nr)) {
 858                                                 border_use(op, step, 1);
 859                                                 bitset_set(live, nr);
 860                                                 msg = "X";
 861                                         }
 862
 863                                         DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
 864                                 }
 865                         }
 866                 }
 867                 ++step;
 868         }
 869
 870         bitset_foreach(live, elm) {
 871                 ir_node *irn = get_idx_irn(env->irg, elm);
 872                 if (be_is_live_in(lv, block, irn))
 873                         border_def(irn, step, 0);
 874         }
 875 }
 876
 877 static void assign(ir_node *block, void *env_ptr)
 878 {
 879         be_chordal_alloc_env_t *alloc_env = env_ptr;
 880         be_chordal_env_t *env       = alloc_env->chordal_env;
 881         bitset_t *live              = alloc_env->live;
 882         bitset_t *colors            = alloc_env->colors;
 883         bitset_t *in_colors         = alloc_env->in_colors;
 884         const arch_env_t *arch_env  = env->birg->main_env->arch_env;
 885         struct list_head *head      = get_block_border_head(env, block);
 886         be_lv_t *lv                 = env->birg->lv;
 887         pset *live_in               = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
 888
 889         const ir_node *irn;
 890         border_t *b;
 891
 892         bitset_clear_all(colors);
 893         bitset_clear_all(live);
 894         bitset_clear_all(in_colors);
 895
 896         DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
 897         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 898         list_for_each_entry(border_t, b, head, list) {
 899                 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
 900                                         b->irn, get_irn_idx(b->irn)));
 901         }
 902
 903         /*
 904          * Add initial defs for all values live in.
 905          * Since their colors have already been assigned (The dominators were
 906          * allocated before), we have to mark their colors as used also.
 907          */
 908         foreach_pset(live_in, irn) {
 909                 if(has_reg_class(env, irn)) {
 910                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 911                         int col;
 912
 913                         assert(reg && "Node must have been assigned a register");
 914                         col = arch_register_get_index(reg);
 915
 916                         DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
 917
 918                         /* Mark the color of the live in value as used. */
 919                         bitset_set(colors, col);
 920                         bitset_set(in_colors, col);
 921
 922                         /* Mark the value live in. */
 923                         bitset_set(live, get_irn_idx(irn));
 924                 }
 925         }
 926
 927         /*
 928          * Mind that the sequence of defs from back to front defines a perfect
 929          * elimination order. So, coloring the definitions from first to last
 930          * will work.
 931          */
 932         list_for_each_entry_reverse(border_t, b, head, list) {
 933                 ir_node *irn = b->irn;
 934                 int nr       = get_irn_idx(irn);
 935                 int ignore   = arch_irn_is(arch_env, irn, ignore);
 936
 937                 /*
 938                  * Assign a color, if it is a local def. Global defs already have a
 939                  * color.
 940                  */
 941                 if(b->is_def && !be_is_live_in(lv, block, irn)) {
 942                         const arch_register_t *reg;
 943                         int col = NO_COLOR;
 944
 945                         if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
 946                                 reg = arch_get_irn_register(arch_env, irn);
 947                                 col = reg->index;
 948                                 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
 949                         } else {
 950                                 col = get_next_free_reg(alloc_env, colors);
 951                                 reg = arch_register_for_index(env->cls, col);
 952                                 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
 953                                 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
 954                         }
 955
 956                         bitset_set(colors, col);
 957                         arch_set_irn_register(arch_env, irn, reg);
 958
 959                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
 960
 961                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 962                         bitset_set(live, nr);
 963                 }
 964
 965                 /* Clear the color upon a use. */
 966                 else if(!b->is_def) {
 967                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 968                         int col;
 969
 970                         assert(reg && "Register must have been assigned");
 971
 972                         col = arch_register_get_index(reg);
 973 #ifndef NDEBUG
 974                         if(!arch_register_type_is(reg, ignore)) {
 975                                 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 976                         }
 977 #endif
 978
 979                         bitset_clear(colors, col);
 980                         bitset_clear(live, nr);
 981                 }
 982         }
 983
 984         del_pset(live_in);
 985 }
 986
 987 /**
 988  * A new assign...
 989  */
 990 static void assign_new(ir_node *block, be_chordal_alloc_env_t *alloc_env, bitset_t *live_end_dom)
 991 {
 992         be_chordal_env_t *env      = alloc_env->chordal_env;
 993         bitset_t *colors           = alloc_env->colors;
 994         bitset_t *in_colors        = alloc_env->in_colors;
 995         bitset_t *live             = bitset_irg_malloc(env->irg);
 996         const arch_env_t *arch_env = env->birg->main_env->arch_env;
 997         be_irg_t *birg             = env->birg;
 998
 999         bitset_pos_t elm;
1000         ir_node *irn;
1001
1002         bitset_clear_all(colors);
1003         bitset_clear_all(in_colors);
1004
1005         /*
1006          * All variables which are live in to this block are live out
1007          * of the immediate dominator thanks to SSA properties. As we
1008          * have already visited the immediate dominator, we know these
1009          * variables. The only tjing left is to check wheather they are live
1010          * in here (they also could be phi arguments to some ohi not
1011          * in this block, hence we have to check).
1012          */
1013         bitset_foreach (live_end_dom, elm) {
1014                 ir_node *irn = get_idx_irn(env->irg, elm);
1015                 if (be_is_live_in(birg->lv, block, irn)) {
1016                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
1017                         int col;
1018
1019                         assert(be_is_live_in(env->birg->lv, block, irn));
1020                         assert(reg && "Node must have been assigned a register");
1021                         col = arch_register_get_index(reg);
1022
1023                         DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
1024
1025                         /* Mark the color of the live in value as used. */
1026                         bitset_set(colors, col);
1027                         bitset_set(in_colors, col);
1028
1029                         /* Mark the value live in. */
1030                         bitset_set(live, elm);
1031                 }
1032
1033                 else {
1034                         assert(!be_is_live_in(env->birg->lv, block, irn));
1035                 }
1036         }
1037
1038         /*
1039          * Mind that the sequence of defs from back to front defines a perfect
1040          * elimination order. So, coloring the definitions from first to last
1041          * will work.
1042          */
1043         sched_foreach (block, irn) {
1044                 int nr       = get_irn_idx(irn);
1045                 int ignore   = arch_irn_is(arch_env, irn, ignore);
1046
1047                 /* Clear the color upon a last use. */
1048                 if(!is_Phi(irn)) {
1049                         int i;
1050                         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
1051                                 ir_node *op = get_irn_n(irn, i);
1052
1053                                 /*
1054                                  * If the reg class matches and the operand is not live after
1055                                  * the node, irn is a last use of op and the register can
1056                                  * be freed.
1057                                  */
1058                                 if (has_reg_class(env, op)) {
1059                                         if (!be_lv_chk_after_irn(birg, op, irn)) {
1060                                                 const arch_register_t *reg = arch_get_irn_register(arch_env, op);
1061                                                 int col;
1062
1063                                                 assert(reg && "Register must have been assigned");
1064                                                 col = arch_register_get_index(reg);
1065                                                 bitset_clear(colors, col);
1066                                                 bitset_clear(live, nr);
1067                                         }
1068                                 }
1069                         }
1070                 }
1071
1072                 if (has_reg_class(env, irn)) {
1073                         const arch_register_t *reg;
1074                         int col = NO_COLOR;
1075
1076                         /*
1077                          * Assign a color, if it is a local def. Global defs already have a
1078                          * color.
1079                          */
1080                         if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
1081                                 reg = arch_get_irn_register(arch_env, irn);
1082                                 col = reg->index;
1083                                 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
1084                         } else {
1085                                 col = get_next_free_reg(alloc_env, colors);
1086                                 reg = arch_register_for_index(env->cls, col);
1087                                 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
1088                                 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
1089                         }
1090
1091                         bitset_set(colors, col);
1092                         arch_set_irn_register(arch_env, irn, reg);
1093
1094                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
1095
1096                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
1097                         bitset_set(live, nr);
1098                 }
1099
1100         }
1101
1102         dominates_for_each (block, irn) {
1103                 assign_new(irn, alloc_env, live);
1104         }
1105
1106         bitset_free(live);
1107 }
1108
1109 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
1110 {
1111         be_chordal_alloc_env_t env;
1112         char buf[256];
1113         be_lv_t *lv;
1114         be_irg_t *birg = chordal_env->birg;
1115         const arch_register_class_t *cls = chordal_env->cls;
1116
1117         int colors_n          = arch_register_class_n_regs(cls);
1118         ir_graph *irg         = chordal_env->irg;
1119         int allocatable_regs  = colors_n - be_put_ignore_regs(birg, cls, NULL);
1120
1121         /* some special classes contain only ignore regs, no work to be done */
1122         if(allocatable_regs == 0)
1123                 return;
1124
1125         be_assure_dom_front(birg);
1126         lv = be_assure_liveness(birg);
1127         be_liveness_assure_sets(lv);
1128         be_liveness_assure_chk(lv);
1129
1130         assure_doms(irg);
1131
1132         env.chordal_env   = chordal_env;
1133         env.colors_n      = colors_n;
1134         env.colors        = bitset_alloca(colors_n);
1135         env.tmp_colors    = bitset_alloca(colors_n);
1136         env.in_colors     = bitset_alloca(colors_n);
1137         env.pre_colored   = pset_new_ptr_default();
1138
1139         /* Handle register targeting constraints */
1140         dom_tree_walk_irg(irg, constraints, NULL, &env);
1141
1142         if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1143                 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1144                 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1145         }
1146
1147         env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1148
1149         /* First, determine the pressure */
1150         dom_tree_walk_irg(irg, pressure, NULL, &env);
1151
1152         /* Assign the colors */
1153 #ifdef NEW_STYLE_ASSIGN
1154         assign_new(get_irg_start_block(irg), &env, env.live);
1155 #else
1156         dom_tree_walk_irg(irg, assign, NULL, &env);
1157 #endif
1158
1159         if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1160                 plotter_t *plotter;
1161                 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1162                 plotter = new_plotter_ps(buf);
1163                 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1164                 plotter_free(plotter);
1165         }
1166
1167         bitset_free(env.live);
1168         del_pset(env.pre_colored);
1169 }
1170
1171 void be_init_chordal(void)
1172 {
1173         FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1174 }
1175
1176 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);