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