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