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