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

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