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