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

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