nsz Git - libfirm/blob - ir/be/beabi.c

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