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