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

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