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