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