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