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