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

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