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