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

   1 /*
   2  * Copyright (C) 1995-2008 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 ABI implementation.
  23  * @author      Sebastian Hack, Michael Beck
  24  * @version     $Id$
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include "obst.h"
  31 #include "offset.h"
  32
  33 #include "irgopt.h"
  34
  35 #include "irgraph_t.h"
  36 #include "irnode_t.h"
  37 #include "ircons_t.h"
  38 #include "iredges_t.h"
  39 #include "irgmod.h"
  40 #include "irgwalk.h"
  41 #include "irprintf_t.h"
  42 #include "irgopt.h"
  43 #include "irbitset.h"
  44 #include "height.h"
  45 #include "pdeq.h"
  46 #include "irtools.h"
  47 #include "raw_bitset.h"
  48 #include "error.h"
  49
  50 #include "be.h"
  51 #include "beabi.h"
  52 #include "bearch_t.h"
  53 #include "benode_t.h"
  54 #include "belive_t.h"
  55 #include "besched_t.h"
  56 #include "beirg_t.h"
  57 #include "bessaconstr.h"
  58
  59 typedef struct _be_abi_call_arg_t {
  60         unsigned is_res   : 1;  /**< 1: the call argument is a return value. 0: it's a call parameter. */
  61         unsigned in_reg   : 1;  /**< 1: this argument is transmitted in registers. */
  62         unsigned on_stack : 1;  /**< 1: this argument is transmitted on the stack. */
  63
  64         int                    pos;
  65         const arch_register_t *reg;
  66         ir_entity             *stack_ent;
  67         ir_mode               *load_mode;
  68         unsigned               alignment;    /**< stack alignment */
  69         unsigned               space_before; /**< allocate space before */
  70         unsigned               space_after;  /**< allocate space after */
  71 } be_abi_call_arg_t;
  72
  73 struct _be_abi_call_t {
  74         be_abi_call_flags_t          flags;
  75         int                          pop;
  76         const be_abi_callbacks_t    *cb;
  77         ir_type                     *between_type;
  78         set                         *params;
  79         const arch_register_class_t *cls_addr;
  80 };
  81
  82 struct _be_abi_irg_t {
  83         struct obstack       obst;
  84         be_stack_layout_t    *frame;        /**< The stack frame model. */
  85         be_irg_t             *birg;         /**< The back end IRG. */
  86         const arch_env_t     *arch_env;
  87         survive_dce_t        *dce_survivor;
  88
  89         be_abi_call_t        *call;         /**< The ABI call information. */
  90         ir_type              *method_type;  /**< The type of the method of the IRG. */
  91
  92         ir_node              *init_sp;      /**< The node representing the stack pointer
  93                                                  at the start of the function. */
  94
  95         ir_node              *reg_params;   /**< The reg params node. */
  96         pmap                 *regs;         /**< A map of all callee-save and ignore regs to
  97                                                  their Projs to the RegParams node. */
  98
  99         int                  start_block_bias; /**< The stack bias at the end of the start block. */
 100
 101         void                 *cb;           /**< ABI Callback self pointer. */
 102
 103         pmap                 *keep_map;     /**< mapping blocks to keep nodes. */
 104         pset                 *ignore_regs;  /**< Additional registers which shall be ignored. */
 105
 106         ir_node             **calls;        /**< flexible array containing all be_Call nodes */
 107
 108         arch_register_req_t sp_req;
 109         arch_register_req_t sp_cls_req;
 110
 111         DEBUG_ONLY(firm_dbg_module_t    *dbg;)  /**< The debugging module. */
 112 };
 113
 114 static heights_t *ir_heights;
 115
 116 /** Flag: if set, try to omit the frame pointer in all routines. */
 117 static int be_omit_fp = 1;
 118
 119 /** Flag: if set, try to omit the frame pointer in leaf routines only. */
 120 static int be_omit_leaf_fp = 1;
 121
 122 /*
 123      _    ____ ___    ____      _ _ _                _
 124     / \  | __ )_ _|  / ___|__ _| | | |__   __ _  ___| | _____
 125    / _ \ |  _ \| |  | |   / _` | | | '_ \ / _` |/ __| |/ / __|
 126   / ___ \| |_) | |  | |__| (_| | | | |_) | (_| | (__|   <\__ \
 127  /_/   \_\____/___|  \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
 128
 129   These callbacks are used by the backend to set the parameters
 130   for a specific call type.
 131 */
 132
 133 /**
 134  * Set compare function: compares two ABI call object arguments.
 135  */
 136 static int cmp_call_arg(const void *a, const void *b, size_t n)
 137 {
 138         const be_abi_call_arg_t *p = a, *q = b;
 139         (void) n;
 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_set_pop(be_abi_call_t *call, int pop)
 187 {
 188         assert(pop >= 0);
 189         call->pop = pop;
 190 }
 191
 192 /* Set register class for call address */
 193 void be_abi_call_set_call_address_reg_class(be_abi_call_t *call, const arch_register_class_t *cls)
 194 {
 195         call->cls_addr = cls;
 196 }
 197
 198
 199 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos, ir_mode *load_mode, unsigned alignment, unsigned space_before, unsigned space_after)
 200 {
 201         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
 202         arg->on_stack     = 1;
 203         arg->load_mode    = load_mode;
 204         arg->alignment    = alignment;
 205         arg->space_before = space_before;
 206         arg->space_after  = space_after;
 207         assert(alignment > 0 && "Alignment must be greater than 0");
 208 }
 209
 210 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
 211 {
 212         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
 213         arg->in_reg = 1;
 214         arg->reg = reg;
 215 }
 216
 217 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
 218 {
 219         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 1, arg_pos, 1);
 220         arg->in_reg = 1;
 221         arg->reg = reg;
 222 }
 223
 224 /* Get the flags of a ABI call object. */
 225 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
 226 {
 227         return call->flags;
 228 }
 229
 230 /**
 231  * Constructor for a new ABI call object.
 232  *
 233  * @return the new ABI call object
 234  */
 235 static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
 236 {
 237         be_abi_call_t *call = xmalloc(sizeof(call[0]));
 238         memset(call, 0, sizeof(call[0]));
 239
 240         call->flags.val  = 0;
 241         call->params     = new_set(cmp_call_arg, 16);
 242         call->cb         = NULL;
 243         call->cls_addr   = cls_addr;
 244
 245         call->flags.bits.try_omit_fp = be_omit_fp | be_omit_leaf_fp;
 246
 247         return call;
 248 }
 249
 250 /**
 251  * Destructor for an ABI call object.
 252  */
 253 static void be_abi_call_free(be_abi_call_t *call)
 254 {
 255         del_set(call->params);
 256         free(call);
 257 }
 258
 259 /*
 260   _____                           _   _                 _ _ _
 261  |  ___| __ __ _ _ __ ___   ___  | | | | __ _ _ __   __| | (_)_ __   __ _
 262  | |_ | '__/ _` | '_ ` _ \ / _ \ | |_| |/ _` | '_ \ / _` | | | '_ \ / _` |
 263  |  _|| | | (_| | | | | | |  __/ |  _  | (_| | | | | (_| | | | | | | (_| |
 264  |_|  |_|  \__,_|_| |_| |_|\___| |_| |_|\__,_|_| |_|\__,_|_|_|_| |_|\__, |
 265                                                                     |___/
 266
 267   Handling of the stack frame. It is composed of three types:
 268   1) The type of the arguments which are pushed on the stack.
 269   2) The "between type" which consists of stuff the call of the
 270      function pushes on the stack (like the return address and
 271          the old base pointer for ia32).
 272   3) The Firm frame type which consists of all local variables
 273      and the spills.
 274 */
 275
 276 static int get_stack_entity_offset(be_stack_layout_t *frame, ir_entity *ent,
 277                                    int bias)
 278 {
 279         ir_type *t = get_entity_owner(ent);
 280         int ofs    = get_entity_offset(ent);
 281
 282         int index;
 283
 284         /* Find the type the entity is contained in. */
 285         for (index = 0; index < N_FRAME_TYPES; ++index) {
 286                 if (frame->order[index] == t)
 287                         break;
 288                 /* Add the size of all the types below the one of the entity to the entity's offset */
 289                 ofs += get_type_size_bytes(frame->order[index]);
 290         }
 291
 292         /* correct the offset by the initial position of the frame pointer */
 293         ofs -= frame->initial_offset;
 294
 295         /* correct the offset with the current bias. */
 296         ofs += bias;
 297
 298         return ofs;
 299 }
 300
 301 /**
 302  * Retrieve the entity with given offset from a frame type.
 303  */
 304 static ir_entity *search_ent_with_offset(ir_type *t, int offset)
 305 {
 306         int i, n;
 307
 308         for(i = 0, n = get_compound_n_members(t); i < n; ++i) {
 309                 ir_entity *ent = get_compound_member(t, i);
 310                 if (get_entity_offset(ent) == offset)
 311                         return ent;
 312         }
 313
 314         return NULL;
 315 }
 316
 317 static int stack_frame_compute_initial_offset(be_stack_layout_t *frame)
 318 {
 319         ir_type  *base = frame->stack_dir < 0 ? frame->between_type : frame->frame_type;
 320         ir_entity *ent = search_ent_with_offset(base, 0);
 321
 322         frame->initial_offset = ent ? get_stack_entity_offset(frame, ent, 0) : 0;
 323
 324         return frame->initial_offset;
 325 }
 326
 327 /**
 328  * Initializes the frame layout from parts
 329  *
 330  * @param frame     the stack layout that will be initialized
 331  * @param args      the stack argument layout type
 332  * @param between   the between layout type
 333  * @param locals    the method frame type
 334  * @param stack_dir the stack direction
 335  * @param param_map an array mapping method argument positions to the stack argument type
 336  *
 337  * @return the initialized stack layout
 338  */
 339 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
 340                                            ir_type *between, ir_type *locals, int stack_dir,
 341                                            ir_entity *param_map[])
 342 {
 343         frame->arg_type       = args;
 344         frame->between_type   = between;
 345         frame->frame_type     = locals;
 346         frame->initial_offset = 0;
 347         frame->stack_dir      = stack_dir;
 348         frame->order[1]       = between;
 349         frame->param_map      = param_map;
 350
 351         if(stack_dir > 0) {
 352                 frame->order[0] = args;
 353                 frame->order[2] = locals;
 354         }
 355         else {
 356                 frame->order[0] = locals;
 357                 frame->order[2] = args;
 358         }
 359         return frame;
 360 }
 361
 362 #if 0
 363 /** Dumps the stack layout to file. */
 364 static void stack_layout_dump(FILE *file, be_stack_layout_t *frame)
 365 {
 366         int i, j, n;
 367
 368         ir_fprintf(file, "initial offset: %d\n", frame->initial_offset);
 369         for (j = 0; j < N_FRAME_TYPES; ++j) {
 370                 ir_type *t = frame->order[j];
 371
 372                 ir_fprintf(file, "type %d: %F size: %d\n", j, t, get_type_size_bytes(t));
 373                 for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
 374                         ir_entity *ent = get_compound_member(t, i);
 375                         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));
 376                 }
 377         }
 378 }
 379 #endif
 380
 381 /**
 382  * Returns non-zero if the call argument at given position
 383  * is transfered on the stack.
 384  */
 385 static INLINE int is_on_stack(be_abi_call_t *call, int pos)
 386 {
 387         be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
 388         return arg && !arg->in_reg;
 389 }
 390
 391 /*
 392    ____      _ _
 393   / ___|__ _| | |___
 394  | |   / _` | | / __|
 395  | |__| (_| | | \__ \
 396   \____\__,_|_|_|___/
 397
 398   Adjustment of the calls inside a graph.
 399
 400 */
 401
 402 /**
 403  * Transform a call node into a be_Call node.
 404  *
 405  * @param env The ABI environment for the current irg.
 406  * @param irn The call node.
 407  * @param curr_sp The stack pointer node to use.
 408  * @return The stack pointer after the call.
 409  */
 410 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
 411 {
 412         ir_graph *irg              = env->birg->irg;
 413         const arch_env_t *arch_env = env->birg->main_env->arch_env;
 414         ir_type *call_tp           = get_Call_type(irn);
 415         ir_node *call_ptr          = get_Call_ptr(irn);
 416         int n_params               = get_method_n_params(call_tp);
 417         ir_node *curr_mem          = get_Call_mem(irn);
 418         ir_node *bl                = get_nodes_block(irn);
 419         pset *results              = pset_new_ptr(8);
 420         pset *caller_save          = pset_new_ptr(8);
 421         pset *states               = pset_new_ptr(2);
 422         int stack_size             = 0;
 423         int stack_dir              = arch_env_stack_dir(arch_env);
 424         const arch_register_t *sp  = arch_env_sp(arch_env);
 425         be_abi_call_t *call        = be_abi_call_new(sp->reg_class);
 426         ir_mode *mach_mode         = sp->reg_class->mode;
 427         struct obstack *obst       = &env->obst;
 428         int no_alloc               = call->flags.bits.frame_is_setup_on_call;
 429         int n_res                  = get_method_n_ress(call_tp);
 430         int do_seq                 = call->flags.bits.store_args_sequential && !no_alloc;
 431
 432         ir_node *res_proj  = NULL;
 433         int n_reg_params   = 0;
 434         int n_stack_params = 0;
 435         int n_ins;
 436
 437         ir_node *low_call;
 438         ir_node **in;
 439         ir_node **res_projs;
 440         int      n_reg_results = 0;
 441         const arch_register_t *reg;
 442         const ir_edge_t *edge;
 443         int *reg_param_idxs;
 444         int *stack_param_idx;
 445         int i, n;
 446
 447         /* Let the isa fill out the abi description for that call node. */
 448         arch_env_get_call_abi(arch_env, call_tp, call);
 449
 450         /* Insert code to put the stack arguments on the stack. */
 451         assert(get_Call_n_params(irn) == n_params);
 452         for (i = 0; i < n_params; ++i) {
 453                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 454                 assert(arg);
 455                 if (arg->on_stack) {
 456                         int arg_size = get_type_size_bytes(get_method_param_type(call_tp, i));
 457
 458                         stack_size += round_up2(arg->space_before, arg->alignment);
 459                         stack_size += round_up2(arg_size, arg->alignment);
 460                         stack_size += round_up2(arg->space_after, arg->alignment);
 461                         obstack_int_grow(obst, i);
 462                         ++n_stack_params;
 463                 }
 464         }
 465         stack_param_idx = obstack_finish(obst);
 466
 467         /* Collect all arguments which are passed in registers. */
 468         for (i = 0; i < n_params; ++i) {
 469                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 470                 if (arg && arg->in_reg) {
 471                         obstack_int_grow(obst, i);
 472                         ++n_reg_params;
 473                 }
 474         }
 475         reg_param_idxs = obstack_finish(obst);
 476
 477         /*
 478          * If the stack is decreasing and we do not want to store sequentially,
 479          * or someone else allocated the call frame
 480          * we allocate as much space on the stack all parameters need, by
 481          * moving the stack pointer along the stack's direction.
 482          *
 483          * Note: we also have to do this for stack_size == 0, because we may have
 484          * to adjust stack alignment for the call.
 485          */
 486         if (stack_dir < 0 && !do_seq && !no_alloc) {
 487                 curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, stack_size, 1);
 488         }
 489
 490         /* If there are some parameters which shall be passed on the stack. */
 491         if (n_stack_params > 0) {
 492                 int curr_ofs      = 0;
 493
 494                 /*
 495                  * Reverse list of stack parameters if call arguments are from left to right.
 496                  * We must them reverse again if they are pushed (not stored) and the stack
 497                  * direction is downwards.
 498                  */
 499                 if (call->flags.bits.left_to_right ^ (do_seq && stack_dir < 0)) {
 500                         for (i = 0; i < n_stack_params >> 1; ++i) {
 501                                 int other  = n_stack_params - i - 1;
 502                                 int tmp    = stack_param_idx[i];
 503                                 stack_param_idx[i]     = stack_param_idx[other];
 504                                 stack_param_idx[other] = tmp;
 505                         }
 506                 }
 507
 508                 curr_mem = get_Call_mem(irn);
 509                 if (! do_seq) {
 510                         obstack_ptr_grow(obst, curr_mem);
 511                 }
 512
 513                 for (i = 0; i < n_stack_params; ++i) {
 514                         int p                  = stack_param_idx[i];
 515                         be_abi_call_arg_t *arg = get_call_arg(call, 0, p);
 516                         ir_node *param         = get_Call_param(irn, p);
 517                         ir_node *addr          = curr_sp;
 518                         ir_node *mem           = NULL;
 519                         ir_type *param_type    = get_method_param_type(call_tp, p);
 520                         int param_size         = get_type_size_bytes(param_type) + arg->space_after;
 521
 522                         /*
 523                          * If we wanted to build the arguments sequentially,
 524                          * the stack pointer for the next must be incremented,
 525                          * and the memory value propagated.
 526                          */
 527                         if (do_seq) {
 528                                 curr_ofs = 0;
 529                                 addr = curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, param_size + arg->space_before, 0);
 530                                 add_irn_dep(curr_sp, curr_mem);
 531                         }
 532                         else {
 533                                 curr_ofs += arg->space_before;
 534                                 curr_ofs =  round_up2(curr_ofs, arg->alignment);
 535
 536                                 /* Make the expression to compute the argument's offset. */
 537                                 if (curr_ofs > 0) {
 538                                         ir_mode *constmode = mach_mode;
 539                                         if(mode_is_reference(mach_mode)) {
 540                                                 constmode = mode_Is;
 541                                         }
 542                                         addr = new_r_Const_long(irg, bl, constmode, curr_ofs);
 543                                         addr = new_r_Add(irg, bl, curr_sp, addr, mach_mode);
 544                                 }
 545                         }
 546
 547                         /* Insert a store for primitive arguments. */
 548                         if (is_atomic_type(param_type)) {
 549                                 ir_node *store;
 550                                 ir_node *mem_input = do_seq ? curr_mem : new_NoMem();
 551                                 store = new_r_Store(irg, bl, mem_input, addr, param);
 552                                 mem = new_r_Proj(irg, bl, store, mode_M, pn_Store_M);
 553                         }
 554
 555                         /* Make a mem copy for compound arguments. */
 556                         else {
 557                                 ir_node *copy;
 558
 559                                 assert(mode_is_reference(get_irn_mode(param)));
 560                                 copy = new_r_CopyB(irg, bl, curr_mem, addr, param, param_type);
 561                                 mem = new_r_Proj(irg, bl, copy, mode_M, pn_CopyB_M_regular);
 562                         }
 563
 564                         curr_ofs += param_size;
 565
 566                         if (do_seq)
 567                                 curr_mem = mem;
 568                         else
 569                                 obstack_ptr_grow(obst, mem);
 570                 }
 571
 572                 in = (ir_node **) obstack_finish(obst);
 573
 574                 /* We need the sync only, if we didn't build the stores sequentially. */
 575                 if (! do_seq) {
 576                         if (n_stack_params >= 1) {
 577                                 curr_mem = new_r_Sync(irg, bl, n_stack_params + 1, in);
 578                         } else {
 579                                 curr_mem = get_Call_mem(irn);
 580                         }
 581                 }
 582                 obstack_free(obst, in);
 583         }
 584
 585         /* Collect caller save registers */
 586         for (i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
 587                 unsigned j;
 588                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
 589                 for (j = 0; j < cls->n_regs; ++j) {
 590                         const arch_register_t *reg = arch_register_for_index(cls, j);
 591                         if (arch_register_type_is(reg, caller_save)) {
 592                                 pset_insert_ptr(caller_save, (void *) reg);
 593                         }
 594                         if (arch_register_type_is(reg, state)) {
 595                                 pset_insert_ptr(caller_save, (void*) reg);
 596                                 pset_insert_ptr(states, (void*) reg);
 597                         }
 598                 }
 599         }
 600
 601         /* search the greatest result proj number */
 602
 603         res_projs = alloca(n_res * sizeof(res_projs[0]));
 604         memset(res_projs, 0, n_res * sizeof(res_projs[0]));
 605
 606         foreach_out_edge(irn, edge) {
 607                 const ir_edge_t *res_edge;
 608                 ir_node         *irn = get_edge_src_irn(edge);
 609
 610                 if(!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
 611                         continue;
 612
 613                 foreach_out_edge(irn, res_edge) {
 614                         int proj;
 615                         ir_node *res = get_edge_src_irn(res_edge);
 616
 617                         assert(is_Proj(res));
 618
 619                         proj = get_Proj_proj(res);
 620                         assert(proj < n_res);
 621                         assert(res_projs[proj] == NULL);
 622                         res_projs[proj] = res;
 623                 }
 624                 res_proj = irn;
 625                 break;
 626         }
 627
 628         /** TODO: this is not correct for cases where return values are passed
 629          * on the stack, but no known ABI does this currently...
 630          */
 631         n_reg_results = n_res;
 632
 633         /* make the back end call node and set its register requirements. */
 634         for (i = 0; i < n_reg_params; ++i) {
 635                 obstack_ptr_grow(obst, get_Call_param(irn, reg_param_idxs[i]));
 636         }
 637         foreach_pset(states, reg) {
 638                 const arch_register_class_t *cls = arch_register_get_class(reg);
 639 #if 0
 640                 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
 641                 ir_fprintf(stderr, "Adding %+F\n", regnode);
 642 #endif
 643                 ir_node *regnode = new_rd_Unknown(irg, arch_register_class_mode(cls));
 644                 obstack_ptr_grow(obst, regnode);
 645         }
 646         n_ins = n_reg_params + pset_count(states);
 647
 648         in = obstack_finish(obst);
 649
 650         if (env->call->flags.bits.call_has_imm && is_SymConst(call_ptr)) {
 651                 /* direct call */
 652                 low_call = be_new_Call(get_irn_dbg_info(irn), irg, bl, curr_mem,
 653                                        curr_sp, curr_sp,
 654                                        n_reg_results + pn_be_Call_first_res + pset_count(caller_save),
 655                                        n_ins, in, get_Call_type(irn));
 656                 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
 657         } else {
 658                 /* indirect call */
 659                 low_call = be_new_Call(get_irn_dbg_info(irn), irg, bl, curr_mem,
 660                                        curr_sp, call_ptr,
 661                                        n_reg_results + pn_be_Call_first_res + pset_count(caller_save),
 662                                        n_ins, in, get_Call_type(irn));
 663         }
 664         be_Call_set_pop(low_call, call->pop);
 665         ARR_APP1(ir_node *, env->calls, low_call);
 666
 667         /* create new stack pointer */
 668         curr_sp = new_r_Proj(irg, bl, low_call, get_irn_mode(curr_sp),
 669                              pn_be_Call_sp);
 670         be_set_constr_single_reg(low_call, BE_OUT_POS(pn_be_Call_sp), sp);
 671         arch_set_irn_register(arch_env, curr_sp, sp);
 672         be_node_set_flags(low_call, BE_OUT_POS(pn_be_Call_sp),
 673                         arch_irn_flags_ignore | arch_irn_flags_modify_sp);
 674
 675         for(i = 0; i < n_res; ++i) {
 676                 int pn;
 677                 ir_node           *proj = res_projs[i];
 678                 be_abi_call_arg_t *arg  = get_call_arg(call, 1, i);
 679
 680                 /* returns values on stack not supported yet */
 681                 assert(arg->in_reg);
 682
 683                 /*
 684                         shift the proj number to the right, since we will drop the
 685                         unspeakable Proj_T from the Call. Therefore, all real argument
 686                         Proj numbers must be increased by pn_be_Call_first_res
 687                 */
 688                 pn = i + pn_be_Call_first_res;
 689
 690                 if(proj == NULL) {
 691                         ir_type *res_type = get_method_res_type(call_tp, i);
 692                         ir_mode *mode     = get_type_mode(res_type);
 693                         proj              = new_r_Proj(irg, bl, low_call, mode, pn);
 694                         res_projs[i]      = proj;
 695                 } else {
 696                         set_Proj_pred(proj, low_call);
 697                         set_Proj_proj(proj, pn);
 698                 }
 699
 700                 if (arg->in_reg) {
 701                         pset_remove_ptr(caller_save, arg->reg);
 702                 }
 703         }
 704
 705         /*
 706                 Set the register class of the call address to
 707                 the backend provided class (default: stack pointer class)
 708         */
 709         be_node_set_reg_class(low_call, be_pos_Call_ptr, call->cls_addr);
 710
 711         DBG((env->dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
 712
 713         /* Set the register classes and constraints of the Call parameters. */
 714         for (i = 0; i < n_reg_params; ++i) {
 715                 int index = reg_param_idxs[i];
 716                 be_abi_call_arg_t *arg = get_call_arg(call, 0, index);
 717                 assert(arg->reg != NULL);
 718
 719                 be_set_constr_single_reg(low_call, be_pos_Call_first_arg + i, arg->reg);
 720         }
 721
 722         /* Set the register constraints of the results. */
 723         for (i = 0; i < n_res; ++i) {
 724                 ir_node                 *proj = res_projs[i];
 725                 const be_abi_call_arg_t *arg  = get_call_arg(call, 1, i);
 726                 int                      pn   = get_Proj_proj(proj);
 727
 728                 assert(arg->in_reg);
 729                 be_set_constr_single_reg(low_call, BE_OUT_POS(pn), arg->reg);
 730                 arch_set_irn_register(arch_env, proj, arg->reg);
 731         }
 732         obstack_free(obst, in);
 733         exchange(irn, low_call);
 734
 735         /* kill the ProjT node */
 736         if (res_proj != NULL) {
 737                 kill_node(res_proj);
 738         }
 739
 740         /* Make additional projs for the caller save registers
 741            and the Keep node which keeps them alive. */
 742         if (1 || pset_count(caller_save) + n_reg_results > 0) {
 743                 const arch_register_t *reg;
 744                 ir_node               **in, *keep;
 745                 int                   i;
 746                 int                   n = 0;
 747                 int                   curr_res_proj
 748                         = pn_be_Call_first_res + n_reg_results;
 749
 750                 /* also keep the stack pointer */
 751                 ++n;
 752                 set_irn_link(curr_sp, (void*) sp);
 753                 obstack_ptr_grow(obst, curr_sp);
 754
 755                 for (reg = pset_first(caller_save); reg; reg = pset_next(caller_save), ++n) {
 756                         ir_node *proj = new_r_Proj(irg, bl, low_call, reg->reg_class->mode,
 757                                                    curr_res_proj);
 758
 759                         /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
 760                         be_set_constr_single_reg(low_call, BE_OUT_POS(curr_res_proj), reg);
 761                         arch_set_irn_register(arch_env, proj, reg);
 762
 763                         /* a call can produce ignore registers, in this case set the flag and register for the Proj */
 764                         if (arch_register_type_is(reg, ignore)) {
 765                                 be_node_set_flags(low_call, BE_OUT_POS(curr_res_proj),
 766                                                   arch_irn_flags_ignore);
 767                         }
 768
 769                         set_irn_link(proj, (void*) reg);
 770                         obstack_ptr_grow(obst, proj);
 771                         curr_res_proj++;
 772                 }
 773
 774                 for(i = 0; i < n_reg_results; ++i) {
 775                         ir_node *proj = res_projs[i];
 776                         const arch_register_t *reg = arch_get_irn_register(arch_env, proj);
 777                         set_irn_link(proj, (void*) reg);
 778                         obstack_ptr_grow(obst, proj);
 779                 }
 780                 n += n_reg_results;
 781
 782                 /* create the Keep for the caller save registers */
 783                 in   = (ir_node **) obstack_finish(obst);
 784                 keep = be_new_Keep(NULL, irg, bl, n, in);
 785                 for (i = 0; i < n; ++i) {
 786                         const arch_register_t *reg = get_irn_link(in[i]);
 787                         be_node_set_reg_class(keep, i, reg->reg_class);
 788                 }
 789                 obstack_free(obst, in);
 790         }
 791
 792         /* Clean up the stack. */
 793         assert(stack_size >= call->pop);
 794         stack_size -= call->pop;
 795
 796         if (stack_size > 0) {
 797                 ir_node *mem_proj = NULL;
 798
 799                 foreach_out_edge(low_call, edge) {
 800                         ir_node *irn = get_edge_src_irn(edge);
 801                         if(is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
 802                                 mem_proj = irn;
 803                                 break;
 804                         }
 805                 }
 806
 807                 if (! mem_proj) {
 808                         mem_proj = new_r_Proj(irg, bl, low_call, mode_M, pn_be_Call_M_regular);
 809                         keep_alive(mem_proj);
 810                 }
 811         }
 812         /* Clean up the stack frame or revert alignment fixes if we allocated it */
 813         if (! no_alloc) {
 814                 curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, -stack_size, 0);
 815         }
 816
 817         be_abi_call_free(call);
 818         obstack_free(obst, stack_param_idx);
 819         del_pset(results);
 820         del_pset(states);
 821         del_pset(caller_save);
 822
 823         return curr_sp;
 824 }
 825
 826 /**
 827  * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
 828  *
 829  * @param alignment  the minimum stack alignment
 830  * @param size       the node containing the non-aligned size
 831  * @param irg        the irg where new nodes are allocated on
 832  * @param irg        the block where new nodes are allocated on
 833  * @param dbg        debug info for new nodes
 834  *
 835  * @return a node representing the aligned size
 836  */
 837 static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
 838                                   ir_graph *irg, ir_node *block, dbg_info *dbg)
 839 {
 840         if (stack_alignment > 1) {
 841                 ir_mode *mode;
 842                 tarval  *tv;
 843                 ir_node *mask;
 844
 845                 assert(is_po2(stack_alignment));
 846
 847                 mode = get_irn_mode(size);
 848                 tv   = new_tarval_from_long(stack_alignment-1, mode);
 849                 mask = new_r_Const(irg, block, mode, tv);
 850                 size = new_rd_Add(dbg, irg, block, size, mask, mode);
 851
 852                 tv   = new_tarval_from_long(-(long)stack_alignment, mode);
 853                 mask = new_r_Const(irg, block, mode, tv);
 854                 size = new_rd_And(dbg, irg, block, size, mask, mode);
 855         }
 856         return size;
 857 }
 858 /**
 859  * Adjust an alloca.
 860  * The alloca is transformed into a back end alloca node and connected to the stack nodes.
 861  */
 862 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
 863 {
 864         ir_node *block;
 865         ir_graph *irg;
 866         ir_node *alloc_mem;
 867         ir_node *alloc_res;
 868         ir_type *type;
 869         dbg_info *dbg;
 870
 871         const ir_edge_t *edge;
 872         ir_node *new_alloc, *size, *addr, *ins[2];
 873         unsigned stack_alignment;
 874
 875         assert(get_Alloc_where(alloc) == stack_alloc);
 876
 877         block = get_nodes_block(alloc);
 878         irg = get_irn_irg(block);
 879         alloc_mem = NULL;
 880         alloc_res = NULL;
 881         type = get_Alloc_type(alloc);
 882
 883         foreach_out_edge(alloc, edge) {
 884                 ir_node *irn = get_edge_src_irn(edge);
 885
 886                 assert(is_Proj(irn));
 887                 switch (get_Proj_proj(irn)) {
 888                 case pn_Alloc_M:
 889                         alloc_mem = irn;
 890                         break;
 891                 case pn_Alloc_res:
 892                         alloc_res = irn;
 893                         break;
 894                 default:
 895                         break;
 896                 }
 897         }
 898
 899         /* Beware: currently Alloc nodes without a result might happen,
 900            only escape analysis kills them and this phase runs only for object
 901            oriented source. We kill the Alloc here. */
 902         if (alloc_res == NULL && alloc_mem) {
 903                 exchange(alloc_mem, get_Alloc_mem(alloc));
 904                 return curr_sp;
 905         }
 906
 907         dbg = get_irn_dbg_info(alloc);
 908
 909         /* we might need to multiply the size with the element size */
 910         if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
 911                 tarval *tv    = new_tarval_from_long(get_type_size_bytes(type),
 912                                                      mode_Iu);
 913                 ir_node *cnst = new_rd_Const(dbg, irg, block, mode_Iu, tv);
 914                 ir_node *mul  = new_rd_Mul(dbg, irg, block, get_Alloc_size(alloc),
 915                                            cnst, mode_Iu);
 916                 size = mul;
 917         } else {
 918                 size = get_Alloc_size(alloc);
 919         }
 920
 921         /* The stack pointer will be modified in an unknown manner.
 922            We cannot omit it. */
 923         env->call->flags.bits.try_omit_fp = 0;
 924
 925         stack_alignment = 1 << env->arch_env->stack_alignment;
 926         size            = adjust_alloc_size(stack_alignment, size, irg, block, dbg);
 927         new_alloc       = be_new_AddSP(env->arch_env->sp, irg, block, curr_sp, size);
 928         set_irn_dbg_info(new_alloc, dbg);
 929
 930         if(alloc_mem != NULL) {
 931                 ir_node *addsp_mem;
 932                 ir_node *sync;
 933
 934                 addsp_mem = new_r_Proj(irg, block, new_alloc, mode_M, pn_be_AddSP_M);
 935
 936                 /* We need to sync the output mem of the AddSP with the input mem
 937                    edge into the alloc node. */
 938                 ins[0] = get_Alloc_mem(alloc);
 939                 ins[1] = addsp_mem;
 940                 sync = new_r_Sync(irg, block, 2, ins);
 941
 942                 exchange(alloc_mem, sync);
 943         }
 944
 945         exchange(alloc, new_alloc);
 946
 947         /* fix projnum of alloca res */
 948         set_Proj_proj(alloc_res, pn_be_AddSP_res);
 949
 950         addr    = alloc_res;
 951         curr_sp = new_r_Proj(irg, block, new_alloc,  get_irn_mode(curr_sp),
 952                              pn_be_AddSP_sp);
 953
 954         return curr_sp;
 955 }  /* adjust_alloc */
 956
 957 /**
 958  * Adjust a Free.
 959  * The Free is transformed into a back end free node and connected to the stack nodes.
 960  */
 961 static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
 962 {
 963         ir_node *block;
 964         ir_graph *irg;
 965         ir_node *subsp, *mem, *res, *size, *sync;
 966         ir_type *type;
 967         ir_node *in[2];
 968         ir_mode *sp_mode;
 969         unsigned stack_alignment;
 970         dbg_info *dbg;
 971
 972         assert(get_Free_where(free) == stack_alloc);
 973
 974         block = get_nodes_block(free);
 975         irg = get_irn_irg(block);
 976         type = get_Free_type(free);
 977         sp_mode = env->arch_env->sp->reg_class->mode;
 978         dbg = get_irn_dbg_info(free);
 979
 980         /* we might need to multiply the size with the element size */
 981         if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
 982                 tarval *tv = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
 983                 ir_node *cnst = new_rd_Const(dbg, irg, block, mode_Iu, tv);
 984                 ir_node *mul = new_rd_Mul(dbg, irg, block, get_Free_size(free),
 985                                           cnst, mode_Iu);
 986                 size = mul;
 987         } else {
 988                 size = get_Free_size(free);
 989         }
 990
 991         stack_alignment = 1 << env->arch_env->stack_alignment;
 992         size            = adjust_alloc_size(stack_alignment, size, irg, block, dbg);
 993
 994         /* The stack pointer will be modified in an unknown manner.
 995            We cannot omit it. */
 996         env->call->flags.bits.try_omit_fp = 0;
 997         subsp = be_new_SubSP(env->arch_env->sp, irg, block, curr_sp, size);
 998         set_irn_dbg_info(subsp, dbg);
 999
1000         mem = new_r_Proj(irg, block, subsp, mode_M, pn_be_SubSP_M);
1001         res = new_r_Proj(irg, block, subsp, sp_mode, pn_be_SubSP_sp);
1002
1003         /* we need to sync the memory */
1004         in[0] = get_Free_mem(free);
1005         in[1] = mem;
1006         sync = new_r_Sync(irg, block, 2, in);
1007
1008         /* and make the AddSP dependent on the former memory */
1009         add_irn_dep(subsp, get_Free_mem(free));
1010
1011         /* kill the free */
1012         exchange(free, sync);
1013         curr_sp = res;
1014
1015         return curr_sp;
1016 }  /* adjust_free */
1017
1018 /* the following function is replaced by the usage of the heights module */
1019 #if 0
1020 /**
1021  * Walker for dependent_on().
1022  * This function searches a node tgt recursively from a given node
1023  * but is restricted to the given block.
1024  * @return 1 if tgt was reachable from curr, 0 if not.
1025  */
1026 static int check_dependence(ir_node *curr, ir_node *tgt, ir_node *bl)
1027 {
1028         int n, i;
1029
1030         if (get_nodes_block(curr) != bl)
1031                 return 0;
1032
1033         if (curr == tgt)
1034                 return 1;
1035
1036         /* Phi functions stop the recursion inside a basic block */
1037         if (! is_Phi(curr)) {
1038                 for(i = 0, n = get_irn_arity(curr); i < n; ++i) {
1039                         if (check_dependence(get_irn_n(curr, i), tgt, bl))
1040                                 return 1;
1041                 }
1042         }
1043
1044         return 0;
1045 }
1046 #endif /* if 0 */
1047
1048 /**
1049  * Check if a node is somehow data dependent on another one.
1050  * both nodes must be in the same basic block.
1051  * @param n1 The first node.
1052  * @param n2 The second node.
1053  * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
1054  */
1055 static int dependent_on(ir_node *n1, ir_node *n2)
1056 {
1057         assert(get_nodes_block(n1) == get_nodes_block(n2));
1058
1059         return heights_reachable_in_block(ir_heights, n1, n2);
1060 }
1061
1062 static int cmp_call_dependency(const void *c1, const void *c2)
1063 {
1064         ir_node *n1 = *(ir_node **) c1;
1065         ir_node *n2 = *(ir_node **) c2;
1066
1067         /*
1068                 Classical qsort() comparison function behavior:
1069                 0  if both elements are equal
1070                 1  if second is "smaller" that first
1071                 -1 if first is "smaller" that second
1072         */
1073         if (dependent_on(n1, n2))
1074                 return -1;
1075
1076         if (dependent_on(n2, n1))
1077                 return 1;
1078
1079         return 0;
1080 }
1081
1082 /**
1083  * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
1084  * Clears the irg_is_leaf flag if a Call is detected.
1085  */
1086 static void link_ops_in_block_walker(ir_node *irn, void *data)
1087 {
1088         ir_opcode code = get_irn_opcode(irn);
1089
1090         if (code == iro_Call ||
1091            (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
1092            (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
1093                 be_abi_irg_t *env = data;
1094                 ir_node *bl       = get_nodes_block(irn);
1095                 void *save        = get_irn_link(bl);
1096
1097                 if (code == iro_Call)
1098                         env->call->flags.bits.irg_is_leaf = 0;
1099
1100                 set_irn_link(irn, save);
1101                 set_irn_link(bl, irn);
1102         }
1103 }
1104
1105 /**
1106  * Block-walker:
1107  * Process all Call/Alloc/Free nodes inside a basic block.
1108  * Note that the link field of the block must contain a linked list of all
1109  * Call nodes inside the Block. We first order this list according to data dependency
1110  * and that connect the calls together.
1111  */
1112 static void process_ops_in_block(ir_node *bl, void *data)
1113 {
1114         be_abi_irg_t *env = data;
1115         ir_node *curr_sp  = env->init_sp;
1116         ir_node *irn;
1117         int n;
1118
1119         for (irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
1120                 obstack_ptr_grow(&env->obst, irn);
1121
1122         /* If there were call nodes in the block. */
1123         if (n > 0) {
1124                 ir_node *keep;
1125                 ir_node **nodes;
1126                 int i;
1127
1128                 nodes = obstack_finish(&env->obst);
1129
1130                 /* order the call nodes according to data dependency */
1131                 qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependency);
1132
1133                 for (i = n - 1; i >= 0; --i) {
1134                         ir_node *irn = nodes[i];
1135
1136                         DBG((env->dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1137                         switch (get_irn_opcode(irn)) {
1138                         case iro_Call:
1139                                 if (! be_omit_fp) {
1140                                         /* The stack pointer will be modified due to a call. */
1141                                         env->call->flags.bits.try_omit_fp = 0;
1142                                 }
1143                                 curr_sp = adjust_call(env, irn, curr_sp);
1144                                 break;
1145                         case iro_Alloc:
1146                                 if (get_Alloc_where(irn) == stack_alloc)
1147                                         curr_sp = adjust_alloc(env, irn, curr_sp);
1148                                 break;
1149                         case iro_Free:
1150                                 if (get_Free_where(irn) == stack_alloc)
1151                                         curr_sp = adjust_free(env, irn, curr_sp);
1152                                 break;
1153                         default:
1154                                 panic("invalid call");
1155                                 break;
1156                         }
1157                 }
1158
1159                 obstack_free(&env->obst, nodes);
1160
1161                 /* Keep the last stack state in the block by tying it to Keep node,
1162                  * the proj from calls is already kept */
1163                 if (curr_sp != env->init_sp &&
1164                     !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1165                         nodes[0] = curr_sp;
1166                         keep     = be_new_Keep(env->arch_env->sp->reg_class,
1167                                                get_irn_irg(bl), bl, 1, nodes);
1168                         pmap_insert(env->keep_map, bl, keep);
1169                 }
1170         }
1171
1172         set_irn_link(bl, curr_sp);
1173 }  /* process_calls_in_block */
1174
1175 /**
1176  * Adjust all call nodes in the graph to the ABI conventions.
1177  */
1178 static void process_calls(be_abi_irg_t *env)
1179 {
1180         ir_graph *irg = env->birg->irg;
1181
1182         env->call->flags.bits.irg_is_leaf = 1;
1183         irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, env);
1184
1185         ir_heights = heights_new(env->birg->irg);
1186         irg_block_walk_graph(irg, NULL, process_ops_in_block, env);
1187         heights_free(ir_heights);
1188 }
1189
1190 /**
1191  * Computes the stack argument layout type.
1192  * Changes a possibly allocated value param type by moving
1193  * entities to the stack layout type.
1194  *
1195  * @param env          the ABI environment
1196  * @param call         the current call ABI
1197  * @param method_type  the method type
1198  * @param param_map    an array mapping method arguments to the stack layout type
1199  *
1200  * @return the stack argument layout type
1201  */
1202 static ir_type *compute_arg_type(be_abi_irg_t *env, be_abi_call_t *call, ir_type *method_type, ir_entity ***param_map)
1203 {
1204         int dir  = env->call->flags.bits.left_to_right ? 1 : -1;
1205         int inc  = env->birg->main_env->arch_env->stack_dir * dir;
1206         int n    = get_method_n_params(method_type);
1207         int curr = inc > 0 ? 0 : n - 1;
1208         int ofs  = 0;
1209
1210         char buf[128];
1211         ir_type *res;
1212         int i;
1213         ir_type *val_param_tp = get_method_value_param_type(method_type);
1214         ident *id = get_entity_ident(get_irg_entity(env->birg->irg));
1215         ir_entity **map;
1216
1217         *param_map = map = obstack_alloc(&env->obst, n * sizeof(ir_entity *));
1218         res = new_type_struct(mangle_u(id, new_id_from_chars("arg_type", 8)));
1219         for (i = 0; i < n; ++i, curr += inc) {
1220                 ir_type *param_type    = get_method_param_type(method_type, curr);
1221                 be_abi_call_arg_t *arg = get_call_arg(call, 0, curr);
1222
1223                 map[i] = NULL;
1224                 if (arg->on_stack) {
1225                         if (val_param_tp) {
1226                                 /* the entity was already created, move it to the param type */
1227                                 arg->stack_ent = get_method_value_param_ent(method_type, i);
1228                                 remove_struct_member(val_param_tp, arg->stack_ent);
1229                                 set_entity_owner(arg->stack_ent, res);
1230                                 add_struct_member(res, arg->stack_ent);
1231                                 /* must be automatic to set a fixed layout */
1232                                 set_entity_allocation(arg->stack_ent, allocation_automatic);
1233                         }
1234                         else {
1235                                 snprintf(buf, sizeof(buf), "param_%d", i);
1236                                 arg->stack_ent = new_entity(res, new_id_from_str(buf), param_type);
1237                         }
1238                         ofs += arg->space_before;
1239                         ofs = round_up2(ofs, arg->alignment);
1240                         set_entity_offset(arg->stack_ent, ofs);
1241                         ofs += arg->space_after;
1242                         ofs += get_type_size_bytes(param_type);
1243                         map[i] = arg->stack_ent;
1244                 }
1245         }
1246         set_type_size_bytes(res, ofs);
1247         set_type_state(res, layout_fixed);
1248         return res;
1249 }
1250
1251 #if 0
1252 static void create_register_perms(const arch_isa_t *isa, ir_graph *irg, ir_node *bl, pmap *regs)
1253 {
1254         int i, j, n;
1255         struct obstack obst;
1256
1257         obstack_init(&obst);
1258
1259         /* Create a Perm after the RegParams node to delimit it. */
1260         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
1261                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
1262                 ir_node *perm;
1263                 ir_node **in;
1264                 int n_regs;
1265
1266                 for(n_regs = 0, j = 0; j < cls->n_regs; ++j) {
1267                         const arch_register_t *reg = &cls->regs[j];
1268                         ir_node *irn = pmap_get(regs, (void *) reg);
1269
1270                         if(irn && !arch_register_type_is(reg, ignore)) {
1271                                 n_regs++;
1272                                 obstack_ptr_grow(&obst, irn);
1273                                 set_irn_link(irn, (void *) reg);
1274                         }
1275                 }
1276
1277                 obstack_ptr_grow(&obst, NULL);
1278                 in = obstack_finish(&obst);
1279                 if(n_regs > 0) {
1280                         perm = be_new_Perm(cls, irg, bl, n_regs, in);
1281                         for(j = 0; j < n_regs; ++j) {
1282                                 ir_node *arg = in[j];
1283                                 arch_register_t *reg = get_irn_link(arg);
1284                                 pmap_insert(regs, reg, arg);
1285                                 be_set_constr_single_reg(perm, BE_OUT_POS(j), reg);
1286                         }
1287                 }
1288                 obstack_free(&obst, in);
1289         }
1290
1291         obstack_free(&obst, NULL);
1292 }
1293 #endif
1294
1295 typedef struct {
1296         const arch_register_t *reg;
1297         ir_node *irn;
1298 } reg_node_map_t;
1299
1300 static int cmp_regs(const void *a, const void *b)
1301 {
1302         const reg_node_map_t *p = a;
1303         const reg_node_map_t *q = b;
1304
1305         if(p->reg->reg_class == q->reg->reg_class)
1306                 return p->reg->index - q->reg->index;
1307         else
1308                 return p->reg->reg_class - q->reg->reg_class;
1309 }
1310
1311 static reg_node_map_t *reg_map_to_arr(struct obstack *obst, pmap *reg_map)
1312 {
1313         pmap_entry *ent;
1314         int n = pmap_count(reg_map);
1315         int i = 0;
1316         reg_node_map_t *res = obstack_alloc(obst, n * sizeof(res[0]));
1317
1318         foreach_pmap(reg_map, ent) {
1319                 res[i].reg = ent->key;
1320                 res[i].irn = ent->value;
1321                 i++;
1322         }
1323
1324         qsort(res, n, sizeof(res[0]), cmp_regs);
1325         return res;
1326 }
1327
1328 /**
1329  * Creates a barrier.
1330  */
1331 static ir_node *create_barrier(be_abi_irg_t *env, ir_node *bl, ir_node **mem, pmap *regs, int in_req)
1332 {
1333         ir_graph *irg = env->birg->irg;
1334         int n_regs    = pmap_count(regs);
1335         int n;
1336         ir_node *irn;
1337         ir_node **in;
1338         reg_node_map_t *rm;
1339
1340         rm = reg_map_to_arr(&env->obst, regs);
1341
1342         for(n = 0; n < n_regs; ++n)
1343                 obstack_ptr_grow(&env->obst, rm[n].irn);
1344
1345         if(mem) {
1346                 obstack_ptr_grow(&env->obst, *mem);
1347                 n++;
1348         }
1349
1350         in = (ir_node **) obstack_finish(&env->obst);
1351         irn = be_new_Barrier(irg, bl, n, in);
1352         obstack_free(&env->obst, in);
1353
1354         for(n = 0; n < n_regs; ++n) {
1355                 const arch_register_t *reg = rm[n].reg;
1356                 int flags                  = 0;
1357                 int pos                    = BE_OUT_POS(n);
1358                 ir_node *proj;
1359
1360                 proj = new_r_Proj(irg, bl, irn, get_irn_mode(rm[n].irn), n);
1361                 be_node_set_reg_class(irn, n, reg->reg_class);
1362                 if(in_req)
1363                         be_set_constr_single_reg(irn, n, reg);
1364                 be_set_constr_single_reg(irn, pos, reg);
1365                 be_node_set_reg_class(irn, pos, reg->reg_class);
1366                 arch_set_irn_register(env->birg->main_env->arch_env, proj, reg);
1367
1368                 /* if the proj projects a ignore register or a node which is set to ignore, propagate this property. */
1369                 if(arch_register_type_is(reg, ignore) || arch_irn_is(env->birg->main_env->arch_env, in[n], ignore))
1370                         flags |= arch_irn_flags_ignore;
1371
1372                 if(arch_irn_is(env->birg->main_env->arch_env, in[n], modify_sp))
1373                         flags |= arch_irn_flags_modify_sp;
1374
1375                 be_node_set_flags(irn, pos, flags);
1376
1377                 pmap_insert(regs, (void *) reg, proj);
1378         }
1379
1380         if(mem) {
1381                 *mem = new_r_Proj(irg, bl, irn, mode_M, n);
1382         }
1383
1384         obstack_free(&env->obst, rm);
1385         return irn;
1386 }
1387
1388 /**
1389  * Creates a be_Return for a Return node.
1390  *
1391  * @param @env    the abi environment
1392  * @param irn     the Return node or NULL if there was none
1393  * @param bl      the block where the be_Retun should be placed
1394  * @param mem     the current memory
1395  * @param n_res   number of return results
1396  */
1397 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1398                 ir_node *mem, int n_res)
1399 {
1400         be_abi_call_t    *call     = env->call;
1401         const arch_env_t *arch_env = env->birg->main_env->arch_env;
1402         dbg_info *dbgi;
1403         pmap *reg_map  = pmap_create();
1404         ir_node *keep  = pmap_get(env->keep_map, bl);
1405         int in_max;
1406         ir_node *ret;
1407         int i, n;
1408         unsigned pop;
1409         ir_node **in;
1410         ir_node *stack;
1411         const arch_register_t **regs;
1412         pmap_entry *ent ;
1413
1414         /*
1415                 get the valid stack node in this block.
1416                 If we had a call in that block there is a Keep constructed by process_calls()
1417                 which points to the last stack modification in that block. we'll use
1418                 it then. Else we use the stack from the start block and let
1419                 the ssa construction fix the usage.
1420         */
1421         stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1422         if (keep) {
1423                 stack = get_irn_n(keep, 0);
1424                 kill_node(keep);
1425                 remove_End_keepalive(get_irg_end(env->birg->irg), keep);
1426         }
1427
1428         /* Insert results for Return into the register map. */
1429         for(i = 0; i < n_res; ++i) {
1430                 ir_node *res           = get_Return_res(irn, i);
1431                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1432                 assert(arg->in_reg && "return value must be passed in register");
1433                 pmap_insert(reg_map, (void *) arg->reg, res);
1434         }
1435
1436         /* Add uses of the callee save registers. */
1437         foreach_pmap(env->regs, ent) {
1438                 const arch_register_t *reg = ent->key;
1439                 if(arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1440                         pmap_insert(reg_map, ent->key, ent->value);
1441         }
1442
1443         be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1444
1445         /* Make the Epilogue node and call the arch's epilogue maker. */
1446         create_barrier(env, bl, &mem, reg_map, 1);
1447         call->cb->epilogue(env->cb, bl, &mem, reg_map);
1448
1449         /*
1450                 Maximum size of the in array for Return nodes is
1451                 return args + callee save/ignore registers + memory + stack pointer
1452         */
1453         in_max = pmap_count(reg_map) + n_res + 2;
1454
1455         in   = obstack_alloc(&env->obst, in_max * sizeof(in[0]));
1456         regs = obstack_alloc(&env->obst, in_max * sizeof(regs[0]));
1457
1458         in[0]   = mem;
1459         in[1]   = be_abi_reg_map_get(reg_map, arch_env->sp);
1460         regs[0] = NULL;
1461         regs[1] = arch_env->sp;
1462         n       = 2;
1463
1464         /* clear SP entry, since it has already been grown. */
1465         pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1466         for(i = 0; i < n_res; ++i) {
1467                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1468
1469                 in[n]     = be_abi_reg_map_get(reg_map, arg->reg);
1470                 regs[n++] = arg->reg;
1471
1472                 /* Clear the map entry to mark the register as processed. */
1473                 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1474         }
1475
1476         /* grow the rest of the stuff. */
1477         foreach_pmap(reg_map, ent) {
1478                 if(ent->value) {
1479                         in[n]     = ent->value;
1480                         regs[n++] = ent->key;
1481                 }
1482         }
1483
1484         /* The in array for the new back end return is now ready. */
1485         if(irn != NULL) {
1486                 dbgi = get_irn_dbg_info(irn);
1487         } else {
1488                 dbgi = NULL;
1489         }
1490         /* we have to pop the shadow parameter in in case of struct returns */
1491         pop = call->pop;
1492         ret = be_new_Return(dbgi, env->birg->irg, bl, n_res, pop, n, in);
1493
1494         /* Set the register classes of the return's parameter accordingly. */
1495         for(i = 0; i < n; ++i)
1496                 if(regs[i])
1497                         be_node_set_reg_class(ret, i, regs[i]->reg_class);
1498
1499         /* Free the space of the Epilog's in array and the register <-> proj map. */
1500         obstack_free(&env->obst, in);
1501         pmap_destroy(reg_map);
1502
1503         return ret;
1504 }
1505
1506 typedef struct lower_frame_sels_env_t {
1507         be_abi_irg_t *env;
1508         ir_entity    *value_param_list;  /**< the list of all value param entities */
1509         ir_entity    *value_param_tail;  /**< the tail of the list of all value param entities */
1510 } lower_frame_sels_env_t;
1511
1512 /**
1513  * Walker: Replaces Sels of frame type and
1514  * value param type entities by FrameAddress.
1515  * Links all used entities.
1516  */
1517 static void lower_frame_sels_walker(ir_node *irn, void *data) {
1518         lower_frame_sels_env_t *ctx = data;
1519
1520         if (is_Sel(irn)) {
1521                 ir_graph *irg        = current_ir_graph;
1522                 ir_node  *frame      = get_irg_frame(irg);
1523                 ir_node  *param_base = get_irg_value_param_base(irg);
1524                 ir_node  *ptr        = get_Sel_ptr(irn);
1525
1526                 if (ptr == frame || ptr == param_base) {
1527                         be_abi_irg_t *env = ctx->env;
1528                         ir_entity    *ent = get_Sel_entity(irn);
1529                         ir_node      *bl  = get_nodes_block(irn);
1530                         ir_node      *nw;
1531
1532                         nw = be_new_FrameAddr(env->arch_env->sp->reg_class, irg, bl, frame, ent);
1533                         exchange(irn, nw);
1534
1535                         /* check, if it's a param sel and if have not seen this entity before */
1536                         if (ptr == param_base &&
1537                                         ent != ctx->value_param_tail &&
1538                                         get_entity_link(ent) == NULL) {
1539                                 set_entity_link(ent, ctx->value_param_list);
1540                                 ctx->value_param_list = ent;
1541                                 if (ctx->value_param_tail == NULL) ctx->value_param_tail = ent;
1542                         }
1543                 }
1544         }
1545 }
1546
1547 /**
1548  * Check if a value parameter is transmitted as a register.
1549  * This might happen if the address of an parameter is taken which is
1550  * transmitted in registers.
1551  *
1552  * Note that on some architectures this case must be handled specially
1553  * because the place of the backing store is determined by their ABI.
1554  *
1555  * In the default case we move the entity to the frame type and create
1556  * a backing store into the first block.
1557  */
1558 static void fix_address_of_parameter_access(be_abi_irg_t *env, ir_entity *value_param_list) {
1559         be_abi_call_t *call = env->call;
1560         ir_graph *irg       = env->birg->irg;
1561         ir_entity *ent, *next_ent, *new_list;
1562         ir_type *frame_tp;
1563         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1564
1565         new_list = NULL;
1566         for (ent = value_param_list; ent; ent = next_ent) {
1567                 int i = get_struct_member_index(get_entity_owner(ent), ent);
1568                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1569
1570                 next_ent = get_entity_link(ent);
1571                 if (arg->in_reg) {
1572                         DBG((dbg, LEVEL_2, "\targ #%d need backing store\n", i));
1573                         set_entity_link(ent, new_list);
1574                         new_list = ent;
1575                 }
1576         }
1577         if (new_list) {
1578                 /* ok, change the graph */
1579                 ir_node *start_bl = get_irg_start_block(irg);
1580                 ir_node *first_bl = NULL;
1581                 ir_node *frame, *imem, *nmem, *store, *mem, *args, *args_bl;
1582                 const ir_edge_t *edge;
1583                 optimization_state_t state;
1584                 unsigned offset;
1585
1586                 foreach_block_succ(start_bl, edge) {
1587                         ir_node *succ = get_edge_src_irn(edge);
1588                         if (start_bl != succ) {
1589                                 first_bl = succ;
1590                                 break;
1591                         }
1592                 }
1593                 assert(first_bl);
1594                 /* we had already removed critical edges, so the following
1595                    assertion should be always true. */
1596                 assert(get_Block_n_cfgpreds(first_bl) == 1);
1597
1598                 /* now create backing stores */
1599                 frame = get_irg_frame(irg);
1600                 imem = get_irg_initial_mem(irg);
1601
1602                 save_optimization_state(&state);
1603                 set_optimize(0);
1604                 nmem = new_r_Proj(irg, first_bl, get_irg_start(irg), mode_M, pn_Start_M);
1605                 restore_optimization_state(&state);
1606
1607                 /* reroute all edges to the new memory source */
1608                 edges_reroute(imem, nmem, irg);
1609
1610                 store   = NULL;
1611                 mem     = imem;
1612                 args    = get_irg_args(irg);
1613                 args_bl = get_nodes_block(args);
1614                 for (ent = new_list; ent; ent = get_entity_link(ent)) {
1615                         int     i     = get_struct_member_index(get_entity_owner(ent), ent);
1616                         ir_type *tp   = get_entity_type(ent);
1617                         ir_mode *mode = get_type_mode(tp);
1618                         ir_node *addr;
1619
1620                         /* address for the backing store */
1621                         addr = be_new_FrameAddr(env->arch_env->sp->reg_class, irg, first_bl, frame, ent);
1622
1623                         if (store)
1624                                 mem = new_r_Proj(irg, first_bl, store, mode_M, pn_Store_M);
1625
1626                         /* the backing store itself */
1627                         store = new_r_Store(irg, first_bl, mem, addr,
1628                                             new_r_Proj(irg, args_bl, args, mode, i));
1629                 }
1630                 /* the new memory Proj gets the last Proj from store */
1631                 set_Proj_pred(nmem, store);
1632                 set_Proj_proj(nmem, pn_Store_M);
1633
1634                 /* move all entities to the frame type */
1635                 frame_tp = get_irg_frame_type(irg);
1636                 offset   = get_type_size_bytes(frame_tp);
1637
1638                 /* we will add new entities: set the layout to undefined */
1639                 assert(get_type_state(frame_tp) == layout_fixed);
1640                 set_type_state(frame_tp, layout_undefined);
1641                 for (ent = new_list; ent; ent = get_entity_link(ent)) {
1642                         ir_type  *tp   = get_entity_type(ent);
1643                         unsigned align = get_type_alignment_bytes(tp);
1644
1645                         offset += align - 1;
1646                         offset &= ~(align - 1);
1647                         set_entity_owner(ent, frame_tp);
1648                         add_class_member(frame_tp, ent);
1649                         /* must be automatic to set a fixed layout */
1650                         set_entity_allocation(ent, allocation_automatic);
1651                         set_entity_offset(ent, offset);
1652                         offset += get_type_size_bytes(tp);
1653                 }
1654                 set_type_size_bytes(frame_tp, offset);
1655                 /* fix the layout again */
1656                 set_type_state(frame_tp, layout_fixed);
1657         }
1658 }
1659
1660 #if 1
1661 /**
1662  * The start block has no jump, instead it has an initial exec Proj.
1663  * The backend wants to handle all blocks the same way, so we replace
1664  * the out cfg edge with a real jump.
1665  */
1666 static void fix_start_block(ir_node *block, void *env) {
1667         int      *done = env;
1668         int      i;
1669         ir_node  *start_block;
1670         ir_graph *irg;
1671
1672         /* we processed the start block, return */
1673         if (*done)
1674                 return;
1675
1676         irg         = get_irn_irg(block);
1677         start_block = get_irg_start_block(irg);
1678
1679         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
1680                 ir_node *pred       = get_Block_cfgpred(block, i);
1681                 ir_node *pred_block = get_nodes_block(pred);
1682
1683                 /* ok, we are in the block, having start as cfg predecessor */
1684                 if (pred_block == start_block) {
1685                         ir_node *jump = new_r_Jmp(irg, pred_block);
1686                         set_Block_cfgpred(block, i, jump);
1687                         *done = 1;
1688                 }
1689         }
1690 }
1691 #endif
1692
1693 /**
1694  * Modify the irg itself and the frame type.
1695  */
1696 static void modify_irg(be_abi_irg_t *env)
1697 {
1698         be_abi_call_t *call       = env->call;
1699         const arch_env_t *arch_env= env->birg->main_env->arch_env;
1700         const arch_register_t *sp = arch_env_sp(arch_env);
1701         ir_graph *irg             = env->birg->irg;
1702         ir_node *bl               = get_irg_start_block(irg);
1703         ir_node *end              = get_irg_end_block(irg);
1704         ir_node *old_mem          = get_irg_initial_mem(irg);
1705         ir_node *new_mem_proj;
1706         ir_node *mem;
1707         ir_type *method_type      = get_entity_type(get_irg_entity(irg));
1708         pset *dont_save           = pset_new_ptr(8);
1709
1710         int n_params;
1711         int i, n;
1712         unsigned j;
1713
1714         reg_node_map_t *rm;
1715         const arch_register_t *fp_reg;
1716         ir_node *frame_pointer;
1717         ir_node *reg_params_bl;
1718         ir_node **args;
1719         ir_node *arg_tuple;
1720         ir_node *value_param_base;
1721         const ir_edge_t *edge;
1722         ir_type *arg_type, *bet_type, *tp;
1723         lower_frame_sels_env_t ctx;
1724         ir_entity **param_map;
1725
1726         bitset_t *used_proj_nr;
1727         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1728
1729         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1730
1731         /* set the links of all frame entities to NULL, we use it
1732            to detect if an entity is already linked in the value_param_list */
1733         tp = get_method_value_param_type(method_type);
1734         if (tp != NULL) {
1735                 for (i = get_struct_n_members(tp) - 1; i >= 0; --i)
1736                         set_entity_link(get_struct_member(tp, i), NULL);
1737         }
1738
1739         /* Convert the Sel nodes in the irg to frame load/store/addr nodes. */
1740         ctx.env              = env;
1741         ctx.value_param_list = NULL;
1742         ctx.value_param_tail = NULL;
1743         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1744
1745         /* value_param_base anchor is not needed anymore now */
1746         value_param_base = get_irg_value_param_base(irg);
1747         kill_node(value_param_base);
1748         set_irg_value_param_base(irg, new_r_Bad(irg));
1749
1750         env->frame = obstack_alloc(&env->obst, sizeof(env->frame[0]));
1751         env->regs  = pmap_create();
1752
1753         used_proj_nr = bitset_alloca(1024);
1754         n_params     = get_method_n_params(method_type);
1755         args         = obstack_alloc(&env->obst, n_params * sizeof(args[0]));
1756         memset(args, 0, n_params * sizeof(args[0]));
1757
1758         /* Check if a value parameter is transmitted as a register.
1759          * This might happen if the address of an parameter is taken which is
1760          * transmitted in registers.
1761          *
1762          * Note that on some architectures this case must be handled specially
1763          * because the place of the backing store is determined by their ABI.
1764          *
1765          * In the default case we move the entity to the frame type and create
1766          * a backing store into the first block.
1767          */
1768         fix_address_of_parameter_access(env, ctx.value_param_list);
1769
1770         /* Fill the argument vector */
1771         arg_tuple = get_irg_args(irg);
1772         foreach_out_edge(arg_tuple, edge) {
1773                 ir_node *irn = get_edge_src_irn(edge);
1774                 if (! is_Anchor(irn)) {
1775                         int nr       = get_Proj_proj(irn);
1776                         args[nr]     = irn;
1777                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1778                 }
1779         }
1780
1781         arg_type = compute_arg_type(env, call, method_type, &param_map);
1782         bet_type = call->cb->get_between_type(env->cb);
1783         stack_frame_init(env->frame, arg_type, bet_type, get_irg_frame_type(irg), arch_env->stack_dir, param_map);
1784
1785         /* Count the register params and add them to the number of Projs for the RegParams node */
1786         for(i = 0; i < n_params; ++i) {
1787                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1788                 if(arg->in_reg && args[i]) {
1789                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1790                         assert(i == get_Proj_proj(args[i]));
1791
1792                         /* For now, associate the register with the old Proj from Start representing that argument. */
1793                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1794                         bitset_set(used_proj_nr, i);
1795                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1796                 }
1797         }
1798
1799         /* Collect all callee-save registers */
1800         for(i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
1801                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
1802                 for(j = 0; j < cls->n_regs; ++j) {
1803                         const arch_register_t *reg = &cls->regs[j];
1804                         if(arch_register_type_is(reg, callee_save) ||
1805                                         arch_register_type_is(reg, state)) {
1806                                 pmap_insert(env->regs, (void *) reg, NULL);
1807                         }
1808                 }
1809         }
1810
1811         pmap_insert(env->regs, (void *) sp, NULL);
1812         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1813         reg_params_bl   = get_irg_start_block(irg);
1814         env->reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(env->regs));
1815         add_irn_dep(env->reg_params, get_irg_start(irg));
1816
1817         /*
1818          * make proj nodes for the callee save registers.
1819          * memorize them, since Return nodes get those as inputs.
1820          *
1821          * Note, that if a register corresponds to an argument, the regs map contains
1822          * the old Proj from start for that argument.
1823          */
1824
1825         rm = reg_map_to_arr(&env->obst, env->regs);
1826         for(i = 0, n = pmap_count(env->regs); i < n; ++i) {
1827                 arch_register_t *reg = (void *) rm[i].reg;
1828                 ir_mode *mode        = reg->reg_class->mode;
1829                 long nr              = i;
1830                 int pos              = BE_OUT_POS((int) nr);
1831                 int flags            = 0;
1832
1833                 ir_node *proj;
1834
1835                 assert(nr >= 0);
1836                 bitset_set(used_proj_nr, nr);
1837                 proj = new_r_Proj(irg, reg_params_bl, env->reg_params, mode, nr);
1838                 pmap_insert(env->regs, (void *) reg, proj);
1839                 be_set_constr_single_reg(env->reg_params, pos, reg);
1840                 arch_set_irn_register(env->birg->main_env->arch_env, proj, reg);
1841
1842                 /*
1843                  * If the register is an ignore register,
1844                  * The Proj for that register shall also be ignored during register allocation.
1845                  */
1846                 if(arch_register_type_is(reg, ignore))
1847                         flags |= arch_irn_flags_ignore;
1848
1849                 if(reg == sp)
1850                         flags |= arch_irn_flags_modify_sp;
1851
1852                 be_node_set_flags(env->reg_params, pos, flags);
1853
1854                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1855         }
1856         obstack_free(&env->obst, rm);
1857
1858         /* create a new initial memory proj */
1859         assert(is_Proj(old_mem));
1860         new_mem_proj = new_r_Proj(irg, get_nodes_block(old_mem),
1861                                   new_r_Unknown(irg, mode_T), mode_M,
1862                                   get_Proj_proj(old_mem));
1863         mem = new_mem_proj;
1864
1865         /* Generate the Prologue */
1866         fp_reg  = call->cb->prologue(env->cb, &mem, env->regs, &env->frame->initial_bias);
1867
1868         /* do the stack allocation BEFORE the barrier, or spill code
1869            might be added before it */
1870         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1871         env->init_sp = be_new_IncSP(sp, irg, bl, env->init_sp, BE_STACK_FRAME_SIZE_EXPAND, 0);
1872         be_abi_reg_map_set(env->regs, sp, env->init_sp);
1873
1874         create_barrier(env, bl, &mem, env->regs, 0);
1875
1876         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1877         arch_set_irn_register(env->birg->main_env->arch_env, env->init_sp, sp);
1878
1879         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1880         set_irg_frame(irg, frame_pointer);
1881         pset_insert_ptr(env->ignore_regs, fp_reg);
1882
1883         /* rewire old mem users to new mem */
1884         set_Proj_pred(new_mem_proj, get_Proj_pred(old_mem));
1885         exchange(old_mem, mem);
1886
1887         set_irg_initial_mem(irg, mem);
1888
1889         /* Now, introduce stack param nodes for all parameters passed on the stack */
1890         for(i = 0; i < n_params; ++i) {
1891                 ir_node *arg_proj = args[i];
1892                 ir_node *repl     = NULL;
1893
1894                 if(arg_proj != NULL) {
1895                         be_abi_call_arg_t *arg;
1896                         ir_type *param_type;
1897                         int     nr = get_Proj_proj(arg_proj);
1898                         ir_mode *mode;
1899
1900                         nr         = MIN(nr, n_params);
1901                         arg        = get_call_arg(call, 0, nr);
1902                         param_type = get_method_param_type(method_type, nr);
1903
1904                         if (arg->in_reg) {
1905                                 repl = pmap_get(env->regs, (void *) arg->reg);
1906                         } else if(arg->on_stack) {
1907                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, irg, reg_params_bl, frame_pointer, arg->stack_ent);
1908
1909                                 /* For atomic parameters which are actually used, we create a Load node. */
1910                                 if(is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1911                                         ir_mode *mode      = get_type_mode(param_type);
1912                                         ir_mode *load_mode = arg->load_mode;
1913
1914                                         ir_node *load = new_r_Load(irg, reg_params_bl, new_NoMem(), addr, load_mode);
1915                                         set_irn_pinned(load, op_pin_state_floats);
1916                                         repl = new_r_Proj(irg, reg_params_bl, load, load_mode, pn_Load_res);
1917
1918                                         if (mode != load_mode) {
1919                                                 repl = new_r_Conv(irg, reg_params_bl, repl, mode);
1920                                         }
1921                                 } else {
1922                                         /* The stack parameter is not primitive (it is a struct or array),
1923                                          * we thus will create a node representing the parameter's address
1924                                          * on the stack. */
1925                                         repl = addr;
1926                                 }
1927                         }
1928
1929                         assert(repl != NULL);
1930
1931                         /* Beware: the mode of the register parameters is always the mode of the register class
1932                            which may be wrong. Add Conv's then. */
1933                         mode = get_irn_mode(args[i]);
1934                         if (mode != get_irn_mode(repl)) {
1935                                 repl = new_r_Conv(irg, get_irn_n(repl, -1), repl, mode);
1936                         }
1937                         exchange(args[i], repl);
1938                 }
1939         }
1940
1941         /* the arg proj is not needed anymore now and should be only used by the anchor */
1942         assert(get_irn_n_edges(arg_tuple) == 1);
1943         kill_node(arg_tuple);
1944         set_irg_args(irg, new_rd_Bad(irg));
1945
1946         /* All Return nodes hang on the End node, so look for them there. */
1947         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1948                 ir_node *irn = get_Block_cfgpred(end, i);
1949
1950                 if (is_Return(irn)) {
1951                         ir_node *blk = get_nodes_block(irn);
1952                         ir_node *mem = get_Return_mem(irn);
1953                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1954                         exchange(irn, ret);
1955                 }
1956         }
1957         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1958            the code is dead and will never be executed. */
1959
1960         del_pset(dont_save);
1961         obstack_free(&env->obst, args);
1962
1963         /* handle start block here (place a jump in the block) */
1964         i = 0;
1965         irg_block_walk_graph(irg, fix_start_block, NULL, &i);
1966 }
1967
1968 /** Fix the state inputs of calls that still hang on unknowns */
1969 static
1970 void fix_call_state_inputs(be_abi_irg_t *env)
1971 {
1972         const arch_env_t *arch_env = env->arch_env;
1973         int i, n, n_states;
1974         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1975
1976         /* Collect caller save registers */
1977         n = arch_env_get_n_reg_class(arch_env);
1978         for(i = 0; i < n; ++i) {
1979                 unsigned j;
1980                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
1981                 for(j = 0; j < cls->n_regs; ++j) {
1982                         const arch_register_t *reg = arch_register_for_index(cls, j);
1983                         if(arch_register_type_is(reg, state)) {
1984                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1985                         }
1986                 }
1987         }
1988
1989         n = ARR_LEN(env->calls);
1990         n_states = ARR_LEN(stateregs);
1991         for(i = 0; i < n; ++i) {
1992                 int s, arity;
1993                 ir_node *call = env->calls[i];
1994
1995                 arity = get_irn_arity(call);
1996
1997                 /* the state reg inputs are the last n inputs of the calls */
1998                 for(s = 0; s < n_states; ++s) {
1999                         int inp = arity - n_states + s;
2000                         const arch_register_t *reg = stateregs[s];
2001                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
2002
2003                         set_irn_n(call, inp, regnode);
2004                 }
2005         }
2006
2007         DEL_ARR_F(stateregs);
2008 }
2009
2010 /**
2011  * Create a trampoline entity for the given method.
2012  */
2013 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
2014 {
2015         ir_type   *type   = get_entity_type(method);
2016         ident     *old_id = get_entity_ld_ident(method);
2017         ident     *id     = mangle3("L", old_id, "$stub");
2018         ir_type   *parent = be->pic_trampolines_type;
2019         ir_entity *ent    = new_entity(parent, old_id, type);
2020         set_entity_ld_ident(ent, id);
2021         set_entity_visibility(ent, visibility_local);
2022         set_entity_variability(ent, variability_uninitialized);
2023
2024         return ent;
2025 }
2026
2027 /**
2028  * Returns the trampoline entity for the given method.
2029  */
2030 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
2031 {
2032         ir_entity *result = pmap_get(env->ent_trampoline_map, method);
2033         if (result == NULL) {
2034                 result = create_trampoline(env, method);
2035                 pmap_insert(env->ent_trampoline_map, method, result);
2036         }
2037
2038         return result;
2039 }
2040
2041 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
2042 {
2043         ident     *old_id = get_entity_ld_ident(entity);
2044         ident     *id     = mangle3("L", old_id, "$non_lazy_ptr");
2045         ir_type   *e_type = get_entity_type(entity);
2046         ir_type   *type   = new_type_pointer(id, e_type, mode_P_data);
2047         ir_type   *parent = be->pic_symbols_type;
2048         ir_entity *ent    = new_entity(parent, old_id, type);
2049         set_entity_ld_ident(ent, id);
2050         set_entity_visibility(ent, visibility_local);
2051         set_entity_variability(ent, variability_uninitialized);
2052
2053         return ent;
2054 }
2055
2056 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
2057 {
2058         ir_entity *result = pmap_get(env->ent_pic_symbol_map, entity);
2059         if (result == NULL) {
2060                 result = create_pic_symbol(env, entity);
2061                 pmap_insert(env->ent_pic_symbol_map, entity, result);
2062         }
2063
2064         return result;
2065 }
2066
2067
2068
2069 /**
2070  * Returns non-zero if a given entity can be accessed using a relative address.
2071  */
2072 static int can_address_relative(ir_entity *entity)
2073 {
2074         return get_entity_variability(entity) == variability_initialized
2075                 || get_entity_visibility(entity) == visibility_local;
2076 }
2077
2078 /** patches SymConsts to work in position independent code */
2079 static void fix_pic_symconsts(ir_node *node, void *data)
2080 {
2081         ir_graph     *irg;
2082         ir_node      *pic_base;
2083         ir_node      *add;
2084         ir_node      *block;
2085         ir_node      *unknown;
2086         ir_mode      *mode;
2087         ir_node      *load;
2088         ir_node      *load_res;
2089         be_abi_irg_t *env = data;
2090         int           arity, i;
2091         be_main_env_t *be = env->birg->main_env;
2092
2093         arity = get_irn_arity(node);
2094         for (i = 0; i < arity; ++i) {
2095                 dbg_info  *dbgi;
2096                 ir_node   *pred = get_irn_n(node, i);
2097                 ir_entity *entity;
2098                 ir_entity *pic_symbol;
2099                 ir_node   *pic_symconst;
2100
2101                 if (!is_SymConst(pred))
2102                         continue;
2103
2104                 entity = get_SymConst_entity(pred);
2105                 block  = get_nodes_block(pred);
2106                 irg    = get_irn_irg(pred);
2107
2108                 /* calls can jump to relative addresses, so we can directly jump to
2109                    the (relatively) known call address or the trampoline */
2110                 if (is_Call(node) && i == 1) {
2111                         ir_entity *trampoline;
2112                         ir_node   *trampoline_const;
2113
2114                         if (can_address_relative(entity))
2115                                 continue;
2116
2117                         dbgi             = get_irn_dbg_info(pred);
2118                         trampoline       = get_trampoline(be, entity);
2119                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2120                                                                     trampoline, NULL);
2121                         set_irn_n(node, i, trampoline_const);
2122                         continue;
2123                 }
2124
2125                 /* everything else is accessed relative to EIP */
2126                 mode     = get_irn_mode(pred);
2127                 unknown  = new_r_Unknown(irg, mode);
2128                 pic_base = arch_code_generator_get_pic_base(env->birg->cg);
2129                 add      = new_r_Add(irg, block, pic_base, pred, mode);
2130
2131                 /* make sure the walker doesn't visit this add again */
2132                 mark_irn_visited(add);
2133
2134                 /* all ok now for locally constructed stuff */
2135                 if (can_address_relative(entity)) {
2136                         set_irn_n(node, i, add);
2137                         continue;
2138                 }
2139
2140                 /* get entry from pic symbol segment */
2141                 dbgi         = get_irn_dbg_info(pred);
2142                 pic_symbol   = get_pic_symbol(be, entity);
2143                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2144                                                         pic_symbol, NULL);
2145                 set_Add_right(add, pic_symconst);
2146
2147                 /* we need an extra indirection for global data outside our current
2148                    module. The loads are always safe and can therefore float
2149                    and need no memory input */
2150                 load     = new_r_Load(irg, block, new_NoMem(), add, mode);
2151                 load_res = new_r_Proj(irg, block, load, mode, pn_Load_res);
2152                 set_irn_pinned(load, op_pin_state_floats);
2153
2154                 set_irn_n(node, i, load_res);
2155         }
2156 }
2157
2158 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
2159 {
2160         be_abi_irg_t *env  = xmalloc(sizeof(env[0]));
2161         ir_node *old_frame = get_irg_frame(birg->irg);
2162         ir_graph *irg      = birg->irg;
2163
2164         pmap_entry *ent;
2165         ir_node *dummy;
2166         optimization_state_t state;
2167         unsigned *limited_bitset;
2168
2169         be_omit_fp      = birg->main_env->options->omit_fp;
2170         be_omit_leaf_fp = birg->main_env->options->omit_leaf_fp;
2171
2172         obstack_init(&env->obst);
2173
2174         env->arch_env    = birg->main_env->arch_env;
2175         env->method_type = get_entity_type(get_irg_entity(irg));
2176         env->call        = be_abi_call_new(env->arch_env->sp->reg_class);
2177         arch_env_get_call_abi(env->arch_env, env->method_type, env->call);
2178
2179         env->ignore_regs  = pset_new_ptr_default();
2180         env->keep_map     = pmap_create();
2181         env->dce_survivor = new_survive_dce();
2182         env->birg         = birg;
2183
2184         env->sp_req.type    = arch_register_req_type_limited;
2185         env->sp_req.cls     = arch_register_get_class(env->arch_env->sp);
2186         limited_bitset      = rbitset_obstack_alloc(&env->obst, env->sp_req.cls->n_regs);
2187         rbitset_set(limited_bitset, arch_register_get_index(env->arch_env->sp));
2188         env->sp_req.limited = limited_bitset;
2189
2190         env->sp_cls_req.type  = arch_register_req_type_normal;
2191         env->sp_cls_req.cls   = arch_register_get_class(env->arch_env->sp);
2192
2193         /* Beware: later we replace this node by the real one, ensure it is not CSE'd
2194            to another Unknown or the stack pointer gets used */
2195         save_optimization_state(&state);
2196         set_optimize(0);
2197         env->init_sp = dummy  = new_r_Unknown(irg, env->arch_env->sp->reg_class->mode);
2198         restore_optimization_state(&state);
2199         FIRM_DBG_REGISTER(env->dbg, "firm.be.abi");
2200
2201         env->calls = NEW_ARR_F(ir_node*, 0);
2202
2203         if (birg->main_env->options->pic) {
2204                 irg_walk_graph(irg, fix_pic_symconsts, NULL, env);
2205         }
2206
2207         /* Lower all call nodes in the IRG. */
2208         process_calls(env);
2209
2210         /*
2211                 Beware: init backend abi call object after processing calls,
2212                 otherwise some information might be not yet available.
2213         */
2214         env->cb = env->call->cb->init(env->call, birg->main_env->arch_env, irg);
2215
2216         /* Process the IRG */
2217         modify_irg(env);
2218
2219         /* fix call inputs for state registers */
2220         fix_call_state_inputs(env);
2221
2222         /* We don't need the keep map anymore. */
2223         pmap_destroy(env->keep_map);
2224         env->keep_map = NULL;
2225
2226         /* calls array is not needed anymore */
2227         DEL_ARR_F(env->calls);
2228         env->calls = NULL;
2229
2230         /* reroute the stack origin of the calls to the true stack origin. */
2231         exchange(dummy, env->init_sp);
2232         exchange(old_frame, get_irg_frame(irg));
2233
2234         /* Make some important node pointers survive the dead node elimination. */
2235         survive_dce_register_irn(env->dce_survivor, &env->init_sp);
2236         foreach_pmap(env->regs, ent) {
2237                 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
2238         }
2239
2240         env->call->cb->done(env->cb);
2241         env->cb = NULL;
2242         return env;
2243 }
2244
2245 void be_abi_free(be_abi_irg_t *env)
2246 {
2247         be_abi_call_free(env->call);
2248         free_survive_dce(env->dce_survivor);
2249         del_pset(env->ignore_regs);
2250         pmap_destroy(env->regs);
2251         obstack_free(&env->obst, NULL);
2252         free(env);
2253 }
2254
2255 void be_abi_put_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, bitset_t *bs)
2256 {
2257         arch_register_t *reg;
2258
2259         for(reg = pset_first(abi->ignore_regs); reg; reg = pset_next(abi->ignore_regs))
2260                 if(reg->reg_class == cls)
2261                         bitset_set(bs, reg->index);
2262 }
2263
2264 void be_abi_set_non_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, unsigned *raw_bitset)
2265 {
2266         unsigned         i;
2267         arch_register_t *reg;
2268
2269         for (i = 0; i < cls->n_regs; ++i) {
2270                 if (arch_register_type_is(&cls->regs[i], ignore))
2271                         continue;
2272
2273                 rbitset_set(raw_bitset, i);
2274         }
2275
2276         for (reg = pset_first(abi->ignore_regs); reg != NULL;
2277              reg = pset_next(abi->ignore_regs)) {
2278                 if (reg->reg_class != cls)
2279                         continue;
2280
2281                 rbitset_clear(raw_bitset, reg->index);
2282         }
2283 }
2284
2285 /* Returns the stack layout from a abi environment. */
2286 const be_stack_layout_t *be_abi_get_stack_layout(const be_abi_irg_t *abi) {
2287         return abi->frame;
2288 }
2289
2290 /*
2291
2292   _____ _        ____  _             _
2293  |  ___(_)_  __ / ___|| |_ __ _  ___| | __
2294  | |_  | \ \/ / \___ \| __/ _` |/ __| |/ /
2295  |  _| | |>  <   ___) | || (_| | (__|   <
2296  |_|   |_/_/\_\ |____/ \__\__,_|\___|_|\_\
2297
2298 */
2299
2300 typedef ir_node **node_array;
2301
2302 typedef struct fix_stack_walker_env_t {
2303         node_array sp_nodes;
2304         const arch_env_t *arch_env;
2305 } fix_stack_walker_env_t;
2306
2307 /**
2308  * Walker. Collect all stack modifying nodes.
2309  */
2310 static void collect_stack_nodes_walker(ir_node *node, void *data)
2311 {
2312         fix_stack_walker_env_t *env = data;
2313
2314         if (arch_irn_is(env->arch_env, node, modify_sp)) {
2315                 assert(get_irn_mode(node) != mode_M && get_irn_mode(node) != mode_T);
2316                 ARR_APP1(ir_node*, env->sp_nodes, node);
2317         }
2318 }
2319
2320 void be_abi_fix_stack_nodes(be_abi_irg_t *env)
2321 {
2322         be_ssa_construction_env_t senv;
2323         int i, len;
2324         ir_node **phis;
2325         be_irg_t *birg = env->birg;
2326         be_lv_t *lv = be_get_birg_liveness(birg);
2327         fix_stack_walker_env_t walker_env;
2328
2329         walker_env.sp_nodes = NEW_ARR_F(ir_node*, 0);
2330         walker_env.arch_env = birg->main_env->arch_env;
2331
2332         irg_walk_graph(birg->irg, collect_stack_nodes_walker, NULL, &walker_env);
2333
2334         /* nothing to be done if we didn't find any node, in fact we mustn't
2335          * continue, as for endless loops incsp might have had no users and is bad
2336          * now.
2337          */
2338         len = ARR_LEN(walker_env.sp_nodes);
2339         if(len == 0) {
2340                 DEL_ARR_F(walker_env.sp_nodes);
2341                 return;
2342         }
2343
2344         be_ssa_construction_init(&senv, birg);
2345         be_ssa_construction_add_copies(&senv, walker_env.sp_nodes,
2346                                    ARR_LEN(walker_env.sp_nodes));
2347         be_ssa_construction_fix_users_array(&senv, walker_env.sp_nodes,
2348                                       ARR_LEN(walker_env.sp_nodes));
2349
2350         if(lv != NULL) {
2351                 len = ARR_LEN(walker_env.sp_nodes);
2352                 for(i = 0; i < len; ++i) {
2353                         be_liveness_update(lv, walker_env.sp_nodes[i]);
2354                 }
2355                 be_ssa_construction_update_liveness_phis(&senv, lv);
2356         }
2357
2358         phis = be_ssa_construction_get_new_phis(&senv);
2359
2360         /* set register requirements for stack phis */
2361         len = ARR_LEN(phis);
2362         for(i = 0; i < len; ++i) {
2363                 ir_node *phi = phis[i];
2364                 be_set_phi_reg_req(walker_env.arch_env, phi, &env->sp_req);
2365                 be_set_phi_flags(walker_env.arch_env, phi, arch_irn_flags_ignore | arch_irn_flags_modify_sp);
2366                 arch_set_irn_register(walker_env.arch_env, phi, env->arch_env->sp);
2367         }
2368         be_ssa_construction_destroy(&senv);
2369
2370         DEL_ARR_F(walker_env.sp_nodes);
2371 }
2372
2373 /**
2374  * Fix all stack accessing operations in the block bl.
2375  *
2376  * @param env        the abi environment
2377  * @param bl         the block to process
2378  * @param real_bias  the bias value
2379  *
2380  * @return the bias at the end of this block
2381  */
2382 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int real_bias)
2383 {
2384         const arch_env_t *arch_env = env->birg->main_env->arch_env;
2385         int               omit_fp  = env->call->flags.bits.try_omit_fp;
2386         ir_node          *irn;
2387         int               wanted_bias = real_bias;
2388
2389         sched_foreach(bl, irn) {
2390                 int ofs;
2391
2392                 /*
2393                    Check, if the node relates to an entity on the stack frame.
2394                    If so, set the true offset (including the bias) for that
2395                    node.
2396                  */
2397                 ir_entity *ent = arch_get_frame_entity(arch_env, irn);
2398                 if (ent) {
2399                         int bias   = omit_fp ? real_bias : 0;
2400                         int offset = get_stack_entity_offset(env->frame, ent, bias);
2401                         arch_set_frame_offset(arch_env, irn, offset);
2402                         DBG((env->dbg, LEVEL_2, "%F has offset %d (including bias %d)\n",
2403                              ent, offset, bias));
2404                 }
2405
2406                 /*
2407                  * If the node modifies the stack pointer by a constant offset,
2408                  * record that in the bias.
2409                  */
2410                 ofs = arch_get_sp_bias(arch_env, irn);
2411
2412                 if (be_is_IncSP(irn)) {
2413                         /* fill in real stack frame size */
2414                         if (ofs == BE_STACK_FRAME_SIZE_EXPAND) {
2415                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2416                                 ofs = (int) get_type_size_bytes(frame_type);
2417                                 be_set_IncSP_offset(irn, ofs);
2418                         } else if (ofs == BE_STACK_FRAME_SIZE_SHRINK) {
2419                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2420                                 ofs = - (int)get_type_size_bytes(frame_type);
2421                                 be_set_IncSP_offset(irn, ofs);
2422                         } else {
2423                                 if (be_get_IncSP_align(irn)) {
2424                                         /* patch IncSP to produce an aligned stack pointer */
2425                                         ir_type *between_type = env->frame->between_type;
2426                                         int      between_size = get_type_size_bytes(between_type);
2427                                         int      alignment    = 1 << env->arch_env->stack_alignment;
2428                                         int      delta        = (real_bias + ofs + between_size) & (alignment - 1);
2429                                         assert(ofs >= 0);
2430                                         if (delta > 0) {
2431                                                 be_set_IncSP_offset(irn, ofs + alignment - delta);
2432                                                 real_bias += alignment - delta;
2433                                         }
2434                                 } else {
2435                                         /* adjust so real_bias corresponds with wanted_bias */
2436                                         int delta = wanted_bias - real_bias;
2437                                         assert(delta <= 0);
2438                                         if(delta != 0) {
2439                                                 be_set_IncSP_offset(irn, ofs + delta);
2440                                                 real_bias += delta;
2441                                         }
2442                                 }
2443                         }
2444                 }
2445
2446                 real_bias   += ofs;
2447                 wanted_bias += ofs;
2448         }
2449
2450         assert(real_bias == wanted_bias);
2451         return real_bias;
2452 }
2453
2454 /**
2455  * A helper struct for the bias walker.
2456  */
2457 struct bias_walk {
2458         be_abi_irg_t *env;     /**< The ABI irg environment. */
2459         int           start_block_bias;  /**< The bias at the end of the start block. */
2460         int           between_size;
2461         ir_node      *start_block;  /**< The start block of the current graph. */
2462 };
2463
2464 /**
2465  * Block-Walker: fix all stack offsets for all blocks
2466  * except the start block
2467  */
2468 static void stack_bias_walker(ir_node *bl, void *data)
2469 {
2470         struct bias_walk *bw = data;
2471         if (bl != bw->start_block) {
2472                 process_stack_bias(bw->env, bl, bw->start_block_bias);
2473         }
2474 }
2475
2476 void be_abi_fix_stack_bias(be_abi_irg_t *env)
2477 {
2478         be_stack_layout_t *frame = env->frame;
2479         ir_graph          *irg;
2480         struct bias_walk  bw;
2481
2482         stack_frame_compute_initial_offset(frame);
2483         // stack_layout_dump(stdout, frame);
2484
2485         /* Determine the stack bias at the end of the start block. */
2486         bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), frame->initial_bias);
2487         bw.between_size     = get_type_size_bytes(frame->between_type);
2488
2489         /* fix the bias is all other blocks */
2490         irg    = env->birg->irg;
2491         bw.env = env;
2492         bw.start_block = get_irg_start_block(irg);
2493         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
2494 }
2495
2496 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2497 {
2498         assert(arch_register_type_is(reg, callee_save));
2499         assert(pmap_contains(abi->regs, (void *) reg));
2500         return pmap_get(abi->regs, (void *) reg);
2501 }
2502
2503 ir_node *be_abi_get_ignore_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2504 {
2505         assert(arch_register_type_is(reg, ignore));
2506         assert(pmap_contains(abi->regs, (void *) reg));
2507         return pmap_get(abi->regs, (void *) reg);
2508 }
2509
2510 /**
2511  * Returns non-zero if the ABI has omitted the frame pointer in
2512  * the current graph.
2513  */
2514 int be_abi_omit_fp(const be_abi_irg_t *abi) {
2515         return abi->call->flags.bits.try_omit_fp;
2516 }