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