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_unary,    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_SubSP         (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_SubSP          ; }
 781 int be_is_RegParams     (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_RegParams      ; }
 782 int be_is_StackParam    (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_StackParam     ; }
 783 int be_is_FrameAddr     (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_FrameAddr      ; }
 784 int be_is_FrameLoad     (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_FrameLoad      ; }
 785 int be_is_FrameStore    (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_FrameStore     ; }
 786 int be_is_Barrier       (const ir_node *irn) { return be_get_irn_opcode(irn) == beo_Barrier        ; }
 787
 788 int be_has_frame_entity(const ir_node *irn)
 789 {
 790         switch(be_get_irn_opcode(irn)) {
 791         case beo_StackParam:
 792         case beo_Spill:
 793         case beo_Reload:
 794         case beo_FrameStore:
 795         case beo_FrameLoad:
 796         case beo_FrameAddr:
 797                 return 1;
 798         default:
 799                 return 0;
 800         }
 801 }
 802
 803 ir_entity *be_get_frame_entity(const ir_node *irn)
 804 {
 805         if (be_has_frame_entity(irn)) {
 806                 be_frame_attr_t *a = get_irn_attr(irn);
 807                 return a->ent;
 808         }
 809         return NULL;
 810 }
 811
 812 int be_get_frame_offset(const ir_node *irn)
 813 {
 814         assert(is_be_node(irn));
 815         if (be_has_frame_entity(irn)) {
 816                 be_frame_attr_t *a = get_irn_attr(irn);
 817                 return a->offset;
 818         }
 819         return 0;
 820 }
 821
 822 void be_set_MemPerm_in_entity(const ir_node *irn, int n, ir_entity *ent)
 823 {
 824         be_memperm_attr_t *attr = get_irn_attr(irn);
 825
 826         assert(be_is_MemPerm(irn));
 827         assert(n < be_get_MemPerm_entity_arity(irn));
 828
 829         attr->in_entities[n] = ent;
 830 }
 831
 832 ir_entity* be_get_MemPerm_in_entity(const ir_node* irn, int n)
 833 {
 834         be_memperm_attr_t *attr = get_irn_attr(irn);
 835
 836         assert(be_is_MemPerm(irn));
 837         assert(n < be_get_MemPerm_entity_arity(irn));
 838
 839         return attr->in_entities[n];
 840 }
 841
 842 void be_set_MemPerm_out_entity(const ir_node *irn, int n, ir_entity *ent)
 843 {
 844         be_memperm_attr_t *attr = get_irn_attr(irn);
 845
 846         assert(be_is_MemPerm(irn));
 847         assert(n < be_get_MemPerm_entity_arity(irn));
 848
 849         attr->out_entities[n] = ent;
 850 }
 851
 852 ir_entity* be_get_MemPerm_out_entity(const ir_node* irn, int n)
 853 {
 854         be_memperm_attr_t *attr = get_irn_attr(irn);
 855
 856         assert(be_is_MemPerm(irn));
 857         assert(n < be_get_MemPerm_entity_arity(irn));
 858
 859         return attr->out_entities[n];
 860 }
 861
 862 int be_get_MemPerm_entity_arity(const ir_node *irn)
 863 {
 864         return get_irn_arity(irn) - 1;
 865 }
 866
 867 static void be_limited(void *data, bitset_t *bs)
 868 {
 869         be_req_t *req = data;
 870
 871         switch(req->kind) {
 872         case be_req_kind_negate_old_limited:
 873         case be_req_kind_old_limited:
 874                 req->x.old_limited.old_limited(req->x.old_limited.old_limited_env, bs);
 875                 if(req->kind == be_req_kind_negate_old_limited)
 876                         bitset_flip_all(bs);
 877                 break;
 878         case be_req_kind_single_reg:
 879                 bitset_clear_all(bs);
 880                 bitset_set(bs, req->x.single_reg->index);
 881                 break;
 882         }
 883 }
 884
 885 static INLINE be_req_t *get_req(ir_node *irn, int pos)
 886 {
 887         int idx           = pos < 0 ? -(pos + 1) : pos;
 888         be_node_attr_t *a = get_irn_attr(irn);
 889         be_reg_data_t *rd = &a->reg_data[idx];
 890         be_req_t       *r = pos < 0 ? &rd->req : &rd->in_req;
 891
 892         assert(is_be_node(irn));
 893         assert(!(pos >= 0) || pos < get_irn_arity(irn));
 894         assert(!(pos < 0)  || -(pos + 1) <= a->max_reg_data);
 895
 896         return r;
 897 }
 898
 899 void be_set_constr_single_reg(ir_node *irn, int pos, const arch_register_t *reg)
 900 {
 901         be_req_t *r = get_req(irn, pos);
 902
 903         r->kind            = be_req_kind_single_reg;
 904         r->x.single_reg    = reg;
 905         r->req.limited     = be_limited;
 906         r->req.limited_env = r;
 907         r->req.type        = arch_register_req_type_limited;
 908         r->req.cls         = reg->reg_class;
 909 }
 910
 911 void be_set_constr_limited(ir_node *irn, int pos, const arch_register_req_t *req)
 912 {
 913         be_req_t *r = get_req(irn, pos);
 914
 915         assert(arch_register_req_is(req, limited));
 916
 917         r->kind            = be_req_kind_old_limited;
 918         r->req.limited     = be_limited;
 919         r->req.limited_env = r;
 920         r->req.type        = arch_register_req_type_limited;
 921         r->req.cls         = req->cls;
 922
 923         r->x.old_limited.old_limited     = req->limited;
 924         r->x.old_limited.old_limited_env = req->limited_env;
 925 }
 926
 927 void be_node_set_flags(ir_node *irn, int pos, arch_irn_flags_t flags)
 928 {
 929         be_req_t *r = get_req(irn, pos);
 930         r->flags = flags;
 931 }
 932
 933 void be_node_set_reg_class(ir_node *irn, int pos, const arch_register_class_t *cls)
 934 {
 935         be_req_t *r = get_req(irn, pos);
 936
 937         r->req.cls = cls;
 938
 939         if (cls == NULL)
 940                 r->req.type = arch_register_req_type_none;
 941         else if (r->req.type == arch_register_req_type_none)
 942                 r->req.type = arch_register_req_type_normal;
 943 }
 944
 945 void be_node_set_req_type(ir_node *irn, int pos, arch_register_req_type_t type)
 946 {
 947         be_req_t *r = get_req(irn, pos);
 948         r->req.type = type;
 949 }
 950
 951 ir_node *be_get_IncSP_pred(ir_node *irn) {
 952         assert(be_is_IncSP(irn));
 953         return get_irn_n(irn, 0);
 954 }
 955
 956 void be_set_IncSP_pred(ir_node *incsp, ir_node *pred) {
 957         assert(be_is_IncSP(incsp));
 958         set_irn_n(incsp, 0, pred);
 959 }
 960
 961 ir_node *be_get_IncSP_mem(ir_node *irn) {
 962         assert(be_is_IncSP(irn));
 963         return get_irn_n(irn, 1);
 964 }
 965
 966 void be_set_IncSP_offset(ir_node *irn, int offset)
 967 {
 968         be_stack_attr_t *a = get_irn_attr(irn);
 969         assert(be_is_IncSP(irn));
 970         a->offset = offset;
 971 }
 972
 973 int be_get_IncSP_offset(const ir_node *irn)
 974 {
 975         be_stack_attr_t *a = get_irn_attr(irn);
 976         assert(be_is_IncSP(irn));
 977         return a->offset;
 978 }
 979
 980 ir_node *be_spill(const arch_env_t *arch_env, ir_node *irn)
 981 {
 982         ir_node                     *bl        = get_nodes_block(irn);
 983         ir_graph                    *irg       = get_irn_irg(bl);
 984         ir_node                     *frame     = get_irg_frame(irg);
 985         const arch_register_class_t *cls       = arch_get_irn_reg_class(arch_env, irn, -1);
 986         const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
 987         ir_node                     *spill;
 988
 989         spill = be_new_Spill(cls, cls_frame, irg, bl, frame, irn);
 990         return spill;
 991 }
 992
 993 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)
 994 {
 995         ir_node  *reload;
 996         ir_node  *bl    = is_Block(insert) ? insert : get_nodes_block(insert);
 997         ir_graph *irg   = get_irn_irg(bl);
 998         ir_node  *frame = get_irg_frame(irg);
 999         const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
1000
1001         assert(be_is_Spill(spill) || (is_Phi(spill) && get_irn_mode(spill) == mode_M));
1002
1003         reload = be_new_Reload(cls, cls_frame, irg, bl, frame, spill, mode);
1004
1005         if (is_Block(insert)) {
1006                 insert = sched_skip(insert, 0, sched_skip_cf_predicator, (void *) arch_env);
1007                 sched_add_after(insert, reload);
1008         }
1009
1010         else
1011                 sched_add_before(insert, reload);
1012
1013         return reload;
1014 }
1015
1016 /*
1017   ____              ____
1018  |  _ \ ___  __ _  |  _ \ ___  __ _ ___
1019  | |_) / _ \/ _` | | |_) / _ \/ _` / __|
1020  |  _ <  __/ (_| | |  _ <  __/ (_| \__ \
1021  |_| \_\___|\__, | |_| \_\___|\__, |___/
1022             |___/                |_|
1023
1024 */
1025
1026
1027 static void *put_out_reg_req(arch_register_req_t *req, const ir_node *irn, int out_pos)
1028 {
1029         const be_node_attr_t *a = get_irn_attr(irn);
1030
1031         if(out_pos < a->max_reg_data) {
1032                 memcpy(req, &a->reg_data[out_pos].req, sizeof(req[0]));
1033
1034                 if(be_is_Copy(irn)) {
1035                         req->type |= arch_register_req_type_should_be_same;
1036                         req->other_same = be_get_Copy_op(irn);
1037                 }
1038         }
1039         else {
1040                 req->type = arch_register_req_type_none;
1041                 req->cls  = NULL;
1042         }
1043
1044         return req;
1045 }
1046
1047 static void *put_in_reg_req(arch_register_req_t *req, const ir_node *irn, int pos)
1048 {
1049         const be_node_attr_t *a = get_irn_attr(irn);
1050
1051         if(pos < get_irn_arity(irn) && pos < a->max_reg_data)
1052                 memcpy(req, &a->reg_data[pos].in_req, sizeof(req[0]));
1053         else {
1054                 req->type = arch_register_req_type_none;
1055                 req->cls  = NULL;
1056         }
1057
1058         return req;
1059 }
1060
1061 static const arch_register_req_t *
1062 be_node_get_irn_reg_req(const void *self, arch_register_req_t *req, const ir_node *irn, int pos)
1063 {
1064         int out_pos = pos;
1065
1066         if (pos < 0) {
1067                 if (get_irn_mode(irn) == mode_T)
1068                         return NULL;
1069
1070                 out_pos = redir_proj((const ir_node **)&irn);
1071                 assert(is_be_node(irn));
1072                 return put_out_reg_req(req, irn, out_pos);
1073         }
1074
1075         else {
1076                 if (is_be_node(irn)) {
1077                         /*
1078                                 For spills and reloads, we return "none" as requirement for frame pointer,
1079                                 so every input is ok. Some backends need this (e.g. STA). We use an arbitrary
1080                                 large number as pos, so put_in_reg_req will return "none" as requirement.
1081                         */
1082                         if ((be_is_Spill(irn)  && pos == be_pos_Spill_frame) ||
1083                                 (be_is_Reload(irn) && pos == be_pos_Reload_frame))
1084                                 return put_in_reg_req(req, irn, INT_MAX);
1085                         else
1086                                 return put_in_reg_req(req, irn, pos);
1087                 }
1088                 return NULL;
1089         }
1090
1091         return req;
1092 }
1093
1094 const arch_register_t *
1095 be_node_get_irn_reg(const void *_self, const ir_node *irn)
1096 {
1097         be_reg_data_t *r = retrieve_reg_data(irn);
1098         return r ? r->reg : NULL;
1099 }
1100
1101 static arch_irn_class_t be_node_classify(const void *_self, const ir_node *irn)
1102 {
1103         redir_proj((const ir_node **) &irn);
1104
1105         switch(be_get_irn_opcode(irn)) {
1106 #define XXX(a,b) case beo_ ## a: return arch_irn_class_ ## b
1107                 XXX(Spill, spill);
1108                 XXX(Reload, reload);
1109                 XXX(Perm, perm);
1110                 XXX(Copy, copy);
1111                 XXX(Return, branch);
1112                 XXX(StackParam, stackparam);
1113 #undef XXX
1114                 default:
1115                 return arch_irn_class_normal;
1116         }
1117
1118         return 0;
1119 }
1120
1121 static arch_irn_flags_t be_node_get_flags(const void *_self, const ir_node *irn)
1122 {
1123         be_reg_data_t *r = retrieve_reg_data(irn);
1124         return r ? r->req.flags : 0;
1125 }
1126
1127 static ir_entity *be_node_get_frame_entity(const void *self, const ir_node *irn)
1128 {
1129         return be_get_frame_entity(irn);
1130 }
1131
1132 static void be_node_set_frame_entity(const void *self, ir_node *irn, ir_entity *ent)
1133 {
1134         be_frame_attr_t *a;
1135
1136         assert(be_has_frame_entity(irn));
1137
1138         a = get_irn_attr(irn);
1139         a->ent = ent;
1140 }
1141
1142 static void be_node_set_frame_offset(const void *self, ir_node *irn, int offset)
1143 {
1144         if(be_has_frame_entity(irn)) {
1145                 be_frame_attr_t *a = get_irn_attr(irn);
1146                 a->offset = offset;
1147         }
1148 }
1149
1150 static int be_node_get_sp_bias(const void *self, const ir_node *irn)
1151 {
1152         return be_is_IncSP(irn) ? be_get_IncSP_offset(irn) : 0;
1153 }
1154
1155 /*
1156   ___ ____  _   _   _   _                 _ _
1157  |_ _|  _ \| \ | | | | | | __ _ _ __   __| | | ___ _ __
1158   | || |_) |  \| | | |_| |/ _` | '_ \ / _` | |/ _ \ '__|
1159   | ||  _ <| |\  | |  _  | (_| | | | | (_| | |  __/ |
1160  |___|_| \_\_| \_| |_| |_|\__,_|_| |_|\__,_|_|\___|_|
1161
1162 */
1163
1164 static const arch_irn_ops_if_t be_node_irn_ops_if = {
1165         be_node_get_irn_reg_req,
1166         be_node_set_irn_reg,
1167         be_node_get_irn_reg,
1168         be_node_classify,
1169         be_node_get_flags,
1170         be_node_get_frame_entity,
1171         be_node_set_frame_entity,
1172         be_node_set_frame_offset,
1173         be_node_get_sp_bias,
1174         NULL,    /* get_inverse             */
1175         NULL,    /* get_op_estimated_cost   */
1176         NULL,    /* possible_memory_operand */
1177         NULL,    /* perform_memory_operand  */
1178 };
1179
1180 static const arch_irn_ops_t be_node_irn_ops = {
1181         &be_node_irn_ops_if
1182 };
1183
1184 const void *be_node_get_irn_ops(const arch_irn_handler_t *self, const ir_node *irn)
1185 {
1186         redir_proj((const ir_node **) &irn);
1187         return is_be_node(irn) ? &be_node_irn_ops : NULL;
1188 }
1189
1190 const arch_irn_handler_t be_node_irn_handler = {
1191         be_node_get_irn_ops
1192 };
1193
1194 /*
1195   ____  _     _   ___ ____  _   _   _   _                 _ _
1196  |  _ \| |__ (_) |_ _|  _ \| \ | | | | | | __ _ _ __   __| | | ___ _ __
1197  | |_) | '_ \| |  | || |_) |  \| | | |_| |/ _` | '_ \ / _` | |/ _ \ '__|
1198  |  __/| | | | |  | ||  _ <| |\  | |  _  | (_| | | | | (_| | |  __/ |
1199  |_|   |_| |_|_| |___|_| \_\_| \_| |_| |_|\__,_|_| |_|\__,_|_|\___|_|
1200
1201 */
1202
1203 typedef struct {
1204         arch_irn_handler_t irn_handler;
1205         arch_irn_ops_t     irn_ops;
1206         const arch_env_t   *arch_env;
1207         pmap               *regs;
1208 } phi_handler_t;
1209
1210 #define get_phi_handler_from_handler(h)  container_of(h, phi_handler_t, irn_handler)
1211 #define get_phi_handler_from_ops(h)      container_of(h, phi_handler_t, irn_ops)
1212
1213 static const void *phi_get_irn_ops(const arch_irn_handler_t *handler, const ir_node *irn)
1214 {
1215         const phi_handler_t *h = get_phi_handler_from_handler(handler);
1216         return is_Phi(irn) && mode_is_datab(get_irn_mode(irn)) ? &h->irn_ops : NULL;
1217 }
1218
1219 /**
1220  * Get register class of a Phi.
1221  *
1222  */
1223 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)
1224 {
1225         int n = get_irn_arity(phi);
1226         ir_node *op;
1227         int i;
1228
1229         if(*visited && pset_find_ptr(*visited, phi))
1230                 return NULL;
1231
1232         for(i = 0; i < n; ++i) {
1233                 op = get_irn_n(phi, i);
1234                 if(!is_Phi(op))
1235                         return arch_get_register_req(h->arch_env, req, op, BE_OUT_POS(0));
1236         }
1237
1238         /*
1239         The operands of that Phi were all Phis themselves.
1240         We have to start a DFS for a non-Phi argument now.
1241         */
1242         if(!*visited)
1243                 *visited = pset_new_ptr(16);
1244
1245         pset_insert_ptr(*visited, phi);
1246
1247         for(i = 0; i < n; ++i) {
1248                 op = get_irn_n(phi, i);
1249                 if(get_Phi_reg_req_recursive(h, req, op, visited))
1250                         return req;
1251         }
1252
1253         return NULL;
1254 }
1255
1256 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)
1257 {
1258         phi_handler_t *phi_handler = get_phi_handler_from_ops(self);
1259         pset *visited              = NULL;
1260
1261         get_Phi_reg_req_recursive(phi_handler, req, irn, &visited);
1262         /* Set the requirements type to normal, since an operand of the Phi could have had constraints. */
1263         req->type = arch_register_req_type_normal;
1264         if(visited)
1265                 del_pset(visited);
1266
1267         return req;
1268 }
1269
1270 static void phi_set_irn_reg(const void *self, ir_node *irn, const arch_register_t *reg)
1271 {
1272         phi_handler_t *h = get_phi_handler_from_ops(self);
1273         pmap_insert(h->regs, irn, (void *) reg);
1274 }
1275
1276 static const arch_register_t *phi_get_irn_reg(const void *self, const ir_node *irn)
1277 {
1278         phi_handler_t *h = get_phi_handler_from_ops(self);
1279         return pmap_get(h->regs, (void *) irn);
1280 }
1281
1282 static arch_irn_class_t phi_classify(const void *_self, const ir_node *irn)
1283 {
1284         return arch_irn_class_normal;
1285 }
1286
1287 static arch_irn_flags_t phi_get_flags(const void *_self, const ir_node *irn)
1288 {
1289         return arch_irn_flags_none;
1290 }
1291
1292 static ir_entity *phi_get_frame_entity(const void *_self, const ir_node *irn)
1293 {
1294         return NULL;
1295 }
1296
1297 static void phi_set_frame_entity(const void *_self, ir_node *irn, ir_entity *ent)
1298 {
1299 }
1300
1301 static void phi_set_frame_offset(const void *_self, ir_node *irn, int bias)
1302 {
1303 }
1304
1305 static int phi_get_sp_bias(const void* self, const ir_node *irn)
1306 {
1307         return 0;
1308 }
1309
1310 static const arch_irn_ops_if_t phi_irn_ops = {
1311         phi_get_irn_reg_req,
1312         phi_set_irn_reg,
1313         phi_get_irn_reg,
1314         phi_classify,
1315         phi_get_flags,
1316         phi_get_frame_entity,
1317         phi_set_frame_entity,
1318         phi_set_frame_offset,
1319         phi_get_sp_bias,
1320         NULL,    /* get_inverse             */
1321         NULL,    /* get_op_estimated_cost   */
1322         NULL,    /* possible_memory_operand */
1323         NULL,    /* perform_memory_operand  */
1324 };
1325
1326 static const arch_irn_handler_t phi_irn_handler = {
1327         phi_get_irn_ops
1328 };
1329
1330 arch_irn_handler_t *be_phi_handler_new(const arch_env_t *arch_env)
1331 {
1332         phi_handler_t *h           = xmalloc(sizeof(h[0]));
1333         h->irn_handler.get_irn_ops = phi_get_irn_ops;
1334         h->irn_ops.impl            = &phi_irn_ops;
1335         h->arch_env                = arch_env;
1336         h->regs                    = pmap_create();
1337         return (arch_irn_handler_t *) h;
1338 }
1339
1340 void be_phi_handler_free(arch_irn_handler_t *handler)
1341 {
1342         phi_handler_t *h = (void *) handler;
1343         pmap_destroy(h->regs);
1344         free(handler);
1345 }
1346
1347 const void *be_phi_get_irn_ops(const arch_irn_handler_t *self, const ir_node *irn)
1348 {
1349         phi_handler_t *phi_handler = get_phi_handler_from_handler(self);
1350         return is_Phi(irn) ? &phi_handler->irn_ops : NULL;
1351 }
1352
1353 void be_phi_handler_reset(arch_irn_handler_t *handler)
1354 {
1355         phi_handler_t *h = get_phi_handler_from_handler(handler);
1356         if(h->regs)
1357                 pmap_destroy(h->regs);
1358         h->regs = pmap_create();
1359 }
1360
1361 /*
1362   _   _           _        ____                        _
1363  | \ | | ___   __| | ___  |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
1364  |  \| |/ _ \ / _` |/ _ \ | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
1365  | |\  | (_) | (_| |  __/ | |_| | |_| | | | | | | |_) | | | | | (_| |
1366  |_| \_|\___/ \__,_|\___| |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
1367                                                 |_|            |___/
1368 */
1369
1370 /**
1371  * Dumps a register requirement to a file.
1372  */
1373 static void dump_node_req(FILE *f, int idx, be_req_t *req)
1374 {
1375         unsigned i;
1376         int did_something = 0;
1377         char buf[16];
1378         const char *prefix = buf;
1379
1380         snprintf(buf, sizeof(buf), "#%d ", idx);
1381         buf[sizeof(buf) - 1] = '\0';
1382
1383         if(req->flags != arch_irn_flags_none) {
1384                 fprintf(f, "%sflags: ", prefix);
1385                 prefix = "";
1386                 for(i = arch_irn_flags_none; i <= log2_ceil(arch_irn_flags_last); ++i) {
1387                         if(req->flags & (1 << i)) {
1388                                 fprintf(f, "%s%s", prefix, arch_irn_flag_str(1 << i));
1389                                 prefix = "|";
1390                         }
1391                 }
1392                 prefix = ", ";
1393                 did_something = 1;
1394         }
1395
1396         if(req->req.cls != 0) {
1397                 char tmp[256];
1398                 fprintf(f, prefix);
1399                 arch_register_req_format(tmp, sizeof(tmp), &req->req);
1400                 fprintf(f, "%s", tmp);
1401                 did_something = 1;
1402         }
1403
1404         if(did_something)
1405                 fprintf(f, "\n");
1406 }
1407
1408 /**
1409  * Dumps node register requirements to a file.
1410  */
1411 static void dump_node_reqs(FILE *f, ir_node *irn)
1412 {
1413         int i;
1414         be_node_attr_t *a = get_irn_attr(irn);
1415
1416         fprintf(f, "registers: \n");
1417         for(i = 0; i < a->max_reg_data; ++i) {
1418                 be_reg_data_t *rd = &a->reg_data[i];
1419                 if(rd->reg)
1420                         fprintf(f, "#%d: %s\n", i, rd->reg->name);
1421         }
1422
1423         fprintf(f, "in requirements\n");
1424         for(i = 0; i < a->max_reg_data; ++i) {
1425                 dump_node_req(f, i, &a->reg_data[i].in_req);
1426         }
1427
1428         fprintf(f, "\nout requirements\n");
1429         for(i = 0; i < a->max_reg_data; ++i) {
1430                 dump_node_req(f, i, &a->reg_data[i].req);
1431         }
1432 }
1433
1434 /**
1435  * ir_op-Operation: dump a be node to file
1436  */
1437 static int dump_node(ir_node *irn, FILE *f, dump_reason_t reason)
1438 {
1439         be_node_attr_t *at = get_irn_attr(irn);
1440
1441         assert(is_be_node(irn));
1442
1443         switch(reason) {
1444                 case dump_node_opcode_txt:
1445                         fprintf(f, get_op_name(get_irn_op(irn)));
1446                         break;
1447                 case dump_node_mode_txt:
1448                         fprintf(f, get_mode_name(get_irn_mode(irn)));
1449                         break;
1450                 case dump_node_nodeattr_txt:
1451                         break;
1452                 case dump_node_info_txt:
1453                         dump_node_reqs(f, irn);
1454
1455                         if(be_has_frame_entity(irn)) {
1456                                 be_frame_attr_t *a = (be_frame_attr_t *) at;
1457                                 if (a->ent) {
1458                                         int bits = get_type_size_bits(get_entity_type(a->ent));
1459                                         ir_fprintf(f, "frame entity: %+F, offset 0x%x (%d), size 0x%x (%d) bits\n",
1460                                           a->ent, a->offset, a->offset, bits, bits);
1461                                 }
1462
1463                         }
1464
1465                         switch(be_get_irn_opcode(irn)) {
1466                         case beo_IncSP:
1467                                 {
1468                                         be_stack_attr_t *a = (be_stack_attr_t *) at;
1469                                         if (a->offset == BE_STACK_FRAME_SIZE_EXPAND)
1470                                                 fprintf(f, "offset: FRAME_SIZE\n");
1471                                         else if(a->offset == BE_STACK_FRAME_SIZE_SHRINK)
1472                                                 fprintf(f, "offset: -FRAME SIZE\n");
1473                                         else
1474                                                 fprintf(f, "offset: %u\n", a->offset);
1475                                 }
1476                                 break;
1477                         case beo_Call:
1478                                 {
1479                                         be_call_attr_t *a = (be_call_attr_t *) at;
1480
1481                                         if (a->ent)
1482                                                 fprintf(f, "\ncalling: %s\n", get_entity_name(a->ent));
1483                                 }
1484                                 break;
1485                         case beo_MemPerm:
1486                                 {
1487                                         int i;
1488                                         for(i = 0; i < be_get_MemPerm_entity_arity(irn); ++i) {
1489                                                 ir_entity *in, *out;
1490                                                 in = be_get_MemPerm_in_entity(irn, i);
1491                                                 out = be_get_MemPerm_out_entity(irn, i);
1492                                                 if(in) {
1493                                                         fprintf(f, "\nin[%d]: %s\n", i, get_entity_name(in));
1494                                                 }
1495                                                 if(out) {
1496                                                         fprintf(f, "\nout[%d]: %s\n", i, get_entity_name(out));
1497                                                 }
1498                                         }
1499                                 }
1500                                 break;
1501
1502                         default:
1503                                 break;
1504                         }
1505         }
1506
1507         return 0;
1508 }
1509
1510 /**
1511  * ir_op-Operation:
1512  * Copies the backend specific attributes from old node to new node.
1513  */
1514 static void copy_attr(const ir_node *old_node, ir_node *new_node)
1515 {
1516         be_node_attr_t *old_attr = get_irn_attr(old_node);
1517         be_node_attr_t *new_attr = get_irn_attr(new_node);
1518         int i;
1519
1520         assert(is_be_node(old_node));
1521         assert(is_be_node(new_node));
1522
1523         memcpy(new_attr, old_attr, get_op_attr_size(get_irn_op(old_node)));
1524         new_attr->reg_data = NULL;
1525
1526         if(new_attr->max_reg_data > 0) {
1527                 new_attr->reg_data = NEW_ARR_D(be_reg_data_t, get_irg_obstack(get_irn_irg(new_node)), new_attr->max_reg_data);
1528                 memcpy(new_attr->reg_data, old_attr->reg_data, new_attr->max_reg_data * sizeof(be_reg_data_t));
1529
1530                 for(i = 0; i < old_attr->max_reg_data; ++i) {
1531                         be_req_t *r;
1532
1533                         r = &new_attr->reg_data[i].req;
1534                         r->req.limited_env = r;
1535
1536                         r = &new_attr->reg_data[i].in_req;
1537                         r->req.limited_env = r;
1538                 }
1539         }
1540 }
1541
1542 static const ir_op_ops be_node_op_ops = {
1543         NULL,
1544         NULL,
1545         NULL,
1546         NULL,
1547         NULL,
1548         copy_attr,
1549         NULL,
1550         NULL,
1551         NULL,
1552         NULL,
1553         NULL,
1554         dump_node,
1555         NULL
1556 };