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