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                         pmap_insert(partners, op->carrier, partner);
 583                         if(partner != NULL)
 584                                 pmap_insert(partners, partner, op->carrier);
 585
 586                         /* don't insert a node twice */
 587                         int i;
 588                         for(i = 0; i < n_alloc; ++i) {
 589                                 if(alloc_nodes[i] == op->carrier) {
 590                                         break;
 591                                 }
 592                         }
 593                         if(i < n_alloc)
 594                                 continue;
 595
 596                         alloc_nodes[n_alloc] = op->carrier;
 597
 598                         DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier,
 599                              partner));
 600
 601                         bitset_clear_all(bs);
 602                         get_decisive_partner_regs(bs, op, op->partner);
 603
 604                         DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier,
 605                              bs));
 606
 607                         bitset_foreach(bs, col) {
 608                                 hungarian_add(bp, n_alloc, col, 1);
 609                                 // bipartite_add(bp, n_alloc, col);
 610                         }
 611
 612                         n_alloc++;
 613                 }
 614         }
 615
 616         /*
 617                 Put all nodes which live through the constrained instruction also to the
 618                 allocation bipartite graph. They are considered unconstrained.
 619         */
 620         if(perm != NULL) {
 621                 foreach_out_edge(perm, edge) {
 622                         int i;
 623                         ir_node *proj = get_edge_src_irn(edge);
 624
 625                         assert(is_Proj(proj));
 626
 627                         if(!values_interfere(birg, proj, irn) || pmap_contains(partners, proj))
 628                                 continue;
 629
 630                         /* don't insert a node twice */
 631                         for(i = 0; i < n_alloc; ++i) {
 632                                 if(alloc_nodes[i] == proj) {
 633                                         break;
 634                                 }
 635                         }
 636                         if(i < n_alloc)
 637                                 continue;
 638
 639
 640                         assert(n_alloc < n_regs);
 641
 642                         alloc_nodes[n_alloc] = proj;
 643                         pmap_insert(partners, proj, NULL);
 644
 645                         bitset_clear_all(bs);
 646                         arch_put_non_ignore_regs(aenv, env->cls, bs);
 647                         bitset_andnot(bs, env->ignore_colors);
 648                         bitset_foreach(bs, col) {
 649                                 hungarian_add(bp, n_alloc, col, 1);
 650                                 // bipartite_add(bp, n_alloc, col);
 651                         }
 652
 653                         n_alloc++;
 654                 }
 655         }
 656
 657         /* Compute a valid register allocation. */
 658         hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
 659         match_res = hungarian_solve(bp, assignment, &cost, 1);
 660         assert(match_res == 0 && "matching failed");
 661         //bipartite_matching(bp, assignment);
 662
 663         /* Assign colors obtained from the matching. */
 664         for(i = 0; i < n_alloc; ++i) {
 665                 const arch_register_t *reg;
 666                 ir_node *nodes[2];
 667                 int j;
 668
 669                 assert(assignment[i] >= 0 && "there must have been a register assigned");
 670                 reg = arch_register_for_index(env->cls, assignment[i]);
 671
 672                 nodes[0] = alloc_nodes[i];
 673                 nodes[1] = pmap_get(partners, alloc_nodes[i]);
 674
 675                 for(j = 0; j < 2; ++j) {
 676                         if(!nodes[j])
 677                                 continue;
 678
 679                         assert(! (reg->type & arch_register_type_ignore));
 680                         arch_set_irn_register(aenv, nodes[j], reg);
 681                         (void) pset_hinsert_ptr(alloc_env->pre_colored, nodes[j]);
 682                         DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", nodes[j], reg->name));
 683                 }
 684         }
 685
 686         /* Allocate the non-constrained Projs of the Perm. */
 687         if(perm != NULL) {
 688                 bitset_clear_all(bs);
 689
 690                 /* Put the colors of all Projs in a bitset. */
 691                 foreach_out_edge(perm, edge) {
 692                         ir_node *proj              = get_edge_src_irn(edge);
 693                         const arch_register_t *reg = arch_get_irn_register(aenv, proj);
 694
 695                         if(reg != NULL)
 696                                 bitset_set(bs, reg->index);
 697                 }
 698
 699                 /* Assign the not yet assigned Projs of the Perm a suitable color. */
 700                 foreach_out_edge(perm, edge) {
 701                         ir_node *proj              = get_edge_src_irn(edge);
 702                         const arch_register_t *reg = arch_get_irn_register(aenv, proj);
 703
 704                         DBG((dbg, LEVEL_2, "\tchecking reg of %+F: %s\n", proj, reg ? reg->name : "<none>"));
 705
 706                         if(reg == NULL) {
 707                                 col = get_next_free_reg(alloc_env, bs);
 708                                 reg = arch_register_for_index(env->cls, col);
 709                                 bitset_set(bs, reg->index);
 710                                 arch_set_irn_register(aenv, proj, reg);
 711                                 pset_insert_ptr(alloc_env->pre_colored, proj);
 712                                 DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", proj, reg->name));
 713                         }
 714                 }
 715         }
 716
 717         //bipartite_free(bp);
 718         hungarian_free(bp);
 719         pmap_destroy(partners);
 720
 721 end:
 722         obstack_free(env->obst, base);
 723         return res;
 724 }
 725
 726 /**
 727  * Handle constraint nodes in each basic block.
 728  * handle_constraints() inserts Perm nodes which perm
 729  * over all values live at the constrained node right in front
 730  * of the constrained node. These Perms signal a constrained node.
 731  * For further comments, refer to handle_constraints().
 732  */
 733 static void constraints(ir_node *bl, void *data)
 734 {
 735         be_chordal_alloc_env_t *env = data;
 736
 737         /*
 738                 Start silent in the start block.
 739                 The silence remains until the first barrier is seen.
 740                 Each other block is begun loud.
 741         */
 742         int silent                  = bl == get_irg_start_block(get_irn_irg(bl));
 743         ir_node *irn;
 744
 745         /*
 746                 If the block is the start block search the barrier and
 747                 start handling constraints from there.
 748         */
 749
 750         for(irn = sched_first(bl); !sched_is_end(irn);) {
 751                 irn = handle_constraints(env, irn, &silent);
 752         }
 753 }
 754
 755 /**
 756  * Annotate the register pressure to the nodes and compute
 757  * the liveness intervals.
 758  * @param block The block to do it for.
 759  * @param env_ptr The environment.
 760  */
 761 static void pressure(ir_node *block, void *env_ptr)
 762 {
 763 /* Convenience macro for a def */
 764 #define border_def(irn, step, real) \
 765         border_add(env, head, irn, step, pressure--, 1, real)
 766
 767 /* Convenience macro for a use */
 768 #define border_use(irn, step, real) \
 769         border_add(env, head, irn, step, ++pressure, 0, real)
 770
 771         be_chordal_alloc_env_t *alloc_env = env_ptr;
 772         be_chordal_env_t *env             = alloc_env->chordal_env;
 773         bitset_t *live                    = alloc_env->live;
 774         ir_node *irn;
 775         be_lv_t *lv                       = env->birg->lv;
 776
 777         int i, n;
 778         bitset_pos_t elm;
 779         unsigned step = 0;
 780         unsigned pressure = 0;
 781         struct list_head *head;
 782
 783         DBG((dbg, LEVEL_1, "Computing pressure in block %+F\n", block));
 784         bitset_clear_all(live);
 785
 786         /* Set up the border list in the block info */
 787         head = obstack_alloc(env->obst, sizeof(*head));
 788         INIT_LIST_HEAD(head);
 789         assert(pmap_get(env->border_heads, block) == NULL);
 790         pmap_insert(env->border_heads, block, head);
 791
 792         /*
 793          * Make final uses of all values live out of the block.
 794          * They are necessary to build up real intervals.
 795          */
 796         be_lv_foreach(lv, block, be_lv_state_end, i) {
 797                 ir_node *irn = be_lv_get_irn(lv, block, i);
 798                 if(has_reg_class(env, irn)) {
 799                         DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_idx(irn)));
 800                         bitset_set(live, get_irn_idx(irn));
 801                         border_use(irn, step, 0);
 802                 }
 803         }
 804         ++step;
 805
 806         /*
 807          * Determine the last uses of a value inside the block, since they are
 808          * relevant for the interval borders.
 809          */
 810         sched_foreach_reverse(block, irn) {
 811                 DBG((dbg, LEVEL_1, "\tinsn: %+F, pressure: %d\n", irn, pressure));
 812                 DBG((dbg, LEVEL_2, "\tlive: %B\n", live));
 813
 814 #ifndef SCHEDULE_PROJS
 815                 if (get_irn_mode(irn) == mode_T) {
 816                         const ir_edge_t *edge;
 817
 818                         foreach_out_edge(irn, edge) {
 819                                 ir_node *proj = get_edge_src_irn(edge);
 820
 821                                 /*
 822                                  * If the node defines some value, which can put into a
 823                                  * register of the current class, make a border for it.
 824                                  */
 825                                 if(has_reg_class(env, proj)) {
 826                                         int nr = get_irn_idx(proj);
 827
 828                                         bitset_clear(live, nr);
 829                                         border_def(proj, step, 1);
 830                                 }
 831                         }
 832                 }
 833 #endif
 834                 /*
 835                  * If the node defines some value, which can put into a
 836                  * register of the current class, make a border for it.
 837                  */
 838                 if(has_reg_class(env, irn)) {
 839                         int nr = get_irn_idx(irn);
 840
 841                         bitset_clear(live, nr);
 842                         border_def(irn, step, 1);
 843                 }
 844
 845                 /*
 846                  * If the node is no phi node we can examine the uses.
 847                  */
 848                 if(!is_Phi(irn)) {
 849                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 850                                 ir_node *op = get_irn_n(irn, i);
 851
 852                                 if(has_reg_class(env, op)) {
 853                                         int nr = get_irn_idx(op);
 854                                         const char *msg = "-";
 855
 856                                         if(!bitset_is_set(live, nr)) {
 857                                                 border_use(op, step, 1);
 858                                                 bitset_set(live, nr);
 859                                                 msg = "X";
 860                                         }
 861
 862                                         DBG((dbg, LEVEL_4, "\t\t%s pos: %d, use: %+F\n", msg, i, op));
 863                                 }
 864                         }
 865                 }
 866                 ++step;
 867         }
 868
 869         bitset_foreach(live, elm) {
 870                 ir_node *irn = get_idx_irn(env->irg, elm);
 871                 if (be_is_live_in(lv, block, irn))
 872                         border_def(irn, step, 0);
 873         }
 874 }
 875
 876 static void assign(ir_node *block, void *env_ptr)
 877 {
 878         be_chordal_alloc_env_t *alloc_env = env_ptr;
 879         be_chordal_env_t *env       = alloc_env->chordal_env;
 880         bitset_t *live              = alloc_env->live;
 881         bitset_t *colors            = alloc_env->colors;
 882         bitset_t *in_colors         = alloc_env->in_colors;
 883         const arch_env_t *arch_env  = env->birg->main_env->arch_env;
 884         struct list_head *head      = get_block_border_head(env, block);
 885         be_lv_t *lv                 = env->birg->lv;
 886         pset *live_in               = be_lv_pset_put_in(lv, block, pset_new_ptr_default());
 887
 888         const ir_node *irn;
 889         border_t *b;
 890
 891         bitset_clear_all(colors);
 892         bitset_clear_all(live);
 893         bitset_clear_all(in_colors);
 894
 895         DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
 896         DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
 897         list_for_each_entry(border_t, b, head, list) {
 898                 DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
 899                                         b->irn, get_irn_idx(b->irn)));
 900         }
 901
 902         /*
 903          * Add initial defs for all values live in.
 904          * Since their colors have already been assigned (The dominators were
 905          * allocated before), we have to mark their colors as used also.
 906          */
 907         foreach_pset(live_in, irn) {
 908                 if(has_reg_class(env, irn)) {
 909                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 910                         int col;
 911
 912                         assert(reg && "Node must have been assigned a register");
 913                         col = arch_register_get_index(reg);
 914
 915                         DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
 916
 917                         /* Mark the color of the live in value as used. */
 918                         bitset_set(colors, col);
 919                         bitset_set(in_colors, col);
 920
 921                         /* Mark the value live in. */
 922                         bitset_set(live, get_irn_idx(irn));
 923                 }
 924         }
 925
 926         /*
 927          * Mind that the sequence of defs from back to front defines a perfect
 928          * elimination order. So, coloring the definitions from first to last
 929          * will work.
 930          */
 931         list_for_each_entry_reverse(border_t, b, head, list) {
 932                 ir_node *irn = b->irn;
 933                 int nr       = get_irn_idx(irn);
 934                 int ignore   = arch_irn_is(arch_env, irn, ignore);
 935
 936                 /*
 937                  * Assign a color, if it is a local def. Global defs already have a
 938                  * color.
 939                  */
 940                 if(b->is_def && !be_is_live_in(lv, block, irn)) {
 941                         const arch_register_t *reg;
 942                         int col = NO_COLOR;
 943
 944                         if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
 945                                 reg = arch_get_irn_register(arch_env, irn);
 946                                 col = reg->index;
 947                                 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
 948                         } else {
 949                                 col = get_next_free_reg(alloc_env, colors);
 950                                 reg = arch_register_for_index(env->cls, col);
 951                                 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
 952                                 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
 953                         }
 954
 955                         bitset_set(colors, col);
 956                         arch_set_irn_register(arch_env, irn, reg);
 957
 958                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
 959
 960                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
 961                         bitset_set(live, nr);
 962                 }
 963
 964                 /* Clear the color upon a use. */
 965                 else if(!b->is_def) {
 966                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 967                         int col;
 968
 969                         assert(reg && "Register must have been assigned");
 970
 971                         col = arch_register_get_index(reg);
 972 #ifndef NDEBUG
 973                         if(!arch_register_type_is(reg, ignore)) {
 974                                 assert(bitset_is_set(live, nr) && "Cannot have a non live use");
 975                         }
 976 #endif
 977
 978                         bitset_clear(colors, col);
 979                         bitset_clear(live, nr);
 980                 }
 981         }
 982
 983         del_pset(live_in);
 984 }
 985
 986 /**
 987  * A new assign...
 988  */
 989 static void assign_new(ir_node *block, be_chordal_alloc_env_t *alloc_env, bitset_t *live_end_dom)
 990 {
 991         be_chordal_env_t *env      = alloc_env->chordal_env;
 992         bitset_t *colors           = alloc_env->colors;
 993         bitset_t *in_colors        = alloc_env->in_colors;
 994         bitset_t *live             = bitset_irg_malloc(env->irg);
 995         const arch_env_t *arch_env = env->birg->main_env->arch_env;
 996         be_irg_t *birg             = env->birg;
 997
 998         bitset_pos_t elm;
 999         ir_node *irn;
1000
1001         bitset_clear_all(colors);
1002         bitset_clear_all(in_colors);
1003
1004         /*
1005          * All variables which are live in to this block are live out
1006          * of the immediate dominator thanks to SSA properties. As we
1007          * have already visited the immediate dominator, we know these
1008          * variables. The only tjing left is to check wheather they are live
1009          * in here (they also could be phi arguments to some ohi not
1010          * in this block, hence we have to check).
1011          */
1012         bitset_foreach (live_end_dom, elm) {
1013                 ir_node *irn = get_idx_irn(env->irg, elm);
1014                 if (be_is_live_in(birg->lv, block, irn)) {
1015                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
1016                         int col;
1017
1018                         assert(be_is_live_in(env->birg->lv, block, irn));
1019                         assert(reg && "Node must have been assigned a register");
1020                         col = arch_register_get_index(reg);
1021
1022                         DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
1023
1024                         /* Mark the color of the live in value as used. */
1025                         bitset_set(colors, col);
1026                         bitset_set(in_colors, col);
1027
1028                         /* Mark the value live in. */
1029                         bitset_set(live, elm);
1030                 }
1031
1032                 else {
1033                         assert(!be_is_live_in(env->birg->lv, block, irn));
1034                 }
1035         }
1036
1037         /*
1038          * Mind that the sequence of defs from back to front defines a perfect
1039          * elimination order. So, coloring the definitions from first to last
1040          * will work.
1041          */
1042         sched_foreach (block, irn) {
1043                 int nr       = get_irn_idx(irn);
1044                 int ignore   = arch_irn_is(arch_env, irn, ignore);
1045
1046                 /* Clear the color upon a last use. */
1047                 if(!is_Phi(irn)) {
1048                         int i;
1049                         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
1050                                 ir_node *op = get_irn_n(irn, i);
1051
1052                                 /*
1053                                  * If the reg class matches and the operand is not live after
1054                                  * the node, irn is a last use of op and the register can
1055                                  * be freed.
1056                                  */
1057                                 if (has_reg_class(env, op)) {
1058                                         if (!be_lv_chk_after_irn(birg, op, irn)) {
1059                                                 const arch_register_t *reg = arch_get_irn_register(arch_env, op);
1060                                                 int col;
1061
1062                                                 assert(reg && "Register must have been assigned");
1063                                                 col = arch_register_get_index(reg);
1064                                                 bitset_clear(colors, col);
1065                                                 bitset_clear(live, nr);
1066                                         }
1067                                 }
1068                         }
1069                 }
1070
1071                 if (has_reg_class(env, irn)) {
1072                         const arch_register_t *reg;
1073                         int col = NO_COLOR;
1074
1075                         /*
1076                          * Assign a color, if it is a local def. Global defs already have a
1077                          * color.
1078                          */
1079                         if(ignore || pset_find_ptr(alloc_env->pre_colored, irn)) {
1080                                 reg = arch_get_irn_register(arch_env, irn);
1081                                 col = reg->index;
1082                                 assert(!bitset_is_set(colors, col) && "pre-colored register must be free");
1083                         } else {
1084                                 col = get_next_free_reg(alloc_env, colors);
1085                                 reg = arch_register_for_index(env->cls, col);
1086                                 assert(arch_get_irn_register(arch_env, irn) == NULL && "This node must not have been assigned a register yet");
1087                                 assert(!arch_register_type_is(reg, ignore) && "Must not assign ignore register");
1088                         }
1089
1090                         bitset_set(colors, col);
1091                         arch_set_irn_register(arch_env, irn, reg);
1092
1093                         DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_register_get_name(reg), col, irn));
1094
1095                         assert(!bitset_is_set(live, nr) && "Value's definition must not have been encountered");
1096                         bitset_set(live, nr);
1097                 }
1098
1099         }
1100
1101         dominates_for_each (block, irn) {
1102                 assign_new(irn, alloc_env, live);
1103         }
1104
1105         bitset_free(live);
1106 }
1107
1108 void be_ra_chordal_color(be_chordal_env_t *chordal_env)
1109 {
1110         be_chordal_alloc_env_t env;
1111         char buf[256];
1112         be_lv_t *lv;
1113         be_irg_t *birg = chordal_env->birg;
1114         const arch_register_class_t *cls = chordal_env->cls;
1115
1116         int colors_n          = arch_register_class_n_regs(cls);
1117         ir_graph *irg         = chordal_env->irg;
1118         int allocatable_regs  = colors_n - be_put_ignore_regs(birg, cls, NULL);
1119
1120         /* some special classes contain only ignore regs, no work to be done */
1121         if(allocatable_regs == 0)
1122                 return;
1123
1124         be_assure_dom_front(birg);
1125         lv = be_assure_liveness(birg);
1126         be_liveness_assure_sets(lv);
1127         be_liveness_assure_chk(lv);
1128
1129         assure_doms(irg);
1130
1131         env.chordal_env   = chordal_env;
1132         env.colors_n      = colors_n;
1133         env.colors        = bitset_alloca(colors_n);
1134         env.tmp_colors    = bitset_alloca(colors_n);
1135         env.in_colors     = bitset_alloca(colors_n);
1136         env.pre_colored   = pset_new_ptr_default();
1137
1138         /* Handle register targeting constraints */
1139         dom_tree_walk_irg(irg, constraints, NULL, &env);
1140
1141         if(chordal_env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
1142                 snprintf(buf, sizeof(buf), "-%s-constr", chordal_env->cls->name);
1143                 be_dump(chordal_env->irg, buf, dump_ir_block_graph_sched);
1144         }
1145
1146         env.live = bitset_malloc(get_irg_last_idx(chordal_env->irg));
1147
1148         /* First, determine the pressure */
1149         dom_tree_walk_irg(irg, pressure, NULL, &env);
1150
1151         /* Assign the colors */
1152 #ifdef NEW_STYLE_ASSIGN
1153         assign_new(get_irg_start_block(irg), &env, env.live);
1154 #else
1155         dom_tree_walk_irg(irg, assign, NULL, &env);
1156 #endif
1157
1158         if(chordal_env->opts->dump_flags & BE_CH_DUMP_TREE_INTV) {
1159                 plotter_t *plotter;
1160                 ir_snprintf(buf, sizeof(buf), "ifg_%s_%F.eps", chordal_env->cls->name, irg);
1161                 plotter = new_plotter_ps(buf);
1162                 draw_interval_tree(&draw_chordal_def_opts, chordal_env, plotter);
1163                 plotter_free(plotter);
1164         }
1165
1166         bitset_free(env.live);
1167         del_pset(env.pre_colored);
1168 }
1169
1170 void be_init_chordal(void)
1171 {
1172         FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
1173 }
1174
1175 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal);