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