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