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                 set_nodes_block(nmem, get_nodes_block(store));
1514
1515                 /* move all entities to the frame type */
1516                 frame_tp = get_irg_frame_type(irg);
1517                 offset   = get_type_size_bytes(frame_tp);
1518
1519                 /* we will add new entities: set the layout to undefined */
1520                 assert(get_type_state(frame_tp) == layout_fixed);
1521                 set_type_state(frame_tp, layout_undefined);
1522                 for (entry = new_list; entry != NULL; entry = entry->next) {
1523                         ir_entity *ent = entry->ent;
1524
1525                         /* If the entity is still on the argument type, move it to the
1526                          * frame type.
1527                          * This happens if the value_param type was build due to compound
1528                          * params. */
1529                         if (get_entity_owner(ent) != frame_tp) {
1530                                 ir_type  *tp   = get_entity_type(ent);
1531                                 unsigned align = get_type_alignment_bytes(tp);
1532
1533                                 offset += align - 1;
1534                                 offset &= ~(align - 1);
1535                                 set_entity_owner(ent, frame_tp);
1536                                 /* must be automatic to set a fixed layout */
1537                                 set_entity_offset(ent, offset);
1538                                 offset += get_type_size_bytes(tp);
1539                         }
1540                 }
1541                 set_type_size_bytes(frame_tp, offset);
1542                 /* fix the layout again */
1543                 set_type_state(frame_tp, layout_fixed);
1544         }
1545 }
1546
1547 /**
1548  * The start block has no jump, instead it has an initial exec Proj.
1549  * The backend wants to handle all blocks the same way, so we replace
1550  * the out cfg edge with a real jump.
1551  */
1552 static void fix_start_block(ir_graph *irg)
1553 {
1554         ir_node *initial_X   = get_irg_initial_exec(irg);
1555         ir_node *start_block = get_irg_start_block(irg);
1556         ir_node *jmp         = new_r_Jmp(start_block);
1557
1558         assert(is_Proj(initial_X));
1559         exchange(initial_X, jmp);
1560         set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1561 }
1562
1563 /**
1564  * Update the entity of Sels to the outer value parameters.
1565  */
1566 static void update_outer_frame_sels(ir_node *irn, void *env)
1567 {
1568         lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)env;
1569         ir_node                *ptr;
1570         ir_entity              *ent;
1571         int                    pos = 0;
1572
1573         if (! is_Sel(irn))
1574                 return;
1575         ptr = get_Sel_ptr(irn);
1576         if (! is_arg_Proj(ptr))
1577                 return;
1578         if (get_Proj_proj(ptr) != ctx->static_link_pos)
1579                 return;
1580         ent   = get_Sel_entity(irn);
1581
1582         if (get_entity_owner(ent) == ctx->value_tp) {
1583                 /* replace by its copy from the argument type */
1584                 pos = get_struct_member_index(ctx->value_tp, ent);
1585                 ent = get_argument_entity(ent, ctx);
1586                 set_Sel_entity(irn, ent);
1587
1588                 /* check, if we have not seen this entity before */
1589                 if (get_entity_link(ent) == NULL) {
1590                         ent_pos_pair pair;
1591
1592                         pair.ent  = ent;
1593                         pair.pos  = pos;
1594                         pair.next = NULL;
1595                         ARR_APP1(ent_pos_pair, ctx->value_param_list, pair);
1596                         /* just a mark */
1597                         set_entity_link(ent, ctx->value_param_list);
1598                 }
1599         }
1600 }
1601
1602 /**
1603  * Fix access to outer local variables.
1604  */
1605 static void fix_outer_variable_access(be_abi_irg_t *env,
1606                                       lower_frame_sels_env_t *ctx)
1607 {
1608         int      i;
1609         ir_graph *irg;
1610         (void) env;
1611
1612         for (i = get_class_n_members(ctx->frame_tp) - 1; i >= 0; --i) {
1613                 ir_entity *ent = get_class_member(ctx->frame_tp, i);
1614
1615                 if (! is_method_entity(ent))
1616                         continue;
1617
1618                 irg = get_entity_irg(ent);
1619                 if (irg == NULL)
1620                         continue;
1621
1622                 /*
1623                  * FIXME: find the number of the static link parameter
1624                  * for now we assume 0 here
1625                  */
1626                 ctx->static_link_pos = 0;
1627
1628                 irg_walk_graph(irg, NULL, update_outer_frame_sels, ctx);
1629         }
1630 }
1631
1632 /**
1633  * Modify the irg itself and the frame type.
1634  */
1635 static void modify_irg(ir_graph *irg)
1636 {
1637         be_abi_irg_t          *env          = be_get_irg_abi(irg);
1638         be_abi_call_t         *call         = env->call;
1639         const arch_env_t      *arch_env     = be_get_irg_arch_env(irg);
1640         const arch_register_t *sp           = arch_env->sp;
1641         ir_type               *method_type  = get_entity_type(get_irg_entity(irg));
1642         be_irg_t              *birg         = be_birg_from_irg(irg);
1643         struct obstack        *obst         = be_get_be_obst(irg);
1644         be_stack_layout_t     *stack_layout = be_get_irg_stack_layout(irg);
1645         ir_node *end;
1646         ir_node *old_mem;
1647         ir_node *new_mem_proj;
1648         ir_node *mem;
1649
1650         int n_params;
1651         int i, n;
1652         unsigned j;
1653         unsigned frame_size;
1654
1655         reg_node_map_t *rm;
1656         const arch_register_t *fp_reg;
1657         ir_node *frame_pointer;
1658         ir_node *start_bl;
1659         ir_node **args;
1660         ir_node *arg_tuple;
1661         const ir_edge_t *edge;
1662         ir_type *arg_type, *bet_type, *tp;
1663         lower_frame_sels_env_t ctx;
1664         ir_entity **param_map;
1665
1666         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1667
1668         old_mem = get_irg_initial_mem(irg);
1669
1670         irp_reserve_resources(irp, IR_RESOURCE_ENTITY_LINK);
1671
1672         /* set the links of all frame entities to NULL, we use it
1673            to detect if an entity is already linked in the value_param_list */
1674         tp = get_method_value_param_type(method_type);
1675         ctx.value_tp = tp;
1676         if (tp != NULL) {
1677                 /* clear the links of the clone type, let the
1678                    original entities point to its clones */
1679                 for (i = get_struct_n_members(tp) - 1; i >= 0; --i) {
1680                         ir_entity *mem  = get_struct_member(tp, i);
1681                         set_entity_link(mem, NULL);
1682                 }
1683         }
1684
1685         arg_type = compute_arg_type(env, irg, call, method_type, tp, &param_map);
1686
1687         /* Convert the Sel nodes in the irg to frame addr nodes: */
1688         ctx.value_param_list = NEW_ARR_F(ent_pos_pair, 0);
1689         ctx.frame            = get_irg_frame(irg);
1690         ctx.sp_class         = arch_env->sp->reg_class;
1691         ctx.link_class       = arch_env->link_class;
1692         ctx.frame_tp         = get_irg_frame_type(irg);
1693
1694         /* layout the stackframe now */
1695         if (get_type_state(ctx.frame_tp) == layout_undefined) {
1696                 default_layout_compound_type(ctx.frame_tp);
1697         }
1698
1699         /* we will possible add new entities to the frame: set the layout to undefined */
1700         assert(get_type_state(ctx.frame_tp) == layout_fixed);
1701         set_type_state(ctx.frame_tp, layout_undefined);
1702
1703         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1704
1705         /* fix the frame type layout again */
1706         set_type_state(ctx.frame_tp, layout_fixed);
1707         /* align stackframe to 4 byte */
1708         frame_size = get_type_size_bytes(ctx.frame_tp);
1709         if (frame_size % 4 != 0) {
1710                 set_type_size_bytes(ctx.frame_tp, frame_size + 4 - (frame_size % 4));
1711         }
1712
1713         env->regs  = pmap_create();
1714
1715         n_params = get_method_n_params(method_type);
1716         args     = OALLOCNZ(obst, ir_node*, n_params);
1717
1718         /*
1719          * for inner function we must now fix access to outer frame entities.
1720          */
1721         fix_outer_variable_access(env, &ctx);
1722
1723         /* Check if a value parameter is transmitted as a register.
1724          * This might happen if the address of an parameter is taken which is
1725          * transmitted in registers.
1726          *
1727          * Note that on some architectures this case must be handled specially
1728          * because the place of the backing store is determined by their ABI.
1729          *
1730          * In the default case we move the entity to the frame type and create
1731          * a backing store into the first block.
1732          */
1733         fix_address_of_parameter_access(env, irg, ctx.value_param_list);
1734
1735         DEL_ARR_F(ctx.value_param_list);
1736         irp_free_resources(irp, IR_RESOURCE_ENTITY_LINK);
1737
1738         /* Fill the argument vector */
1739         arg_tuple = get_irg_args(irg);
1740         foreach_out_edge(arg_tuple, edge) {
1741                 ir_node *irn = get_edge_src_irn(edge);
1742                 if (! is_Anchor(irn)) {
1743                         int nr       = get_Proj_proj(irn);
1744                         args[nr]     = irn;
1745                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1746                 }
1747         }
1748
1749         stack_layout->sp_relative = call->flags.bits.try_omit_fp;
1750         bet_type = call->cb->get_between_type(irg);
1751         stack_frame_init(stack_layout, arg_type, bet_type,
1752                          get_irg_frame_type(irg), param_map);
1753
1754         /* Count the register params and add them to the number of Projs for the RegParams node */
1755         for (i = 0; i < n_params; ++i) {
1756                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1757                 if (arg->in_reg && args[i]) {
1758                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1759                         assert(i == get_Proj_proj(args[i]));
1760
1761                         /* For now, associate the register with the old Proj from Start representing that argument. */
1762                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1763                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1764                 }
1765         }
1766
1767         /* Collect all callee-save registers */
1768         for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1769                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1770                 for (j = 0; j < cls->n_regs; ++j) {
1771                         const arch_register_t *reg = &cls->regs[j];
1772                         if (reg->type & (arch_register_type_callee_save | arch_register_type_state)) {
1773                                 pmap_insert(env->regs, (void *) reg, NULL);
1774                         }
1775                 }
1776         }
1777
1778         fp_reg = call->flags.bits.try_omit_fp ? arch_env->sp : arch_env->bp;
1779         rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1780
1781         /* handle start block here (place a jump in the block) */
1782         fix_start_block(irg);
1783
1784         pmap_insert(env->regs, (void *) sp, NULL);
1785         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1786         start_bl   = get_irg_start_block(irg);
1787         env->start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1788         set_irg_start(irg, env->start);
1789
1790         /*
1791          * make proj nodes for the callee save registers.
1792          * memorize them, since Return nodes get those as inputs.
1793          *
1794          * Note, that if a register corresponds to an argument, the regs map
1795          * contains the old Proj from start for that argument.
1796          */
1797         rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1798         reg_map_to_arr(rm, env->regs);
1799         for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1800                 const arch_register_t    *reg      = rm[i].reg;
1801                 ir_mode                  *mode     = reg->reg_class->mode;
1802                 long                      nr       = i;
1803                 arch_register_req_type_t  add_type = arch_register_req_type_none;
1804                 ir_node                  *proj;
1805
1806                 if (reg == sp)
1807                         add_type |= arch_register_req_type_produces_sp;
1808                 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1809                         add_type |= arch_register_req_type_ignore;
1810                 }
1811
1812                 assert(nr >= 0);
1813                 proj = new_r_Proj(env->start, mode, nr + 1);
1814                 pmap_insert(env->regs, (void *) reg, proj);
1815                 be_set_constr_single_reg_out(env->start, nr + 1, reg, add_type);
1816                 arch_set_irn_register(proj, reg);
1817
1818                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1819         }
1820
1821         /* create a new initial memory proj */
1822         assert(is_Proj(old_mem));
1823         arch_set_out_register_req(env->start, 0, arch_no_register_req);
1824         new_mem_proj = new_r_Proj(env->start, mode_M, 0);
1825         mem = new_mem_proj;
1826         set_irg_initial_mem(irg, mem);
1827
1828         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1829
1830         /* set new frame_pointer */
1831         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1832         set_irg_frame(irg, frame_pointer);
1833
1834         /* rewire old mem users to new mem */
1835         exchange(old_mem, mem);
1836
1837         /* keep the mem (for functions with an endless loop = no return) */
1838         keep_alive(mem);
1839
1840         set_irg_initial_mem(irg, mem);
1841
1842         /* Now, introduce stack param nodes for all parameters passed on the stack */
1843         for (i = 0; i < n_params; ++i) {
1844                 ir_node *arg_proj = args[i];
1845                 ir_node *repl     = NULL;
1846
1847                 if (arg_proj != NULL) {
1848                         be_abi_call_arg_t *arg;
1849                         ir_type *param_type;
1850                         int     nr = get_Proj_proj(arg_proj);
1851                         ir_mode *mode;
1852
1853                         nr         = MIN(nr, n_params);
1854                         arg        = get_call_arg(call, 0, nr, 1);
1855                         param_type = get_method_param_type(method_type, nr);
1856
1857                         if (arg->in_reg) {
1858                                 repl = (ir_node*)pmap_get(env->regs, arg->reg);
1859                         } else if (arg->on_stack) {
1860                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1861
1862                                 /* For atomic parameters which are actually used, we create a Load node. */
1863                                 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1864                                         ir_mode *mode      = get_type_mode(param_type);
1865                                         ir_mode *load_mode = arg->load_mode;
1866                                         ir_node *nomem     = get_irg_no_mem(irg);
1867
1868                                         ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1869                                         repl = new_r_Proj(load, load_mode, pn_Load_res);
1870
1871                                         if (mode != load_mode) {
1872                                                 repl = new_r_Conv(start_bl, repl, mode);
1873                                         }
1874                                 } else {
1875                                         /* The stack parameter is not primitive (it is a struct or array),
1876                                          * we thus will create a node representing the parameter's address
1877                                          * on the stack. */
1878                                         repl = addr;
1879                                 }
1880                         }
1881
1882                         assert(repl != NULL);
1883
1884                         /* Beware: the mode of the register parameters is always the mode of the register class
1885                            which may be wrong. Add Conv's then. */
1886                         mode = get_irn_mode(args[i]);
1887                         if (mode != get_irn_mode(repl)) {
1888                                 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1889                         }
1890                         exchange(args[i], repl);
1891                 }
1892         }
1893
1894         /* the arg proj is not needed anymore now and should be only used by the anchor */
1895         assert(get_irn_n_edges(arg_tuple) == 1);
1896         kill_node(arg_tuple);
1897         set_irg_args(irg, new_r_Bad(irg, mode_T));
1898
1899         /* All Return nodes hang on the End node, so look for them there. */
1900         end = get_irg_end_block(irg);
1901         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1902                 ir_node *irn = get_Block_cfgpred(end, i);
1903
1904                 if (is_Return(irn)) {
1905                         ir_node *blk = get_nodes_block(irn);
1906                         ir_node *mem = get_Return_mem(irn);
1907                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1908                         exchange(irn, ret);
1909                 }
1910         }
1911
1912         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1913            the code is dead and will never be executed. */
1914 }
1915
1916 /** Fix the state inputs of calls that still hang on unknowns */
1917 static void fix_call_state_inputs(ir_graph *irg)
1918 {
1919         be_abi_irg_t     *env      = be_get_irg_abi(irg);
1920         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1921         int i, n, n_states;
1922         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1923
1924         /* Collect caller save registers */
1925         n = arch_env->n_register_classes;
1926         for (i = 0; i < n; ++i) {
1927                 unsigned j;
1928                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1929                 for (j = 0; j < cls->n_regs; ++j) {
1930                         const arch_register_t *reg = arch_register_for_index(cls, j);
1931                         if (reg->type & arch_register_type_state) {
1932                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1933                         }
1934                 }
1935         }
1936
1937         n = ARR_LEN(env->calls);
1938         n_states = ARR_LEN(stateregs);
1939         for (i = 0; i < n; ++i) {
1940                 int s, arity;
1941                 ir_node *call = env->calls[i];
1942
1943                 arity = get_irn_arity(call);
1944
1945                 /* the state reg inputs are the last n inputs of the calls */
1946                 for (s = 0; s < n_states; ++s) {
1947                         int inp = arity - n_states + s;
1948                         const arch_register_t *reg = stateregs[s];
1949                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1950
1951                         set_irn_n(call, inp, regnode);
1952                 }
1953         }
1954
1955         DEL_ARR_F(stateregs);
1956 }
1957
1958 /**
1959  * Create a trampoline entity for the given method.
1960  */
1961 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1962 {
1963         ir_type   *type   = get_entity_type(method);
1964         ident     *old_id = get_entity_ld_ident(method);
1965         ident     *id     = id_mangle3("", old_id, "$stub");
1966         ir_type   *parent = be->pic_trampolines_type;
1967         ir_entity *ent    = new_entity(parent, old_id, type);
1968         set_entity_ld_ident(ent, id);
1969         set_entity_visibility(ent, ir_visibility_private);
1970
1971         return ent;
1972 }
1973
1974 /**
1975  * Returns the trampoline entity for the given method.
1976  */
1977 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1978 {
1979         ir_entity *result = (ir_entity*)pmap_get(env->ent_trampoline_map, method);
1980         if (result == NULL) {
1981                 result = create_trampoline(env, method);
1982                 pmap_insert(env->ent_trampoline_map, method, result);
1983         }
1984
1985         return result;
1986 }
1987
1988 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1989 {
1990         ident     *old_id = get_entity_ld_ident(entity);
1991         ident     *id     = id_mangle3("", old_id, "$non_lazy_ptr");
1992         ir_type   *e_type = get_entity_type(entity);
1993         ir_type   *type   = new_type_pointer(e_type);
1994         ir_type   *parent = be->pic_symbols_type;
1995         ir_entity *ent    = new_entity(parent, old_id, type);
1996         set_entity_ld_ident(ent, id);
1997         set_entity_visibility(ent, ir_visibility_private);
1998
1999         return ent;
2000 }
2001
2002 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
2003 {
2004         ir_entity *result = (ir_entity*)pmap_get(env->ent_pic_symbol_map, entity);
2005         if (result == NULL) {
2006                 result = create_pic_symbol(env, entity);
2007                 pmap_insert(env->ent_pic_symbol_map, entity, result);
2008         }
2009
2010         return result;
2011 }
2012
2013
2014
2015 /**
2016  * Returns non-zero if a given entity can be accessed using a relative address.
2017  */
2018 static int can_address_relative(ir_entity *entity)
2019 {
2020         return get_entity_visibility(entity) != ir_visibility_external
2021                 && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
2022 }
2023
2024 static ir_node *get_pic_base(ir_graph *irg)
2025 {
2026         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
2027         if (arch_env->impl->get_pic_base == NULL)
2028                 return NULL;
2029         return arch_env->impl->get_pic_base(irg);
2030 }
2031
2032 /** patches SymConsts to work in position independent code */
2033 static void fix_pic_symconsts(ir_node *node, void *data)
2034 {
2035         ir_graph         *irg = get_irn_irg(node);
2036         be_main_env_t    *be  = be_get_irg_main_env(irg);
2037         ir_node          *pic_base;
2038         ir_node          *add;
2039         ir_node          *block;
2040         ir_mode          *mode;
2041         ir_node          *load;
2042         ir_node          *load_res;
2043         int               arity, i;
2044         (void) data;
2045
2046         arity = get_irn_arity(node);
2047         for (i = 0; i < arity; ++i) {
2048                 dbg_info  *dbgi;
2049                 ir_node   *pred = get_irn_n(node, i);
2050                 ir_entity *entity;
2051                 ir_entity *pic_symbol;
2052                 ir_node   *pic_symconst;
2053
2054                 if (!is_SymConst(pred))
2055                         continue;
2056
2057                 entity = get_SymConst_entity(pred);
2058                 block  = get_nodes_block(pred);
2059
2060                 /* calls can jump to relative addresses, so we can directly jump to
2061                    the (relatively) known call address or the trampoline */
2062                 if (i == 1 && is_Call(node)) {
2063                         ir_entity *trampoline;
2064                         ir_node   *trampoline_const;
2065
2066                         if (can_address_relative(entity))
2067                                 continue;
2068
2069                         dbgi             = get_irn_dbg_info(pred);
2070                         trampoline       = get_trampoline(be, entity);
2071                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2072                                                                     trampoline);
2073                         set_irn_n(node, i, trampoline_const);
2074                         continue;
2075                 }
2076
2077                 /* everything else is accessed relative to EIP */
2078                 mode     = get_irn_mode(pred);
2079                 pic_base = get_pic_base(irg);
2080
2081                 /* all ok now for locally constructed stuff */
2082                 if (can_address_relative(entity)) {
2083                         ir_node *add = new_r_Add(block, pic_base, pred, mode);
2084
2085                         /* make sure the walker doesn't visit this add again */
2086                         mark_irn_visited(add);
2087                         set_irn_n(node, i, add);
2088                         continue;
2089                 }
2090
2091                 /* get entry from pic symbol segment */
2092                 dbgi         = get_irn_dbg_info(pred);
2093                 pic_symbol   = get_pic_symbol(be, entity);
2094                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2095                                                         pic_symbol);
2096                 add = new_r_Add(block, pic_base, pic_symconst, mode);
2097                 mark_irn_visited(add);
2098
2099                 /* we need an extra indirection for global data outside our current
2100                    module. The loads are always safe and can therefore float
2101                    and need no memory input */
2102                 load     = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
2103                 load_res = new_r_Proj(load, mode, pn_Load_res);
2104
2105                 set_irn_n(node, i, load_res);
2106         }
2107 }
2108
2109 void be_abi_introduce(ir_graph *irg)
2110 {
2111         be_abi_irg_t     *env         = XMALLOCZ(be_abi_irg_t);
2112         ir_node          *old_frame   = get_irg_frame(irg);
2113         be_options_t     *options     = be_get_irg_options(irg);
2114         const arch_env_t *arch_env    = be_get_irg_arch_env(irg);
2115         ir_entity        *entity      = get_irg_entity(irg);
2116         ir_type          *method_type = get_entity_type(entity);
2117         be_irg_t         *birg        = be_birg_from_irg(irg);
2118         struct obstack   *obst        = &birg->obst;
2119         ir_node          *dummy       = new_r_Dummy(irg,
2120                                                     arch_env->sp->reg_class->mode);
2121         unsigned          r;
2122
2123         /* determine allocatable registers */
2124         assert(birg->allocatable_regs == NULL);
2125         birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
2126         for (r = 0; r < arch_env->n_registers; ++r) {
2127                 const arch_register_t *reg = &arch_env->registers[r];
2128                 if ( !(reg->type & arch_register_type_ignore)) {
2129                         rbitset_set(birg->allocatable_regs, r);
2130                 }
2131         }
2132
2133         /* break here if backend provides a custom API.
2134          * Note: we shouldn't have to setup any be_abi_irg_t* stuff at all,
2135          * but need more cleanup to make this work
2136          */
2137         be_set_irg_abi(irg, env);
2138
2139         be_omit_fp      = options->omit_fp;
2140
2141         env->keep_map     = pmap_create();
2142         env->call         = be_abi_call_new(arch_env->sp->reg_class);
2143         arch_env_get_call_abi(arch_env, method_type, env->call);
2144
2145         env->init_sp = dummy;
2146         env->calls   = NEW_ARR_F(ir_node*, 0);
2147
2148         edges_assure(irg);
2149
2150         if (options->pic) {
2151                 irg_walk_graph(irg, fix_pic_symconsts, NULL, env);
2152         }
2153
2154         /* Lower all call nodes in the IRG. */
2155         process_calls(irg);
2156
2157         /* Process the IRG */
2158         modify_irg(irg);
2159
2160         /* fix call inputs for state registers */
2161         fix_call_state_inputs(irg);
2162
2163         /* We don't need the keep map anymore. */
2164         pmap_destroy(env->keep_map);
2165         env->keep_map = NULL;
2166
2167         /* calls array is not needed anymore */
2168         DEL_ARR_F(env->calls);
2169         env->calls = NULL;
2170
2171         /* reroute the stack origin of the calls to the true stack origin. */
2172         exchange(dummy, env->init_sp);
2173         exchange(old_frame, get_irg_frame(irg));
2174
2175         pmap_destroy(env->regs);
2176         env->regs = NULL;
2177 }
2178
2179 void be_abi_free(ir_graph *irg)
2180 {
2181         be_abi_irg_t *env = be_get_irg_abi(irg);
2182
2183         if (env->call != NULL)
2184                 be_abi_call_free(env->call);
2185         assert(env->regs == NULL);
2186         free(env);
2187
2188         be_set_irg_abi(irg, NULL);
2189 }
2190
2191 void be_put_allocatable_regs(const ir_graph *irg,
2192                              const arch_register_class_t *cls, bitset_t *bs)
2193 {
2194         be_irg_t *birg             = be_birg_from_irg(irg);
2195         unsigned *allocatable_regs = birg->allocatable_regs;
2196         unsigned  i;
2197
2198         assert(bitset_size(bs) == cls->n_regs);
2199         bitset_clear_all(bs);
2200         for (i = 0; i < cls->n_regs; ++i) {
2201                 const arch_register_t *reg = &cls->regs[i];
2202                 if (rbitset_is_set(allocatable_regs, reg->global_index))
2203                         bitset_set(bs, i);
2204         }
2205 }
2206
2207 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
2208                                    const arch_register_class_t *cls)
2209 {
2210         bitset_t *bs = bitset_alloca(cls->n_regs);
2211         be_put_allocatable_regs(irg, cls, bs);
2212         return bitset_popcount(bs);
2213 }
2214
2215 void be_set_allocatable_regs(const ir_graph *irg,
2216                              const arch_register_class_t *cls,
2217                              unsigned *raw_bitset)
2218 {
2219         be_irg_t *birg             = be_birg_from_irg(irg);
2220         unsigned *allocatable_regs = birg->allocatable_regs;
2221         unsigned  i;
2222
2223         rbitset_clear_all(raw_bitset, cls->n_regs);
2224         for (i = 0; i < cls->n_regs; ++i) {
2225                 const arch_register_t *reg = &cls->regs[i];
2226                 if (rbitset_is_set(allocatable_regs, reg->global_index))
2227                         rbitset_set(raw_bitset, i);
2228         }
2229 }
2230
2231 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
2232 void be_init_abi(void)
2233 {
2234         FIRM_DBG_REGISTER(dbg, "firm.be.abi");
2235 }