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  * @param bl    the block where the be_Retun should be placed
1184  * @param mem   the current memory
1185  * @param n_res number of return results
1186  */
1187 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1188                 ir_node *mem, int n_res)
1189 {
1190         be_abi_call_t    *call     = env->call;
1191         ir_graph         *irg      = get_Block_irg(bl);
1192         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1193         pmap *reg_map  = pmap_create();
1194         ir_node *keep  = pmap_get(ir_node, env->keep_map, bl);
1195         size_t in_max;
1196         ir_node *ret;
1197         int i, n;
1198         unsigned pop;
1199         ir_node **in;
1200         ir_node *stack;
1201         const arch_register_t **regs;
1202         pmap_entry *ent;
1203
1204         /*
1205                 get the valid stack node in this block.
1206                 If we had a call in that block there is a Keep constructed by process_calls()
1207                 which points to the last stack modification in that block. we'll use
1208                 it then. Else we use the stack from the start block and let
1209                 the ssa construction fix the usage.
1210         */
1211         stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1212         if (keep) {
1213                 stack = get_irn_n(keep, 0);
1214                 kill_node(keep);
1215                 remove_End_keepalive(get_irg_end(irg), keep);
1216         }
1217
1218         /* Insert results for Return into the register map. */
1219         for (i = 0; i < n_res; ++i) {
1220                 ir_node *res           = get_Return_res(irn, i);
1221                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1222                 assert(arg->in_reg && "return value must be passed in register");
1223                 pmap_insert(reg_map, (void *) arg->reg, res);
1224         }
1225
1226         /* Add uses of the callee save registers. */
1227         foreach_pmap(env->regs, ent) {
1228                 const arch_register_t *reg = (const arch_register_t*)ent->key;
1229                 if ((reg->type & arch_register_type_ignore) || arch_register_is_callee_save(arch_env, reg))
1230                         pmap_insert(reg_map, ent->key, ent->value);
1231         }
1232
1233         be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1234
1235         /*
1236                 Maximum size of the in array for Return nodes is
1237                 return args + callee save/ignore registers + memory + stack pointer
1238         */
1239         in_max = pmap_count(reg_map) + n_res + 2;
1240
1241         in   = ALLOCAN(ir_node*,               in_max);
1242         regs = ALLOCAN(arch_register_t const*, in_max);
1243
1244         in[0]   = mem;
1245         in[1]   = be_abi_reg_map_get(reg_map, arch_env->sp);
1246         regs[0] = NULL;
1247         regs[1] = arch_env->sp;
1248         n       = 2;
1249
1250         /* clear SP entry, since it has already been grown. */
1251         pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1252         for (i = 0; i < n_res; ++i) {
1253                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1254
1255                 in[n]     = be_abi_reg_map_get(reg_map, arg->reg);
1256                 regs[n++] = arg->reg;
1257
1258                 /* Clear the map entry to mark the register as processed. */
1259                 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1260         }
1261
1262         /* grow the rest of the stuff. */
1263         foreach_pmap(reg_map, ent) {
1264                 if (ent->value) {
1265                         in[n]     = (ir_node*)ent->value;
1266                         regs[n++] = (const arch_register_t*)ent->key;
1267                 }
1268         }
1269
1270         /* The in array for the new back end return is now ready. */
1271         dbg_info *const dbgi = get_irn_dbg_info(irn);
1272         /* we have to pop the shadow parameter in in case of struct returns */
1273         pop = call->pop;
1274         ret = be_new_Return(dbgi, irg, bl, n_res, pop, n, in);
1275
1276         /* Set the register classes of the return's parameter accordingly. */
1277         for (i = 0; i < n; ++i) {
1278                 if (regs[i] == NULL)
1279                         continue;
1280
1281                 be_set_constr_single_reg_in(ret, i, regs[i], arch_register_req_type_none);
1282         }
1283
1284         /* Free the space of the Epilog's in array and the register <-> proj map. */
1285         pmap_destroy(reg_map);
1286
1287         return ret;
1288 }
1289
1290 typedef struct lower_frame_sels_env_t {
1291         ir_node      *frame;                     /**< the current frame */
1292         const arch_register_class_t *sp_class;   /**< register class of the stack pointer */
1293 } lower_frame_sels_env_t;
1294
1295 /**
1296  * Walker: Replaces Sels of frame type and
1297  * value param type entities by FrameAddress.
1298  * Links all used entities.
1299  */
1300 static void lower_frame_sels_walker(ir_node *irn, void *data)
1301 {
1302         lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1303
1304         if (is_Sel(irn)) {
1305                 ir_node *ptr = get_Sel_ptr(irn);
1306
1307                 if (ptr == ctx->frame) {
1308                         ir_entity    *ent = get_Sel_entity(irn);
1309                         ir_node      *bl  = get_nodes_block(irn);
1310                         ir_node      *nw;
1311
1312                         nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1313                         exchange(irn, nw);
1314                 }
1315         }
1316 }
1317
1318 /**
1319  * The start block has no jump, instead it has an initial exec Proj.
1320  * The backend wants to handle all blocks the same way, so we replace
1321  * the out cfg edge with a real jump.
1322  */
1323 static void fix_start_block(ir_graph *irg)
1324 {
1325         ir_node *initial_X   = get_irg_initial_exec(irg);
1326         ir_node *start_block = get_irg_start_block(irg);
1327         ir_node *jmp         = new_r_Jmp(start_block);
1328
1329         assert(is_Proj(initial_X));
1330         exchange(initial_X, jmp);
1331         set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1332
1333         /* merge start block with successor if possible */
1334         {
1335                 foreach_out_edge(jmp, edge) {
1336                         ir_node *succ = get_edge_src_irn(edge);
1337                         if (!is_Block(succ))
1338                                 continue;
1339
1340                         if (get_irn_arity(succ) == 1) {
1341                                 exchange(succ, start_block);
1342                         }
1343                         break;
1344                 }
1345         }
1346 }
1347
1348 /**
1349  * Modify the irg itself and the frame type.
1350  */
1351 static void modify_irg(ir_graph *const irg, be_abi_irg_t *const env)
1352 {
1353         be_abi_call_t         *call         = env->call;
1354         const arch_env_t      *arch_env     = be_get_irg_arch_env(irg);
1355         const arch_register_t *sp           = arch_env->sp;
1356         ir_type               *method_type  = get_entity_type(get_irg_entity(irg));
1357         be_irg_t              *birg         = be_birg_from_irg(irg);
1358         struct obstack        *obst         = be_get_be_obst(irg);
1359         be_stack_layout_t     *stack_layout = be_get_irg_stack_layout(irg);
1360         ir_node *end;
1361         ir_node *old_mem;
1362         ir_node *new_mem_proj;
1363         ir_node *mem;
1364
1365         int n_params;
1366         int i, n;
1367         unsigned j;
1368
1369         reg_node_map_t *rm;
1370         const arch_register_t *fp_reg;
1371         ir_node *frame_pointer;
1372         ir_node *start_bl;
1373         ir_node **args;
1374         ir_node *arg_tuple;
1375         ir_type *arg_type, *bet_type;
1376         lower_frame_sels_env_t ctx;
1377
1378         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1379
1380         old_mem = get_irg_initial_mem(irg);
1381
1382         irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1383
1384         arg_type = compute_arg_type(irg, call, method_type);
1385
1386         /* Convert the Sel nodes in the irg to frame addr nodes: */
1387         ctx.frame    = get_irg_frame(irg);
1388         ctx.sp_class = arch_env->sp->reg_class;
1389
1390         ir_type *const frame_tp = get_irg_frame_type(irg);
1391         /* layout the stackframe now */
1392         if (get_type_state(frame_tp) == layout_undefined) {
1393                 default_layout_compound_type(frame_tp);
1394         }
1395
1396         /* align stackframe */
1397         unsigned const alignment  = 1U << arch_env->stack_alignment;
1398         unsigned const frame_size = round_up2(get_type_size_bytes(frame_tp), alignment);
1399         set_type_size_bytes(frame_tp, frame_size);
1400
1401         env->regs  = pmap_create();
1402
1403         n_params = get_method_n_params(method_type);
1404         args     = OALLOCNZ(obst, ir_node*, n_params);
1405
1406         be_add_parameter_entity_stores(irg);
1407
1408         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1409
1410         irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1411
1412         /* Fill the argument vector */
1413         arg_tuple = get_irg_args(irg);
1414         foreach_out_edge(arg_tuple, edge) {
1415                 ir_node *irn = get_edge_src_irn(edge);
1416                 if (! is_Anchor(irn)) {
1417                         int nr       = get_Proj_proj(irn);
1418                         args[nr]     = irn;
1419                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1420                 }
1421         }
1422
1423         stack_layout->sp_relative = call->flags.try_omit_fp;
1424         bet_type = call->cb->get_between_type(irg);
1425         stack_frame_init(stack_layout, arg_type, bet_type,
1426                          get_irg_frame_type(irg));
1427
1428         /* Count the register params and add them to the number of Projs for the RegParams node */
1429         for (i = 0; i < n_params; ++i) {
1430                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1431                 if (arg->in_reg && args[i]) {
1432                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1433                         assert(i == get_Proj_proj(args[i]));
1434
1435                         /* For now, associate the register with the old Proj from Start representing that argument. */
1436                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1437                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1438                 }
1439         }
1440
1441         /* Collect all callee-save registers */
1442         for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1443                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1444                 for (j = 0; j < cls->n_regs; ++j) {
1445                         const arch_register_t *reg = &cls->regs[j];
1446                         if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1447                                 pmap_insert(env->regs, (void *) reg, NULL);
1448                         }
1449                 }
1450         }
1451
1452         fp_reg = call->flags.try_omit_fp ? arch_env->sp : arch_env->bp;
1453         rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1454
1455         /* handle start block here (place a jump in the block) */
1456         fix_start_block(irg);
1457
1458         pmap_insert(env->regs, (void *) sp, NULL);
1459         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1460         start_bl   = get_irg_start_block(irg);
1461         ir_node *const start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1462         set_irg_start(irg, start);
1463
1464         /*
1465          * make proj nodes for the callee save registers.
1466          * memorize them, since Return nodes get those as inputs.
1467          *
1468          * Note, that if a register corresponds to an argument, the regs map
1469          * contains the old Proj from start for that argument.
1470          */
1471         rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1472         reg_map_to_arr(rm, env->regs);
1473         for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1474                 const arch_register_t    *reg      = rm[i].reg;
1475                 ir_mode                  *mode     = reg->reg_class->mode;
1476                 long                      nr       = i;
1477                 arch_register_req_type_t  add_type = arch_register_req_type_none;
1478                 ir_node                  *proj;
1479
1480                 if (reg == sp)
1481                         add_type |= arch_register_req_type_produces_sp;
1482                 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1483                         add_type |= arch_register_req_type_ignore;
1484                 }
1485
1486                 assert(nr >= 0);
1487                 proj = new_r_Proj(start, mode, nr + 1);
1488                 pmap_insert(env->regs, (void *) reg, proj);
1489                 be_set_constr_single_reg_out(start, nr + 1, reg, add_type);
1490                 arch_set_irn_register(proj, reg);
1491
1492                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1493         }
1494
1495         /* create a new initial memory proj */
1496         assert(is_Proj(old_mem));
1497         arch_set_irn_register_req_out(start, 0, arch_no_register_req);
1498         new_mem_proj = new_r_Proj(start, mode_M, 0);
1499         mem = new_mem_proj;
1500         set_irg_initial_mem(irg, mem);
1501
1502         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1503
1504         /* set new frame_pointer */
1505         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1506         set_irg_frame(irg, frame_pointer);
1507
1508         /* rewire old mem users to new mem */
1509         exchange(old_mem, mem);
1510
1511         /* keep the mem (for functions with an endless loop = no return) */
1512         keep_alive(mem);
1513
1514         set_irg_initial_mem(irg, mem);
1515
1516         /* Now, introduce stack param nodes for all parameters passed on the stack */
1517         for (i = 0; i < n_params; ++i) {
1518                 ir_node *arg_proj = args[i];
1519                 ir_node *repl     = NULL;
1520
1521                 if (arg_proj != NULL) {
1522                         be_abi_call_arg_t *arg;
1523                         ir_type *param_type;
1524                         int     nr = get_Proj_proj(arg_proj);
1525                         ir_mode *mode;
1526
1527                         nr         = MIN(nr, n_params);
1528                         arg        = get_call_arg(call, 0, nr, 1);
1529                         param_type = get_method_param_type(method_type, nr);
1530
1531                         if (arg->in_reg) {
1532                                 repl = pmap_get(ir_node, env->regs, arg->reg);
1533                         } else {
1534                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1535
1536                                 /* For atomic parameters which are actually used, we create a Load node. */
1537                                 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1538                                         ir_mode *mode      = get_type_mode(param_type);
1539                                         ir_mode *load_mode = arg->load_mode;
1540                                         ir_node *nomem     = get_irg_no_mem(irg);
1541
1542                                         ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1543                                         repl = new_r_Proj(load, load_mode, pn_Load_res);
1544
1545                                         if (mode != load_mode) {
1546                                                 repl = new_r_Conv(start_bl, repl, mode);
1547                                         }
1548                                 } else {
1549                                         /* The stack parameter is not primitive (it is a struct or array),
1550                                          * we thus will create a node representing the parameter's address
1551                                          * on the stack. */
1552                                         repl = addr;
1553                                 }
1554                         }
1555
1556                         assert(repl != NULL);
1557
1558                         /* Beware: the mode of the register parameters is always the mode of the register class
1559                            which may be wrong. Add Conv's then. */
1560                         mode = get_irn_mode(args[i]);
1561                         if (mode != get_irn_mode(repl)) {
1562                                 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1563                         }
1564                         exchange(args[i], repl);
1565                 }
1566         }
1567
1568         /* the arg proj is not needed anymore now and should be only used by the anchor */
1569         assert(get_irn_n_edges(arg_tuple) == 1);
1570         kill_node(arg_tuple);
1571         set_irg_args(irg, new_r_Bad(irg, mode_T));
1572
1573         /* All Return nodes hang on the End node, so look for them there. */
1574         end = get_irg_end_block(irg);
1575         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1576                 ir_node *irn = get_Block_cfgpred(end, i);
1577
1578                 if (is_Return(irn)) {
1579                         ir_node *blk = get_nodes_block(irn);
1580                         ir_node *mem = get_Return_mem(irn);
1581                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1582                         exchange(irn, ret);
1583                 }
1584         }
1585
1586         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1587            the code is dead and will never be executed. */
1588 }
1589
1590 /** Fix the state inputs of calls that still hang on unknowns */
1591 static void fix_call_state_inputs(ir_graph *const irg, be_abi_irg_t *const env)
1592 {
1593         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1594         int i, n, n_states;
1595         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1596
1597         /* Collect caller save registers */
1598         n = arch_env->n_register_classes;
1599         for (i = 0; i < n; ++i) {
1600                 unsigned j;
1601                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1602                 for (j = 0; j < cls->n_regs; ++j) {
1603                         const arch_register_t *reg = arch_register_for_index(cls, j);
1604                         if (reg->type & arch_register_type_state) {
1605                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1606                         }
1607                 }
1608         }
1609
1610         n = ARR_LEN(env->calls);
1611         n_states = ARR_LEN(stateregs);
1612         for (i = 0; i < n; ++i) {
1613                 int s, arity;
1614                 ir_node *call = env->calls[i];
1615
1616                 arity = get_irn_arity(call);
1617
1618                 /* the state reg inputs are the last n inputs of the calls */
1619                 for (s = 0; s < n_states; ++s) {
1620                         int inp = arity - n_states + s;
1621                         const arch_register_t *reg = stateregs[s];
1622                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1623
1624                         set_irn_n(call, inp, regnode);
1625                 }
1626         }
1627
1628         DEL_ARR_F(stateregs);
1629 }
1630
1631 /**
1632  * Create a trampoline entity for the given method.
1633  */
1634 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1635 {
1636         ir_type   *type   = get_entity_type(method);
1637         ident     *old_id = get_entity_ld_ident(method);
1638         ident     *id     = id_mangle3("", old_id, "$stub");
1639         ir_type   *parent = be->pic_trampolines_type;
1640         ir_entity *ent    = new_entity(parent, old_id, type);
1641         set_entity_ld_ident(ent, id);
1642         set_entity_visibility(ent, ir_visibility_private);
1643
1644         return ent;
1645 }
1646
1647 /**
1648  * Returns the trampoline entity for the given method.
1649  */
1650 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1651 {
1652         ir_entity *result = pmap_get(ir_entity, env->ent_trampoline_map, method);
1653         if (result == NULL) {
1654                 result = create_trampoline(env, method);
1655                 pmap_insert(env->ent_trampoline_map, method, result);
1656         }
1657
1658         return result;
1659 }
1660
1661 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1662 {
1663         ident     *old_id = get_entity_ld_ident(entity);
1664         ident     *id     = id_mangle3("", old_id, "$non_lazy_ptr");
1665         ir_type   *e_type = get_entity_type(entity);
1666         ir_type   *type   = new_type_pointer(e_type);
1667         ir_type   *parent = be->pic_symbols_type;
1668         ir_entity *ent    = new_entity(parent, old_id, type);
1669         set_entity_ld_ident(ent, id);
1670         set_entity_visibility(ent, ir_visibility_private);
1671
1672         return ent;
1673 }
1674
1675 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1676 {
1677         ir_entity *result = pmap_get(ir_entity, env->ent_pic_symbol_map, entity);
1678         if (result == NULL) {
1679                 result = create_pic_symbol(env, entity);
1680                 pmap_insert(env->ent_pic_symbol_map, entity, result);
1681         }
1682
1683         return result;
1684 }
1685
1686
1687
1688 /**
1689  * Returns non-zero if a given entity can be accessed using a relative address.
1690  */
1691 static int can_address_relative(ir_entity *entity)
1692 {
1693         return entity_has_definition(entity) && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1694 }
1695
1696 static ir_node *get_pic_base(ir_graph *irg)
1697 {
1698         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1699         if (arch_env->impl->get_pic_base == NULL)
1700                 return NULL;
1701         return arch_env->impl->get_pic_base(irg);
1702 }
1703
1704 /** patches SymConsts to work in position independent code */
1705 static void fix_pic_symconsts(ir_node *node, void *data)
1706 {
1707         ir_graph         *irg = get_irn_irg(node);
1708         be_main_env_t    *be  = be_get_irg_main_env(irg);
1709         ir_node          *pic_base;
1710         ir_node          *add;
1711         ir_node          *block;
1712         ir_mode          *mode;
1713         ir_node          *load;
1714         ir_node          *load_res;
1715         int               arity, i;
1716         (void) data;
1717
1718         arity = get_irn_arity(node);
1719         for (i = 0; i < arity; ++i) {
1720                 dbg_info  *dbgi;
1721                 ir_node   *pred = get_irn_n(node, i);
1722                 ir_entity *entity;
1723                 ir_entity *pic_symbol;
1724                 ir_node   *pic_symconst;
1725
1726                 if (!is_SymConst(pred))
1727                         continue;
1728
1729                 entity = get_SymConst_entity(pred);
1730                 block  = get_nodes_block(pred);
1731
1732                 /* calls can jump to relative addresses, so we can directly jump to
1733                    the (relatively) known call address or the trampoline */
1734                 if (i == 1 && is_Call(node)) {
1735                         ir_entity *trampoline;
1736                         ir_node   *trampoline_const;
1737
1738                         if (can_address_relative(entity))
1739                                 continue;
1740
1741                         dbgi             = get_irn_dbg_info(pred);
1742                         trampoline       = get_trampoline(be, entity);
1743                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1744                                                                     trampoline);
1745                         set_irn_n(node, i, trampoline_const);
1746                         continue;
1747                 }
1748
1749                 /* everything else is accessed relative to EIP */
1750                 mode     = get_irn_mode(pred);
1751                 pic_base = get_pic_base(irg);
1752
1753                 /* all ok now for locally constructed stuff */
1754                 if (can_address_relative(entity)) {
1755                         ir_node *add = new_r_Add(block, pic_base, pred, mode);
1756
1757                         /* make sure the walker doesn't visit this add again */
1758                         mark_irn_visited(add);
1759                         set_irn_n(node, i, add);
1760                         continue;
1761                 }
1762
1763                 /* get entry from pic symbol segment */
1764                 dbgi         = get_irn_dbg_info(pred);
1765                 pic_symbol   = get_pic_symbol(be, entity);
1766                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1767                                                         pic_symbol);
1768                 add = new_r_Add(block, pic_base, pic_symconst, mode);
1769                 mark_irn_visited(add);
1770
1771                 /* we need an extra indirection for global data outside our current
1772                    module. The loads are always safe and can therefore float
1773                    and need no memory input */
1774                 load     = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1775                 load_res = new_r_Proj(load, mode, pn_Load_res);
1776
1777                 set_irn_n(node, i, load_res);
1778         }
1779 }
1780
1781 void be_abi_introduce(ir_graph *irg)
1782 {
1783         ir_node          *old_frame   = get_irg_frame(irg);
1784         const arch_env_t *arch_env    = be_get_irg_arch_env(irg);
1785         ir_entity        *entity      = get_irg_entity(irg);
1786         ir_type          *method_type = get_entity_type(entity);
1787         be_irg_t         *birg        = be_birg_from_irg(irg);
1788         struct obstack   *obst        = &birg->obst;
1789         ir_node          *dummy       = new_r_Dummy(irg,
1790                                                     arch_env->sp->reg_class->mode);
1791         unsigned          r;
1792
1793         /* determine allocatable registers */
1794         assert(birg->allocatable_regs == NULL);
1795         birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1796         for (r = 0; r < arch_env->n_registers; ++r) {
1797                 const arch_register_t *reg = &arch_env->registers[r];
1798                 if ( !(reg->type & arch_register_type_ignore)) {
1799                         rbitset_set(birg->allocatable_regs, r);
1800                 }
1801         }
1802
1803         /* Break here if backend provides a custom API. */
1804
1805         be_abi_irg_t env;
1806         env.keep_map     = pmap_create();
1807         env.call         = be_abi_call_new();
1808         arch_env_get_call_abi(arch_env, method_type, env.call);
1809
1810         env.init_sp = dummy;
1811         env.calls   = NEW_ARR_F(ir_node*, 0);
1812
1813         assure_edges(irg);
1814
1815         if (be_options.pic) {
1816                 irg_walk_graph(irg, fix_pic_symconsts, NULL, NULL);
1817         }
1818
1819         /* Lower all call nodes in the IRG. */
1820         process_calls(irg, &env);
1821
1822         /* Process the IRG */
1823         modify_irg(irg, &env);
1824
1825         /* fix call inputs for state registers */
1826         fix_call_state_inputs(irg, &env);
1827
1828         be_abi_call_free(env.call);
1829
1830         /* We don't need the keep map anymore. */
1831         pmap_destroy(env.keep_map);
1832
1833         /* calls array is not needed anymore */
1834         DEL_ARR_F(env.calls);
1835
1836         /* reroute the stack origin of the calls to the true stack origin. */
1837         exchange(dummy, env.init_sp);
1838         exchange(old_frame, get_irg_frame(irg));
1839
1840         pmap_destroy(env.regs);
1841 }
1842
1843 void be_put_allocatable_regs(const ir_graph *irg,
1844                              const arch_register_class_t *cls, bitset_t *bs)
1845 {
1846         be_irg_t *birg             = be_birg_from_irg(irg);
1847         unsigned *allocatable_regs = birg->allocatable_regs;
1848         unsigned  i;
1849
1850         assert(bitset_size(bs) == cls->n_regs);
1851         bitset_clear_all(bs);
1852         for (i = 0; i < cls->n_regs; ++i) {
1853                 const arch_register_t *reg = &cls->regs[i];
1854                 if (rbitset_is_set(allocatable_regs, reg->global_index))
1855                         bitset_set(bs, i);
1856         }
1857 }
1858
1859 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1860                                    const arch_register_class_t *cls)
1861 {
1862         bitset_t *bs = bitset_alloca(cls->n_regs);
1863         be_put_allocatable_regs(irg, cls, bs);
1864         return bitset_popcount(bs);
1865 }
1866
1867 void be_set_allocatable_regs(const ir_graph *irg,
1868                              const arch_register_class_t *cls,
1869                              unsigned *raw_bitset)
1870 {
1871         be_irg_t *birg             = be_birg_from_irg(irg);
1872         unsigned *allocatable_regs = birg->allocatable_regs;
1873         unsigned  i;
1874
1875         rbitset_clear_all(raw_bitset, cls->n_regs);
1876         for (i = 0; i < cls->n_regs; ++i) {
1877                 const arch_register_t *reg = &cls->regs[i];
1878                 if (rbitset_is_set(allocatable_regs, reg->global_index))
1879                         rbitset_set(raw_bitset, i);
1880         }
1881 }
1882
1883 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
1884 void be_init_abi(void)
1885 {
1886         FIRM_DBG_REGISTER(dbg, "firm.be.abi");
1887 }