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