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

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