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