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

   1 /*
   2  * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Backend ABI implementation.
  23  * @author      Sebastian Hack, Michael Beck
  24  */
  25 #include "config.h"
  26
  27 #include "obst.h"
  28
  29 #include "irgopt.h"
  30
  31 #include "irgraph_t.h"
  32 #include "irnode_t.h"
  33 #include "ircons_t.h"
  34 #include "iredges_t.h"
  35 #include "irgmod.h"
  36 #include "irgwalk.h"
  37 #include "irprintf_t.h"
  38 #include "irgopt.h"
  39 #include "iropt_t.h"
  40 #include "irtools.h"
  41 #include "heights.h"
  42 #include "pdeq.h"
  43 #include "util.h"
  44 #include "raw_bitset.h"
  45 #include "error.h"
  46 #include "pset_new.h"
  47
  48 #include "be.h"
  49 #include "beabi.h"
  50 #include "bearch.h"
  51 #include "benode.h"
  52 #include "belive_t.h"
  53 #include "besched.h"
  54 #include "beirg.h"
  55 #include "bessaconstr.h"
  56 #include "bemodule.h"
  57 #include "betranshlp.h"
  58
  59 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  60
  61 typedef struct be_abi_call_arg_t {
  62         unsigned is_res   : 1;  /**< 1: the call argument is a return value. 0: it's a call parameter. */
  63         unsigned in_reg   : 1;  /**< 1: this argument is transmitted 1: in registers, 0: on stack. */
  64         unsigned callee   : 1;  /**< 1: someone called us. 0: We call another function */
  65
  66         int                    pos;
  67         const arch_register_t *reg;
  68         ir_entity             *stack_ent;
  69         ir_mode               *load_mode;
  70         unsigned               alignment;    /**< stack alignment */
  71         unsigned               space_before; /**< allocate space before */
  72         unsigned               space_after;  /**< allocate space after */
  73 } be_abi_call_arg_t;
  74
  75 struct be_abi_call_t {
  76         be_abi_call_flags_t          flags;  /**< Flags describing the ABI behavior on calls */
  77         int                          pop;    /**< number of bytes the stack frame is shrinked by the callee on return. */
  78         const be_abi_callbacks_t    *cb;
  79         ir_type                     *between_type;
  80         set                         *params;
  81         const arch_register_class_t *cls_addr; /**< register class of the call address */
  82 };
  83
  84 /**
  85  * The ABI information for the current graph.
  86  */
  87 struct be_abi_irg_t {
  88         be_abi_call_t        *call;         /**< The ABI call information. */
  89
  90         ir_node              *init_sp;      /**< The node representing the stack pointer
  91                                                  at the start of the function. */
  92
  93         pmap                 *regs;         /**< A map of all callee-save and ignore regs to
  94                                                  their Projs to the RegParams node. */
  95         pmap                 *keep_map;     /**< mapping blocks to keep nodes. */
  96
  97         ir_node              **calls;       /**< flexible array containing all be_Call nodes */
  98 };
  99
 100 static ir_heights_t *ir_heights;
 101
 102 /** Flag: if set, try to omit the frame pointer in all routines. */
 103 static int be_omit_fp = 1;
 104
 105 static ir_node *be_abi_reg_map_get(pmap *map, const arch_register_t *reg)
 106 {
 107         return pmap_get(ir_node, map, reg);
 108 }
 109
 110 static void be_abi_reg_map_set(pmap *map, const arch_register_t* reg,
 111                                ir_node *node)
 112 {
 113         pmap_insert(map, reg, node);
 114 }
 115
 116 /**
 117  * Check if the given register is callee save, ie. will be saved by the callee.
 118  */
 119 static bool arch_register_is_callee_save(
 120         const arch_env_t      *arch_env,
 121         const arch_register_t *reg)
 122 {
 123         if (arch_env->impl->register_saved_by)
 124                 return arch_env->impl->register_saved_by(reg, /*callee=*/1);
 125         return false;
 126 }
 127
 128 /**
 129  * Check if the given register is caller save, ie. must be saved by the caller.
 130  */
 131 static bool arch_register_is_caller_save(
 132         const arch_env_t      *arch_env,
 133         const arch_register_t *reg)
 134 {
 135         if (arch_env->impl->register_saved_by)
 136                 return arch_env->impl->register_saved_by(reg, /*callee=*/0);
 137         return false;
 138 }
 139
 140
 141
 142 /*
 143      _    ____ ___    ____      _ _ _                _
 144     / \  | __ )_ _|  / ___|__ _| | | |__   __ _  ___| | _____
 145    / _ \ |  _ \| |  | |   / _` | | | '_ \ / _` |/ __| |/ / __|
 146   / ___ \| |_) | |  | |__| (_| | | | |_) | (_| | (__|   <\__ \
 147  /_/   \_\____/___|  \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
 148
 149   These callbacks are used by the backend to set the parameters
 150   for a specific call type.
 151 */
 152
 153 /**
 154  * Set compare function: compares two ABI call object arguments.
 155  */
 156 static int cmp_call_arg(const void *a, const void *b, size_t n)
 157 {
 158         const be_abi_call_arg_t *p = (const be_abi_call_arg_t*)a;
 159         const be_abi_call_arg_t *q = (const be_abi_call_arg_t*)b;
 160         (void) n;
 161         return !(p->is_res == q->is_res && p->pos == q->pos && p->callee == q->callee);
 162 }
 163
 164 /**
 165  * Get  an ABI call object argument.
 166  *
 167  * @param call      the abi call
 168  * @param is_res    true for call results, false for call arguments
 169  * @param pos       position of the argument
 170  * @param callee    context type - if we are callee or caller
 171  */
 172 static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos, int callee)
 173 {
 174         be_abi_call_arg_t arg;
 175         unsigned hash;
 176
 177         memset(&arg, 0, sizeof(arg));
 178         arg.is_res = is_res;
 179         arg.pos    = pos;
 180         arg.callee = callee;
 181
 182         hash = is_res * 128 + pos;
 183
 184         return set_find(be_abi_call_arg_t, call->params, &arg, sizeof(arg), hash);
 185 }
 186
 187 /**
 188  * Set an ABI call object argument.
 189  */
 190 static void remember_call_arg(be_abi_call_arg_t *arg, be_abi_call_t *call, be_abi_context_t context)
 191 {
 192         unsigned hash = arg->is_res * 128 + arg->pos;
 193         if (context & ABI_CONTEXT_CALLEE) {
 194                 arg->callee = 1;
 195                 (void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
 196         }
 197         if (context & ABI_CONTEXT_CALLER) {
 198                 arg->callee = 0;
 199                 (void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
 200         }
 201 }
 202
 203 /* Set the flags for a call. */
 204 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
 205 {
 206         call->flags = flags;
 207         call->cb    = cb;
 208 }
 209
 210 /* Sets the number of bytes the stackframe is shrinked by the callee on return */
 211 void be_abi_call_set_pop(be_abi_call_t *call, int pop)
 212 {
 213         assert(pop >= 0);
 214         call->pop = pop;
 215 }
 216
 217 /* Set register class for call address */
 218 void be_abi_call_set_call_address_reg_class(be_abi_call_t *call, const arch_register_class_t *cls)
 219 {
 220         call->cls_addr = cls;
 221 }
 222
 223
 224 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos,
 225                              ir_mode *load_mode, unsigned alignment,
 226                              unsigned space_before, unsigned space_after,
 227                              be_abi_context_t context)
 228 {
 229         be_abi_call_arg_t arg;
 230         memset(&arg, 0, sizeof(arg));
 231         assert(alignment > 0 && "Alignment must be greater than 0");
 232         arg.load_mode    = load_mode;
 233         arg.alignment    = alignment;
 234         arg.space_before = space_before;
 235         arg.space_after  = space_after;
 236         arg.is_res       = 0;
 237         arg.pos          = arg_pos;
 238
 239         remember_call_arg(&arg, call, context);
 240 }
 241
 242 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
 243 {
 244         be_abi_call_arg_t arg;
 245         memset(&arg, 0, sizeof(arg));
 246
 247         arg.in_reg = 1;
 248         arg.reg    = reg;
 249         arg.is_res = 0;
 250         arg.pos    = arg_pos;
 251
 252         remember_call_arg(&arg, call, context);
 253 }
 254
 255 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
 256 {
 257         be_abi_call_arg_t arg;
 258         memset(&arg, 0, sizeof(arg));
 259
 260         arg.in_reg = 1;
 261         arg.reg    = reg;
 262         arg.is_res = 1;
 263         arg.pos    = arg_pos;
 264
 265         remember_call_arg(&arg, call, context);
 266 }
 267
 268 /* Get the flags of a ABI call object. */
 269 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
 270 {
 271         return call->flags;
 272 }
 273
 274 /**
 275  * Constructor for a new ABI call object.
 276  *
 277  * @param cls_addr  register class of the call address
 278  *
 279  * @return the new ABI call object
 280  */
 281 static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
 282 {
 283         be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
 284
 285         call->params            = new_set(cmp_call_arg, 16);
 286         call->cb                = NULL;
 287         call->cls_addr          = cls_addr;
 288         call->flags.try_omit_fp = be_omit_fp;
 289
 290         return call;
 291 }
 292
 293 /**
 294  * Destructor for an ABI call object.
 295  */
 296 static void be_abi_call_free(be_abi_call_t *call)
 297 {
 298         del_set(call->params);
 299         free(call);
 300 }
 301
 302 /**
 303  * Initializes the frame layout from parts
 304  *
 305  * @param frame     the stack layout that will be initialized
 306  * @param args      the stack argument layout type
 307  * @param between   the between layout type
 308  * @param locals    the method frame type
 309  *
 310  * @return the initialized stack layout
 311  */
 312 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
 313                                            ir_type *between, ir_type *locals)
 314 {
 315         frame->arg_type       = args;
 316         frame->between_type   = between;
 317         frame->frame_type     = locals;
 318         frame->initial_offset = 0;
 319         frame->initial_bias   = 0;
 320         frame->order[1]       = between;
 321
 322         /* typical decreasing stack: locals have the
 323          * lowest addresses, arguments the highest */
 324         frame->order[0] = locals;
 325         frame->order[2] = args;
 326         return frame;
 327 }
 328
 329 /*
 330    ____      _ _
 331   / ___|__ _| | |___
 332  | |   / _` | | / __|
 333  | |__| (_| | | \__ \
 334   \____\__,_|_|_|___/
 335
 336   Adjustment of the calls inside a graph.
 337
 338 */
 339
 340 /**
 341  * Transform a call node into a be_Call node.
 342  *
 343  * @param env The ABI environment for the current irg.
 344  * @param irn The call node.
 345  * @param curr_sp The stack pointer node to use.
 346  * @return The stack pointer after the call.
 347  */
 348 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
 349 {
 350         ir_graph *irg              = get_irn_irg(irn);
 351         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
 352         ir_type *call_tp           = get_Call_type(irn);
 353         ir_node *call_ptr          = get_Call_ptr(irn);
 354         size_t   n_params          = get_method_n_params(call_tp);
 355         ir_node *curr_mem          = get_Call_mem(irn);
 356         ir_node *bl                = get_nodes_block(irn);
 357         int stack_size             = 0;
 358         const arch_register_t *sp  = arch_env->sp;
 359         be_abi_call_t *call        = be_abi_call_new(sp->reg_class);
 360         ir_mode *mach_mode         = sp->reg_class->mode;
 361         int n_res                  = get_method_n_ress(call_tp);
 362
 363         ir_node *res_proj  = NULL;
 364         int n_reg_params   = 0;
 365         int n_stack_params = 0;
 366         int n_ins;
 367
 368         const arch_register_t **states = NEW_ARR_F(const arch_register_t*, 0);
 369         const arch_register_t **destroyed_regs = NEW_ARR_F(const arch_register_t*, 0);
 370         ir_node                *low_call;
 371         ir_node               **in;
 372         ir_node               **res_projs;
 373         int                     n_reg_results = 0;
 374         int                    *reg_param_idxs;
 375         int                    *stack_param_idx;
 376         int                     i, n;
 377         int                     throws_exception;
 378         size_t                  s;
 379         size_t                  p;
 380         dbg_info               *dbgi;
 381
 382         /* Let the isa fill out the abi description for that call node. */
 383         arch_env_get_call_abi(arch_env, call_tp, call);
 384
 385         /* Insert code to put the stack arguments on the stack. */
 386         assert((size_t)get_Call_n_params(irn) == n_params);
 387         stack_param_idx = ALLOCAN(int, n_params);
 388         for (p = 0; p < n_params; ++p) {
 389                 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
 390                 assert(arg);
 391                 if (!arg->in_reg) {
 392                         int arg_size = get_type_size_bytes(get_method_param_type(call_tp, p));
 393
 394                         stack_size += round_up2(arg->space_before, arg->alignment);
 395                         stack_size += round_up2(arg_size, arg->alignment);
 396                         stack_size += round_up2(arg->space_after, arg->alignment);
 397
 398                         stack_param_idx[n_stack_params++] = p;
 399                 }
 400         }
 401
 402         /* Collect all arguments which are passed in registers. */
 403         reg_param_idxs = ALLOCAN(int, n_params);
 404         for (p = 0; p < n_params; ++p) {
 405                 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
 406                 if (arg && arg->in_reg) {
 407                         reg_param_idxs[n_reg_params++] = p;
 408                 }
 409         }
 410
 411         /*
 412          * If the stack is decreasing and we do not want to store sequentially,
 413          * or someone else allocated the call frame
 414          * we allocate as much space on the stack all parameters need, by
 415          * moving the stack pointer along the stack's direction.
 416          *
 417          * Note: we also have to do this for stack_size == 0, because we may have
 418          * to adjust stack alignment for the call.
 419          */
 420         curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
 421
 422         dbgi = get_irn_dbg_info(irn);
 423         /* If there are some parameters which shall be passed on the stack. */
 424         if (n_stack_params > 0) {
 425                 int       curr_ofs = 0;
 426                 ir_node **in       = ALLOCAN(ir_node*, n_stack_params+1);
 427                 unsigned  n_in     = 0;
 428
 429                 curr_mem = get_Call_mem(irn);
 430                 in[n_in++] = curr_mem;
 431
 432                 for (i = 0; i < n_stack_params; ++i) {
 433                         int p                  = stack_param_idx[i];
 434                         be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
 435                         ir_node *param         = get_Call_param(irn, p);
 436                         ir_node *addr          = curr_sp;
 437                         ir_node *mem           = NULL;
 438                         ir_type *param_type    = get_method_param_type(call_tp, p);
 439                         int param_size         = get_type_size_bytes(param_type) + arg->space_after;
 440
 441                         /*
 442                          * If we wanted to build the arguments sequentially,
 443                          * the stack pointer for the next must be incremented,
 444                          * and the memory value propagated.
 445                          */
 446                         curr_ofs += arg->space_before;
 447                         curr_ofs =  round_up2(curr_ofs, arg->alignment);
 448
 449                         /* Make the expression to compute the argument's offset. */
 450                         if (curr_ofs > 0) {
 451                                 ir_mode *constmode = mach_mode;
 452                                 if (mode_is_reference(mach_mode)) {
 453                                         constmode = mode_Is;
 454                                 }
 455                                 addr = new_r_Const_long(irg, constmode, curr_ofs);
 456                                 addr = new_r_Add(bl, curr_sp, addr, mach_mode);
 457                         }
 458
 459                         /* Insert a store for primitive arguments. */
 460                         if (is_atomic_type(param_type)) {
 461                                 ir_node *nomem     = get_irg_no_mem(irg);
 462                                 ir_node *mem_input = nomem;
 463                                 ir_node *store     = new_rd_Store(dbgi, bl, mem_input, addr, param, cons_none);
 464                                 mem   = new_r_Proj(store, mode_M, pn_Store_M);
 465                         } else {
 466                                 /* Make a mem copy for compound arguments. */
 467                                 ir_node *copy;
 468
 469                                 assert(mode_is_reference(get_irn_mode(param)));
 470                                 copy = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type);
 471                                 mem = new_r_Proj(copy, mode_M, pn_CopyB_M);
 472                         }
 473
 474                         curr_ofs += param_size;
 475
 476                         in[n_in++] = mem;
 477                 }
 478
 479                 /* We need the sync only, if we didn't build the stores sequentially. */
 480                 if (n_stack_params >= 1) {
 481                         curr_mem = new_r_Sync(bl, n_in, in);
 482                 } else {
 483                         curr_mem = get_Call_mem(irn);
 484                 }
 485         }
 486
 487         /* Put caller save into the destroyed set and state registers in the states
 488          * set */
 489         for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
 490                 unsigned j;
 491                 const arch_register_class_t *cls = &arch_env->register_classes[i];
 492                 for (j = 0; j < cls->n_regs; ++j) {
 493                         const arch_register_t *reg = arch_register_for_index(cls, j);
 494
 495                         /* even if destroyed all is specified, neither SP nor FP are
 496                          * destroyed (else bad things will happen) */
 497                         if (reg == arch_env->sp || reg == arch_env->bp)
 498                                 continue;
 499
 500                         if (reg->type & arch_register_type_state) {
 501                                 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
 502                                 ARR_APP1(const arch_register_t*, states, reg);
 503                                 /* we're already in the destroyed set so no need for further
 504                                  * checking */
 505                                 continue;
 506                         }
 507                         if (arch_register_is_caller_save(arch_env, reg)) {
 508                                 if (!(reg->type & arch_register_type_ignore)) {
 509                                         ARR_APP1(const arch_register_t*, destroyed_regs, reg);
 510                                 }
 511                         }
 512                 }
 513         }
 514
 515         /* search the largest result proj number */
 516         res_projs = ALLOCANZ(ir_node*, n_res);
 517
 518         foreach_out_edge(irn, edge) {
 519                 ir_node *irn = get_edge_src_irn(edge);
 520
 521                 if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
 522                         continue;
 523
 524                 foreach_out_edge(irn, res_edge) {
 525                         int proj;
 526                         ir_node *res = get_edge_src_irn(res_edge);
 527
 528                         assert(is_Proj(res));
 529
 530                         proj = get_Proj_proj(res);
 531                         assert(proj < n_res);
 532                         assert(res_projs[proj] == NULL);
 533                         res_projs[proj] = res;
 534                 }
 535                 res_proj = irn;
 536                 break;
 537         }
 538
 539         /** TODO: this is not correct for cases where return values are passed
 540          * on the stack, but no known ABI does this currently...
 541          */
 542         n_reg_results = n_res;
 543
 544         n_ins = 0;
 545         in    = ALLOCAN(ir_node*, n_reg_params + ARR_LEN(states));
 546
 547         /* make the back end call node and set its register requirements. */
 548         for (i = 0; i < n_reg_params; ++i) {
 549                 in[n_ins++] = get_Call_param(irn, reg_param_idxs[i]);
 550         }
 551
 552         /* add state registers ins */
 553         for (s = 0; s < ARR_LEN(states); ++s) {
 554                 const arch_register_t       *reg = states[s];
 555                 const arch_register_class_t *cls = reg->reg_class;
 556                 ir_node *regnode = new_r_Unknown(irg, cls->mode);
 557                 in[n_ins++]      = regnode;
 558         }
 559         assert(n_ins == (int) (n_reg_params + ARR_LEN(states)));
 560
 561         /* ins collected, build the call */
 562         throws_exception = ir_throws_exception(irn);
 563         if (env->call->flags.call_has_imm && is_SymConst(call_ptr)) {
 564                 /* direct call */
 565                 low_call = be_new_Call(dbgi, irg, bl, curr_mem, sp->single_req, curr_sp,
 566                                        sp->single_req, curr_sp,
 567                                        n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
 568                                        n_ins, in, get_Call_type(irn));
 569                 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
 570         } else {
 571                 /* indirect call */
 572                 low_call = be_new_Call(dbgi, irg, bl, curr_mem, sp->single_req, curr_sp,
 573                                        call->cls_addr->class_req, call_ptr,
 574                                        n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
 575                                        n_ins, in, get_Call_type(irn));
 576         }
 577         ir_set_throws_exception(low_call, throws_exception);
 578         be_Call_set_pop(low_call, call->pop);
 579
 580         /* put the call into the list of all calls for later processing */
 581         ARR_APP1(ir_node *, env->calls, low_call);
 582
 583         /* create new stack pointer */
 584         curr_sp = new_r_Proj(low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
 585         be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
 586                         arch_register_req_type_ignore | arch_register_req_type_produces_sp);
 587         arch_set_irn_register(curr_sp, sp);
 588
 589         /* now handle results */
 590         for (i = 0; i < n_res; ++i) {
 591                 ir_node           *proj = res_projs[i];
 592                 be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);
 593
 594                 /* returns values on stack not supported yet */
 595                 assert(arg->in_reg);
 596
 597                 /*
 598                         shift the proj number to the right, since we will drop the
 599                         unspeakable Proj_T from the Call. Therefore, all real argument
 600                         Proj numbers must be increased by pn_be_Call_first_res
 601                 */
 602                 long pn = i + pn_be_Call_first_res;
 603
 604                 if (proj == NULL) {
 605                         ir_type *res_type = get_method_res_type(call_tp, i);
 606                         ir_mode *mode     = get_type_mode(res_type);
 607                         proj              = new_r_Proj(low_call, mode, pn);
 608                         res_projs[i]      = proj;
 609                 } else {
 610                         set_Proj_pred(proj, low_call);
 611                         set_Proj_proj(proj, pn);
 612                 }
 613
 614                 if (arg->in_reg) {
 615                         /* remove register from destroyed regs */
 616                         size_t j;
 617                         size_t n = ARR_LEN(destroyed_regs);
 618                         for (j = 0; j < n; ++j) {
 619                                 if (destroyed_regs[j] == arg->reg) {
 620                                         destroyed_regs[j] = destroyed_regs[n-1];
 621                                         ARR_SHRINKLEN(destroyed_regs,n-1);
 622                                         break;
 623                                 }
 624                         }
 625                 }
 626         }
 627
 628         DBG((dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
 629
 630         /* Set the register classes and constraints of the Call parameters. */
 631         for (i = 0; i < n_reg_params; ++i) {
 632                 int index = reg_param_idxs[i];
 633                 be_abi_call_arg_t *arg = get_call_arg(call, 0, index, 0);
 634                 assert(arg->reg != NULL);
 635
 636                 be_set_constr_single_reg_in(low_call, n_be_Call_first_arg + i,
 637                                             arg->reg, arch_register_req_type_none);
 638         }
 639
 640         /* Set the register constraints of the results. */
 641         for (i = 0; i < n_res; ++i) {
 642                 ir_node                 *proj = res_projs[i];
 643                 const be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);
 644                 int                      pn   = get_Proj_proj(proj);
 645
 646                 assert(arg->in_reg);
 647                 be_set_constr_single_reg_out(low_call, pn, arg->reg,
 648                                              arch_register_req_type_none);
 649                 arch_set_irn_register(proj, arg->reg);
 650         }
 651         exchange(irn, low_call);
 652
 653         /* kill the ProjT node */
 654         if (res_proj != NULL) {
 655                 kill_node(res_proj);
 656         }
 657
 658         /* Make additional projs for the caller save registers
 659            and the Keep node which keeps them alive. */
 660         {
 661                 ir_node               **in, *keep;
 662                 int                   i;
 663                 size_t                d;
 664                 int                   n = 0;
 665                 int                   curr_res_proj = pn_be_Call_first_res + n_reg_results;
 666                 int                   n_ins;
 667
 668                 n_ins = ARR_LEN(destroyed_regs) + n_reg_results + 1;
 669                 in    = ALLOCAN(ir_node *, n_ins);
 670
 671                 /* also keep the stack pointer */
 672                 set_irn_link(curr_sp, (void*) sp);
 673                 in[n++] = curr_sp;
 674
 675                 for (d = 0; d < ARR_LEN(destroyed_regs); ++d) {
 676                         const arch_register_t *reg = destroyed_regs[d];
 677                         ir_node *proj = new_r_Proj(low_call, reg->reg_class->mode, curr_res_proj);
 678
 679                         /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
 680                         be_set_constr_single_reg_out(low_call, curr_res_proj, reg,
 681                                                      arch_register_req_type_none);
 682                         arch_set_irn_register(proj, reg);
 683
 684                         set_irn_link(proj, (void*) reg);
 685                         in[n++] = proj;
 686                         ++curr_res_proj;
 687                 }
 688
 689                 for (i = 0; i < n_reg_results; ++i) {
 690                         ir_node *proj = res_projs[i];
 691                         const arch_register_t *reg = arch_get_irn_register(proj);
 692                         set_irn_link(proj, (void*) reg);
 693                         in[n++] = proj;
 694                 }
 695                 assert(n <= n_ins);
 696
 697                 /* create the Keep for the caller save registers */
 698                 keep = be_new_Keep(bl, n, in);
 699                 for (i = 0; i < n; ++i) {
 700                         const arch_register_t *reg = (const arch_register_t*)get_irn_link(in[i]);
 701                         be_node_set_reg_class_in(keep, i, reg->reg_class);
 702                 }
 703         }
 704
 705         /* Clean up the stack. */
 706         assert(stack_size >= call->pop);
 707         stack_size -= call->pop;
 708
 709         if (stack_size > 0) {
 710                 ir_node *mem_proj = NULL;
 711
 712                 foreach_out_edge(low_call, edge) {
 713                         ir_node *irn = get_edge_src_irn(edge);
 714                         if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
 715                                 mem_proj = irn;
 716                                 break;
 717                         }
 718                 }
 719
 720                 if (! mem_proj) {
 721                         mem_proj = new_r_Proj(low_call, mode_M, pn_be_Call_M);
 722                         keep_alive(mem_proj);
 723                 }
 724         }
 725         /* Clean up the stack frame or revert alignment fixes if we allocated it */
 726         curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
 727
 728         be_abi_call_free(call);
 729
 730         DEL_ARR_F(states);
 731         DEL_ARR_F(destroyed_regs);
 732
 733         return curr_sp;
 734 }
 735
 736 /**
 737  * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
 738  *
 739  * @param alignment  the minimum stack alignment
 740  * @param size       the node containing the non-aligned size
 741  * @param block      the block where new nodes are allocated on
 742  * @param dbg        debug info for new nodes
 743  *
 744  * @return a node representing the aligned size
 745  */
 746 static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
 747                                   ir_node *block, dbg_info *dbg)
 748 {
 749         if (stack_alignment > 1) {
 750                 ir_mode   *mode;
 751                 ir_tarval *tv;
 752                 ir_node   *mask;
 753                 ir_graph  *irg;
 754
 755                 assert(is_po2(stack_alignment));
 756
 757                 mode = get_irn_mode(size);
 758                 tv   = new_tarval_from_long(stack_alignment-1, mode);
 759                 irg  = get_Block_irg(block);
 760                 mask = new_r_Const(irg, tv);
 761                 size = new_rd_Add(dbg, block, size, mask, mode);
 762
 763                 tv   = new_tarval_from_long(-(long)stack_alignment, mode);
 764                 mask = new_r_Const(irg, tv);
 765                 size = new_rd_And(dbg, block, size, mask, mode);
 766         }
 767         return size;
 768 }
 769 /**
 770  * Adjust an alloca.
 771  * The alloca is transformed into a back end alloca node and connected to the stack nodes.
 772  */
 773 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
 774 {
 775         ir_node          *block     = get_nodes_block(alloc);
 776         ir_graph         *irg       = get_Block_irg(block);
 777         const arch_env_t *arch_env  = be_get_irg_arch_env(irg);
 778         ir_node          *alloc_mem = NULL;
 779         ir_node          *alloc_res = NULL;
 780         ir_type          *type      = get_Alloc_type(alloc);
 781         dbg_info         *dbg;
 782
 783         ir_node *new_alloc;
 784         ir_node *count;
 785         ir_node *size;
 786         ir_node *ins[2];
 787         unsigned stack_alignment;
 788
 789         /* all non-stack Alloc nodes should already be lowered before the backend */
 790         assert(get_Alloc_where(alloc) == stack_alloc);
 791
 792         foreach_out_edge(alloc, edge) {
 793                 ir_node *irn = get_edge_src_irn(edge);
 794
 795                 assert(is_Proj(irn));
 796                 switch (get_Proj_proj(irn)) {
 797                 case pn_Alloc_M:
 798                         alloc_mem = irn;
 799                         break;
 800                 case pn_Alloc_res:
 801                         alloc_res = irn;
 802                         break;
 803                 default:
 804                         break;
 805                 }
 806         }
 807
 808         /* Beware: currently Alloc nodes without a result might happen,
 809            only escape analysis kills them and this phase runs only for object
 810            oriented source. We kill the Alloc here. */
 811         if (alloc_res == NULL && alloc_mem) {
 812                 exchange(alloc_mem, get_Alloc_mem(alloc));
 813                 return curr_sp;
 814         }
 815
 816         dbg   = get_irn_dbg_info(alloc);
 817         count = get_Alloc_count(alloc);
 818
 819         /* we might need to multiply the count with the element size */
 820         if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
 821                 ir_mode   *mode  = get_irn_mode(count);
 822                 ir_tarval *tv    = new_tarval_from_long(get_type_size_bytes(type),
 823                                                         mode);
 824                 ir_node   *cnst = new_rd_Const(dbg, irg, tv);
 825                 size            = new_rd_Mul(dbg, block, count, cnst, mode);
 826         } else {
 827                 size = count;
 828         }
 829
 830         /* The stack pointer will be modified in an unknown manner.
 831            We cannot omit it. */
 832         env->call->flags.try_omit_fp = 0;
 833
 834         stack_alignment = 1 << arch_env->stack_alignment;
 835         size            = adjust_alloc_size(stack_alignment, size, block, dbg);
 836         new_alloc       = be_new_AddSP(arch_env->sp, block, curr_sp, size);
 837         set_irn_dbg_info(new_alloc, dbg);
 838
 839         if (alloc_mem != NULL) {
 840                 ir_node *addsp_mem;
 841                 ir_node *sync;
 842
 843                 addsp_mem = new_r_Proj(new_alloc, mode_M, pn_be_AddSP_M);
 844
 845                 /* We need to sync the output mem of the AddSP with the input mem
 846                    edge into the alloc node. */
 847                 ins[0] = get_Alloc_mem(alloc);
 848                 ins[1] = addsp_mem;
 849                 sync = new_r_Sync(block, 2, ins);
 850
 851                 exchange(alloc_mem, sync);
 852         }
 853
 854         exchange(alloc, new_alloc);
 855
 856         /* fix projnum of alloca res */
 857         set_Proj_proj(alloc_res, pn_be_AddSP_res);
 858
 859         curr_sp = new_r_Proj(new_alloc,  get_irn_mode(curr_sp), pn_be_AddSP_sp);
 860
 861         return curr_sp;
 862 }
 863
 864 /**
 865  * Adjust a Free.
 866  * The Free is transformed into a back end free node and connected to the stack nodes.
 867  */
 868 static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
 869 {
 870         ir_node          *block    = get_nodes_block(free);
 871         ir_graph         *irg      = get_irn_irg(free);
 872         ir_type          *type     = get_Free_type(free);
 873         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
 874         ir_mode          *sp_mode  = arch_env->sp->reg_class->mode;
 875         dbg_info         *dbg      = get_irn_dbg_info(free);
 876         ir_node  *subsp, *mem, *res, *size, *sync;
 877         ir_node *in[2];
 878         unsigned stack_alignment;
 879
 880         /* all non-stack-alloc Free nodes should already be lowered before the
 881          * backend phase */
 882         assert(get_Free_where(free) == stack_alloc);
 883
 884         /* we might need to multiply the size with the element size */
 885         if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
 886                 ir_tarval *tv   = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
 887                 ir_node   *cnst = new_rd_Const(dbg, irg, tv);
 888                 ir_node   *mul  = new_rd_Mul(dbg, block, get_Free_count(free),
 889                                              cnst, mode_Iu);
 890                 size = mul;
 891         } else {
 892                 size = get_Free_count(free);
 893         }
 894
 895         stack_alignment = 1 << arch_env->stack_alignment;
 896         size            = adjust_alloc_size(stack_alignment, size, block, dbg);
 897
 898         /* The stack pointer will be modified in an unknown manner.
 899            We cannot omit it. */
 900         env->call->flags.try_omit_fp = 0;
 901         subsp = be_new_SubSP(arch_env->sp, block, curr_sp, size);
 902         set_irn_dbg_info(subsp, dbg);
 903
 904         mem = new_r_Proj(subsp, mode_M, pn_be_SubSP_M);
 905         res = new_r_Proj(subsp, sp_mode, pn_be_SubSP_sp);
 906
 907         /* we need to sync the memory */
 908         in[0] = get_Free_mem(free);
 909         in[1] = mem;
 910         sync = new_r_Sync(block, 2, in);
 911
 912         /* and make the AddSP dependent on the former memory */
 913         add_irn_dep(subsp, get_Free_mem(free));
 914
 915         /* kill the free */
 916         exchange(free, sync);
 917         curr_sp = res;
 918
 919         return curr_sp;
 920 }
 921
 922 /**
 923  * Check if a node is somehow data dependent on another one.
 924  * both nodes must be in the same basic block.
 925  * @param n1 The first node.
 926  * @param n2 The second node.
 927  * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
 928  */
 929 static int dependent_on(ir_node *n1, ir_node *n2)
 930 {
 931         assert(get_nodes_block(n1) == get_nodes_block(n2));
 932
 933         return heights_reachable_in_block(ir_heights, n1, n2);
 934 }
 935
 936 static int cmp_call_dependency(const void *c1, const void *c2)
 937 {
 938         ir_node *n1 = *(ir_node **) c1;
 939         ir_node *n2 = *(ir_node **) c2;
 940         unsigned h1, h2;
 941
 942         /*
 943                 Classical qsort() comparison function behavior:
 944                 0  if both elements are equal
 945                 1  if second is "smaller" that first
 946                 -1 if first is "smaller" that second
 947         */
 948         if (dependent_on(n1, n2))
 949                 return -1;
 950
 951         if (dependent_on(n2, n1))
 952                 return 1;
 953
 954         /* The nodes have no depth order, but we need a total order because qsort()
 955          * is not stable.
 956          *
 957          * Additionally, we need to respect transitive dependencies. Consider a
 958          * Call a depending on Call b and an independent Call c.
 959          * We MUST NOT order c > a and b > c. */
 960         h1 = get_irn_height(ir_heights, n1);
 961         h2 = get_irn_height(ir_heights, n2);
 962         if (h1 < h2) return -1;
 963         if (h1 > h2) return  1;
 964         /* Same height, so use a random (but stable) order */
 965         return get_irn_idx(n1) - get_irn_idx(n2);
 966 }
 967
 968 /**
 969  * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
 970  */
 971 static void link_ops_in_block_walker(ir_node *irn, void *data)
 972 {
 973         be_abi_irg_t *env  = (be_abi_irg_t*)data;
 974         unsigned      code = get_irn_opcode(irn);
 975
 976         if (code == iro_Call ||
 977            (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
 978            (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
 979                 ir_node *bl       = get_nodes_block(irn);
 980                 void *save        = get_irn_link(bl);
 981
 982                 set_irn_link(irn, save);
 983                 set_irn_link(bl, irn);
 984         }
 985
 986         if (code == iro_Builtin && get_Builtin_kind(irn) == ir_bk_return_address) {
 987                 ir_node       *param = get_Builtin_param(irn, 0);
 988                 ir_tarval     *tv    = get_Const_tarval(param);
 989                 unsigned long  value = get_tarval_long(tv);
 990                 /* use ebp, so the climbframe algo works... */
 991                 if (value > 0) {
 992                         env->call->flags.try_omit_fp = 0;
 993                 }
 994         }
 995 }
 996
 997 /**
 998  * Block-walker:
 999  * Process all Call/Alloc/Free nodes inside a basic block.
1000  * Note that the link field of the block must contain a linked list of all
1001  * nodes inside the Block. We first order this list according to data dependency
1002  * and that connect the nodes together.
1003  */
1004 static void process_ops_in_block(ir_node *bl, void *data)
1005 {
1006         be_abi_irg_t   *env     = (be_abi_irg_t*)data;
1007         ir_node        *curr_sp = env->init_sp;
1008         ir_node        *irn;
1009         ir_node       **nodes;
1010         int             n;
1011         int             n_nodes;
1012
1013         n_nodes = 0;
1014         for (irn = (ir_node*)get_irn_link(bl); irn != NULL;
1015              irn = (ir_node*)get_irn_link(irn)) {
1016                 ++n_nodes;
1017         }
1018
1019         nodes = ALLOCAN(ir_node*, n_nodes);
1020         for (irn = (ir_node*)get_irn_link(bl), n = 0; irn != NULL;
1021              irn = (ir_node*)get_irn_link(irn), ++n) {
1022                 nodes[n] = irn;
1023         }
1024
1025         /* If there were call nodes in the block. */
1026         if (n > 0) {
1027                 ir_node *keep;
1028                 int i;
1029
1030                 /* order the call nodes according to data dependency */
1031                 qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
1032
1033                 for (i = n_nodes - 1; i >= 0; --i) {
1034                         ir_node *irn = nodes[i];
1035
1036                         DBG((dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1037                         switch (get_irn_opcode(irn)) {
1038                         case iro_Call:
1039                                 if (! be_omit_fp) {
1040                                         /* The stack pointer will be modified due to a call. */
1041                                         env->call->flags.try_omit_fp = 0;
1042                                 }
1043                                 curr_sp = adjust_call(env, irn, curr_sp);
1044                                 break;
1045                         case iro_Alloc:
1046                                 if (get_Alloc_where(irn) == stack_alloc)
1047                                         curr_sp = adjust_alloc(env, irn, curr_sp);
1048                                 break;
1049                         case iro_Free:
1050                                 if (get_Free_where(irn) == stack_alloc)
1051                                         curr_sp = adjust_free(env, irn, curr_sp);
1052                                 break;
1053                         default:
1054                                 panic("invalid call");
1055                         }
1056                 }
1057
1058                 /* Keep the last stack state in the block by tying it to Keep node,
1059                  * the proj from calls is already kept */
1060                 if (curr_sp != env->init_sp &&
1061                     !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1062                         nodes[0] = curr_sp;
1063                         keep     = be_new_Keep(bl, 1, nodes);
1064                         pmap_insert(env->keep_map, bl, keep);
1065                 }
1066         }
1067
1068         set_irn_link(bl, curr_sp);
1069 }
1070
1071 /**
1072  * Adjust all call nodes in the graph to the ABI conventions.
1073  */
1074 static void process_calls(ir_graph *const irg, be_abi_irg_t *const abi)
1075 {
1076         irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, abi);
1077
1078         ir_heights = heights_new(irg);
1079         irg_block_walk_graph(irg, NULL, process_ops_in_block, abi);
1080         heights_free(ir_heights);
1081 }
1082
1083 /**
1084  * Computes the stack argument layout type.
1085  * Changes a possibly allocated value param type by moving
1086  * entities to the stack layout type.
1087  *
1088  * @param call          the current call ABI
1089  * @param method_type   the method type
1090  *
1091  * @return the stack argument layout type
1092  */
1093 static ir_type *compute_arg_type(ir_graph *irg, be_abi_call_t *call,
1094                                                                  ir_type *method_type)
1095 {
1096         struct obstack *obst = be_get_be_obst(irg);
1097         ir_type   *frame_type      = get_irg_frame_type(irg);
1098         size_t     n_params        = get_method_n_params(method_type);
1099         size_t     n_frame_members = get_compound_n_members(frame_type);
1100         ir_entity *va_start_entity = NULL;
1101         size_t   f;
1102         int      ofs  = 0;
1103
1104         ir_type *res;
1105         size_t i;
1106         ir_entity **map = OALLOCNZ(obst, ir_entity*, n_params);
1107         res = new_type_struct(new_id_from_chars("arg_type", 8));
1108
1109         /* collect existing entities for value_param_types */
1110         for (f = n_frame_members; f > 0; ) {
1111                 ir_entity *entity = get_compound_member(frame_type, --f);
1112                 size_t     num;
1113
1114                 set_entity_link(entity, NULL);
1115                 if (!is_parameter_entity(entity))
1116                         continue;
1117                 num = get_entity_parameter_number(entity);
1118                 if (num == IR_VA_START_PARAMETER_NUMBER) {
1119                         /* move entity to new arg_type */
1120                         set_entity_owner(entity, res);
1121                         va_start_entity = entity;
1122                         continue;
1123                 }
1124                 assert(num < n_params);
1125                 if (map[num] != NULL)
1126                         panic("multiple entities for parameter %u in %+F found", f, irg);
1127
1128                 if (num != n_params && get_call_arg(call, 0, num, 1)->in_reg) {
1129                         /* don't move this entity */
1130                         continue;
1131                 }
1132
1133                 map[num] = entity;
1134                 /* move entity to new arg_type */
1135                 set_entity_owner(entity, res);
1136         }
1137
1138         for (i = 0; i < n_params; ++i) {
1139                 be_abi_call_arg_t *arg        = get_call_arg(call, 0, i, 1);
1140                 ir_type           *param_type = get_method_param_type(method_type, i);
1141                 ir_entity         *entity;
1142
1143                 if (arg->in_reg)
1144                         continue;
1145                 entity = map[i];
1146                 if (entity == NULL) {
1147                         /* create a new entity */
1148                         entity = new_parameter_entity(res, i, param_type);
1149                 }
1150                 ofs += arg->space_before;
1151                 ofs = round_up2(ofs, arg->alignment);
1152                 set_entity_offset(entity, ofs);
1153                 ofs += arg->space_after;
1154                 ofs += get_type_size_bytes(param_type);
1155                 arg->stack_ent = entity;
1156         }
1157         if (va_start_entity != NULL) {
1158                 set_entity_offset(va_start_entity, ofs);
1159         }
1160         set_type_size_bytes(res, ofs);
1161         set_type_state(res, layout_fixed);
1162
1163         return res;
1164 }
1165
1166 typedef struct {
1167         const arch_register_t *reg;
1168         ir_node *irn;
1169 } reg_node_map_t;
1170
1171 static int cmp_regs(const void *a, const void *b)
1172 {
1173         const reg_node_map_t *p = (const reg_node_map_t*)a;
1174         const reg_node_map_t *q = (const reg_node_map_t*)b;
1175
1176         if (p->reg->reg_class == q->reg->reg_class)
1177                 return p->reg->index - q->reg->index;
1178         else
1179                 return p->reg->reg_class < q->reg->reg_class ? -1 : +1;
1180 }
1181
1182 static void reg_map_to_arr(reg_node_map_t *res, pmap *reg_map)
1183 {
1184         pmap_entry *ent;
1185         size_t n = pmap_count(reg_map);
1186         size_t i = 0;
1187
1188         foreach_pmap(reg_map, ent) {
1189                 res[i].reg = (const arch_register_t*)ent->key;
1190                 res[i].irn = (ir_node*)ent->value;
1191                 i++;
1192         }
1193
1194         qsort(res, n, sizeof(res[0]), cmp_regs);
1195 }
1196
1197 /**
1198  * Creates a be_Return for a Return node.
1199  *
1200  * @param @env  the abi environment
1201  * @param irn   the Return node or NULL if there was none
1202  * @param bl    the block where the be_Retun should be placed
1203  * @param mem   the current memory
1204  * @param n_res number of return results
1205  */
1206 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1207                 ir_node *mem, int n_res)
1208 {
1209         be_abi_call_t    *call     = env->call;
1210         ir_graph         *irg      = get_Block_irg(bl);
1211         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1212         dbg_info *dbgi;
1213         pmap *reg_map  = pmap_create();
1214         ir_node *keep  = pmap_get(ir_node, env->keep_map, bl);
1215         size_t in_max;
1216         ir_node *ret;
1217         int i, n;
1218         unsigned pop;
1219         ir_node **in;
1220         ir_node *stack;
1221         const arch_register_t **regs;
1222         pmap_entry *ent;
1223
1224         /*
1225                 get the valid stack node in this block.
1226                 If we had a call in that block there is a Keep constructed by process_calls()
1227                 which points to the last stack modification in that block. we'll use
1228                 it then. Else we use the stack from the start block and let
1229                 the ssa construction fix the usage.
1230         */
1231         stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1232         if (keep) {
1233                 stack = get_irn_n(keep, 0);
1234                 kill_node(keep);
1235                 remove_End_keepalive(get_irg_end(irg), keep);
1236         }
1237
1238         /* Insert results for Return into the register map. */
1239         for (i = 0; i < n_res; ++i) {
1240                 ir_node *res           = get_Return_res(irn, i);
1241                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1242                 assert(arg->in_reg && "return value must be passed in register");
1243                 pmap_insert(reg_map, (void *) arg->reg, res);
1244         }
1245
1246         /* Add uses of the callee save registers. */
1247         foreach_pmap(env->regs, ent) {
1248                 const arch_register_t *reg = (const arch_register_t*)ent->key;
1249                 if ((reg->type & arch_register_type_ignore) || arch_register_is_callee_save(arch_env, reg))
1250                         pmap_insert(reg_map, ent->key, ent->value);
1251         }
1252
1253         be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1254
1255         /*
1256                 Maximum size of the in array for Return nodes is
1257                 return args + callee save/ignore registers + memory + stack pointer
1258         */
1259         in_max = pmap_count(reg_map) + n_res + 2;
1260
1261         in   = ALLOCAN(ir_node*,               in_max);
1262         regs = ALLOCAN(arch_register_t const*, in_max);
1263
1264         in[0]   = mem;
1265         in[1]   = be_abi_reg_map_get(reg_map, arch_env->sp);
1266         regs[0] = NULL;
1267         regs[1] = arch_env->sp;
1268         n       = 2;
1269
1270         /* clear SP entry, since it has already been grown. */
1271         pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1272         for (i = 0; i < n_res; ++i) {
1273                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1274
1275                 in[n]     = be_abi_reg_map_get(reg_map, arg->reg);
1276                 regs[n++] = arg->reg;
1277
1278                 /* Clear the map entry to mark the register as processed. */
1279                 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1280         }
1281
1282         /* grow the rest of the stuff. */
1283         foreach_pmap(reg_map, ent) {
1284                 if (ent->value) {
1285                         in[n]     = (ir_node*)ent->value;
1286                         regs[n++] = (const arch_register_t*)ent->key;
1287                 }
1288         }
1289
1290         /* The in array for the new back end return is now ready. */
1291         if (irn != NULL) {
1292                 dbgi = get_irn_dbg_info(irn);
1293         } else {
1294                 dbgi = NULL;
1295         }
1296         /* we have to pop the shadow parameter in in case of struct returns */
1297         pop = call->pop;
1298         ret = be_new_Return(dbgi, irg, bl, n_res, pop, n, in);
1299
1300         /* Set the register classes of the return's parameter accordingly. */
1301         for (i = 0; i < n; ++i) {
1302                 if (regs[i] == NULL)
1303                         continue;
1304
1305                 be_set_constr_single_reg_in(ret, i, regs[i], arch_register_req_type_none);
1306         }
1307
1308         /* Free the space of the Epilog's in array and the register <-> proj map. */
1309         pmap_destroy(reg_map);
1310
1311         return ret;
1312 }
1313
1314 typedef struct lower_frame_sels_env_t {
1315         ir_node      *frame;                     /**< the current frame */
1316         const arch_register_class_t *sp_class;   /**< register class of the stack pointer */
1317 } lower_frame_sels_env_t;
1318
1319 /**
1320  * Walker: Replaces Sels of frame type and
1321  * value param type entities by FrameAddress.
1322  * Links all used entities.
1323  */
1324 static void lower_frame_sels_walker(ir_node *irn, void *data)
1325 {
1326         lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1327
1328         if (is_Sel(irn)) {
1329                 ir_node *ptr = get_Sel_ptr(irn);
1330
1331                 if (ptr == ctx->frame) {
1332                         ir_entity    *ent = get_Sel_entity(irn);
1333                         ir_node      *bl  = get_nodes_block(irn);
1334                         ir_node      *nw;
1335
1336                         nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1337                         exchange(irn, nw);
1338                 }
1339         }
1340 }
1341
1342 /**
1343  * The start block has no jump, instead it has an initial exec Proj.
1344  * The backend wants to handle all blocks the same way, so we replace
1345  * the out cfg edge with a real jump.
1346  */
1347 static void fix_start_block(ir_graph *irg)
1348 {
1349         ir_node *initial_X   = get_irg_initial_exec(irg);
1350         ir_node *start_block = get_irg_start_block(irg);
1351         ir_node *jmp         = new_r_Jmp(start_block);
1352
1353         assert(is_Proj(initial_X));
1354         exchange(initial_X, jmp);
1355         set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1356
1357         /* merge start block with successor if possible */
1358         {
1359                 foreach_out_edge(jmp, edge) {
1360                         ir_node *succ = get_edge_src_irn(edge);
1361                         if (!is_Block(succ))
1362                                 continue;
1363
1364                         if (get_irn_arity(succ) == 1) {
1365                                 exchange(succ, start_block);
1366                         }
1367                         break;
1368                 }
1369         }
1370 }
1371
1372 /**
1373  * Modify the irg itself and the frame type.
1374  */
1375 static void modify_irg(ir_graph *const irg, be_abi_irg_t *const env)
1376 {
1377         be_abi_call_t         *call         = env->call;
1378         const arch_env_t      *arch_env     = be_get_irg_arch_env(irg);
1379         const arch_register_t *sp           = arch_env->sp;
1380         ir_type               *method_type  = get_entity_type(get_irg_entity(irg));
1381         be_irg_t              *birg         = be_birg_from_irg(irg);
1382         struct obstack        *obst         = be_get_be_obst(irg);
1383         be_stack_layout_t     *stack_layout = be_get_irg_stack_layout(irg);
1384         ir_node *end;
1385         ir_node *old_mem;
1386         ir_node *new_mem_proj;
1387         ir_node *mem;
1388
1389         int n_params;
1390         int i, n;
1391         unsigned j;
1392
1393         reg_node_map_t *rm;
1394         const arch_register_t *fp_reg;
1395         ir_node *frame_pointer;
1396         ir_node *start_bl;
1397         ir_node **args;
1398         ir_node *arg_tuple;
1399         ir_type *arg_type, *bet_type;
1400         lower_frame_sels_env_t ctx;
1401
1402         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1403
1404         old_mem = get_irg_initial_mem(irg);
1405
1406         irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1407
1408         arg_type = compute_arg_type(irg, call, method_type);
1409
1410         /* Convert the Sel nodes in the irg to frame addr nodes: */
1411         ctx.frame    = get_irg_frame(irg);
1412         ctx.sp_class = arch_env->sp->reg_class;
1413
1414         ir_type *const frame_tp = get_irg_frame_type(irg);
1415         /* layout the stackframe now */
1416         if (get_type_state(frame_tp) == layout_undefined) {
1417                 default_layout_compound_type(frame_tp);
1418         }
1419
1420         /* align stackframe */
1421         unsigned const alignment  = 1U << arch_env->stack_alignment;
1422         unsigned const frame_size = round_up2(get_type_size_bytes(frame_tp), alignment);
1423         set_type_size_bytes(frame_tp, frame_size);
1424
1425         env->regs  = pmap_create();
1426
1427         n_params = get_method_n_params(method_type);
1428         args     = OALLOCNZ(obst, ir_node*, n_params);
1429
1430         be_add_parameter_entity_stores(irg);
1431
1432         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1433
1434         irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1435
1436         /* Fill the argument vector */
1437         arg_tuple = get_irg_args(irg);
1438         foreach_out_edge(arg_tuple, edge) {
1439                 ir_node *irn = get_edge_src_irn(edge);
1440                 if (! is_Anchor(irn)) {
1441                         int nr       = get_Proj_proj(irn);
1442                         args[nr]     = irn;
1443                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1444                 }
1445         }
1446
1447         stack_layout->sp_relative = call->flags.try_omit_fp;
1448         bet_type = call->cb->get_between_type(irg);
1449         stack_frame_init(stack_layout, arg_type, bet_type,
1450                          get_irg_frame_type(irg));
1451
1452         /* Count the register params and add them to the number of Projs for the RegParams node */
1453         for (i = 0; i < n_params; ++i) {
1454                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1455                 if (arg->in_reg && args[i]) {
1456                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1457                         assert(i == get_Proj_proj(args[i]));
1458
1459                         /* For now, associate the register with the old Proj from Start representing that argument. */
1460                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1461                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1462                 }
1463         }
1464
1465         /* Collect all callee-save registers */
1466         for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1467                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1468                 for (j = 0; j < cls->n_regs; ++j) {
1469                         const arch_register_t *reg = &cls->regs[j];
1470                         if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1471                                 pmap_insert(env->regs, (void *) reg, NULL);
1472                         }
1473                 }
1474         }
1475
1476         fp_reg = call->flags.try_omit_fp ? arch_env->sp : arch_env->bp;
1477         rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1478
1479         /* handle start block here (place a jump in the block) */
1480         fix_start_block(irg);
1481
1482         pmap_insert(env->regs, (void *) sp, NULL);
1483         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1484         start_bl   = get_irg_start_block(irg);
1485         ir_node *const start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1486         set_irg_start(irg, start);
1487
1488         /*
1489          * make proj nodes for the callee save registers.
1490          * memorize them, since Return nodes get those as inputs.
1491          *
1492          * Note, that if a register corresponds to an argument, the regs map
1493          * contains the old Proj from start for that argument.
1494          */
1495         rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1496         reg_map_to_arr(rm, env->regs);
1497         for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1498                 const arch_register_t    *reg      = rm[i].reg;
1499                 ir_mode                  *mode     = reg->reg_class->mode;
1500                 long                      nr       = i;
1501                 arch_register_req_type_t  add_type = arch_register_req_type_none;
1502                 ir_node                  *proj;
1503
1504                 if (reg == sp)
1505                         add_type |= arch_register_req_type_produces_sp;
1506                 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1507                         add_type |= arch_register_req_type_ignore;
1508                 }
1509
1510                 assert(nr >= 0);
1511                 proj = new_r_Proj(start, mode, nr + 1);
1512                 pmap_insert(env->regs, (void *) reg, proj);
1513                 be_set_constr_single_reg_out(start, nr + 1, reg, add_type);
1514                 arch_set_irn_register(proj, reg);
1515
1516                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1517         }
1518
1519         /* create a new initial memory proj */
1520         assert(is_Proj(old_mem));
1521         arch_set_irn_register_req_out(start, 0, arch_no_register_req);
1522         new_mem_proj = new_r_Proj(start, mode_M, 0);
1523         mem = new_mem_proj;
1524         set_irg_initial_mem(irg, mem);
1525
1526         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1527
1528         /* set new frame_pointer */
1529         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1530         set_irg_frame(irg, frame_pointer);
1531
1532         /* rewire old mem users to new mem */
1533         exchange(old_mem, mem);
1534
1535         /* keep the mem (for functions with an endless loop = no return) */
1536         keep_alive(mem);
1537
1538         set_irg_initial_mem(irg, mem);
1539
1540         /* Now, introduce stack param nodes for all parameters passed on the stack */
1541         for (i = 0; i < n_params; ++i) {
1542                 ir_node *arg_proj = args[i];
1543                 ir_node *repl     = NULL;
1544
1545                 if (arg_proj != NULL) {
1546                         be_abi_call_arg_t *arg;
1547                         ir_type *param_type;
1548                         int     nr = get_Proj_proj(arg_proj);
1549                         ir_mode *mode;
1550
1551                         nr         = MIN(nr, n_params);
1552                         arg        = get_call_arg(call, 0, nr, 1);
1553                         param_type = get_method_param_type(method_type, nr);
1554
1555                         if (arg->in_reg) {
1556                                 repl = pmap_get(ir_node, env->regs, arg->reg);
1557                         } else {
1558                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1559
1560                                 /* For atomic parameters which are actually used, we create a Load node. */
1561                                 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1562                                         ir_mode *mode      = get_type_mode(param_type);
1563                                         ir_mode *load_mode = arg->load_mode;
1564                                         ir_node *nomem     = get_irg_no_mem(irg);
1565
1566                                         ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1567                                         repl = new_r_Proj(load, load_mode, pn_Load_res);
1568
1569                                         if (mode != load_mode) {
1570                                                 repl = new_r_Conv(start_bl, repl, mode);
1571                                         }
1572                                 } else {
1573                                         /* The stack parameter is not primitive (it is a struct or array),
1574                                          * we thus will create a node representing the parameter's address
1575                                          * on the stack. */
1576                                         repl = addr;
1577                                 }
1578                         }
1579
1580                         assert(repl != NULL);
1581
1582                         /* Beware: the mode of the register parameters is always the mode of the register class
1583                            which may be wrong. Add Conv's then. */
1584                         mode = get_irn_mode(args[i]);
1585                         if (mode != get_irn_mode(repl)) {
1586                                 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1587                         }
1588                         exchange(args[i], repl);
1589                 }
1590         }
1591
1592         /* the arg proj is not needed anymore now and should be only used by the anchor */
1593         assert(get_irn_n_edges(arg_tuple) == 1);
1594         kill_node(arg_tuple);
1595         set_irg_args(irg, new_r_Bad(irg, mode_T));
1596
1597         /* All Return nodes hang on the End node, so look for them there. */
1598         end = get_irg_end_block(irg);
1599         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1600                 ir_node *irn = get_Block_cfgpred(end, i);
1601
1602                 if (is_Return(irn)) {
1603                         ir_node *blk = get_nodes_block(irn);
1604                         ir_node *mem = get_Return_mem(irn);
1605                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1606                         exchange(irn, ret);
1607                 }
1608         }
1609
1610         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1611            the code is dead and will never be executed. */
1612 }
1613
1614 /** Fix the state inputs of calls that still hang on unknowns */
1615 static void fix_call_state_inputs(ir_graph *const irg, be_abi_irg_t *const env)
1616 {
1617         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1618         int i, n, n_states;
1619         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1620
1621         /* Collect caller save registers */
1622         n = arch_env->n_register_classes;
1623         for (i = 0; i < n; ++i) {
1624                 unsigned j;
1625                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1626                 for (j = 0; j < cls->n_regs; ++j) {
1627                         const arch_register_t *reg = arch_register_for_index(cls, j);
1628                         if (reg->type & arch_register_type_state) {
1629                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1630                         }
1631                 }
1632         }
1633
1634         n = ARR_LEN(env->calls);
1635         n_states = ARR_LEN(stateregs);
1636         for (i = 0; i < n; ++i) {
1637                 int s, arity;
1638                 ir_node *call = env->calls[i];
1639
1640                 arity = get_irn_arity(call);
1641
1642                 /* the state reg inputs are the last n inputs of the calls */
1643                 for (s = 0; s < n_states; ++s) {
1644                         int inp = arity - n_states + s;
1645                         const arch_register_t *reg = stateregs[s];
1646                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1647
1648                         set_irn_n(call, inp, regnode);
1649                 }
1650         }
1651
1652         DEL_ARR_F(stateregs);
1653 }
1654
1655 /**
1656  * Create a trampoline entity for the given method.
1657  */
1658 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1659 {
1660         ir_type   *type   = get_entity_type(method);
1661         ident     *old_id = get_entity_ld_ident(method);
1662         ident     *id     = id_mangle3("", old_id, "$stub");
1663         ir_type   *parent = be->pic_trampolines_type;
1664         ir_entity *ent    = new_entity(parent, old_id, type);
1665         set_entity_ld_ident(ent, id);
1666         set_entity_visibility(ent, ir_visibility_private);
1667
1668         return ent;
1669 }
1670
1671 /**
1672  * Returns the trampoline entity for the given method.
1673  */
1674 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1675 {
1676         ir_entity *result = pmap_get(ir_entity, env->ent_trampoline_map, method);
1677         if (result == NULL) {
1678                 result = create_trampoline(env, method);
1679                 pmap_insert(env->ent_trampoline_map, method, result);
1680         }
1681
1682         return result;
1683 }
1684
1685 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1686 {
1687         ident     *old_id = get_entity_ld_ident(entity);
1688         ident     *id     = id_mangle3("", old_id, "$non_lazy_ptr");
1689         ir_type   *e_type = get_entity_type(entity);
1690         ir_type   *type   = new_type_pointer(e_type);
1691         ir_type   *parent = be->pic_symbols_type;
1692         ir_entity *ent    = new_entity(parent, old_id, type);
1693         set_entity_ld_ident(ent, id);
1694         set_entity_visibility(ent, ir_visibility_private);
1695
1696         return ent;
1697 }
1698
1699 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1700 {
1701         ir_entity *result = pmap_get(ir_entity, env->ent_pic_symbol_map, entity);
1702         if (result == NULL) {
1703                 result = create_pic_symbol(env, entity);
1704                 pmap_insert(env->ent_pic_symbol_map, entity, result);
1705         }
1706
1707         return result;
1708 }
1709
1710
1711
1712 /**
1713  * Returns non-zero if a given entity can be accessed using a relative address.
1714  */
1715 static int can_address_relative(ir_entity *entity)
1716 {
1717         return entity_has_definition(entity) && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1718 }
1719
1720 static ir_node *get_pic_base(ir_graph *irg)
1721 {
1722         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1723         if (arch_env->impl->get_pic_base == NULL)
1724                 return NULL;
1725         return arch_env->impl->get_pic_base(irg);
1726 }
1727
1728 /** patches SymConsts to work in position independent code */
1729 static void fix_pic_symconsts(ir_node *node, void *data)
1730 {
1731         ir_graph         *irg = get_irn_irg(node);
1732         be_main_env_t    *be  = be_get_irg_main_env(irg);
1733         ir_node          *pic_base;
1734         ir_node          *add;
1735         ir_node          *block;
1736         ir_mode          *mode;
1737         ir_node          *load;
1738         ir_node          *load_res;
1739         int               arity, i;
1740         (void) data;
1741
1742         arity = get_irn_arity(node);
1743         for (i = 0; i < arity; ++i) {
1744                 dbg_info  *dbgi;
1745                 ir_node   *pred = get_irn_n(node, i);
1746                 ir_entity *entity;
1747                 ir_entity *pic_symbol;
1748                 ir_node   *pic_symconst;
1749
1750                 if (!is_SymConst(pred))
1751                         continue;
1752
1753                 entity = get_SymConst_entity(pred);
1754                 block  = get_nodes_block(pred);
1755
1756                 /* calls can jump to relative addresses, so we can directly jump to
1757                    the (relatively) known call address or the trampoline */
1758                 if (i == 1 && is_Call(node)) {
1759                         ir_entity *trampoline;
1760                         ir_node   *trampoline_const;
1761
1762                         if (can_address_relative(entity))
1763                                 continue;
1764
1765                         dbgi             = get_irn_dbg_info(pred);
1766                         trampoline       = get_trampoline(be, entity);
1767                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1768                                                                     trampoline);
1769                         set_irn_n(node, i, trampoline_const);
1770                         continue;
1771                 }
1772
1773                 /* everything else is accessed relative to EIP */
1774                 mode     = get_irn_mode(pred);
1775                 pic_base = get_pic_base(irg);
1776
1777                 /* all ok now for locally constructed stuff */
1778                 if (can_address_relative(entity)) {
1779                         ir_node *add = new_r_Add(block, pic_base, pred, mode);
1780
1781                         /* make sure the walker doesn't visit this add again */
1782                         mark_irn_visited(add);
1783                         set_irn_n(node, i, add);
1784                         continue;
1785                 }
1786
1787                 /* get entry from pic symbol segment */
1788                 dbgi         = get_irn_dbg_info(pred);
1789                 pic_symbol   = get_pic_symbol(be, entity);
1790                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1791                                                         pic_symbol);
1792                 add = new_r_Add(block, pic_base, pic_symconst, mode);
1793                 mark_irn_visited(add);
1794
1795                 /* we need an extra indirection for global data outside our current
1796                    module. The loads are always safe and can therefore float
1797                    and need no memory input */
1798                 load     = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1799                 load_res = new_r_Proj(load, mode, pn_Load_res);
1800
1801                 set_irn_n(node, i, load_res);
1802         }
1803 }
1804
1805 void be_abi_introduce(ir_graph *irg)
1806 {
1807         ir_node          *old_frame   = get_irg_frame(irg);
1808         const arch_env_t *arch_env    = be_get_irg_arch_env(irg);
1809         ir_entity        *entity      = get_irg_entity(irg);
1810         ir_type          *method_type = get_entity_type(entity);
1811         be_irg_t         *birg        = be_birg_from_irg(irg);
1812         struct obstack   *obst        = &birg->obst;
1813         ir_node          *dummy       = new_r_Dummy(irg,
1814                                                     arch_env->sp->reg_class->mode);
1815         unsigned          r;
1816
1817         /* determine allocatable registers */
1818         assert(birg->allocatable_regs == NULL);
1819         birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1820         for (r = 0; r < arch_env->n_registers; ++r) {
1821                 const arch_register_t *reg = &arch_env->registers[r];
1822                 if ( !(reg->type & arch_register_type_ignore)) {
1823                         rbitset_set(birg->allocatable_regs, r);
1824                 }
1825         }
1826
1827         /* Break here if backend provides a custom API. */
1828
1829         be_omit_fp        = be_options.omit_fp;
1830
1831         be_abi_irg_t env;
1832         env.keep_map     = pmap_create();
1833         env.call         = be_abi_call_new(arch_env->sp->reg_class);
1834         arch_env_get_call_abi(arch_env, method_type, env.call);
1835
1836         env.init_sp = dummy;
1837         env.calls   = NEW_ARR_F(ir_node*, 0);
1838
1839         assure_edges(irg);
1840
1841         if (be_options.pic) {
1842                 irg_walk_graph(irg, fix_pic_symconsts, NULL, NULL);
1843         }
1844
1845         /* Lower all call nodes in the IRG. */
1846         process_calls(irg, &env);
1847
1848         /* Process the IRG */
1849         modify_irg(irg, &env);
1850
1851         /* fix call inputs for state registers */
1852         fix_call_state_inputs(irg, &env);
1853
1854         be_abi_call_free(env.call);
1855
1856         /* We don't need the keep map anymore. */
1857         pmap_destroy(env.keep_map);
1858
1859         /* calls array is not needed anymore */
1860         DEL_ARR_F(env.calls);
1861
1862         /* reroute the stack origin of the calls to the true stack origin. */
1863         exchange(dummy, env.init_sp);
1864         exchange(old_frame, get_irg_frame(irg));
1865
1866         pmap_destroy(env.regs);
1867 }
1868
1869 void be_put_allocatable_regs(const ir_graph *irg,
1870                              const arch_register_class_t *cls, bitset_t *bs)
1871 {
1872         be_irg_t *birg             = be_birg_from_irg(irg);
1873         unsigned *allocatable_regs = birg->allocatable_regs;
1874         unsigned  i;
1875
1876         assert(bitset_size(bs) == cls->n_regs);
1877         bitset_clear_all(bs);
1878         for (i = 0; i < cls->n_regs; ++i) {
1879                 const arch_register_t *reg = &cls->regs[i];
1880                 if (rbitset_is_set(allocatable_regs, reg->global_index))
1881                         bitset_set(bs, i);
1882         }
1883 }
1884
1885 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1886                                    const arch_register_class_t *cls)
1887 {
1888         bitset_t *bs = bitset_alloca(cls->n_regs);
1889         be_put_allocatable_regs(irg, cls, bs);
1890         return bitset_popcount(bs);
1891 }
1892
1893 void be_set_allocatable_regs(const ir_graph *irg,
1894                              const arch_register_class_t *cls,
1895                              unsigned *raw_bitset)
1896 {
1897         be_irg_t *birg             = be_birg_from_irg(irg);
1898         unsigned *allocatable_regs = birg->allocatable_regs;
1899         unsigned  i;
1900
1901         rbitset_clear_all(raw_bitset, cls->n_regs);
1902         for (i = 0; i < cls->n_regs; ++i) {
1903                 const arch_register_t *reg = &cls->regs[i];
1904                 if (rbitset_is_set(allocatable_regs, reg->global_index))
1905                         rbitset_set(raw_bitset, i);
1906         }
1907 }
1908
1909 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
1910 void be_init_abi(void)
1911 {
1912         FIRM_DBG_REGISTER(dbg, "firm.be.abi");
1913 }