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