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