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

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