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

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