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