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 provides Perm, Copy, Spill and Reload nodes.
   9  *
  10  * Copyright (C) 2005-2006 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 #include "offset.h"
  27 #include "bitfiddle.h"
  28
  29 #include "irop_t.h"
  30 #include "irmode_t.h"
  31 #include "irnode_t.h"
  32 #include "ircons_t.h"
  33 #include "irprintf.h"
  34 #include "irgwalk.h"
  35 #include "iropt_t.h"
  36
  37 #include "be_t.h"
  38 #include "belive_t.h"
  39 #include "besched_t.h"
  40 #include "benode_t.h"
  41
  42 #include "beirgmod.h"
  43
  44 #define OUT_POS(x) (-((x) + 1))
  45
  46 /* Sometimes we want to put const nodes into get_irn_generic_attr ... */
  47 #define get_irn_attr(irn) get_irn_generic_attr((ir_node *) (irn))
  48
  49 static unsigned be_node_tag = FOURCC('B', 'E', 'N', 'O');
  50
  51 typedef enum {
  52         be_req_kind_old_limited,
  53         be_req_kind_negate_old_limited,
  54         be_req_kind_single_reg
  55 } be_req_kind_t;
  56
  57 typedef struct {
  58         arch_register_req_t req;
  59         be_req_kind_t       kind;
  60         arch_irn_flags_t    flags;
  61         union {
  62                 struct {
  63                         void (*old_limited)(void *ptr, bitset_t *bs);
  64                         void *old_limited_env;
  65                 } old_limited;
  66
  67                 const arch_register_t *single_reg;
  68         } x;
  69 } be_req_t;
  70
  71 typedef struct {
  72         const arch_register_t *reg;
  73         be_req_t              req;
  74         be_req_t              in_req;
  75 } be_reg_data_t;
  76
  77 /** The generic be nodes attribute type. */
  78 typedef struct {
  79         int                   max_reg_data;
  80         be_reg_data_t         *reg_data;
  81 } be_node_attr_t;
  82
  83 /** The be_Return nodes attribute type. */
  84 typedef struct {
  85         be_node_attr_t node_attr;
  86         int            num_ret_vals;  /**< number of return values */
  87 } be_return_attr_t;
  88
  89 /** The be_Stack attribute type. */
  90 typedef struct {
  91         be_node_attr_t node_attr;
  92         int offset;           /**< The offset by which the stack shall be expanded/shrinked. */
  93 } be_stack_attr_t;
  94
  95 /** The be_Frame attribute type. */
  96 typedef struct {
  97         be_node_attr_t node_attr;
  98         ir_entity *ent;
  99         int offset;
 100 } be_frame_attr_t;
 101
 102 /** The be_Call attribute type. */
 103 typedef struct {
 104         be_node_attr_t node_attr;
 105         ir_entity *ent;      /**< The called entity if this is a static call. */
 106         ir_type *call_tp;    /**< The call type, copied from the original Call node. */
 107 } be_call_attr_t;
 108
 109 typedef struct {
 110         be_node_attr_t node_attr;
 111         ir_entity **in_entities;
 112         ir_entity **out_entities;
 113 } be_memperm_attr_t;
 114
 115 ir_op *op_be_Spill;
 116 ir_op *op_be_Reload;
 117 ir_op *op_be_Perm;
 118 ir_op *op_be_MemPerm;
 119 ir_op *op_be_Copy;
 120 ir_op *op_be_Keep;
 121 ir_op *op_be_CopyKeep;
 122 ir_op *op_be_Call;
 123 ir_op *op_be_Return;
 124 ir_op *op_be_IncSP;
 125 ir_op *op_be_AddSP;
 126 ir_op *op_be_SubSP;
 127 ir_op *op_be_SetSP;
 128 ir_op *op_be_RegParams;
 129 ir_op *op_be_StackParam;
 130 ir_op *op_be_FrameAddr;
 131 ir_op *op_be_FrameLoad;
 132 ir_op *op_be_FrameStore;
 133 ir_op *op_be_Barrier;
 134
 135 static int beo_base = -1;
 136
 137 static const ir_op_ops be_node_op_ops;
 138
 139 #define N   irop_flag_none
 140 #define L   irop_flag_labeled
 141 #define C   irop_flag_commutative
 142 #define X   irop_flag_cfopcode
 143 #define I   irop_flag_ip_cfopcode
 144 #define F   irop_flag_fragile
 145 #define Y   irop_flag_forking
 146 #define H   irop_flag_highlevel
 147 #define c   irop_flag_constlike
 148 #define K   irop_flag_keep
 149 #define M   irop_flag_machine
 150
 151
 152 /**
 153  * Compare two node attributes.
 154  *
 155  * @return zero if both attributes are identically
 156  */
 157 static int cmp_node_attr(be_node_attr_t *a, be_node_attr_t *b) {
 158         if (a->max_reg_data == b->max_reg_data) {
 159                 int i;
 160
 161                 for (i = 0; i < a->max_reg_data; ++i) {
 162                         if (a->reg_data[i].reg    != b->reg_data[i].reg ||
 163                             memcmp(&a->reg_data[i].in_req, &b->reg_data[i].in_req, sizeof(b->reg_data[i].in_req)) ||
 164                             memcmp(&a->reg_data[i].req,    &b->reg_data[i].req,    sizeof(a->reg_data[i].req)))
 165                                 return 1;
 166                 }
 167                 return 0;
 168         }
 169         return 1;
 170 }
 171
 172 /**
 173  * Compare the attributes of two FrameAddr nodes.
 174  *
 175  * @return zero if both attributes are identically
 176  */
 177 static int FrameAddr_cmp_attr(ir_node *a, ir_node *b) {
 178         be_frame_attr_t *a_attr = get_irn_attr(a);
 179         be_frame_attr_t *b_attr = get_irn_attr(b);
 180
 181         if (a_attr->ent == b_attr->ent && a_attr->offset == b_attr->offset)
 182                 return cmp_node_attr(&a_attr->node_attr, &b_attr->node_attr);
 183         return 1;
 184 }
 185
 186 void be_node_init(void) {
 187         static int inited = 0;
 188
 189         if(inited)
 190                 return;
 191
 192         inited = 1;
 193
 194         /* Acquire all needed opcodes. */
 195         beo_base = get_next_ir_opcodes(beo_Last - 1);
 196
 197         op_be_Spill      = new_ir_op(beo_base + beo_Spill,      "be_Spill",      op_pin_state_mem_pinned, N, oparity_unary,    0, sizeof(be_frame_attr_t),   &be_node_op_ops);
 198         op_be_Reload     = new_ir_op(beo_base + beo_Reload,     "be_Reload",     op_pin_state_mem_pinned, N, oparity_zero,     0, sizeof(be_frame_attr_t),   &be_node_op_ops);
 199         op_be_Perm       = new_ir_op(beo_base + beo_Perm,       "be_Perm",       op_pin_state_pinned,     N, oparity_variable, 0, sizeof(be_node_attr_t),    &be_node_op_ops);
 200         op_be_MemPerm    = new_ir_op(beo_base + beo_MemPerm,    "be_MemPerm",    op_pin_state_mem_pinned, N, oparity_variable, 0, sizeof(be_memperm_attr_t), &be_node_op_ops);
 201         op_be_Copy       = new_ir_op(beo_base + beo_Copy,       "be_Copy",       op_pin_state_floats,     N, oparity_unary,    0, sizeof(be_node_attr_t),    &be_node_op_ops);
 202         op_be_Keep       = new_ir_op(beo_base + beo_Keep,       "be_Keep",       op_pin_state_pinned,     K, oparity_variable, 0, sizeof(be_node_attr_t),    &be_node_op_ops);
 203         op_be_CopyKeep   = new_ir_op(beo_base + beo_CopyKeep,   "be_CopyKeep",   op_pin_state_pinned,     K, oparity_variable, 0, sizeof(be_node_attr_t),    &be_node_op_ops);
 204         op_be_Call       = new_ir_op(beo_base + beo_Call,       "be_Call",       op_pin_state_pinned,     F, oparity_variable, 0, sizeof(be_call_attr_t),    &be_node_op_ops);
 205         op_be_Return     = new_ir_op(beo_base + beo_Return,     "be_Return",     op_pin_state_pinned,     X, oparity_variable, 0, sizeof(be_return_attr_t),  &be_node_op_ops);
 206         op_be_AddSP      = new_ir_op(beo_base + beo_AddSP,      "be_AddSP",      op_pin_state_pinned,     N, oparity_unary,    0, sizeof(be_node_attr_t),    &be_node_op_ops);
 207         op_be_SubSP      = new_ir_op(beo_base + beo_SubSP,      "be_SubSP",      op_pin_state_pinned,     N, oparity_unary,    0, sizeof(be_node_attr_t),    &be_node_op_ops);
 208         op_be_SetSP      = new_ir_op(beo_base + beo_SetSP,      "be_SetSP",      op_pin_state_pinned,     N, oparity_binary,   0, sizeof(be_stack_attr_t),   &be_node_op_ops);
 209         op_be_IncSP      = new_ir_op(beo_base + beo_IncSP,      "be_IncSP",      op_pin_state_pinned,     N, oparity_binary,   0, sizeof(be_stack_attr_t),   &be_node_op_ops);
 210         op_be_RegParams  = new_ir_op(beo_base + beo_RegParams,  "be_RegParams",  op_pin_state_pinned,     N, oparity_zero,     0, sizeof(be_node_attr_t),    &be_node_op_ops);
 211         op_be_StackParam = new_ir_op(beo_base + beo_StackParam, "be_StackParam", op_pin_state_pinned,     N, oparity_unary,    0, sizeof(be_frame_attr_t),   &be_node_op_ops);
 212         op_be_FrameAddr  = new_ir_op(beo_base + beo_FrameAddr,  "be_FrameAddr",  op_pin_state_pinned,     N, oparity_unary,    0, sizeof(be_frame_attr_t),   &be_node_op_ops);
 213         op_be_FrameLoad  = new_ir_op(beo_base + beo_FrameLoad,  "be_FrameLoad",  op_pin_state_pinned,     N, oparity_any,      0, sizeof(be_frame_attr_t),   &be_node_op_ops);
 214         op_be_FrameStore = new_ir_op(beo_base + beo_FrameStore, "be_FrameStore", op_pin_state_pinned,     N, oparity_any,      0, sizeof(be_frame_attr_t),   &be_node_op_ops);
 215         op_be_Barrier    = new_ir_op(beo_base + beo_Barrier,    "be_Barrier",    op_pin_state_pinned,     N, oparity_any,      0, sizeof(be_node_attr_t),    &be_node_op_ops);
 216
 217         set_op_tag(op_be_Spill,      &be_node_tag);
 218         set_op_tag(op_be_Reload,     &be_node_tag);
 219         set_op_tag(op_be_Perm,       &be_node_tag);
 220         set_op_tag(op_be_MemPerm,    &be_node_tag);
 221         set_op_tag(op_be_Copy,       &be_node_tag);
 222         set_op_tag(op_be_Keep,       &be_node_tag);
 223         set_op_tag(op_be_CopyKeep,   &be_node_tag);
 224         set_op_tag(op_be_Call,       &be_node_tag);
 225         set_op_tag(op_be_Return,     &be_node_tag);
 226         set_op_tag(op_be_AddSP,      &be_node_tag);
 227         set_op_tag(op_be_SubSP,      &be_node_tag);
 228         set_op_tag(op_be_SetSP,      &be_node_tag);
 229         set_op_tag(op_be_IncSP,      &be_node_tag);
 230         set_op_tag(op_be_RegParams,  &be_node_tag);
 231         set_op_tag(op_be_StackParam, &be_node_tag);
 232         set_op_tag(op_be_FrameLoad,  &be_node_tag);
 233         set_op_tag(op_be_FrameStore, &be_node_tag);
 234         set_op_tag(op_be_FrameAddr,  &be_node_tag);
 235         set_op_tag(op_be_Barrier,    &be_node_tag);
 236
 237         op_be_FrameAddr->ops.node_cmp_attr = FrameAddr_cmp_attr;
 238 }
 239
 240 /**
 241  * Initializes the generic attribute of all be nodes and return ir.
 242  */
 243 static void *init_node_attr(ir_node* irn, int max_reg_data)
 244 {
 245         ir_graph *irg     = get_irn_irg(irn);
 246         be_node_attr_t *a = get_irn_attr(irn);
 247
 248         memset(a, 0, sizeof(get_op_attr_size(get_irn_op(irn))));
 249         a->max_reg_data = max_reg_data;
 250         a->reg_data     = NULL;
 251
 252         if(max_reg_data > 0) {
 253                 int i;
 254
 255                 a->reg_data = NEW_ARR_D(be_reg_data_t, get_irg_obstack(irg), max_reg_data);
 256                 memset(a->reg_data, 0, max_reg_data * sizeof(a->reg_data[0]));
 257                 for(i = 0; i < max_reg_data; ++i) {
 258                         a->reg_data[i].req.req.cls  = NULL;
 259                         a->reg_data[i].req.req.type = arch_register_req_type_none;
 260                 }
 261         }
 262
 263         return a;
 264 }
 265
 266 int is_be_node(const ir_node *irn)
 267 {
 268         return get_op_tag(get_irn_op(irn)) == &be_node_tag;
 269 }
 270
 271 be_opcode_t be_get_irn_opcode(const ir_node *irn)
 272 {
 273         return is_be_node(irn) ? get_irn_opcode(irn) - beo_base : beo_NoBeOp;
 274 }
 275
 276 /**
 277  * Skip Proj nodes and return their Proj numbers.
 278  *
 279  * If *node is a Proj or Proj(Proj) node, skip it.
 280  *
 281  * @param node  points to the node to be skipped
 282  *
 283  * @return 0 if *node was no Proj node, its Proj number else.
 284  */
 285 static int redir_proj(const ir_node **node)
 286 {
 287         const ir_node *n = *node;
 288
 289         if(is_Proj(n)) {
 290                 ir_node *irn;
 291
 292                 *node = irn = get_Proj_pred(n);
 293                 if(is_Proj(irn)) {
 294                         assert(get_irn_mode(irn) == mode_T);
 295                         *node = get_Proj_pred(irn);
 296                 }
 297                 return get_Proj_proj(n);
 298         }
 299
 300         return 0;
 301 }
 302
 303 static be_node_attr_t *retrieve_irn_attr(const ir_node *irn, int *the_pos)
 304 {
 305         int dummy;
 306         be_node_attr_t *res = NULL;
 307         int *pos = the_pos ? the_pos : &dummy;
 308
 309         *pos = -1;
 310         if(is_Proj(irn)) {
 311                 ir_node *pred = get_Proj_pred(irn);
 312                 int p         = get_Proj_proj(irn);
 313
 314                 if(is_be_node(pred)) {
 315                         assert(get_irn_mode(pred) == mode_T);
 316                         *pos = p;
 317                         res = get_irn_attr(pred);
 318                         assert(p >= 0 && p < res->max_reg_data && "illegal proj number");
 319                 }
 320         }
 321
 322         else if(is_be_node(irn) && get_irn_mode(irn) != mode_T) {
 323                 be_node_attr_t *a = get_irn_attr(irn);
 324                 if(a->max_reg_data > 0) {
 325                         res  = a;
 326                         *pos = 0;
 327                 }
 328         }
 329
 330         return res;
 331 }
 332
 333 static be_reg_data_t *retrieve_reg_data(const ir_node *irn)
 334 {
 335         int pos;
 336         be_node_attr_t *a = retrieve_irn_attr(irn, &pos);
 337         return a ? &a->reg_data[pos] : NULL;
 338 }
 339
 340 static void
 341 be_node_set_irn_reg(const void *_self, ir_node *irn, const arch_register_t *reg)
 342 {
 343         be_reg_data_t *r = retrieve_reg_data(irn);
 344
 345         if(r)
 346                 r->reg = reg;
 347 }
 348
 349
 350 ir_node *be_new_Spill(const arch_register_class_t *cls, const arch_register_class_t *cls_frame,
 351         ir_graph *irg, ir_node *bl, ir_node *frame, ir_node *to_spill)
 352 {
 353         be_frame_attr_t *a;
 354         ir_node         *in[2];
 355         ir_node         *res;
 356
 357         in[0]     = frame;
 358         in[1]     = to_spill;
 359         res       = new_ir_node(NULL, irg, bl, op_be_Spill, mode_M, 2, in);
 360         a         = init_node_attr(res, 2);
 361         a->ent    = NULL;
 362         a->offset = 0;
 363
 364         be_node_set_reg_class(res, be_pos_Spill_frame, cls_frame);
 365         be_node_set_reg_class(res, be_pos_Spill_val, cls);
 366         return res;
 367 }
 368
 369 ir_node *be_new_Reload(const arch_register_class_t *cls, const arch_register_class_t *cls_frame,
 370         ir_graph *irg, ir_node *bl, ir_node *frame, ir_node *mem, ir_mode *mode)
 371 {
 372         ir_node *in[2];
 373         ir_node *res;
 374
 375         in[0] = frame;
 376         in[1] = mem;
 377         res   = new_ir_node(NULL, irg, bl, op_be_Reload, mode, 2, in);
 378
 379         init_node_attr(res, 2);
 380         be_node_set_reg_class(res, -1, cls);
 381         be_node_set_reg_class(res, be_pos_Reload_frame, cls_frame);
 382         be_node_set_flags(res, -1, arch_irn_flags_rematerializable);
 383         return res;
 384 }
 385
 386 ir_node *be_get_Reload_mem(const ir_node *irn)
 387 {
 388         assert(be_is_Reload(irn));
 389         return get_irn_n(irn, be_pos_Reload_mem);
 390 }
 391
 392 ir_node *be_get_Reload_frame(const ir_node *irn)
 393 {
 394         assert(be_is_Reload(irn));
 395         return get_irn_n(irn, be_pos_Reload_frame);
 396 }
 397
 398 ir_node *be_get_Spill_val(const ir_node *irn)
 399 {
 400         assert(be_is_Spill(irn));
 401         return get_irn_n(irn, be_pos_Spill_val);
 402 }
 403 ir_node *be_get_Spill_frame(const ir_node *irn)
 404 {
 405         assert(be_is_Spill(irn));
 406         return get_irn_n(irn, be_pos_Spill_frame);
 407 }
 408
 409 ir_node *be_new_Perm(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, int n, ir_node *in[])
 410 {
 411         int i;
 412         ir_node *irn = new_ir_node(NULL, irg, bl, op_be_Perm, mode_T, n, in);
 413         init_node_attr(irn, n);
 414         for(i = 0; i < n; ++i) {
 415                 be_node_set_reg_class(irn, i, cls);
 416                 be_node_set_reg_class(irn, OUT_POS(i), cls);
 417         }
 418
 419         return irn;
 420 }
 421
 422 ir_node *be_new_MemPerm(const arch_env_t *arch_env, ir_graph *irg, ir_node *bl, int n, ir_node *in[])
 423 {
 424         int i;
 425         ir_node *frame = get_irg_frame(irg);
 426         const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
 427         ir_node *irn;
 428         const arch_register_t *sp = arch_env->isa->sp;
 429         be_memperm_attr_t *attr;
 430         ir_node **real_in;
 431
 432         real_in = alloca((n+1) * sizeof(real_in[0]));
 433         real_in[0] = frame;
 434         memcpy(&real_in[1], in, n * sizeof(real_in[0]));
 435
 436         irn =  new_ir_node(NULL, irg, bl, op_be_MemPerm, mode_T, n+1, real_in);
 437
 438         init_node_attr(irn, n + 1);
 439         be_node_set_reg_class(irn, 0, sp->reg_class);
 440         for(i = 0; i < n; ++i) {
 441                 be_node_set_reg_class(irn, i + 1, cls_frame);
 442                 be_node_set_reg_class(irn, OUT_POS(i), cls_frame);
 443         }
 444
 445         attr = get_irn_attr(irn);
 446
 447         attr->in_entities = obstack_alloc(irg->obst, n * sizeof(attr->in_entities[0]));
 448         memset(attr->in_entities, 0, n * sizeof(attr->in_entities[0]));
 449         attr->out_entities = obstack_alloc(irg->obst, n*sizeof(attr->out_entities[0]));
 450         memset(attr->out_entities, 0, n*sizeof(attr->out_entities[0]));
 451
 452         return irn;
 453 }
 454
 455
 456 ir_node *be_new_Copy(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_node *op)
 457 {
 458         ir_node *in[1];
 459         ir_node *res;
 460
 461         in[0] = op;
 462         res   = new_ir_node(NULL, irg, bl, op_be_Copy, get_irn_mode(op), 1, in);
 463         init_node_attr(res, 1);
 464         be_node_set_reg_class(res, 0, cls);
 465         be_node_set_reg_class(res, OUT_POS(0), cls);
 466         return res;
 467 }
 468
 469 ir_node *be_get_Copy_op(const ir_node *cpy) {
 470         return get_irn_n(cpy, be_pos_Copy_op);
 471 }
 472
 473 void be_set_Copy_op(ir_node *cpy, ir_node *op) {
 474         set_irn_n(cpy, be_pos_Copy_op, op);
 475 }
 476
 477 ir_node *be_new_Keep(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, int n, ir_node *in[])
 478 {
 479         int i;
 480         ir_node *irn;
 481
 482         irn = new_ir_node(NULL, irg, bl, op_be_Keep, mode_ANY, n, in);
 483         init_node_attr(irn, n);
 484         for(i = 0; i < n; ++i) {
 485                 be_node_set_reg_class(irn, i, cls);
 486         }
 487         keep_alive(irn);
 488         return irn;
 489 }
 490
 491 ir_node *be_new_Call(dbg_info *dbg, ir_graph *irg, ir_node *bl, ir_node *mem, ir_node *sp, ir_node *ptr,
 492                      int n_outs, int n, ir_node *in[], ir_type *call_tp)
 493 {
 494         be_call_attr_t *a;
 495         int real_n = be_pos_Call_first_arg + n;
 496         ir_node *irn;
 497         ir_node **real_in;
 498
 499         NEW_ARR_A(ir_node *, real_in, real_n);
 500         real_in[be_pos_Call_mem] = mem;
 501         real_in[be_pos_Call_sp]  = sp;
 502         real_in[be_pos_Call_ptr] = ptr;
 503         memcpy(&real_in[be_pos_Call_first_arg], in, n * sizeof(in[0]));
 504
 505         irn = new_ir_node(dbg, irg, bl, op_be_Call, mode_T, real_n, real_in);
 506         a = init_node_attr(irn, (n_outs > real_n ? n_outs : real_n));
 507         a->ent     = NULL;
 508         a->call_tp = call_tp;
 509         return irn;
 510 }
 511
 512 /* Gets the call entity or NULL if this is no static call. */
 513 ir_entity *be_Call_get_entity(const ir_node *call) {
 514         be_call_attr_t *a = get_irn_attr(call);
 515         assert(be_is_Call(call));
 516         return a->ent;
 517 }
 518
 519 /* Sets the call entity. */
 520 void be_Call_set_entity(ir_node *call, ir_entity *ent) {
 521         be_call_attr_t *a = get_irn_attr(call);
 522         assert(be_is_Call(call));
 523         a->ent = ent;
 524 }
 525
 526 /* Gets the call type. */
 527 ir_type *be_Call_get_type(ir_node *call) {
 528         be_call_attr_t *a = get_irn_attr(call);
 529         assert(be_is_Call(call));
 530         return a->call_tp;
 531 }
 532
 533 /* Sets the call type. */
 534 void be_Call_set_type(ir_node *call, ir_type *call_tp) {
 535         be_call_attr_t *a = get_irn_attr(call);
 536         assert(be_is_Call(call));
 537         a->call_tp = call_tp;
 538 }
 539
 540 /* Construct a new be_Return. */
 541 ir_node *be_new_Return(dbg_info *dbg, ir_graph *irg, ir_node *bl, int n_res, int n, ir_node *in[])
 542 {
 543         be_return_attr_t *a;
 544         ir_node *irn = new_ir_node(dbg, irg, bl, op_be_Return, mode_X, n, in);
 545         init_node_attr(irn, n);
 546         a = get_irn_attr(irn);
 547         a->num_ret_vals = n_res;
 548
 549         return irn;
 550 }
 551
 552 /* Returns the number of real returns values */
 553 int be_Return_get_n_rets(ir_node *ret)
 554 {
 555         be_return_attr_t *a = get_irn_attr(ret);
 556         return a->num_ret_vals;
 557 }
 558
 559 ir_node *be_new_IncSP(const arch_register_t *sp, ir_graph *irg, ir_node *bl, ir_node *old_sp, int offset)
 560 {
 561         be_stack_attr_t *a;
 562         ir_node *irn;
 563         ir_node *in[1];
 564
 565         in[0]     = old_sp;
 566         irn       = new_ir_node(NULL, irg, bl, op_be_IncSP, sp->reg_class->mode, sizeof(in) / sizeof(in[0]), in);
 567         a         = init_node_attr(irn, 1);
 568         a->offset = offset;
 569
 570         be_node_set_flags(irn, -1, arch_irn_flags_ignore | arch_irn_flags_modify_sp);
 571
 572         /* Set output constraint to stack register. */
 573         be_node_set_reg_class(irn, 0, sp->reg_class);
 574         be_set_constr_single_reg(irn, BE_OUT_POS(0), sp);
 575         be_node_set_irn_reg(NULL, irn, sp);
 576
 577         return irn;
 578 }
 579
 580 ir_node *be_new_AddSP(const arch_register_t *sp, ir_graph *irg, ir_node *bl, ir_node *old_sp, ir_node *sz)
 581 {
 582         be_node_attr_t *a;
 583         ir_node *irn;
 584         ir_node *in[be_pos_AddSP_last];
 585
 586         in[be_pos_AddSP_old_sp] = old_sp;
 587         in[be_pos_AddSP_size]   = sz;
 588
 589         irn = new_ir_node(NULL, irg, bl, op_be_AddSP, mode_T, be_pos_AddSP_last, in);
 590         a   = init_node_attr(irn, be_pos_AddSP_last);
 591
 592         be_node_set_flags(irn, OUT_POS(pn_be_AddSP_res), arch_irn_flags_ignore | arch_irn_flags_modify_sp);
 593
 594         /* Set output constraint to stack register. */
 595         be_set_constr_single_reg(irn, be_pos_AddSP_old_sp, sp);
 596         be_node_set_reg_class(irn, be_pos_AddSP_size, arch_register_get_class(sp));
 597         be_set_constr_single_reg(irn, OUT_POS(pn_be_AddSP_res), sp);
 598         a->reg_data[pn_be_AddSP_res].reg = sp;
 599
 600         return irn;
 601 }
 602
 603 ir_node *be_new_SubSP(const arch_register_t *sp, ir_graph *irg, ir_node *bl, ir_node *old_sp, ir_node *sz)
 604 {
 605         be_node_attr_t *a;
 606         ir_node *irn;
 607         ir_node *in[be_pos_SubSP_last];
 608
 609         in[be_pos_SubSP_old_sp] = old_sp;
 610         in[be_pos_SubSP_size]   = sz;
 611
 612         irn = new_ir_node(NULL, irg, bl, op_be_SubSP, mode_T, be_pos_SubSP_last, in);
 613         a   = init_node_attr(irn, be_pos_SubSP_last);
 614
 615         be_node_set_flags(irn, OUT_POS(pn_be_SubSP_res), arch_irn_flags_ignore | arch_irn_flags_modify_sp);
 616
 617         /* Set output constraint to stack register. */
 618         be_set_constr_single_reg(irn, be_pos_SubSP_old_sp, sp);
 619         be_node_set_reg_class(irn, be_pos_SubSP_size, arch_register_get_class(sp));
 620         be_set_constr_single_reg(irn, OUT_POS(pn_be_SubSP_res), sp);
 621         a->reg_data[pn_be_SubSP_res].reg = sp;
 622
 623         return irn;
 624 }
 625
 626 ir_node *be_new_SetSP(const arch_register_t *sp, ir_graph *irg, ir_node *bl, ir_node *old_sp, ir_node *op, ir_node *mem)
 627 {
 628         be_node_attr_t *a;
 629         ir_node *irn;
 630         ir_node *in[3];
 631
 632         in[0]    = mem;
 633         in[1]    = old_sp;
 634         in[2]    = op;
 635         irn      = new_ir_node(NULL, irg, bl, op_be_SetSP, get_irn_mode(old_sp), 3, in);
 636         a        = init_node_attr(irn, 3);
 637
 638         be_node_set_flags(irn, OUT_POS(0), arch_irn_flags_ignore | arch_irn_flags_modify_sp);
 639
 640         /* Set output constraint to stack register. */
 641         be_set_constr_single_reg(irn, OUT_POS(0), sp);
 642         be_node_set_reg_class(irn, be_pos_AddSP_size, sp->reg_class);
 643         be_node_set_reg_class(irn, be_pos_AddSP_old_sp, sp->reg_class);
 644
 645         return irn;
 646 }
 647
 648 ir_node *be_new_StackParam(const arch_register_class_t *cls, const arch_register_class_t *cls_frame, ir_graph *irg, ir_node *bl, ir_mode *mode, ir_node *frame_pointer, ir_entity *ent)
 649 {
 650         be_frame_attr_t *a;
 651         ir_node *irn;
 652         ir_node *in[1];
 653
 654         in[0] = frame_pointer;
 655         irn = new_ir_node(NULL, irg, bl, op_be_StackParam, mode, 1, in);
 656         a = init_node_attr(irn, 1);
 657         a->ent = ent;
 658
 659         be_node_set_reg_class(irn, 0, cls_frame);
 660         be_node_set_reg_class(irn, OUT_POS(0), cls);
 661         return irn;
 662 }
 663
 664 ir_node *be_new_RegParams(ir_graph *irg, ir_node *bl, int n_outs)
 665 {
 666         ir_node *irn;
 667         ir_node *in[1];
 668
 669         irn = new_ir_node(NULL, irg, bl, op_be_RegParams, mode_T, 0, in);
 670         init_node_attr(irn, n_outs);
 671         return irn;
 672 }
 673
 674 ir_node *be_new_FrameLoad(const arch_register_class_t *cls_frame, const arch_register_class_t *cls_data,
 675                                                   ir_graph *irg, ir_node *bl, ir_node *mem, ir_node *frame, ir_entity *ent)
 676 {
 677         be_frame_attr_t *a;
 678         ir_node *irn;
 679         ir_node *in[2];
 680
 681         in[0]  = mem;
 682         in[1]  = frame;
 683         irn    = new_ir_node(NULL, irg, bl, op_be_FrameLoad, mode_T, 2, in);
 684         a      = init_node_attr(irn, 3);
 685         a->ent = ent;
 686         a->offset = 0;
 687         be_node_set_reg_class(irn, 1, cls_frame);
 688         be_node_set_reg_class(irn, OUT_POS(pn_Load_res), cls_data);
 689         return irn;
 690 }
 691
 692 ir_node *be_new_FrameStore(const arch_register_class_t *cls_frame, const arch_register_class_t *cls_data,
 693                                                    ir_graph *irg, ir_node *bl, ir_node *mem, ir_node *frame, ir_node *data, ir_entity *ent)
 694 {
 695         be_frame_attr_t *a;
 696         ir_node *irn;
 697         ir_node *in[3];
 698
 699         in[0]  = mem;
 700         in[1]  = frame;
 701         in[2]  = data;
 702         irn    = new_ir_node(NULL, irg, bl, op_be_FrameStore, mode_T, 3, in);
 703         a      = init_node_attr(irn, 3);
 704         a->ent = ent;
 705         a->offset = 0;
 706         be_node_set_reg_class(irn, 1, cls_frame);
 707         be_node_set_reg_class(irn, 2, cls_data);
 708         return irn;
 709 }
 710
 711 ir_node *be_new_FrameAddr(const arch_register_class_t *cls_frame, ir_graph *irg, ir_node *bl, ir_node *frame, ir_entity *ent)
 712 {
 713         be_frame_attr_t *a;
 714         ir_node *irn;
 715         ir_node *in[1];
 716
 717         in[0]  = frame;
 718         irn    = new_ir_node(NULL, irg, bl, op_be_FrameAddr, get_irn_mode(frame), 1, in);
 719         a      = init_node_attr(irn, 1);
 720         a->ent = ent;
 721         a->offset = 0;
 722         be_node_set_reg_class(irn, 0, cls_frame);
 723         be_node_set_reg_class(irn, OUT_POS(0), cls_frame);
 724
 725         return optimize_node(irn);
 726 }
 727
 728 ir_node *be_new_CopyKeep(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_node *src, int n, ir_node *in_keep[], ir_mode *mode)
 729 {
 730         ir_node *irn;
 731         ir_node **in = (ir_node **) alloca((n + 1) * sizeof(in[0]));
 732
 733         in[0] = src;
 734         memcpy(&in[1], in_keep, n * sizeof(in[0]));
 735         irn   = new_ir_node(NULL, irg, bl, op_be_CopyKeep, mode, n + 1, in);
 736         init_node_attr(irn, n + 1);
 737         be_node_set_reg_class(irn, OUT_POS(0), cls);
 738         be_node_set_reg_class(irn, 0, cls);
 739
 740         return irn;
 741 }
 742
 743 ir_node *be_new_CopyKeep_single(const arch_register_class_t *cls, ir_graph *irg, ir_node *bl, ir_node *src, ir_node *keep, ir_mode *mode)
 744 {
 745         ir_node *in[1];
 746
 747         in[0] = keep;
 748         return be_new_CopyKeep(cls, irg, bl, src, 1, in, mode);
 749 }
 750
 751 ir_node *be_get_CopyKeep_op(const ir_node *cpy) {
 752         return get_irn_n(cpy, be_pos_CopyKeep_op);
 753 }
 754
 755 void be_set_CopyKeep_op(ir_node *cpy, ir_node *op) {
 756         set_irn_n(cpy, be_pos_CopyKeep_op, op);
 757 }
 758
 759 ir_node *be_new_Barrier(ir_graph *irg, ir_node *bl, int n, ir_node *in[])
 760 {
 761         ir_node *irn;
 762
 763         irn = new_ir_node(NULL, irg, bl, op_be_Barrier, mode_T, n, in);
 764         init_node_attr(irn, n);
 765         return irn;
 766 }
 767
 768 int be_is_Spill         (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Spill          ; }
 769 int be_is_Reload        (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Reload         ; }
 770 int be_is_Copy          (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Copy           ; }
 771 int be_is_CopyKeep      (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_CopyKeep       ; }
 772 int be_is_Perm          (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Perm           ; }
 773 int be_is_MemPerm       (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_MemPerm        ; }
 774 int be_is_Keep          (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Keep           ; }
 775 int be_is_Call          (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Call           ; }
 776 int be_is_Return        (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Return         ; }
 777 int be_is_IncSP         (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_IncSP          ; }
 778 int be_is_SetSP         (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_SetSP          ; }
 779 int be_is_AddSP         (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_AddSP          ; }
 780 int be_is_RegParams     (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_RegParams      ; }
 781 int be_is_StackParam    (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_StackParam     ; }
 782 int be_is_FrameAddr     (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_FrameAddr      ; }
 783 int be_is_FrameLoad     (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_FrameLoad      ; }
 784 int be_is_FrameStore    (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_FrameStore     ; }
 785 int be_is_Barrier       (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Barrier        ; }
 786
 787 int be_has_frame_entity(const ir_node *irn)
 788 {
 789         switch(be_get_irn_opcode(irn)) {
 790         case beo_StackParam:
 791         case beo_Spill:
 792         case beo_Reload:
 793         case beo_FrameStore:
 794         case beo_FrameLoad:
 795         case beo_FrameAddr:
 796                 return 1;
 797         default:
 798                 return 0;
 799         }
 800 }
 801
 802 ir_entity *be_get_frame_entity(const ir_node *irn)
 803 {
 804         if (be_has_frame_entity(irn)) {
 805                 be_frame_attr_t *a = get_irn_attr(irn);
 806                 return a->ent;
 807         }
 808         return NULL;
 809 }
 810
 811 int be_get_frame_offset(const ir_node *irn)
 812 {
 813         assert(is_be_node(irn));
 814         if (be_has_frame_entity(irn)) {
 815                 be_frame_attr_t *a = get_irn_attr(irn);
 816                 return a->offset;
 817         }
 818         return 0;
 819 }
 820
 821 void be_set_MemPerm_in_entity(const ir_node *irn, int n, ir_entity *ent)
 822 {
 823         be_memperm_attr_t *attr = get_irn_attr(irn);
 824
 825         assert(be_is_MemPerm(irn));
 826         assert(n < be_get_MemPerm_entity_arity(irn));
 827
 828         attr->in_entities[n] = ent;
 829 }
 830
 831 ir_entity* be_get_MemPerm_in_entity(const ir_node* irn, int n)
 832 {
 833         be_memperm_attr_t *attr = get_irn_attr(irn);
 834
 835         assert(be_is_MemPerm(irn));
 836         assert(n < be_get_MemPerm_entity_arity(irn));
 837
 838         return attr->in_entities[n];
 839 }
 840
 841 void be_set_MemPerm_out_entity(const ir_node *irn, int n, ir_entity *ent)
 842 {
 843         be_memperm_attr_t *attr = get_irn_attr(irn);
 844
 845         assert(be_is_MemPerm(irn));
 846         assert(n < be_get_MemPerm_entity_arity(irn));
 847
 848         attr->out_entities[n] = ent;
 849 }
 850
 851 ir_entity* be_get_MemPerm_out_entity(const ir_node* irn, int n)
 852 {
 853         be_memperm_attr_t *attr = get_irn_attr(irn);
 854
 855         assert(be_is_MemPerm(irn));
 856         assert(n < be_get_MemPerm_entity_arity(irn));
 857
 858         return attr->out_entities[n];
 859 }
 860
 861 int be_get_MemPerm_entity_arity(const ir_node *irn)
 862 {
 863         return get_irn_arity(irn) - 1;
 864 }
 865
 866 static void be_limited(void *data, bitset_t *bs)
 867 {
 868         be_req_t *req = data;
 869
 870         switch(req->kind) {
 871         case be_req_kind_negate_old_limited:
 872         case be_req_kind_old_limited:
 873                 req->x.old_limited.old_limited(req->x.old_limited.old_limited_env, bs);
 874                 if(req->kind == be_req_kind_negate_old_limited)
 875                         bitset_flip_all(bs);
 876                 break;
 877         case be_req_kind_single_reg:
 878                 bitset_clear_all(bs);
 879                 bitset_set(bs, req->x.single_reg->index);
 880                 break;
 881         }
 882 }
 883
 884 static INLINE be_req_t *get_req(ir_node *irn, int pos)
 885 {
 886         int idx           = pos < 0 ? -(pos + 1) : pos;
 887         be_node_attr_t *a = get_irn_attr(irn);
 888         be_reg_data_t *rd = &a->reg_data[idx];
 889         be_req_t       *r = pos < 0 ? &rd->req : &rd->in_req;
 890
 891         assert(is_be_node(irn));
 892         assert(!(pos >= 0) || pos < get_irn_arity(irn));
 893         assert(!(pos < 0)  || -(pos + 1) <= a->max_reg_data);
 894
 895         return r;
 896 }
 897
 898 void be_set_constr_single_reg(ir_node *irn, int pos, const arch_register_t *reg)
 899 {
 900         be_req_t *r = get_req(irn, pos);
 901
 902         r->kind            = be_req_kind_single_reg;
 903         r->x.single_reg    = reg;
 904         r->req.limited     = be_limited;
 905         r->req.limited_env = r;
 906         r->req.type        = arch_register_req_type_limited;
 907         r->req.cls         = reg->reg_class;
 908 }
 909
 910 void be_set_constr_limited(ir_node *irn, int pos, const arch_register_req_t *req)
 911 {
 912         be_req_t *r = get_req(irn, pos);
 913
 914         assert(arch_register_req_is(req, limited));
 915
 916         r->kind            = be_req_kind_old_limited;
 917         r->req.limited     = be_limited;
 918         r->req.limited_env = r;
 919         r->req.type        = arch_register_req_type_limited;
 920         r->req.cls         = req->cls;
 921
 922         r->x.old_limited.old_limited     = req->limited;
 923         r->x.old_limited.old_limited_env = req->limited_env;
 924 }
 925
 926 void be_node_set_flags(ir_node *irn, int pos, arch_irn_flags_t flags)
 927 {
 928         be_req_t *r = get_req(irn, pos);
 929         r->flags = flags;
 930 }
 931
 932 void be_node_set_reg_class(ir_node *irn, int pos, const arch_register_class_t *cls)
 933 {
 934         be_req_t *r = get_req(irn, pos);
 935
 936         r->req.cls = cls;
 937
 938         if (cls == NULL)
 939                 r->req.type = arch_register_req_type_none;
 940         else if (r->req.type == arch_register_req_type_none)
 941                 r->req.type = arch_register_req_type_normal;
 942 }
 943
 944 void be_node_set_req_type(ir_node *irn, int pos, arch_register_req_type_t type)
 945 {
 946         be_req_t *r = get_req(irn, pos);
 947         r->req.type = type;
 948 }
 949
 950 ir_node *be_get_IncSP_pred(ir_node *irn) {
 951         assert(be_is_IncSP(irn));
 952         return get_irn_n(irn, 0);
 953 }
 954
 955 void be_set_IncSP_pred(ir_node *incsp, ir_node *pred) {
 956         assert(be_is_IncSP(incsp));
 957         set_irn_n(incsp, 0, pred);
 958 }
 959
 960 ir_node *be_get_IncSP_mem(ir_node *irn) {
 961         assert(be_is_IncSP(irn));
 962         return get_irn_n(irn, 1);
 963 }
 964
 965 void be_set_IncSP_offset(ir_node *irn, int offset)
 966 {
 967         be_stack_attr_t *a = get_irn_attr(irn);
 968         assert(be_is_IncSP(irn));
 969         a->offset = offset;
 970 }
 971
 972 int be_get_IncSP_offset(const ir_node *irn)
 973 {
 974         be_stack_attr_t *a = get_irn_attr(irn);
 975         assert(be_is_IncSP(irn));
 976         return a->offset;
 977 }
 978
 979 ir_node *be_spill(const arch_env_t *arch_env, ir_node *irn)
 980 {
 981         ir_node                     *bl        = get_nodes_block(irn);
 982         ir_graph                    *irg       = get_irn_irg(bl);
 983         ir_node                     *frame     = get_irg_frame(irg);
 984         const arch_register_class_t *cls       = arch_get_irn_reg_class(arch_env, irn, -1);
 985         const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
 986         ir_node                     *spill;
 987
 988         spill = be_new_Spill(cls, cls_frame, irg, bl, frame, irn);
 989         return spill;
 990 }
 991
 992 ir_node *be_reload(const arch_env_t *arch_env, const arch_register_class_t *cls, ir_node *insert, ir_mode *mode, ir_node *spill)
 993 {
 994         ir_node  *reload;
 995         ir_node  *bl    = is_Block(insert) ? insert : get_nodes_block(insert);
 996         ir_graph *irg   = get_irn_irg(bl);
 997         ir_node  *frame = get_irg_frame(irg);
 998         const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
 999
1000         assert(be_is_Spill(spill) || (is_Phi(spill) && get_irn_mode(spill) == mode_M));
1001
1002         reload = be_new_Reload(cls, cls_frame, irg, bl, frame, spill, mode);
1003
1004         if (is_Block(insert)) {
1005                 insert = sched_skip(insert, 0, sched_skip_cf_predicator, (void *) arch_env);
1006                 sched_add_after(insert, reload);
1007         }
1008
1009         else
1010                 sched_add_before(insert, reload);
1011
1012         return reload;
1013 }
1014
1015 /*
1016   ____              ____
1017  |  _ \ ___  __ _  |  _ \ ___  __ _ ___
1018  | |_) / _ \/ _` | | |_) / _ \/ _` / __|
1019  |  _ <  __/ (_| | |  _ <  __/ (_| \__ \
1020  |_| \_\___|\__, | |_| \_\___|\__, |___/
1021             |___/                |_|
1022
1023 */
1024
1025
1026 static void *put_out_reg_req(arch_register_req_t *req, const ir_node *irn, int out_pos)
1027 {
1028         const be_node_attr_t *a = get_irn_attr(irn);
1029
1030         if(out_pos < a->max_reg_data) {
1031                 memcpy(req, &a->reg_data[out_pos].req, sizeof(req[0]));
1032
1033                 if(be_is_Copy(irn)) {
1034                         req->type |= arch_register_req_type_should_be_same;
1035                         req->other_same = be_get_Copy_op(irn);
1036                 }
1037         }
1038         else {
1039                 req->type = arch_register_req_type_none;
1040                 req->cls  = NULL;
1041         }
1042
1043         return req;
1044 }
1045
1046 static void *put_in_reg_req(arch_register_req_t *req, const ir_node *irn, int pos)
1047 {
1048         const be_node_attr_t *a = get_irn_attr(irn);
1049
1050         if(pos < get_irn_arity(irn) && pos < a->max_reg_data)
1051                 memcpy(req, &a->reg_data[pos].in_req, sizeof(req[0]));
1052         else {
1053                 req->type = arch_register_req_type_none;
1054                 req->cls  = NULL;
1055         }
1056
1057         return req;
1058 }
1059
1060 static const arch_register_req_t *
1061 be_node_get_irn_reg_req(const void *self, arch_register_req_t *req, const ir_node *irn, int pos)
1062 {
1063         int out_pos = pos;
1064
1065         if (pos < 0) {
1066                 if (get_irn_mode(irn) == mode_T)
1067                         return NULL;
1068
1069                 out_pos = redir_proj((const ir_node **)&irn);
1070                 assert(is_be_node(irn));
1071                 return put_out_reg_req(req, irn, out_pos);
1072         }
1073
1074         else {
1075                 if (is_be_node(irn)) {
1076                         /*
1077                                 For spills and reloads, we return "none" as requirement for frame pointer,
1078                                 so every input is ok. Some backends need this (e.g. STA). We use an arbitrary
1079                                 large number as pos, so put_in_reg_req will return "none" as requirement.
1080                         */
1081                         if ((be_is_Spill(irn)  && pos == be_pos_Spill_frame) ||
1082                                 (be_is_Reload(irn) && pos == be_pos_Reload_frame))
1083                                 return put_in_reg_req(req, irn, INT_MAX);
1084                         else
1085                                 return put_in_reg_req(req, irn, pos);
1086                 }
1087                 return NULL;
1088         }
1089
1090         return req;
1091 }
1092
1093 const arch_register_t *
1094 be_node_get_irn_reg(const void *_self, const ir_node *irn)
1095 {
1096         be_reg_data_t *r = retrieve_reg_data(irn);
1097         return r ? r->reg : NULL;
1098 }
1099
1100 static arch_irn_class_t be_node_classify(const void *_self, const ir_node *irn)
1101 {
1102         redir_proj((const ir_node **) &irn);
1103
1104         switch(be_get_irn_opcode(irn)) {
1105 #define XXX(a,b) case beo_ ## a: return arch_irn_class_ ## b
1106                 XXX(Spill, spill);
1107                 XXX(Reload, reload);
1108                 XXX(Perm, perm);
1109                 XXX(Copy, copy);
1110                 XXX(Return, branch);
1111                 XXX(StackParam, stackparam);
1112 #undef XXX
1113                 default:
1114                 return arch_irn_class_normal;
1115         }
1116
1117         return 0;
1118 }
1119
1120 static arch_irn_flags_t be_node_get_flags(const void *_self, const ir_node *irn)
1121 {
1122         be_reg_data_t *r = retrieve_reg_data(irn);
1123         return r ? r->req.flags : 0;
1124 }
1125
1126 static ir_entity *be_node_get_frame_entity(const void *self, const ir_node *irn)
1127 {
1128         return be_get_frame_entity(irn);
1129 }
1130
1131 static void be_node_set_frame_entity(const void *self, ir_node *irn, ir_entity *ent)
1132 {
1133         be_frame_attr_t *a;
1134
1135         assert(be_has_frame_entity(irn));
1136
1137         a = get_irn_attr(irn);
1138         a->ent = ent;
1139 }
1140
1141 static void be_node_set_frame_offset(const void *self, ir_node *irn, int offset)
1142 {
1143         if(be_has_frame_entity(irn)) {
1144                 be_frame_attr_t *a = get_irn_attr(irn);
1145                 a->offset = offset;
1146         }
1147 }
1148
1149 static int be_node_get_sp_bias(const void *self, const ir_node *irn)
1150 {
1151         return be_is_IncSP(irn) ? be_get_IncSP_offset(irn) : 0;
1152 }
1153
1154 /*
1155   ___ ____  _   _   _   _                 _ _
1156  |_ _|  _ \| \ | | | | | | __ _ _ __   __| | | ___ _ __
1157   | || |_) |  \| | | |_| |/ _` | '_ \ / _` | |/ _ \ '__|
1158   | ||  _ <| |\  | |  _  | (_| | | | | (_| | |  __/ |
1159  |___|_| \_\_| \_| |_| |_|\__,_|_| |_|\__,_|_|\___|_|
1160
1161 */
1162
1163 static const arch_irn_ops_if_t be_node_irn_ops_if = {
1164         be_node_get_irn_reg_req,
1165         be_node_set_irn_reg,
1166         be_node_get_irn_reg,
1167         be_node_classify,
1168         be_node_get_flags,
1169         be_node_get_frame_entity,
1170         be_node_set_frame_entity,
1171         be_node_set_frame_offset,
1172         be_node_get_sp_bias,
1173         NULL,    /* get_inverse             */
1174         NULL,    /* get_op_estimated_cost   */
1175         NULL,    /* possible_memory_operand */
1176         NULL,    /* perform_memory_operand  */
1177 };
1178
1179 static const arch_irn_ops_t be_node_irn_ops = {
1180         &be_node_irn_ops_if
1181 };
1182
1183 const void *be_node_get_irn_ops(const arch_irn_handler_t *self, const ir_node *irn)
1184 {
1185         redir_proj((const ir_node **) &irn);
1186         return is_be_node(irn) ? &be_node_irn_ops : NULL;
1187 }
1188
1189 const arch_irn_handler_t be_node_irn_handler = {
1190         be_node_get_irn_ops
1191 };
1192
1193 /*
1194   ____  _     _   ___ ____  _   _   _   _                 _ _
1195  |  _ \| |__ (_) |_ _|  _ \| \ | | | | | | __ _ _ __   __| | | ___ _ __
1196  | |_) | '_ \| |  | || |_) |  \| | | |_| |/ _` | '_ \ / _` | |/ _ \ '__|
1197  |  __/| | | | |  | ||  _ <| |\  | |  _  | (_| | | | | (_| | |  __/ |
1198  |_|   |_| |_|_| |___|_| \_\_| \_| |_| |_|\__,_|_| |_|\__,_|_|\___|_|
1199
1200 */
1201
1202 typedef struct {
1203         arch_irn_handler_t irn_handler;
1204         arch_irn_ops_t     irn_ops;
1205         const arch_env_t   *arch_env;
1206         pmap               *regs;
1207 } phi_handler_t;
1208
1209 #define get_phi_handler_from_handler(h)  container_of(h, phi_handler_t, irn_handler)
1210 #define get_phi_handler_from_ops(h)      container_of(h, phi_handler_t, irn_ops)
1211
1212 static const void *phi_get_irn_ops(const arch_irn_handler_t *handler, const ir_node *irn)
1213 {
1214         const phi_handler_t *h = get_phi_handler_from_handler(handler);
1215         return is_Phi(irn) && mode_is_datab(get_irn_mode(irn)) ? &h->irn_ops : NULL;
1216 }
1217
1218 /**
1219  * Get register class of a Phi.
1220  *
1221  */
1222 static const arch_register_req_t *get_Phi_reg_req_recursive(const phi_handler_t *h, arch_register_req_t *req, const ir_node *phi, pset **visited)
1223 {
1224         int n = get_irn_arity(phi);
1225         ir_node *op;
1226         int i;
1227
1228         if(*visited && pset_find_ptr(*visited, phi))
1229                 return NULL;
1230
1231         for(i = 0; i < n; ++i) {
1232                 op = get_irn_n(phi, i);
1233                 if(!is_Phi(op))
1234                         return arch_get_register_req(h->arch_env, req, op, BE_OUT_POS(0));
1235         }
1236
1237         /*
1238         The operands of that Phi were all Phis themselves.
1239         We have to start a DFS for a non-Phi argument now.
1240         */
1241         if(!*visited)
1242                 *visited = pset_new_ptr(16);
1243
1244         pset_insert_ptr(*visited, phi);
1245
1246         for(i = 0; i < n; ++i) {
1247                 op = get_irn_n(phi, i);
1248                 if(get_Phi_reg_req_recursive(h, req, op, visited))
1249                         return req;
1250         }
1251
1252         return NULL;
1253 }
1254
1255 static const arch_register_req_t *phi_get_irn_reg_req(const void *self, arch_register_req_t *req, const ir_node *irn, int pos)
1256 {
1257         phi_handler_t *phi_handler = get_phi_handler_from_ops(self);
1258         pset *visited              = NULL;
1259
1260         get_Phi_reg_req_recursive(phi_handler, req, irn, &visited);
1261         /* Set the requirements type to normal, since an operand of the Phi could have had constraints. */
1262         req->type = arch_register_req_type_normal;
1263         if(visited)
1264                 del_pset(visited);
1265
1266         return req;
1267 }
1268
1269 static void phi_set_irn_reg(const void *self, ir_node *irn, const arch_register_t *reg)
1270 {
1271         phi_handler_t *h = get_phi_handler_from_ops(self);
1272         pmap_insert(h->regs, irn, (void *) reg);
1273 }
1274
1275 static const arch_register_t *phi_get_irn_reg(const void *self, const ir_node *irn)
1276 {
1277         phi_handler_t *h = get_phi_handler_from_ops(self);
1278         return pmap_get(h->regs, (void *) irn);
1279 }
1280
1281 static arch_irn_class_t phi_classify(const void *_self, const ir_node *irn)
1282 {
1283         return arch_irn_class_normal;
1284 }
1285
1286 static arch_irn_flags_t phi_get_flags(const void *_self, const ir_node *irn)
1287 {
1288         return arch_irn_flags_none;
1289 }
1290
1291 static ir_entity *phi_get_frame_entity(const void *_self, const ir_node *irn)
1292 {
1293         return NULL;
1294 }
1295
1296 static void phi_set_frame_entity(const void *_self, ir_node *irn, ir_entity *ent)
1297 {
1298 }
1299
1300 static void phi_set_frame_offset(const void *_self, ir_node *irn, int bias)
1301 {
1302 }
1303
1304 static int phi_get_sp_bias(const void* self, const ir_node *irn)
1305 {
1306         return 0;
1307 }
1308
1309 static const arch_irn_ops_if_t phi_irn_ops = {
1310         phi_get_irn_reg_req,
1311         phi_set_irn_reg,
1312         phi_get_irn_reg,
1313         phi_classify,
1314         phi_get_flags,
1315         phi_get_frame_entity,
1316         phi_set_frame_entity,
1317         phi_set_frame_offset,
1318         phi_get_sp_bias,
1319         NULL,    /* get_inverse             */
1320         NULL,    /* get_op_estimated_cost   */
1321         NULL,    /* possible_memory_operand */
1322         NULL,    /* perform_memory_operand  */
1323 };
1324
1325 static const arch_irn_handler_t phi_irn_handler = {
1326         phi_get_irn_ops
1327 };
1328
1329 arch_irn_handler_t *be_phi_handler_new(const arch_env_t *arch_env)
1330 {
1331         phi_handler_t *h           = xmalloc(sizeof(h[0]));
1332         h->irn_handler.get_irn_ops = phi_get_irn_ops;
1333         h->irn_ops.impl            = &phi_irn_ops;
1334         h->arch_env                = arch_env;
1335         h->regs                    = pmap_create();
1336         return (arch_irn_handler_t *) h;
1337 }
1338
1339 void be_phi_handler_free(arch_irn_handler_t *handler)
1340 {
1341         phi_handler_t *h = (void *) handler;
1342         pmap_destroy(h->regs);
1343         free(handler);
1344 }
1345
1346 const void *be_phi_get_irn_ops(const arch_irn_handler_t *self, const ir_node *irn)
1347 {
1348         phi_handler_t *phi_handler = get_phi_handler_from_handler(self);
1349         return is_Phi(irn) ? &phi_handler->irn_ops : NULL;
1350 }
1351
1352 void be_phi_handler_reset(arch_irn_handler_t *handler)
1353 {
1354         phi_handler_t *h = get_phi_handler_from_handler(handler);
1355         if(h->regs)
1356                 pmap_destroy(h->regs);
1357         h->regs = pmap_create();
1358 }
1359
1360 /*
1361   _   _           _        ____                        _
1362  | \ | | ___   __| | ___  |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
1363  |  \| |/ _ \ / _` |/ _ \ | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1364  | |\  | (_) | (_| |  __/ | |_| | |_| | | | | | | |_) | | | | | (_| |
1365  |_| \_|\___/ \__,_|\___| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1366                                                 |_|            |___/
1367 */
1368
1369 /**
1370  * Dumps a register requirement to a file.
1371  */
1372 static void dump_node_req(FILE *f, int idx, be_req_t *req)
1373 {
1374         unsigned i;
1375         int did_something = 0;
1376         char buf[16];
1377         const char *prefix = buf;
1378
1379         snprintf(buf, sizeof(buf), "#%d ", idx);
1380         buf[sizeof(buf) - 1] = '\0';
1381
1382         if(req->flags != arch_irn_flags_none) {
1383                 fprintf(f, "%sflags: ", prefix);
1384                 prefix = "";
1385                 for(i = arch_irn_flags_none; i <= log2_ceil(arch_irn_flags_last); ++i) {
1386                         if(req->flags & (1 << i)) {
1387                                 fprintf(f, "%s%s", prefix, arch_irn_flag_str(1 << i));
1388                                 prefix = "|";
1389                         }
1390                 }
1391                 prefix = ", ";
1392                 did_something = 1;
1393         }
1394
1395         if(req->req.cls != 0) {
1396                 char tmp[256];
1397                 fprintf(f, prefix);
1398                 arch_register_req_format(tmp, sizeof(tmp), &req->req);
1399                 fprintf(f, "%s", tmp);
1400                 did_something = 1;
1401         }
1402
1403         if(did_something)
1404                 fprintf(f, "\n");
1405 }
1406
1407 /**
1408  * Dumps node register requirements to a file.
1409  */
1410 static void dump_node_reqs(FILE *f, ir_node *irn)
1411 {
1412         int i;
1413         be_node_attr_t *a = get_irn_attr(irn);
1414
1415         fprintf(f, "registers: \n");
1416         for(i = 0; i < a->max_reg_data; ++i) {
1417                 be_reg_data_t *rd = &a->reg_data[i];
1418                 if(rd->reg)
1419                         fprintf(f, "#%d: %s\n", i, rd->reg->name);
1420         }
1421
1422         fprintf(f, "in requirements\n");
1423         for(i = 0; i < a->max_reg_data; ++i) {
1424                 dump_node_req(f, i, &a->reg_data[i].in_req);
1425         }
1426
1427         fprintf(f, "\nout requirements\n");
1428         for(i = 0; i < a->max_reg_data; ++i) {
1429                 dump_node_req(f, i, &a->reg_data[i].req);
1430         }
1431 }
1432
1433 /**
1434  * ir_op-Operation: dump a be node to file
1435  */
1436 static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason)
1437 {
1438         be_node_attr_t *at = get_irn_attr(irn);
1439
1440         assert(is_be_node(irn));
1441
1442         switch(reason) {
1443                 case dump_node_opcode_txt:
1444                         fprintf(f, get_op_name(get_irn_op(irn)));
1445                         break;
1446                 case dump_node_mode_txt:
1447                         fprintf(f, get_mode_name(get_irn_mode(irn)));
1448                         break;
1449                 case dump_node_nodeattr_txt:
1450                         break;
1451                 case dump_node_info_txt:
1452                         dump_node_reqs(f, irn);
1453
1454                         if(be_has_frame_entity(irn)) {
1455                                 be_frame_attr_t *a = (be_frame_attr_t *) at;
1456                                 if (a->ent) {
1457                                         int bits = get_type_size_bits(get_entity_type(a->ent));
1458                                         ir_fprintf(f, "frame entity: %+F, offset 0x%x (%d), size 0x%x (%d) bits\n",
1459                                           a->ent, a->offset, a->offset, bits, bits);
1460                                 }
1461
1462                         }
1463
1464                         switch(be_get_irn_opcode(irn)) {
1465                         case beo_IncSP:
1466                                 {
1467                                         be_stack_attr_t *a = (be_stack_attr_t *) at;
1468                                         if (a->offset == BE_STACK_FRAME_SIZE_EXPAND)
1469                                                 fprintf(f, "offset: FRAME_SIZE\n");
1470                                         else if(a->offset == BE_STACK_FRAME_SIZE_SHRINK)
1471                                                 fprintf(f, "offset: -FRAME SIZE\n");
1472                                         else
1473                                                 fprintf(f, "offset: %u\n", a->offset);
1474                                 }
1475                                 break;
1476                         case beo_Call:
1477                                 {
1478                                         be_call_attr_t *a = (be_call_attr_t *) at;
1479
1480                                         if (a->ent)
1481                                                 fprintf(f, "\ncalling: %s\n", get_entity_name(a->ent));
1482                                 }
1483                                 break;
1484                         case beo_MemPerm:
1485                                 {
1486                                         int i;
1487                                         for(i = 0; i < be_get_MemPerm_entity_arity(irn); ++i) {
1488                                                 ir_entity *in, *out;
1489                                                 in = be_get_MemPerm_in_entity(irn, i);
1490                                                 out = be_get_MemPerm_out_entity(irn, i);
1491                                                 if(in) {
1492                                                         fprintf(f, "\nin[%d]: %s\n", i, get_entity_name(in));
1493                                                 }
1494                                                 if(out) {
1495                                                         fprintf(f, "\nout[%d]: %s\n", i, get_entity_name(out));
1496                                                 }
1497                                         }
1498                                 }
1499                                 break;
1500
1501                         default:
1502                                 break;
1503                         }
1504         }
1505
1506         return 0;
1507 }
1508
1509 /**
1510  * ir_op-Operation:
1511  * Copies the backend specific attributes from old node to new node.
1512  */
1513 static void copy_attr(const ir_node *old_node, ir_node *new_node)
1514 {
1515         be_node_attr_t *old_attr = get_irn_attr(old_node);
1516         be_node_attr_t *new_attr = get_irn_attr(new_node);
1517         int i;
1518
1519         assert(is_be_node(old_node));
1520         assert(is_be_node(new_node));
1521
1522         memcpy(new_attr, old_attr, get_op_attr_size(get_irn_op(old_node)));
1523         new_attr->reg_data = NULL;
1524
1525         if(new_attr->max_reg_data > 0) {
1526                 new_attr->reg_data = NEW_ARR_D(be_reg_data_t, get_irg_obstack(get_irn_irg(new_node)), new_attr->max_reg_data);
1527                 memcpy(new_attr->reg_data, old_attr->reg_data, new_attr->max_reg_data * sizeof(be_reg_data_t));
1528
1529                 for(i = 0; i < old_attr->max_reg_data; ++i) {
1530                         be_req_t *r;
1531
1532                         r = &new_attr->reg_data[i].req;
1533                         r->req.limited_env = r;
1534
1535                         r = &new_attr->reg_data[i].in_req;
1536                         r->req.limited_env = r;
1537                 }
1538         }
1539 }
1540
1541 static const ir_op_ops be_node_op_ops = {
1542         NULL,
1543         NULL,
1544         NULL,
1545         NULL,
1546         NULL,
1547         copy_attr,
1548         NULL,
1549         NULL,
1550         NULL,
1551         NULL,
1552         NULL,
1553         dump_node,
1554         NULL
1555 };