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 /**
1745  * Update the entity of Sels to the outer value parameters.
1746  */
1747 static void update_outer_frame_sels(ir_node *irn, void *env) {
1748         lower_frame_sels_env_t *ctx = env;
1749         ir_node                *ptr;
1750         ir_entity              *ent;
1751         int                    pos = 0;
1752
1753         if (! is_Sel(irn))
1754                 return;
1755         ptr = get_Sel_ptr(irn);
1756         if (! is_arg_Proj(ptr))
1757                 return;
1758         if (get_Proj_proj(ptr) != ctx->static_link_pos)
1759                 return;
1760         ent   = get_Sel_entity(irn);
1761
1762         if (get_entity_owner(ent) == ctx->value_tp) {
1763                 /* replace by its copy from the argument type */
1764                 pos = get_struct_member_index(ctx->value_tp, ent);
1765                 ent = get_argument_entity(ent, ctx);
1766                 set_Sel_entity(irn, ent);
1767
1768                 /* check, if we have not seen this entity before */
1769                 if (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 /**
1783  * Fix access to outer local variables.
1784  */
1785 static void fix_outer_variable_access(be_abi_irg_t *env,
1786                                       lower_frame_sels_env_t *ctx)
1787 {
1788         int      i;
1789         ir_graph *irg;
1790         (void) env;
1791
1792         for (i = get_class_n_members(ctx->frame_tp) - 1; i >= 0; --i) {
1793                 ir_entity *ent = get_class_member(ctx->frame_tp, i);
1794
1795                 if (! is_method_entity(ent))
1796                         continue;
1797                 if (get_entity_peculiarity(ent) == peculiarity_description)
1798                         continue;
1799
1800                 /*
1801                  * FIXME: find the number of the static link parameter
1802                  * for now we assume 0 here
1803                  */
1804                 ctx->static_link_pos = 0;
1805
1806                 irg = get_entity_irg(ent);
1807                 irg_walk_graph(irg, NULL, update_outer_frame_sels, ctx);
1808         }
1809 }
1810
1811 /**
1812  * Modify the irg itself and the frame type.
1813  */
1814 static void modify_irg(be_abi_irg_t *env)
1815 {
1816         be_abi_call_t *call       = env->call;
1817         const arch_env_t *arch_env= env->birg->main_env->arch_env;
1818         const arch_register_t *sp = arch_env->sp;
1819         ir_graph *irg             = env->birg->irg;
1820         ir_node *start_bl;
1821         ir_node *end;
1822         ir_node *old_mem;
1823         ir_node *new_mem_proj;
1824         ir_node *mem;
1825         ir_type *method_type      = get_entity_type(get_irg_entity(irg));
1826
1827         int n_params;
1828         int i, n;
1829         unsigned j;
1830
1831         reg_node_map_t *rm;
1832         const arch_register_t *fp_reg;
1833         ir_node *frame_pointer;
1834         ir_node *reg_params_bl;
1835         ir_node **args;
1836         ir_node *arg_tuple;
1837         const ir_edge_t *edge;
1838         ir_type *arg_type, *bet_type, *tp;
1839         lower_frame_sels_env_t ctx;
1840         ir_entity **param_map;
1841
1842         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1843
1844         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1845
1846         /* Must fetch memory here, otherwise the start Barrier gets the wrong
1847          * memory, which leads to loops in the DAG. */
1848         old_mem = get_irg_initial_mem(irg);
1849
1850         irp_reserve_resources(irp, IR_RESOURCE_ENTITY_LINK);
1851
1852         /* set the links of all frame entities to NULL, we use it
1853            to detect if an entity is already linked in the value_param_list */
1854         tp = get_method_value_param_type(method_type);
1855         ctx.value_tp = tp;
1856         if (tp != NULL) {
1857                 /* clear the links of the clone type, let the
1858                    original entities point to its clones */
1859                 for (i = get_struct_n_members(tp) - 1; i >= 0; --i) {
1860                         ir_entity *mem  = get_struct_member(tp, i);
1861                         set_entity_link(mem, NULL);
1862                 }
1863         }
1864
1865         arg_type = compute_arg_type(env, call, method_type, tp, &param_map);
1866
1867         /* Convert the Sel nodes in the irg to frame addr nodes: */
1868         ctx.value_param_list = NEW_ARR_F(ent_pos_pair, 0);
1869         ctx.frame            = get_irg_frame(irg);
1870         ctx.sp_class         = env->arch_env->sp->reg_class;
1871         ctx.link_class       = env->arch_env->link_class;
1872         ctx.frame_tp         = get_irg_frame_type(irg);
1873
1874         /* we will possible add new entities to the frame: set the layout to undefined */
1875         assert(get_type_state(ctx.frame_tp) == layout_fixed);
1876         set_type_state(ctx.frame_tp, layout_undefined);
1877
1878         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1879
1880         /* fix the frame type layout again */
1881         set_type_state(ctx.frame_tp, layout_fixed);
1882
1883         env->regs  = pmap_create();
1884
1885         n_params = get_method_n_params(method_type);
1886         args     = obstack_alloc(&env->obst, n_params * sizeof(args[0]));
1887         memset(args, 0, n_params * sizeof(args[0]));
1888
1889         /*
1890          * for inner function we must now fix access to outer frame entities.
1891          */
1892         fix_outer_variable_access(env, &ctx);
1893
1894         /* Check if a value parameter is transmitted as a register.
1895          * This might happen if the address of an parameter is taken which is
1896          * transmitted in registers.
1897          *
1898          * Note that on some architectures this case must be handled specially
1899          * because the place of the backing store is determined by their ABI.
1900          *
1901          * In the default case we move the entity to the frame type and create
1902          * a backing store into the first block.
1903          */
1904         fix_address_of_parameter_access(env, ctx.value_param_list);
1905
1906         DEL_ARR_F(ctx.value_param_list);
1907         irp_free_resources(irp, IR_RESOURCE_ENTITY_LINK);
1908
1909         /* Fill the argument vector */
1910         arg_tuple = get_irg_args(irg);
1911         foreach_out_edge(arg_tuple, edge) {
1912                 ir_node *irn = get_edge_src_irn(edge);
1913                 if (! is_Anchor(irn)) {
1914                         int nr       = get_Proj_proj(irn);
1915                         args[nr]     = irn;
1916                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1917                 }
1918         }
1919
1920         bet_type = call->cb->get_between_type(env->cb);
1921         stack_frame_init(&env->frame, arg_type, bet_type, get_irg_frame_type(irg), arch_env->stack_dir, param_map);
1922
1923         /* Count the register params and add them to the number of Projs for the RegParams node */
1924         for (i = 0; i < n_params; ++i) {
1925                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1926                 if (arg->in_reg && args[i]) {
1927                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1928                         assert(i == get_Proj_proj(args[i]));
1929
1930                         /* For now, associate the register with the old Proj from Start representing that argument. */
1931                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1932                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1933                 }
1934         }
1935
1936         /* Collect all callee-save registers */
1937         for (i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
1938                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
1939                 for (j = 0; j < cls->n_regs; ++j) {
1940                         const arch_register_t *reg = &cls->regs[j];
1941                         if (arch_register_type_is(reg, callee_save) ||
1942                                         arch_register_type_is(reg, state)) {
1943                                 pmap_insert(env->regs, (void *) reg, NULL);
1944                         }
1945                 }
1946         }
1947
1948         pmap_insert(env->regs, (void *) sp, NULL);
1949         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1950         reg_params_bl   = get_irg_start_block(irg);
1951         env->reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(env->regs));
1952         add_irn_dep(env->reg_params, get_irg_start(irg));
1953
1954         /*
1955          * make proj nodes for the callee save registers.
1956          * memorize them, since Return nodes get those as inputs.
1957          *
1958          * Note, that if a register corresponds to an argument, the regs map contains
1959          * the old Proj from start for that argument.
1960          */
1961
1962         rm = reg_map_to_arr(&env->obst, env->regs);
1963         for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1964                 arch_register_t          *reg      = (void *) rm[i].reg;
1965                 ir_mode                  *mode     = reg->reg_class->mode;
1966                 long                      nr       = i;
1967                 arch_register_req_type_t  add_type = 0;
1968                 ir_node                  *proj;
1969
1970                 if (reg == sp)
1971                         add_type |= arch_register_req_type_produces_sp | arch_register_req_type_ignore;
1972
1973                 assert(nr >= 0);
1974                 proj = new_r_Proj(irg, reg_params_bl, env->reg_params, mode, nr);
1975                 pmap_insert(env->regs, (void *) reg, proj);
1976                 be_set_constr_single_reg_out(env->reg_params, nr, reg, add_type);
1977                 arch_set_irn_register(proj, reg);
1978
1979                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1980         }
1981         obstack_free(&env->obst, rm);
1982
1983         /* create a new initial memory proj */
1984         assert(is_Proj(old_mem));
1985         new_mem_proj = new_r_Proj(irg, get_nodes_block(old_mem),
1986                                   new_r_Unknown(irg, mode_T), mode_M,
1987                                   get_Proj_proj(old_mem));
1988         mem = new_mem_proj;
1989
1990         /* Generate the Prologue */
1991         fp_reg = call->cb->prologue(env->cb, &mem, env->regs, &env->frame.initial_bias);
1992
1993         /* do the stack allocation BEFORE the barrier, or spill code
1994            might be added before it */
1995         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1996         start_bl     = get_irg_start_block(irg);
1997         env->init_sp = be_new_IncSP(sp, irg, start_bl, env->init_sp, BE_STACK_FRAME_SIZE_EXPAND, 0);
1998         be_abi_reg_map_set(env->regs, sp, env->init_sp);
1999
2000         create_barrier(env, start_bl, &mem, env->regs, 0);
2001
2002         env->init_sp = be_abi_reg_map_get(env->regs, sp);
2003         arch_set_irn_register(env->init_sp, sp);
2004
2005         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
2006         set_irg_frame(irg, frame_pointer);
2007         pset_insert_ptr(env->ignore_regs, fp_reg);
2008
2009         /* rewire old mem users to new mem */
2010         set_Proj_pred(new_mem_proj, get_Proj_pred(old_mem));
2011         exchange(old_mem, mem);
2012
2013         set_irg_initial_mem(irg, mem);
2014
2015         /* Now, introduce stack param nodes for all parameters passed on the stack */
2016         for (i = 0; i < n_params; ++i) {
2017                 ir_node *arg_proj = args[i];
2018                 ir_node *repl     = NULL;
2019
2020                 if (arg_proj != NULL) {
2021                         be_abi_call_arg_t *arg;
2022                         ir_type *param_type;
2023                         int     nr = get_Proj_proj(arg_proj);
2024                         ir_mode *mode;
2025
2026                         nr         = MIN(nr, n_params);
2027                         arg        = get_call_arg(call, 0, nr);
2028                         param_type = get_method_param_type(method_type, nr);
2029
2030                         if (arg->in_reg) {
2031                                 repl = pmap_get(env->regs, (void *) arg->reg);
2032                         } else if (arg->on_stack) {
2033                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, irg, reg_params_bl, frame_pointer, arg->stack_ent);
2034
2035                                 /* For atomic parameters which are actually used, we create a Load node. */
2036                                 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
2037                                         ir_mode *mode      = get_type_mode(param_type);
2038                                         ir_mode *load_mode = arg->load_mode;
2039
2040                                         ir_node *load = new_r_Load(irg, reg_params_bl, new_NoMem(), addr, load_mode, cons_floats);
2041                                         repl = new_r_Proj(irg, reg_params_bl, load, load_mode, pn_Load_res);
2042
2043                                         if (mode != load_mode) {
2044                                                 repl = new_r_Conv(irg, reg_params_bl, repl, mode);
2045                                         }
2046                                 } else {
2047                                         /* The stack parameter is not primitive (it is a struct or array),
2048                                          * we thus will create a node representing the parameter's address
2049                                          * on the stack. */
2050                                         repl = addr;
2051                                 }
2052                         }
2053
2054                         assert(repl != NULL);
2055
2056                         /* Beware: the mode of the register parameters is always the mode of the register class
2057                            which may be wrong. Add Conv's then. */
2058                         mode = get_irn_mode(args[i]);
2059                         if (mode != get_irn_mode(repl)) {
2060                                 repl = new_r_Conv(irg, get_irn_n(repl, -1), repl, mode);
2061                         }
2062                         exchange(args[i], repl);
2063                 }
2064         }
2065
2066         /* the arg proj is not needed anymore now and should be only used by the anchor */
2067         assert(get_irn_n_edges(arg_tuple) == 1);
2068         kill_node(arg_tuple);
2069         set_irg_args(irg, new_r_Bad(irg));
2070
2071         /* All Return nodes hang on the End node, so look for them there. */
2072         end = get_irg_end_block(irg);
2073         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
2074                 ir_node *irn = get_Block_cfgpred(end, i);
2075
2076                 if (is_Return(irn)) {
2077                         ir_node *blk = get_nodes_block(irn);
2078                         ir_node *mem = get_Return_mem(irn);
2079                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
2080                         exchange(irn, ret);
2081                 }
2082         }
2083         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
2084            the code is dead and will never be executed. */
2085
2086         obstack_free(&env->obst, args);
2087
2088         /* handle start block here (place a jump in the block) */
2089         fix_start_block(irg);
2090 }
2091
2092 /** Fix the state inputs of calls that still hang on unknowns */
2093 static
2094 void fix_call_state_inputs(be_abi_irg_t *env)
2095 {
2096         const arch_env_t *arch_env = env->arch_env;
2097         int i, n, n_states;
2098         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
2099
2100         /* Collect caller save registers */
2101         n = arch_env_get_n_reg_class(arch_env);
2102         for (i = 0; i < n; ++i) {
2103                 unsigned j;
2104                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
2105                 for (j = 0; j < cls->n_regs; ++j) {
2106                         const arch_register_t *reg = arch_register_for_index(cls, j);
2107                         if (arch_register_type_is(reg, state)) {
2108                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
2109                         }
2110                 }
2111         }
2112
2113         n = ARR_LEN(env->calls);
2114         n_states = ARR_LEN(stateregs);
2115         for (i = 0; i < n; ++i) {
2116                 int s, arity;
2117                 ir_node *call = env->calls[i];
2118
2119                 arity = get_irn_arity(call);
2120
2121                 /* the state reg inputs are the last n inputs of the calls */
2122                 for (s = 0; s < n_states; ++s) {
2123                         int inp = arity - n_states + s;
2124                         const arch_register_t *reg = stateregs[s];
2125                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
2126
2127                         set_irn_n(call, inp, regnode);
2128                 }
2129         }
2130
2131         DEL_ARR_F(stateregs);
2132 }
2133
2134 /**
2135  * Create a trampoline entity for the given method.
2136  */
2137 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
2138 {
2139         ir_type   *type   = get_entity_type(method);
2140         ident     *old_id = get_entity_ld_ident(method);
2141         ident     *id     = id_mangle3("L", old_id, "$stub");
2142         ir_type   *parent = be->pic_trampolines_type;
2143         ir_entity *ent    = new_entity(parent, old_id, type);
2144         set_entity_ld_ident(ent, id);
2145         set_entity_visibility(ent, visibility_local);
2146         set_entity_variability(ent, variability_uninitialized);
2147
2148         return ent;
2149 }
2150
2151 /**
2152  * Returns the trampoline entity for the given method.
2153  */
2154 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
2155 {
2156         ir_entity *result = pmap_get(env->ent_trampoline_map, method);
2157         if (result == NULL) {
2158                 result = create_trampoline(env, method);
2159                 pmap_insert(env->ent_trampoline_map, method, result);
2160         }
2161
2162         return result;
2163 }
2164
2165 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
2166 {
2167         ident     *old_id = get_entity_ld_ident(entity);
2168         ident     *id     = id_mangle3("L", old_id, "$non_lazy_ptr");
2169         ir_type   *e_type = get_entity_type(entity);
2170         ir_type   *type   = new_type_pointer(id, e_type, mode_P_data);
2171         ir_type   *parent = be->pic_symbols_type;
2172         ir_entity *ent    = new_entity(parent, old_id, type);
2173         set_entity_ld_ident(ent, id);
2174         set_entity_visibility(ent, visibility_local);
2175         set_entity_variability(ent, variability_uninitialized);
2176
2177         return ent;
2178 }
2179
2180 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
2181 {
2182         ir_entity *result = pmap_get(env->ent_pic_symbol_map, entity);
2183         if (result == NULL) {
2184                 result = create_pic_symbol(env, entity);
2185                 pmap_insert(env->ent_pic_symbol_map, entity, result);
2186         }
2187
2188         return result;
2189 }
2190
2191
2192
2193 /**
2194  * Returns non-zero if a given entity can be accessed using a relative address.
2195  */
2196 static int can_address_relative(ir_entity *entity)
2197 {
2198         return get_entity_variability(entity) == variability_initialized
2199                 || get_entity_visibility(entity) == visibility_local;
2200 }
2201
2202 /** patches SymConsts to work in position independent code */
2203 static void fix_pic_symconsts(ir_node *node, void *data)
2204 {
2205         ir_graph     *irg;
2206         ir_node      *pic_base;
2207         ir_node      *add;
2208         ir_node      *block;
2209         ir_node      *unknown;
2210         ir_mode      *mode;
2211         ir_node      *load;
2212         ir_node      *load_res;
2213         be_abi_irg_t *env = data;
2214         int           arity, i;
2215         be_main_env_t *be = env->birg->main_env;
2216
2217         arity = get_irn_arity(node);
2218         for (i = 0; i < arity; ++i) {
2219                 dbg_info  *dbgi;
2220                 ir_node   *pred = get_irn_n(node, i);
2221                 ir_entity *entity;
2222                 ir_entity *pic_symbol;
2223                 ir_node   *pic_symconst;
2224
2225                 if (!is_SymConst(pred))
2226                         continue;
2227
2228                 entity = get_SymConst_entity(pred);
2229                 block  = get_nodes_block(pred);
2230                 irg    = get_irn_irg(pred);
2231
2232                 /* calls can jump to relative addresses, so we can directly jump to
2233                    the (relatively) known call address or the trampoline */
2234                 if (i == 1 && is_Call(node)) {
2235                         ir_entity *trampoline;
2236                         ir_node   *trampoline_const;
2237
2238                         if (can_address_relative(entity))
2239                                 continue;
2240
2241                         dbgi             = get_irn_dbg_info(pred);
2242                         trampoline       = get_trampoline(be, entity);
2243                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2244                                                                     trampoline, NULL);
2245                         set_irn_n(node, i, trampoline_const);
2246                         continue;
2247                 }
2248
2249                 /* everything else is accessed relative to EIP */
2250                 mode     = get_irn_mode(pred);
2251                 unknown  = new_r_Unknown(irg, mode);
2252                 pic_base = arch_code_generator_get_pic_base(env->birg->cg);
2253
2254                 /* all ok now for locally constructed stuff */
2255                 if (can_address_relative(entity)) {
2256                         ir_node *add = new_r_Add(irg, block, pic_base, pred, mode);
2257
2258                         /* make sure the walker doesn't visit this add again */
2259                         mark_irn_visited(add);
2260                         set_irn_n(node, i, add);
2261                         continue;
2262                 }
2263
2264                 /* get entry from pic symbol segment */
2265                 dbgi         = get_irn_dbg_info(pred);
2266                 pic_symbol   = get_pic_symbol(be, entity);
2267                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2268                                                         pic_symbol, NULL);
2269                 add = new_r_Add(irg, block, pic_base, pic_symconst, mode);
2270                 mark_irn_visited(add);
2271
2272                 /* we need an extra indirection for global data outside our current
2273                    module. The loads are always safe and can therefore float
2274                    and need no memory input */
2275                 load     = new_r_Load(irg, block, new_NoMem(), add, mode, cons_floats);
2276                 load_res = new_r_Proj(irg, block, load, mode, pn_Load_res);
2277
2278                 set_irn_n(node, i, load_res);
2279         }
2280 }
2281
2282 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
2283 {
2284         be_abi_irg_t *env  = XMALLOC(be_abi_irg_t);
2285         ir_node *old_frame = get_irg_frame(birg->irg);
2286         ir_graph *irg      = birg->irg;
2287
2288         pmap_entry *ent;
2289         ir_node *dummy;
2290         optimization_state_t state;
2291         unsigned *limited_bitset;
2292
2293         be_omit_fp      = birg->main_env->options->omit_fp;
2294         be_omit_leaf_fp = birg->main_env->options->omit_leaf_fp;
2295
2296         obstack_init(&env->obst);
2297
2298         env->arch_env    = birg->main_env->arch_env;
2299         env->method_type = get_entity_type(get_irg_entity(irg));
2300         env->call        = be_abi_call_new(env->arch_env->sp->reg_class);
2301         arch_env_get_call_abi(env->arch_env, env->method_type, env->call);
2302
2303         env->ignore_regs  = pset_new_ptr_default();
2304         env->keep_map     = pmap_create();
2305         env->dce_survivor = new_survive_dce();
2306         env->birg         = birg;
2307
2308         env->sp_req.type    = arch_register_req_type_limited;
2309         env->sp_req.cls     = arch_register_get_class(env->arch_env->sp);
2310         limited_bitset      = rbitset_obstack_alloc(&env->obst, env->sp_req.cls->n_regs);
2311         rbitset_set(limited_bitset, arch_register_get_index(env->arch_env->sp));
2312         env->sp_req.limited = limited_bitset;
2313         if (env->arch_env->sp->type & arch_register_type_ignore) {
2314                 env->sp_req.type |= arch_register_req_type_ignore;
2315         }
2316
2317         env->sp_cls_req.type  = arch_register_req_type_normal;
2318         env->sp_cls_req.cls   = arch_register_get_class(env->arch_env->sp);
2319
2320         /* Beware: later we replace this node by the real one, ensure it is not CSE'd
2321            to another Unknown or the stack pointer gets used */
2322         save_optimization_state(&state);
2323         set_optimize(0);
2324         env->init_sp = dummy  = new_r_Unknown(irg, env->arch_env->sp->reg_class->mode);
2325         restore_optimization_state(&state);
2326
2327         FIRM_DBG_REGISTER(env->dbg, "firm.be.abi");
2328
2329         env->calls = NEW_ARR_F(ir_node*, 0);
2330
2331         if (birg->main_env->options->pic) {
2332                 irg_walk_graph(irg, fix_pic_symconsts, NULL, env);
2333         }
2334
2335         /* Lower all call nodes in the IRG. */
2336         process_calls(env);
2337
2338         /*
2339                 Beware: init backend abi call object after processing calls,
2340                 otherwise some information might be not yet available.
2341         */
2342         env->cb = env->call->cb->init(env->call, birg->main_env->arch_env, irg);
2343
2344         /* Process the IRG */
2345         modify_irg(env);
2346
2347         /* fix call inputs for state registers */
2348         fix_call_state_inputs(env);
2349
2350         /* We don't need the keep map anymore. */
2351         pmap_destroy(env->keep_map);
2352         env->keep_map = NULL;
2353
2354         /* calls array is not needed anymore */
2355         DEL_ARR_F(env->calls);
2356         env->calls = NULL;
2357
2358         /* reroute the stack origin of the calls to the true stack origin. */
2359         exchange(dummy, env->init_sp);
2360         exchange(old_frame, get_irg_frame(irg));
2361
2362         /* Make some important node pointers survive the dead node elimination. */
2363         survive_dce_register_irn(env->dce_survivor, &env->init_sp);
2364         foreach_pmap(env->regs, ent) {
2365                 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
2366         }
2367
2368         env->call->cb->done(env->cb);
2369         env->cb = NULL;
2370         return env;
2371 }
2372
2373 void be_abi_free(be_abi_irg_t *env)
2374 {
2375         be_abi_call_free(env->call);
2376         free_survive_dce(env->dce_survivor);
2377         del_pset(env->ignore_regs);
2378         pmap_destroy(env->regs);
2379         obstack_free(&env->obst, NULL);
2380         free(env);
2381 }
2382
2383 void be_abi_put_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, bitset_t *bs)
2384 {
2385         arch_register_t *reg;
2386
2387         for (reg = pset_first(abi->ignore_regs); reg; reg = pset_next(abi->ignore_regs))
2388                 if (reg->reg_class == cls)
2389                         bitset_set(bs, reg->index);
2390 }
2391
2392 void be_abi_set_non_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, unsigned *raw_bitset)
2393 {
2394         unsigned         i;
2395         arch_register_t *reg;
2396
2397         for (i = 0; i < cls->n_regs; ++i) {
2398                 if (arch_register_type_is(&cls->regs[i], ignore))
2399                         continue;
2400
2401                 rbitset_set(raw_bitset, i);
2402         }
2403
2404         for (reg = pset_first(abi->ignore_regs); reg != NULL;
2405              reg = pset_next(abi->ignore_regs)) {
2406                 if (reg->reg_class != cls)
2407                         continue;
2408
2409                 rbitset_clear(raw_bitset, reg->index);
2410         }
2411 }
2412
2413 /* Returns the stack layout from a abi environment. */
2414 const be_stack_layout_t *be_abi_get_stack_layout(const be_abi_irg_t *abi)
2415 {
2416         return &abi->frame;
2417 }
2418
2419 /*
2420
2421   _____ _        ____  _             _
2422  |  ___(_)_  __ / ___|| |_ __ _  ___| | __
2423  | |_  | \ \/ / \___ \| __/ _` |/ __| |/ /
2424  |  _| | |>  <   ___) | || (_| | (__|   <
2425  |_|   |_/_/\_\ |____/ \__\__,_|\___|_|\_\
2426
2427 */
2428
2429 typedef ir_node **node_array;
2430
2431 typedef struct fix_stack_walker_env_t {
2432         node_array sp_nodes;
2433 } fix_stack_walker_env_t;
2434
2435 /**
2436  * Walker. Collect all stack modifying nodes.
2437  */
2438 static void collect_stack_nodes_walker(ir_node *node, void *data)
2439 {
2440         fix_stack_walker_env_t    *env = data;
2441         const arch_register_req_t *req;
2442
2443         if (get_irn_mode(node) == mode_T)
2444                 return;
2445
2446         req = arch_get_register_req_out(node);
2447         if (! (req->type & arch_register_req_type_produces_sp))
2448                 return;
2449
2450         ARR_APP1(ir_node*, env->sp_nodes, node);
2451 }
2452
2453 void be_abi_fix_stack_nodes(be_abi_irg_t *env)
2454 {
2455         be_ssa_construction_env_t senv;
2456         int i, len;
2457         ir_node **phis;
2458         be_irg_t *birg = env->birg;
2459         be_lv_t *lv = be_get_birg_liveness(birg);
2460         fix_stack_walker_env_t walker_env;
2461
2462         walker_env.sp_nodes = NEW_ARR_F(ir_node*, 0);
2463
2464         irg_walk_graph(birg->irg, collect_stack_nodes_walker, NULL, &walker_env);
2465
2466         /* nothing to be done if we didn't find any node, in fact we mustn't
2467          * continue, as for endless loops incsp might have had no users and is bad
2468          * now.
2469          */
2470         len = ARR_LEN(walker_env.sp_nodes);
2471         if (len == 0) {
2472                 DEL_ARR_F(walker_env.sp_nodes);
2473                 return;
2474         }
2475
2476         be_ssa_construction_init(&senv, birg);
2477         be_ssa_construction_add_copies(&senv, walker_env.sp_nodes,
2478                                    ARR_LEN(walker_env.sp_nodes));
2479         be_ssa_construction_fix_users_array(&senv, walker_env.sp_nodes,
2480                                             ARR_LEN(walker_env.sp_nodes));
2481
2482         if (lv != NULL) {
2483                 len = ARR_LEN(walker_env.sp_nodes);
2484                 for (i = 0; i < len; ++i) {
2485                         be_liveness_update(lv, walker_env.sp_nodes[i]);
2486                 }
2487                 be_ssa_construction_update_liveness_phis(&senv, lv);
2488         }
2489
2490         phis = be_ssa_construction_get_new_phis(&senv);
2491
2492         /* set register requirements for stack phis */
2493         len = ARR_LEN(phis);
2494         for (i = 0; i < len; ++i) {
2495                 ir_node *phi = phis[i];
2496                 be_set_phi_reg_req(phi, &env->sp_req, arch_register_req_type_produces_sp);
2497                 arch_set_irn_register(phi, env->arch_env->sp);
2498         }
2499         be_ssa_construction_destroy(&senv);
2500
2501         DEL_ARR_F(walker_env.sp_nodes);
2502 }
2503
2504 /**
2505  * Fix all stack accessing operations in the block bl.
2506  *
2507  * @param env        the abi environment
2508  * @param bl         the block to process
2509  * @param real_bias  the bias value
2510  *
2511  * @return the bias at the end of this block
2512  */
2513 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int real_bias)
2514 {
2515         int               omit_fp  = env->call->flags.bits.try_omit_fp;
2516         ir_node          *irn;
2517         int               wanted_bias = real_bias;
2518
2519         sched_foreach(bl, irn) {
2520                 int ofs;
2521
2522                 /*
2523                    Check, if the node relates to an entity on the stack frame.
2524                    If so, set the true offset (including the bias) for that
2525                    node.
2526                  */
2527                 ir_entity *ent = arch_get_frame_entity(irn);
2528                 if (ent != NULL) {
2529                         int bias   = omit_fp ? real_bias : 0;
2530                         int offset = get_stack_entity_offset(&env->frame, ent, bias);
2531                         arch_set_frame_offset(irn, offset);
2532                         DBG((env->dbg, LEVEL_2, "%F has offset %d (including bias %d)\n",
2533                              ent, offset, bias));
2534                 }
2535
2536                 /*
2537                  * If the node modifies the stack pointer by a constant offset,
2538                  * record that in the bias.
2539                  */
2540                 ofs = arch_get_sp_bias(irn);
2541
2542                 if (be_is_IncSP(irn)) {
2543                         /* fill in real stack frame size */
2544                         if (ofs == BE_STACK_FRAME_SIZE_EXPAND) {
2545                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2546                                 ofs = (int) get_type_size_bytes(frame_type);
2547                                 be_set_IncSP_offset(irn, ofs);
2548                         } else if (ofs == BE_STACK_FRAME_SIZE_SHRINK) {
2549                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2550                                 ofs = - (int)get_type_size_bytes(frame_type);
2551                                 be_set_IncSP_offset(irn, ofs);
2552                         } else {
2553                                 if (be_get_IncSP_align(irn)) {
2554                                         /* patch IncSP to produce an aligned stack pointer */
2555                                         ir_type *between_type = env->frame.between_type;
2556                                         int      between_size = get_type_size_bytes(between_type);
2557                                         int      alignment    = 1 << env->arch_env->stack_alignment;
2558                                         int      delta        = (real_bias + ofs + between_size) & (alignment - 1);
2559                                         assert(ofs >= 0);
2560                                         if (delta > 0) {
2561                                                 be_set_IncSP_offset(irn, ofs + alignment - delta);
2562                                                 real_bias += alignment - delta;
2563                                         }
2564                                 } else {
2565                                         /* adjust so real_bias corresponds with wanted_bias */
2566                                         int delta = wanted_bias - real_bias;
2567                                         assert(delta <= 0);
2568                                         if (delta != 0) {
2569                                                 be_set_IncSP_offset(irn, ofs + delta);
2570                                                 real_bias += delta;
2571                                         }
2572                                 }
2573                         }
2574                 }
2575
2576                 real_bias   += ofs;
2577                 wanted_bias += ofs;
2578         }
2579
2580         assert(real_bias == wanted_bias);
2581         return real_bias;
2582 }
2583
2584 /**
2585  * A helper struct for the bias walker.
2586  */
2587 struct bias_walk {
2588         be_abi_irg_t *env;     /**< The ABI irg environment. */
2589         int           start_block_bias;  /**< The bias at the end of the start block. */
2590         int           between_size;
2591         ir_node      *start_block;  /**< The start block of the current graph. */
2592 };
2593
2594 /**
2595  * Block-Walker: fix all stack offsets for all blocks
2596  * except the start block
2597  */
2598 static void stack_bias_walker(ir_node *bl, void *data)
2599 {
2600         struct bias_walk *bw = data;
2601         if (bl != bw->start_block) {
2602                 process_stack_bias(bw->env, bl, bw->start_block_bias);
2603         }
2604 }
2605
2606 /**
2607  * Walker: finally lower all Sels of outer frame or parameter
2608  * entities.
2609  */
2610 static void lower_outer_frame_sels(ir_node *sel, void *ctx) {
2611         be_abi_irg_t *env = ctx;
2612         ir_node      *ptr;
2613         ir_entity    *ent;
2614         ir_type      *owner;
2615
2616         if (! is_Sel(sel))
2617                 return;
2618
2619         ent   = get_Sel_entity(sel);
2620         owner = get_entity_owner(ent);
2621         ptr   = get_Sel_ptr(sel);
2622
2623         if (owner == env->frame.frame_type || owner == env->frame.arg_type) {
2624                 /* found access to outer frame or arguments */
2625                 int offset = get_stack_entity_offset(&env->frame, ent, 0);
2626
2627                 if (offset != 0) {
2628                         ir_node  *bl   = get_nodes_block(sel);
2629                         dbg_info *dbgi = get_irn_dbg_info(sel);
2630                         ir_mode  *mode = get_irn_mode(sel);
2631                         ir_mode  *mode_UInt = get_reference_mode_unsigned_eq(mode);
2632                         ir_node  *cnst = new_r_Const_long(current_ir_graph, mode_UInt, offset);
2633
2634                         ptr = new_rd_Add(dbgi, current_ir_graph, bl, ptr, cnst, mode);
2635                 }
2636                 exchange(sel, ptr);
2637         }
2638 }
2639
2640 void be_abi_fix_stack_bias(be_abi_irg_t *env)
2641 {
2642         ir_graph          *irg = env->birg->irg;
2643         ir_type           *frame_tp;
2644         int               i;
2645         struct bias_walk  bw;
2646
2647         stack_frame_compute_initial_offset(&env->frame);
2648         // stack_layout_dump(stdout, frame);
2649
2650         /* Determine the stack bias at the end of the start block. */
2651         bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), env->frame.initial_bias);
2652         bw.between_size     = get_type_size_bytes(env->frame.between_type);
2653
2654         /* fix the bias is all other blocks */
2655         bw.env = env;
2656         bw.start_block = get_irg_start_block(irg);
2657         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
2658
2659         /* fix now inner functions: these still have Sel node to outer
2660            frame and parameter entities */
2661         frame_tp = get_irg_frame_type(irg);
2662         for (i = get_class_n_members(frame_tp) - 1; i >= 0; --i) {
2663                 ir_entity *ent = get_class_member(frame_tp, i);
2664
2665                 if (is_method_entity(ent) && get_entity_peculiarity(ent) != peculiarity_description) {
2666                         ir_graph *irg = get_entity_irg(ent);
2667
2668                         irg_walk_graph(irg, NULL, lower_outer_frame_sels, env);
2669                 }
2670         }
2671 }
2672
2673 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2674 {
2675         assert(arch_register_type_is(reg, callee_save));
2676         assert(pmap_contains(abi->regs, (void *) reg));
2677         return pmap_get(abi->regs, (void *) reg);
2678 }
2679
2680 ir_node *be_abi_get_ignore_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2681 {
2682         assert(arch_register_type_is(reg, ignore));
2683         assert(pmap_contains(abi->regs, (void *) reg));
2684         return pmap_get(abi->regs, (void *) reg);
2685 }
2686
2687 /**
2688  * Returns non-zero if the ABI has omitted the frame pointer in
2689  * the current graph.
2690  */
2691 int be_abi_omit_fp(const be_abi_irg_t *abi)
2692 {
2693         return abi->call->flags.bits.try_omit_fp;
2694 }