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