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