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