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

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