nsz Git - libfirm/blob - ir/be/beabi.c

   1 /*
   2  * Copyright (C) 1995-2008 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 #include "offset.h"
  30
  31 #include "irgopt.h"
  32
  33 #include "irgraph_t.h"
  34 #include "irnode_t.h"
  35 #include "ircons_t.h"
  36 #include "iredges_t.h"
  37 #include "irgmod.h"
  38 #include "irgwalk.h"
  39 #include "irprintf_t.h"
  40 #include "irgopt.h"
  41 #include "irbitset.h"
  42 #include "height.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_t.h"
  52 #include "benode_t.h"
  53 #include "belive_t.h"
  54 #include "besched_t.h"
  55 #include "beirg_t.h"
  56 #include "bessaconstr.h"
  57
  58 typedef struct _be_abi_call_arg_t {
  59         unsigned is_res   : 1;  /**< 1: the call argument is a return value. 0: it's a call parameter. */
  60         unsigned in_reg   : 1;  /**< 1: this argument is transmitted in registers. */
  61         unsigned on_stack : 1;  /**< 1: this argument is transmitted on the stack. */
  62
  63         int                    pos;
  64         const arch_register_t *reg;
  65         ir_entity             *stack_ent;
  66         ir_mode               *load_mode;
  67         unsigned               alignment;    /**< stack alignment */
  68         unsigned               space_before; /**< allocate space before */
  69         unsigned               space_after;  /**< allocate space after */
  70 } be_abi_call_arg_t;
  71
  72 struct _be_abi_call_t {
  73         be_abi_call_flags_t          flags;  /**< Flags describing the ABI behavior on calls */
  74         int                          pop;    /**< number of bytes the stack frame is shrinked by the callee on return. */
  75         const be_abi_callbacks_t    *cb;
  76         ir_type                     *between_type;
  77         set                         *params;
  78         const arch_register_class_t *cls_addr; /**< register class of the call address */
  79 };
  80
  81 /**
  82  * The ABI information for the current birg.
  83  */
  84 struct _be_abi_irg_t {
  85         struct obstack       obst;
  86         be_irg_t             *birg;         /**< The back end IRG. */
  87         const arch_env_t     *arch_env;
  88         survive_dce_t        *dce_survivor;
  89
  90         be_abi_call_t        *call;         /**< The ABI call information. */
  91         ir_type              *method_type;  /**< The type of the method of the IRG. */
  92
  93         ir_node              *init_sp;      /**< The node representing the stack pointer
  94                                                  at the start of the function. */
  95
  96         ir_node              *reg_params;   /**< The reg params node. */
  97         pmap                 *regs;         /**< A map of all callee-save and ignore regs to
  98                                                  their Projs to the RegParams node. */
  99
 100         int                  start_block_bias; /**< The stack bias at the end of the start block. */
 101
 102         void                 *cb;           /**< ABI Callback self pointer. */
 103
 104         pmap                 *keep_map;     /**< mapping blocks to keep nodes. */
 105         pset                 *ignore_regs;  /**< Additional registers which shall be ignored. */
 106
 107         ir_node              **calls;       /**< flexible array containing all be_Call nodes */
 108
 109         arch_register_req_t  sp_req;
 110         arch_register_req_t  sp_cls_req;
 111
 112         be_stack_layout_t    frame;         /**< The stack frame model. */
 113
 114         DEBUG_ONLY(firm_dbg_module_t    *dbg;)  /**< The debugging module. */
 115 };
 116
 117 static heights_t *ir_heights;
 118
 119 /** Flag: if set, try to omit the frame pointer in all routines. */
 120 static int be_omit_fp = 1;
 121
 122 /** Flag: if set, try to omit the frame pointer in leaf routines only. */
 123 static int be_omit_leaf_fp = 1;
 124
 125 /*
 126      _    ____ ___    ____      _ _ _                _
 127     / \  | __ )_ _|  / ___|__ _| | | |__   __ _  ___| | _____
 128    / _ \ |  _ \| |  | |   / _` | | | '_ \ / _` |/ __| |/ / __|
 129   / ___ \| |_) | |  | |__| (_| | | | |_) | (_| | (__|   <\__ \
 130  /_/   \_\____/___|  \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
 131
 132   These callbacks are used by the backend to set the parameters
 133   for a specific call type.
 134 */
 135
 136 /**
 137  * Set compare function: compares two ABI call object arguments.
 138  */
 139 static int cmp_call_arg(const void *a, const void *b, size_t n)
 140 {
 141         const be_abi_call_arg_t *p = a, *q = b;
 142         (void) n;
 143         return !(p->is_res == q->is_res && p->pos == q->pos);
 144 }
 145
 146 /**
 147  * Get  an ABI call object argument.
 148  *
 149  * @param call      the abi call
 150  * @param is_res    true for call results, false for call arguments
 151  * @param pos       position of the argument
 152  */
 153 static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
 154 {
 155         be_abi_call_arg_t arg;
 156         unsigned hash;
 157
 158         memset(&arg, 0, sizeof(arg));
 159         arg.is_res = is_res;
 160         arg.pos    = pos;
 161
 162         hash = is_res * 128 + pos;
 163
 164         return set_find(call->params, &arg, sizeof(arg), hash);
 165 }
 166
 167 /**
 168  * Set an ABI call object argument.
 169  *
 170  * @param call      the abi call
 171  * @param is_res    true for call results, false for call arguments
 172  * @param pos       position of the argument
 173  */
 174 static be_abi_call_arg_t *create_call_arg(be_abi_call_t *call, int is_res, int pos)
 175 {
 176         be_abi_call_arg_t arg;
 177         unsigned hash;
 178
 179         memset(&arg, 0, sizeof(arg));
 180         arg.is_res = is_res;
 181         arg.pos    = pos;
 182
 183         hash = is_res * 128 + pos;
 184
 185         return set_insert(call->params, &arg, sizeof(arg), hash);
 186 }
 187
 188 /* Set the flags for a call. */
 189 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
 190 {
 191         call->flags = flags;
 192         call->cb    = cb;
 193 }
 194
 195 /* Sets the number of bytes the stackframe is shrinked by the callee on return */
 196 void be_abi_call_set_pop(be_abi_call_t *call, int pop)
 197 {
 198         assert(pop >= 0);
 199         call->pop = pop;
 200 }
 201
 202 /* Set register class for call address */
 203 void be_abi_call_set_call_address_reg_class(be_abi_call_t *call, const arch_register_class_t *cls)
 204 {
 205         call->cls_addr = cls;
 206 }
 207
 208
 209 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos, ir_mode *load_mode, unsigned alignment, unsigned space_before, unsigned space_after)
 210 {
 211         be_abi_call_arg_t *arg = create_call_arg(call, 0, arg_pos);
 212         arg->on_stack     = 1;
 213         arg->load_mode    = load_mode;
 214         arg->alignment    = alignment;
 215         arg->space_before = space_before;
 216         arg->space_after  = space_after;
 217         assert(alignment > 0 && "Alignment must be greater than 0");
 218 }
 219
 220 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
 221 {
 222         be_abi_call_arg_t *arg = create_call_arg(call, 0, arg_pos);
 223         arg->in_reg = 1;
 224         arg->reg = reg;
 225 }
 226
 227 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
 228 {
 229         be_abi_call_arg_t *arg = create_call_arg(call, 1, arg_pos);
 230         arg->in_reg = 1;
 231         arg->reg = reg;
 232 }
 233
 234 /* Get the flags of a ABI call object. */
 235 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
 236 {
 237         return call->flags;
 238 }
 239
 240 /**
 241  * Constructor for a new ABI call object.
 242  *
 243  * @param cls_addr  register class of the call address
 244  *
 245  * @return the new ABI call object
 246  */
 247 static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
 248 {
 249         be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
 250
 251         call->flags.val  = 0;
 252         call->params     = new_set(cmp_call_arg, 16);
 253         call->cb         = NULL;
 254         call->cls_addr   = cls_addr;
 255
 256         call->flags.bits.try_omit_fp = be_omit_fp | be_omit_leaf_fp;
 257
 258         return call;
 259 }
 260
 261 /**
 262  * Destructor for an ABI call object.
 263  */
 264 static void be_abi_call_free(be_abi_call_t *call)
 265 {
 266         del_set(call->params);
 267         free(call);
 268 }
 269
 270 /*
 271   _____                           _   _                 _ _ _
 272  |  ___| __ __ _ _ __ ___   ___  | | | | __ _ _ __   __| | (_)_ __   __ _
 273  | |_ | '__/ _` | '_ ` _ \ / _ \ | |_| |/ _` | '_ \ / _` | | | '_ \ / _` |
 274  |  _|| | | (_| | | | | | |  __/ |  _  | (_| | | | | (_| | | | | | | (_| |
 275  |_|  |_|  \__,_|_| |_| |_|\___| |_| |_|\__,_|_| |_|\__,_|_|_|_| |_|\__, |
 276                                                                     |___/
 277
 278   Handling of the stack frame. It is composed of three types:
 279   1) The type of the arguments which are pushed on the stack.
 280   2) The "between type" which consists of stuff the call of the
 281      function pushes on the stack (like the return address and
 282          the old base pointer for ia32).
 283   3) The Firm frame type which consists of all local variables
 284      and the spills.
 285 */
 286
 287 static int get_stack_entity_offset(be_stack_layout_t *frame, ir_entity *ent,
 288                                    int bias)
 289 {
 290         ir_type *t = get_entity_owner(ent);
 291         int ofs    = get_entity_offset(ent);
 292
 293         int index;
 294
 295         /* Find the type the entity is contained in. */
 296         for (index = 0; index < N_FRAME_TYPES; ++index) {
 297                 if (frame->order[index] == t)
 298                         break;
 299                 /* Add the size of all the types below the one of the entity to the entity's offset */
 300                 ofs += get_type_size_bytes(frame->order[index]);
 301         }
 302
 303         /* correct the offset by the initial position of the frame pointer */
 304         ofs -= frame->initial_offset;
 305
 306         /* correct the offset with the current bias. */
 307         ofs += bias;
 308
 309         return ofs;
 310 }
 311
 312 /**
 313  * Retrieve the entity with given offset from a frame type.
 314  */
 315 static ir_entity *search_ent_with_offset(ir_type *t, int offset)
 316 {
 317         int i, n;
 318
 319         for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
 320                 ir_entity *ent = get_compound_member(t, i);
 321                 if (get_entity_offset(ent) == offset)
 322                         return ent;
 323         }
 324
 325         return NULL;
 326 }
 327
 328 static int stack_frame_compute_initial_offset(be_stack_layout_t *frame)
 329 {
 330         ir_type  *base = frame->stack_dir < 0 ? frame->between_type : frame->frame_type;
 331         ir_entity *ent = search_ent_with_offset(base, 0);
 332
 333         frame->initial_offset = ent ? get_stack_entity_offset(frame, ent, 0) : 0;
 334
 335         return frame->initial_offset;
 336 }
 337
 338 /**
 339  * Initializes the frame layout from parts
 340  *
 341  * @param frame     the stack layout that will be initialized
 342  * @param args      the stack argument layout type
 343  * @param between   the between layout type
 344  * @param locals    the method frame type
 345  * @param stack_dir the stack direction: < 0 decreasing, > 0 increasing addresses
 346  * @param param_map an array mapping method argument positions to the stack argument type
 347  *
 348  * @return the initialized stack layout
 349  */
 350 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
 351                                            ir_type *between, ir_type *locals, int stack_dir,
 352                                            ir_entity *param_map[])
 353 {
 354         frame->arg_type       = args;
 355         frame->between_type   = between;
 356         frame->frame_type     = locals;
 357         frame->initial_offset = 0;
 358         frame->initial_bias   = 0;
 359         frame->stack_dir      = stack_dir;
 360         frame->order[1]       = between;
 361         frame->param_map      = param_map;
 362
 363         if (stack_dir > 0) {
 364                 frame->order[0] = args;
 365                 frame->order[2] = locals;
 366         }
 367         else {
 368                 /* typical decreasing stack: locals have the
 369                  * lowest addresses, arguments the highest */
 370                 frame->order[0] = locals;
 371                 frame->order[2] = args;
 372         }
 373         return frame;
 374 }
 375
 376 #if 0
 377 /** Dumps the stack layout to file. */
 378 static void stack_layout_dump(FILE *file, be_stack_layout_t *frame)
 379 {
 380         int i, j, n;
 381
 382         ir_fprintf(file, "initial offset: %d\n", frame->initial_offset);
 383         for (j = 0; j < N_FRAME_TYPES; ++j) {
 384                 ir_type *t = frame->order[j];
 385
 386                 ir_fprintf(file, "type %d: %F size: %d\n", j, t, get_type_size_bytes(t));
 387                 for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
 388                         ir_entity *ent = get_compound_member(t, i);
 389                         ir_fprintf(file, "\t%F int ofs: %d glob ofs: %d\n", ent, get_entity_offset_bytes(ent), get_stack_entity_offset(frame, ent, 0));
 390                 }
 391         }
 392 }
 393 #endif
 394
 395 /**
 396  * Returns non-zero if the call argument at given position
 397  * is transfered on the stack.
 398  */
 399 static inline int is_on_stack(be_abi_call_t *call, int pos)
 400 {
 401         be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
 402         return arg && !arg->in_reg;
 403 }
 404
 405 /*
 406    ____      _ _
 407   / ___|__ _| | |___
 408  | |   / _` | | / __|
 409  | |__| (_| | | \__ \
 410   \____\__,_|_|_|___/
 411
 412   Adjustment of the calls inside a graph.
 413
 414 */
 415
 416 /**
 417  * Transform a call node into a be_Call node.
 418  *
 419  * @param env The ABI environment for the current irg.
 420  * @param irn The call node.
 421  * @param curr_sp The stack pointer node to use.
 422  * @return The stack pointer after the call.
 423  */
 424 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
 425 {
 426         ir_graph *irg              = env->birg->irg;
 427         const arch_env_t *arch_env = env->birg->main_env->arch_env;
 428         ir_type *call_tp           = get_Call_type(irn);
 429         ir_node *call_ptr          = get_Call_ptr(irn);
 430         int n_params               = get_method_n_params(call_tp);
 431         ir_node *curr_mem          = get_Call_mem(irn);
 432         ir_node *bl                = get_nodes_block(irn);
 433         int stack_size             = 0;
 434         int stack_dir              = arch_env->stack_dir;
 435         const arch_register_t *sp  = arch_env->sp;
 436         be_abi_call_t *call        = be_abi_call_new(sp->reg_class);
 437         ir_mode *mach_mode         = sp->reg_class->mode;
 438         struct obstack *obst       = &env->obst;
 439         int no_alloc               = call->flags.bits.frame_is_setup_on_call;
 440         int n_res                  = get_method_n_ress(call_tp);
 441         int do_seq                 = call->flags.bits.store_args_sequential && !no_alloc;
 442
 443         ir_node *res_proj  = NULL;
 444         int n_reg_params   = 0;
 445         int n_stack_params = 0;
 446         int n_ins;
 447
 448         pset_new_t              destroyed_regs, states;
 449         pset_new_iterator_t     iter;
 450         ir_node                *low_call;
 451         ir_node               **in;
 452         ir_node               **res_projs;
 453         int                     n_reg_results = 0;
 454         const arch_register_t  *reg;
 455         const ir_edge_t        *edge;
 456         int                    *reg_param_idxs;
 457         int                    *stack_param_idx;
 458         int                     i, n, destroy_all_regs;
 459         dbg_info               *dbgi;
 460
 461         pset_new_init(&destroyed_regs);
 462         pset_new_init(&states);
 463
 464         /* Let the isa fill out the abi description for that call node. */
 465         arch_env_get_call_abi(arch_env, call_tp, call);
 466
 467         /* Insert code to put the stack arguments on the stack. */
 468         assert(get_Call_n_params(irn) == n_params);
 469         for (i = 0; i < n_params; ++i) {
 470                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 471                 assert(arg);
 472                 if (arg->on_stack) {
 473                         int arg_size = get_type_size_bytes(get_method_param_type(call_tp, i));
 474
 475                         stack_size += round_up2(arg->space_before, arg->alignment);
 476                         stack_size += round_up2(arg_size, arg->alignment);
 477                         stack_size += round_up2(arg->space_after, arg->alignment);
 478                         obstack_int_grow(obst, i);
 479                         ++n_stack_params;
 480                 }
 481         }
 482         stack_param_idx = obstack_finish(obst);
 483
 484         /* Collect all arguments which are passed in registers. */
 485         for (i = 0; i < n_params; ++i) {
 486                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 487                 if (arg && arg->in_reg) {
 488                         obstack_int_grow(obst, i);
 489                         ++n_reg_params;
 490                 }
 491         }
 492         reg_param_idxs = obstack_finish(obst);
 493
 494         /*
 495          * If the stack is decreasing and we do not want to store sequentially,
 496          * or someone else allocated the call frame
 497          * we allocate as much space on the stack all parameters need, by
 498          * moving the stack pointer along the stack's direction.
 499          *
 500          * Note: we also have to do this for stack_size == 0, because we may have
 501          * to adjust stack alignment for the call.
 502          */
 503         if (stack_dir < 0 && !do_seq && !no_alloc) {
 504                 curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, stack_size, 1);
 505         }
 506
 507         dbgi = get_irn_dbg_info(irn);
 508         /* If there are some parameters which shall be passed on the stack. */
 509         if (n_stack_params > 0) {
 510                 int curr_ofs      = 0;
 511
 512                 /*
 513                  * Reverse list of stack parameters if call arguments are from left to right.
 514                  * We must them reverse again if they are pushed (not stored) and the stack
 515                  * direction is downwards.
 516                  */
 517                 if (call->flags.bits.left_to_right ^ (do_seq && stack_dir < 0)) {
 518                         for (i = 0; i < n_stack_params >> 1; ++i) {
 519                                 int other  = n_stack_params - i - 1;
 520                                 int tmp    = stack_param_idx[i];
 521                                 stack_param_idx[i]     = stack_param_idx[other];
 522                                 stack_param_idx[other] = tmp;
 523                         }
 524                 }
 525
 526                 curr_mem = get_Call_mem(irn);
 527                 if (! do_seq) {
 528                         obstack_ptr_grow(obst, curr_mem);
 529                 }
 530
 531                 for (i = 0; i < n_stack_params; ++i) {
 532                         int p                  = stack_param_idx[i];
 533                         be_abi_call_arg_t *arg = get_call_arg(call, 0, p);
 534                         ir_node *param         = get_Call_param(irn, p);
 535                         ir_node *addr          = curr_sp;
 536                         ir_node *mem           = NULL;
 537                         ir_type *param_type    = get_method_param_type(call_tp, p);
 538                         int param_size         = get_type_size_bytes(param_type) + arg->space_after;
 539
 540                         /*
 541                          * If we wanted to build the arguments sequentially,
 542                          * the stack pointer for the next must be incremented,
 543                          * and the memory value propagated.
 544                          */
 545                         if (do_seq) {
 546                                 curr_ofs = 0;
 547                                 addr = curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, param_size + arg->space_before, 0);
 548                                 add_irn_dep(curr_sp, curr_mem);
 549                         }
 550                         else {
 551                                 curr_ofs += arg->space_before;
 552                                 curr_ofs =  round_up2(curr_ofs, arg->alignment);
 553
 554                                 /* Make the expression to compute the argument's offset. */
 555                                 if (curr_ofs > 0) {
 556                                         ir_mode *constmode = mach_mode;
 557                                         if (mode_is_reference(mach_mode)) {
 558                                                 constmode = mode_Is;
 559                                         }
 560                                         addr = new_r_Const_long(irg, constmode, curr_ofs);
 561                                         addr = new_r_Add(irg, bl, curr_sp, addr, mach_mode);
 562                                 }
 563                         }
 564
 565                         /* Insert a store for primitive arguments. */
 566                         if (is_atomic_type(param_type)) {
 567                                 ir_node *store;
 568                                 ir_node *mem_input = do_seq ? curr_mem : new_NoMem();
 569                                 store = new_rd_Store(dbgi, irg, bl, mem_input, addr, param, 0);
 570                                 mem = new_r_Proj(irg, bl, store, mode_M, pn_Store_M);
 571                         }
 572
 573                         /* Make a mem copy for compound arguments. */
 574                         else {
 575                                 ir_node *copy;
 576
 577                                 assert(mode_is_reference(get_irn_mode(param)));
 578                                 copy = new_rd_CopyB(dbgi, irg, bl, curr_mem, addr, param, param_type);
 579                                 mem = new_r_Proj(irg, bl, copy, mode_M, pn_CopyB_M_regular);
 580                         }
 581
 582                         curr_ofs += param_size;
 583
 584                         if (do_seq)
 585                                 curr_mem = mem;
 586                         else
 587                                 obstack_ptr_grow(obst, mem);
 588                 }
 589
 590                 in = (ir_node **) obstack_finish(obst);
 591
 592                 /* We need the sync only, if we didn't build the stores sequentially. */
 593                 if (! do_seq) {
 594                         if (n_stack_params >= 1) {
 595                                 curr_mem = new_r_Sync(irg, bl, n_stack_params + 1, in);
 596                         } else {
 597                                 curr_mem = get_Call_mem(irn);
 598                         }
 599                 }
 600                 obstack_free(obst, in);
 601         }
 602
 603         /* check for the return_twice property */
 604         destroy_all_regs = 0;
 605         if (is_SymConst_addr_ent(call_ptr)) {
 606                 ir_entity *ent = get_SymConst_entity(call_ptr);
 607
 608                 if (get_entity_additional_properties(ent) & mtp_property_returns_twice)
 609                         destroy_all_regs = 1;
 610         } else {
 611                 ir_type *call_tp = get_Call_type(irn);
 612
 613                 if (get_method_additional_properties(call_tp) & mtp_property_returns_twice)
 614                         destroy_all_regs = 1;
 615         }
 616
 617         /* Put caller save into the destroyed set and state registers in the states set */
 618         for (i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
 619                 unsigned j;
 620                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
 621                 for (j = 0; j < cls->n_regs; ++j) {
 622                         const arch_register_t *reg = arch_register_for_index(cls, j);
 623
 624                         if (destroy_all_regs || arch_register_type_is(reg, caller_save)) {
 625                                 if (! arch_register_type_is(reg, ignore))
 626                                         pset_new_insert(&destroyed_regs, (void *) reg);
 627                         }
 628                         if (arch_register_type_is(reg, state)) {
 629                                 pset_new_insert(&destroyed_regs, (void*) reg);
 630                                 pset_new_insert(&states, (void*) reg);
 631                         }
 632                 }
 633         }
 634
 635         if (destroy_all_regs) {
 636                 /* even if destroyed all is specified, neither SP nor FP are destroyed (else bad things will happen) */
 637                 pset_new_remove(&destroyed_regs, arch_env->sp);
 638                 pset_new_remove(&destroyed_regs, arch_env->bp);
 639         }
 640
 641         /* search the largest result proj number */
 642         res_projs = ALLOCANZ(ir_node*, n_res);
 643
 644         foreach_out_edge(irn, edge) {
 645                 const ir_edge_t *res_edge;
 646                 ir_node         *irn = get_edge_src_irn(edge);
 647
 648                 if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
 649                         continue;
 650
 651                 foreach_out_edge(irn, res_edge) {
 652                         int proj;
 653                         ir_node *res = get_edge_src_irn(res_edge);
 654
 655                         assert(is_Proj(res));
 656
 657                         proj = get_Proj_proj(res);
 658                         assert(proj < n_res);
 659                         assert(res_projs[proj] == NULL);
 660                         res_projs[proj] = res;
 661                 }
 662                 res_proj = irn;
 663                 break;
 664         }
 665
 666         /** TODO: this is not correct for cases where return values are passed
 667          * on the stack, but no known ABI does this currently...
 668          */
 669         n_reg_results = n_res;
 670
 671         /* make the back end call node and set its register requirements. */
 672         for (i = 0; i < n_reg_params; ++i) {
 673                 obstack_ptr_grow(obst, get_Call_param(irn, reg_param_idxs[i]));
 674         }
 675
 676         /* add state registers ins */
 677         foreach_pset_new(&states, reg, iter) {
 678                 const arch_register_class_t *cls = arch_register_get_class(reg);
 679 #if 0
 680                 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
 681                 ir_fprintf(stderr, "Adding %+F\n", regnode);
 682 #endif
 683                 ir_node *regnode = new_r_Unknown(irg, arch_register_class_mode(cls));
 684                 obstack_ptr_grow(obst, regnode);
 685         }
 686         n_ins = n_reg_params + pset_new_size(&states);
 687
 688         in = obstack_finish(obst);
 689
 690         /* ins collected, build the call */
 691         if (env->call->flags.bits.call_has_imm && is_SymConst(call_ptr)) {
 692                 /* direct call */
 693                 low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, curr_sp,
 694                                        n_reg_results + pn_be_Call_first_res + pset_new_size(&destroyed_regs),
 695                                        n_ins, in, get_Call_type(irn));
 696                 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
 697         } else {
 698                 /* indirect call */
 699                 low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, call_ptr,
 700                                        n_reg_results + pn_be_Call_first_res + pset_new_size(&destroyed_regs),
 701                                        n_ins, in, get_Call_type(irn));
 702         }
 703         be_Call_set_pop(low_call, call->pop);
 704
 705         /* put the call into the list of all calls for later processing */
 706         ARR_APP1(ir_node *, env->calls, low_call);
 707
 708         /* create new stack pointer */
 709         curr_sp = new_r_Proj(irg, bl, low_call, get_irn_mode(curr_sp),
 710                              pn_be_Call_sp);
 711         be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
 712                         arch_register_req_type_ignore | arch_register_req_type_produces_sp);
 713         arch_set_irn_register(curr_sp, sp);
 714
 715         /* now handle results */
 716         for (i = 0; i < n_res; ++i) {
 717                 int pn;
 718                 ir_node           *proj = res_projs[i];
 719                 be_abi_call_arg_t *arg  = get_call_arg(call, 1, i);
 720
 721                 /* returns values on stack not supported yet */
 722                 assert(arg->in_reg);
 723
 724                 /*
 725                         shift the proj number to the right, since we will drop the
 726                         unspeakable Proj_T from the Call. Therefore, all real argument
 727                         Proj numbers must be increased by pn_be_Call_first_res
 728                 */
 729                 pn = i + pn_be_Call_first_res;
 730
 731                 if (proj == NULL) {
 732                         ir_type *res_type = get_method_res_type(call_tp, i);
 733                         ir_mode *mode     = get_type_mode(res_type);
 734                         proj              = new_r_Proj(irg, bl, low_call, mode, pn);
 735                         res_projs[i]      = proj;
 736                 } else {
 737                         set_Proj_pred(proj, low_call);
 738                         set_Proj_proj(proj, pn);
 739                 }
 740
 741                 if (arg->in_reg) {
 742                         pset_new_remove(&destroyed_regs, arg->reg);
 743                 }
 744         }
 745
 746         /*
 747                 Set the register class of the call address to
 748                 the backend provided class (default: stack pointer class)
 749         */
 750         be_node_set_reg_class_in(low_call, be_pos_Call_ptr, call->cls_addr);
 751
 752         DBG((env->dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
 753
 754         /* Set the register classes and constraints of the Call parameters. */
 755         for (i = 0; i < n_reg_params; ++i) {
 756                 int index = reg_param_idxs[i];
 757                 be_abi_call_arg_t *arg = get_call_arg(call, 0, index);
 758                 assert(arg->reg != NULL);
 759
 760                 be_set_constr_single_reg_in(low_call, be_pos_Call_first_arg + i,
 761                                             arg->reg, 0);
 762         }
 763
 764         /* Set the register constraints of the results. */
 765         for (i = 0; i < n_res; ++i) {
 766                 ir_node                 *proj = res_projs[i];
 767                 const be_abi_call_arg_t *arg  = get_call_arg(call, 1, i);
 768                 int                      pn   = get_Proj_proj(proj);
 769
 770                 assert(arg->in_reg);
 771                 be_set_constr_single_reg_out(low_call, pn, arg->reg, 0);
 772                 arch_set_irn_register(proj, arg->reg);
 773         }
 774         obstack_free(obst, in);
 775         exchange(irn, low_call);
 776
 777         /* kill the ProjT node */
 778         if (res_proj != NULL) {
 779                 kill_node(res_proj);
 780         }
 781
 782         /* Make additional projs for the caller save registers
 783            and the Keep node which keeps them alive. */
 784         {
 785                 const arch_register_t *reg;
 786                 ir_node               **in, *keep;
 787                 int                   i;
 788                 int                   n = 0;
 789                 int                   curr_res_proj = pn_be_Call_first_res + n_reg_results;
 790                 pset_new_iterator_t   iter;
 791
 792                 /* also keep the stack pointer */
 793                 ++n;
 794                 set_irn_link(curr_sp, (void*) sp);
 795                 obstack_ptr_grow(obst, curr_sp);
 796
 797                 foreach_pset_new(&destroyed_regs, reg, iter) {
 798                         ir_node *proj = new_r_Proj(irg, bl, low_call, reg->reg_class->mode, curr_res_proj);
 799
 800                         /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
 801                         be_set_constr_single_reg_out(low_call, curr_res_proj, reg, 0);
 802                         arch_set_irn_register(proj, reg);
 803
 804                         set_irn_link(proj, (void*) reg);
 805                         obstack_ptr_grow(obst, proj);
 806                         ++curr_res_proj;
 807                         ++n;
 808                 }
 809
 810                 for (i = 0; i < n_reg_results; ++i) {
 811                         ir_node *proj = res_projs[i];
 812                         const arch_register_t *reg = arch_get_irn_register(proj);
 813                         set_irn_link(proj, (void*) reg);
 814                         obstack_ptr_grow(obst, proj);
 815                 }
 816                 n += n_reg_results;
 817
 818                 /* create the Keep for the caller save registers */
 819                 in   = (ir_node **) obstack_finish(obst);
 820                 keep = be_new_Keep(NULL, irg, bl, n, in);
 821                 for (i = 0; i < n; ++i) {
 822                         const arch_register_t *reg = get_irn_link(in[i]);
 823                         be_node_set_reg_class_in(keep, i, reg->reg_class);
 824                 }
 825                 obstack_free(obst, in);
 826         }
 827
 828         /* Clean up the stack. */
 829         assert(stack_size >= call->pop);
 830         stack_size -= call->pop;
 831
 832         if (stack_size > 0) {
 833                 ir_node *mem_proj = NULL;
 834
 835                 foreach_out_edge(low_call, edge) {
 836                         ir_node *irn = get_edge_src_irn(edge);
 837                         if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
 838                                 mem_proj = irn;
 839                                 break;
 840                         }
 841                 }
 842
 843                 if (! mem_proj) {
 844                         mem_proj = new_r_Proj(irg, bl, low_call, mode_M, pn_be_Call_M_regular);
 845                         keep_alive(mem_proj);
 846                 }
 847         }
 848         /* Clean up the stack frame or revert alignment fixes if we allocated it */
 849         if (! no_alloc) {
 850                 curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, -stack_size, 0);
 851         }
 852
 853         be_abi_call_free(call);
 854         obstack_free(obst, stack_param_idx);
 855
 856         pset_new_destroy(&states);
 857         pset_new_destroy(&destroyed_regs);
 858
 859         return curr_sp;
 860 }
 861
 862 /**
 863  * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
 864  *
 865  * @param alignment  the minimum stack alignment
 866  * @param size       the node containing the non-aligned size
 867  * @param irg        the irg where new nodes are allocated on
 868  * @param irg        the block where new nodes are allocated on
 869  * @param dbg        debug info for new nodes
 870  *
 871  * @return a node representing the aligned size
 872  */
 873 static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
 874                                   ir_graph *irg, ir_node *block, dbg_info *dbg)
 875 {
 876         if (stack_alignment > 1) {
 877                 ir_mode *mode;
 878                 tarval  *tv;
 879                 ir_node *mask;
 880
 881                 assert(is_po2(stack_alignment));
 882
 883                 mode = get_irn_mode(size);
 884                 tv   = new_tarval_from_long(stack_alignment-1, mode);
 885                 mask = new_r_Const(irg, tv);
 886                 size = new_rd_Add(dbg, irg, block, size, mask, mode);
 887
 888                 tv   = new_tarval_from_long(-(long)stack_alignment, mode);
 889                 mask = new_r_Const(irg, tv);
 890                 size = new_rd_And(dbg, irg, block, size, mask, mode);
 891         }
 892         return size;
 893 }
 894 /**
 895  * Adjust an alloca.
 896  * The alloca is transformed into a back end alloca node and connected to the stack nodes.
 897  */
 898 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
 899 {
 900         ir_node *block;
 901         ir_graph *irg;
 902         ir_node *alloc_mem;
 903         ir_node *alloc_res;
 904         ir_type *type;
 905         dbg_info *dbg;
 906
 907         const ir_edge_t *edge;
 908         ir_node *new_alloc, *size, *addr, *ins[2];
 909         unsigned stack_alignment;
 910
 911         assert(get_Alloc_where(alloc) == stack_alloc);
 912
 913         block = get_nodes_block(alloc);
 914         irg = get_irn_irg(block);
 915         alloc_mem = NULL;
 916         alloc_res = NULL;
 917         type = get_Alloc_type(alloc);
 918
 919         foreach_out_edge(alloc, edge) {
 920                 ir_node *irn = get_edge_src_irn(edge);
 921
 922                 assert(is_Proj(irn));
 923                 switch (get_Proj_proj(irn)) {
 924                 case pn_Alloc_M:
 925                         alloc_mem = irn;
 926                         break;
 927                 case pn_Alloc_res:
 928                         alloc_res = irn;
 929                         break;
 930                 default:
 931                         break;
 932                 }
 933         }
 934
 935         /* Beware: currently Alloc nodes without a result might happen,
 936            only escape analysis kills them and this phase runs only for object
 937            oriented source. We kill the Alloc here. */
 938         if (alloc_res == NULL && alloc_mem) {
 939                 exchange(alloc_mem, get_Alloc_mem(alloc));
 940                 return curr_sp;
 941         }
 942
 943         dbg  = get_irn_dbg_info(alloc);
 944         size = get_Alloc_size(alloc);
 945
 946         /* we might need to multiply the size with the element size */
 947         if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
 948                 ir_mode *mode = get_irn_mode(size);
 949                 tarval *tv    = new_tarval_from_long(get_type_size_bytes(type),
 950                                                      mode);
 951                 ir_node *cnst = new_rd_Const(dbg, irg, tv);
 952                 size          = new_rd_Mul(dbg, irg, block, size, cnst, mode);
 953         }
 954
 955         /* The stack pointer will be modified in an unknown manner.
 956            We cannot omit it. */
 957         env->call->flags.bits.try_omit_fp = 0;
 958
 959         stack_alignment = 1 << env->arch_env->stack_alignment;
 960         size            = adjust_alloc_size(stack_alignment, size, irg, block, dbg);
 961         new_alloc       = be_new_AddSP(env->arch_env->sp, irg, block, curr_sp, size);
 962         set_irn_dbg_info(new_alloc, dbg);
 963
 964         if (alloc_mem != NULL) {
 965                 ir_node *addsp_mem;
 966                 ir_node *sync;
 967
 968                 addsp_mem = new_r_Proj(irg, block, new_alloc, mode_M, pn_be_AddSP_M);
 969
 970                 /* We need to sync the output mem of the AddSP with the input mem
 971                    edge into the alloc node. */
 972                 ins[0] = get_Alloc_mem(alloc);
 973                 ins[1] = addsp_mem;
 974                 sync = new_r_Sync(irg, block, 2, ins);
 975
 976                 exchange(alloc_mem, sync);
 977         }
 978
 979         exchange(alloc, new_alloc);
 980
 981         /* fix projnum of alloca res */
 982         set_Proj_proj(alloc_res, pn_be_AddSP_res);
 983
 984         addr    = alloc_res;
 985         curr_sp = new_r_Proj(irg, block, new_alloc,  get_irn_mode(curr_sp),
 986                              pn_be_AddSP_sp);
 987
 988         return curr_sp;
 989 }  /* adjust_alloc */
 990
 991 /**
 992  * Adjust a Free.
 993  * The Free is transformed into a back end free node and connected to the stack nodes.
 994  */
 995 static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
 996 {
 997         ir_node *block;
 998         ir_graph *irg;
 999         ir_node *subsp, *mem, *res, *size, *sync;
1000         ir_type *type;
1001         ir_node *in[2];
1002         ir_mode *sp_mode;
1003         unsigned stack_alignment;
1004         dbg_info *dbg;
1005
1006         assert(get_Free_where(free) == stack_alloc);
1007
1008         block = get_nodes_block(free);
1009         irg = get_irn_irg(block);
1010         type = get_Free_type(free);
1011         sp_mode = env->arch_env->sp->reg_class->mode;
1012         dbg = get_irn_dbg_info(free);
1013
1014         /* we might need to multiply the size with the element size */
1015         if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
1016                 tarval *tv = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
1017                 ir_node *cnst = new_rd_Const(dbg, irg, tv);
1018                 ir_node *mul = new_rd_Mul(dbg, irg, block, get_Free_size(free),
1019                                           cnst, mode_Iu);
1020                 size = mul;
1021         } else {
1022                 size = get_Free_size(free);
1023         }
1024
1025         stack_alignment = 1 << env->arch_env->stack_alignment;
1026         size            = adjust_alloc_size(stack_alignment, size, irg, block, dbg);
1027
1028         /* The stack pointer will be modified in an unknown manner.
1029            We cannot omit it. */
1030         env->call->flags.bits.try_omit_fp = 0;
1031         subsp = be_new_SubSP(env->arch_env->sp, irg, block, curr_sp, size);
1032         set_irn_dbg_info(subsp, dbg);
1033
1034         mem = new_r_Proj(irg, block, subsp, mode_M, pn_be_SubSP_M);
1035         res = new_r_Proj(irg, block, subsp, sp_mode, pn_be_SubSP_sp);
1036
1037         /* we need to sync the memory */
1038         in[0] = get_Free_mem(free);
1039         in[1] = mem;
1040         sync = new_r_Sync(irg, block, 2, in);
1041
1042         /* and make the AddSP dependent on the former memory */
1043         add_irn_dep(subsp, get_Free_mem(free));
1044
1045         /* kill the free */
1046         exchange(free, sync);
1047         curr_sp = res;
1048
1049         return curr_sp;
1050 }  /* adjust_free */
1051
1052 /* the following function is replaced by the usage of the heights module */
1053 #if 0
1054 /**
1055  * Walker for dependent_on().
1056  * This function searches a node tgt recursively from a given node
1057  * but is restricted to the given block.
1058  * @return 1 if tgt was reachable from curr, 0 if not.
1059  */
1060 static int check_dependence(ir_node *curr, ir_node *tgt, ir_node *bl)
1061 {
1062         int n, i;
1063
1064         if (get_nodes_block(curr) != bl)
1065                 return 0;
1066
1067         if (curr == tgt)
1068                 return 1;
1069
1070         /* Phi functions stop the recursion inside a basic block */
1071         if (! is_Phi(curr)) {
1072                 for (i = 0, n = get_irn_arity(curr); i < n; ++i) {
1073                         if (check_dependence(get_irn_n(curr, i), tgt, bl))
1074                                 return 1;
1075                 }
1076         }
1077
1078         return 0;
1079 }
1080 #endif /* if 0 */
1081
1082 /**
1083  * Check if a node is somehow data dependent on another one.
1084  * both nodes must be in the same basic block.
1085  * @param n1 The first node.
1086  * @param n2 The second node.
1087  * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
1088  */
1089 static int dependent_on(ir_node *n1, ir_node *n2)
1090 {
1091         assert(get_nodes_block(n1) == get_nodes_block(n2));
1092
1093         return heights_reachable_in_block(ir_heights, n1, n2);
1094 }
1095
1096 static int cmp_call_dependency(const void *c1, const void *c2)
1097 {
1098         ir_node *n1 = *(ir_node **) c1;
1099         ir_node *n2 = *(ir_node **) c2;
1100
1101         /*
1102                 Classical qsort() comparison function behavior:
1103                 0  if both elements are equal
1104                 1  if second is "smaller" that first
1105                 -1 if first is "smaller" that second
1106         */
1107         if (dependent_on(n1, n2))
1108                 return -1;
1109
1110         if (dependent_on(n2, n1))
1111                 return 1;
1112
1113         /* The nodes have no depth order, but we need a total order because qsort()
1114          * is not stable. */
1115         return get_irn_idx(n1) - get_irn_idx(n2);
1116 }
1117
1118 /**
1119  * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
1120  * Clears the irg_is_leaf flag if a Call is detected.
1121  */
1122 static void link_ops_in_block_walker(ir_node *irn, void *data)
1123 {
1124         ir_opcode code = get_irn_opcode(irn);
1125
1126         if (code == iro_Call ||
1127            (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
1128            (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
1129                 be_abi_irg_t *env = data;
1130                 ir_node *bl       = get_nodes_block(irn);
1131                 void *save        = get_irn_link(bl);
1132
1133                 if (code == iro_Call)
1134                         env->call->flags.bits.irg_is_leaf = 0;
1135
1136                 set_irn_link(irn, save);
1137                 set_irn_link(bl, irn);
1138         }
1139 }
1140
1141 /**
1142  * Block-walker:
1143  * Process all Call/Alloc/Free nodes inside a basic block.
1144  * Note that the link field of the block must contain a linked list of all
1145  * Call nodes inside the Block. We first order this list according to data dependency
1146  * and that connect the calls together.
1147  */
1148 static void process_ops_in_block(ir_node *bl, void *data)
1149 {
1150         be_abi_irg_t *env = data;
1151         ir_node *curr_sp  = env->init_sp;
1152         ir_node *irn;
1153         int n;
1154
1155         for (irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
1156                 obstack_ptr_grow(&env->obst, irn);
1157
1158         /* If there were call nodes in the block. */
1159         if (n > 0) {
1160                 ir_node *keep;
1161                 ir_node **nodes;
1162                 int i;
1163
1164                 nodes = obstack_finish(&env->obst);
1165
1166                 /* order the call nodes according to data dependency */
1167                 qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependency);
1168
1169                 for (i = n - 1; i >= 0; --i) {
1170                         ir_node *irn = nodes[i];
1171
1172                         DBG((env->dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1173                         switch (get_irn_opcode(irn)) {
1174                         case iro_Call:
1175                                 if (! be_omit_fp) {
1176                                         /* The stack pointer will be modified due to a call. */
1177                                         env->call->flags.bits.try_omit_fp = 0;
1178                                 }
1179                                 curr_sp = adjust_call(env, irn, curr_sp);
1180                                 break;
1181                         case iro_Alloc:
1182                                 if (get_Alloc_where(irn) == stack_alloc)
1183                                         curr_sp = adjust_alloc(env, irn, curr_sp);
1184                                 break;
1185                         case iro_Free:
1186                                 if (get_Free_where(irn) == stack_alloc)
1187                                         curr_sp = adjust_free(env, irn, curr_sp);
1188                                 break;
1189                         default:
1190                                 panic("invalid call");
1191                                 break;
1192                         }
1193                 }
1194
1195                 obstack_free(&env->obst, nodes);
1196
1197                 /* Keep the last stack state in the block by tying it to Keep node,
1198                  * the proj from calls is already kept */
1199                 if (curr_sp != env->init_sp &&
1200                     !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1201                         nodes[0] = curr_sp;
1202                         keep     = be_new_Keep(env->arch_env->sp->reg_class,
1203                                                get_irn_irg(bl), bl, 1, nodes);
1204                         pmap_insert(env->keep_map, bl, keep);
1205                 }
1206         }
1207
1208         set_irn_link(bl, curr_sp);
1209 }  /* process_ops_in_block */
1210
1211 /**
1212  * Adjust all call nodes in the graph to the ABI conventions.
1213  */
1214 static void process_calls(be_abi_irg_t *env)
1215 {
1216         ir_graph *irg = env->birg->irg;
1217
1218         env->call->flags.bits.irg_is_leaf = 1;
1219         irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, env);
1220
1221         ir_heights = heights_new(env->birg->irg);
1222         irg_block_walk_graph(irg, NULL, process_ops_in_block, env);
1223         heights_free(ir_heights);
1224 }
1225
1226 /**
1227  * Computes the stack argument layout type.
1228  * Changes a possibly allocated value param type by moving
1229  * entities to the stack layout type.
1230  *
1231  * @param env           the ABI environment
1232  * @param call          the current call ABI
1233  * @param method_type   the method type
1234  * @param val_param_tp  the value parameter type, will be destroyed
1235  * @param param_map     an array mapping method arguments to the stack layout type
1236  *
1237  * @return the stack argument layout type
1238  */
1239 static ir_type *compute_arg_type(be_abi_irg_t *env, be_abi_call_t *call,
1240                                                                  ir_type *method_type, ir_type *val_param_tp,
1241                                                                  ir_entity ***param_map)
1242 {
1243         int dir  = env->call->flags.bits.left_to_right ? 1 : -1;
1244         int inc  = env->birg->main_env->arch_env->stack_dir * dir;
1245         int n    = get_method_n_params(method_type);
1246         int curr = inc > 0 ? 0 : n - 1;
1247         int ofs  = 0;
1248
1249         char buf[128];
1250         ir_type *res;
1251         int i;
1252         ident *id = get_entity_ident(get_irg_entity(env->birg->irg));
1253         ir_entity **map;
1254
1255         *param_map = map = obstack_alloc(&env->obst, n * sizeof(ir_entity *));
1256         res = new_type_struct(id_mangle_u(id, new_id_from_chars("arg_type", 8)));
1257         for (i = 0; i < n; ++i, curr += inc) {
1258                 ir_type *param_type    = get_method_param_type(method_type, curr);
1259                 be_abi_call_arg_t *arg = get_call_arg(call, 0, curr);
1260
1261                 map[i] = NULL;
1262                 if (arg->on_stack) {
1263                         if (val_param_tp != NULL) {
1264                                 /* the entity was already created, create a copy in the param type */
1265                                 ir_entity *val_ent = get_method_value_param_ent(method_type, i);
1266                                 arg->stack_ent = copy_entity_own(val_ent, res);
1267                                 set_entity_link(val_ent, arg->stack_ent);
1268                                 set_entity_link(arg->stack_ent, NULL);
1269                                 /* must be automatic to set a fixed layout */
1270                                 set_entity_allocation(arg->stack_ent, allocation_automatic);
1271                         } else {
1272                                 /* create a new entity */
1273                                 snprintf(buf, sizeof(buf), "param_%d", i);
1274                                 arg->stack_ent = new_entity(res, new_id_from_str(buf), param_type);
1275                         }
1276                         ofs += arg->space_before;
1277                         ofs = round_up2(ofs, arg->alignment);
1278                         set_entity_offset(arg->stack_ent, ofs);
1279                         ofs += arg->space_after;
1280                         ofs += get_type_size_bytes(param_type);
1281                         map[i] = arg->stack_ent;
1282                 }
1283         }
1284         set_type_size_bytes(res, ofs);
1285         set_type_state(res, layout_fixed);
1286         return res;
1287 }
1288
1289 typedef struct {
1290         const arch_register_t *reg;
1291         ir_node *irn;
1292 } reg_node_map_t;
1293
1294 static int cmp_regs(const void *a, const void *b)
1295 {
1296         const reg_node_map_t *p = a;
1297         const reg_node_map_t *q = b;
1298
1299         if (p->reg->reg_class == q->reg->reg_class)
1300                 return p->reg->index - q->reg->index;
1301         else
1302                 return p->reg->reg_class - q->reg->reg_class;
1303 }
1304
1305 static reg_node_map_t *reg_map_to_arr(struct obstack *obst, pmap *reg_map)
1306 {
1307         pmap_entry *ent;
1308         int n = pmap_count(reg_map);
1309         int i = 0;
1310         reg_node_map_t *res = obstack_alloc(obst, n * sizeof(res[0]));
1311
1312         foreach_pmap(reg_map, ent) {
1313                 res[i].reg = ent->key;
1314                 res[i].irn = ent->value;
1315                 i++;
1316         }
1317
1318         qsort(res, n, sizeof(res[0]), cmp_regs);
1319         return res;
1320 }
1321
1322 /**
1323  * Creates a barrier.
1324  */
1325 static ir_node *create_barrier(be_abi_irg_t *env, ir_node *bl, ir_node **mem, pmap *regs, int in_req)
1326 {
1327         ir_graph *irg = env->birg->irg;
1328         int n_regs    = pmap_count(regs);
1329         int n;
1330         ir_node *irn;
1331         ir_node **in;
1332         reg_node_map_t *rm;
1333
1334         rm = reg_map_to_arr(&env->obst, regs);
1335
1336         for (n = 0; n < n_regs; ++n)
1337                 obstack_ptr_grow(&env->obst, rm[n].irn);
1338
1339         if (mem) {
1340                 obstack_ptr_grow(&env->obst, *mem);
1341                 n++;
1342         }
1343
1344         in = (ir_node **) obstack_finish(&env->obst);
1345         irn = be_new_Barrier(irg, bl, n, in);
1346         obstack_free(&env->obst, in);
1347
1348         for (n = 0; n < n_regs; ++n) {
1349                 ir_node                   *pred     = rm[n].irn;
1350                 const arch_register_t     *reg      = rm[n].reg;
1351                 arch_register_type_t       add_type = 0;
1352                 ir_node                   *proj;
1353
1354                 /* stupid workaround for now... as not all nodes report register
1355                  * requirements. */
1356                 if (!is_Phi(pred)) {
1357                         const arch_register_req_t *ireq = arch_get_register_req_out(pred);
1358                         if (ireq->type & arch_register_req_type_ignore)
1359                                 add_type |= arch_register_req_type_ignore;
1360                         if (ireq->type & arch_register_req_type_produces_sp)
1361                                 add_type |= arch_register_req_type_produces_sp;
1362                 }
1363
1364                 proj = new_r_Proj(irg, bl, irn, get_irn_mode(pred), n);
1365                 be_node_set_reg_class_in(irn, n, reg->reg_class);
1366                 if (in_req)
1367                         be_set_constr_single_reg_in(irn, n, reg, 0);
1368                 be_set_constr_single_reg_out(irn, n, reg, add_type);
1369                 arch_set_irn_register(proj, reg);
1370
1371                 pmap_insert(regs, (void *) reg, proj);
1372         }
1373
1374         if (mem) {
1375                 *mem = new_r_Proj(irg, bl, irn, mode_M, n);
1376         }
1377
1378         obstack_free(&env->obst, rm);
1379         return irn;
1380 }
1381
1382 /**
1383  * Creates a be_Return for a Return node.
1384  *
1385  * @param @env    the abi environment
1386  * @param irn     the Return node or NULL if there was none
1387  * @param bl      the block where the be_Retun should be placed
1388  * @param mem     the current memory
1389  * @param n_res   number of return results
1390  */
1391 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1392                 ir_node *mem, int n_res)
1393 {
1394         be_abi_call_t    *call     = env->call;
1395         const arch_env_t *arch_env = env->birg->main_env->arch_env;
1396         dbg_info *dbgi;
1397         pmap *reg_map  = pmap_create();
1398         ir_node *keep  = pmap_get(env->keep_map, bl);
1399         int in_max;
1400         ir_node *ret;
1401         int i, n;
1402         unsigned pop;
1403         ir_node **in;
1404         ir_node *stack;
1405         const arch_register_t **regs;
1406         pmap_entry *ent ;
1407
1408         /*
1409                 get the valid stack node in this block.
1410                 If we had a call in that block there is a Keep constructed by process_calls()
1411                 which points to the last stack modification in that block. we'll use
1412                 it then. Else we use the stack from the start block and let
1413                 the ssa construction fix the usage.
1414         */
1415         stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1416         if (keep) {
1417                 stack = get_irn_n(keep, 0);
1418                 kill_node(keep);
1419                 remove_End_keepalive(get_irg_end(env->birg->irg), keep);
1420         }
1421
1422         /* Insert results for Return into the register map. */
1423         for (i = 0; i < n_res; ++i) {
1424                 ir_node *res           = get_Return_res(irn, i);
1425                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1426                 assert(arg->in_reg && "return value must be passed in register");
1427                 pmap_insert(reg_map, (void *) arg->reg, res);
1428         }
1429
1430         /* Add uses of the callee save registers. */
1431         foreach_pmap(env->regs, ent) {
1432                 const arch_register_t *reg = ent->key;
1433                 if (arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1434                         pmap_insert(reg_map, ent->key, ent->value);
1435         }
1436
1437         be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1438
1439         /* Make the Epilogue node and call the arch's epilogue maker. */
1440         create_barrier(env, bl, &mem, reg_map, 1);
1441         call->cb->epilogue(env->cb, bl, &mem, reg_map);
1442
1443         /*
1444                 Maximum size of the in array for Return nodes is
1445                 return args + callee save/ignore registers + memory + stack pointer
1446         */
1447         in_max = pmap_count(reg_map) + n_res + 2;
1448
1449         in   = obstack_alloc(&env->obst, in_max * sizeof(in[0]));
1450         regs = obstack_alloc(&env->obst, in_max * sizeof(regs[0]));
1451
1452         in[0]   = mem;
1453         in[1]   = be_abi_reg_map_get(reg_map, arch_env->sp);
1454         regs[0] = NULL;
1455         regs[1] = arch_env->sp;
1456         n       = 2;
1457
1458         /* clear SP entry, since it has already been grown. */
1459         pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1460         for (i = 0; i < n_res; ++i) {
1461                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1462
1463                 in[n]     = be_abi_reg_map_get(reg_map, arg->reg);
1464                 regs[n++] = arg->reg;
1465
1466                 /* Clear the map entry to mark the register as processed. */
1467                 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1468         }
1469
1470         /* grow the rest of the stuff. */
1471         foreach_pmap(reg_map, ent) {
1472                 if (ent->value) {
1473                         in[n]     = ent->value;
1474                         regs[n++] = ent->key;
1475                 }
1476         }
1477
1478         /* The in array for the new back end return is now ready. */
1479         if (irn != NULL) {
1480                 dbgi = get_irn_dbg_info(irn);
1481         } else {
1482                 dbgi = NULL;
1483         }
1484         /* we have to pop the shadow parameter in in case of struct returns */
1485         pop = call->pop;
1486         ret = be_new_Return(dbgi, env->birg->irg, bl, n_res, pop, n, in);
1487
1488         /* Set the register classes of the return's parameter accordingly. */
1489         for (i = 0; i < n; ++i) {
1490                 if (regs[i] == NULL)
1491                         continue;
1492
1493                 be_node_set_reg_class_in(ret, i, regs[i]->reg_class);
1494         }
1495
1496         /* Free the space of the Epilog's in array and the register <-> proj map. */
1497         obstack_free(&env->obst, in);
1498         pmap_destroy(reg_map);
1499
1500         return ret;
1501 }
1502
1503 typedef struct ent_pos_pair ent_pos_pair;
1504 struct ent_pos_pair {
1505         ir_entity    *ent;   /**< a value param entity */
1506         int          pos;    /**< its parameter number */
1507         ent_pos_pair *next;  /**< for linking */
1508 };
1509
1510 typedef struct lower_frame_sels_env_t {
1511         ent_pos_pair *value_param_list;          /**< the list of all value param entities */
1512         ir_node      *frame;                     /**< the current frame */
1513         const arch_register_class_t *sp_class;   /**< register class of the stack pointer */
1514         const arch_register_class_t *link_class; /**< register class of the link pointer */
1515         ir_type      *value_tp;                  /**< the value type if any */
1516         ir_type      *frame_tp;                  /**< the frame type */
1517         int          static_link_pos;            /**< argument number of the hidden static link */
1518 } lower_frame_sels_env_t;
1519
1520 /**
1521  * Return an entity from the backend for an value param entity.
1522  *
1523  * @param ent  an value param type entity
1524  * @param ctx  context
1525  */
1526 static ir_entity *get_argument_entity(ir_entity *ent, lower_frame_sels_env_t *ctx)
1527 {
1528         ir_entity *argument_ent = get_entity_link(ent);
1529
1530         if (argument_ent == NULL) {
1531                 /* we have NO argument entity yet: This is bad, as we will
1532                 * need one for backing store.
1533                 * Create one here.
1534                 */
1535                 ir_type *frame_tp = ctx->frame_tp;
1536                 unsigned offset   = get_type_size_bytes(frame_tp);
1537                 ir_type  *tp      = get_entity_type(ent);
1538                 unsigned align    = get_type_alignment_bytes(tp);
1539
1540                 offset += align - 1;
1541                 offset &= ~(align - 1);
1542
1543                 argument_ent = copy_entity_own(ent, frame_tp);
1544
1545                 /* must be automatic to set a fixed layout */
1546                 set_entity_allocation(argument_ent, allocation_automatic);
1547                 set_entity_offset(argument_ent, offset);
1548                 offset += get_type_size_bytes(tp);
1549
1550                 set_type_size_bytes(frame_tp, offset);
1551                 set_entity_link(ent, argument_ent);
1552         }
1553         return argument_ent;
1554 }
1555 /**
1556  * Walker: Replaces Sels of frame type and
1557  * value param type entities by FrameAddress.
1558  * Links all used entities.
1559  */
1560 static void lower_frame_sels_walker(ir_node *irn, void *data)
1561 {
1562         lower_frame_sels_env_t *ctx = data;
1563
1564         if (is_Sel(irn)) {
1565                 ir_node *ptr = get_Sel_ptr(irn);
1566
1567                 if (ptr == ctx->frame) {
1568                         ir_entity    *ent = get_Sel_entity(irn);
1569                         ir_node      *bl  = get_nodes_block(irn);
1570                         ir_node      *nw;
1571                         int          pos = 0;
1572                         int          is_value_param = 0;
1573
1574                         if (get_entity_owner(ent) == ctx->value_tp) {
1575                                 is_value_param = 1;
1576
1577                                 /* replace by its copy from the argument type */
1578                                 pos = get_struct_member_index(ctx->value_tp, ent);
1579                                 ent = get_argument_entity(ent, ctx);
1580                         }
1581
1582                         nw = be_new_FrameAddr(ctx->sp_class, current_ir_graph, bl, ctx->frame, ent);
1583                         exchange(irn, nw);
1584
1585                         /* check, if it's a param Sel and if have not seen this entity before */
1586                         if (is_value_param && get_entity_link(ent) == NULL) {
1587                                 ent_pos_pair pair;
1588
1589                                 pair.ent  = ent;
1590                                 pair.pos  = pos;
1591                                 pair.next = NULL;
1592                                 ARR_APP1(ent_pos_pair, ctx->value_param_list, pair);
1593                                 /* just a mark */
1594                                 set_entity_link(ent, ctx->value_param_list);
1595                         }
1596                 }
1597         }
1598 }
1599
1600 /**
1601  * Check if a value parameter is transmitted as a register.
1602  * This might happen if the address of an parameter is taken which is
1603  * transmitted in registers.
1604  *
1605  * Note that on some architectures this case must be handled specially
1606  * because the place of the backing store is determined by their ABI.
1607  *
1608  * In the default case we move the entity to the frame type and create
1609  * a backing store into the first block.
1610  */
1611 static void fix_address_of_parameter_access(be_abi_irg_t *env, ent_pos_pair *value_param_list)
1612 {
1613         be_abi_call_t *call = env->call;
1614         ir_graph      *irg  = env->birg->irg;
1615         ent_pos_pair  *entry, *new_list;
1616         ir_type       *frame_tp;
1617         int           i, n = ARR_LEN(value_param_list);
1618         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1619
1620         new_list = NULL;
1621         for (i = 0; i < n; ++i) {
1622                 int               pos  = value_param_list[i].pos;
1623                 be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
1624
1625                 if (arg->in_reg) {
1626                         DBG((dbg, LEVEL_2, "\targ #%d need backing store\n", pos));
1627                         value_param_list[i].next = new_list;
1628                         new_list = &value_param_list[i];
1629                 }
1630         }
1631         if (new_list != NULL) {
1632                 /* ok, change the graph */
1633                 ir_node *start_bl = get_irg_start_block(irg);
1634                 ir_node *first_bl = NULL;
1635                 ir_node *frame, *imem, *nmem, *store, *mem, *args, *args_bl;
1636                 const ir_edge_t *edge;
1637                 optimization_state_t state;
1638                 unsigned offset;
1639
1640                 foreach_block_succ(start_bl, edge) {
1641                         ir_node *succ = get_edge_src_irn(edge);
1642                         if (start_bl != succ) {
1643                                 first_bl = succ;
1644                                 break;
1645                         }
1646                 }
1647                 assert(first_bl);
1648                 /* we had already removed critical edges, so the following
1649                    assertion should be always true. */
1650                 assert(get_Block_n_cfgpreds(first_bl) == 1);
1651
1652                 /* now create backing stores */
1653                 frame = get_irg_frame(irg);
1654                 imem = get_irg_initial_mem(irg);
1655
1656                 save_optimization_state(&state);
1657                 set_optimize(0);
1658                 nmem = new_r_Proj(irg, first_bl, get_irg_start(irg), mode_M, pn_Start_M);
1659                 restore_optimization_state(&state);
1660
1661                 /* reroute all edges to the new memory source */
1662                 edges_reroute(imem, nmem, irg);
1663
1664                 store   = NULL;
1665                 mem     = imem;
1666                 args    = get_irg_args(irg);
1667                 args_bl = get_nodes_block(args);
1668                 for (entry = new_list; entry != NULL; entry = entry->next) {
1669                         int     i     = entry->pos;
1670                         ir_type *tp   = get_entity_type(entry->ent);
1671                         ir_mode *mode = get_type_mode(tp);
1672                         ir_node *addr;
1673
1674                         /* address for the backing store */
1675                         addr = be_new_FrameAddr(env->arch_env->sp->reg_class, irg, first_bl, frame, entry->ent);
1676
1677                         if (store)
1678                                 mem = new_r_Proj(irg, first_bl, store, mode_M, pn_Store_M);
1679
1680                         /* the backing store itself */
1681                         store = new_r_Store(irg, first_bl, mem, addr,
1682                                             new_r_Proj(irg, args_bl, args, mode, i), 0);
1683                 }
1684                 /* the new memory Proj gets the last Proj from store */
1685                 set_Proj_pred(nmem, store);
1686                 set_Proj_proj(nmem, pn_Store_M);
1687
1688                 /* move all entities to the frame type */
1689                 frame_tp = get_irg_frame_type(irg);
1690                 offset   = get_type_size_bytes(frame_tp);
1691
1692                 /* we will add new entities: set the layout to undefined */
1693                 assert(get_type_state(frame_tp) == layout_fixed);
1694                 set_type_state(frame_tp, layout_undefined);
1695                 for (entry = new_list; entry != NULL; entry = entry->next) {
1696                         ir_entity *ent = entry->ent;
1697
1698                         /* If the entity is still on the argument type, move it to the frame type.
1699                            This happens if the value_param type was build due to compound
1700                            params. */
1701                         if (get_entity_owner(ent) != frame_tp) {
1702                                 ir_type  *tp   = get_entity_type(ent);
1703                                 unsigned align = get_type_alignment_bytes(tp);
1704
1705                                 offset += align - 1;
1706                                 offset &= ~(align - 1);
1707                                 set_entity_owner(ent, frame_tp);
1708                                 add_class_member(frame_tp, ent);
1709                                 /* must be automatic to set a fixed layout */
1710                                 set_entity_allocation(ent, allocation_automatic);
1711                                 set_entity_offset(ent, offset);
1712                                 offset += get_type_size_bytes(tp);
1713                         }
1714                 }
1715                 set_type_size_bytes(frame_tp, offset);
1716                 /* fix the layout again */
1717                 set_type_state(frame_tp, layout_fixed);
1718         }
1719 }
1720
1721 /**
1722  * The start block has no jump, instead it has an initial exec Proj.
1723  * The backend wants to handle all blocks the same way, so we replace
1724  * the out cfg edge with a real jump.
1725  */
1726 static void fix_start_block(ir_graph *irg)
1727 {
1728         ir_node         *initial_X   = get_irg_initial_exec(irg);
1729         ir_node         *start_block = get_irg_start_block(irg);
1730         const ir_edge_t *edge;
1731
1732         assert(is_Proj(initial_X));
1733
1734         foreach_out_edge(initial_X, edge) {
1735                 ir_node *block = get_edge_src_irn(edge);
1736
1737                 if (is_Anchor(block))
1738                         continue;
1739                 if (block != start_block) {
1740                         ir_node *jmp = new_r_Jmp(irg, start_block);
1741
1742                         set_Block_cfgpred(block, get_edge_src_pos(edge), jmp);
1743                         return;
1744                 }
1745         }
1746         panic("Initial exec has no follow block in %+F", irg);
1747 }
1748
1749 /**
1750  * Update the entity of Sels to the outer value parameters.
1751  */
1752 static void update_outer_frame_sels(ir_node *irn, void *env) {
1753         lower_frame_sels_env_t *ctx = env;
1754         ir_node                *ptr;
1755         ir_entity              *ent;
1756         int                    pos = 0;
1757
1758         if (! is_Sel(irn))
1759                 return;
1760         ptr = get_Sel_ptr(irn);
1761         if (! is_arg_Proj(ptr))
1762                 return;
1763         if (get_Proj_proj(ptr) != ctx->static_link_pos)
1764                 return;
1765         ent   = get_Sel_entity(irn);
1766
1767         if (get_entity_owner(ent) == ctx->value_tp) {
1768                 /* replace by its copy from the argument type */
1769                 pos = get_struct_member_index(ctx->value_tp, ent);
1770                 ent = get_argument_entity(ent, ctx);
1771                 set_Sel_entity(irn, ent);
1772
1773                 /* check, if we have not seen this entity before */
1774                 if (get_entity_link(ent) == NULL) {
1775                         ent_pos_pair pair;
1776
1777                         pair.ent  = ent;
1778                         pair.pos  = pos;
1779                         pair.next = NULL;
1780                         ARR_APP1(ent_pos_pair, ctx->value_param_list, pair);
1781                         /* just a mark */
1782                         set_entity_link(ent, ctx->value_param_list);
1783                 }
1784         }
1785 }
1786
1787 /**
1788  * Fix access to outer local variables.
1789  */
1790 static void fix_outer_variable_access(be_abi_irg_t *env,
1791                                       lower_frame_sels_env_t *ctx)
1792 {
1793         int      i;
1794         ir_graph *irg;
1795         (void) env;
1796
1797         for (i = get_class_n_members(ctx->frame_tp) - 1; i >= 0; --i) {
1798                 ir_entity *ent = get_class_member(ctx->frame_tp, i);
1799
1800                 if (! is_method_entity(ent))
1801                         continue;
1802                 if (get_entity_peculiarity(ent) == peculiarity_description)
1803                         continue;
1804
1805                 /*
1806                  * FIXME: find the number of the static link parameter
1807                  * for now we assume 0 here
1808                  */
1809                 ctx->static_link_pos = 0;
1810
1811                 irg = get_entity_irg(ent);
1812                 irg_walk_graph(irg, NULL, update_outer_frame_sels, ctx);
1813         }
1814 }
1815
1816 /**
1817  * Modify the irg itself and the frame type.
1818  */
1819 static void modify_irg(be_abi_irg_t *env)
1820 {
1821         be_abi_call_t *call       = env->call;
1822         const arch_env_t *arch_env= env->birg->main_env->arch_env;
1823         const arch_register_t *sp = arch_env->sp;
1824         ir_graph *irg             = env->birg->irg;
1825         ir_node *start_bl;
1826         ir_node *end;
1827         ir_node *old_mem;
1828         ir_node *new_mem_proj;
1829         ir_node *mem;
1830         ir_type *method_type      = get_entity_type(get_irg_entity(irg));
1831
1832         int n_params;
1833         int i, n;
1834         unsigned j;
1835
1836         reg_node_map_t *rm;
1837         const arch_register_t *fp_reg;
1838         ir_node *frame_pointer;
1839         ir_node *reg_params_bl;
1840         ir_node **args;
1841         ir_node *arg_tuple;
1842         const ir_edge_t *edge;
1843         ir_type *arg_type, *bet_type, *tp;
1844         lower_frame_sels_env_t ctx;
1845         ir_entity **param_map;
1846
1847         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1848
1849         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1850
1851         /* Must fetch memory here, otherwise the start Barrier gets the wrong
1852          * memory, which leads to loops in the DAG. */
1853         old_mem = get_irg_initial_mem(irg);
1854
1855         irp_reserve_resources(irp, IR_RESOURCE_ENTITY_LINK);
1856
1857         /* set the links of all frame entities to NULL, we use it
1858            to detect if an entity is already linked in the value_param_list */
1859         tp = get_method_value_param_type(method_type);
1860         ctx.value_tp = tp;
1861         if (tp != NULL) {
1862                 /* clear the links of the clone type, let the
1863                    original entities point to its clones */
1864                 for (i = get_struct_n_members(tp) - 1; i >= 0; --i) {
1865                         ir_entity *mem  = get_struct_member(tp, i);
1866                         set_entity_link(mem, NULL);
1867                 }
1868         }
1869
1870         arg_type = compute_arg_type(env, call, method_type, tp, &param_map);
1871
1872         /* Convert the Sel nodes in the irg to frame addr nodes: */
1873         ctx.value_param_list = NEW_ARR_F(ent_pos_pair, 0);
1874         ctx.frame            = get_irg_frame(irg);
1875         ctx.sp_class         = env->arch_env->sp->reg_class;
1876         ctx.link_class       = env->arch_env->link_class;
1877         ctx.frame_tp         = get_irg_frame_type(irg);
1878
1879         /* we will possible add new entities to the frame: set the layout to undefined */
1880         assert(get_type_state(ctx.frame_tp) == layout_fixed);
1881         set_type_state(ctx.frame_tp, layout_undefined);
1882
1883         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1884
1885         /* fix the frame type layout again */
1886         set_type_state(ctx.frame_tp, layout_fixed);
1887
1888         env->regs  = pmap_create();
1889
1890         n_params = get_method_n_params(method_type);
1891         args     = obstack_alloc(&env->obst, n_params * sizeof(args[0]));
1892         memset(args, 0, n_params * sizeof(args[0]));
1893
1894         /*
1895          * for inner function we must now fix access to outer frame entities.
1896          */
1897         fix_outer_variable_access(env, &ctx);
1898
1899         /* Check if a value parameter is transmitted as a register.
1900          * This might happen if the address of an parameter is taken which is
1901          * transmitted in registers.
1902          *
1903          * Note that on some architectures this case must be handled specially
1904          * because the place of the backing store is determined by their ABI.
1905          *
1906          * In the default case we move the entity to the frame type and create
1907          * a backing store into the first block.
1908          */
1909         fix_address_of_parameter_access(env, ctx.value_param_list);
1910
1911         DEL_ARR_F(ctx.value_param_list);
1912         irp_free_resources(irp, IR_RESOURCE_ENTITY_LINK);
1913
1914         /* Fill the argument vector */
1915         arg_tuple = get_irg_args(irg);
1916         foreach_out_edge(arg_tuple, edge) {
1917                 ir_node *irn = get_edge_src_irn(edge);
1918                 if (! is_Anchor(irn)) {
1919                         int nr       = get_Proj_proj(irn);
1920                         args[nr]     = irn;
1921                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1922                 }
1923         }
1924
1925         bet_type = call->cb->get_between_type(env->cb);
1926         stack_frame_init(&env->frame, arg_type, bet_type, get_irg_frame_type(irg), arch_env->stack_dir, param_map);
1927
1928         /* Count the register params and add them to the number of Projs for the RegParams node */
1929         for (i = 0; i < n_params; ++i) {
1930                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1931                 if (arg->in_reg && args[i]) {
1932                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1933                         assert(i == get_Proj_proj(args[i]));
1934
1935                         /* For now, associate the register with the old Proj from Start representing that argument. */
1936                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1937                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1938                 }
1939         }
1940
1941         /* Collect all callee-save registers */
1942         for (i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
1943                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
1944                 for (j = 0; j < cls->n_regs; ++j) {
1945                         const arch_register_t *reg = &cls->regs[j];
1946                         if (arch_register_type_is(reg, callee_save) ||
1947                                         arch_register_type_is(reg, state)) {
1948                                 pmap_insert(env->regs, (void *) reg, NULL);
1949                         }
1950                 }
1951         }
1952
1953         pmap_insert(env->regs, (void *) sp, NULL);
1954         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1955         reg_params_bl   = get_irg_start_block(irg);
1956         env->reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(env->regs));
1957         add_irn_dep(env->reg_params, get_irg_start(irg));
1958
1959         /*
1960          * make proj nodes for the callee save registers.
1961          * memorize them, since Return nodes get those as inputs.
1962          *
1963          * Note, that if a register corresponds to an argument, the regs map contains
1964          * the old Proj from start for that argument.
1965          */
1966
1967         rm = reg_map_to_arr(&env->obst, env->regs);
1968         for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1969                 arch_register_t          *reg      = (void *) rm[i].reg;
1970                 ir_mode                  *mode     = reg->reg_class->mode;
1971                 long                      nr       = i;
1972                 arch_register_req_type_t  add_type = 0;
1973                 ir_node                  *proj;
1974
1975                 if (reg == sp)
1976                         add_type |= arch_register_req_type_produces_sp | arch_register_req_type_ignore;
1977
1978                 assert(nr >= 0);
1979                 proj = new_r_Proj(irg, reg_params_bl, env->reg_params, mode, nr);
1980                 pmap_insert(env->regs, (void *) reg, proj);
1981                 be_set_constr_single_reg_out(env->reg_params, nr, reg, add_type);
1982                 arch_set_irn_register(proj, reg);
1983
1984                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1985         }
1986         obstack_free(&env->obst, rm);
1987
1988         /* create a new initial memory proj */
1989         assert(is_Proj(old_mem));
1990         new_mem_proj = new_r_Proj(irg, get_nodes_block(old_mem),
1991                                   new_r_Unknown(irg, mode_T), mode_M,
1992                                   get_Proj_proj(old_mem));
1993         mem = new_mem_proj;
1994
1995         /* Generate the Prologue */
1996         fp_reg = call->cb->prologue(env->cb, &mem, env->regs, &env->frame.initial_bias);
1997
1998         /* do the stack allocation BEFORE the barrier, or spill code
1999            might be added before it */
2000         env->init_sp = be_abi_reg_map_get(env->regs, sp);
2001         start_bl     = get_irg_start_block(irg);
2002         env->init_sp = be_new_IncSP(sp, irg, start_bl, env->init_sp, BE_STACK_FRAME_SIZE_EXPAND, 0);
2003         be_abi_reg_map_set(env->regs, sp, env->init_sp);
2004
2005         create_barrier(env, start_bl, &mem, env->regs, 0);
2006
2007         env->init_sp = be_abi_reg_map_get(env->regs, sp);
2008         arch_set_irn_register(env->init_sp, sp);
2009
2010         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
2011         set_irg_frame(irg, frame_pointer);
2012         pset_insert_ptr(env->ignore_regs, fp_reg);
2013
2014         /* rewire old mem users to new mem */
2015         set_Proj_pred(new_mem_proj, get_Proj_pred(old_mem));
2016         exchange(old_mem, mem);
2017
2018         set_irg_initial_mem(irg, mem);
2019
2020         /* Now, introduce stack param nodes for all parameters passed on the stack */
2021         for (i = 0; i < n_params; ++i) {
2022                 ir_node *arg_proj = args[i];
2023                 ir_node *repl     = NULL;
2024
2025                 if (arg_proj != NULL) {
2026                         be_abi_call_arg_t *arg;
2027                         ir_type *param_type;
2028                         int     nr = get_Proj_proj(arg_proj);
2029                         ir_mode *mode;
2030
2031                         nr         = MIN(nr, n_params);
2032                         arg        = get_call_arg(call, 0, nr);
2033                         param_type = get_method_param_type(method_type, nr);
2034
2035                         if (arg->in_reg) {
2036                                 repl = pmap_get(env->regs, (void *) arg->reg);
2037                         } else if (arg->on_stack) {
2038                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, irg, reg_params_bl, frame_pointer, arg->stack_ent);
2039
2040                                 /* For atomic parameters which are actually used, we create a Load node. */
2041                                 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
2042                                         ir_mode *mode      = get_type_mode(param_type);
2043                                         ir_mode *load_mode = arg->load_mode;
2044
2045                                         ir_node *load = new_r_Load(irg, reg_params_bl, new_NoMem(), addr, load_mode, cons_floats);
2046                                         repl = new_r_Proj(irg, reg_params_bl, load, load_mode, pn_Load_res);
2047
2048                                         if (mode != load_mode) {
2049                                                 repl = new_r_Conv(irg, reg_params_bl, repl, mode);
2050                                         }
2051                                 } else {
2052                                         /* The stack parameter is not primitive (it is a struct or array),
2053                                          * we thus will create a node representing the parameter's address
2054                                          * on the stack. */
2055                                         repl = addr;
2056                                 }
2057                         }
2058
2059                         assert(repl != NULL);
2060
2061                         /* Beware: the mode of the register parameters is always the mode of the register class
2062                            which may be wrong. Add Conv's then. */
2063                         mode = get_irn_mode(args[i]);
2064                         if (mode != get_irn_mode(repl)) {
2065                                 repl = new_r_Conv(irg, get_irn_n(repl, -1), repl, mode);
2066                         }
2067                         exchange(args[i], repl);
2068                 }
2069         }
2070
2071         /* the arg proj is not needed anymore now and should be only used by the anchor */
2072         assert(get_irn_n_edges(arg_tuple) == 1);
2073         kill_node(arg_tuple);
2074         set_irg_args(irg, new_r_Bad(irg));
2075
2076         /* All Return nodes hang on the End node, so look for them there. */
2077         end = get_irg_end_block(irg);
2078         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
2079                 ir_node *irn = get_Block_cfgpred(end, i);
2080
2081                 if (is_Return(irn)) {
2082                         ir_node *blk = get_nodes_block(irn);
2083                         ir_node *mem = get_Return_mem(irn);
2084                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
2085                         exchange(irn, ret);
2086                 }
2087         }
2088         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
2089            the code is dead and will never be executed. */
2090
2091         obstack_free(&env->obst, args);
2092
2093         /* handle start block here (place a jump in the block) */
2094         fix_start_block(irg);
2095 }
2096
2097 /** Fix the state inputs of calls that still hang on unknowns */
2098 static
2099 void fix_call_state_inputs(be_abi_irg_t *env)
2100 {
2101         const arch_env_t *arch_env = env->arch_env;
2102         int i, n, n_states;
2103         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
2104
2105         /* Collect caller save registers */
2106         n = arch_env_get_n_reg_class(arch_env);
2107         for (i = 0; i < n; ++i) {
2108                 unsigned j;
2109                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
2110                 for (j = 0; j < cls->n_regs; ++j) {
2111                         const arch_register_t *reg = arch_register_for_index(cls, j);
2112                         if (arch_register_type_is(reg, state)) {
2113                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
2114                         }
2115                 }
2116         }
2117
2118         n = ARR_LEN(env->calls);
2119         n_states = ARR_LEN(stateregs);
2120         for (i = 0; i < n; ++i) {
2121                 int s, arity;
2122                 ir_node *call = env->calls[i];
2123
2124                 arity = get_irn_arity(call);
2125
2126                 /* the state reg inputs are the last n inputs of the calls */
2127                 for (s = 0; s < n_states; ++s) {
2128                         int inp = arity - n_states + s;
2129                         const arch_register_t *reg = stateregs[s];
2130                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
2131
2132                         set_irn_n(call, inp, regnode);
2133                 }
2134         }
2135
2136         DEL_ARR_F(stateregs);
2137 }
2138
2139 /**
2140  * Create a trampoline entity for the given method.
2141  */
2142 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
2143 {
2144         ir_type   *type   = get_entity_type(method);
2145         ident     *old_id = get_entity_ld_ident(method);
2146         ident     *id     = id_mangle3("L", old_id, "$stub");
2147         ir_type   *parent = be->pic_trampolines_type;
2148         ir_entity *ent    = new_entity(parent, old_id, type);
2149         set_entity_ld_ident(ent, id);
2150         set_entity_visibility(ent, visibility_local);
2151         set_entity_variability(ent, variability_uninitialized);
2152
2153         return ent;
2154 }
2155
2156 /**
2157  * Returns the trampoline entity for the given method.
2158  */
2159 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
2160 {
2161         ir_entity *result = pmap_get(env->ent_trampoline_map, method);
2162         if (result == NULL) {
2163                 result = create_trampoline(env, method);
2164                 pmap_insert(env->ent_trampoline_map, method, result);
2165         }
2166
2167         return result;
2168 }
2169
2170 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
2171 {
2172         ident     *old_id = get_entity_ld_ident(entity);
2173         ident     *id     = id_mangle3("L", old_id, "$non_lazy_ptr");
2174         ir_type   *e_type = get_entity_type(entity);
2175         ir_type   *type   = new_type_pointer(id, e_type, mode_P_data);
2176         ir_type   *parent = be->pic_symbols_type;
2177         ir_entity *ent    = new_entity(parent, old_id, type);
2178         set_entity_ld_ident(ent, id);
2179         set_entity_visibility(ent, visibility_local);
2180         set_entity_variability(ent, variability_uninitialized);
2181
2182         return ent;
2183 }
2184
2185 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
2186 {
2187         ir_entity *result = pmap_get(env->ent_pic_symbol_map, entity);
2188         if (result == NULL) {
2189                 result = create_pic_symbol(env, entity);
2190                 pmap_insert(env->ent_pic_symbol_map, entity, result);
2191         }
2192
2193         return result;
2194 }
2195
2196
2197
2198 /**
2199  * Returns non-zero if a given entity can be accessed using a relative address.
2200  */
2201 static int can_address_relative(ir_entity *entity)
2202 {
2203         return get_entity_variability(entity) == variability_initialized
2204                 && get_entity_visibility(entity) != visibility_external_allocated;
2205 }
2206
2207 /** patches SymConsts to work in position independent code */
2208 static void fix_pic_symconsts(ir_node *node, void *data)
2209 {
2210         ir_graph     *irg;
2211         ir_node      *pic_base;
2212         ir_node      *add;
2213         ir_node      *block;
2214         ir_node      *unknown;
2215         ir_mode      *mode;
2216         ir_node      *load;
2217         ir_node      *load_res;
2218         be_abi_irg_t *env = data;
2219         int           arity, i;
2220         be_main_env_t *be = env->birg->main_env;
2221
2222         arity = get_irn_arity(node);
2223         for (i = 0; i < arity; ++i) {
2224                 dbg_info  *dbgi;
2225                 ir_node   *pred = get_irn_n(node, i);
2226                 ir_entity *entity;
2227                 ir_entity *pic_symbol;
2228                 ir_node   *pic_symconst;
2229
2230                 if (!is_SymConst(pred))
2231                         continue;
2232
2233                 entity = get_SymConst_entity(pred);
2234                 block  = get_nodes_block(pred);
2235                 irg    = get_irn_irg(pred);
2236
2237                 /* calls can jump to relative addresses, so we can directly jump to
2238                    the (relatively) known call address or the trampoline */
2239                 if (i == 1 && is_Call(node)) {
2240                         ir_entity *trampoline;
2241                         ir_node   *trampoline_const;
2242
2243                         if (can_address_relative(entity))
2244                                 continue;
2245
2246                         dbgi             = get_irn_dbg_info(pred);
2247                         trampoline       = get_trampoline(be, entity);
2248                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2249                                                                     trampoline, NULL);
2250                         set_irn_n(node, i, trampoline_const);
2251                         continue;
2252                 }
2253
2254                 /* everything else is accessed relative to EIP */
2255                 mode     = get_irn_mode(pred);
2256                 unknown  = new_r_Unknown(irg, mode);
2257                 pic_base = arch_code_generator_get_pic_base(env->birg->cg);
2258
2259                 /* all ok now for locally constructed stuff */
2260                 if (can_address_relative(entity)) {
2261                         ir_node *add = new_r_Add(irg, block, pic_base, pred, mode);
2262
2263                         /* make sure the walker doesn't visit this add again */
2264                         mark_irn_visited(add);
2265                         set_irn_n(node, i, add);
2266                         continue;
2267                 }
2268
2269                 /* get entry from pic symbol segment */
2270                 dbgi         = get_irn_dbg_info(pred);
2271                 pic_symbol   = get_pic_symbol(be, entity);
2272                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2273                                                         pic_symbol, NULL);
2274                 add = new_r_Add(irg, block, pic_base, pic_symconst, mode);
2275                 mark_irn_visited(add);
2276
2277                 /* we need an extra indirection for global data outside our current
2278                    module. The loads are always safe and can therefore float
2279                    and need no memory input */
2280                 load     = new_r_Load(irg, block, new_NoMem(), add, mode, cons_floats);
2281                 load_res = new_r_Proj(irg, block, load, mode, pn_Load_res);
2282
2283                 set_irn_n(node, i, load_res);
2284         }
2285 }
2286
2287 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
2288 {
2289         be_abi_irg_t *env  = XMALLOC(be_abi_irg_t);
2290         ir_node *old_frame = get_irg_frame(birg->irg);
2291         ir_graph *irg      = birg->irg;
2292
2293         pmap_entry *ent;
2294         ir_node *dummy;
2295         optimization_state_t state;
2296         unsigned *limited_bitset;
2297
2298         be_omit_fp      = birg->main_env->options->omit_fp;
2299         be_omit_leaf_fp = birg->main_env->options->omit_leaf_fp;
2300
2301         obstack_init(&env->obst);
2302
2303         env->arch_env    = birg->main_env->arch_env;
2304         env->method_type = get_entity_type(get_irg_entity(irg));
2305         env->call        = be_abi_call_new(env->arch_env->sp->reg_class);
2306         arch_env_get_call_abi(env->arch_env, env->method_type, env->call);
2307
2308         env->ignore_regs  = pset_new_ptr_default();
2309         env->keep_map     = pmap_create();
2310         env->dce_survivor = new_survive_dce();
2311         env->birg         = birg;
2312
2313         env->sp_req.type    = arch_register_req_type_limited;
2314         env->sp_req.cls     = arch_register_get_class(env->arch_env->sp);
2315         limited_bitset      = rbitset_obstack_alloc(&env->obst, env->sp_req.cls->n_regs);
2316         rbitset_set(limited_bitset, arch_register_get_index(env->arch_env->sp));
2317         env->sp_req.limited = limited_bitset;
2318         if (env->arch_env->sp->type & arch_register_type_ignore) {
2319                 env->sp_req.type |= arch_register_req_type_ignore;
2320         }
2321
2322         env->sp_cls_req.type  = arch_register_req_type_normal;
2323         env->sp_cls_req.cls   = arch_register_get_class(env->arch_env->sp);
2324
2325         /* Beware: later we replace this node by the real one, ensure it is not CSE'd
2326            to another Unknown or the stack pointer gets used */
2327         save_optimization_state(&state);
2328         set_optimize(0);
2329         env->init_sp = dummy  = new_r_Unknown(irg, env->arch_env->sp->reg_class->mode);
2330         restore_optimization_state(&state);
2331
2332         FIRM_DBG_REGISTER(env->dbg, "firm.be.abi");
2333
2334         env->calls = NEW_ARR_F(ir_node*, 0);
2335
2336         if (birg->main_env->options->pic) {
2337                 irg_walk_graph(irg, fix_pic_symconsts, NULL, env);
2338         }
2339
2340         /* Lower all call nodes in the IRG. */
2341         process_calls(env);
2342
2343         /*
2344                 Beware: init backend abi call object after processing calls,
2345                 otherwise some information might be not yet available.
2346         */
2347         env->cb = env->call->cb->init(env->call, birg->main_env->arch_env, irg);
2348
2349         /* Process the IRG */
2350         modify_irg(env);
2351
2352         /* fix call inputs for state registers */
2353         fix_call_state_inputs(env);
2354
2355         /* We don't need the keep map anymore. */
2356         pmap_destroy(env->keep_map);
2357         env->keep_map = NULL;
2358
2359         /* calls array is not needed anymore */
2360         DEL_ARR_F(env->calls);
2361         env->calls = NULL;
2362
2363         /* reroute the stack origin of the calls to the true stack origin. */
2364         exchange(dummy, env->init_sp);
2365         exchange(old_frame, get_irg_frame(irg));
2366
2367         /* Make some important node pointers survive the dead node elimination. */
2368         survive_dce_register_irn(env->dce_survivor, &env->init_sp);
2369         foreach_pmap(env->regs, ent) {
2370                 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
2371         }
2372
2373         env->call->cb->done(env->cb);
2374         env->cb = NULL;
2375         return env;
2376 }
2377
2378 void be_abi_free(be_abi_irg_t *env)
2379 {
2380         be_abi_call_free(env->call);
2381         free_survive_dce(env->dce_survivor);
2382         del_pset(env->ignore_regs);
2383         pmap_destroy(env->regs);
2384         obstack_free(&env->obst, NULL);
2385         free(env);
2386 }
2387
2388 void be_abi_put_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, bitset_t *bs)
2389 {
2390         arch_register_t *reg;
2391
2392         for (reg = pset_first(abi->ignore_regs); reg; reg = pset_next(abi->ignore_regs))
2393                 if (reg->reg_class == cls)
2394                         bitset_set(bs, reg->index);
2395 }
2396
2397 void be_abi_set_non_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, unsigned *raw_bitset)
2398 {
2399         unsigned         i;
2400         arch_register_t *reg;
2401
2402         for (i = 0; i < cls->n_regs; ++i) {
2403                 if (arch_register_type_is(&cls->regs[i], ignore))
2404                         continue;
2405
2406                 rbitset_set(raw_bitset, i);
2407         }
2408
2409         for (reg = pset_first(abi->ignore_regs); reg != NULL;
2410              reg = pset_next(abi->ignore_regs)) {
2411                 if (reg->reg_class != cls)
2412                         continue;
2413
2414                 rbitset_clear(raw_bitset, reg->index);
2415         }
2416 }
2417
2418 /* Returns the stack layout from a abi environment. */
2419 const be_stack_layout_t *be_abi_get_stack_layout(const be_abi_irg_t *abi)
2420 {
2421         return &abi->frame;
2422 }
2423
2424 /*
2425
2426   _____ _        ____  _             _
2427  |  ___(_)_  __ / ___|| |_ __ _  ___| | __
2428  | |_  | \ \/ / \___ \| __/ _` |/ __| |/ /
2429  |  _| | |>  <   ___) | || (_| | (__|   <
2430  |_|   |_/_/\_\ |____/ \__\__,_|\___|_|\_\
2431
2432 */
2433
2434 typedef ir_node **node_array;
2435
2436 typedef struct fix_stack_walker_env_t {
2437         node_array sp_nodes;
2438 } fix_stack_walker_env_t;
2439
2440 /**
2441  * Walker. Collect all stack modifying nodes.
2442  */
2443 static void collect_stack_nodes_walker(ir_node *node, void *data)
2444 {
2445         fix_stack_walker_env_t    *env = data;
2446         const arch_register_req_t *req;
2447
2448         if (get_irn_mode(node) == mode_T)
2449                 return;
2450
2451         req = arch_get_register_req_out(node);
2452         if (! (req->type & arch_register_req_type_produces_sp))
2453                 return;
2454
2455         ARR_APP1(ir_node*, env->sp_nodes, node);
2456 }
2457
2458 void be_abi_fix_stack_nodes(be_abi_irg_t *env)
2459 {
2460         be_ssa_construction_env_t senv;
2461         int i, len;
2462         ir_node **phis;
2463         be_irg_t *birg = env->birg;
2464         be_lv_t *lv = be_get_birg_liveness(birg);
2465         fix_stack_walker_env_t walker_env;
2466
2467         walker_env.sp_nodes = NEW_ARR_F(ir_node*, 0);
2468
2469         irg_walk_graph(birg->irg, collect_stack_nodes_walker, NULL, &walker_env);
2470
2471         /* nothing to be done if we didn't find any node, in fact we mustn't
2472          * continue, as for endless loops incsp might have had no users and is bad
2473          * now.
2474          */
2475         len = ARR_LEN(walker_env.sp_nodes);
2476         if (len == 0) {
2477                 DEL_ARR_F(walker_env.sp_nodes);
2478                 return;
2479         }
2480
2481         be_ssa_construction_init(&senv, birg);
2482         be_ssa_construction_add_copies(&senv, walker_env.sp_nodes,
2483                                    ARR_LEN(walker_env.sp_nodes));
2484         be_ssa_construction_fix_users_array(&senv, walker_env.sp_nodes,
2485                                             ARR_LEN(walker_env.sp_nodes));
2486
2487         if (lv != NULL) {
2488                 len = ARR_LEN(walker_env.sp_nodes);
2489                 for (i = 0; i < len; ++i) {
2490                         be_liveness_update(lv, walker_env.sp_nodes[i]);
2491                 }
2492                 be_ssa_construction_update_liveness_phis(&senv, lv);
2493         }
2494
2495         phis = be_ssa_construction_get_new_phis(&senv);
2496
2497         /* set register requirements for stack phis */
2498         len = ARR_LEN(phis);
2499         for (i = 0; i < len; ++i) {
2500                 ir_node *phi = phis[i];
2501                 be_set_phi_reg_req(phi, &env->sp_req, arch_register_req_type_produces_sp);
2502                 arch_set_irn_register(phi, env->arch_env->sp);
2503         }
2504         be_ssa_construction_destroy(&senv);
2505
2506         DEL_ARR_F(walker_env.sp_nodes);
2507 }
2508
2509 /**
2510  * Fix all stack accessing operations in the block bl.
2511  *
2512  * @param env        the abi environment
2513  * @param bl         the block to process
2514  * @param real_bias  the bias value
2515  *
2516  * @return the bias at the end of this block
2517  */
2518 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int real_bias)
2519 {
2520         int               omit_fp  = env->call->flags.bits.try_omit_fp;
2521         ir_node          *irn;
2522         int               wanted_bias = real_bias;
2523
2524         sched_foreach(bl, irn) {
2525                 int ofs;
2526
2527                 /*
2528                    Check, if the node relates to an entity on the stack frame.
2529                    If so, set the true offset (including the bias) for that
2530                    node.
2531                  */
2532                 ir_entity *ent = arch_get_frame_entity(irn);
2533                 if (ent != NULL) {
2534                         int bias   = omit_fp ? real_bias : 0;
2535                         int offset = get_stack_entity_offset(&env->frame, ent, bias);
2536                         arch_set_frame_offset(irn, offset);
2537                         DBG((env->dbg, LEVEL_2, "%F has offset %d (including bias %d)\n",
2538                              ent, offset, bias));
2539                 }
2540
2541                 /*
2542                  * If the node modifies the stack pointer by a constant offset,
2543                  * record that in the bias.
2544                  */
2545                 ofs = arch_get_sp_bias(irn);
2546
2547                 if (be_is_IncSP(irn)) {
2548                         /* fill in real stack frame size */
2549                         if (ofs == BE_STACK_FRAME_SIZE_EXPAND) {
2550                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2551                                 ofs = (int) get_type_size_bytes(frame_type);
2552                                 be_set_IncSP_offset(irn, ofs);
2553                         } else if (ofs == BE_STACK_FRAME_SIZE_SHRINK) {
2554                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2555                                 ofs = - (int)get_type_size_bytes(frame_type);
2556                                 be_set_IncSP_offset(irn, ofs);
2557                         } else {
2558                                 if (be_get_IncSP_align(irn)) {
2559                                         /* patch IncSP to produce an aligned stack pointer */
2560                                         ir_type *between_type = env->frame.between_type;
2561                                         int      between_size = get_type_size_bytes(between_type);
2562                                         int      alignment    = 1 << env->arch_env->stack_alignment;
2563                                         int      delta        = (real_bias + ofs + between_size) & (alignment - 1);
2564                                         assert(ofs >= 0);
2565                                         if (delta > 0) {
2566                                                 be_set_IncSP_offset(irn, ofs + alignment - delta);
2567                                                 real_bias += alignment - delta;
2568                                         }
2569                                 } else {
2570                                         /* adjust so real_bias corresponds with wanted_bias */
2571                                         int delta = wanted_bias - real_bias;
2572                                         assert(delta <= 0);
2573                                         if (delta != 0) {
2574                                                 be_set_IncSP_offset(irn, ofs + delta);
2575                                                 real_bias += delta;
2576                                         }
2577                                 }
2578                         }
2579                 }
2580
2581                 real_bias   += ofs;
2582                 wanted_bias += ofs;
2583         }
2584
2585         assert(real_bias == wanted_bias);
2586         return real_bias;
2587 }
2588
2589 /**
2590  * A helper struct for the bias walker.
2591  */
2592 struct bias_walk {
2593         be_abi_irg_t *env;     /**< The ABI irg environment. */
2594         int           start_block_bias;  /**< The bias at the end of the start block. */
2595         int           between_size;
2596         ir_node      *start_block;  /**< The start block of the current graph. */
2597 };
2598
2599 /**
2600  * Block-Walker: fix all stack offsets for all blocks
2601  * except the start block
2602  */
2603 static void stack_bias_walker(ir_node *bl, void *data)
2604 {
2605         struct bias_walk *bw = data;
2606         if (bl != bw->start_block) {
2607                 process_stack_bias(bw->env, bl, bw->start_block_bias);
2608         }
2609 }
2610
2611 /**
2612  * Walker: finally lower all Sels of outer frame or parameter
2613  * entities.
2614  */
2615 static void lower_outer_frame_sels(ir_node *sel, void *ctx) {
2616         be_abi_irg_t *env = ctx;
2617         ir_node      *ptr;
2618         ir_entity    *ent;
2619         ir_type      *owner;
2620
2621         if (! is_Sel(sel))
2622                 return;
2623
2624         ent   = get_Sel_entity(sel);
2625         owner = get_entity_owner(ent);
2626         ptr   = get_Sel_ptr(sel);
2627
2628         if (owner == env->frame.frame_type || owner == env->frame.arg_type) {
2629                 /* found access to outer frame or arguments */
2630                 int offset = get_stack_entity_offset(&env->frame, ent, 0);
2631
2632                 if (offset != 0) {
2633                         ir_node  *bl   = get_nodes_block(sel);
2634                         dbg_info *dbgi = get_irn_dbg_info(sel);
2635                         ir_mode  *mode = get_irn_mode(sel);
2636                         ir_mode  *mode_UInt = get_reference_mode_unsigned_eq(mode);
2637                         ir_node  *cnst = new_r_Const_long(current_ir_graph, mode_UInt, offset);
2638
2639                         ptr = new_rd_Add(dbgi, current_ir_graph, bl, ptr, cnst, mode);
2640                 }
2641                 exchange(sel, ptr);
2642         }
2643 }
2644
2645 void be_abi_fix_stack_bias(be_abi_irg_t *env)
2646 {
2647         ir_graph          *irg = env->birg->irg;
2648         ir_type           *frame_tp;
2649         int               i;
2650         struct bias_walk  bw;
2651
2652         stack_frame_compute_initial_offset(&env->frame);
2653         // stack_layout_dump(stdout, frame);
2654
2655         /* Determine the stack bias at the end of the start block. */
2656         bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), env->frame.initial_bias);
2657         bw.between_size     = get_type_size_bytes(env->frame.between_type);
2658
2659         /* fix the bias is all other blocks */
2660         bw.env = env;
2661         bw.start_block = get_irg_start_block(irg);
2662         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
2663
2664         /* fix now inner functions: these still have Sel node to outer
2665            frame and parameter entities */
2666         frame_tp = get_irg_frame_type(irg);
2667         for (i = get_class_n_members(frame_tp) - 1; i >= 0; --i) {
2668                 ir_entity *ent = get_class_member(frame_tp, i);
2669
2670                 if (is_method_entity(ent) && get_entity_peculiarity(ent) != peculiarity_description) {
2671                         ir_graph *irg = get_entity_irg(ent);
2672
2673                         irg_walk_graph(irg, NULL, lower_outer_frame_sels, env);
2674                 }
2675         }
2676 }
2677
2678 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2679 {
2680         assert(arch_register_type_is(reg, callee_save));
2681         assert(pmap_contains(abi->regs, (void *) reg));
2682         return pmap_get(abi->regs, (void *) reg);
2683 }
2684
2685 ir_node *be_abi_get_ignore_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2686 {
2687         assert(arch_register_type_is(reg, ignore));
2688         assert(pmap_contains(abi->regs, (void *) reg));
2689         return pmap_get(abi->regs, (void *) reg);
2690 }
2691
2692 /**
2693  * Returns non-zero if the ABI has omitted the frame pointer in
2694  * the current graph.
2695  */
2696 int be_abi_omit_fp(const be_abi_irg_t *abi)
2697 {
2698         return abi->call->flags.bits.try_omit_fp;
2699 }