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

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