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

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