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

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