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 } lower_frame_sels_env_t;
1323
1324 /**
1325  * Walker: Replaces Sels of frame type and
1326  * value param type entities by FrameAddress.
1327  * Links all used entities.
1328  */
1329 static void lower_frame_sels_walker(ir_node *irn, void *data)
1330 {
1331         lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1332
1333         if (is_Sel(irn)) {
1334                 ir_node *ptr = get_Sel_ptr(irn);
1335
1336                 if (ptr == ctx->frame) {
1337                         ir_entity    *ent = get_Sel_entity(irn);
1338                         ir_node      *bl  = get_nodes_block(irn);
1339                         ir_node      *nw;
1340
1341                         nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1342                         exchange(irn, nw);
1343                 }
1344         }
1345 }
1346
1347 /**
1348  * The start block has no jump, instead it has an initial exec Proj.
1349  * The backend wants to handle all blocks the same way, so we replace
1350  * the out cfg edge with a real jump.
1351  */
1352 static void fix_start_block(ir_graph *irg)
1353 {
1354         ir_node *initial_X   = get_irg_initial_exec(irg);
1355         ir_node *start_block = get_irg_start_block(irg);
1356         ir_node *jmp         = new_r_Jmp(start_block);
1357
1358         assert(is_Proj(initial_X));
1359         exchange(initial_X, jmp);
1360         set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1361
1362         /* merge start block with successor if possible */
1363         {
1364                 foreach_out_edge(jmp, edge) {
1365                         ir_node *succ = get_edge_src_irn(edge);
1366                         if (!is_Block(succ))
1367                                 continue;
1368
1369                         if (get_irn_arity(succ) == 1) {
1370                                 exchange(succ, start_block);
1371                         }
1372                         break;
1373                 }
1374         }
1375 }
1376
1377 /**
1378  * Modify the irg itself and the frame type.
1379  */
1380 static void modify_irg(ir_graph *const irg, be_abi_irg_t *const env)
1381 {
1382         be_abi_call_t         *call         = env->call;
1383         const arch_env_t      *arch_env     = be_get_irg_arch_env(irg);
1384         const arch_register_t *sp           = arch_env->sp;
1385         ir_type               *method_type  = get_entity_type(get_irg_entity(irg));
1386         be_irg_t              *birg         = be_birg_from_irg(irg);
1387         struct obstack        *obst         = be_get_be_obst(irg);
1388         be_stack_layout_t     *stack_layout = be_get_irg_stack_layout(irg);
1389         ir_node *end;
1390         ir_node *old_mem;
1391         ir_node *new_mem_proj;
1392         ir_node *mem;
1393
1394         int n_params;
1395         int i, n;
1396         unsigned j;
1397         unsigned frame_size;
1398
1399         reg_node_map_t *rm;
1400         const arch_register_t *fp_reg;
1401         ir_node *frame_pointer;
1402         ir_node *start_bl;
1403         ir_node **args;
1404         ir_node *arg_tuple;
1405         ir_type *arg_type, *bet_type;
1406         lower_frame_sels_env_t ctx;
1407
1408         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1409
1410         old_mem = get_irg_initial_mem(irg);
1411
1412         irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1413
1414         arg_type = compute_arg_type(irg, call, method_type);
1415
1416         /* Convert the Sel nodes in the irg to frame addr nodes: */
1417         ctx.frame    = get_irg_frame(irg);
1418         ctx.sp_class = arch_env->sp->reg_class;
1419
1420         ir_type *const frame_tp = get_irg_frame_type(irg);
1421         /* layout the stackframe now */
1422         if (get_type_state(frame_tp) == layout_undefined) {
1423                 default_layout_compound_type(frame_tp);
1424         }
1425
1426         /* align stackframe to 4 byte */
1427         frame_size = get_type_size_bytes(frame_tp);
1428         if (frame_size % 4 != 0) {
1429                 set_type_size_bytes(frame_tp, frame_size + 4 - (frame_size % 4));
1430         }
1431
1432         env->regs  = pmap_create();
1433
1434         n_params = get_method_n_params(method_type);
1435         args     = OALLOCNZ(obst, ir_node*, n_params);
1436
1437         be_add_parameter_entity_stores(irg);
1438
1439         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1440
1441         irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1442
1443         /* Fill the argument vector */
1444         arg_tuple = get_irg_args(irg);
1445         foreach_out_edge(arg_tuple, edge) {
1446                 ir_node *irn = get_edge_src_irn(edge);
1447                 if (! is_Anchor(irn)) {
1448                         int nr       = get_Proj_proj(irn);
1449                         args[nr]     = irn;
1450                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1451                 }
1452         }
1453
1454         stack_layout->sp_relative = call->flags.bits.try_omit_fp;
1455         bet_type = call->cb->get_between_type(irg);
1456         stack_frame_init(stack_layout, arg_type, bet_type,
1457                          get_irg_frame_type(irg));
1458
1459         /* Count the register params and add them to the number of Projs for the RegParams node */
1460         for (i = 0; i < n_params; ++i) {
1461                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1462                 if (arg->in_reg && args[i]) {
1463                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1464                         assert(i == get_Proj_proj(args[i]));
1465
1466                         /* For now, associate the register with the old Proj from Start representing that argument. */
1467                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1468                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1469                 }
1470         }
1471
1472         /* Collect all callee-save registers */
1473         for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1474                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1475                 for (j = 0; j < cls->n_regs; ++j) {
1476                         const arch_register_t *reg = &cls->regs[j];
1477                         if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1478                                 pmap_insert(env->regs, (void *) reg, NULL);
1479                         }
1480                 }
1481         }
1482
1483         fp_reg = call->flags.bits.try_omit_fp ? arch_env->sp : arch_env->bp;
1484         rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1485
1486         /* handle start block here (place a jump in the block) */
1487         fix_start_block(irg);
1488
1489         pmap_insert(env->regs, (void *) sp, NULL);
1490         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1491         start_bl   = get_irg_start_block(irg);
1492         ir_node *const start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1493         set_irg_start(irg, start);
1494
1495         /*
1496          * make proj nodes for the callee save registers.
1497          * memorize them, since Return nodes get those as inputs.
1498          *
1499          * Note, that if a register corresponds to an argument, the regs map
1500          * contains the old Proj from start for that argument.
1501          */
1502         rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1503         reg_map_to_arr(rm, env->regs);
1504         for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1505                 const arch_register_t    *reg      = rm[i].reg;
1506                 ir_mode                  *mode     = reg->reg_class->mode;
1507                 long                      nr       = i;
1508                 arch_register_req_type_t  add_type = arch_register_req_type_none;
1509                 ir_node                  *proj;
1510
1511                 if (reg == sp)
1512                         add_type |= arch_register_req_type_produces_sp;
1513                 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1514                         add_type |= arch_register_req_type_ignore;
1515                 }
1516
1517                 assert(nr >= 0);
1518                 proj = new_r_Proj(start, mode, nr + 1);
1519                 pmap_insert(env->regs, (void *) reg, proj);
1520                 be_set_constr_single_reg_out(start, nr + 1, reg, add_type);
1521                 arch_set_irn_register(proj, reg);
1522
1523                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1524         }
1525
1526         /* create a new initial memory proj */
1527         assert(is_Proj(old_mem));
1528         arch_set_irn_register_req_out(start, 0, arch_no_register_req);
1529         new_mem_proj = new_r_Proj(start, mode_M, 0);
1530         mem = new_mem_proj;
1531         set_irg_initial_mem(irg, mem);
1532
1533         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1534
1535         /* set new frame_pointer */
1536         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1537         set_irg_frame(irg, frame_pointer);
1538
1539         /* rewire old mem users to new mem */
1540         exchange(old_mem, mem);
1541
1542         /* keep the mem (for functions with an endless loop = no return) */
1543         keep_alive(mem);
1544
1545         set_irg_initial_mem(irg, mem);
1546
1547         /* Now, introduce stack param nodes for all parameters passed on the stack */
1548         for (i = 0; i < n_params; ++i) {
1549                 ir_node *arg_proj = args[i];
1550                 ir_node *repl     = NULL;
1551
1552                 if (arg_proj != NULL) {
1553                         be_abi_call_arg_t *arg;
1554                         ir_type *param_type;
1555                         int     nr = get_Proj_proj(arg_proj);
1556                         ir_mode *mode;
1557
1558                         nr         = MIN(nr, n_params);
1559                         arg        = get_call_arg(call, 0, nr, 1);
1560                         param_type = get_method_param_type(method_type, nr);
1561
1562                         if (arg->in_reg) {
1563                                 repl = pmap_get(ir_node, env->regs, arg->reg);
1564                         } else if (arg->on_stack) {
1565                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1566
1567                                 /* For atomic parameters which are actually used, we create a Load node. */
1568                                 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1569                                         ir_mode *mode      = get_type_mode(param_type);
1570                                         ir_mode *load_mode = arg->load_mode;
1571                                         ir_node *nomem     = get_irg_no_mem(irg);
1572
1573                                         ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1574                                         repl = new_r_Proj(load, load_mode, pn_Load_res);
1575
1576                                         if (mode != load_mode) {
1577                                                 repl = new_r_Conv(start_bl, repl, mode);
1578                                         }
1579                                 } else {
1580                                         /* The stack parameter is not primitive (it is a struct or array),
1581                                          * we thus will create a node representing the parameter's address
1582                                          * on the stack. */
1583                                         repl = addr;
1584                                 }
1585                         }
1586
1587                         assert(repl != NULL);
1588
1589                         /* Beware: the mode of the register parameters is always the mode of the register class
1590                            which may be wrong. Add Conv's then. */
1591                         mode = get_irn_mode(args[i]);
1592                         if (mode != get_irn_mode(repl)) {
1593                                 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1594                         }
1595                         exchange(args[i], repl);
1596                 }
1597         }
1598
1599         /* the arg proj is not needed anymore now and should be only used by the anchor */
1600         assert(get_irn_n_edges(arg_tuple) == 1);
1601         kill_node(arg_tuple);
1602         set_irg_args(irg, new_r_Bad(irg, mode_T));
1603
1604         /* All Return nodes hang on the End node, so look for them there. */
1605         end = get_irg_end_block(irg);
1606         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1607                 ir_node *irn = get_Block_cfgpred(end, i);
1608
1609                 if (is_Return(irn)) {
1610                         ir_node *blk = get_nodes_block(irn);
1611                         ir_node *mem = get_Return_mem(irn);
1612                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1613                         exchange(irn, ret);
1614                 }
1615         }
1616
1617         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1618            the code is dead and will never be executed. */
1619 }
1620
1621 /** Fix the state inputs of calls that still hang on unknowns */
1622 static void fix_call_state_inputs(ir_graph *const irg, be_abi_irg_t *const env)
1623 {
1624         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1625         int i, n, n_states;
1626         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1627
1628         /* Collect caller save registers */
1629         n = arch_env->n_register_classes;
1630         for (i = 0; i < n; ++i) {
1631                 unsigned j;
1632                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1633                 for (j = 0; j < cls->n_regs; ++j) {
1634                         const arch_register_t *reg = arch_register_for_index(cls, j);
1635                         if (reg->type & arch_register_type_state) {
1636                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1637                         }
1638                 }
1639         }
1640
1641         n = ARR_LEN(env->calls);
1642         n_states = ARR_LEN(stateregs);
1643         for (i = 0; i < n; ++i) {
1644                 int s, arity;
1645                 ir_node *call = env->calls[i];
1646
1647                 arity = get_irn_arity(call);
1648
1649                 /* the state reg inputs are the last n inputs of the calls */
1650                 for (s = 0; s < n_states; ++s) {
1651                         int inp = arity - n_states + s;
1652                         const arch_register_t *reg = stateregs[s];
1653                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1654
1655                         set_irn_n(call, inp, regnode);
1656                 }
1657         }
1658
1659         DEL_ARR_F(stateregs);
1660 }
1661
1662 /**
1663  * Create a trampoline entity for the given method.
1664  */
1665 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1666 {
1667         ir_type   *type   = get_entity_type(method);
1668         ident     *old_id = get_entity_ld_ident(method);
1669         ident     *id     = id_mangle3("", old_id, "$stub");
1670         ir_type   *parent = be->pic_trampolines_type;
1671         ir_entity *ent    = new_entity(parent, old_id, type);
1672         set_entity_ld_ident(ent, id);
1673         set_entity_visibility(ent, ir_visibility_private);
1674
1675         return ent;
1676 }
1677
1678 /**
1679  * Returns the trampoline entity for the given method.
1680  */
1681 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1682 {
1683         ir_entity *result = pmap_get(ir_entity, env->ent_trampoline_map, method);
1684         if (result == NULL) {
1685                 result = create_trampoline(env, method);
1686                 pmap_insert(env->ent_trampoline_map, method, result);
1687         }
1688
1689         return result;
1690 }
1691
1692 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1693 {
1694         ident     *old_id = get_entity_ld_ident(entity);
1695         ident     *id     = id_mangle3("", old_id, "$non_lazy_ptr");
1696         ir_type   *e_type = get_entity_type(entity);
1697         ir_type   *type   = new_type_pointer(e_type);
1698         ir_type   *parent = be->pic_symbols_type;
1699         ir_entity *ent    = new_entity(parent, old_id, type);
1700         set_entity_ld_ident(ent, id);
1701         set_entity_visibility(ent, ir_visibility_private);
1702
1703         return ent;
1704 }
1705
1706 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1707 {
1708         ir_entity *result = pmap_get(ir_entity, env->ent_pic_symbol_map, entity);
1709         if (result == NULL) {
1710                 result = create_pic_symbol(env, entity);
1711                 pmap_insert(env->ent_pic_symbol_map, entity, result);
1712         }
1713
1714         return result;
1715 }
1716
1717
1718
1719 /**
1720  * Returns non-zero if a given entity can be accessed using a relative address.
1721  */
1722 static int can_address_relative(ir_entity *entity)
1723 {
1724         return entity_has_definition(entity) && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1725 }
1726
1727 static ir_node *get_pic_base(ir_graph *irg)
1728 {
1729         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1730         if (arch_env->impl->get_pic_base == NULL)
1731                 return NULL;
1732         return arch_env->impl->get_pic_base(irg);
1733 }
1734
1735 /** patches SymConsts to work in position independent code */
1736 static void fix_pic_symconsts(ir_node *node, void *data)
1737 {
1738         ir_graph         *irg = get_irn_irg(node);
1739         be_main_env_t    *be  = be_get_irg_main_env(irg);
1740         ir_node          *pic_base;
1741         ir_node          *add;
1742         ir_node          *block;
1743         ir_mode          *mode;
1744         ir_node          *load;
1745         ir_node          *load_res;
1746         int               arity, i;
1747         (void) data;
1748
1749         arity = get_irn_arity(node);
1750         for (i = 0; i < arity; ++i) {
1751                 dbg_info  *dbgi;
1752                 ir_node   *pred = get_irn_n(node, i);
1753                 ir_entity *entity;
1754                 ir_entity *pic_symbol;
1755                 ir_node   *pic_symconst;
1756
1757                 if (!is_SymConst(pred))
1758                         continue;
1759
1760                 entity = get_SymConst_entity(pred);
1761                 block  = get_nodes_block(pred);
1762
1763                 /* calls can jump to relative addresses, so we can directly jump to
1764                    the (relatively) known call address or the trampoline */
1765                 if (i == 1 && is_Call(node)) {
1766                         ir_entity *trampoline;
1767                         ir_node   *trampoline_const;
1768
1769                         if (can_address_relative(entity))
1770                                 continue;
1771
1772                         dbgi             = get_irn_dbg_info(pred);
1773                         trampoline       = get_trampoline(be, entity);
1774                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1775                                                                     trampoline);
1776                         set_irn_n(node, i, trampoline_const);
1777                         continue;
1778                 }
1779
1780                 /* everything else is accessed relative to EIP */
1781                 mode     = get_irn_mode(pred);
1782                 pic_base = get_pic_base(irg);
1783
1784                 /* all ok now for locally constructed stuff */
1785                 if (can_address_relative(entity)) {
1786                         ir_node *add = new_r_Add(block, pic_base, pred, mode);
1787
1788                         /* make sure the walker doesn't visit this add again */
1789                         mark_irn_visited(add);
1790                         set_irn_n(node, i, add);
1791                         continue;
1792                 }
1793
1794                 /* get entry from pic symbol segment */
1795                 dbgi         = get_irn_dbg_info(pred);
1796                 pic_symbol   = get_pic_symbol(be, entity);
1797                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1798                                                         pic_symbol);
1799                 add = new_r_Add(block, pic_base, pic_symconst, mode);
1800                 mark_irn_visited(add);
1801
1802                 /* we need an extra indirection for global data outside our current
1803                    module. The loads are always safe and can therefore float
1804                    and need no memory input */
1805                 load     = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1806                 load_res = new_r_Proj(load, mode, pn_Load_res);
1807
1808                 set_irn_n(node, i, load_res);
1809         }
1810 }
1811
1812 void be_abi_introduce(ir_graph *irg)
1813 {
1814         ir_node          *old_frame   = get_irg_frame(irg);
1815         const arch_env_t *arch_env    = be_get_irg_arch_env(irg);
1816         ir_entity        *entity      = get_irg_entity(irg);
1817         ir_type          *method_type = get_entity_type(entity);
1818         be_irg_t         *birg        = be_birg_from_irg(irg);
1819         struct obstack   *obst        = &birg->obst;
1820         ir_node          *dummy       = new_r_Dummy(irg,
1821                                                     arch_env->sp->reg_class->mode);
1822         unsigned          r;
1823
1824         /* determine allocatable registers */
1825         assert(birg->allocatable_regs == NULL);
1826         birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1827         for (r = 0; r < arch_env->n_registers; ++r) {
1828                 const arch_register_t *reg = &arch_env->registers[r];
1829                 if ( !(reg->type & arch_register_type_ignore)) {
1830                         rbitset_set(birg->allocatable_regs, r);
1831                 }
1832         }
1833
1834         /* Break here if backend provides a custom API. */
1835
1836         be_omit_fp        = be_options.omit_fp;
1837
1838         be_abi_irg_t env;
1839         env.keep_map     = pmap_create();
1840         env.call         = be_abi_call_new(arch_env->sp->reg_class);
1841         arch_env_get_call_abi(arch_env, method_type, env.call);
1842
1843         env.init_sp = dummy;
1844         env.calls   = NEW_ARR_F(ir_node*, 0);
1845
1846         assure_edges(irg);
1847
1848         if (be_options.pic) {
1849                 irg_walk_graph(irg, fix_pic_symconsts, NULL, NULL);
1850         }
1851
1852         /* Lower all call nodes in the IRG. */
1853         process_calls(irg, &env);
1854
1855         /* Process the IRG */
1856         modify_irg(irg, &env);
1857
1858         /* fix call inputs for state registers */
1859         fix_call_state_inputs(irg, &env);
1860
1861         be_abi_call_free(env.call);
1862
1863         /* We don't need the keep map anymore. */
1864         pmap_destroy(env.keep_map);
1865
1866         /* calls array is not needed anymore */
1867         DEL_ARR_F(env.calls);
1868
1869         /* reroute the stack origin of the calls to the true stack origin. */
1870         exchange(dummy, env.init_sp);
1871         exchange(old_frame, get_irg_frame(irg));
1872
1873         pmap_destroy(env.regs);
1874 }
1875
1876 void be_put_allocatable_regs(const ir_graph *irg,
1877                              const arch_register_class_t *cls, bitset_t *bs)
1878 {
1879         be_irg_t *birg             = be_birg_from_irg(irg);
1880         unsigned *allocatable_regs = birg->allocatable_regs;
1881         unsigned  i;
1882
1883         assert(bitset_size(bs) == cls->n_regs);
1884         bitset_clear_all(bs);
1885         for (i = 0; i < cls->n_regs; ++i) {
1886                 const arch_register_t *reg = &cls->regs[i];
1887                 if (rbitset_is_set(allocatable_regs, reg->global_index))
1888                         bitset_set(bs, i);
1889         }
1890 }
1891
1892 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1893                                    const arch_register_class_t *cls)
1894 {
1895         bitset_t *bs = bitset_alloca(cls->n_regs);
1896         be_put_allocatable_regs(irg, cls, bs);
1897         return bitset_popcount(bs);
1898 }
1899
1900 void be_set_allocatable_regs(const ir_graph *irg,
1901                              const arch_register_class_t *cls,
1902                              unsigned *raw_bitset)
1903 {
1904         be_irg_t *birg             = be_birg_from_irg(irg);
1905         unsigned *allocatable_regs = birg->allocatable_regs;
1906         unsigned  i;
1907
1908         rbitset_clear_all(raw_bitset, cls->n_regs);
1909         for (i = 0; i < cls->n_regs; ++i) {
1910                 const arch_register_t *reg = &cls->regs[i];
1911                 if (rbitset_is_set(allocatable_regs, reg->global_index))
1912                         rbitset_set(raw_bitset, i);
1913         }
1914 }
1915
1916 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
1917 void be_init_abi(void)
1918 {
1919         FIRM_DBG_REGISTER(dbg, "firm.be.abi");
1920 }