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         /* The nodes have no depth order, but we need a total order because qsort()
1114          * is not stable. */
1115         return get_irn_idx(n1) - get_irn_idx(n2);
1116 }
1117
1118 /**
1119  * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
1120  * Clears the irg_is_leaf flag if a Call is detected.
1121  */
1122 static void link_ops_in_block_walker(ir_node *irn, void *data)
1123 {
1124         ir_opcode code = get_irn_opcode(irn);
1125
1126         if (code == iro_Call ||
1127            (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
1128            (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
1129                 be_abi_irg_t *env = data;
1130                 ir_node *bl       = get_nodes_block(irn);
1131                 void *save        = get_irn_link(bl);
1132
1133                 if (code == iro_Call)
1134                         env->call->flags.bits.irg_is_leaf = 0;
1135
1136                 set_irn_link(irn, save);
1137                 set_irn_link(bl, irn);
1138         }
1139 }
1140
1141 /**
1142  * Block-walker:
1143  * Process all Call/Alloc/Free nodes inside a basic block.
1144  * Note that the link field of the block must contain a linked list of all
1145  * Call nodes inside the Block. We first order this list according to data dependency
1146  * and that connect the calls together.
1147  */
1148 static void process_ops_in_block(ir_node *bl, void *data)
1149 {
1150         be_abi_irg_t *env = data;
1151         ir_node *curr_sp  = env->init_sp;
1152         ir_node *irn;
1153         int n;
1154
1155         for (irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
1156                 obstack_ptr_grow(&env->obst, irn);
1157
1158         /* If there were call nodes in the block. */
1159         if (n > 0) {
1160                 ir_node *keep;
1161                 ir_node **nodes;
1162                 int i;
1163
1164                 nodes = obstack_finish(&env->obst);
1165
1166                 /* order the call nodes according to data dependency */
1167                 qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependency);
1168
1169                 for (i = n - 1; i >= 0; --i) {
1170                         ir_node *irn = nodes[i];
1171
1172                         DBG((env->dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1173                         switch (get_irn_opcode(irn)) {
1174                         case iro_Call:
1175                                 if (! be_omit_fp) {
1176                                         /* The stack pointer will be modified due to a call. */
1177                                         env->call->flags.bits.try_omit_fp = 0;
1178                                 }
1179                                 curr_sp = adjust_call(env, irn, curr_sp);
1180                                 break;
1181                         case iro_Alloc:
1182                                 if (get_Alloc_where(irn) == stack_alloc)
1183                                         curr_sp = adjust_alloc(env, irn, curr_sp);
1184                                 break;
1185                         case iro_Free:
1186                                 if (get_Free_where(irn) == stack_alloc)
1187                                         curr_sp = adjust_free(env, irn, curr_sp);
1188                                 break;
1189                         default:
1190                                 panic("invalid call");
1191                                 break;
1192                         }
1193                 }
1194
1195                 obstack_free(&env->obst, nodes);
1196
1197                 /* Keep the last stack state in the block by tying it to Keep node,
1198                  * the proj from calls is already kept */
1199                 if (curr_sp != env->init_sp &&
1200                     !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1201                         nodes[0] = curr_sp;
1202                         keep     = be_new_Keep(env->arch_env->sp->reg_class,
1203                                                get_irn_irg(bl), bl, 1, nodes);
1204                         pmap_insert(env->keep_map, bl, keep);
1205                 }
1206         }
1207
1208         set_irn_link(bl, curr_sp);
1209 }  /* process_ops_in_block */
1210
1211 /**
1212  * Adjust all call nodes in the graph to the ABI conventions.
1213  */
1214 static void process_calls(be_abi_irg_t *env)
1215 {
1216         ir_graph *irg = env->birg->irg;
1217
1218         env->call->flags.bits.irg_is_leaf = 1;
1219         irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, env);
1220
1221         ir_heights = heights_new(env->birg->irg);
1222         irg_block_walk_graph(irg, NULL, process_ops_in_block, env);
1223         heights_free(ir_heights);
1224 }
1225
1226 /**
1227  * Computes the stack argument layout type.
1228  * Changes a possibly allocated value param type by moving
1229  * entities to the stack layout type.
1230  *
1231  * @param env           the ABI environment
1232  * @param call          the current call ABI
1233  * @param method_type   the method type
1234  * @param val_param_tp  the value parameter type, will be destroyed
1235  * @param param_map     an array mapping method arguments to the stack layout type
1236  *
1237  * @return the stack argument layout type
1238  */
1239 static ir_type *compute_arg_type(be_abi_irg_t *env, be_abi_call_t *call,
1240                                                                  ir_type *method_type, ir_type *val_param_tp,
1241                                                                  ir_entity ***param_map)
1242 {
1243         int dir  = env->call->flags.bits.left_to_right ? 1 : -1;
1244         int inc  = env->birg->main_env->arch_env->stack_dir * dir;
1245         int n    = get_method_n_params(method_type);
1246         int curr = inc > 0 ? 0 : n - 1;
1247         int ofs  = 0;
1248
1249         char buf[128];
1250         ir_type *res;
1251         int i;
1252         ident *id = get_entity_ident(get_irg_entity(env->birg->irg));
1253         ir_entity **map;
1254
1255         *param_map = map = obstack_alloc(&env->obst, n * sizeof(ir_entity *));
1256         res = new_type_struct(id_mangle_u(id, new_id_from_chars("arg_type", 8)));
1257         for (i = 0; i < n; ++i, curr += inc) {
1258                 ir_type *param_type    = get_method_param_type(method_type, curr);
1259                 be_abi_call_arg_t *arg = get_call_arg(call, 0, curr);
1260
1261                 map[i] = NULL;
1262                 if (arg->on_stack) {
1263                         if (val_param_tp != NULL) {
1264                                 /* the entity was already created, create a copy in the param type */
1265                                 ir_entity *val_ent = get_method_value_param_ent(method_type, i);
1266                                 arg->stack_ent = copy_entity_own(val_ent, res);
1267                                 set_entity_link(val_ent, arg->stack_ent);
1268                                 set_entity_link(arg->stack_ent, NULL);
1269                                 /* must be automatic to set a fixed layout */
1270                                 set_entity_allocation(arg->stack_ent, allocation_automatic);
1271                         } else {
1272                                 /* create a new entity */
1273                                 snprintf(buf, sizeof(buf), "param_%d", i);
1274                                 arg->stack_ent = new_entity(res, new_id_from_str(buf), param_type);
1275                         }
1276                         ofs += arg->space_before;
1277                         ofs = round_up2(ofs, arg->alignment);
1278                         set_entity_offset(arg->stack_ent, ofs);
1279                         ofs += arg->space_after;
1280                         ofs += get_type_size_bytes(param_type);
1281                         map[i] = arg->stack_ent;
1282                 }
1283         }
1284         set_type_size_bytes(res, ofs);
1285         set_type_state(res, layout_fixed);
1286         return res;
1287 }
1288
1289 typedef struct {
1290         const arch_register_t *reg;
1291         ir_node *irn;
1292 } reg_node_map_t;
1293
1294 static int cmp_regs(const void *a, const void *b)
1295 {
1296         const reg_node_map_t *p = a;
1297         const reg_node_map_t *q = b;
1298
1299         if (p->reg->reg_class == q->reg->reg_class)
1300                 return p->reg->index - q->reg->index;
1301         else
1302                 return p->reg->reg_class - q->reg->reg_class;
1303 }
1304
1305 static reg_node_map_t *reg_map_to_arr(struct obstack *obst, pmap *reg_map)
1306 {
1307         pmap_entry *ent;
1308         int n = pmap_count(reg_map);
1309         int i = 0;
1310         reg_node_map_t *res = obstack_alloc(obst, n * sizeof(res[0]));
1311
1312         foreach_pmap(reg_map, ent) {
1313                 res[i].reg = ent->key;
1314                 res[i].irn = ent->value;
1315                 i++;
1316         }
1317
1318         qsort(res, n, sizeof(res[0]), cmp_regs);
1319         return res;
1320 }
1321
1322 /**
1323  * Creates a barrier.
1324  */
1325 static ir_node *create_barrier(be_abi_irg_t *env, ir_node *bl, ir_node **mem, pmap *regs, int in_req)
1326 {
1327         ir_graph *irg = env->birg->irg;
1328         int n_regs    = pmap_count(regs);
1329         int n;
1330         ir_node *irn;
1331         ir_node **in;
1332         reg_node_map_t *rm;
1333
1334         rm = reg_map_to_arr(&env->obst, regs);
1335
1336         for (n = 0; n < n_regs; ++n)
1337                 obstack_ptr_grow(&env->obst, rm[n].irn);
1338
1339         if (mem) {
1340                 obstack_ptr_grow(&env->obst, *mem);
1341                 n++;
1342         }
1343
1344         in = (ir_node **) obstack_finish(&env->obst);
1345         irn = be_new_Barrier(irg, bl, n, in);
1346         obstack_free(&env->obst, in);
1347
1348         for (n = 0; n < n_regs; ++n) {
1349                 ir_node                   *pred     = rm[n].irn;
1350                 const arch_register_t     *reg      = rm[n].reg;
1351                 arch_register_type_t       add_type = 0;
1352                 ir_node                   *proj;
1353
1354                 /* stupid workaround for now... as not all nodes report register
1355                  * requirements. */
1356                 if (!is_Phi(pred)) {
1357                         const arch_register_req_t *ireq = arch_get_register_req_out(pred);
1358                         if (ireq->type & arch_register_req_type_ignore)
1359                                 add_type |= arch_register_req_type_ignore;
1360                         if (ireq->type & arch_register_req_type_produces_sp)
1361                                 add_type |= arch_register_req_type_produces_sp;
1362                 }
1363
1364                 proj = new_r_Proj(irg, bl, irn, get_irn_mode(pred), n);
1365                 be_node_set_reg_class_in(irn, n, reg->reg_class);
1366                 if (in_req)
1367                         be_set_constr_single_reg_in(irn, n, reg, 0);
1368                 be_set_constr_single_reg_out(irn, n, reg, add_type);
1369                 arch_set_irn_register(proj, reg);
1370
1371                 pmap_insert(regs, (void *) reg, proj);
1372         }
1373
1374         if (mem) {
1375                 *mem = new_r_Proj(irg, bl, irn, mode_M, n);
1376         }
1377
1378         obstack_free(&env->obst, rm);
1379         return irn;
1380 }
1381
1382 /**
1383  * Creates a be_Return for a Return node.
1384  *
1385  * @param @env    the abi environment
1386  * @param irn     the Return node or NULL if there was none
1387  * @param bl      the block where the be_Retun should be placed
1388  * @param mem     the current memory
1389  * @param n_res   number of return results
1390  */
1391 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1392                 ir_node *mem, int n_res)
1393 {
1394         be_abi_call_t    *call     = env->call;
1395         const arch_env_t *arch_env = env->birg->main_env->arch_env;
1396         dbg_info *dbgi;
1397         pmap *reg_map  = pmap_create();
1398         ir_node *keep  = pmap_get(env->keep_map, bl);
1399         int in_max;
1400         ir_node *ret;
1401         int i, n;
1402         unsigned pop;
1403         ir_node **in;
1404         ir_node *stack;
1405         const arch_register_t **regs;
1406         pmap_entry *ent ;
1407
1408         /*
1409                 get the valid stack node in this block.
1410                 If we had a call in that block there is a Keep constructed by process_calls()
1411                 which points to the last stack modification in that block. we'll use
1412                 it then. Else we use the stack from the start block and let
1413                 the ssa construction fix the usage.
1414         */
1415         stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1416         if (keep) {
1417                 stack = get_irn_n(keep, 0);
1418                 kill_node(keep);
1419                 remove_End_keepalive(get_irg_end(env->birg->irg), keep);
1420         }
1421
1422         /* Insert results for Return into the register map. */
1423         for (i = 0; i < n_res; ++i) {
1424                 ir_node *res           = get_Return_res(irn, i);
1425                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1426                 assert(arg->in_reg && "return value must be passed in register");
1427                 pmap_insert(reg_map, (void *) arg->reg, res);
1428         }
1429
1430         /* Add uses of the callee save registers. */
1431         foreach_pmap(env->regs, ent) {
1432                 const arch_register_t *reg = ent->key;
1433                 if (arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1434                         pmap_insert(reg_map, ent->key, ent->value);
1435         }
1436
1437         be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1438
1439         /* Make the Epilogue node and call the arch's epilogue maker. */
1440         create_barrier(env, bl, &mem, reg_map, 1);
1441         call->cb->epilogue(env->cb, bl, &mem, reg_map);
1442
1443         /*
1444                 Maximum size of the in array for Return nodes is
1445                 return args + callee save/ignore registers + memory + stack pointer
1446         */
1447         in_max = pmap_count(reg_map) + n_res + 2;
1448
1449         in   = obstack_alloc(&env->obst, in_max * sizeof(in[0]));
1450         regs = obstack_alloc(&env->obst, in_max * sizeof(regs[0]));
1451
1452         in[0]   = mem;
1453         in[1]   = be_abi_reg_map_get(reg_map, arch_env->sp);
1454         regs[0] = NULL;
1455         regs[1] = arch_env->sp;
1456         n       = 2;
1457
1458         /* clear SP entry, since it has already been grown. */
1459         pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1460         for (i = 0; i < n_res; ++i) {
1461                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1462
1463                 in[n]     = be_abi_reg_map_get(reg_map, arg->reg);
1464                 regs[n++] = arg->reg;
1465
1466                 /* Clear the map entry to mark the register as processed. */
1467                 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1468         }
1469
1470         /* grow the rest of the stuff. */
1471         foreach_pmap(reg_map, ent) {
1472                 if (ent->value) {
1473                         in[n]     = ent->value;
1474                         regs[n++] = ent->key;
1475                 }
1476         }
1477
1478         /* The in array for the new back end return is now ready. */
1479         if (irn != NULL) {
1480                 dbgi = get_irn_dbg_info(irn);
1481         } else {
1482                 dbgi = NULL;
1483         }
1484         /* we have to pop the shadow parameter in in case of struct returns */
1485         pop = call->pop;
1486         ret = be_new_Return(dbgi, env->birg->irg, bl, n_res, pop, n, in);
1487
1488         /* Set the register classes of the return's parameter accordingly. */
1489         for (i = 0; i < n; ++i) {
1490                 if (regs[i] == NULL)
1491                         continue;
1492
1493                 be_node_set_reg_class_in(ret, i, regs[i]->reg_class);
1494         }
1495
1496         /* Free the space of the Epilog's in array and the register <-> proj map. */
1497         obstack_free(&env->obst, in);
1498         pmap_destroy(reg_map);
1499
1500         return ret;
1501 }
1502
1503 typedef struct ent_pos_pair ent_pos_pair;
1504 struct ent_pos_pair {
1505         ir_entity    *ent;   /**< a value param entity */
1506         int          pos;    /**< its parameter number */
1507         ent_pos_pair *next;  /**< for linking */
1508 };
1509
1510 typedef struct lower_frame_sels_env_t {
1511         ent_pos_pair *value_param_list;          /**< the list of all value param entities */
1512         ir_node      *frame;                     /**< the current frame */
1513         const arch_register_class_t *sp_class;   /**< register class of the stack pointer */
1514         const arch_register_class_t *link_class; /**< register class of the link pointer */
1515         ir_type      *value_tp;                  /**< the value type if any */
1516         ir_type      *frame_tp;                  /**< the frame type */
1517         int          static_link_pos;            /**< argument number of the hidden static link */
1518 } lower_frame_sels_env_t;
1519
1520 /**
1521  * Return an entity from the backend for an value param entity.
1522  *
1523  * @param ent  an value param type entity
1524  * @param ctx  context
1525  */
1526 static ir_entity *get_argument_entity(ir_entity *ent, lower_frame_sels_env_t *ctx)
1527 {
1528         ir_entity *argument_ent = get_entity_link(ent);
1529
1530         if (argument_ent == NULL) {
1531                 /* we have NO argument entity yet: This is bad, as we will
1532                 * need one for backing store.
1533                 * Create one here.
1534                 */
1535                 ir_type *frame_tp = ctx->frame_tp;
1536                 unsigned offset   = get_type_size_bytes(frame_tp);
1537                 ir_type  *tp      = get_entity_type(ent);
1538                 unsigned align    = get_type_alignment_bytes(tp);
1539
1540                 offset += align - 1;
1541                 offset &= ~(align - 1);
1542
1543                 argument_ent = copy_entity_own(ent, frame_tp);
1544
1545                 /* must be automatic to set a fixed layout */
1546                 set_entity_allocation(argument_ent, allocation_automatic);
1547                 set_entity_offset(argument_ent, offset);
1548                 offset += get_type_size_bytes(tp);
1549
1550                 set_type_size_bytes(frame_tp, offset);
1551                 set_entity_link(ent, argument_ent);
1552         }
1553         return argument_ent;
1554 }
1555 /**
1556  * Walker: Replaces Sels of frame type and
1557  * value param type entities by FrameAddress.
1558  * Links all used entities.
1559  */
1560 static void lower_frame_sels_walker(ir_node *irn, void *data)
1561 {
1562         lower_frame_sels_env_t *ctx = data;
1563
1564         if (is_Sel(irn)) {
1565                 ir_node *ptr = get_Sel_ptr(irn);
1566
1567                 if (ptr == ctx->frame) {
1568                         ir_entity    *ent = get_Sel_entity(irn);
1569                         ir_node      *bl  = get_nodes_block(irn);
1570                         ir_node      *nw;
1571                         int          pos = 0;
1572
1573                         if (get_entity_owner(ent) == ctx->value_tp) {
1574                                 /* replace by its copy from the argument type */
1575                                 pos = get_struct_member_index(ctx->value_tp, ent);
1576                                 ent = get_argument_entity(ent, ctx);
1577                         }
1578
1579                         nw = be_new_FrameAddr(ctx->sp_class, current_ir_graph, bl, ctx->frame, ent);
1580                         exchange(irn, nw);
1581
1582                         /* check, if it's a param sel and if have not seen this entity before */
1583                         if (get_entity_owner(ent) == ctx->value_tp && get_entity_link(ent) == NULL) {
1584                                 ent_pos_pair pair;
1585
1586                                 pair.ent  = ent;
1587                                 pair.pos  = pos;
1588                                 pair.next = NULL;
1589                                 ARR_APP1(ent_pos_pair, ctx->value_param_list, pair);
1590                                 /* just a mark */
1591                                 set_entity_link(ent, ctx->value_param_list);
1592                         }
1593                 }
1594         }
1595 }
1596
1597 /**
1598  * Check if a value parameter is transmitted as a register.
1599  * This might happen if the address of an parameter is taken which is
1600  * transmitted in registers.
1601  *
1602  * Note that on some architectures this case must be handled specially
1603  * because the place of the backing store is determined by their ABI.
1604  *
1605  * In the default case we move the entity to the frame type and create
1606  * a backing store into the first block.
1607  */
1608 static void fix_address_of_parameter_access(be_abi_irg_t *env, ent_pos_pair *value_param_list)
1609 {
1610         be_abi_call_t *call = env->call;
1611         ir_graph      *irg  = env->birg->irg;
1612         ent_pos_pair  *entry, *new_list;
1613         ir_type       *frame_tp;
1614         int           i, n = ARR_LEN(value_param_list);
1615         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1616
1617         new_list = NULL;
1618         for (i = 0; i < n; ++i) {
1619                 int               pos  = value_param_list[i].pos;
1620                 be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
1621
1622                 if (arg->in_reg) {
1623                         DBG((dbg, LEVEL_2, "\targ #%d need backing store\n", pos));
1624                         value_param_list[i].next = new_list;
1625                         new_list = &value_param_list[i];
1626                 }
1627         }
1628         if (new_list != NULL) {
1629                 /* ok, change the graph */
1630                 ir_node *start_bl = get_irg_start_block(irg);
1631                 ir_node *first_bl = NULL;
1632                 ir_node *frame, *imem, *nmem, *store, *mem, *args, *args_bl;
1633                 const ir_edge_t *edge;
1634                 optimization_state_t state;
1635                 unsigned offset;
1636
1637                 foreach_block_succ(start_bl, edge) {
1638                         ir_node *succ = get_edge_src_irn(edge);
1639                         if (start_bl != succ) {
1640                                 first_bl = succ;
1641                                 break;
1642                         }
1643                 }
1644                 assert(first_bl);
1645                 /* we had already removed critical edges, so the following
1646                    assertion should be always true. */
1647                 assert(get_Block_n_cfgpreds(first_bl) == 1);
1648
1649                 /* now create backing stores */
1650                 frame = get_irg_frame(irg);
1651                 imem = get_irg_initial_mem(irg);
1652
1653                 save_optimization_state(&state);
1654                 set_optimize(0);
1655                 nmem = new_r_Proj(irg, first_bl, get_irg_start(irg), mode_M, pn_Start_M);
1656                 restore_optimization_state(&state);
1657
1658                 /* reroute all edges to the new memory source */
1659                 edges_reroute(imem, nmem, irg);
1660
1661                 store   = NULL;
1662                 mem     = imem;
1663                 args    = get_irg_args(irg);
1664                 args_bl = get_nodes_block(args);
1665                 for (entry = new_list; entry != NULL; entry = entry->next) {
1666                         int     i     = entry->pos;
1667                         ir_type *tp   = get_entity_type(entry->ent);
1668                         ir_mode *mode = get_type_mode(tp);
1669                         ir_node *addr;
1670
1671                         /* address for the backing store */
1672                         addr = be_new_FrameAddr(env->arch_env->sp->reg_class, irg, first_bl, frame, entry->ent);
1673
1674                         if (store)
1675                                 mem = new_r_Proj(irg, first_bl, store, mode_M, pn_Store_M);
1676
1677                         /* the backing store itself */
1678                         store = new_r_Store(irg, first_bl, mem, addr,
1679                                             new_r_Proj(irg, args_bl, args, mode, i), 0);
1680                 }
1681                 /* the new memory Proj gets the last Proj from store */
1682                 set_Proj_pred(nmem, store);
1683                 set_Proj_proj(nmem, pn_Store_M);
1684
1685                 /* move all entities to the frame type */
1686                 frame_tp = get_irg_frame_type(irg);
1687                 offset   = get_type_size_bytes(frame_tp);
1688
1689                 /* we will add new entities: set the layout to undefined */
1690                 assert(get_type_state(frame_tp) == layout_fixed);
1691                 set_type_state(frame_tp, layout_undefined);
1692                 for (entry = new_list; entry != NULL; entry = entry->next) {
1693                         ir_entity *ent = entry->ent;
1694
1695                         /* If the entity is still on the argument type, move it to the frame type.
1696                            This happens if the value_param type was build due to compound
1697                            params. */
1698                         if (get_entity_owner(ent) != frame_tp) {
1699                                 ir_type  *tp   = get_entity_type(ent);
1700                                 unsigned align = get_type_alignment_bytes(tp);
1701
1702                                 offset += align - 1;
1703                                 offset &= ~(align - 1);
1704                                 set_entity_owner(ent, frame_tp);
1705                                 add_class_member(frame_tp, ent);
1706                                 /* must be automatic to set a fixed layout */
1707                                 set_entity_allocation(ent, allocation_automatic);
1708                                 set_entity_offset(ent, offset);
1709                                 offset += get_type_size_bytes(tp);
1710                         }
1711                 }
1712                 set_type_size_bytes(frame_tp, offset);
1713                 /* fix the layout again */
1714                 set_type_state(frame_tp, layout_fixed);
1715         }
1716 }
1717
1718 /**
1719  * The start block has no jump, instead it has an initial exec Proj.
1720  * The backend wants to handle all blocks the same way, so we replace
1721  * the out cfg edge with a real jump.
1722  */
1723 static void fix_start_block(ir_graph *irg)
1724 {
1725         ir_node         *initial_X   = get_irg_initial_exec(irg);
1726         ir_node         *start_block = get_irg_start_block(irg);
1727         const ir_edge_t *edge;
1728
1729         assert(is_Proj(initial_X));
1730
1731         foreach_out_edge(initial_X, edge) {
1732                 ir_node *block = get_edge_src_irn(edge);
1733
1734                 if (is_Anchor(block))
1735                         continue;
1736                 if (block != start_block) {
1737                         ir_node *jmp = new_r_Jmp(irg, start_block);
1738
1739                         set_Block_cfgpred(block, get_edge_src_pos(edge), jmp);
1740                         return;
1741                 }
1742         }
1743         panic("Initial exec has no follow block in %+F", irg);
1744 }
1745
1746 /**
1747  * Update the entity of Sels to the outer value parameters.
1748  */
1749 static void update_outer_frame_sels(ir_node *irn, void *env) {
1750         lower_frame_sels_env_t *ctx = env;
1751         ir_node                *ptr;
1752         ir_entity              *ent;
1753         int                    pos = 0;
1754
1755         if (! is_Sel(irn))
1756                 return;
1757         ptr = get_Sel_ptr(irn);
1758         if (! is_arg_Proj(ptr))
1759                 return;
1760         if (get_Proj_proj(ptr) != ctx->static_link_pos)
1761                 return;
1762         ent   = get_Sel_entity(irn);
1763
1764         if (get_entity_owner(ent) == ctx->value_tp) {
1765                 /* replace by its copy from the argument type */
1766                 pos = get_struct_member_index(ctx->value_tp, ent);
1767                 ent = get_argument_entity(ent, ctx);
1768                 set_Sel_entity(irn, ent);
1769
1770                 /* check, if we have not seen this entity before */
1771                 if (get_entity_link(ent) == NULL) {
1772                         ent_pos_pair pair;
1773
1774                         pair.ent  = ent;
1775                         pair.pos  = pos;
1776                         pair.next = NULL;
1777                         ARR_APP1(ent_pos_pair, ctx->value_param_list, pair);
1778                         /* just a mark */
1779                         set_entity_link(ent, ctx->value_param_list);
1780                 }
1781         }
1782 }
1783
1784 /**
1785  * Fix access to outer local variables.
1786  */
1787 static void fix_outer_variable_access(be_abi_irg_t *env,
1788                                       lower_frame_sels_env_t *ctx)
1789 {
1790         int      i;
1791         ir_graph *irg;
1792         (void) env;
1793
1794         for (i = get_class_n_members(ctx->frame_tp) - 1; i >= 0; --i) {
1795                 ir_entity *ent = get_class_member(ctx->frame_tp, i);
1796
1797                 if (! is_method_entity(ent))
1798                         continue;
1799                 if (get_entity_peculiarity(ent) == peculiarity_description)
1800                         continue;
1801
1802                 /*
1803                  * FIXME: find the number of the static link parameter
1804                  * for now we assume 0 here
1805                  */
1806                 ctx->static_link_pos = 0;
1807
1808                 irg = get_entity_irg(ent);
1809                 irg_walk_graph(irg, NULL, update_outer_frame_sels, ctx);
1810         }
1811 }
1812
1813 /**
1814  * Modify the irg itself and the frame type.
1815  */
1816 static void modify_irg(be_abi_irg_t *env)
1817 {
1818         be_abi_call_t *call       = env->call;
1819         const arch_env_t *arch_env= env->birg->main_env->arch_env;
1820         const arch_register_t *sp = arch_env->sp;
1821         ir_graph *irg             = env->birg->irg;
1822         ir_node *start_bl;
1823         ir_node *end;
1824         ir_node *old_mem;
1825         ir_node *new_mem_proj;
1826         ir_node *mem;
1827         ir_type *method_type      = get_entity_type(get_irg_entity(irg));
1828
1829         int n_params;
1830         int i, n;
1831         unsigned j;
1832
1833         reg_node_map_t *rm;
1834         const arch_register_t *fp_reg;
1835         ir_node *frame_pointer;
1836         ir_node *reg_params_bl;
1837         ir_node **args;
1838         ir_node *arg_tuple;
1839         const ir_edge_t *edge;
1840         ir_type *arg_type, *bet_type, *tp;
1841         lower_frame_sels_env_t ctx;
1842         ir_entity **param_map;
1843
1844         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1845
1846         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1847
1848         /* Must fetch memory here, otherwise the start Barrier gets the wrong
1849          * memory, which leads to loops in the DAG. */
1850         old_mem = get_irg_initial_mem(irg);
1851
1852         irp_reserve_resources(irp, IR_RESOURCE_ENTITY_LINK);
1853
1854         /* set the links of all frame entities to NULL, we use it
1855            to detect if an entity is already linked in the value_param_list */
1856         tp = get_method_value_param_type(method_type);
1857         ctx.value_tp = tp;
1858         if (tp != NULL) {
1859                 /* clear the links of the clone type, let the
1860                    original entities point to its clones */
1861                 for (i = get_struct_n_members(tp) - 1; i >= 0; --i) {
1862                         ir_entity *mem  = get_struct_member(tp, i);
1863                         set_entity_link(mem, NULL);
1864                 }
1865         }
1866
1867         arg_type = compute_arg_type(env, call, method_type, tp, &param_map);
1868
1869         /* Convert the Sel nodes in the irg to frame addr nodes: */
1870         ctx.value_param_list = NEW_ARR_F(ent_pos_pair, 0);
1871         ctx.frame            = get_irg_frame(irg);
1872         ctx.sp_class         = env->arch_env->sp->reg_class;
1873         ctx.link_class       = env->arch_env->link_class;
1874         ctx.frame_tp         = get_irg_frame_type(irg);
1875
1876         /* we will possible add new entities to the frame: set the layout to undefined */
1877         assert(get_type_state(ctx.frame_tp) == layout_fixed);
1878         set_type_state(ctx.frame_tp, layout_undefined);
1879
1880         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1881
1882         /* fix the frame type layout again */
1883         set_type_state(ctx.frame_tp, layout_fixed);
1884
1885         env->regs  = pmap_create();
1886
1887         n_params = get_method_n_params(method_type);
1888         args     = obstack_alloc(&env->obst, n_params * sizeof(args[0]));
1889         memset(args, 0, n_params * sizeof(args[0]));
1890
1891         /*
1892          * for inner function we must now fix access to outer frame entities.
1893          */
1894         fix_outer_variable_access(env, &ctx);
1895
1896         /* Check if a value parameter is transmitted as a register.
1897          * This might happen if the address of an parameter is taken which is
1898          * transmitted in registers.
1899          *
1900          * Note that on some architectures this case must be handled specially
1901          * because the place of the backing store is determined by their ABI.
1902          *
1903          * In the default case we move the entity to the frame type and create
1904          * a backing store into the first block.
1905          */
1906         fix_address_of_parameter_access(env, ctx.value_param_list);
1907
1908         DEL_ARR_F(ctx.value_param_list);
1909         irp_free_resources(irp, IR_RESOURCE_ENTITY_LINK);
1910
1911         /* Fill the argument vector */
1912         arg_tuple = get_irg_args(irg);
1913         foreach_out_edge(arg_tuple, edge) {
1914                 ir_node *irn = get_edge_src_irn(edge);
1915                 if (! is_Anchor(irn)) {
1916                         int nr       = get_Proj_proj(irn);
1917                         args[nr]     = irn;
1918                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1919                 }
1920         }
1921
1922         bet_type = call->cb->get_between_type(env->cb);
1923         stack_frame_init(&env->frame, arg_type, bet_type, get_irg_frame_type(irg), arch_env->stack_dir, param_map);
1924
1925         /* Count the register params and add them to the number of Projs for the RegParams node */
1926         for (i = 0; i < n_params; ++i) {
1927                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1928                 if (arg->in_reg && args[i]) {
1929                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1930                         assert(i == get_Proj_proj(args[i]));
1931
1932                         /* For now, associate the register with the old Proj from Start representing that argument. */
1933                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1934                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1935                 }
1936         }
1937
1938         /* Collect all callee-save registers */
1939         for (i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
1940                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
1941                 for (j = 0; j < cls->n_regs; ++j) {
1942                         const arch_register_t *reg = &cls->regs[j];
1943                         if (arch_register_type_is(reg, callee_save) ||
1944                                         arch_register_type_is(reg, state)) {
1945                                 pmap_insert(env->regs, (void *) reg, NULL);
1946                         }
1947                 }
1948         }
1949
1950         pmap_insert(env->regs, (void *) sp, NULL);
1951         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1952         reg_params_bl   = get_irg_start_block(irg);
1953         env->reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(env->regs));
1954         add_irn_dep(env->reg_params, get_irg_start(irg));
1955
1956         /*
1957          * make proj nodes for the callee save registers.
1958          * memorize them, since Return nodes get those as inputs.
1959          *
1960          * Note, that if a register corresponds to an argument, the regs map contains
1961          * the old Proj from start for that argument.
1962          */
1963
1964         rm = reg_map_to_arr(&env->obst, env->regs);
1965         for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1966                 arch_register_t          *reg      = (void *) rm[i].reg;
1967                 ir_mode                  *mode     = reg->reg_class->mode;
1968                 long                      nr       = i;
1969                 arch_register_req_type_t  add_type = 0;
1970                 ir_node                  *proj;
1971
1972                 if (reg == sp)
1973                         add_type |= arch_register_req_type_produces_sp | arch_register_req_type_ignore;
1974
1975                 assert(nr >= 0);
1976                 proj = new_r_Proj(irg, reg_params_bl, env->reg_params, mode, nr);
1977                 pmap_insert(env->regs, (void *) reg, proj);
1978                 be_set_constr_single_reg_out(env->reg_params, nr, reg, add_type);
1979                 arch_set_irn_register(proj, reg);
1980
1981                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1982         }
1983         obstack_free(&env->obst, rm);
1984
1985         /* create a new initial memory proj */
1986         assert(is_Proj(old_mem));
1987         new_mem_proj = new_r_Proj(irg, get_nodes_block(old_mem),
1988                                   new_r_Unknown(irg, mode_T), mode_M,
1989                                   get_Proj_proj(old_mem));
1990         mem = new_mem_proj;
1991
1992         /* Generate the Prologue */
1993         fp_reg = call->cb->prologue(env->cb, &mem, env->regs, &env->frame.initial_bias);
1994
1995         /* do the stack allocation BEFORE the barrier, or spill code
1996            might be added before it */
1997         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1998         start_bl     = get_irg_start_block(irg);
1999         env->init_sp = be_new_IncSP(sp, irg, start_bl, env->init_sp, BE_STACK_FRAME_SIZE_EXPAND, 0);
2000         be_abi_reg_map_set(env->regs, sp, env->init_sp);
2001
2002         create_barrier(env, start_bl, &mem, env->regs, 0);
2003
2004         env->init_sp = be_abi_reg_map_get(env->regs, sp);
2005         arch_set_irn_register(env->init_sp, sp);
2006
2007         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
2008         set_irg_frame(irg, frame_pointer);
2009         pset_insert_ptr(env->ignore_regs, fp_reg);
2010
2011         /* rewire old mem users to new mem */
2012         set_Proj_pred(new_mem_proj, get_Proj_pred(old_mem));
2013         exchange(old_mem, mem);
2014
2015         set_irg_initial_mem(irg, mem);
2016
2017         /* Now, introduce stack param nodes for all parameters passed on the stack */
2018         for (i = 0; i < n_params; ++i) {
2019                 ir_node *arg_proj = args[i];
2020                 ir_node *repl     = NULL;
2021
2022                 if (arg_proj != NULL) {
2023                         be_abi_call_arg_t *arg;
2024                         ir_type *param_type;
2025                         int     nr = get_Proj_proj(arg_proj);
2026                         ir_mode *mode;
2027
2028                         nr         = MIN(nr, n_params);
2029                         arg        = get_call_arg(call, 0, nr);
2030                         param_type = get_method_param_type(method_type, nr);
2031
2032                         if (arg->in_reg) {
2033                                 repl = pmap_get(env->regs, (void *) arg->reg);
2034                         } else if (arg->on_stack) {
2035                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, irg, reg_params_bl, frame_pointer, arg->stack_ent);
2036
2037                                 /* For atomic parameters which are actually used, we create a Load node. */
2038                                 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
2039                                         ir_mode *mode      = get_type_mode(param_type);
2040                                         ir_mode *load_mode = arg->load_mode;
2041
2042                                         ir_node *load = new_r_Load(irg, reg_params_bl, new_NoMem(), addr, load_mode, cons_floats);
2043                                         repl = new_r_Proj(irg, reg_params_bl, load, load_mode, pn_Load_res);
2044
2045                                         if (mode != load_mode) {
2046                                                 repl = new_r_Conv(irg, reg_params_bl, repl, mode, 0);
2047                                         }
2048                                 } else {
2049                                         /* The stack parameter is not primitive (it is a struct or array),
2050                                          * we thus will create a node representing the parameter's address
2051                                          * on the stack. */
2052                                         repl = addr;
2053                                 }
2054                         }
2055
2056                         assert(repl != NULL);
2057
2058                         /* Beware: the mode of the register parameters is always the mode of the register class
2059                            which may be wrong. Add Conv's then. */
2060                         mode = get_irn_mode(args[i]);
2061                         if (mode != get_irn_mode(repl)) {
2062                                 repl = new_r_Conv(irg, get_irn_n(repl, -1), repl, mode, 0);
2063                         }
2064                         exchange(args[i], repl);
2065                 }
2066         }
2067
2068         /* the arg proj is not needed anymore now and should be only used by the anchor */
2069         assert(get_irn_n_edges(arg_tuple) == 1);
2070         kill_node(arg_tuple);
2071         set_irg_args(irg, new_r_Bad(irg));
2072
2073         /* All Return nodes hang on the End node, so look for them there. */
2074         end = get_irg_end_block(irg);
2075         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
2076                 ir_node *irn = get_Block_cfgpred(end, i);
2077
2078                 if (is_Return(irn)) {
2079                         ir_node *blk = get_nodes_block(irn);
2080                         ir_node *mem = get_Return_mem(irn);
2081                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
2082                         exchange(irn, ret);
2083                 }
2084         }
2085         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
2086            the code is dead and will never be executed. */
2087
2088         obstack_free(&env->obst, args);
2089
2090         /* handle start block here (place a jump in the block) */
2091         fix_start_block(irg);
2092 }
2093
2094 /** Fix the state inputs of calls that still hang on unknowns */
2095 static
2096 void fix_call_state_inputs(be_abi_irg_t *env)
2097 {
2098         const arch_env_t *arch_env = env->arch_env;
2099         int i, n, n_states;
2100         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
2101
2102         /* Collect caller save registers */
2103         n = arch_env_get_n_reg_class(arch_env);
2104         for (i = 0; i < n; ++i) {
2105                 unsigned j;
2106                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
2107                 for (j = 0; j < cls->n_regs; ++j) {
2108                         const arch_register_t *reg = arch_register_for_index(cls, j);
2109                         if (arch_register_type_is(reg, state)) {
2110                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
2111                         }
2112                 }
2113         }
2114
2115         n = ARR_LEN(env->calls);
2116         n_states = ARR_LEN(stateregs);
2117         for (i = 0; i < n; ++i) {
2118                 int s, arity;
2119                 ir_node *call = env->calls[i];
2120
2121                 arity = get_irn_arity(call);
2122
2123                 /* the state reg inputs are the last n inputs of the calls */
2124                 for (s = 0; s < n_states; ++s) {
2125                         int inp = arity - n_states + s;
2126                         const arch_register_t *reg = stateregs[s];
2127                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
2128
2129                         set_irn_n(call, inp, regnode);
2130                 }
2131         }
2132
2133         DEL_ARR_F(stateregs);
2134 }
2135
2136 /**
2137  * Create a trampoline entity for the given method.
2138  */
2139 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
2140 {
2141         ir_type   *type   = get_entity_type(method);
2142         ident     *old_id = get_entity_ld_ident(method);
2143         ident     *id     = id_mangle3("L", old_id, "$stub");
2144         ir_type   *parent = be->pic_trampolines_type;
2145         ir_entity *ent    = new_entity(parent, old_id, type);
2146         set_entity_ld_ident(ent, id);
2147         set_entity_visibility(ent, visibility_local);
2148         set_entity_variability(ent, variability_uninitialized);
2149
2150         return ent;
2151 }
2152
2153 /**
2154  * Returns the trampoline entity for the given method.
2155  */
2156 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
2157 {
2158         ir_entity *result = pmap_get(env->ent_trampoline_map, method);
2159         if (result == NULL) {
2160                 result = create_trampoline(env, method);
2161                 pmap_insert(env->ent_trampoline_map, method, result);
2162         }
2163
2164         return result;
2165 }
2166
2167 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
2168 {
2169         ident     *old_id = get_entity_ld_ident(entity);
2170         ident     *id     = id_mangle3("L", old_id, "$non_lazy_ptr");
2171         ir_type   *e_type = get_entity_type(entity);
2172         ir_type   *type   = new_type_pointer(id, e_type, mode_P_data);
2173         ir_type   *parent = be->pic_symbols_type;
2174         ir_entity *ent    = new_entity(parent, old_id, type);
2175         set_entity_ld_ident(ent, id);
2176         set_entity_visibility(ent, visibility_local);
2177         set_entity_variability(ent, variability_uninitialized);
2178
2179         return ent;
2180 }
2181
2182 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
2183 {
2184         ir_entity *result = pmap_get(env->ent_pic_symbol_map, entity);
2185         if (result == NULL) {
2186                 result = create_pic_symbol(env, entity);
2187                 pmap_insert(env->ent_pic_symbol_map, entity, result);
2188         }
2189
2190         return result;
2191 }
2192
2193
2194
2195 /**
2196  * Returns non-zero if a given entity can be accessed using a relative address.
2197  */
2198 static int can_address_relative(ir_entity *entity)
2199 {
2200         return get_entity_variability(entity) == variability_initialized
2201                 || get_entity_visibility(entity) == visibility_local;
2202 }
2203
2204 /** patches SymConsts to work in position independent code */
2205 static void fix_pic_symconsts(ir_node *node, void *data)
2206 {
2207         ir_graph     *irg;
2208         ir_node      *pic_base;
2209         ir_node      *add;
2210         ir_node      *block;
2211         ir_node      *unknown;
2212         ir_mode      *mode;
2213         ir_node      *load;
2214         ir_node      *load_res;
2215         be_abi_irg_t *env = data;
2216         int           arity, i;
2217         be_main_env_t *be = env->birg->main_env;
2218
2219         arity = get_irn_arity(node);
2220         for (i = 0; i < arity; ++i) {
2221                 dbg_info  *dbgi;
2222                 ir_node   *pred = get_irn_n(node, i);
2223                 ir_entity *entity;
2224                 ir_entity *pic_symbol;
2225                 ir_node   *pic_symconst;
2226
2227                 if (!is_SymConst(pred))
2228                         continue;
2229
2230                 entity = get_SymConst_entity(pred);
2231                 block  = get_nodes_block(pred);
2232                 irg    = get_irn_irg(pred);
2233
2234                 /* calls can jump to relative addresses, so we can directly jump to
2235                    the (relatively) known call address or the trampoline */
2236                 if (i == 1 && is_Call(node)) {
2237                         ir_entity *trampoline;
2238                         ir_node   *trampoline_const;
2239
2240                         if (can_address_relative(entity))
2241                                 continue;
2242
2243                         dbgi             = get_irn_dbg_info(pred);
2244                         trampoline       = get_trampoline(be, entity);
2245                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2246                                                                     trampoline, NULL);
2247                         set_irn_n(node, i, trampoline_const);
2248                         continue;
2249                 }
2250
2251                 /* everything else is accessed relative to EIP */
2252                 mode     = get_irn_mode(pred);
2253                 unknown  = new_r_Unknown(irg, mode);
2254                 pic_base = arch_code_generator_get_pic_base(env->birg->cg);
2255
2256                 /* all ok now for locally constructed stuff */
2257                 if (can_address_relative(entity)) {
2258                         ir_node *add = new_r_Add(irg, block, pic_base, pred, mode);
2259
2260                         /* make sure the walker doesn't visit this add again */
2261                         mark_irn_visited(add);
2262                         set_irn_n(node, i, add);
2263                         continue;
2264                 }
2265
2266                 /* get entry from pic symbol segment */
2267                 dbgi         = get_irn_dbg_info(pred);
2268                 pic_symbol   = get_pic_symbol(be, entity);
2269                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2270                                                         pic_symbol, NULL);
2271                 add = new_r_Add(irg, block, pic_base, pic_symconst, mode);
2272                 mark_irn_visited(add);
2273
2274                 /* we need an extra indirection for global data outside our current
2275                    module. The loads are always safe and can therefore float
2276                    and need no memory input */
2277                 load     = new_r_Load(irg, block, new_NoMem(), add, mode, cons_floats);
2278                 load_res = new_r_Proj(irg, block, load, mode, pn_Load_res);
2279
2280                 set_irn_n(node, i, load_res);
2281         }
2282 }
2283
2284 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
2285 {
2286         be_abi_irg_t *env  = XMALLOC(be_abi_irg_t);
2287         ir_node *old_frame = get_irg_frame(birg->irg);
2288         ir_graph *irg      = birg->irg;
2289
2290         pmap_entry *ent;
2291         ir_node *dummy;
2292         optimization_state_t state;
2293         unsigned *limited_bitset;
2294
2295         be_omit_fp      = birg->main_env->options->omit_fp;
2296         be_omit_leaf_fp = birg->main_env->options->omit_leaf_fp;
2297
2298         obstack_init(&env->obst);
2299
2300         env->arch_env    = birg->main_env->arch_env;
2301         env->method_type = get_entity_type(get_irg_entity(irg));
2302         env->call        = be_abi_call_new(env->arch_env->sp->reg_class);
2303         arch_env_get_call_abi(env->arch_env, env->method_type, env->call);
2304
2305         env->ignore_regs  = pset_new_ptr_default();
2306         env->keep_map     = pmap_create();
2307         env->dce_survivor = new_survive_dce();
2308         env->birg         = birg;
2309
2310         env->sp_req.type    = arch_register_req_type_limited;
2311         env->sp_req.cls     = arch_register_get_class(env->arch_env->sp);
2312         limited_bitset      = rbitset_obstack_alloc(&env->obst, env->sp_req.cls->n_regs);
2313         rbitset_set(limited_bitset, arch_register_get_index(env->arch_env->sp));
2314         env->sp_req.limited = limited_bitset;
2315         if (env->arch_env->sp->type & arch_register_type_ignore) {
2316                 env->sp_req.type |= arch_register_req_type_ignore;
2317         }
2318
2319         env->sp_cls_req.type  = arch_register_req_type_normal;
2320         env->sp_cls_req.cls   = arch_register_get_class(env->arch_env->sp);
2321
2322         /* Beware: later we replace this node by the real one, ensure it is not CSE'd
2323            to another Unknown or the stack pointer gets used */
2324         save_optimization_state(&state);
2325         set_optimize(0);
2326         env->init_sp = dummy  = new_r_Unknown(irg, env->arch_env->sp->reg_class->mode);
2327         restore_optimization_state(&state);
2328
2329         FIRM_DBG_REGISTER(env->dbg, "firm.be.abi");
2330
2331         env->calls = NEW_ARR_F(ir_node*, 0);
2332
2333         if (birg->main_env->options->pic) {
2334                 irg_walk_graph(irg, fix_pic_symconsts, NULL, env);
2335         }
2336
2337         /* Lower all call nodes in the IRG. */
2338         process_calls(env);
2339
2340         /*
2341                 Beware: init backend abi call object after processing calls,
2342                 otherwise some information might be not yet available.
2343         */
2344         env->cb = env->call->cb->init(env->call, birg->main_env->arch_env, irg);
2345
2346         /* Process the IRG */
2347         modify_irg(env);
2348
2349         /* fix call inputs for state registers */
2350         fix_call_state_inputs(env);
2351
2352         /* We don't need the keep map anymore. */
2353         pmap_destroy(env->keep_map);
2354         env->keep_map = NULL;
2355
2356         /* calls array is not needed anymore */
2357         DEL_ARR_F(env->calls);
2358         env->calls = NULL;
2359
2360         /* reroute the stack origin of the calls to the true stack origin. */
2361         exchange(dummy, env->init_sp);
2362         exchange(old_frame, get_irg_frame(irg));
2363
2364         /* Make some important node pointers survive the dead node elimination. */
2365         survive_dce_register_irn(env->dce_survivor, &env->init_sp);
2366         foreach_pmap(env->regs, ent) {
2367                 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
2368         }
2369
2370         env->call->cb->done(env->cb);
2371         env->cb = NULL;
2372         return env;
2373 }
2374
2375 void be_abi_free(be_abi_irg_t *env)
2376 {
2377         be_abi_call_free(env->call);
2378         free_survive_dce(env->dce_survivor);
2379         del_pset(env->ignore_regs);
2380         pmap_destroy(env->regs);
2381         obstack_free(&env->obst, NULL);
2382         free(env);
2383 }
2384
2385 void be_abi_put_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, bitset_t *bs)
2386 {
2387         arch_register_t *reg;
2388
2389         for (reg = pset_first(abi->ignore_regs); reg; reg = pset_next(abi->ignore_regs))
2390                 if (reg->reg_class == cls)
2391                         bitset_set(bs, reg->index);
2392 }
2393
2394 void be_abi_set_non_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, unsigned *raw_bitset)
2395 {
2396         unsigned         i;
2397         arch_register_t *reg;
2398
2399         for (i = 0; i < cls->n_regs; ++i) {
2400                 if (arch_register_type_is(&cls->regs[i], ignore))
2401                         continue;
2402
2403                 rbitset_set(raw_bitset, i);
2404         }
2405
2406         for (reg = pset_first(abi->ignore_regs); reg != NULL;
2407              reg = pset_next(abi->ignore_regs)) {
2408                 if (reg->reg_class != cls)
2409                         continue;
2410
2411                 rbitset_clear(raw_bitset, reg->index);
2412         }
2413 }
2414
2415 /* Returns the stack layout from a abi environment. */
2416 const be_stack_layout_t *be_abi_get_stack_layout(const be_abi_irg_t *abi)
2417 {
2418         return &abi->frame;
2419 }
2420
2421 /*
2422
2423   _____ _        ____  _             _
2424  |  ___(_)_  __ / ___|| |_ __ _  ___| | __
2425  | |_  | \ \/ / \___ \| __/ _` |/ __| |/ /
2426  |  _| | |>  <   ___) | || (_| | (__|   <
2427  |_|   |_/_/\_\ |____/ \__\__,_|\___|_|\_\
2428
2429 */
2430
2431 typedef ir_node **node_array;
2432
2433 typedef struct fix_stack_walker_env_t {
2434         node_array sp_nodes;
2435 } fix_stack_walker_env_t;
2436
2437 /**
2438  * Walker. Collect all stack modifying nodes.
2439  */
2440 static void collect_stack_nodes_walker(ir_node *node, void *data)
2441 {
2442         fix_stack_walker_env_t    *env = data;
2443         const arch_register_req_t *req;
2444
2445         if (get_irn_mode(node) == mode_T)
2446                 return;
2447
2448         req = arch_get_register_req_out(node);
2449         if (! (req->type & arch_register_req_type_produces_sp))
2450                 return;
2451
2452         ARR_APP1(ir_node*, env->sp_nodes, node);
2453 }
2454
2455 void be_abi_fix_stack_nodes(be_abi_irg_t *env)
2456 {
2457         be_ssa_construction_env_t senv;
2458         int i, len;
2459         ir_node **phis;
2460         be_irg_t *birg = env->birg;
2461         be_lv_t *lv = be_get_birg_liveness(birg);
2462         fix_stack_walker_env_t walker_env;
2463
2464         walker_env.sp_nodes = NEW_ARR_F(ir_node*, 0);
2465
2466         irg_walk_graph(birg->irg, collect_stack_nodes_walker, NULL, &walker_env);
2467
2468         /* nothing to be done if we didn't find any node, in fact we mustn't
2469          * continue, as for endless loops incsp might have had no users and is bad
2470          * now.
2471          */
2472         len = ARR_LEN(walker_env.sp_nodes);
2473         if (len == 0) {
2474                 DEL_ARR_F(walker_env.sp_nodes);
2475                 return;
2476         }
2477
2478         be_ssa_construction_init(&senv, birg);
2479         be_ssa_construction_add_copies(&senv, walker_env.sp_nodes,
2480                                    ARR_LEN(walker_env.sp_nodes));
2481         be_ssa_construction_fix_users_array(&senv, walker_env.sp_nodes,
2482                                             ARR_LEN(walker_env.sp_nodes));
2483
2484         if (lv != NULL) {
2485                 len = ARR_LEN(walker_env.sp_nodes);
2486                 for (i = 0; i < len; ++i) {
2487                         be_liveness_update(lv, walker_env.sp_nodes[i]);
2488                 }
2489                 be_ssa_construction_update_liveness_phis(&senv, lv);
2490         }
2491
2492         phis = be_ssa_construction_get_new_phis(&senv);
2493
2494         /* set register requirements for stack phis */
2495         len = ARR_LEN(phis);
2496         for (i = 0; i < len; ++i) {
2497                 ir_node *phi = phis[i];
2498                 be_set_phi_reg_req(phi, &env->sp_req, arch_register_req_type_produces_sp);
2499                 arch_set_irn_register(phi, env->arch_env->sp);
2500         }
2501         be_ssa_construction_destroy(&senv);
2502
2503         DEL_ARR_F(walker_env.sp_nodes);
2504 }
2505
2506 /**
2507  * Fix all stack accessing operations in the block bl.
2508  *
2509  * @param env        the abi environment
2510  * @param bl         the block to process
2511  * @param real_bias  the bias value
2512  *
2513  * @return the bias at the end of this block
2514  */
2515 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int real_bias)
2516 {
2517         int               omit_fp  = env->call->flags.bits.try_omit_fp;
2518         ir_node          *irn;
2519         int               wanted_bias = real_bias;
2520
2521         sched_foreach(bl, irn) {
2522                 int ofs;
2523
2524                 /*
2525                    Check, if the node relates to an entity on the stack frame.
2526                    If so, set the true offset (including the bias) for that
2527                    node.
2528                  */
2529                 ir_entity *ent = arch_get_frame_entity(irn);
2530                 if (ent != NULL) {
2531                         int bias   = omit_fp ? real_bias : 0;
2532                         int offset = get_stack_entity_offset(&env->frame, ent, bias);
2533                         arch_set_frame_offset(irn, offset);
2534                         DBG((env->dbg, LEVEL_2, "%F has offset %d (including bias %d)\n",
2535                              ent, offset, bias));
2536                 }
2537
2538                 /*
2539                  * If the node modifies the stack pointer by a constant offset,
2540                  * record that in the bias.
2541                  */
2542                 ofs = arch_get_sp_bias(irn);
2543
2544                 if (be_is_IncSP(irn)) {
2545                         /* fill in real stack frame size */
2546                         if (ofs == BE_STACK_FRAME_SIZE_EXPAND) {
2547                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2548                                 ofs = (int) get_type_size_bytes(frame_type);
2549                                 be_set_IncSP_offset(irn, ofs);
2550                         } else if (ofs == BE_STACK_FRAME_SIZE_SHRINK) {
2551                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2552                                 ofs = - (int)get_type_size_bytes(frame_type);
2553                                 be_set_IncSP_offset(irn, ofs);
2554                         } else {
2555                                 if (be_get_IncSP_align(irn)) {
2556                                         /* patch IncSP to produce an aligned stack pointer */
2557                                         ir_type *between_type = env->frame.between_type;
2558                                         int      between_size = get_type_size_bytes(between_type);
2559                                         int      alignment    = 1 << env->arch_env->stack_alignment;
2560                                         int      delta        = (real_bias + ofs + between_size) & (alignment - 1);
2561                                         assert(ofs >= 0);
2562                                         if (delta > 0) {
2563                                                 be_set_IncSP_offset(irn, ofs + alignment - delta);
2564                                                 real_bias += alignment - delta;
2565                                         }
2566                                 } else {
2567                                         /* adjust so real_bias corresponds with wanted_bias */
2568                                         int delta = wanted_bias - real_bias;
2569                                         assert(delta <= 0);
2570                                         if (delta != 0) {
2571                                                 be_set_IncSP_offset(irn, ofs + delta);
2572                                                 real_bias += delta;
2573                                         }
2574                                 }
2575                         }
2576                 }
2577
2578                 real_bias   += ofs;
2579                 wanted_bias += ofs;
2580         }
2581
2582         assert(real_bias == wanted_bias);
2583         return real_bias;
2584 }
2585
2586 /**
2587  * A helper struct for the bias walker.
2588  */
2589 struct bias_walk {
2590         be_abi_irg_t *env;     /**< The ABI irg environment. */
2591         int           start_block_bias;  /**< The bias at the end of the start block. */
2592         int           between_size;
2593         ir_node      *start_block;  /**< The start block of the current graph. */
2594 };
2595
2596 /**
2597  * Block-Walker: fix all stack offsets for all blocks
2598  * except the start block
2599  */
2600 static void stack_bias_walker(ir_node *bl, void *data)
2601 {
2602         struct bias_walk *bw = data;
2603         if (bl != bw->start_block) {
2604                 process_stack_bias(bw->env, bl, bw->start_block_bias);
2605         }
2606 }
2607
2608 /**
2609  * Walker: finally lower all Sels of outer frame or parameter
2610  * entities.
2611  */
2612 static void lower_outer_frame_sels(ir_node *sel, void *ctx) {
2613         be_abi_irg_t *env = ctx;
2614         ir_node      *ptr;
2615         ir_entity    *ent;
2616         ir_type      *owner;
2617
2618         if (! is_Sel(sel))
2619                 return;
2620
2621         ent   = get_Sel_entity(sel);
2622         owner = get_entity_owner(ent);
2623         ptr   = get_Sel_ptr(sel);
2624
2625         if (owner == env->frame.frame_type || owner == env->frame.arg_type) {
2626                 /* found access to outer frame or arguments */
2627                 int offset = get_stack_entity_offset(&env->frame, ent, 0);
2628
2629                 if (offset != 0) {
2630                         ir_node  *bl   = get_nodes_block(sel);
2631                         dbg_info *dbgi = get_irn_dbg_info(sel);
2632                         ir_mode  *mode = get_irn_mode(sel);
2633                         ir_mode  *mode_UInt = get_reference_mode_unsigned_eq(mode);
2634                         ir_node  *cnst = new_r_Const_long(current_ir_graph, mode_UInt, offset);
2635
2636                         ptr = new_rd_Add(dbgi, current_ir_graph, bl, ptr, cnst, mode);
2637                 }
2638                 exchange(sel, ptr);
2639         }
2640 }
2641
2642 void be_abi_fix_stack_bias(be_abi_irg_t *env)
2643 {
2644         ir_graph          *irg = env->birg->irg;
2645         ir_type           *frame_tp;
2646         int               i;
2647         struct bias_walk  bw;
2648
2649         stack_frame_compute_initial_offset(&env->frame);
2650         // stack_layout_dump(stdout, frame);
2651
2652         /* Determine the stack bias at the end of the start block. */
2653         bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), env->frame.initial_bias);
2654         bw.between_size     = get_type_size_bytes(env->frame.between_type);
2655
2656         /* fix the bias is all other blocks */
2657         bw.env = env;
2658         bw.start_block = get_irg_start_block(irg);
2659         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
2660
2661         /* fix now inner functions: these still have Sel node to outer
2662            frame and parameter entities */
2663         frame_tp = get_irg_frame_type(irg);
2664         for (i = get_class_n_members(frame_tp) - 1; i >= 0; --i) {
2665                 ir_entity *ent = get_class_member(frame_tp, i);
2666
2667                 if (is_method_entity(ent) && get_entity_peculiarity(ent) != peculiarity_description) {
2668                         ir_graph *irg = get_entity_irg(ent);
2669
2670                         irg_walk_graph(irg, NULL, lower_outer_frame_sels, env);
2671                 }
2672         }
2673 }
2674
2675 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2676 {
2677         assert(arch_register_type_is(reg, callee_save));
2678         assert(pmap_contains(abi->regs, (void *) reg));
2679         return pmap_get(abi->regs, (void *) reg);
2680 }
2681
2682 ir_node *be_abi_get_ignore_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2683 {
2684         assert(arch_register_type_is(reg, ignore));
2685         assert(pmap_contains(abi->regs, (void *) reg));
2686         return pmap_get(abi->regs, (void *) reg);
2687 }
2688
2689 /**
2690  * Returns non-zero if the ABI has omitted the frame pointer in
2691  * the current graph.
2692  */
2693 int be_abi_omit_fp(const be_abi_irg_t *abi)
2694 {
2695         return abi->call->flags.bits.try_omit_fp;
2696 }