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