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

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