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