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

   1 /**
   2  * @file   benode.c
   3  * @date   17.05.2005
   4  * @author Sebastian Hack
   5  *
   6  * Backend node support.
   7  *
   8  * This file provdies Perm, Copy, Spill and Reload nodes.
   9  *
  10  * Copyright (C) 2005 Universitaet Karlsruhe
  11  * Released under the GPL
  12  */
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include "config.h"
  16 #endif
  17
  18 #include <stdlib.h>
  19
  20 #include "obst.h"
  21 #include "set.h"
  22 #include "pmap.h"
  23 #include "util.h"
  24 #include "debug.h"
  25 #include "fourcc.h"
  26
  27 #include "irop_t.h"
  28 #include "irmode_t.h"
  29 #include "irnode_t.h"
  30 #include "ircons_t.h"
  31 #include "irprintf.h"
  32
  33 #include "be_t.h"
  34 #include "belive_t.h"
  35 #include "besched_t.h"
  36 #include "benode_t.h"
  37
  38 #include "beirgmod.h"
  39
  40 #define DBG_LEVEL 0
  41
  42 #define BENODE_MAGIC FOURCC('B', 'E', 'N', 'O')
  43
  44 typedef enum _node_kind_t {
  45         node_kind_spill,
  46         node_kind_reload,
  47         node_kind_perm,
  48         node_kind_copy,
  49         node_kind_kill,
  50         node_kind_last
  51 } node_kind_t;
  52
  53 typedef struct {
  54         node_kind_t kind;
  55         const arch_register_class_t *cls;
  56         ir_op *op;
  57         int n_pos;
  58         int *pos;
  59 } be_op_t;
  60
  61 typedef struct {
  62         const arch_register_t *reg;
  63         arch_register_req_t   req;
  64 } be_reg_data_t;
  65
  66 typedef struct {
  67         unsigned      magic;
  68         const be_op_t *op;
  69         int           n_regs;
  70         be_reg_data_t reg_data[1];
  71 } be_node_attr_t;
  72
  73 typedef struct {
  74         be_node_attr_t attr;
  75         ir_node *spill_ctx;  /**< The node in whose context this spill was introduced. */
  76         unsigned offset;     /**< The offset of the memory location the spill writes to
  77                                                    in the spill area. */
  78 } be_spill_attr_t;
  79
  80
  81 ir_node *new_Keep(ir_graph *irg, ir_node *bl, int n, ir_node *in[])
  82 {
  83         static ir_op *keep_op = NULL;
  84         ir_node *irn;
  85
  86         if(!keep_op)
  87                 keep_op = new_ir_op(get_next_ir_opcode(), "Keep", op_pin_state_pinned,
  88                         irop_flag_keep, oparity_variable, 0, 0, NULL);
  89
  90         irn = new_ir_node(NULL, irg, bl, keep_op, mode_ANY, n, in);
  91         keep_alive(irn);
  92
  93         return irn;
  94 }
  95
  96 static int templ_pos_Spill[] = {
  97         0
  98 };
  99
 100 static int templ_pos_Reload[] = {
 101         -1
 102 };
 103
 104 static int templ_pos_Copy[] = {
 105         0, -1
 106 };
 107
 108 static int templ_pos_Kill[] = {
 109         0
 110 };
 111
 112 static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason);
 113
 114 static const ir_op_ops be_node_ops = {
 115         NULL,
 116         NULL,
 117         NULL,
 118         NULL,
 119         NULL,
 120         NULL,
 121         NULL,
 122         NULL,
 123         NULL,
 124         NULL,
 125         NULL,
 126         dump_node,
 127         NULL
 128 };
 129
 130 static INLINE int is_be_node(const ir_node *irn)
 131 {
 132         const be_node_attr_t *attr = (const be_node_attr_t *) &irn->attr;
 133         return attr->magic == BENODE_MAGIC;
 134 }
 135
 136 static INLINE int is_be_kind(const ir_node *irn, node_kind_t kind)
 137 {
 138         const be_node_attr_t *a = (const be_node_attr_t *) &irn->attr;
 139         return a->magic == BENODE_MAGIC && a->op && a->op->kind == kind;
 140 }
 141
 142 static INLINE void *get_attr_and_check(ir_node *irn, node_kind_t kind)
 143 {
 144         is_be_kind(irn, kind);
 145         return &irn->attr;
 146 }
 147
 148 static be_node_attr_t *init_node_attr(ir_node *irn,
 149                                                                           const be_op_t *op,
 150                                                                           const arch_register_class_t *cls,
 151                                                                           int n_regs)
 152
 153 {
 154         be_node_attr_t *attr = (be_node_attr_t *) &irn->attr;
 155         int i;
 156
 157         attr->magic   = BENODE_MAGIC;
 158         attr->n_regs  = n_regs;
 159         attr->op      = op;
 160
 161         for(i = 0; i < n_regs; ++i) {
 162                 be_reg_data_t *rd = attr->reg_data + i;
 163
 164                 memset(&rd->req, 0, sizeof(rd->req));
 165                 rd->reg         = NULL;
 166                 rd->req.cls     = cls;
 167                 rd->req.type    = arch_register_req_type_normal;
 168         }
 169
 170         return attr;
 171 }
 172
 173 #define ARRSIZE(x) (sizeof(x) / sizeof(x[0]))
 174
 175 static int cmp_op_map(const void *a, const void *b, size_t size)
 176 {
 177         const be_op_t *x = a;
 178         const be_op_t *y = b;
 179
 180         return !(x->kind == y->kind && x->cls == y->cls);
 181 }
 182
 183 static be_op_t *get_op(const be_node_factory_t *fact,
 184                 const arch_register_class_t *cls, node_kind_t kind)
 185 {
 186         be_op_t templ;
 187
 188         templ.kind = kind;
 189         templ.cls = cls;
 190
 191         return set_insert(fact->ops, &templ, sizeof(templ),
 192                 HASH_PTR(cls) + 7 * kind);
 193 }
 194
 195
 196
 197 ir_node *new_Spill(const be_node_factory_t *factory,
 198                 const arch_register_class_t *cls,
 199                 ir_graph *irg, ir_node *bl, ir_node *node_to_spill, ir_node *ctx)
 200 {
 201         be_spill_attr_t *a;
 202         ir_node *irn;
 203         ir_node *in[1];
 204         be_op_t *bop = get_op(factory, cls, node_kind_spill);
 205         ir_op *op    = bop->op;
 206
 207         assert(op && "Spill opcode must be present for this register class");
 208         in[0]        = node_to_spill;
 209         irn          = new_ir_node(NULL, irg, bl, op, mode_M, 1, in);
 210         a            = (be_spill_attr_t *) init_node_attr(irn, bop, cls, 0);
 211         a->spill_ctx = ctx;
 212         a->offset    = 0;
 213
 214         return irn;
 215 }
 216
 217 void set_Spill_offset(ir_node *irn, unsigned offset)
 218 {
 219         be_spill_attr_t *a = (be_spill_attr_t *) &irn->attr;
 220         assert(is_be_kind(irn, node_kind_spill));
 221         a->offset = offset;
 222 }
 223
 224 static ir_node *find_a_spill_walker(ir_node *irn, unsigned visited_nr)
 225 {
 226         if(get_irn_visited(irn) < visited_nr) {
 227                 set_irn_visited(irn, visited_nr);
 228
 229                 if(is_Phi(irn)) {
 230                         int i, n;
 231                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 232                                 ir_node *n = find_a_spill_walker(get_irn_n(irn, i), visited_nr);
 233                                 if(n != NULL)
 234                                         return n;
 235                         }
 236                 }
 237
 238                 else if(is_be_kind(irn, node_kind_spill))
 239                         return irn;
 240         }
 241
 242         return NULL;
 243 }
 244
 245 ir_node *get_Spill_context(const ir_node *irn) {
 246         be_spill_attr_t *a = (be_spill_attr_t *) &irn->attr;
 247         assert(is_be_kind(irn, node_kind_spill));
 248         return a->spill_ctx;
 249 }
 250
 251 /**
 252  * Finds a spill for a reload.
 253  * If the reload is directly using the spill, this is simple,
 254  * else we perform DFS from the reload (over all PhiMs) and return
 255  * the first spill node we find.
 256  */
 257 static INLINE ir_node *find_a_spill(ir_node *irn)
 258 {
 259         ir_graph *irg       = get_irn_irg(irn);
 260         unsigned visited_nr = get_irg_visited(irg) + 1;
 261
 262         assert(is_be_kind(irn, node_kind_reload));
 263         set_irg_visited(irg, visited_nr);
 264         return find_a_spill_walker(irn, visited_nr);
 265 }
 266
 267
 268 unsigned get_Spill_offset(ir_node *irn)
 269 {
 270         be_node_attr_t *a = (be_node_attr_t *) &irn->attr;
 271         assert(is_be_node(irn));
 272
 273         switch(a->op->kind) {
 274         case node_kind_reload:
 275                 assert(0 && "not yet implemented");
 276                 return get_Spill_offset(find_a_spill(irn));
 277         case node_kind_spill:
 278                 return ((be_spill_attr_t *) a)->offset;
 279         default:
 280                 assert(0 && "Illegal node kind (spill/reload required)");
 281         }
 282
 283         return 0;
 284 }
 285
 286 ir_node *new_Reload(const be_node_factory_t *factory,
 287                 const arch_register_class_t *cls, ir_graph *irg,
 288                 ir_node *bl, ir_mode *mode, ir_node *spill_node)
 289 {
 290         ir_node *irn, *in[1];
 291         be_op_t *bop = get_op(factory, cls, node_kind_reload);
 292         ir_op *op    = bop->op;
 293
 294         assert(op && "Reload opcode must be present for this register class");
 295         in[0] = spill_node;
 296
 297         irn  = new_ir_node(NULL, irg, bl, op, mode, 1, in);
 298         init_node_attr(irn, bop, cls, 1);
 299
 300         return irn;
 301 }
 302
 303 ir_node *new_Perm(const be_node_factory_t *factory,
 304                 const arch_register_class_t *cls,
 305                 ir_graph *irg, ir_node *bl, int arity, ir_node **in)
 306 {
 307         ir_node *irn;
 308         be_op_t *bop = get_op(factory, cls, node_kind_perm);
 309         ir_op *op    = bop->op;
 310
 311         irn  = new_ir_node(NULL, irg, bl, op, mode_T, arity, in);
 312         init_node_attr(irn, bop, cls, arity);
 313
 314         return irn;
 315 }
 316
 317 ir_node *new_Copy(const be_node_factory_t *factory,
 318                 const arch_register_class_t *cls,
 319                 ir_graph *irg, ir_node *bl, ir_node *in)
 320 {
 321         ir_node *irn, *ins[1];
 322         be_op_t *bop = get_op(factory, cls, node_kind_copy);
 323         ir_op *op    = bop->op;
 324
 325         ins[0] = in;
 326
 327         irn  = new_ir_node(NULL, irg, bl, op, get_irn_mode(in), 1, ins);
 328         init_node_attr(irn, bop, cls, 1);
 329
 330         return irn;
 331 }
 332
 333 ir_node *be_spill(
 334                 const be_node_factory_t *factory,
 335                 const arch_env_t *arch_env,
 336                 ir_node *irn, ir_node *ctx)
 337 {
 338         const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
 339
 340         ir_node *bl    = get_nodes_block(irn);
 341         ir_graph *irg  = get_irn_irg(bl);
 342         ir_node *spill = new_Spill(factory, cls, irg, bl, irn, ctx);
 343         ir_node *insert;
 344
 345         /*
 346          * search the right insertion point. a spill of a phi cannot be put
 347          * directly after the phi, if there are some phis behind the one which
 348          * is spilled.
 349          */
 350         insert = sched_next(irn);
 351         while(is_Phi(insert) && !sched_is_end(insert))
 352                 insert = sched_next(insert);
 353
 354         sched_add_before(insert, spill);
 355         return spill;
 356 }
 357
 358 ir_node *be_reload(const be_node_factory_t *factory,
 359                                          const arch_env_t *arch_env,
 360                                          const arch_register_class_t *cls,
 361                                          ir_node *irn, int pos, ir_mode *mode, ir_node *spill)
 362 {
 363         ir_node *reload;
 364
 365         ir_node *bl   = get_nodes_block(irn);
 366         ir_graph *irg = get_irn_irg(bl);
 367
 368         assert(be_is_Spill(spill)
 369                         || (is_Phi(spill) && get_irn_mode(spill) == mode_M));
 370
 371         reload = new_Reload(factory, cls, irg, bl, mode, spill);
 372
 373         set_irn_n(irn, pos, reload);
 374         sched_add_before(irn, reload);
 375         return reload;
 376 }
 377
 378 /**
 379  * If the node is a proj, reset the node to the proj's target and return
 380  * the proj number.
 381  * @param node The address of a node pointer.
 382  * @param def  A default value.
 383  * @return     If *node is a Proj, *node is set to the Proj's target and
 384  *             the Proj number is returned. Else *node remains the same and @p def
 385  *             is returned.
 386  */
 387 static int redir_proj(const ir_node **node, int def)
 388 {
 389         const ir_node *n = *node;
 390
 391         if(is_Proj(n)) {
 392                 *node = get_Proj_pred(n);
 393                 def = -(get_Proj_proj(n) + 1);
 394         }
 395
 396         return def;
 397 }
 398
 399 static const arch_register_req_t *
 400 be_node_get_irn_reg_req(const arch_irn_ops_t *_self,
 401                 arch_register_req_t *req, const ir_node *irn, int pos)
 402 {
 403         /* We cannot get output requirements for tuple nodes. */
 404         if(get_irn_mode(irn) == mode_T && pos < 0)
 405                 return NULL;
 406
 407         /*
 408          * if we're interested in an output operand (pos < 0), so let's resolve projs.
 409          */
 410         if(pos < 0)
 411                 pos = redir_proj((const ir_node **) &irn, pos);
 412
 413         if(is_be_node(irn)) {
 414                 const be_node_attr_t *a = (const be_node_attr_t *) &irn->attr;
 415                 const be_op_t *bo       = a->op;
 416                 int i;
 417
 418                 for(i = 0; i < bo->n_pos; ++i) {
 419                         if(pos == bo->pos[i]) {
 420
 421                                 /* be nodes have no input constraints.
 422                                    so return normal register requirements. */
 423                                 if(pos >= 0) {
 424                                         memset(req, 0, sizeof(req[0]));
 425                                         req->cls = bo->cls;
 426                                         req->type = arch_register_req_type_normal;
 427                                 }
 428
 429                                 /*
 430                                  * if an output requirement is requested,
 431                                  * return the one stored in the node.
 432                                  */
 433                                 else
 434                                         *req = a->reg_data[-pos - 1].req;
 435
 436                                 return req;
 437                         }
 438                 }
 439         }
 440
 441         return NULL;
 442 }
 443
 444 void be_set_Perm_out_req(ir_node *irn, int pos, const arch_register_req_t *req)
 445 {
 446         be_node_attr_t *a = get_attr_and_check(irn, node_kind_perm);
 447         assert(pos >= 0 && pos < get_irn_arity(irn) && "position out of range");
 448         a->reg_data[pos].req = *req;
 449 }
 450
 451 void
 452 be_node_set_irn_reg(const arch_irn_ops_t *_self, ir_node *irn,
 453                 const arch_register_t *reg)
 454 {
 455         int pos;
 456         be_op_t *bo;
 457         be_node_attr_t *attr;
 458         const be_node_factory_t *factory =
 459                 container_of(_self, const be_node_factory_t, irn_ops);
 460
 461         if(get_irn_mode(irn) == mode_T)
 462                 return;
 463
 464         pos = redir_proj((const ir_node **) &irn, -1);
 465         bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
 466
 467         if(!bo)
 468                 return;
 469
 470         attr = (be_node_attr_t *) &irn->attr;
 471         attr->reg_data[-pos - 1].reg = reg;
 472 }
 473
 474 const arch_register_t *
 475 be_node_get_irn_reg(const arch_irn_ops_t *_self, const ir_node *irn)
 476 {
 477         int i, pos;
 478         be_op_t *bo;
 479         const be_node_factory_t *factory =
 480                 container_of(_self, const be_node_factory_t, irn_ops);
 481
 482         if(get_irn_mode(irn) == mode_T)
 483                 return NULL;
 484
 485         pos = redir_proj((const ir_node **) &irn, -1);
 486         bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
 487
 488         if(!bo)
 489                 return NULL;
 490
 491         for(i = 0; i < bo->n_pos; ++i) {
 492                 if(bo->pos[i] == pos) {
 493                         be_node_attr_t *attr = (be_node_attr_t *) &irn->attr;
 494                         return attr->reg_data[-pos - 1].reg;
 495                 }
 496         }
 497
 498         return NULL;
 499 }
 500
 501 arch_irn_class_t be_node_classify(const arch_irn_ops_t *_self, const ir_node *irn)
 502 {
 503         const be_node_factory_t *factory = container_of(_self, const be_node_factory_t, irn_ops);
 504
 505         be_op_t *bo;
 506         int idx;
 507
 508         idx = redir_proj(&irn, 0);
 509         bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
 510
 511         switch(bo->kind) {
 512 #define XXX(a) case node_kind_ ## a: return arch_irn_class_ ## a;
 513                 XXX(spill)
 514                 XXX(reload)
 515                 XXX(perm)
 516                 XXX(copy)
 517 #undef XXX
 518                 default:
 519                 return 0;
 520         }
 521
 522         return 0;
 523 }
 524
 525 arch_irn_class_t be_node_get_flags(const arch_irn_ops_t *_self, const ir_node *irn)
 526 {
 527         return 0;
 528 }
 529
 530 static const arch_irn_ops_t *
 531 be_node_get_irn_ops(const arch_irn_handler_t *_self, const ir_node *irn)
 532 {
 533         be_op_t *bo;
 534         const be_node_factory_t *factory =
 535                 container_of(_self, const be_node_factory_t, handler);
 536
 537         redir_proj(&irn, 0);
 538         bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
 539
 540         return bo ? &factory->irn_ops : NULL;
 541 }
 542
 543 const arch_irn_handler_t *be_node_get_irn_handler(const be_node_factory_t *f)
 544 {
 545         return &f->handler;
 546 }
 547
 548 int be_is_Spill(const ir_node *irn)
 549 {
 550         return is_be_kind(irn, node_kind_spill);
 551 }
 552
 553 int be_is_Reload(const ir_node *irn)
 554 {
 555         return is_be_kind(irn, node_kind_reload);
 556 }
 557
 558 int be_is_Copy(const ir_node *irn)
 559 {
 560         return is_be_kind(irn, node_kind_copy);
 561 }
 562
 563 int be_is_Perm(const ir_node *irn)
 564 {
 565         return is_be_kind(irn, node_kind_perm);
 566 }
 567
 568
 569 be_node_factory_t *be_node_factory_init(be_node_factory_t *factory, const arch_isa_t *isa)
 570 {
 571         int i, j, n;
 572
 573         factory->ops = new_set(cmp_op_map, 64);
 574         factory->irn_op_map = pmap_create();
 575         obstack_init(&factory->obst);
 576
 577         factory->handler.get_irn_ops = be_node_get_irn_ops;
 578
 579         factory->irn_ops.get_irn_reg_req = be_node_get_irn_reg_req;
 580         factory->irn_ops.set_irn_reg     = be_node_set_irn_reg;
 581         factory->irn_ops.get_irn_reg     = be_node_get_irn_reg;
 582         factory->irn_ops.classify        = be_node_classify;
 583         factory->irn_ops.get_flags       = be_node_get_flags;
 584
 585         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
 586                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
 587                 be_op_t *ent;
 588
 589                 ent = get_op(factory, cls, node_kind_spill);
 590                 ent->op = new_ir_op(get_next_ir_opcode(), "Spill", op_pin_state_pinned,
 591                                 0, oparity_unary, 0, sizeof(be_spill_attr_t), &be_node_ops);
 592                 ent->n_pos = ARRSIZE(templ_pos_Spill);
 593                 ent->pos = templ_pos_Spill;
 594                 pmap_insert(factory->irn_op_map, ent->op, ent);
 595
 596                 ent = get_op(factory, cls, node_kind_reload);
 597                 ent->op = new_ir_op(get_next_ir_opcode(), "Reload", op_pin_state_pinned, 0,
 598                                 oparity_unary, 0, sizeof(be_node_attr_t), &be_node_ops);
 599                 ent->n_pos = ARRSIZE(templ_pos_Reload);
 600                 ent->pos = templ_pos_Reload;
 601                 pmap_insert(factory->irn_op_map, ent->op, ent);
 602
 603                 ent = get_op(factory, cls, node_kind_copy);
 604                 ent->op = new_ir_op(get_next_ir_opcode(), "Copy", op_pin_state_pinned, 0,
 605                                 oparity_unary, 0, sizeof(be_node_attr_t), &be_node_ops);
 606                 ent->n_pos = ARRSIZE(templ_pos_Copy);
 607                 ent->pos = templ_pos_Copy;
 608                 pmap_insert(factory->irn_op_map, ent->op, ent);
 609
 610                 ent = get_op(factory, cls, node_kind_perm);
 611                 ent->op = new_ir_op(get_next_ir_opcode(), "Perm", op_pin_state_pinned, 0,
 612                                 oparity_variable, 0,
 613                                 sizeof(be_node_attr_t)
 614                                 + sizeof(be_reg_data_t) * cls->n_regs, &be_node_ops);
 615                 ent->n_pos = 2 * cls->n_regs;
 616                 ent->pos = obstack_alloc(&factory->obst, sizeof(ent->pos[0]) * ent->n_pos);
 617                 for(j = 0; j < ent->n_pos; j += 2) {
 618                         int k = j / 2;
 619                         ent->pos[j] = k;
 620                         ent->pos[j + 1] = -(k + 1);
 621                 }
 622                 pmap_insert(factory->irn_op_map, ent->op, ent);
 623
 624         }
 625
 626         return factory;
 627 }
 628
 629 static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason)
 630 {
 631         be_node_attr_t *at = (be_node_attr_t *) &irn->attr;
 632         const be_op_t *bo;
 633         int i;
 634
 635         assert(is_be_node(irn));
 636         bo = at->op;
 637
 638         switch(reason) {
 639                 case dump_node_opcode_txt:
 640                         fprintf(f, get_op_name(bo->op));
 641                         break;
 642                 case dump_node_mode_txt:
 643                         fprintf(f, get_mode_name(get_irn_mode(irn)));
 644                         break;
 645                 case dump_node_nodeattr_txt:
 646                         fprintf(f, "%s ", bo->cls->name);
 647                         break;
 648                 case dump_node_info_txt:
 649                         for(i = 0; i < at->n_regs; ++i) {
 650                                 const arch_register_t *reg = at->reg_data[i].reg;
 651                                 fprintf(f, "reg #%d: %s\n", i, reg ? reg->name : "n/a");
 652                         }
 653
 654                         if(bo->kind == node_kind_spill) {
 655                                 be_spill_attr_t *a = (be_spill_attr_t *) at;
 656                                 ir_fprintf(f, "spill context: %+F\n", a->spill_ctx);
 657                                 ir_fprintf(f, "spill offset: %u\n", a->offset);
 658                         }
 659                         break;
 660         }
 661
 662         return 0;
 663 }
 664
 665 ir_node *insert_Perm_after(const be_main_env_t *env,
 666                                                          const arch_register_class_t *cls,
 667                                                          dom_front_info_t *dom_front,
 668                                                          ir_node *pos)
 669 {
 670         const arch_env_t *arch_env  = env->arch_env;
 671         ir_node *bl                 = is_Block(pos) ? pos : get_nodes_block(pos);
 672         ir_graph *irg               = get_irn_irg(bl);
 673         pset *live                  = pset_new_ptr_default();
 674         firm_dbg_module_t *dbg      = firm_dbg_register("be.node");
 675
 676         irn_live_t *li;
 677         ir_node *curr, *irn, *perm, **nodes;
 678         int i, n;
 679
 680         DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
 681
 682
 683         live_foreach(bl, li) {
 684                 ir_node *irn = (ir_node *) li->irn;
 685                 if(live_is_end(li) && arch_irn_has_reg_class(arch_env, irn, -1, cls))
 686                         pset_insert_ptr(live, irn);
 687         }
 688
 689         sched_foreach_reverse(bl, irn) {
 690                 ir_node *x;
 691
 692         /*
 693          * If we encounter the node we want to insert the Perm after,
 694          * exit immediately, so that this node is still live
 695          */
 696                 if(irn == pos)
 697                         break;
 698
 699                 DBG((dbg, LEVEL_1, "%+F\n", irn));
 700                 for(x = pset_first(live); x; x = pset_next(live))
 701                         DBG((dbg, LEVEL_1, "\tlive: %+F\n", x));
 702
 703                 if(arch_irn_has_reg_class(arch_env, irn, -1, cls))
 704                         pset_remove_ptr(live, irn);
 705
 706                 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 707                         ir_node *op = get_irn_n(irn, i);
 708
 709                         if(arch_irn_has_reg_class(arch_env, op, -1, cls))
 710                                 pset_insert_ptr(live, op);
 711                 }
 712         }
 713
 714         n = pset_count(live);
 715         nodes = malloc(n * sizeof(nodes[0]));
 716
 717         DBG((dbg, LEVEL_1, "live:\n"));
 718         for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
 719                 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
 720                 nodes[i] = irn;
 721         }
 722
 723         perm = new_Perm(env->node_factory, cls, irg, bl, n, nodes);
 724         sched_add_after(pos, perm);
 725         free(nodes);
 726
 727         curr = perm;
 728         for(i = 0; i < n; ++i) {
 729                 ir_node *copies[1];
 730                 ir_node *perm_op = get_irn_n(perm, i);
 731                 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
 732
 733                 ir_mode *mode = get_irn_mode(perm_op);
 734                 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
 735                 arch_set_irn_register(arch_env, proj, reg);
 736
 737                 sched_add_after(curr, proj);
 738                 curr = proj;
 739
 740                 copies[0] = proj;
 741                 be_introduce_copies(dom_front, perm_op, array_size(copies), copies);
 742         }
 743         return perm;
 744 }