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

   1 /*
   2  * Copyright (C) 1995-2007 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 *mt                = get_Call_type(irn);
 414         ir_node *call_ptr          = get_Call_ptr(irn);
 415         int n_params               = get_method_n_params(mt);
 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(mt);
 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, mt, 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(mt, 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(mt, 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(mt, 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         pmap_foreach(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         pmap_foreach(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         pmap_foreach(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                 int 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                 for (ent = new_list; ent; ent = get_entity_link(ent)) {
1633                         ir_type *tp = get_entity_type(ent);
1634                         int align = get_type_alignment_bytes(tp);
1635
1636                         offset += align - 1;
1637                         offset &= -align;
1638                         set_entity_owner(ent, frame_tp);
1639                         add_class_member(frame_tp, ent);
1640                         /* must be automatic to set a fixed layout */
1641                         set_entity_allocation(ent, allocation_automatic);
1642                         set_entity_offset(ent, offset);
1643                         offset += get_type_size_bytes(tp);
1644                 }
1645                 set_type_size_bytes(frame_tp, offset);
1646         }
1647 }
1648
1649 #if 1
1650 /**
1651  * The start block has no jump, instead it has an initial exec Proj.
1652  * The backend wants to handle all blocks the same way, so we replace
1653  * the out cfg edge with a real jump.
1654  */
1655 static void fix_start_block(ir_node *block, void *env) {
1656         int      *done = env;
1657         int      i;
1658         ir_node  *start_block;
1659         ir_graph *irg;
1660
1661         /* we processed the start block, return */
1662         if (*done)
1663                 return;
1664
1665         irg         = get_irn_irg(block);
1666         start_block = get_irg_start_block(irg);
1667
1668         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
1669                 ir_node *pred       = get_Block_cfgpred(block, i);
1670                 ir_node *pred_block = get_nodes_block(pred);
1671
1672                 /* ok, we are in the block, having start as cfg predecessor */
1673                 if (pred_block == start_block) {
1674                         ir_node *jump = new_r_Jmp(irg, pred_block);
1675                         set_Block_cfgpred(block, i, jump);
1676                         *done = 1;
1677                 }
1678         }
1679 }
1680 #endif
1681
1682 /**
1683  * Modify the irg itself and the frame type.
1684  */
1685 static void modify_irg(be_abi_irg_t *env)
1686 {
1687         be_abi_call_t *call       = env->call;
1688         const arch_isa_t *isa     = env->birg->main_env->arch_env->isa;
1689         const arch_register_t *sp = arch_isa_sp(isa);
1690         ir_graph *irg             = env->birg->irg;
1691         ir_node *bl               = get_irg_start_block(irg);
1692         ir_node *end              = get_irg_end_block(irg);
1693         ir_node *old_mem          = get_irg_initial_mem(irg);
1694         ir_node *new_mem_proj;
1695         ir_node *mem;
1696         ir_type *method_type      = get_entity_type(get_irg_entity(irg));
1697         pset *dont_save           = pset_new_ptr(8);
1698
1699         int n_params;
1700         int i, n;
1701         unsigned j;
1702
1703         reg_node_map_t *rm;
1704         const arch_register_t *fp_reg;
1705         ir_node *frame_pointer;
1706         ir_node *reg_params_bl;
1707         ir_node **args;
1708         ir_node *arg_tuple;
1709         ir_node *value_param_base;
1710         const ir_edge_t *edge;
1711         ir_type *arg_type, *bet_type, *tp;
1712         lower_frame_sels_env_t ctx;
1713         ir_entity **param_map;
1714
1715         bitset_t *used_proj_nr;
1716         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1717
1718         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1719
1720         /* set the links of all frame entities to NULL, we use it
1721            to detect if an entity is already linked in the value_param_list */
1722         tp = get_method_value_param_type(method_type);
1723         if (tp != NULL) {
1724                 for (i = get_struct_n_members(tp) - 1; i >= 0; --i)
1725                         set_entity_link(get_struct_member(tp, i), NULL);
1726         }
1727
1728         /* Convert the Sel nodes in the irg to frame load/store/addr nodes. */
1729         ctx.env              = env;
1730         ctx.value_param_list = NULL;
1731         ctx.value_param_tail = NULL;
1732         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1733
1734         /* value_param_base anchor is not needed anymore now */
1735         value_param_base = get_irg_value_param_base(irg);
1736         be_kill_node(value_param_base);
1737         set_irg_value_param_base(irg, new_r_Bad(irg));
1738
1739         env->frame = obstack_alloc(&env->obst, sizeof(env->frame[0]));
1740         env->regs  = pmap_create();
1741
1742         used_proj_nr = bitset_alloca(1024);
1743         n_params     = get_method_n_params(method_type);
1744         args         = obstack_alloc(&env->obst, n_params * sizeof(args[0]));
1745         memset(args, 0, n_params * sizeof(args[0]));
1746
1747         /* Check if a value parameter is transmitted as a register.
1748          * This might happen if the address of an parameter is taken which is
1749          * transmitted in registers.
1750          *
1751          * Note that on some architectures this case must be handled specially
1752          * because the place of the backing store is determined by their ABI.
1753          *
1754          * In the default case we move the entity to the frame type and create
1755          * a backing store into the first block.
1756          */
1757         fix_address_of_parameter_access(env, ctx.value_param_list);
1758
1759         /* Fill the argument vector */
1760         arg_tuple = get_irg_args(irg);
1761         foreach_out_edge(arg_tuple, edge) {
1762                 ir_node *irn = get_edge_src_irn(edge);
1763                 if (! is_Anchor(irn)) {
1764                         int nr       = get_Proj_proj(irn);
1765                         args[nr]     = irn;
1766                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1767                 }
1768         }
1769
1770         arg_type = compute_arg_type(env, call, method_type, &param_map);
1771         bet_type = call->cb->get_between_type(env->cb);
1772         stack_frame_init(env->frame, arg_type, bet_type, get_irg_frame_type(irg), isa->stack_dir, param_map);
1773
1774         /* Count the register params and add them to the number of Projs for the RegParams node */
1775         for(i = 0; i < n_params; ++i) {
1776                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1777                 if(arg->in_reg && args[i]) {
1778                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1779                         assert(i == get_Proj_proj(args[i]));
1780
1781                         /* For now, associate the register with the old Proj from Start representing that argument. */
1782                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1783                         bitset_set(used_proj_nr, i);
1784                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1785                 }
1786         }
1787
1788         /* Collect all callee-save registers */
1789         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
1790                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
1791                 for(j = 0; j < cls->n_regs; ++j) {
1792                         const arch_register_t *reg = &cls->regs[j];
1793                         if(arch_register_type_is(reg, callee_save) ||
1794                                         arch_register_type_is(reg, state)) {
1795                                 pmap_insert(env->regs, (void *) reg, NULL);
1796                         }
1797                 }
1798         }
1799
1800         pmap_insert(env->regs, (void *) sp, NULL);
1801         pmap_insert(env->regs, (void *) isa->bp, NULL);
1802         reg_params_bl   = get_irg_start_block(irg);
1803         env->reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(env->regs));
1804         add_irn_dep(env->reg_params, get_irg_start(irg));
1805
1806         /*
1807          * make proj nodes for the callee save registers.
1808          * memorize them, since Return nodes get those as inputs.
1809          *
1810          * Note, that if a register corresponds to an argument, the regs map contains
1811          * the old Proj from start for that argument.
1812          */
1813
1814         rm = reg_map_to_arr(&env->obst, env->regs);
1815         for(i = 0, n = pmap_count(env->regs); i < n; ++i) {
1816                 arch_register_t *reg = (void *) rm[i].reg;
1817                 ir_mode *mode        = reg->reg_class->mode;
1818                 long nr              = i;
1819                 int pos              = BE_OUT_POS((int) nr);
1820                 int flags            = 0;
1821
1822                 ir_node *proj;
1823
1824                 assert(nr >= 0);
1825                 bitset_set(used_proj_nr, nr);
1826                 proj = new_r_Proj(irg, reg_params_bl, env->reg_params, mode, nr);
1827                 pmap_insert(env->regs, (void *) reg, proj);
1828                 be_set_constr_single_reg(env->reg_params, pos, reg);
1829                 arch_set_irn_register(env->birg->main_env->arch_env, proj, reg);
1830
1831                 /*
1832                  * If the register is an ignore register,
1833                  * The Proj for that register shall also be ignored during register allocation.
1834                  */
1835                 if(arch_register_type_is(reg, ignore))
1836                         flags |= arch_irn_flags_ignore;
1837
1838                 if(reg == sp)
1839                         flags |= arch_irn_flags_modify_sp;
1840
1841                 be_node_set_flags(env->reg_params, pos, flags);
1842
1843                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1844         }
1845         obstack_free(&env->obst, rm);
1846
1847         /* create a new initial memory proj */
1848         assert(is_Proj(old_mem));
1849         new_mem_proj = new_r_Proj(irg, get_nodes_block(old_mem),
1850                                   new_r_Unknown(irg, mode_T), mode_M,
1851                                   get_Proj_proj(old_mem));
1852         mem = new_mem_proj;
1853
1854         /* Generate the Prologue */
1855         fp_reg  = call->cb->prologue(env->cb, &mem, env->regs);
1856
1857         /* do the stack allocation BEFORE the barrier, or spill code
1858            might be added before it */
1859         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1860         env->init_sp = be_new_IncSP(sp, irg, bl, env->init_sp, BE_STACK_FRAME_SIZE_EXPAND);
1861         be_abi_reg_map_set(env->regs, sp, env->init_sp);
1862
1863         create_barrier(env, bl, &mem, env->regs, 0);
1864
1865         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1866         arch_set_irn_register(env->birg->main_env->arch_env, env->init_sp, sp);
1867
1868         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1869         set_irg_frame(irg, frame_pointer);
1870         pset_insert_ptr(env->ignore_regs, fp_reg);
1871
1872         /* rewire old mem users to new mem */
1873         set_Proj_pred(new_mem_proj, get_Proj_pred(old_mem));
1874         exchange(old_mem, mem);
1875
1876         set_irg_initial_mem(irg, mem);
1877
1878         /* Now, introduce stack param nodes for all parameters passed on the stack */
1879         for(i = 0; i < n_params; ++i) {
1880                 ir_node *arg_proj = args[i];
1881                 ir_node *repl     = NULL;
1882
1883                 if(arg_proj != NULL) {
1884                         be_abi_call_arg_t *arg;
1885                         ir_type *param_type;
1886                         int     nr = get_Proj_proj(arg_proj);
1887                         ir_mode *mode;
1888
1889                         nr         = MIN(nr, n_params);
1890                         arg        = get_call_arg(call, 0, nr);
1891                         param_type = get_method_param_type(method_type, nr);
1892
1893                         if (arg->in_reg) {
1894                                 repl = pmap_get(env->regs, (void *) arg->reg);
1895                         } else if(arg->on_stack) {
1896                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, irg, reg_params_bl, frame_pointer, arg->stack_ent);
1897
1898                                 /* For atomic parameters which are actually used, we create a Load node. */
1899                                 if(is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1900                                         ir_mode *mode      = get_type_mode(param_type);
1901                                         ir_mode *load_mode = arg->load_mode;
1902
1903                                         ir_node *load = new_r_Load(irg, reg_params_bl, new_NoMem(), addr, load_mode);
1904                                         set_irn_pinned(load, op_pin_state_floats);
1905                                         repl = new_r_Proj(irg, reg_params_bl, load, load_mode, pn_Load_res);
1906
1907                                         if (mode != load_mode) {
1908                                                 repl = new_r_Conv(irg, reg_params_bl, repl, mode);
1909                                         }
1910                                 } else {
1911                                         /* The stack parameter is not primitive (it is a struct or array),
1912                                          * we thus will create a node representing the parameter's address
1913                                          * on the stack. */
1914                                         repl = addr;
1915                                 }
1916                         }
1917
1918                         assert(repl != NULL);
1919
1920                         /* Beware: the mode of the register parameters is always the mode of the register class
1921                            which may be wrong. Add Conv's then. */
1922                         mode = get_irn_mode(args[i]);
1923                         if (mode != get_irn_mode(repl)) {
1924                                 repl = new_r_Conv(irg, get_irn_n(repl, -1), repl, mode);
1925                         }
1926                         exchange(args[i], repl);
1927                 }
1928         }
1929
1930         /* the arg proj is not needed anymore now and should be only used by the anchor */
1931         assert(get_irn_n_edges(arg_tuple) == 1);
1932         be_kill_node(arg_tuple);
1933         set_irg_args(irg, new_rd_Bad(irg));
1934
1935         /* All Return nodes hang on the End node, so look for them there. */
1936         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1937                 ir_node *irn = get_Block_cfgpred(end, i);
1938
1939                 if (is_Return(irn)) {
1940                         ir_node *ret = create_be_return(env, irn, get_nodes_block(irn), get_Return_mem(irn), get_Return_n_ress(irn));
1941                         exchange(irn, ret);
1942                 }
1943         }
1944         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1945            the code is dead and will never be executed. */
1946
1947         del_pset(dont_save);
1948         obstack_free(&env->obst, args);
1949
1950         /* handle start block here (place a jump in the block) */
1951         i = 0;
1952         irg_block_walk_graph(irg, fix_start_block, NULL, &i);
1953 }
1954
1955 /** Fix the state inputs of calls that still hang on unknowns */
1956 static
1957 void fix_call_state_inputs(be_abi_irg_t *env)
1958 {
1959         const arch_isa_t *isa = env->isa;
1960         int i, n, n_states;
1961         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1962
1963         /* Collect caller save registers */
1964         n = arch_isa_get_n_reg_class(isa);
1965         for(i = 0; i < n; ++i) {
1966                 unsigned j;
1967                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
1968                 for(j = 0; j < cls->n_regs; ++j) {
1969                         const arch_register_t *reg = arch_register_for_index(cls, j);
1970                         if(arch_register_type_is(reg, state)) {
1971                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1972                         }
1973                 }
1974         }
1975
1976         n = ARR_LEN(env->calls);
1977         n_states = ARR_LEN(stateregs);
1978         for(i = 0; i < n; ++i) {
1979                 int s, arity;
1980                 ir_node *call = env->calls[i];
1981
1982                 arity = get_irn_arity(call);
1983
1984                 /* the statereg inputs are the last n inputs of the calls */
1985                 for(s = 0; s < n_states; ++s) {
1986                         int inp = arity - n_states + s;
1987                         const arch_register_t *reg = stateregs[s];
1988                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1989
1990                         set_irn_n(call, inp, regnode);
1991                 }
1992         }
1993 }
1994
1995 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
1996 {
1997         be_abi_irg_t *env  = xmalloc(sizeof(env[0]));
1998         ir_node *old_frame = get_irg_frame(birg->irg);
1999         ir_graph *irg      = birg->irg;
2000
2001         pmap_entry *ent;
2002         ir_node *dummy;
2003         optimization_state_t state;
2004         unsigned *limited_bitset;
2005
2006         be_omit_fp = birg->main_env->options->omit_fp;
2007
2008         obstack_init(&env->obst);
2009
2010         env->isa         = birg->main_env->arch_env->isa;
2011         env->method_type = get_entity_type(get_irg_entity(irg));
2012         env->call        = be_abi_call_new(env->isa->sp->reg_class);
2013         arch_isa_get_call_abi(env->isa, env->method_type, env->call);
2014
2015         env->ignore_regs  = pset_new_ptr_default();
2016         env->keep_map     = pmap_create();
2017         env->dce_survivor = new_survive_dce();
2018         env->birg         = birg;
2019
2020         env->sp_req.type    = arch_register_req_type_limited;
2021         env->sp_req.cls     = arch_register_get_class(env->isa->sp);
2022         limited_bitset      = rbitset_obstack_alloc(&env->obst, env->sp_req.cls->n_regs);
2023         rbitset_set(limited_bitset, arch_register_get_index(env->isa->sp));
2024         env->sp_req.limited = limited_bitset;
2025
2026         env->sp_cls_req.type  = arch_register_req_type_normal;
2027         env->sp_cls_req.cls   = arch_register_get_class(env->isa->sp);
2028
2029         /* Beware: later we replace this node by the real one, ensure it is not CSE'd
2030            to another Unknown or the stack pointer gets used */
2031         save_optimization_state(&state);
2032         set_optimize(0);
2033         env->init_sp = dummy  = new_r_Unknown(irg, env->isa->sp->reg_class->mode);
2034         restore_optimization_state(&state);
2035         FIRM_DBG_REGISTER(env->dbg, "firm.be.abi");
2036
2037         env->calls = NEW_ARR_F(ir_node*, 0);
2038
2039         /* Lower all call nodes in the IRG. */
2040         process_calls(env);
2041
2042         /*
2043                 Beware: init backend abi call object after processing calls,
2044                 otherwise some information might be not yet available.
2045         */
2046         env->cb = env->call->cb->init(env->call, birg->main_env->arch_env, irg);
2047
2048         /* Process the IRG */
2049         modify_irg(env);
2050
2051         /* fix call inputs for state registers */
2052         fix_call_state_inputs(env);
2053
2054         /* We don't need the keep map anymore. */
2055         pmap_destroy(env->keep_map);
2056
2057         /* calls array is not needed anymore */
2058         DEL_ARR_F(env->calls);
2059
2060         /* reroute the stack origin of the calls to the true stack origin. */
2061         exchange(dummy, env->init_sp);
2062         exchange(old_frame, get_irg_frame(irg));
2063
2064         /* Make some important node pointers survive the dead node elimination. */
2065         survive_dce_register_irn(env->dce_survivor, &env->init_sp);
2066         pmap_foreach(env->regs, ent) {
2067                 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
2068         }
2069
2070         env->call->cb->done(env->cb);
2071         env->cb = NULL;
2072         return env;
2073 }
2074
2075 void be_abi_free(be_abi_irg_t *env)
2076 {
2077         be_abi_call_free(env->call);
2078         free_survive_dce(env->dce_survivor);
2079         del_pset(env->ignore_regs);
2080         pmap_destroy(env->regs);
2081         obstack_free(&env->obst, NULL);
2082         free(env);
2083 }
2084
2085 void be_abi_put_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, bitset_t *bs)
2086 {
2087         arch_register_t *reg;
2088
2089         for(reg = pset_first(abi->ignore_regs); reg; reg = pset_next(abi->ignore_regs))
2090                 if(reg->reg_class == cls)
2091                         bitset_set(bs, reg->index);
2092 }
2093
2094 /* Returns the stack layout from a abi environment. */
2095 const be_stack_layout_t *be_abi_get_stack_layout(const be_abi_irg_t *abi) {
2096         return abi->frame;
2097 }
2098
2099 /*
2100
2101   _____ _        ____  _             _
2102  |  ___(_)_  __ / ___|| |_ __ _  ___| | __
2103  | |_  | \ \/ / \___ \| __/ _` |/ __| |/ /
2104  |  _| | |>  <   ___) | || (_| | (__|   <
2105  |_|   |_/_/\_\ |____/ \__\__,_|\___|_|\_\
2106
2107 */
2108
2109 typedef ir_node **node_array;
2110
2111 typedef struct fix_stack_walker_env_t {
2112         node_array sp_nodes;
2113         const arch_env_t *arch_env;
2114 } fix_stack_walker_env_t;
2115
2116 /**
2117  * Walker. Collect all stack modifying nodes.
2118  */
2119 static void collect_stack_nodes_walker(ir_node *node, void *data)
2120 {
2121         fix_stack_walker_env_t *env = data;
2122
2123         if (arch_irn_is(env->arch_env, node, modify_sp)) {
2124                 assert(get_irn_mode(node) != mode_M && get_irn_mode(node) != mode_T);
2125                 ARR_APP1(ir_node*, env->sp_nodes, node);
2126         }
2127 }
2128
2129 void be_abi_fix_stack_nodes(be_abi_irg_t *env)
2130 {
2131         be_ssa_construction_env_t senv;
2132         int i, len;
2133         ir_node **phis;
2134         be_irg_t *birg = env->birg;
2135         be_lv_t *lv = be_get_birg_liveness(birg);
2136         fix_stack_walker_env_t walker_env;
2137         arch_isa_t *isa;
2138
2139         walker_env.sp_nodes = NEW_ARR_F(ir_node*, 0);
2140         walker_env.arch_env = birg->main_env->arch_env;
2141         isa = walker_env.arch_env->isa;
2142
2143         irg_walk_graph(birg->irg, collect_stack_nodes_walker, NULL, &walker_env);
2144
2145         /* nothing to be done if we didn't find any node, in fact we mustn't
2146          * continue, as for endless loops incsp might have had no users and is bad
2147          * now.
2148          */
2149         len = ARR_LEN(walker_env.sp_nodes);
2150         if(len == 0) {
2151                 DEL_ARR_F(walker_env.sp_nodes);
2152                 return;
2153         }
2154
2155         be_ssa_construction_init(&senv, birg);
2156         be_ssa_construction_add_copies(&senv, walker_env.sp_nodes,
2157                                    ARR_LEN(walker_env.sp_nodes));
2158         be_ssa_construction_fix_users_array(&senv, walker_env.sp_nodes,
2159                                       ARR_LEN(walker_env.sp_nodes));
2160
2161         if(lv != NULL) {
2162                 len = ARR_LEN(walker_env.sp_nodes);
2163                 for(i = 0; i < len; ++i) {
2164                         be_liveness_update(lv, walker_env.sp_nodes[i]);
2165                 }
2166                 be_ssa_construction_update_liveness_phis(&senv, lv);
2167         }
2168
2169         phis = be_ssa_construction_get_new_phis(&senv);
2170
2171         /* set register requirements for stack phis */
2172         len = ARR_LEN(phis);
2173         for(i = 0; i < len; ++i) {
2174                 ir_node *phi = phis[i];
2175                 be_set_phi_reg_req(walker_env.arch_env, phi, &env->sp_req);
2176                 be_set_phi_flags(walker_env.arch_env, phi, arch_irn_flags_ignore | arch_irn_flags_modify_sp);
2177                 arch_set_irn_register(walker_env.arch_env, phi, env->isa->sp);
2178         }
2179         be_ssa_construction_destroy(&senv);
2180
2181         DEL_ARR_F(walker_env.sp_nodes);
2182 }
2183
2184 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int bias)
2185 {
2186         const arch_env_t *arch_env = env->birg->main_env->arch_env;
2187         int omit_fp            = env->call->flags.bits.try_omit_fp;
2188         ir_node *irn;
2189
2190         sched_foreach(bl, irn) {
2191                 int ofs;
2192
2193                 /*
2194                    Check, if the node relates to an entity on the stack frame.
2195                    If so, set the true offset (including the bias) for that
2196                    node.
2197                  */
2198                 ir_entity *ent = arch_get_frame_entity(arch_env, irn);
2199                 if(ent) {
2200                         int offset = get_stack_entity_offset(env->frame, ent, bias);
2201                         arch_set_frame_offset(arch_env, irn, offset);
2202                         DBG((env->dbg, LEVEL_2, "%F has offset %d (including bias %d)\n", ent, offset, bias));
2203                 }
2204
2205                 if(omit_fp || be_is_IncSP(irn)) {
2206                         /*
2207                          * If the node modifies the stack pointer by a constant offset,
2208                          * record that in the bias.
2209                          */
2210                         ofs = arch_get_sp_bias(arch_env, irn);
2211
2212                         if(be_is_IncSP(irn)) {
2213                                 if(ofs == BE_STACK_FRAME_SIZE_EXPAND) {
2214                                         ofs = get_type_size_bytes(get_irg_frame_type(env->birg->irg));
2215                                         be_set_IncSP_offset(irn, ofs);
2216                                 } else if(ofs == BE_STACK_FRAME_SIZE_SHRINK) {
2217                                         ofs = - get_type_size_bytes(get_irg_frame_type(env->birg->irg));
2218                                         be_set_IncSP_offset(irn, ofs);
2219                                 }
2220                         }
2221
2222                         if(omit_fp)
2223                                 bias += ofs;
2224                 }
2225         }
2226
2227         return bias;
2228 }
2229
2230 /**
2231  * A helper struct for the bias walker.
2232  */
2233 struct bias_walk {
2234         be_abi_irg_t *env;     /**< The ABI irg environment. */
2235         int start_block_bias;  /**< The bias at the end of the start block. */
2236         ir_node *start_block;  /**< The start block of the current graph. */
2237 };
2238
2239 /**
2240  * Block-Walker: fix all stack offsets
2241  */
2242 static void stack_bias_walker(ir_node *bl, void *data)
2243 {
2244         struct bias_walk *bw = data;
2245         if (bl != bw->start_block) {
2246                 process_stack_bias(bw->env, bl, bw->start_block_bias);
2247         }
2248 }
2249
2250 void be_abi_fix_stack_bias(be_abi_irg_t *env)
2251 {
2252         ir_graph *irg  = env->birg->irg;
2253         struct bias_walk bw;
2254
2255         stack_frame_compute_initial_offset(env->frame);
2256         // stack_layout_dump(stdout, env->frame);
2257
2258         /* Determine the stack bias at the end of the start block. */
2259         bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), 0);
2260
2261         /* fix the bias is all other blocks */
2262         bw.env = env;
2263         bw.start_block = get_irg_start_block(irg);
2264         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
2265 }
2266
2267 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2268 {
2269         assert(arch_register_type_is(reg, callee_save));
2270         assert(pmap_contains(abi->regs, (void *) reg));
2271         return pmap_get(abi->regs, (void *) reg);
2272 }
2273
2274 ir_node *be_abi_get_ignore_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2275 {
2276         assert(arch_register_type_is(reg, ignore));
2277         assert(pmap_contains(abi->regs, (void *) reg));
2278         return pmap_get(abi->regs, (void *) reg);
2279 }
2280
2281 /**
2282  * Returns non-zero if the ABI has omitted the frame pointer in
2283  * the current graph.
2284  */
2285 int be_abi_omit_fp(const be_abi_irg_t *abi) {
2286         return abi->call->flags.bits.try_omit_fp;
2287 }