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