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