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

   1 /**
   2  * ABI lowering.
   3  *
   4  * @author Sebastian Hack
   5  * @date   7.3.2005
   6  * @cvsid  $Id$
   7  */
   8
   9 #ifdef HAVE_CONFIG_H
  10 # include "config.h"
  11 #endif
  12
  13 #include "obst.h"
  14 #include "offset.h"
  15
  16 #include "type.h"
  17 #include "irgopt.h"
  18
  19 #include "irgraph_t.h"
  20 #include "irnode_t.h"
  21 #include "ircons_t.h"
  22 #include "iredges_t.h"
  23 #include "irgmod.h"
  24 #include "irgwalk.h"
  25 #include "irprintf_t.h"
  26 #include "irgopt.h"
  27 #include "irbitset.h"
  28 #include "height.h"
  29 #include "pdeq.h"
  30 #include "irtools.h"
  31
  32 #include "be.h"
  33 #include "beabi.h"
  34 #include "bearch.h"
  35 #include "benode_t.h"
  36 #include "belive_t.h"
  37 #include "besched_t.h"
  38
  39 typedef struct _be_abi_call_arg_t {
  40         unsigned is_res   : 1;  /**< 1: the call argument is a return value. 0: it's a call parameter. */
  41         unsigned in_reg   : 1;  /**< 1: this argument is transmitted in registers. */
  42         unsigned on_stack : 1;  /**< 1: this argument is transmitted on the stack. */
  43
  44         int pos;
  45         const arch_register_t *reg;
  46         entity *stack_ent;
  47         unsigned alignment;
  48         unsigned space_before;
  49         unsigned space_after;
  50 } be_abi_call_arg_t;
  51
  52 struct _be_abi_call_t {
  53         be_abi_call_flags_t flags;
  54         const be_abi_callbacks_t *cb;
  55         ir_type *between_type;
  56         set *params;
  57 };
  58
  59 #define N_FRAME_TYPES 3
  60
  61 /**
  62  * This type describes the stack layout.
  63  * The stack is divided into 3 parts:
  64  * - arg_type:     A struct type describing the stack arguments and it's order.
  65  * - between_type: A struct type describing the stack layout between arguments
  66  *                 and frame type
  67  * - frame_type:   A class type descibing the frame layout
  68  */
  69 typedef struct _be_stack_layout_t {
  70         ir_type *arg_type;                 /**< A type describing the stack argument layout. */
  71         ir_type *between_type;             /**< A type describing the "between" layout. */
  72         ir_type *frame_type;               /**< The frame type. */
  73
  74         ir_type *order[N_FRAME_TYPES];     /**< arg, between and frame types ordered. */
  75
  76         int initial_offset;
  77         int stack_dir;                     /**< -1 for decreasing, 1 for increasing. */
  78 } be_stack_layout_t;
  79
  80 struct _be_abi_irg_t {
  81         struct obstack       obst;
  82         be_stack_layout_t    *frame;        /**< The stack frame model. */
  83         const be_irg_t       *birg;         /**< The back end IRG. */
  84         const arch_isa_t     *isa;          /**< The isa. */
  85         survive_dce_t        *dce_survivor;
  86
  87         be_abi_call_t        *call;         /**< The ABI call information. */
  88         ir_type              *method_type;  /**< The type of the method of the IRG. */
  89
  90         ir_node              *init_sp;      /**< The node representing the stack pointer
  91                                                                              at the start of the function. */
  92
  93         ir_node              *reg_params;   /**< The reg params node. */
  94         pmap                 *regs;         /**< A map of all callee-save and ignore regs to
  95                                                                                         their Projs to the RegParams node. */
  96
  97         pset                 *stack_phis;   /**< The set of all Phi nodes inserted due to
  98                                                                                         stack pointer modifying nodes. */
  99
 100         int                  start_block_bias;  /**< The stack bias at the end of the start block. */
 101
 102         void                 *cb;           /**< ABI Callback self pointer. */
 103
 104         pmap                 *keep_map;     /**< mapping blocks to keep nodes. */
 105         pset                 *ignore_regs;  /**< Additional registers which shall be ignored. */
 106
 107         arch_irn_handler_t irn_handler;
 108         arch_irn_ops_t     irn_ops;
 109         DEBUG_ONLY(firm_dbg_module_t    *dbg;)          /**< The debugging module. */
 110 };
 111
 112 #define get_abi_from_handler(ptr) firm_container_of(ptr, be_abi_irg_t, irn_handler)
 113 #define get_abi_from_ops(ptr)     firm_container_of(ptr, be_abi_irg_t, irn_ops)
 114
 115 /* Forward, since be need it in be_abi_introduce(). */
 116 static const arch_irn_ops_if_t abi_irn_ops;
 117 static const arch_irn_handler_t abi_irn_handler;
 118 static heights_t *ir_heights;
 119
 120 /* Flag: if set, try to omit the frame pointer if called by the backend */
 121 int be_omit_fp = 1;
 122
 123 /*
 124      _    ____ ___    ____      _ _ _                _
 125     / \  | __ )_ _|  / ___|__ _| | | |__   __ _  ___| | _____
 126    / _ \ |  _ \| |  | |   / _` | | | '_ \ / _` |/ __| |/ / __|
 127   / ___ \| |_) | |  | |__| (_| | | | |_) | (_| | (__|   <\__ \
 128  /_/   \_\____/___|  \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
 129
 130   These callbacks are used by the backend to set the parameters
 131   for a specific call type.
 132 */
 133
 134 /**
 135  * Set compare function: compares two ABI call object arguments.
 136  */
 137 static int cmp_call_arg(const void *a, const void *b, size_t n)
 138 {
 139         const be_abi_call_arg_t *p = a, *q = b;
 140         return !(p->is_res == q->is_res && p->pos == q->pos);
 141 }
 142
 143 /**
 144  * Get or set an ABI call object argument.
 145  *
 146  * @param call      the abi call
 147  * @param is_res    true for call results, false for call arguments
 148  * @param pos       position of the argument
 149  * @param do_insert true if the argument is set, false if it's retrieved
 150  */
 151 static be_abi_call_arg_t *get_or_set_call_arg(be_abi_call_t *call, int is_res, int pos, int do_insert)
 152 {
 153         be_abi_call_arg_t arg;
 154         unsigned hash;
 155
 156         memset(&arg, 0, sizeof(arg));
 157         arg.is_res = is_res;
 158         arg.pos    = pos;
 159
 160         hash = is_res * 128 + pos;
 161
 162         return do_insert
 163                 ? set_insert(call->params, &arg, sizeof(arg), hash)
 164                 : set_find(call->params, &arg, sizeof(arg), hash);
 165 }
 166
 167 /**
 168  * Retrieve an ABI call object argument.
 169  *
 170  * @param call      the ABI call object
 171  * @param is_res    true for call results, false for call arguments
 172  * @param pos       position of the argument
 173  */
 174 static INLINE be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
 175 {
 176         return get_or_set_call_arg(call, is_res, pos, 0);
 177 }
 178
 179 /* Set the flags for a call. */
 180 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
 181 {
 182         call->flags        = flags;
 183         call->cb           = cb;
 184 }
 185
 186 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos, unsigned alignment, unsigned space_before, unsigned space_after)
 187 {
 188         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
 189         arg->on_stack     = 1;
 190         arg->alignment    = alignment;
 191         arg->space_before = space_before;
 192         arg->space_after  = space_after;
 193         assert(alignment > 0 && "Alignment must be greater than 0");
 194 }
 195
 196 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
 197 {
 198         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
 199         arg->in_reg = 1;
 200         arg->reg = reg;
 201 }
 202
 203 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
 204 {
 205         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 1, arg_pos, 1);
 206         arg->in_reg = 1;
 207         arg->reg = reg;
 208 }
 209
 210 /* Get the flags of a ABI call object. */
 211 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
 212 {
 213         return call->flags;
 214 }
 215
 216 /**
 217  * Constructor for a new ABI call object.
 218  *
 219  * @return the new ABI call object
 220  */
 221 static be_abi_call_t *be_abi_call_new(void)
 222 {
 223         be_abi_call_t *call = xmalloc(sizeof(call[0]));
 224         call->flags.val  = 0;
 225         call->params     = new_set(cmp_call_arg, 16);
 226         call->cb         = NULL;
 227
 228         call->flags.bits.try_omit_fp = be_omit_fp;
 229         return call;
 230 }
 231
 232 /**
 233  * Destructor for an ABI call object.
 234  */
 235 static void be_abi_call_free(be_abi_call_t *call)
 236 {
 237         del_set(call->params);
 238         free(call);
 239 }
 240
 241 /*
 242   _____                           _   _                 _ _ _
 243  |  ___| __ __ _ _ __ ___   ___  | | | | __ _ _ __   __| | (_)_ __   __ _
 244  | |_ | '__/ _` | '_ ` _ \ / _ \ | |_| |/ _` | '_ \ / _` | | | '_ \ / _` |
 245  |  _|| | | (_| | | | | | |  __/ |  _  | (_| | | | | (_| | | | | | | (_| |
 246  |_|  |_|  \__,_|_| |_| |_|\___| |_| |_|\__,_|_| |_|\__,_|_|_|_| |_|\__, |
 247                                                                     |___/
 248
 249   Handling of the stack frame. It is composed of three types:
 250   1) The type of the arguments which are pushed on the stack.
 251   2) The "between type" which consists of stuff the call of the
 252      function pushes on the stack (like the return address and
 253          the old base pointer for ia32).
 254   3) The Firm frame type which consists of all local variables
 255      and the spills.
 256 */
 257
 258 static int get_stack_entity_offset(be_stack_layout_t *frame, entity *ent, int bias)
 259 {
 260         ir_type *t = get_entity_owner(ent);
 261         int ofs    = get_entity_offset_bytes(ent);
 262
 263         int i, index;
 264
 265         /* Find the type the entity is contained in. */
 266         for(index = 0; index < N_FRAME_TYPES; ++index) {
 267                 if(frame->order[index] == t)
 268                         break;
 269         }
 270
 271         /* Add the size of all the types below the one of the entity to the entity's offset */
 272         for(i = 0; i < index; ++i)
 273                 ofs += get_type_size_bytes(frame->order[i]);
 274
 275         /* correct the offset by the initial position of the frame pointer */
 276         ofs -= frame->initial_offset;
 277
 278         /* correct the offset with the current bias. */
 279         ofs += bias;
 280
 281         return ofs;
 282 }
 283
 284 /**
 285  * Retrieve the entity with given offset from a frame type.
 286  */
 287 static entity *search_ent_with_offset(ir_type *t, int offset)
 288 {
 289         int i, n;
 290
 291         for(i = 0, n = get_compound_n_members(t); i < n; ++i) {
 292                 entity *ent = get_compound_member(t, i);
 293                 if(get_entity_offset_bytes(ent) == offset)
 294                         return ent;
 295         }
 296
 297         return NULL;
 298 }
 299
 300 static int stack_frame_compute_initial_offset(be_stack_layout_t *frame)
 301 {
 302         ir_type *base = frame->stack_dir < 0 ? frame->between_type : frame->frame_type;
 303         entity *ent   = search_ent_with_offset(base, 0);
 304         frame->initial_offset = 0;
 305         frame->initial_offset = get_stack_entity_offset(frame, ent, 0);
 306         return frame->initial_offset;
 307 }
 308
 309 /**
 310  * Initializes the frame layout from parts
 311  *
 312  * @param frame     the stack layout that will be initialized
 313  * @param args      the stack argument layout type
 314  * @param between   the between layout type
 315  * @param locals    the method frame type
 316  * @param stack_dir the stack direction
 317  *
 318  * @return the initialized stack layout
 319  */
 320 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
 321                                            ir_type *between, ir_type *locals, int stack_dir)
 322 {
 323         frame->arg_type       = args;
 324         frame->between_type   = between;
 325         frame->frame_type     = locals;
 326         frame->initial_offset = 0;
 327         frame->stack_dir      = stack_dir;
 328         frame->order[1]       = between;
 329
 330         if(stack_dir > 0) {
 331                 frame->order[0] = args;
 332                 frame->order[2] = locals;
 333         }
 334         else {
 335                 frame->order[0] = locals;
 336                 frame->order[2] = args;
 337         }
 338         return frame;
 339 }
 340
 341 /** Dumps the stack layout to file. */
 342 static void stack_layout_dump(FILE *file, be_stack_layout_t *frame)
 343 {
 344         int i, j, n;
 345
 346         ir_fprintf(file, "initial offset: %d\n", frame->initial_offset);
 347         for (j = 0; j < N_FRAME_TYPES; ++j) {
 348                 ir_type *t = frame->order[j];
 349
 350                 ir_fprintf(file, "type %d: %F size: %d\n", j, t, get_type_size_bytes(t));
 351                 for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
 352                         entity *ent = get_compound_member(t, i);
 353                         ir_fprintf(file, "\t%F int ofs: %d glob ofs: %d\n", ent, get_entity_offset_bytes(ent), get_stack_entity_offset(frame, ent, 0));
 354                 }
 355         }
 356 }
 357
 358 /**
 359  * Returns non-zero if the call argument at given position
 360  * is transfered on the stack.
 361  */
 362 static INLINE int is_on_stack(be_abi_call_t *call, int pos)
 363 {
 364         be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
 365         return arg && !arg->in_reg;
 366 }
 367
 368 /*
 369    ____      _ _
 370   / ___|__ _| | |___
 371  | |   / _` | | / __|
 372  | |__| (_| | | \__ \
 373   \____\__,_|_|_|___/
 374
 375   Adjustment of the calls inside a graph.
 376
 377 */
 378
 379 /**
 380  * Transform a call node.
 381  * @param env The ABI environment for the current irg.
 382  * @param irn The call node.
 383  * @param curr_sp The stack pointer node to use.
 384  * @return The stack pointer after the call.
 385  */
 386 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp, ir_node *alloca_copy)
 387 {
 388         ir_graph *irg             = env->birg->irg;
 389         const arch_isa_t *isa     = env->birg->main_env->arch_env->isa;
 390         be_abi_call_t *call       = be_abi_call_new();
 391         ir_type *mt               = get_Call_type(irn);
 392         ir_node *call_ptr         = get_Call_ptr(irn);
 393         int n_params              = get_method_n_params(mt);
 394         ir_node *curr_mem         = get_Call_mem(irn);
 395         ir_node *bl               = get_nodes_block(irn);
 396         pset *results             = pset_new_ptr(8);
 397         pset *caller_save         = pset_new_ptr(8);
 398         int stack_size            = 0;
 399         int stack_dir             = arch_isa_stack_dir(isa);
 400         const arch_register_t *sp = arch_isa_sp(isa);
 401         ir_mode *mach_mode        = sp->reg_class->mode;
 402         struct obstack *obst      = &env->obst;
 403         int no_alloc              = call->flags.bits.frame_is_setup_on_call;
 404
 405         ir_node *res_proj = NULL;
 406         int curr_res_proj = pn_Call_max;
 407         int n_low_args    = 0;
 408         int n_pos         = 0;
 409
 410         ir_node *low_call;
 411         ir_node **in;
 412         ir_node **res_projs;
 413         const ir_edge_t *edge;
 414         int *low_args;
 415         int *pos;
 416         int i, n;
 417
 418         /* Let the isa fill out the abi description for that call node. */
 419         arch_isa_get_call_abi(isa, mt, call);
 420
 421         /* Insert code to put the stack arguments on the stack. */
 422         assert(get_Call_n_params(irn) == n_params);
 423         for(i = 0; i < n_params; ++i) {
 424                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 425                 assert(arg);
 426                 if(arg->on_stack) {
 427                         stack_size += arg->space_before;
 428                         stack_size =  round_up2(stack_size, arg->alignment);
 429                         stack_size += get_type_size_bytes(get_method_param_type(mt, i));
 430                         stack_size += arg->space_after;
 431                         obstack_int_grow(obst, i);
 432                         n_pos++;
 433                 }
 434         }
 435         pos = obstack_finish(obst);
 436
 437         /* Collect all arguments which are passed in registers. */
 438         for(i = 0, n = get_Call_n_params(irn); i < n; ++i) {
 439                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 440                 if(arg && arg->in_reg) {
 441                         obstack_int_grow(obst, i);
 442                         n_low_args++;
 443                 }
 444         }
 445         low_args = obstack_finish(obst);
 446
 447         /* If there are some parameters which shall be passed on the stack. */
 448         if(n_pos > 0) {
 449                 int curr_ofs      = 0;
 450                 int do_seq        = call->flags.bits.store_args_sequential && !no_alloc;
 451
 452                 /*
 453                  * Reverse list of stack parameters if call arguments are from left to right.
 454                  * We must them reverse again in they are pushed (not stored) and the stack
 455                  * direction is downwards.
 456                  */
 457                 if (call->flags.bits.left_to_right ^ (do_seq && stack_dir < 0)) {
 458                         for(i = 0; i < n_pos >> 1; ++i) {
 459                                 int other  = n_pos - i - 1;
 460                                 int tmp    = pos[i];
 461                                 pos[i]     = pos[other];
 462                                 pos[other] = tmp;
 463                         }
 464                 }
 465
 466                 /*
 467                  * If the stack is decreasing and we do not want to store sequentially,
 468                  * or someone else allocated the call frame
 469                  * we allocate as much space on the stack all parameters need, by
 470                  * moving the stack pointer along the stack's direction.
 471                  */
 472                 if(stack_dir < 0 && !do_seq && !no_alloc) {
 473                         curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, stack_size);
 474                         if(alloca_copy) {
 475                                 add_irn_dep(curr_sp, alloca_copy);
 476                                 alloca_copy = NULL;
 477                         }
 478                 }
 479
 480                 if(!do_seq) {
 481                         obstack_ptr_grow(obst, get_Call_mem(irn));
 482                         curr_mem = new_NoMem();
 483                 } else {
 484                         curr_mem = get_Call_mem(irn);
 485                 }
 486
 487                 assert(mode_is_reference(mach_mode) && "machine mode must be pointer");
 488                 for(i = 0; i < n_pos; ++i) {
 489                         int p                  = pos[i];
 490                         be_abi_call_arg_t *arg = get_call_arg(call, 0, p);
 491                         ir_node *param         = get_Call_param(irn, p);
 492                         ir_node *addr          = curr_sp;
 493                         ir_node *mem           = NULL;
 494                         ir_type *param_type    = get_method_param_type(mt, p);
 495                         int param_size         = get_type_size_bytes(param_type) + arg->space_after;
 496
 497                         /*
 498                          * If we wanted to build the arguments sequentially,
 499                          * the stack pointer for the next must be incremented,
 500                          * and the memory value propagated.
 501                          */
 502                         if (do_seq) {
 503                                 curr_ofs = 0;
 504                                 addr = curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, param_size + arg->space_before);
 505                                 if(alloca_copy) {
 506                                         add_irn_dep(curr_sp, alloca_copy);
 507                                         alloca_copy = NULL;
 508                                 }
 509                                 add_irn_dep(curr_sp, curr_mem);
 510                         }
 511                         else {
 512                                 curr_ofs += arg->space_before;
 513                                 curr_ofs =  round_up2(curr_ofs, arg->alignment);
 514
 515                                 /* Make the expression to compute the argument's offset. */
 516                                 if(curr_ofs > 0) {
 517                                         addr = new_r_Const_long(irg, bl, mode_Is, curr_ofs);
 518                                         addr = new_r_Add(irg, bl, curr_sp, addr, mach_mode);
 519                                 }
 520                         }
 521
 522                         /* Insert a store for primitive arguments. */
 523                         if (is_atomic_type(param_type)) {
 524                                 ir_node *store;
 525                                 store = new_r_Store(irg, bl, curr_mem, addr, param);
 526                                 mem = new_r_Proj(irg, bl, store, mode_M, pn_Store_M);
 527                         }
 528
 529                         /* Make a mem copy for compound arguments. */
 530                         else {
 531                                 ir_node *copy;
 532
 533                                 assert(mode_is_reference(get_irn_mode(param)));
 534                                 copy = new_r_CopyB(irg, bl, curr_mem, addr, param, param_type);
 535                                 mem = new_r_Proj(irg, bl, copy, mode_M, pn_CopyB_M_regular);
 536                         }
 537
 538                         curr_ofs += param_size;
 539
 540                         if (do_seq)
 541                                 curr_mem = mem;
 542                         else
 543                                 obstack_ptr_grow(obst, mem);
 544                 }
 545
 546                 in = (ir_node **) obstack_finish(obst);
 547
 548                 /* We need the sync only, if we didn't build the stores sequentially. */
 549                 if(!do_seq) {
 550                         if(n_pos >= 1) {
 551                                 curr_mem = new_r_Sync(irg, bl, n_pos + 1, in);
 552                         } else {
 553                                 curr_mem = get_Call_mem(irn);
 554                         }
 555                 }
 556                 obstack_free(obst, in);
 557         }
 558
 559         /* Collect caller save registers */
 560         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
 561                 int j;
 562                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
 563                 for(j = 0; j < cls->n_regs; ++j) {
 564                         const arch_register_t *reg = arch_register_for_index(cls, j);
 565                         if(arch_register_type_is(reg, caller_save))
 566                                 pset_insert_ptr(caller_save, (void *) reg);
 567                 }
 568         }
 569
 570         /* search the greatest result proj number */
 571
 572         /* TODO: what if the result is NOT used? Currently there is
 573          * no way to detect this later, especially there is no way to
 574          * see this in the proj numbers.
 575          * While this is ok for the register allocator, it is bad for
 576          * backends which need to change the be_Call further (x87 simulator
 577          * for instance. However for this particular case the call_type is
 578          * sufficient.).
 579          */
 580         foreach_out_edge(irn, edge) {
 581                 const ir_edge_t *res_edge;
 582                 ir_node *irn = get_edge_src_irn(edge);
 583
 584                 if(is_Proj(irn) && get_Proj_proj(irn) == pn_Call_T_result) {
 585                         res_proj = irn;
 586                         foreach_out_edge(irn, res_edge) {
 587                                 int proj;
 588                                 be_abi_call_arg_t *arg;
 589                                 ir_node *res = get_edge_src_irn(res_edge);
 590
 591                                 assert(is_Proj(res));
 592
 593                                 proj = get_Proj_proj(res);
 594                                 arg = get_call_arg(call, 1, proj);
 595
 596                                 /*
 597                                         shift the proj number to the right, since we will drop the
 598                                         unspeakable Proj_T from the Call. Therefore, all real argument
 599                                         Proj numbers must be increased by pn_be_Call_first_res
 600                                 */
 601                                 proj += pn_be_Call_first_res;
 602                                 set_Proj_proj(res, proj);
 603                                 obstack_ptr_grow(obst, res);
 604
 605                                 if(proj > curr_res_proj)
 606                                         curr_res_proj = proj;
 607                                 if(arg->in_reg) {
 608                                         pset_remove_ptr(caller_save, arg->reg);
 609                                         //pmap_insert(arg_regs, arg->reg, INT_TO_PTR(proj + 1))
 610                                 }
 611                         }
 612                 }
 613         }
 614
 615         curr_res_proj++;
 616         obstack_ptr_grow(obst, NULL);
 617         res_projs = obstack_finish(obst);
 618
 619         /* make the back end call node and set its register requirements. */
 620         for(i = 0; i < n_low_args; ++i)
 621                 obstack_ptr_grow(obst, get_Call_param(irn, low_args[i]));
 622
 623         in = obstack_finish(obst);
 624
 625         if(env->call->flags.bits.call_has_imm && get_irn_opcode(call_ptr) == iro_SymConst) {
 626                 low_call = be_new_Call(get_irn_dbg_info(irn), irg, bl, curr_mem, curr_sp, curr_sp,
 627                                        curr_res_proj + pset_count(caller_save), n_low_args, in,
 628                                        get_Call_type(irn));
 629                 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
 630         }
 631
 632         else
 633                 low_call = be_new_Call(get_irn_dbg_info(irn), irg, bl, curr_mem, curr_sp, call_ptr,
 634                                        curr_res_proj + pset_count(caller_save), n_low_args, in,
 635                                        get_Call_type(irn));
 636
 637         /*
 638                 TODO:
 639                 Set the register class of the call address to the same as the stack pointer's.
 640                 That' probably buggy for some architectures.
 641         */
 642         be_node_set_reg_class(low_call, be_pos_Call_ptr, sp->reg_class);
 643
 644         DBG((env->dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
 645
 646         /* Set the register classes and constraints of the Call parameters. */
 647         for(i = 0; i < n_low_args; ++i) {
 648                 int index = low_args[i];
 649                 be_abi_call_arg_t *arg = get_call_arg(call, 0, index);
 650                 assert(arg->reg != NULL);
 651
 652                 be_set_constr_single_reg(low_call, be_pos_Call_first_arg + index, arg->reg);
 653         }
 654
 655         /* Set the register constraints of the results. */
 656         for(i = 0; res_projs[i]; ++i) {
 657                 ir_node *irn                 = res_projs[i];
 658                 int proj                     = get_Proj_proj(irn);
 659
 660                 /* Correct Proj number since it has been adjusted! (see above) */
 661                 const be_abi_call_arg_t *arg = get_call_arg(call, 1, proj - pn_Call_max);
 662
 663                 assert(arg->in_reg);
 664                 be_set_constr_single_reg(low_call, BE_OUT_POS(proj), arg->reg);
 665         }
 666         obstack_free(obst, in);
 667         exchange(irn, low_call);
 668
 669         /* redirect the result projs to the lowered call instead of the Proj_T */
 670         for(i = 0; res_projs[i]; ++i)
 671                 set_Proj_pred(res_projs[i], low_call);
 672
 673         /* Make additional projs for the caller save registers
 674            and the Keep node which keeps them alive. */
 675         if(pset_count(caller_save) > 0) {
 676                 const arch_register_t *reg;
 677                 ir_node **in, *keep;
 678                 int i, n;
 679
 680                 for(reg = pset_first(caller_save), n = 0; reg; reg = pset_next(caller_save), ++n) {
 681                         ir_node *proj = new_r_Proj(irg, bl, low_call, reg->reg_class->mode, curr_res_proj);
 682
 683                         /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
 684                         be_set_constr_single_reg(low_call, BE_OUT_POS(curr_res_proj), reg);
 685                         set_irn_link(proj, (void *) reg);
 686                         obstack_ptr_grow(obst, proj);
 687                         curr_res_proj++;
 688                 }
 689
 690                 in   = (ir_node **) obstack_finish(obst);
 691                 keep = be_new_Keep(NULL, irg, bl, n, in);
 692                 for(i = 0; i < n; ++i) {
 693                         const arch_register_t *reg = get_irn_link(in[i]);
 694                         be_node_set_reg_class(keep, i, reg->reg_class);
 695                 }
 696                 obstack_free(obst, in);
 697         }
 698
 699         /* Clean up the stack. */
 700         if(stack_size > 0) {
 701                 ir_node *mem_proj = NULL;
 702
 703                 foreach_out_edge(low_call, edge) {
 704                         ir_node *irn = get_edge_src_irn(edge);
 705                         if(is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
 706                                 mem_proj = irn;
 707                                 break;
 708                         }
 709                 }
 710
 711                 if(!mem_proj) {
 712                         mem_proj = new_r_Proj(irg, bl, low_call, mode_M, pn_Call_M);
 713                         keep_alive(mem_proj);
 714                 }
 715
 716                  /* Clean up the stack frame if we allocated it */
 717                 if(!no_alloc) {
 718                         curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, -stack_size);
 719                         add_irn_dep(curr_sp, mem_proj);
 720                         if(alloca_copy) {
 721                                 add_irn_dep(curr_sp, alloca_copy);
 722                                 alloca_copy = NULL;
 723                         }
 724                 }
 725         }
 726
 727         be_abi_call_free(call);
 728         obstack_free(obst, pos);
 729         del_pset(results);
 730         del_pset(caller_save);
 731
 732         return curr_sp;
 733 }
 734
 735 /**
 736  * Adjust an alloca.
 737  * The alloca is transformed into a back end alloca node and connected to the stack nodes.
 738  */
 739 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp, ir_node **result_copy)
 740 {
 741         if (get_Alloc_where(alloc) == stack_alloc) {
 742                 ir_node *bl        = get_nodes_block(alloc);
 743                 ir_graph *irg      = get_irn_irg(bl);
 744                 ir_node *alloc_mem = NULL;
 745                 ir_node *alloc_res = NULL;
 746
 747                 const ir_edge_t *edge;
 748                 ir_node *new_alloc;
 749                 ir_node *addr;
 750                 ir_node *copy;
 751
 752                 foreach_out_edge(alloc, edge) {
 753                         ir_node *irn = get_edge_src_irn(edge);
 754
 755                         assert(is_Proj(irn));
 756                         switch(get_Proj_proj(irn)) {
 757                         case pn_Alloc_M:
 758                                 alloc_mem = irn;
 759                                 break;
 760                         case pn_Alloc_res:
 761                                 alloc_res = irn;
 762                                 break;
 763                         default:
 764                                 break;
 765                         }
 766                 }
 767
 768                 /* Beware: currently Alloc nodes without a result might happen,
 769                    only escape analysis kills them and this phase runs only for object
 770                    oriented source. We kill the Alloc here. */
 771                 if (alloc_res == NULL && alloc_mem) {
 772                         exchange(alloc_mem, get_Alloc_mem(alloc));
 773                         return curr_sp;
 774                 }
 775
 776                 /* The stack pointer will be modified in an unknown manner.
 777                    We cannot omit it. */
 778                 env->call->flags.bits.try_omit_fp = 0;
 779                 new_alloc = be_new_AddSP(env->isa->sp, irg, bl, curr_sp, get_Alloc_size(alloc));
 780
 781                 exchange(alloc, new_alloc);
 782
 783                 if(alloc_mem != NULL)
 784                         set_Proj_proj(alloc_mem, pn_be_AddSP_M);
 785
 786                 /* fix projnum of alloca res */
 787                 set_Proj_proj(alloc_res, pn_be_AddSP_res);
 788
 789                 addr = env->isa->stack_dir < 0 ? alloc_res : curr_sp;
 790
 791                 /* copy the address away, since it could be used after further stack pointer modifications. */
 792                 /* Let it point curr_sp just for the moment, I'll reroute it in a second. */
 793                 *result_copy = copy = be_new_Copy(env->isa->sp->reg_class, irg, bl, curr_sp);
 794
 795                 /* Let all users of the Alloc() result now point to the copy. */
 796                 edges_reroute(alloc_res, copy, irg);
 797
 798                 /* Rewire the copy appropriately. */
 799                 set_irn_n(copy, be_pos_Copy_op, addr);
 800
 801                 curr_sp = alloc_res;
 802         }
 803
 804         return curr_sp;
 805 }
 806
 807 /* the following function is replaced by the usage of the heights module */
 808 #if 0
 809 /**
 810  * Walker for dependent_on().
 811  * This function searches a node tgt recursively from a given node
 812  * but is restricted to the given block.
 813  * @return 1 if tgt was reachable from curr, 0 if not.
 814  */
 815 static int check_dependence(ir_node *curr, ir_node *tgt, ir_node *bl)
 816 {
 817         int n, i;
 818
 819         if (get_nodes_block(curr) != bl)
 820                 return 0;
 821
 822         if (curr == tgt)
 823                 return 1;
 824
 825         /* Phi functions stop the recursion inside a basic block */
 826         if (! is_Phi(curr)) {
 827                 for(i = 0, n = get_irn_arity(curr); i < n; ++i) {
 828                         if (check_dependence(get_irn_n(curr, i), tgt, bl))
 829                                 return 1;
 830                 }
 831         }
 832
 833         return 0;
 834 }
 835 #endif /* if 0 */
 836
 837 /**
 838  * Check if a node is somehow data dependent on another one.
 839  * both nodes must be in the same basic block.
 840  * @param n1 The first node.
 841  * @param n2 The second node.
 842  * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
 843  */
 844 static int dependent_on(ir_node *n1, ir_node *n2)
 845 {
 846         ir_node *bl   = get_nodes_block(n1);
 847
 848         assert(bl == get_nodes_block(n2));
 849
 850         return heights_reachable_in_block(ir_heights, n1, n2);
 851         //return check_dependence(n1, n2, bl);
 852 }
 853
 854 static int cmp_call_dependecy(const void *c1, const void *c2)
 855 {
 856         ir_node *n1 = *(ir_node **) c1;
 857         ir_node *n2 = *(ir_node **) c2;
 858
 859         /*
 860                 Classical qsort() comparison function behavior:
 861                 0  if both elements are equal
 862                 1  if second is "smaller" that first
 863                 -1 if first is "smaller" that second
 864         */
 865         if (dependent_on(n1, n2))
 866                 return -1;
 867
 868         if (dependent_on(n2, n1))
 869                 return 1;
 870
 871         return 0;
 872 }
 873
 874 /**
 875  * Walker: links all Call nodes to the Block they are contained.
 876  */
 877 static void link_calls_in_block_walker(ir_node *irn, void *data)
 878 {
 879         if(is_Call(irn) || (get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc)) {
 880                 be_abi_irg_t *env = data;
 881                 ir_node *bl       = get_nodes_block(irn);
 882                 void *save        = get_irn_link(bl);
 883
 884                 if (is_Call(irn))
 885                         env->call->flags.bits.irg_is_leaf = 0;
 886
 887                 set_irn_link(irn, save);
 888                 set_irn_link(bl, irn);
 889         }
 890 }
 891
 892 /**
 893  * Block-walker:
 894  * Process all Call nodes inside a basic block.
 895  * Note that the link field of the block must contain a linked list of all
 896  * Call nodes inside the Block. We first order this list according to data dependency
 897  * and that connect the calls together.
 898  */
 899 static void process_calls_in_block(ir_node *bl, void *data)
 900 {
 901         be_abi_irg_t *env = data;
 902         ir_node *curr_sp  = env->init_sp;
 903         ir_node *irn;
 904         int n;
 905
 906         for(irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
 907                 obstack_ptr_grow(&env->obst, irn);
 908
 909         /* If there were call nodes in the block. */
 910         if(n > 0) {
 911                 ir_node *keep;
 912                 ir_node **nodes;
 913                 ir_node *copy = NULL;
 914                 int i;
 915
 916                 nodes = obstack_finish(&env->obst);
 917
 918                 /* order the call nodes according to data dependency */
 919                 qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependecy);
 920
 921                 for(i = n - 1; i >= 0; --i) {
 922                         ir_node *irn = nodes[i];
 923
 924                         DBG((env->dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
 925                         switch(get_irn_opcode(irn)) {
 926                         case iro_Call:
 927                                 curr_sp = adjust_call(env, irn, curr_sp, copy);
 928                                 break;
 929                         case iro_Alloc:
 930                                 curr_sp = adjust_alloc(env, irn, curr_sp, &copy);
 931                                 break;
 932                         default:
 933                                 break;
 934                         }
 935                 }
 936
 937                 obstack_free(&env->obst, nodes);
 938
 939                 /* Keep the last stack state in the block by tying it to Keep node */
 940                 nodes[0] = curr_sp;
 941                 keep     = be_new_Keep(env->isa->sp->reg_class, get_irn_irg(bl), bl, 1, nodes);
 942                 pmap_insert(env->keep_map, bl, keep);
 943         }
 944
 945         set_irn_link(bl, curr_sp);
 946 }
 947
 948 /**
 949  * Adjust all call nodes in the graph to the ABI conventions.
 950  */
 951 static void process_calls(be_abi_irg_t *env)
 952 {
 953         ir_graph *irg = env->birg->irg;
 954
 955         env->call->flags.bits.irg_is_leaf = 1;
 956         irg_walk_graph(irg, firm_clear_link, link_calls_in_block_walker, env);
 957
 958         ir_heights = heights_new(env->birg->irg);
 959         irg_block_walk_graph(irg, NULL, process_calls_in_block, env);
 960         heights_free(ir_heights);
 961 }
 962
 963 static void collect_return_walker(ir_node *irn, void *data)
 964 {
 965         if(get_irn_opcode(irn) == iro_Return) {
 966                 struct obstack *obst = data;
 967                 obstack_ptr_grow(obst, irn);
 968         }
 969 }
 970
 971 #if 0 /*
 972 static ir_node *setup_frame(be_abi_irg_t *env)
 973 {
 974         const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
 975         const arch_register_t *sp = isa->sp;
 976         const arch_register_t *bp = isa->bp;
 977         be_abi_call_flags_bits_t flags = env->call->flags.bits;
 978         ir_graph *irg      = env->birg->irg;
 979         ir_node *bl        = get_irg_start_block(irg);
 980         ir_node *no_mem    = get_irg_no_mem(irg);
 981         ir_node *old_frame = get_irg_frame(irg);
 982         ir_node *stack     = pmap_get(env->regs, (void *) sp);
 983         ir_node *frame     = pmap_get(env->regs, (void *) bp);
 984
 985         int stack_nr       = get_Proj_proj(stack);
 986
 987         if(flags.try_omit_fp) {
 988                 stack = be_new_IncSP(sp, irg, bl, stack, no_mem, BE_STACK_FRAME_SIZE_EXPAND);
 989                 frame = stack;
 990         }
 991
 992         else {
 993                 frame = be_new_Copy(bp->reg_class, irg, bl, stack);
 994
 995                 be_node_set_flags(frame, -1, arch_irn_flags_dont_spill);
 996                 if(!flags.fp_free) {
 997                         be_set_constr_single_reg(frame, -1, bp);
 998                         be_node_set_flags(frame, -1, arch_irn_flags_ignore);
 999                         arch_set_irn_register(env->birg->main_env->arch_env, frame, bp);
1000                 }
1001
1002                 stack = be_new_IncSP(sp, irg, bl, stack, frame, BE_STACK_FRAME_SIZE_EXPAND);
1003         }
1004
1005         be_node_set_flags(env->reg_params, -(stack_nr + 1), arch_irn_flags_ignore);
1006         env->init_sp = stack;
1007         set_irg_frame(irg, frame);
1008         edges_reroute(old_frame, frame, irg);
1009
1010         return frame;
1011 }
1012
1013 static void clearup_frame(be_abi_irg_t *env, ir_node *ret, pmap *reg_map, struct obstack *obst)
1014 {
1015         const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
1016         const arch_register_t *sp = isa->sp;
1017         const arch_register_t *bp = isa->bp;
1018         ir_graph *irg      = env->birg->irg;
1019         ir_node *ret_mem   = get_Return_mem(ret);
1020         ir_node *frame     = get_irg_frame(irg);
1021         ir_node *bl        = get_nodes_block(ret);
1022         ir_node *stack     = get_irn_link(bl);
1023
1024         pmap_entry *ent;
1025
1026         if(env->call->flags.bits.try_omit_fp) {
1027                 stack = be_new_IncSP(sp, irg, bl, stack, ret_mem, -BE_STACK_FRAME_SIZE_SHRINK);
1028         }
1029
1030         else {
1031                 stack = be_new_SetSP(sp, irg, bl, stack, frame, ret_mem);
1032                 be_set_constr_single_reg(stack, -1, sp);
1033                 be_node_set_flags(stack, -1, arch_irn_flags_ignore);
1034         }
1035
1036         pmap_foreach(env->regs, ent) {
1037                 const arch_register_t *reg = ent->key;
1038                 ir_node *irn               = ent->value;
1039
1040                 if(reg == sp)
1041                         obstack_ptr_grow(&env->obst, stack);
1042                 else if(reg == bp)
1043                         obstack_ptr_grow(&env->obst, frame);
1044                 else if(arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1045                         obstack_ptr_grow(obst, irn);
1046         }
1047 }
1048 */
1049 #endif
1050
1051 /**
1052  * Computes the stack argument layout type.
1053  * Changes a possibly allocated value param type by moving
1054  * entities to the stack layout type.
1055  *
1056  * @param env          the ABI environment
1057  * @param call         the current call ABI
1058  * @param method_type  the method type
1059  *
1060  * @return the stack argument layout type
1061  */
1062 static ir_type *compute_arg_type(be_abi_irg_t *env, be_abi_call_t *call, ir_type *method_type)
1063 {
1064         int dir  = env->call->flags.bits.left_to_right ? 1 : -1;
1065         int inc  = env->birg->main_env->arch_env->isa->stack_dir * dir;
1066         int n    = get_method_n_params(method_type);
1067         int curr = inc > 0 ? 0 : n - 1;
1068         int ofs  = 0;
1069
1070         char buf[128];
1071         ir_type *res;
1072         int i;
1073         ir_type *val_param_tp = get_method_value_param_type(method_type);
1074         ident *id = get_entity_ident(get_irg_entity(env->birg->irg));
1075
1076         res = new_type_struct(mangle_u(id, new_id_from_chars("arg_type", 8)));
1077         for (i = 0; i < n; ++i, curr += inc) {
1078                 ir_type *param_type    = get_method_param_type(method_type, curr);
1079                 be_abi_call_arg_t *arg = get_call_arg(call, 0, curr);
1080
1081                 if (arg->on_stack) {
1082                         if (val_param_tp) {
1083                                 /* the entity was already created, move it to the param type */
1084                                 arg->stack_ent = get_method_value_param_ent(method_type, i);
1085                                 remove_struct_member(val_param_tp, arg->stack_ent);
1086                                 set_entity_owner(arg->stack_ent, res);
1087                                 add_struct_member(res, arg->stack_ent);
1088                                 /* must be automatic to set a fixed layout */
1089                                 set_entity_allocation(arg->stack_ent, allocation_automatic);
1090                         }
1091                         else {
1092                                 snprintf(buf, sizeof(buf), "param_%d", i);
1093                                 arg->stack_ent = new_entity(res, new_id_from_str(buf), param_type);
1094                         }
1095                         ofs += arg->space_before;
1096                         ofs = round_up2(ofs, arg->alignment);
1097                         set_entity_offset_bytes(arg->stack_ent, ofs);
1098                         ofs += arg->space_after;
1099                         ofs += get_type_size_bytes(param_type);
1100                 }
1101         }
1102         set_type_size_bytes(res, ofs);
1103         set_type_state(res, layout_fixed);
1104         return res;
1105 }
1106
1107 static void create_register_perms(const arch_isa_t *isa, ir_graph *irg, ir_node *bl, pmap *regs)
1108 {
1109         int i, j, n;
1110         struct obstack obst;
1111
1112         obstack_init(&obst);
1113
1114         /* Create a Perm after the RegParams node to delimit it. */
1115         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
1116                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
1117                 ir_node *perm;
1118                 ir_node **in;
1119                 int n_regs;
1120
1121                 for(n_regs = 0, j = 0; j < cls->n_regs; ++j) {
1122                         const arch_register_t *reg = &cls->regs[j];
1123                         ir_node *irn = pmap_get(regs, (void *) reg);
1124
1125                         if(irn && !arch_register_type_is(reg, ignore)) {
1126                                 n_regs++;
1127                                 obstack_ptr_grow(&obst, irn);
1128                                 set_irn_link(irn, (void *) reg);
1129                         }
1130                 }
1131
1132                 obstack_ptr_grow(&obst, NULL);
1133                 in = obstack_finish(&obst);
1134                 if(n_regs > 0) {
1135                         perm = be_new_Perm(cls, irg, bl, n_regs, in);
1136                         for(j = 0; j < n_regs; ++j) {
1137                                 ir_node *arg = in[j];
1138                                 arch_register_t *reg = get_irn_link(arg);
1139                                 pmap_insert(regs, reg, arg);
1140                                 be_set_constr_single_reg(perm, BE_OUT_POS(j), reg);
1141                         }
1142                 }
1143                 obstack_free(&obst, in);
1144         }
1145
1146         obstack_free(&obst, NULL);
1147 }
1148
1149 typedef struct {
1150         const arch_register_t *reg;
1151         ir_node *irn;
1152 } reg_node_map_t;
1153
1154 static int cmp_regs(const void *a, const void *b)
1155 {
1156         const reg_node_map_t *p = a;
1157         const reg_node_map_t *q = b;
1158
1159         if(p->reg->reg_class == q->reg->reg_class)
1160                 return p->reg->index - q->reg->index;
1161         else
1162                 return p->reg->reg_class - q->reg->reg_class;
1163 }
1164
1165 static reg_node_map_t *reg_map_to_arr(struct obstack *obst, pmap *reg_map)
1166 {
1167         pmap_entry *ent;
1168         int n = pmap_count(reg_map);
1169         int i = 0;
1170         reg_node_map_t *res = obstack_alloc(obst, n * sizeof(res[0]));
1171
1172         pmap_foreach(reg_map, ent) {
1173                 res[i].reg = ent->key;
1174                 res[i].irn = ent->value;
1175                 i++;
1176         }
1177
1178         qsort(res, n, sizeof(res[0]), cmp_regs);
1179         return res;
1180 }
1181
1182 /**
1183  * Creates a barrier.
1184  */
1185 static ir_node *create_barrier(be_abi_irg_t *env, ir_node *bl, ir_node **mem, pmap *regs, int in_req)
1186 {
1187         ir_graph *irg = env->birg->irg;
1188         int n_regs    = pmap_count(regs);
1189         int n;
1190         ir_node *irn;
1191         ir_node **in;
1192         reg_node_map_t *rm;
1193
1194         rm = reg_map_to_arr(&env->obst, regs);
1195
1196         for(n = 0; n < n_regs; ++n)
1197                 obstack_ptr_grow(&env->obst, rm[n].irn);
1198
1199         if(mem) {
1200                 obstack_ptr_grow(&env->obst, *mem);
1201                 n++;
1202         }
1203
1204         in = (ir_node **) obstack_finish(&env->obst);
1205         irn = be_new_Barrier(irg, bl, n, in);
1206         obstack_free(&env->obst, in);
1207
1208         for(n = 0; n < n_regs; ++n) {
1209                 const arch_register_t *reg = rm[n].reg;
1210                 int flags                  = 0;
1211                 int pos                    = BE_OUT_POS(n);
1212                 ir_node *proj;
1213
1214                 proj = new_r_Proj(irg, bl, irn, get_irn_mode(rm[n].irn), n);
1215                 be_node_set_reg_class(irn, n, reg->reg_class);
1216                 if(in_req)
1217                         be_set_constr_single_reg(irn, n, reg);
1218                 be_set_constr_single_reg(irn, pos, reg);
1219                 be_node_set_reg_class(irn, pos, reg->reg_class);
1220                 arch_set_irn_register(env->birg->main_env->arch_env, proj, reg);
1221
1222                 /* if the proj projects a ignore register or a node which is set to ignore, propagate this property. */
1223                 if(arch_register_type_is(reg, ignore) || arch_irn_is(env->birg->main_env->arch_env, in[n], ignore))
1224                         flags |= arch_irn_flags_ignore;
1225
1226                 if(arch_irn_is(env->birg->main_env->arch_env, in[n], modify_sp))
1227                         flags |= arch_irn_flags_modify_sp;
1228
1229                 be_node_set_flags(irn, pos, flags);
1230
1231                 pmap_insert(regs, (void *) reg, proj);
1232         }
1233
1234         if(mem) {
1235                 *mem = new_r_Proj(irg, bl, irn, mode_M, n);
1236         }
1237
1238         obstack_free(&env->obst, rm);
1239         return irn;
1240 }
1241
1242 /**
1243  * Creates a be_Return for a Return node.
1244  *
1245  * @param @env    the abi environment
1246  * @param irn     the Return node or NULL if there was none
1247  * @param bl      the block where the be_Retun should be placed
1248  * @param mem     the current memory
1249  * @param n_res   number of return results
1250  */
1251 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl, ir_node *mem, int n_res) {
1252         be_abi_call_t *call = env->call;
1253         const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
1254
1255         pmap *reg_map  = pmap_create();
1256         ir_node *keep  = pmap_get(env->keep_map, bl);
1257         int in_max;
1258         ir_node *ret;
1259         int i, n;
1260         ir_node **in;
1261         ir_node *stack;
1262         const arch_register_t **regs;
1263         pmap_entry *ent ;
1264
1265         /*
1266                 get the valid stack node in this block.
1267                 If we had a call in that block there is a Keep constructed by process_calls()
1268                 which points to the last stack modification in that block. we'll use
1269                 it then. Else we use the stack from the start block and let
1270                 the ssa construction fix the usage.
1271         */
1272         stack = be_abi_reg_map_get(env->regs, isa->sp);
1273         if (keep) {
1274                 ir_node *bad = new_r_Bad(env->birg->irg);
1275                 stack = get_irn_n(keep, 0);
1276                 set_nodes_block(keep, bad);
1277                 set_irn_n(keep, 0, bad);
1278                 // exchange(keep, new_r_Bad(env->birg->irg));
1279         }
1280
1281         /* Insert results for Return into the register map. */
1282         for(i = 0; i < n_res; ++i) {
1283                 ir_node *res           = get_Return_res(irn, i);
1284                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1285                 assert(arg->in_reg && "return value must be passed in register");
1286                 pmap_insert(reg_map, (void *) arg->reg, res);
1287         }
1288
1289         /* Add uses of the callee save registers. */
1290         pmap_foreach(env->regs, ent) {
1291                 const arch_register_t *reg = ent->key;
1292                 if(arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1293                         pmap_insert(reg_map, ent->key, ent->value);
1294         }
1295
1296         be_abi_reg_map_set(reg_map, isa->sp, stack);
1297
1298         /* Make the Epilogue node and call the arch's epilogue maker. */
1299         create_barrier(env, bl, &mem, reg_map, 1);
1300         call->cb->epilogue(env->cb, bl, &mem, reg_map);
1301
1302         /*
1303                 Maximum size of the in array for Return nodes is
1304                 return args + callee save/ignore registers + memory + stack pointer
1305         */
1306         in_max = pmap_count(reg_map) + n_res + 2;
1307
1308         in   = obstack_alloc(&env->obst, in_max * sizeof(in[0]));
1309         regs = obstack_alloc(&env->obst, in_max * sizeof(regs[0]));
1310
1311         in[0]   = mem;
1312         in[1]   = be_abi_reg_map_get(reg_map, isa->sp);
1313         regs[0] = NULL;
1314         regs[1] = isa->sp;
1315         n       = 2;
1316
1317         /* clear SP entry, since it has already been grown. */
1318         pmap_insert(reg_map, (void *) isa->sp, NULL);
1319         for(i = 0; i < n_res; ++i) {
1320                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1321
1322                 in[n]     = be_abi_reg_map_get(reg_map, arg->reg);
1323                 regs[n++] = arg->reg;
1324
1325                 /* Clear the map entry to mark the register as processed. */
1326                 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1327         }
1328
1329         /* grow the rest of the stuff. */
1330         pmap_foreach(reg_map, ent) {
1331                 if(ent->value) {
1332                         in[n]     = ent->value;
1333                         regs[n++] = ent->key;
1334                 }
1335         }
1336
1337         /* The in array for the new back end return is now ready. */
1338         ret = be_new_Return(irn ? get_irn_dbg_info(irn) : NULL, env->birg->irg, bl, n_res, n, in);
1339
1340         /* Set the register classes of the return's parameter accordingly. */
1341         for(i = 0; i < n; ++i)
1342                 if(regs[i])
1343                         be_node_set_reg_class(ret, i, regs[i]->reg_class);
1344
1345         /* Free the space of the Epilog's in array and the register <-> proj map. */
1346         obstack_free(&env->obst, in);
1347         pmap_destroy(reg_map);
1348
1349         return ret;
1350 }
1351
1352 typedef struct lower_frame_sels_env_t {
1353         be_abi_irg_t *env;
1354         entity       *value_param_list;  /**< the list of all value param antities */
1355 } lower_frame_sels_env_t;
1356
1357 /**
1358  * Walker: Replaces Sels of frame type and
1359  * value param type entities by FrameAddress.
1360  */
1361 static void lower_frame_sels_walker(ir_node *irn, void *data)
1362 {
1363         lower_frame_sels_env_t *ctx = data;
1364
1365         if (is_Sel(irn)) {
1366                 ir_graph *irg        = current_ir_graph;
1367                 ir_node  *frame      = get_irg_frame(irg);
1368                 ir_node  *param_base = get_irg_value_param_base(irg);
1369                 ir_node  *ptr        = get_Sel_ptr(irn);
1370
1371                 if (ptr == frame || ptr == param_base) {
1372                         be_abi_irg_t *env = ctx->env;
1373                         entity       *ent = get_Sel_entity(irn);
1374                         ir_node      *bl  = get_nodes_block(irn);
1375                         ir_node      *nw;
1376
1377                         nw = be_new_FrameAddr(env->isa->sp->reg_class, irg, bl, frame, ent);
1378                         exchange(irn, nw);
1379
1380                         if (ptr == param_base) {
1381                                 set_entity_link(ent, ctx->value_param_list);
1382                                 ctx->value_param_list = ent;
1383                         }
1384                 }
1385         }
1386 }
1387
1388 /**
1389  * Check if a value parameter is transmitted as a register.
1390  * This might happen if the address of an parameter is taken which is
1391  * transmitted in registers.
1392  *
1393  * Note that on some architectures this case must be handled specially
1394  * because the place of the backing store is determined by their ABI.
1395  *
1396  * In the default case we move the entity to the frame type and create
1397  * a backing store into the first block.
1398  */
1399 static void fix_address_of_parameter_access(be_abi_irg_t *env, entity *value_param_list) {
1400         be_abi_call_t *call = env->call;
1401         ir_graph *irg       = env->birg->irg;
1402         entity *ent, *next_ent, *new_list;
1403         ir_type *frame_tp;
1404         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1405
1406         new_list = NULL;
1407         for (ent = value_param_list; ent; ent = next_ent) {
1408                 int i = get_struct_member_index(get_entity_owner(ent), ent);
1409                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1410
1411                 next_ent = get_entity_link(ent);
1412                 if (arg->in_reg) {
1413                         DBG((dbg, LEVEL_2, "\targ #%d need backing store\n", i));
1414                         set_entity_link(ent, new_list);
1415                         new_list = ent;
1416                 }
1417         }
1418         if (new_list) {
1419                 /* ok, change the graph */
1420                 ir_node *start_bl = get_irg_start_block(irg);
1421                 ir_node *first_bl = NULL;
1422                 ir_node *frame, *imem, *nmem, *store, *mem, *args, *args_bl;
1423                 const ir_edge_t *edge;
1424                 optimization_state_t state;
1425                 int offset;
1426
1427                 foreach_block_succ(start_bl, edge) {
1428                         ir_node *succ = get_edge_src_irn(edge);
1429                         if (start_bl != succ) {
1430                                 first_bl = succ;
1431                                 break;
1432                         }
1433                 }
1434                 assert(first_bl);
1435                 /* we had already removed critical edges, so the following
1436                    assertion should be always true. */
1437                 assert(get_Block_n_cfgpreds(first_bl) == 1);
1438
1439                 /* now create backing stores */
1440                 frame = get_irg_frame(irg);
1441                 imem = get_irg_initial_mem(irg);
1442
1443                 save_optimization_state(&state);
1444                 set_optimize(0);
1445                 nmem = new_r_Proj(irg, first_bl, get_irg_start(irg), mode_M, pn_Start_M);
1446                 restore_optimization_state(&state);
1447
1448                 /* reroute all edges to the new memory source */
1449                 edges_reroute(imem, nmem, irg);
1450
1451                 store   = NULL;
1452                 mem     = imem;
1453                 args    = get_irg_args(irg);
1454                 args_bl = get_nodes_block(args);
1455                 for (ent = new_list; ent; ent = get_entity_link(ent)) {
1456                         int     i     = get_struct_member_index(get_entity_owner(ent), ent);
1457                         ir_type *tp   = get_entity_type(ent);
1458                         ir_mode *mode = get_type_mode(tp);
1459                         ir_node *addr;
1460
1461                         /* address for the backing store */
1462                         addr = be_new_FrameAddr(env->isa->sp->reg_class, irg, first_bl, frame, ent);
1463
1464                         if (store)
1465                                 mem = new_r_Proj(irg, first_bl, store, mode_M, pn_Store_M);
1466
1467                         /* the backing store itself */
1468                         store = new_r_Store(irg, first_bl, mem, addr,
1469                                             new_r_Proj(irg, args_bl, args, mode, i));
1470                 }
1471                 /* the new memory Proj gets the last Proj from store */
1472                 set_Proj_pred(nmem, store);
1473                 set_Proj_proj(nmem, pn_Store_M);
1474
1475                 /* move all entities to the frame type */
1476                 frame_tp = get_irg_frame_type(irg);
1477                 offset   = get_type_size_bytes(frame_tp);
1478                 for (ent = new_list; ent; ent = get_entity_link(ent)) {
1479                         ir_type *tp = get_entity_type(ent);
1480                         int align = get_type_alignment_bytes(tp);
1481
1482                         offset += align - 1;
1483                         offset &= -align;
1484                         set_entity_owner(ent, frame_tp);
1485                         add_class_member(frame_tp, ent);
1486                         /* must be automatic to set a fixed layout */
1487                         set_entity_allocation(ent, allocation_automatic);
1488                         set_entity_offset_bytes(ent, offset);
1489                         offset += get_type_size_bytes(tp);
1490                 }
1491                 set_type_size_bytes(frame_tp, offset);
1492         }
1493 }
1494
1495 /**
1496  * Modify the irg itself and the frame type.
1497  */
1498 static void modify_irg(be_abi_irg_t *env)
1499 {
1500         be_abi_call_t *call       = env->call;
1501         const arch_isa_t *isa     = env->birg->main_env->arch_env->isa;
1502         const arch_register_t *sp = arch_isa_sp(isa);
1503         ir_graph *irg             = env->birg->irg;
1504         ir_node *bl               = get_irg_start_block(irg);
1505         ir_node *end              = get_irg_end_block(irg);
1506         ir_node *mem              = get_irg_initial_mem(irg);
1507         ir_type *method_type      = get_entity_type(get_irg_entity(irg));
1508         pset *dont_save           = pset_new_ptr(8);
1509
1510         int n_params;
1511         int i, j, n;
1512
1513         reg_node_map_t *rm;
1514         const arch_register_t *fp_reg;
1515         ir_node *frame_pointer;
1516         ir_node *barrier;
1517         ir_node *reg_params_bl;
1518         ir_node **args;
1519         ir_node *arg_tuple;
1520         const ir_edge_t *edge;
1521         ir_type *arg_type, *bet_type;
1522         lower_frame_sels_env_t ctx;
1523
1524         bitset_t *used_proj_nr;
1525         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1526
1527         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1528
1529         /* Convert the Sel nodes in the irg to frame load/store/addr nodes. */
1530         ctx.env              = env;
1531         ctx.value_param_list = NULL;
1532         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1533
1534         env->frame = obstack_alloc(&env->obst, sizeof(env->frame[0]));
1535         env->regs  = pmap_create();
1536
1537         used_proj_nr = bitset_alloca(1024);
1538         n_params     = get_method_n_params(method_type);
1539         args         = obstack_alloc(&env->obst, n_params * sizeof(args[0]));
1540         memset(args, 0, n_params * sizeof(args[0]));
1541
1542         /* Check if a value parameter is transmitted as a register.
1543          * This might happen if the address of an parameter is taken which is
1544          * transmitted in registers.
1545          *
1546          * Note that on some architectures this case must be handled specially
1547          * because the place of the backing store is determined by their ABI.
1548          *
1549          * In the default case we move the entity to the frame type and create
1550          * a backing store into the first block.
1551          */
1552         fix_address_of_parameter_access(env, ctx.value_param_list);
1553
1554         /* Fill the argument vector */
1555         arg_tuple = get_irg_args(irg);
1556         foreach_out_edge(arg_tuple, edge) {
1557                 ir_node *irn = get_edge_src_irn(edge);
1558                 int nr       = get_Proj_proj(irn);
1559                 args[nr]     = irn;
1560                 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1561         }
1562
1563         arg_type = compute_arg_type(env, call, method_type);
1564         bet_type = call->cb->get_between_type(env->cb);
1565         stack_frame_init(env->frame, arg_type, bet_type, get_irg_frame_type(irg), isa->stack_dir);
1566
1567         /* Count the register params and add them to the number of Projs for the RegParams node */
1568         for(i = 0; i < n_params; ++i) {
1569                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1570                 if(arg->in_reg && args[i]) {
1571                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1572                         assert(i == get_Proj_proj(args[i]));
1573
1574                         /* For now, associate the register with the old Proj from Start representing that argument. */
1575                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1576                         bitset_set(used_proj_nr, i);
1577                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1578                 }
1579         }
1580
1581         /* Collect all callee-save registers */
1582         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
1583                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
1584                 for(j = 0; j < cls->n_regs; ++j) {
1585                         const arch_register_t *reg = &cls->regs[j];
1586                         if(arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1587                                 pmap_insert(env->regs, (void *) reg, NULL);
1588                 }
1589         }
1590
1591         pmap_insert(env->regs, (void *) sp, NULL);
1592         pmap_insert(env->regs, (void *) isa->bp, NULL);
1593         reg_params_bl   = get_irg_start_block(irg);
1594         env->reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(env->regs));
1595
1596         /*
1597          * make proj nodes for the callee save registers.
1598          * memorize them, since Return nodes get those as inputs.
1599          *
1600          * Note, that if a register corresponds to an argument, the regs map contains
1601          * the old Proj from start for that argument.
1602          */
1603
1604         rm = reg_map_to_arr(&env->obst, env->regs);
1605         for(i = 0, n = pmap_count(env->regs); i < n; ++i) {
1606                 arch_register_t *reg = (void *) rm[i].reg;
1607                 ir_node *arg_proj    = rm[i].irn;
1608                 ir_mode *mode        = arg_proj ? get_irn_mode(arg_proj) : reg->reg_class->mode;
1609                 long nr              = i;
1610                 int pos              = BE_OUT_POS((int) nr);
1611                 int flags            = 0;
1612
1613                 ir_node *proj;
1614
1615                 assert(nr >= 0);
1616                 bitset_set(used_proj_nr, nr);
1617                 proj = new_r_Proj(irg, reg_params_bl, env->reg_params, mode, nr);
1618                 pmap_insert(env->regs, (void *) reg, proj);
1619                 be_set_constr_single_reg(env->reg_params, pos, reg);
1620                 arch_set_irn_register(env->birg->main_env->arch_env, proj, reg);
1621
1622                 /*
1623                  * If the register is an ignore register,
1624                  * The Proj for that register shall also be ignored during register allocation.
1625                  */
1626                 if(arch_register_type_is(reg, ignore))
1627                         flags |= arch_irn_flags_ignore;
1628
1629                 if(reg == sp)
1630                         flags |= arch_irn_flags_modify_sp;
1631
1632                 be_node_set_flags(env->reg_params, pos, flags);
1633
1634                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1635         }
1636         obstack_free(&env->obst, rm);
1637
1638         /* Generate the Prologue */
1639         fp_reg  = call->cb->prologue(env->cb, &mem, env->regs);
1640
1641         /* do the stack allocation BEFORE the barrier, or spill code
1642            might be added before it */
1643         env->init_sp  = be_abi_reg_map_get(env->regs, sp);
1644         env->init_sp = be_new_IncSP(sp, irg, bl, env->init_sp, BE_STACK_FRAME_SIZE_EXPAND);
1645         be_abi_reg_map_set(env->regs, sp, env->init_sp);
1646
1647         barrier = create_barrier(env, bl, &mem, env->regs, 0);
1648
1649         env->init_sp  = be_abi_reg_map_get(env->regs, sp);
1650         arch_set_irn_register(env->birg->main_env->arch_env, env->init_sp, sp);
1651
1652         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1653         set_irg_frame(irg, frame_pointer);
1654         pset_insert_ptr(env->ignore_regs, fp_reg);
1655
1656         /* Now, introduce stack param nodes for all parameters passed on the stack */
1657         for(i = 0; i < n_params; ++i) {
1658                 ir_node *arg_proj = args[i];
1659                 ir_node *repl     = NULL;
1660
1661                 if(arg_proj != NULL) {
1662                         be_abi_call_arg_t *arg;
1663                         ir_type *param_type;
1664                         int nr = get_Proj_proj(arg_proj);
1665
1666                         nr         = MIN(nr, n_params);
1667                         arg        = get_call_arg(call, 0, nr);
1668                         param_type = get_method_param_type(method_type, nr);
1669
1670                         if(arg->in_reg) {
1671                                 repl = pmap_get(env->regs, (void *) arg->reg);
1672                         }
1673
1674                         else if(arg->on_stack) {
1675                                 /* For atomic parameters which are actually used, we create a StackParam node. */
1676                                 if(is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1677                                         ir_mode *mode                    = get_type_mode(param_type);
1678                                         const arch_register_class_t *cls = arch_isa_get_reg_class_for_mode(isa, mode);
1679                                         repl = be_new_StackParam(cls, isa->bp->reg_class, irg, reg_params_bl, mode, frame_pointer, arg->stack_ent);
1680                                 }
1681
1682                                 /* The stack parameter is not primitive (it is a struct or array),
1683                                 we thus will create a node representing the parameter's address
1684                                 on the stack. */
1685                                 else {
1686                                         repl = be_new_FrameAddr(sp->reg_class, irg, reg_params_bl, frame_pointer, arg->stack_ent);
1687                                 }
1688                         }
1689
1690                         assert(repl != NULL);
1691                         edges_reroute(args[i], repl, irg);
1692                 }
1693         }
1694
1695         /* All Return nodes hang on the End node, so look for them there. */
1696         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1697                 ir_node *irn = get_Block_cfgpred(end, i);
1698
1699                 if (is_Return(irn)) {
1700                         ir_node *ret = create_be_return(env, irn, get_nodes_block(irn), get_Return_mem(irn), get_Return_n_ress(irn));
1701                         exchange(irn, ret);
1702                 }
1703         }
1704         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return than,
1705            the code is dead and will never be executed. */
1706
1707         del_pset(dont_save);
1708         obstack_free(&env->obst, args);
1709 }
1710
1711 /**
1712  * Walker: puts all Alloc(stack_alloc) on a obstack
1713  */
1714 static void collect_alloca_walker(ir_node *irn, void *data)
1715 {
1716         be_abi_irg_t *env = data;
1717         if(get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc)
1718                 obstack_ptr_grow(&env->obst, irn);
1719 }
1720
1721 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
1722 {
1723         be_abi_irg_t *env  = xmalloc(sizeof(env[0]));
1724         ir_node *old_frame = get_irg_frame(birg->irg);
1725         ir_graph *irg      = birg->irg;
1726
1727         pmap_entry *ent;
1728         ir_node *dummy;
1729         optimization_state_t state;
1730
1731         obstack_init(&env->obst);
1732
1733         env->isa           = birg->main_env->arch_env->isa;
1734         env->method_type   = get_entity_type(get_irg_entity(irg));
1735         env->call          = be_abi_call_new();
1736         arch_isa_get_call_abi(env->isa, env->method_type, env->call);
1737
1738         env->ignore_regs      = pset_new_ptr_default();
1739         env->keep_map         = pmap_create();
1740         env->dce_survivor     = new_survive_dce();
1741         env->birg             = birg;
1742         env->stack_phis       = pset_new_ptr(16);
1743         /* Beware: later we replace this node by the real one, ensure it is not CSE'd
1744            to another Unknown or the stack pointer gets used */
1745         save_optimization_state(&state);
1746         set_optimize(0);
1747         env->init_sp = dummy  = new_r_Unknown(irg, env->isa->sp->reg_class->mode);
1748         restore_optimization_state(&state);
1749         FIRM_DBG_REGISTER(env->dbg, "firm.be.abi");
1750
1751         memcpy(&env->irn_handler, &abi_irn_handler, sizeof(abi_irn_handler));
1752         env->irn_ops.impl = &abi_irn_ops;
1753
1754         /* Lower all call nodes in the IRG. */
1755         process_calls(env);
1756
1757         /*
1758                 Beware: init backend abi call object after processing calls,
1759                 otherwise some information might be not yet available.
1760         */
1761         env->cb = env->call->cb->init(env->call, birg->main_env->arch_env, irg);
1762
1763         /* Process the IRG */
1764         modify_irg(env);
1765
1766         /* We don't need the keep map anymore. */
1767         pmap_destroy(env->keep_map);
1768
1769         /* reroute the stack origin of the calls to the true stack origin. */
1770         edges_reroute(dummy, env->init_sp, irg);
1771         edges_reroute(old_frame, get_irg_frame(irg), irg);
1772
1773         /* Make some important node pointers survive the dead node elimination. */
1774         survive_dce_register_irn(env->dce_survivor, &env->init_sp);
1775         pmap_foreach(env->regs, ent)
1776                 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
1777
1778         arch_env_push_irn_handler(env->birg->main_env->arch_env, &env->irn_handler);
1779
1780         env->call->cb->done(env->cb);
1781         return env;
1782 }
1783
1784 void be_abi_free(be_abi_irg_t *env)
1785 {
1786         free_survive_dce(env->dce_survivor);
1787         del_pset(env->stack_phis);
1788         del_pset(env->ignore_regs);
1789         pmap_destroy(env->regs);
1790         obstack_free(&env->obst, NULL);
1791         arch_env_pop_irn_handler(env->birg->main_env->arch_env);
1792         free(env);
1793 }
1794
1795 void be_abi_put_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, bitset_t *bs)
1796 {
1797         arch_register_t *reg;
1798
1799         for(reg = pset_first(abi->ignore_regs); reg; reg = pset_next(abi->ignore_regs))
1800                 if(reg->reg_class == cls)
1801                         bitset_set(bs, reg->index);
1802 }
1803
1804
1805 /*
1806
1807   _____ _        ____  _             _
1808  |  ___(_)_  __ / ___|| |_ __ _  ___| | __
1809  | |_  | \ \/ / \___ \| __/ _` |/ __| |/ /
1810  |  _| | |>  <   ___) | || (_| | (__|   <
1811  |_|   |_/_/\_\ |____/ \__\__,_|\___|_|\_\
1812
1813 */
1814
1815 struct fix_stack_walker_info {
1816         nodeset *nodes;
1817         const arch_env_t *aenv;
1818 };
1819
1820 /**
1821  * Walker. Collect all stack modifying nodes.
1822  */
1823 static void collect_stack_nodes_walker(ir_node *irn, void *data)
1824 {
1825         struct fix_stack_walker_info *info = data;
1826
1827         if (is_Block(irn))
1828                 return;
1829
1830         if (arch_irn_is(info->aenv, irn, modify_sp)) {
1831                 assert(get_irn_mode(irn) != mode_M && get_irn_mode(irn) != mode_T);
1832                 pset_insert_ptr(info->nodes, irn);
1833         }
1834 }
1835
1836 void be_abi_fix_stack_nodes(be_abi_irg_t *env, be_lv_t *lv)
1837 {
1838         dom_front_info_t *df;
1839         pset *stack_nodes = pset_new_ptr(16);
1840         struct fix_stack_walker_info info;
1841
1842         info.nodes = stack_nodes;
1843         info.aenv  = env->birg->main_env->arch_env;
1844
1845         /* We need dominance frontiers for fix up */
1846         df = be_compute_dominance_frontiers(env->birg->irg);
1847         irg_walk_graph(env->birg->irg, collect_stack_nodes_walker, NULL, &info);
1848         pset_insert_ptr(stack_nodes, env->init_sp);
1849         be_ssa_constr_set_phis(df, lv, stack_nodes, env->stack_phis);
1850         del_pset(stack_nodes);
1851
1852         /* free these dominance frontiers */
1853         be_free_dominance_frontiers(df);
1854 }
1855
1856 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int bias)
1857 {
1858         const arch_env_t *arch_env = env->birg->main_env->arch_env;
1859         int omit_fp            = env->call->flags.bits.try_omit_fp;
1860         ir_node *irn;
1861
1862         sched_foreach(bl, irn) {
1863
1864                 /*
1865                    Check, if the node relates to an entity on the stack frame.
1866                    If so, set the true offset (including the bias) for that
1867                    node.
1868                  */
1869                 entity *ent = arch_get_frame_entity(arch_env, irn);
1870                 if(ent) {
1871                         int offset = get_stack_entity_offset(env->frame, ent, bias);
1872                         arch_set_frame_offset(arch_env, irn, offset);
1873                         DBG((env->dbg, LEVEL_2, "%F has offset %d (including bias %d)\n", ent, offset, bias));
1874                 }
1875
1876                 /*
1877                    If the node modifies the stack pointer by a constant offset,
1878                    record that in the bias.
1879                  */
1880                 if(arch_irn_is(arch_env, irn, modify_sp)) {
1881                         int ofs = arch_get_sp_bias(arch_env, irn);
1882
1883                         if(be_is_IncSP(irn)) {
1884                                 if(ofs == BE_STACK_FRAME_SIZE_EXPAND) {
1885                                         ofs = get_type_size_bytes(get_irg_frame_type(env->birg->irg));
1886                                         be_set_IncSP_offset(irn, ofs);
1887                                 } else if(ofs == BE_STACK_FRAME_SIZE_SHRINK) {
1888                                         ofs = - get_type_size_bytes(get_irg_frame_type(env->birg->irg));
1889                                         be_set_IncSP_offset(irn, ofs);
1890                                 }
1891                         }
1892
1893                         if(omit_fp)
1894                                 bias += ofs;
1895                 }
1896         }
1897
1898         return bias;
1899 }
1900
1901 /**
1902  * A helper struct for the bias walker.
1903  */
1904 struct bias_walk {
1905         be_abi_irg_t *env;     /**< The ABI irg environment. */
1906         int start_block_bias;  /**< The bias at the end of the start block. */
1907         ir_node *start_block;  /**< The start block of the current graph. */
1908 };
1909
1910 /**
1911  * Block-Walker: fix all stack offsets
1912  */
1913 static void stack_bias_walker(ir_node *bl, void *data)
1914 {
1915         struct bias_walk *bw = data;
1916         if (bl != bw->start_block) {
1917                 process_stack_bias(bw->env, bl, bw->start_block_bias);
1918         }
1919 }
1920
1921 void be_abi_fix_stack_bias(be_abi_irg_t *env)
1922 {
1923         ir_graph *irg  = env->birg->irg;
1924         struct bias_walk bw;
1925
1926         stack_frame_compute_initial_offset(env->frame);
1927         // stack_layout_dump(stdout, env->frame);
1928
1929         /* Determine the stack bias at the end of the start block. */
1930         bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), 0);
1931
1932         /* fix the bias is all other blocks */
1933         bw.env = env;
1934         bw.start_block = get_irg_start_block(irg);
1935         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
1936 }
1937
1938 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
1939 {
1940         assert(arch_register_type_is(reg, callee_save));
1941         assert(pmap_contains(abi->regs, (void *) reg));
1942         return pmap_get(abi->regs, (void *) reg);
1943 }
1944
1945 /*
1946   _____ _____  _   _   _    _                 _ _
1947  |_   _|  __ \| \ | | | |  | |               | | |
1948    | | | |__) |  \| | | |__| | __ _ _ __   __| | | ___ _ __
1949    | | |  _  /| . ` | |  __  |/ _` | '_ \ / _` | |/ _ \ '__|
1950   _| |_| | \ \| |\  | | |  | | (_| | | | | (_| | |  __/ |
1951  |_____|_|  \_\_| \_| |_|  |_|\__,_|_| |_|\__,_|_|\___|_|
1952
1953   for Phi nodes which are created due to stack modifying nodes
1954   such as IncSP, AddSP and SetSP.
1955
1956   These Phis are always to be ignored by the reg alloc and are
1957   fixed on the SP register of the ISA.
1958 */
1959
1960 static const void *abi_get_irn_ops(const arch_irn_handler_t *handler, const ir_node *irn)
1961 {
1962         const be_abi_irg_t *abi = get_abi_from_handler(handler);
1963         const void *res = NULL;
1964
1965         if(is_Phi(irn) && pset_find_ptr(abi->stack_phis, (void *) irn))
1966                 res = &abi->irn_ops;
1967
1968         return res;
1969 }
1970
1971 static void be_abi_limited(void *data, bitset_t *bs)
1972 {
1973         be_abi_irg_t *abi = data;
1974         bitset_clear_all(bs);
1975         bitset_set(bs, abi->isa->sp->index);
1976 }
1977
1978 static const arch_register_req_t *abi_get_irn_reg_req(const void *self, arch_register_req_t *req, const ir_node *irn, int pos)
1979 {
1980         be_abi_irg_t *abi          = get_abi_from_ops(self);
1981         const arch_register_t *reg = abi->isa->sp;
1982
1983         memset(req, 0, sizeof(req[0]));
1984
1985         if(pos == BE_OUT_POS(0)) {
1986                 req->cls         = reg->reg_class;
1987                 req->type        = arch_register_req_type_limited;
1988                 req->limited     = be_abi_limited;
1989                 req->limited_env = abi;
1990         }
1991
1992         else if(pos >= 0 && pos < get_irn_arity(irn)) {
1993                 req->cls  = reg->reg_class;
1994                 req->type = arch_register_req_type_normal;
1995         }
1996
1997         return req;
1998 }
1999
2000 static void abi_set_irn_reg(const void *self, ir_node *irn, const arch_register_t *reg)
2001 {
2002 }
2003
2004 static const arch_register_t *abi_get_irn_reg(const void *self, const ir_node *irn)
2005 {
2006         const be_abi_irg_t *abi = get_abi_from_ops(self);
2007         return abi->isa->sp;
2008 }
2009
2010 static arch_irn_class_t abi_classify(const void *_self, const ir_node *irn)
2011 {
2012         return arch_irn_class_normal;
2013 }
2014
2015 static arch_irn_flags_t abi_get_flags(const void *_self, const ir_node *irn)
2016 {
2017         return arch_irn_flags_ignore | arch_irn_flags_modify_sp;
2018 }
2019
2020 static entity *abi_get_frame_entity(const void *_self, const ir_node *irn)
2021 {
2022         return NULL;
2023 }
2024
2025 static void abi_set_frame_entity(const void *_self, ir_node *irn, entity *ent)
2026 {
2027 }
2028
2029 static void abi_set_frame_offset(const void *_self, ir_node *irn, int bias)
2030 {
2031 }
2032
2033 static int abi_get_sp_bias(const void *self, const ir_node *irn)
2034 {
2035         return 0;
2036 }
2037
2038 static const arch_irn_ops_if_t abi_irn_ops = {
2039         abi_get_irn_reg_req,
2040         abi_set_irn_reg,
2041         abi_get_irn_reg,
2042         abi_classify,
2043         abi_get_flags,
2044         abi_get_frame_entity,
2045         abi_set_frame_entity,
2046         abi_set_frame_offset,
2047         abi_get_sp_bias,
2048         NULL,    /* get_inverse             */
2049         NULL,    /* get_op_estimated_cost   */
2050         NULL,    /* possible_memory_operand */
2051         NULL,    /* perform_memory_operand  */
2052 };
2053
2054 static const arch_irn_handler_t abi_irn_handler = {
2055         abi_get_irn_ops
2056 };