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         assert(get_nodes_block(n1) == get_nodes_block(n2));
 965
 966         return heights_reachable_in_block(ir_heights, n1, n2);
 967 }
 968
 969 static int cmp_call_dependecy(const void *c1, const void *c2)
 970 {
 971         ir_node *n1 = *(ir_node **) c1;
 972         ir_node *n2 = *(ir_node **) c2;
 973
 974         /*
 975                 Classical qsort() comparison function behavior:
 976                 0  if both elements are equal
 977                 1  if second is "smaller" that first
 978                 -1 if first is "smaller" that second
 979         */
 980         if (dependent_on(n1, n2))
 981                 return -1;
 982
 983         if (dependent_on(n2, n1))
 984                 return 1;
 985
 986         return 0;
 987 }
 988
 989 /**
 990  * Walker: links all Call/alloc/Free nodes to the Block they are contained.
 991  */
 992 static void link_calls_in_block_walker(ir_node *irn, void *data)
 993 {
 994         ir_opcode code = get_irn_opcode(irn);
 995
 996         if (code == iro_Call ||
 997                 (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
 998                 (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
 999                 be_abi_irg_t *env = data;
1000                 ir_node *bl       = get_nodes_block(irn);
1001                 void *save        = get_irn_link(bl);
1002
1003                 if (code == iro_Call)
1004                         env->call->flags.bits.irg_is_leaf = 0;
1005
1006                 set_irn_link(irn, save);
1007                 set_irn_link(bl, irn);
1008         }
1009 }
1010
1011 /**
1012  * Block-walker:
1013  * Process all Call nodes inside a basic block.
1014  * Note that the link field of the block must contain a linked list of all
1015  * Call nodes inside the Block. We first order this list according to data dependency
1016  * and that connect the calls together.
1017  */
1018 static void process_calls_in_block(ir_node *bl, void *data)
1019 {
1020         be_abi_irg_t *env = data;
1021         ir_node *curr_sp  = env->init_sp;
1022         ir_node *irn;
1023         int n;
1024
1025         for(irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
1026                 obstack_ptr_grow(&env->obst, irn);
1027
1028         /* If there were call nodes in the block. */
1029         if(n > 0) {
1030                 ir_node *keep;
1031                 ir_node **nodes;
1032                 ir_node *copy = NULL;
1033                 int i;
1034
1035                 nodes = obstack_finish(&env->obst);
1036
1037                 /* order the call nodes according to data dependency */
1038                 qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependecy);
1039
1040                 for(i = n - 1; i >= 0; --i) {
1041                         ir_node *irn = nodes[i];
1042
1043                         DBG((env->dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1044                         switch(get_irn_opcode(irn)) {
1045                         case iro_Call:
1046                                 curr_sp = adjust_call(env, irn, curr_sp, copy);
1047                                 break;
1048                         case iro_Alloc:
1049                                 curr_sp = adjust_alloc(env, irn, curr_sp, &copy);
1050                                 break;
1051                         case iro_Free:
1052                                 curr_sp = adjust_free(env, irn, curr_sp);
1053                                 break;
1054                         default:
1055                                 break;
1056                         }
1057                 }
1058
1059                 obstack_free(&env->obst, nodes);
1060
1061                 /* Keep the last stack state in the block by tying it to Keep node */
1062                 nodes[0] = curr_sp;
1063                 keep     = be_new_Keep(env->isa->sp->reg_class, get_irn_irg(bl), bl, 1, nodes);
1064                 pmap_insert(env->keep_map, bl, keep);
1065         }
1066
1067         set_irn_link(bl, curr_sp);
1068 }  /* process_calls_in_block */
1069
1070 /**
1071  * Adjust all call nodes in the graph to the ABI conventions.
1072  */
1073 static void process_calls(be_abi_irg_t *env)
1074 {
1075         ir_graph *irg = env->birg->irg;
1076
1077         env->call->flags.bits.irg_is_leaf = 1;
1078         irg_walk_graph(irg, firm_clear_link, link_calls_in_block_walker, env);
1079
1080         ir_heights = heights_new(env->birg->irg);
1081         irg_block_walk_graph(irg, NULL, process_calls_in_block, env);
1082         heights_free(ir_heights);
1083 }
1084
1085 #if 0 /*
1086 static ir_node *setup_frame(be_abi_irg_t *env)
1087 {
1088         const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
1089         const arch_register_t *sp = isa->sp;
1090         const arch_register_t *bp = isa->bp;
1091         be_abi_call_flags_bits_t flags = env->call->flags.bits;
1092         ir_graph *irg      = env->birg->irg;
1093         ir_node *bl        = get_irg_start_block(irg);
1094         ir_node *no_mem    = get_irg_no_mem(irg);
1095         ir_node *old_frame = get_irg_frame(irg);
1096         ir_node *stack     = pmap_get(env->regs, (void *) sp);
1097         ir_node *frame     = pmap_get(env->regs, (void *) bp);
1098
1099         int stack_nr       = get_Proj_proj(stack);
1100
1101         if(flags.try_omit_fp) {
1102                 stack = be_new_IncSP(sp, irg, bl, stack, no_mem, BE_STACK_FRAME_SIZE_EXPAND);
1103                 frame = stack;
1104         }
1105
1106         else {
1107                 frame = be_new_Copy(bp->reg_class, irg, bl, stack);
1108
1109                 be_node_set_flags(frame, -1, arch_irn_flags_dont_spill);
1110                 if(!flags.fp_free) {
1111                         be_set_constr_single_reg(frame, -1, bp);
1112                         be_node_set_flags(frame, -1, arch_irn_flags_ignore);
1113                         arch_set_irn_register(env->birg->main_env->arch_env, frame, bp);
1114                 }
1115
1116                 stack = be_new_IncSP(sp, irg, bl, stack, frame, BE_STACK_FRAME_SIZE_EXPAND);
1117         }
1118
1119         be_node_set_flags(env->reg_params, -(stack_nr + 1), arch_irn_flags_ignore);
1120         env->init_sp = stack;
1121         set_irg_frame(irg, frame);
1122         edges_reroute(old_frame, frame, irg);
1123
1124         return frame;
1125 }
1126
1127 static void clearup_frame(be_abi_irg_t *env, ir_node *ret, pmap *reg_map, struct obstack *obst)
1128 {
1129         const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
1130         const arch_register_t *sp = isa->sp;
1131         const arch_register_t *bp = isa->bp;
1132         ir_graph *irg      = env->birg->irg;
1133         ir_node *ret_mem   = get_Return_mem(ret);
1134         ir_node *frame     = get_irg_frame(irg);
1135         ir_node *bl        = get_nodes_block(ret);
1136         ir_node *stack     = get_irn_link(bl);
1137
1138         pmap_entry *ent;
1139
1140         if(env->call->flags.bits.try_omit_fp) {
1141                 stack = be_new_IncSP(sp, irg, bl, stack, ret_mem, -BE_STACK_FRAME_SIZE_SHRINK);
1142         }
1143
1144         else {
1145                 stack = be_new_SetSP(sp, irg, bl, stack, frame, ret_mem);
1146                 be_set_constr_single_reg(stack, -1, sp);
1147                 be_node_set_flags(stack, -1, arch_irn_flags_ignore);
1148         }
1149
1150         pmap_foreach(env->regs, ent) {
1151                 const arch_register_t *reg = ent->key;
1152                 ir_node *irn               = ent->value;
1153
1154                 if(reg == sp)
1155                         obstack_ptr_grow(&env->obst, stack);
1156                 else if(reg == bp)
1157                         obstack_ptr_grow(&env->obst, frame);
1158                 else if(arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1159                         obstack_ptr_grow(obst, irn);
1160         }
1161 }
1162 */
1163 #endif
1164
1165 /**
1166  * Computes the stack argument layout type.
1167  * Changes a possibly allocated value param type by moving
1168  * entities to the stack layout type.
1169  *
1170  * @param env          the ABI environment
1171  * @param call         the current call ABI
1172  * @param method_type  the method type
1173  * @param param_map    an array mapping method arguments to the stack layout type
1174  *
1175  * @return the stack argument layout type
1176  */
1177 static ir_type *compute_arg_type(be_abi_irg_t *env, be_abi_call_t *call, ir_type *method_type, ir_entity ***param_map)
1178 {
1179         int dir  = env->call->flags.bits.left_to_right ? 1 : -1;
1180         int inc  = env->birg->main_env->arch_env->isa->stack_dir * dir;
1181         int n    = get_method_n_params(method_type);
1182         int curr = inc > 0 ? 0 : n - 1;
1183         int ofs  = 0;
1184
1185         char buf[128];
1186         ir_type *res;
1187         int i;
1188         ir_type *val_param_tp = get_method_value_param_type(method_type);
1189         ident *id = get_entity_ident(get_irg_entity(env->birg->irg));
1190         ir_entity **map;
1191
1192         *param_map = map = obstack_alloc(&env->obst, n * sizeof(ir_entity *));
1193         res = new_type_struct(mangle_u(id, new_id_from_chars("arg_type", 8)));
1194         for (i = 0; i < n; ++i, curr += inc) {
1195                 ir_type *param_type    = get_method_param_type(method_type, curr);
1196                 be_abi_call_arg_t *arg = get_call_arg(call, 0, curr);
1197
1198                 map[i] = NULL;
1199                 if (arg->on_stack) {
1200                         if (val_param_tp) {
1201                                 /* the entity was already created, move it to the param type */
1202                                 arg->stack_ent = get_method_value_param_ent(method_type, i);
1203                                 remove_struct_member(val_param_tp, arg->stack_ent);
1204                                 set_entity_owner(arg->stack_ent, res);
1205                                 add_struct_member(res, arg->stack_ent);
1206                                 /* must be automatic to set a fixed layout */
1207                                 set_entity_allocation(arg->stack_ent, allocation_automatic);
1208                         }
1209                         else {
1210                                 snprintf(buf, sizeof(buf), "param_%d", i);
1211                                 arg->stack_ent = new_entity(res, new_id_from_str(buf), param_type);
1212                         }
1213                         ofs += arg->space_before;
1214                         ofs = round_up2(ofs, arg->alignment);
1215                         set_entity_offset(arg->stack_ent, ofs);
1216                         ofs += arg->space_after;
1217                         ofs += get_type_size_bytes(param_type);
1218                         map[i] = arg->stack_ent;
1219                 }
1220         }
1221         set_type_size_bytes(res, ofs);
1222         set_type_state(res, layout_fixed);
1223         return res;
1224 }
1225
1226 #if 0
1227 static void create_register_perms(const arch_isa_t *isa, ir_graph *irg, ir_node *bl, pmap *regs)
1228 {
1229         int i, j, n;
1230         struct obstack obst;
1231
1232         obstack_init(&obst);
1233
1234         /* Create a Perm after the RegParams node to delimit it. */
1235         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
1236                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
1237                 ir_node *perm;
1238                 ir_node **in;
1239                 int n_regs;
1240
1241                 for(n_regs = 0, j = 0; j < cls->n_regs; ++j) {
1242                         const arch_register_t *reg = &cls->regs[j];
1243                         ir_node *irn = pmap_get(regs, (void *) reg);
1244
1245                         if(irn && !arch_register_type_is(reg, ignore)) {
1246                                 n_regs++;
1247                                 obstack_ptr_grow(&obst, irn);
1248                                 set_irn_link(irn, (void *) reg);
1249                         }
1250                 }
1251
1252                 obstack_ptr_grow(&obst, NULL);
1253                 in = obstack_finish(&obst);
1254                 if(n_regs > 0) {
1255                         perm = be_new_Perm(cls, irg, bl, n_regs, in);
1256                         for(j = 0; j < n_regs; ++j) {
1257                                 ir_node *arg = in[j];
1258                                 arch_register_t *reg = get_irn_link(arg);
1259                                 pmap_insert(regs, reg, arg);
1260                                 be_set_constr_single_reg(perm, BE_OUT_POS(j), reg);
1261                         }
1262                 }
1263                 obstack_free(&obst, in);
1264         }
1265
1266         obstack_free(&obst, NULL);
1267 }
1268 #endif
1269
1270 typedef struct {
1271         const arch_register_t *reg;
1272         ir_node *irn;
1273 } reg_node_map_t;
1274
1275 static int cmp_regs(const void *a, const void *b)
1276 {
1277         const reg_node_map_t *p = a;
1278         const reg_node_map_t *q = b;
1279
1280         if(p->reg->reg_class == q->reg->reg_class)
1281                 return p->reg->index - q->reg->index;
1282         else
1283                 return p->reg->reg_class - q->reg->reg_class;
1284 }
1285
1286 static reg_node_map_t *reg_map_to_arr(struct obstack *obst, pmap *reg_map)
1287 {
1288         pmap_entry *ent;
1289         int n = pmap_count(reg_map);
1290         int i = 0;
1291         reg_node_map_t *res = obstack_alloc(obst, n * sizeof(res[0]));
1292
1293         pmap_foreach(reg_map, ent) {
1294                 res[i].reg = ent->key;
1295                 res[i].irn = ent->value;
1296                 i++;
1297         }
1298
1299         qsort(res, n, sizeof(res[0]), cmp_regs);
1300         return res;
1301 }
1302
1303 /**
1304  * Creates a barrier.
1305  */
1306 static ir_node *create_barrier(be_abi_irg_t *env, ir_node *bl, ir_node **mem, pmap *regs, int in_req)
1307 {
1308         ir_graph *irg = env->birg->irg;
1309         int n_regs    = pmap_count(regs);
1310         int n;
1311         ir_node *irn;
1312         ir_node **in;
1313         reg_node_map_t *rm;
1314
1315         rm = reg_map_to_arr(&env->obst, regs);
1316
1317         for(n = 0; n < n_regs; ++n)
1318                 obstack_ptr_grow(&env->obst, rm[n].irn);
1319
1320         if(mem) {
1321                 obstack_ptr_grow(&env->obst, *mem);
1322                 n++;
1323         }
1324
1325         in = (ir_node **) obstack_finish(&env->obst);
1326         irn = be_new_Barrier(irg, bl, n, in);
1327         obstack_free(&env->obst, in);
1328
1329         for(n = 0; n < n_regs; ++n) {
1330                 const arch_register_t *reg = rm[n].reg;
1331                 int flags                  = 0;
1332                 int pos                    = BE_OUT_POS(n);
1333                 ir_node *proj;
1334
1335                 proj = new_r_Proj(irg, bl, irn, get_irn_mode(rm[n].irn), n);
1336                 be_node_set_reg_class(irn, n, reg->reg_class);
1337                 if(in_req)
1338                         be_set_constr_single_reg(irn, n, reg);
1339                 be_set_constr_single_reg(irn, pos, reg);
1340                 be_node_set_reg_class(irn, pos, reg->reg_class);
1341                 arch_set_irn_register(env->birg->main_env->arch_env, proj, reg);
1342
1343                 /* if the proj projects a ignore register or a node which is set to ignore, propagate this property. */
1344                 if(arch_register_type_is(reg, ignore) || arch_irn_is(env->birg->main_env->arch_env, in[n], ignore))
1345                         flags |= arch_irn_flags_ignore;
1346
1347                 if(arch_irn_is(env->birg->main_env->arch_env, in[n], modify_sp))
1348                         flags |= arch_irn_flags_modify_sp;
1349
1350                 be_node_set_flags(irn, pos, flags);
1351
1352                 pmap_insert(regs, (void *) reg, proj);
1353         }
1354
1355         if(mem) {
1356                 *mem = new_r_Proj(irg, bl, irn, mode_M, n);
1357         }
1358
1359         obstack_free(&env->obst, rm);
1360         return irn;
1361 }
1362
1363 /**
1364  * Creates a be_Return for a Return node.
1365  *
1366  * @param @env    the abi environment
1367  * @param irn     the Return node or NULL if there was none
1368  * @param bl      the block where the be_Retun should be placed
1369  * @param mem     the current memory
1370  * @param n_res   number of return results
1371  */
1372 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl, ir_node *mem, int n_res) {
1373         be_abi_call_t *call = env->call;
1374         const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
1375
1376         pmap *reg_map  = pmap_create();
1377         ir_node *keep  = pmap_get(env->keep_map, bl);
1378         int in_max;
1379         ir_node *ret;
1380         int i, n;
1381         ir_node **in;
1382         ir_node *stack;
1383         const arch_register_t **regs;
1384         pmap_entry *ent ;
1385
1386         /*
1387                 get the valid stack node in this block.
1388                 If we had a call in that block there is a Keep constructed by process_calls()
1389                 which points to the last stack modification in that block. we'll use
1390                 it then. Else we use the stack from the start block and let
1391                 the ssa construction fix the usage.
1392         */
1393         stack = be_abi_reg_map_get(env->regs, isa->sp);
1394         if (keep) {
1395                 ir_node *bad = new_r_Bad(env->birg->irg);
1396                 stack = get_irn_n(keep, 0);
1397                 set_nodes_block(keep, bad);
1398                 set_irn_n(keep, 0, bad);
1399                 // exchange(keep, new_r_Bad(env->birg->irg));
1400         }
1401
1402         /* Insert results for Return into the register map. */
1403         for(i = 0; i < n_res; ++i) {
1404                 ir_node *res           = get_Return_res(irn, i);
1405                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1406                 assert(arg->in_reg && "return value must be passed in register");
1407                 pmap_insert(reg_map, (void *) arg->reg, res);
1408         }
1409
1410         /* Add uses of the callee save registers. */
1411         pmap_foreach(env->regs, ent) {
1412                 const arch_register_t *reg = ent->key;
1413                 if(arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1414                         pmap_insert(reg_map, ent->key, ent->value);
1415         }
1416
1417         be_abi_reg_map_set(reg_map, isa->sp, stack);
1418
1419         /* Make the Epilogue node and call the arch's epilogue maker. */
1420         create_barrier(env, bl, &mem, reg_map, 1);
1421         call->cb->epilogue(env->cb, bl, &mem, reg_map);
1422
1423         /*
1424                 Maximum size of the in array for Return nodes is
1425                 return args + callee save/ignore registers + memory + stack pointer
1426         */
1427         in_max = pmap_count(reg_map) + n_res + 2;
1428
1429         in   = obstack_alloc(&env->obst, in_max * sizeof(in[0]));
1430         regs = obstack_alloc(&env->obst, in_max * sizeof(regs[0]));
1431
1432         in[0]   = mem;
1433         in[1]   = be_abi_reg_map_get(reg_map, isa->sp);
1434         regs[0] = NULL;
1435         regs[1] = isa->sp;
1436         n       = 2;
1437
1438         /* clear SP entry, since it has already been grown. */
1439         pmap_insert(reg_map, (void *) isa->sp, NULL);
1440         for(i = 0; i < n_res; ++i) {
1441                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1442
1443                 in[n]     = be_abi_reg_map_get(reg_map, arg->reg);
1444                 regs[n++] = arg->reg;
1445
1446                 /* Clear the map entry to mark the register as processed. */
1447                 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1448         }
1449
1450         /* grow the rest of the stuff. */
1451         pmap_foreach(reg_map, ent) {
1452                 if(ent->value) {
1453                         in[n]     = ent->value;
1454                         regs[n++] = ent->key;
1455                 }
1456         }
1457
1458         /* The in array for the new back end return is now ready. */
1459         ret = be_new_Return(irn ? get_irn_dbg_info(irn) : NULL, env->birg->irg, bl, n_res, n, in);
1460
1461         /* Set the register classes of the return's parameter accordingly. */
1462         for(i = 0; i < n; ++i)
1463                 if(regs[i])
1464                         be_node_set_reg_class(ret, i, regs[i]->reg_class);
1465
1466         /* Free the space of the Epilog's in array and the register <-> proj map. */
1467         obstack_free(&env->obst, in);
1468         pmap_destroy(reg_map);
1469
1470         return ret;
1471 }
1472
1473 typedef struct lower_frame_sels_env_t {
1474         be_abi_irg_t *env;
1475         ir_entity    *value_param_list;  /**< the list of all value param entities */
1476 } lower_frame_sels_env_t;
1477
1478 /**
1479  * Walker: Replaces Sels of frame type and
1480  * value param type entities by FrameAddress.
1481  */
1482 static void lower_frame_sels_walker(ir_node *irn, void *data)
1483 {
1484         lower_frame_sels_env_t *ctx = data;
1485
1486         if (is_Sel(irn)) {
1487                 ir_graph *irg        = current_ir_graph;
1488                 ir_node  *frame      = get_irg_frame(irg);
1489                 ir_node  *param_base = get_irg_value_param_base(irg);
1490                 ir_node  *ptr        = get_Sel_ptr(irn);
1491
1492                 if (ptr == frame || ptr == param_base) {
1493                         be_abi_irg_t *env = ctx->env;
1494                         ir_entity    *ent = get_Sel_entity(irn);
1495                         ir_node      *bl  = get_nodes_block(irn);
1496                         ir_node      *nw;
1497
1498                         nw = be_new_FrameAddr(env->isa->sp->reg_class, irg, bl, frame, ent);
1499                         exchange(irn, nw);
1500
1501                         /* check, if it's a param sel and if have not seen this entity immediatly before */
1502                         if (ptr == param_base && ctx->value_param_list != ent) {
1503                                 set_entity_link(ent, ctx->value_param_list);
1504                                 ctx->value_param_list = ent;
1505                         }
1506                 }
1507         }
1508 }
1509
1510 /**
1511  * Check if a value parameter is transmitted as a register.
1512  * This might happen if the address of an parameter is taken which is
1513  * transmitted in registers.
1514  *
1515  * Note that on some architectures this case must be handled specially
1516  * because the place of the backing store is determined by their ABI.
1517  *
1518  * In the default case we move the entity to the frame type and create
1519  * a backing store into the first block.
1520  */
1521 static void fix_address_of_parameter_access(be_abi_irg_t *env, ir_entity *value_param_list) {
1522         be_abi_call_t *call = env->call;
1523         ir_graph *irg       = env->birg->irg;
1524         ir_entity *ent, *next_ent, *new_list;
1525         ir_type *frame_tp;
1526         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1527
1528         new_list = NULL;
1529         for (ent = value_param_list; ent; ent = next_ent) {
1530                 int i = get_struct_member_index(get_entity_owner(ent), ent);
1531                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1532
1533                 next_ent = get_entity_link(ent);
1534                 if (arg->in_reg) {
1535                         DBG((dbg, LEVEL_2, "\targ #%d need backing store\n", i));
1536                         set_entity_link(ent, new_list);
1537                         new_list = ent;
1538                 }
1539         }
1540         if (new_list) {
1541                 /* ok, change the graph */
1542                 ir_node *start_bl = get_irg_start_block(irg);
1543                 ir_node *first_bl = NULL;
1544                 ir_node *frame, *imem, *nmem, *store, *mem, *args, *args_bl;
1545                 const ir_edge_t *edge;
1546                 optimization_state_t state;
1547                 int offset;
1548
1549                 foreach_block_succ(start_bl, edge) {
1550                         ir_node *succ = get_edge_src_irn(edge);
1551                         if (start_bl != succ) {
1552                                 first_bl = succ;
1553                                 break;
1554                         }
1555                 }
1556                 assert(first_bl);
1557                 /* we had already removed critical edges, so the following
1558                    assertion should be always true. */
1559                 assert(get_Block_n_cfgpreds(first_bl) == 1);
1560
1561                 /* now create backing stores */
1562                 frame = get_irg_frame(irg);
1563                 imem = get_irg_initial_mem(irg);
1564
1565                 save_optimization_state(&state);
1566                 set_optimize(0);
1567                 nmem = new_r_Proj(irg, first_bl, get_irg_start(irg), mode_M, pn_Start_M);
1568                 restore_optimization_state(&state);
1569
1570                 /* reroute all edges to the new memory source */
1571                 edges_reroute(imem, nmem, irg);
1572
1573                 store   = NULL;
1574                 mem     = imem;
1575                 args    = get_irg_args(irg);
1576                 args_bl = get_nodes_block(args);
1577                 for (ent = new_list; ent; ent = get_entity_link(ent)) {
1578                         int     i     = get_struct_member_index(get_entity_owner(ent), ent);
1579                         ir_type *tp   = get_entity_type(ent);
1580                         ir_mode *mode = get_type_mode(tp);
1581                         ir_node *addr;
1582
1583                         /* address for the backing store */
1584                         addr = be_new_FrameAddr(env->isa->sp->reg_class, irg, first_bl, frame, ent);
1585
1586                         if (store)
1587                                 mem = new_r_Proj(irg, first_bl, store, mode_M, pn_Store_M);
1588
1589                         /* the backing store itself */
1590                         store = new_r_Store(irg, first_bl, mem, addr,
1591                                             new_r_Proj(irg, args_bl, args, mode, i));
1592                 }
1593                 /* the new memory Proj gets the last Proj from store */
1594                 set_Proj_pred(nmem, store);
1595                 set_Proj_proj(nmem, pn_Store_M);
1596
1597                 /* move all entities to the frame type */
1598                 frame_tp = get_irg_frame_type(irg);
1599                 offset   = get_type_size_bytes(frame_tp);
1600                 for (ent = new_list; ent; ent = get_entity_link(ent)) {
1601                         ir_type *tp = get_entity_type(ent);
1602                         int align = get_type_alignment_bytes(tp);
1603
1604                         offset += align - 1;
1605                         offset &= -align;
1606                         set_entity_owner(ent, frame_tp);
1607                         add_class_member(frame_tp, ent);
1608                         /* must be automatic to set a fixed layout */
1609                         set_entity_allocation(ent, allocation_automatic);
1610                         set_entity_offset(ent, offset);
1611                         offset += get_type_size_bytes(tp);
1612                 }
1613                 set_type_size_bytes(frame_tp, offset);
1614         }
1615 }
1616
1617 /**
1618  * The start block has no jump, instead it has an initial exec Proj.
1619  * The backend wants to handle all blocks the same way, so we replace
1620  * the out cfg edge with a real jump.
1621  */
1622 static void fix_start_block(ir_node *block, void *env) {
1623         int      *done = env;
1624         int      i;
1625         ir_node  *start_block;
1626         ir_graph *irg;
1627
1628         /* we processed the start block, return */
1629         if (*done)
1630                 return;
1631
1632         irg         = get_irn_irg(block);
1633         start_block = get_irg_start_block(irg);
1634
1635         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
1636                 ir_node *pred       = get_Block_cfgpred(block, i);
1637                 ir_node *pred_block = get_nodes_block(pred);
1638
1639                 /* ok, we are in the block, having start as cfg predecessor */
1640                 if (pred_block == start_block) {
1641                         ir_node *jump = new_r_Jmp(irg, pred_block);
1642                         set_Block_cfgpred(block, i, jump);
1643                         *done = 1;
1644                 }
1645         }
1646 }
1647
1648 /**
1649  * Modify the irg itself and the frame type.
1650  */
1651 static void modify_irg(be_abi_irg_t *env)
1652 {
1653         be_abi_call_t *call       = env->call;
1654         const arch_isa_t *isa     = env->birg->main_env->arch_env->isa;
1655         const arch_register_t *sp = arch_isa_sp(isa);
1656         ir_graph *irg             = env->birg->irg;
1657         ir_node *bl               = get_irg_start_block(irg);
1658         ir_node *end              = get_irg_end_block(irg);
1659         ir_node *mem              = get_irg_initial_mem(irg);
1660         ir_type *method_type      = get_entity_type(get_irg_entity(irg));
1661         pset *dont_save           = pset_new_ptr(8);
1662
1663         int n_params;
1664         int i, j, n, temp;
1665
1666         reg_node_map_t *rm;
1667         const arch_register_t *fp_reg;
1668         ir_node *frame_pointer;
1669         ir_node *barrier;
1670         ir_node *reg_params_bl;
1671         ir_node **args;
1672         ir_node *arg_tuple;
1673         ir_node *value_param_base;
1674         const ir_edge_t *edge;
1675         ir_type *arg_type, *bet_type;
1676         lower_frame_sels_env_t ctx;
1677         ir_entity **param_map;
1678
1679         bitset_t *used_proj_nr;
1680         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1681
1682         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1683
1684         /* Convert the Sel nodes in the irg to frame load/store/addr nodes. */
1685         ctx.env              = env;
1686         ctx.value_param_list = NULL;
1687         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1688
1689         /* value_param_base anchor is not needed anymore now */
1690         value_param_base = get_irg_value_param_base(irg);
1691         be_kill_node(value_param_base);
1692         set_irg_value_param_base(irg, new_r_Bad(irg));
1693
1694         env->frame = obstack_alloc(&env->obst, sizeof(env->frame[0]));
1695         env->regs  = pmap_create();
1696
1697         used_proj_nr = bitset_alloca(1024);
1698         n_params     = get_method_n_params(method_type);
1699         args         = obstack_alloc(&env->obst, n_params * sizeof(args[0]));
1700         memset(args, 0, n_params * sizeof(args[0]));
1701
1702         /* Check if a value parameter is transmitted as a register.
1703          * This might happen if the address of an parameter is taken which is
1704          * transmitted in registers.
1705          *
1706          * Note that on some architectures this case must be handled specially
1707          * because the place of the backing store is determined by their ABI.
1708          *
1709          * In the default case we move the entity to the frame type and create
1710          * a backing store into the first block.
1711          */
1712         fix_address_of_parameter_access(env, ctx.value_param_list);
1713
1714         /* Fill the argument vector */
1715         arg_tuple = get_irg_args(irg);
1716         foreach_out_edge(arg_tuple, edge) {
1717                 ir_node *irn = get_edge_src_irn(edge);
1718                 int nr       = get_Proj_proj(irn);
1719                 args[nr]     = irn;
1720                 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1721         }
1722
1723         arg_type = compute_arg_type(env, call, method_type, &param_map);
1724         bet_type = call->cb->get_between_type(env->cb);
1725         stack_frame_init(env->frame, arg_type, bet_type, get_irg_frame_type(irg), isa->stack_dir, param_map);
1726
1727         /* Count the register params and add them to the number of Projs for the RegParams node */
1728         for(i = 0; i < n_params; ++i) {
1729                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1730                 if(arg->in_reg && args[i]) {
1731                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1732                         assert(i == get_Proj_proj(args[i]));
1733
1734                         /* For now, associate the register with the old Proj from Start representing that argument. */
1735                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1736                         bitset_set(used_proj_nr, i);
1737                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1738                 }
1739         }
1740
1741         /* Collect all callee-save registers */
1742         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
1743                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
1744                 for(j = 0; j < cls->n_regs; ++j) {
1745                         const arch_register_t *reg = &cls->regs[j];
1746                         if(arch_register_type_is(reg, callee_save))
1747                                 pmap_insert(env->regs, (void *) reg, NULL);
1748                 }
1749         }
1750
1751         pmap_insert(env->regs, (void *) sp, NULL);
1752         pmap_insert(env->regs, (void *) isa->bp, NULL);
1753         reg_params_bl   = get_irg_start_block(irg);
1754         env->reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(env->regs));
1755         add_irn_dep(env->reg_params, get_irg_start(irg));
1756
1757         /*
1758          * make proj nodes for the callee save registers.
1759          * memorize them, since Return nodes get those as inputs.
1760          *
1761          * Note, that if a register corresponds to an argument, the regs map contains
1762          * the old Proj from start for that argument.
1763          */
1764
1765         rm = reg_map_to_arr(&env->obst, env->regs);
1766         for(i = 0, n = pmap_count(env->regs); i < n; ++i) {
1767                 arch_register_t *reg = (void *) rm[i].reg;
1768                 ir_mode *mode        = reg->reg_class->mode;
1769                 long nr              = i;
1770                 int pos              = BE_OUT_POS((int) nr);
1771                 int flags            = 0;
1772
1773                 ir_node *proj;
1774
1775                 assert(nr >= 0);
1776                 bitset_set(used_proj_nr, nr);
1777                 proj = new_r_Proj(irg, reg_params_bl, env->reg_params, mode, nr);
1778                 pmap_insert(env->regs, (void *) reg, proj);
1779                 be_set_constr_single_reg(env->reg_params, pos, reg);
1780                 arch_set_irn_register(env->birg->main_env->arch_env, proj, reg);
1781
1782                 /*
1783                  * If the register is an ignore register,
1784                  * The Proj for that register shall also be ignored during register allocation.
1785                  */
1786                 if(arch_register_type_is(reg, ignore))
1787                         flags |= arch_irn_flags_ignore;
1788
1789                 if(reg == sp)
1790                         flags |= arch_irn_flags_modify_sp;
1791
1792                 be_node_set_flags(env->reg_params, pos, flags);
1793
1794                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1795         }
1796         obstack_free(&env->obst, rm);
1797
1798         /* Generate the Prologue */
1799         fp_reg  = call->cb->prologue(env->cb, &mem, env->regs);
1800
1801         /* do the stack allocation BEFORE the barrier, or spill code
1802            might be added before it */
1803         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1804         env->init_sp = be_new_IncSP(sp, irg, bl, env->init_sp, BE_STACK_FRAME_SIZE_EXPAND);
1805         be_abi_reg_map_set(env->regs, sp, env->init_sp);
1806
1807         env->start_barrier = barrier = create_barrier(env, bl, &mem, env->regs, 0);
1808
1809         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1810         arch_set_irn_register(env->birg->main_env->arch_env, env->init_sp, sp);
1811
1812         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1813         set_irg_frame(irg, frame_pointer);
1814         pset_insert_ptr(env->ignore_regs, fp_reg);
1815
1816         set_irg_initial_mem(irg, mem);
1817
1818         /* Now, introduce stack param nodes for all parameters passed on the stack */
1819         for(i = 0; i < n_params; ++i) {
1820                 ir_node *arg_proj = args[i];
1821                 ir_node *repl     = NULL;
1822
1823                 if(arg_proj != NULL) {
1824                         be_abi_call_arg_t *arg;
1825                         ir_type *param_type;
1826                         int nr = get_Proj_proj(arg_proj);
1827
1828                         nr         = MIN(nr, n_params);
1829                         arg        = get_call_arg(call, 0, nr);
1830                         param_type = get_method_param_type(method_type, nr);
1831
1832                         if(arg->in_reg) {
1833                                 repl = pmap_get(env->regs, (void *) arg->reg);
1834                         }
1835
1836                         else if(arg->on_stack) {
1837                                 /* For atomic parameters which are actually used, we create a StackParam node. */
1838                                 if(is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1839                                         ir_mode *mode                    = get_type_mode(param_type);
1840                                         const arch_register_class_t *cls = arch_isa_get_reg_class_for_mode(isa, mode);
1841                                         repl = be_new_StackParam(cls, isa->bp->reg_class, irg, reg_params_bl, mode, frame_pointer, arg->stack_ent);
1842                                 }
1843
1844                                 /* The stack parameter is not primitive (it is a struct or array),
1845                                 we thus will create a node representing the parameter's address
1846                                 on the stack. */
1847                                 else {
1848                                         repl = be_new_FrameAddr(sp->reg_class, irg, reg_params_bl, frame_pointer, arg->stack_ent);
1849                                 }
1850                         }
1851
1852                         assert(repl != NULL);
1853                         exchange(args[i], repl);
1854                 }
1855         }
1856
1857         /* the arg proj is not needed anymore now */
1858         assert(get_irn_n_edges(arg_tuple) == 0);
1859         be_kill_node(arg_tuple);
1860         set_irg_args(irg, new_rd_Bad(irg));
1861
1862         /* All Return nodes hang on the End node, so look for them there. */
1863         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1864                 ir_node *irn = get_Block_cfgpred(end, i);
1865
1866                 if (is_Return(irn)) {
1867                         ir_node *ret = create_be_return(env, irn, get_nodes_block(irn), get_Return_mem(irn), get_Return_n_ress(irn));
1868                         exchange(irn, ret);
1869                 }
1870         }
1871         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return than,
1872            the code is dead and will never be executed. */
1873
1874         del_pset(dont_save);
1875         obstack_free(&env->obst, args);
1876
1877         /* handle start block here (place a jump in the block) */
1878         temp = 0;
1879         irg_block_walk_graph(irg, fix_start_block, NULL, &temp);
1880 }
1881
1882 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
1883 {
1884         be_abi_irg_t *env  = xmalloc(sizeof(env[0]));
1885         ir_node *old_frame = get_irg_frame(birg->irg);
1886         ir_graph *irg      = birg->irg;
1887
1888         pmap_entry *ent;
1889         ir_node *dummy;
1890         optimization_state_t state;
1891         unsigned *limited_bitset;
1892
1893         be_omit_fp = birg->main_env->options->omit_fp;
1894
1895         obstack_init(&env->obst);
1896
1897         env->isa           = birg->main_env->arch_env->isa;
1898         env->method_type   = get_entity_type(get_irg_entity(irg));
1899         env->call          = be_abi_call_new(env->isa->sp->reg_class);
1900         arch_isa_get_call_abi(env->isa, env->method_type, env->call);
1901
1902         env->ignore_regs      = pset_new_ptr_default();
1903         env->keep_map         = pmap_create();
1904         env->dce_survivor     = new_survive_dce();
1905         env->birg             = birg;
1906         env->stack_phis       = pset_new_ptr(16);
1907
1908         env->sp_req.type      = arch_register_req_type_limited;
1909         env->sp_req.cls       = arch_register_get_class(env->isa->sp);
1910         limited_bitset        = rbitset_obstack_alloc(&env->obst, env->sp_req.cls->n_regs);
1911         rbitset_set(limited_bitset, arch_register_get_index(env->isa->sp));
1912         env->sp_req.limited   = limited_bitset;
1913
1914         env->sp_cls_req.type  = arch_register_req_type_normal;
1915         env->sp_cls_req.cls   = arch_register_get_class(env->isa->sp);
1916
1917         /* Beware: later we replace this node by the real one, ensure it is not CSE'd
1918            to another Unknown or the stack pointer gets used */
1919         save_optimization_state(&state);
1920         set_optimize(0);
1921         env->init_sp = dummy  = new_r_Unknown(irg, env->isa->sp->reg_class->mode);
1922         restore_optimization_state(&state);
1923         FIRM_DBG_REGISTER(env->dbg, "firm.be.abi");
1924
1925         memcpy(&env->irn_handler, &abi_irn_handler, sizeof(abi_irn_handler));
1926         env->irn_ops.impl = &abi_irn_ops;
1927
1928         /* Lower all call nodes in the IRG. */
1929         process_calls(env);
1930
1931         /*
1932                 Beware: init backend abi call object after processing calls,
1933                 otherwise some information might be not yet available.
1934         */
1935         env->cb = env->call->cb->init(env->call, birg->main_env->arch_env, irg);
1936
1937         /* Process the IRG */
1938         modify_irg(env);
1939
1940         /* We don't need the keep map anymore. */
1941         pmap_destroy(env->keep_map);
1942
1943         /* reroute the stack origin of the calls to the true stack origin. */
1944         exchange(dummy, env->init_sp);
1945         exchange(old_frame, get_irg_frame(irg));
1946
1947         /* Make some important node pointers survive the dead node elimination. */
1948         survive_dce_register_irn(env->dce_survivor, &env->init_sp);
1949         pmap_foreach(env->regs, ent) {
1950                 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
1951         }
1952
1953         arch_env_push_irn_handler(env->birg->main_env->arch_env, &env->irn_handler);
1954
1955         env->call->cb->done(env->cb);
1956         env->cb = NULL;
1957         return env;
1958 }
1959
1960 void be_abi_free(be_abi_irg_t *env)
1961 {
1962         free_survive_dce(env->dce_survivor);
1963         del_pset(env->stack_phis);
1964         del_pset(env->ignore_regs);
1965         pmap_destroy(env->regs);
1966         obstack_free(&env->obst, NULL);
1967         arch_env_pop_irn_handler(env->birg->main_env->arch_env);
1968         free(env);
1969 }
1970
1971 void be_abi_put_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, bitset_t *bs)
1972 {
1973         arch_register_t *reg;
1974
1975         for(reg = pset_first(abi->ignore_regs); reg; reg = pset_next(abi->ignore_regs))
1976                 if(reg->reg_class == cls)
1977                         bitset_set(bs, reg->index);
1978 }
1979
1980 /* Returns the stack layout from a abi environment. */
1981 const be_stack_layout_t *be_abi_get_stack_layout(const be_abi_irg_t *abi) {
1982         return abi->frame;
1983 }
1984
1985 /*
1986
1987   _____ _        ____  _             _
1988  |  ___(_)_  __ / ___|| |_ __ _  ___| | __
1989  | |_  | \ \/ / \___ \| __/ _` |/ __| |/ /
1990  |  _| | |>  <   ___) | || (_| | (__|   <
1991  |_|   |_/_/\_\ |____/ \__\__,_|\___|_|\_\
1992
1993 */
1994
1995 struct fix_stack_walker_info {
1996         nodeset *nodes;
1997         const arch_env_t *aenv;
1998 };
1999
2000 /**
2001  * Walker. Collect all stack modifying nodes.
2002  */
2003 static void collect_stack_nodes_walker(ir_node *irn, void *data)
2004 {
2005         struct fix_stack_walker_info *info = data;
2006
2007         if (is_Block(irn))
2008                 return;
2009
2010         if (arch_irn_is(info->aenv, irn, modify_sp)) {
2011                 assert(get_irn_mode(irn) != mode_M && get_irn_mode(irn) != mode_T);
2012                 pset_insert_ptr(info->nodes, irn);
2013         }
2014 }
2015
2016 void be_abi_fix_stack_nodes(be_abi_irg_t *env, be_lv_t *lv)
2017 {
2018         pset *stack_nodes = pset_new_ptr(16);
2019         struct fix_stack_walker_info info;
2020         int collect_phis;
2021
2022         info.nodes = stack_nodes;
2023         info.aenv  = env->birg->main_env->arch_env;
2024
2025         be_assure_dom_front(env->birg);
2026
2027
2028         irg_walk_graph(env->birg->irg, collect_stack_nodes_walker, NULL, &info);
2029         pset_insert_ptr(stack_nodes, env->init_sp);
2030         collect_phis = 1;
2031         if (env->call->cb->collect_stack_phis)
2032                 collect_phis = env->call->cb->collect_stack_phis(env->cb);
2033         be_ssa_constr_set_phis(env->birg->dom_front, lv, stack_nodes, collect_phis ? env->stack_phis : NULL);
2034         del_pset(stack_nodes);
2035 }
2036
2037 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int bias)
2038 {
2039         const arch_env_t *arch_env = env->birg->main_env->arch_env;
2040         int omit_fp            = env->call->flags.bits.try_omit_fp;
2041         ir_node *irn;
2042
2043         sched_foreach(bl, irn) {
2044
2045                 /*
2046                    Check, if the node relates to an entity on the stack frame.
2047                    If so, set the true offset (including the bias) for that
2048                    node.
2049                  */
2050                 ir_entity *ent = arch_get_frame_entity(arch_env, irn);
2051                 if(ent) {
2052                         int offset = get_stack_entity_offset(env->frame, ent, bias);
2053                         arch_set_frame_offset(arch_env, irn, offset);
2054                         DBG((env->dbg, LEVEL_2, "%F has offset %d (including bias %d)\n", ent, offset, bias));
2055                 }
2056
2057                 /*
2058                    If the node modifies the stack pointer by a constant offset,
2059                    record that in the bias.
2060                  */
2061                 if(arch_irn_is(arch_env, irn, modify_sp)) {
2062                         int ofs = arch_get_sp_bias(arch_env, irn);
2063
2064                         if(be_is_IncSP(irn)) {
2065                                 if(ofs == BE_STACK_FRAME_SIZE_EXPAND) {
2066                                         ofs = get_type_size_bytes(get_irg_frame_type(env->birg->irg));
2067                                         be_set_IncSP_offset(irn, ofs);
2068                                 } else if(ofs == BE_STACK_FRAME_SIZE_SHRINK) {
2069                                         ofs = - get_type_size_bytes(get_irg_frame_type(env->birg->irg));
2070                                         be_set_IncSP_offset(irn, ofs);
2071                                 }
2072                         }
2073
2074                         if(omit_fp)
2075                                 bias += ofs;
2076                 }
2077         }
2078
2079         return bias;
2080 }
2081
2082 /**
2083  * A helper struct for the bias walker.
2084  */
2085 struct bias_walk {
2086         be_abi_irg_t *env;     /**< The ABI irg environment. */
2087         int start_block_bias;  /**< The bias at the end of the start block. */
2088         ir_node *start_block;  /**< The start block of the current graph. */
2089 };
2090
2091 /**
2092  * Block-Walker: fix all stack offsets
2093  */
2094 static void stack_bias_walker(ir_node *bl, void *data)
2095 {
2096         struct bias_walk *bw = data;
2097         if (bl != bw->start_block) {
2098                 process_stack_bias(bw->env, bl, bw->start_block_bias);
2099         }
2100 }
2101
2102 void be_abi_fix_stack_bias(be_abi_irg_t *env)
2103 {
2104         ir_graph *irg  = env->birg->irg;
2105         struct bias_walk bw;
2106
2107         stack_frame_compute_initial_offset(env->frame);
2108         // stack_layout_dump(stdout, env->frame);
2109
2110         /* Determine the stack bias at the end of the start block. */
2111         bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), 0);
2112
2113         /* fix the bias is all other blocks */
2114         bw.env = env;
2115         bw.start_block = get_irg_start_block(irg);
2116         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
2117 }
2118
2119 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2120 {
2121         assert(arch_register_type_is(reg, callee_save));
2122         assert(pmap_contains(abi->regs, (void *) reg));
2123         return pmap_get(abi->regs, (void *) reg);
2124 }
2125
2126 ir_node *be_abi_get_ignore_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2127 {
2128         assert(arch_register_type_is(reg, ignore));
2129         assert(pmap_contains(abi->regs, (void *) reg));
2130         return pmap_get(abi->regs, (void *) reg);
2131 }
2132
2133 ir_node *be_abi_get_start_barrier(be_abi_irg_t *abi)
2134 {
2135         return abi->start_barrier;
2136 }
2137
2138 /*
2139   _____ _____  _   _   _    _                 _ _
2140  |_   _|  __ \| \ | | | |  | |               | | |
2141    | | | |__) |  \| | | |__| | __ _ _ __   __| | | ___ _ __
2142    | | |  _  /| . ` | |  __  |/ _` | '_ \ / _` | |/ _ \ '__|
2143   _| |_| | \ \| |\  | | |  | | (_| | | | | (_| | |  __/ |
2144  |_____|_|  \_\_| \_| |_|  |_|\__,_|_| |_|\__,_|_|\___|_|
2145
2146   for Phi nodes which are created due to stack modifying nodes
2147   such as IncSP, AddSP and SetSP.
2148
2149   These Phis are always to be ignored by the reg alloc and are
2150   fixed on the SP register of the ISA.
2151 */
2152
2153 static const void *abi_get_irn_ops(const arch_irn_handler_t *handler, const ir_node *irn)
2154 {
2155         const be_abi_irg_t *abi = get_abi_from_handler(handler);
2156         const void *res = NULL;
2157
2158         if(is_Phi(irn) && pset_find_ptr(abi->stack_phis, (void *) irn))
2159                 res = &abi->irn_ops;
2160
2161         return res;
2162 }
2163
2164 static
2165 const arch_register_req_t *abi_get_irn_reg_req(const void *self,
2166                                                const ir_node *irn, int pos)
2167 {
2168         be_abi_irg_t *abi = get_abi_from_ops(self);
2169
2170         if(pos == BE_OUT_POS(0)) {
2171                 return &abi->sp_req;
2172         } else if(pos >= 0 && pos < get_irn_arity(irn)) {
2173                 return &abi->sp_cls_req;
2174         }
2175
2176         return arch_no_register_req;
2177 }
2178
2179 static void abi_set_irn_reg(const void *self, ir_node *irn, const arch_register_t *reg)
2180 {
2181 }
2182
2183 static const arch_register_t *abi_get_irn_reg(const void *self, const ir_node *irn)
2184 {
2185         const be_abi_irg_t *abi = get_abi_from_ops(self);
2186         return abi->isa->sp;
2187 }
2188
2189 static arch_irn_class_t abi_classify(const void *_self, const ir_node *irn)
2190 {
2191         return arch_irn_class_normal;
2192 }
2193
2194 static arch_irn_flags_t abi_get_flags(const void *_self, const ir_node *irn)
2195 {
2196         return arch_irn_flags_ignore | arch_irn_flags_modify_sp;
2197 }
2198
2199 static ir_entity *abi_get_frame_entity(const void *_self, const ir_node *irn)
2200 {
2201         return NULL;
2202 }
2203
2204 static void abi_set_frame_entity(const void *_self, ir_node *irn, ir_entity *ent)
2205 {
2206 }
2207
2208 static void abi_set_frame_offset(const void *_self, ir_node *irn, int bias)
2209 {
2210 }
2211
2212 static int abi_get_sp_bias(const void *self, const ir_node *irn)
2213 {
2214         return 0;
2215 }
2216
2217 static const arch_irn_ops_if_t abi_irn_ops = {
2218         abi_get_irn_reg_req,
2219         abi_set_irn_reg,
2220         abi_get_irn_reg,
2221         abi_classify,
2222         abi_get_flags,
2223         abi_get_frame_entity,
2224         abi_set_frame_entity,
2225         abi_set_frame_offset,
2226         abi_get_sp_bias,
2227         NULL,    /* get_inverse             */
2228         NULL,    /* get_op_estimated_cost   */
2229         NULL,    /* possible_memory_operand */
2230         NULL,    /* perform_memory_operand  */
2231 };
2232
2233 static const arch_irn_handler_t abi_irn_handler = {
2234         abi_get_irn_ops
2235 };
2236
2237 /**
2238  * Returns non-zero if the ABI has omitted the frame pointer in
2239  * the current graph.
2240  */
2241 int be_abi_omit_fp(const be_abi_irg_t *abi) {
2242         return abi->call->flags.bits.try_omit_fp;
2243 }