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

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