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