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         be_abi_irg_t *env  = data;
1125         ir_opcode     code = get_irn_opcode(irn);
1126
1127         if (code == iro_Call ||
1128            (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
1129            (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
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         if (code == iro_Builtin && get_Builtin_kind(irn) == ir_bk_return_address) {
1141                 ir_node       *param = get_Builtin_param(irn, 0);
1142                 tarval        *tv    = get_Const_tarval(param);
1143                 unsigned long  value = get_tarval_long(tv);
1144                 /* use ebp, so the climbframe algo works... */
1145                 if (value > 0) {
1146                         env->call->flags.bits.try_omit_fp = 0;
1147                 }
1148         }
1149 }
1150
1151 /**
1152  * Block-walker:
1153  * Process all Call/Alloc/Free nodes inside a basic block.
1154  * Note that the link field of the block must contain a linked list of all
1155  * Call nodes inside the Block. We first order this list according to data dependency
1156  * and that connect the calls together.
1157  */
1158 static void process_ops_in_block(ir_node *bl, void *data)
1159 {
1160         be_abi_irg_t *env = data;
1161         ir_node *curr_sp  = env->init_sp;
1162         ir_node *irn;
1163         int n;
1164
1165         for (irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
1166                 obstack_ptr_grow(&env->obst, irn);
1167
1168         /* If there were call nodes in the block. */
1169         if (n > 0) {
1170                 ir_node *keep;
1171                 ir_node **nodes;
1172                 int i;
1173
1174                 nodes = obstack_finish(&env->obst);
1175
1176                 /* order the call nodes according to data dependency */
1177                 qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependency);
1178
1179                 for (i = n - 1; i >= 0; --i) {
1180                         ir_node *irn = nodes[i];
1181
1182                         DBG((env->dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1183                         switch (get_irn_opcode(irn)) {
1184                         case iro_Call:
1185                                 if (! be_omit_fp) {
1186                                         /* The stack pointer will be modified due to a call. */
1187                                         env->call->flags.bits.try_omit_fp = 0;
1188                                 }
1189                                 curr_sp = adjust_call(env, irn, curr_sp);
1190                                 break;
1191                         case iro_Alloc:
1192                                 if (get_Alloc_where(irn) == stack_alloc)
1193                                         curr_sp = adjust_alloc(env, irn, curr_sp);
1194                                 break;
1195                         case iro_Free:
1196                                 if (get_Free_where(irn) == stack_alloc)
1197                                         curr_sp = adjust_free(env, irn, curr_sp);
1198                                 break;
1199                         default:
1200                                 panic("invalid call");
1201                                 break;
1202                         }
1203                 }
1204
1205                 obstack_free(&env->obst, nodes);
1206
1207                 /* Keep the last stack state in the block by tying it to Keep node,
1208                  * the proj from calls is already kept */
1209                 if (curr_sp != env->init_sp &&
1210                     !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1211                         nodes[0] = curr_sp;
1212                         keep     = be_new_Keep(env->arch_env->sp->reg_class,
1213                                                get_irn_irg(bl), bl, 1, nodes);
1214                         pmap_insert(env->keep_map, bl, keep);
1215                 }
1216         }
1217
1218         set_irn_link(bl, curr_sp);
1219 }  /* process_ops_in_block */
1220
1221 /**
1222  * Adjust all call nodes in the graph to the ABI conventions.
1223  */
1224 static void process_calls(be_abi_irg_t *env)
1225 {
1226         ir_graph *irg = env->birg->irg;
1227
1228         env->call->flags.bits.irg_is_leaf = 1;
1229         irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, env);
1230
1231         ir_heights = heights_new(env->birg->irg);
1232         irg_block_walk_graph(irg, NULL, process_ops_in_block, env);
1233         heights_free(ir_heights);
1234 }
1235
1236 /**
1237  * Computes the stack argument layout type.
1238  * Changes a possibly allocated value param type by moving
1239  * entities to the stack layout type.
1240  *
1241  * @param env           the ABI environment
1242  * @param call          the current call ABI
1243  * @param method_type   the method type
1244  * @param val_param_tp  the value parameter type, will be destroyed
1245  * @param param_map     an array mapping method arguments to the stack layout type
1246  *
1247  * @return the stack argument layout type
1248  */
1249 static ir_type *compute_arg_type(be_abi_irg_t *env, be_abi_call_t *call,
1250                                                                  ir_type *method_type, ir_type *val_param_tp,
1251                                                                  ir_entity ***param_map)
1252 {
1253         int dir  = env->call->flags.bits.left_to_right ? 1 : -1;
1254         int inc  = env->birg->main_env->arch_env->stack_dir * dir;
1255         int n    = get_method_n_params(method_type);
1256         int curr = inc > 0 ? 0 : n - 1;
1257         int ofs  = 0;
1258
1259         char buf[128];
1260         ir_type *res;
1261         int i;
1262         ident *id = get_entity_ident(get_irg_entity(env->birg->irg));
1263         ir_entity **map;
1264
1265         *param_map = map = obstack_alloc(&env->obst, n * sizeof(ir_entity *));
1266         res = new_type_struct(id_mangle_u(id, new_id_from_chars("arg_type", 8)));
1267         for (i = 0; i < n; ++i, curr += inc) {
1268                 ir_type *param_type    = get_method_param_type(method_type, curr);
1269                 be_abi_call_arg_t *arg = get_call_arg(call, 0, curr);
1270
1271                 map[i] = NULL;
1272                 if (arg->on_stack) {
1273                         if (val_param_tp != NULL) {
1274                                 /* the entity was already created, create a copy in the param type */
1275                                 ir_entity *val_ent = get_method_value_param_ent(method_type, i);
1276                                 arg->stack_ent = copy_entity_own(val_ent, res);
1277                                 set_entity_link(val_ent, arg->stack_ent);
1278                                 set_entity_link(arg->stack_ent, NULL);
1279                                 /* must be automatic to set a fixed layout */
1280                                 set_entity_allocation(arg->stack_ent, allocation_automatic);
1281                         } else {
1282                                 /* create a new entity */
1283                                 snprintf(buf, sizeof(buf), "param_%d", i);
1284                                 arg->stack_ent = new_entity(res, new_id_from_str(buf), param_type);
1285                         }
1286                         ofs += arg->space_before;
1287                         ofs = round_up2(ofs, arg->alignment);
1288                         set_entity_offset(arg->stack_ent, ofs);
1289                         ofs += arg->space_after;
1290                         ofs += get_type_size_bytes(param_type);
1291                         map[i] = arg->stack_ent;
1292                 }
1293         }
1294         set_type_size_bytes(res, ofs);
1295         set_type_state(res, layout_fixed);
1296         return res;
1297 }
1298
1299 typedef struct {
1300         const arch_register_t *reg;
1301         ir_node *irn;
1302 } reg_node_map_t;
1303
1304 static int cmp_regs(const void *a, const void *b)
1305 {
1306         const reg_node_map_t *p = a;
1307         const reg_node_map_t *q = b;
1308
1309         if (p->reg->reg_class == q->reg->reg_class)
1310                 return p->reg->index - q->reg->index;
1311         else
1312                 return p->reg->reg_class - q->reg->reg_class;
1313 }
1314
1315 static reg_node_map_t *reg_map_to_arr(struct obstack *obst, pmap *reg_map)
1316 {
1317         pmap_entry *ent;
1318         int n = pmap_count(reg_map);
1319         int i = 0;
1320         reg_node_map_t *res = obstack_alloc(obst, n * sizeof(res[0]));
1321
1322         foreach_pmap(reg_map, ent) {
1323                 res[i].reg = ent->key;
1324                 res[i].irn = ent->value;
1325                 i++;
1326         }
1327
1328         qsort(res, n, sizeof(res[0]), cmp_regs);
1329         return res;
1330 }
1331
1332 /**
1333  * Creates a barrier.
1334  */
1335 static ir_node *create_barrier(be_abi_irg_t *env, ir_node *bl, ir_node **mem, pmap *regs, int in_req)
1336 {
1337         ir_graph *irg = env->birg->irg;
1338         int n_regs    = pmap_count(regs);
1339         int n;
1340         ir_node *irn;
1341         ir_node **in;
1342         reg_node_map_t *rm;
1343
1344         rm = reg_map_to_arr(&env->obst, regs);
1345
1346         for (n = 0; n < n_regs; ++n)
1347                 obstack_ptr_grow(&env->obst, rm[n].irn);
1348
1349         if (mem) {
1350                 obstack_ptr_grow(&env->obst, *mem);
1351                 n++;
1352         }
1353
1354         in = (ir_node **) obstack_finish(&env->obst);
1355         irn = be_new_Barrier(irg, bl, n, in);
1356         obstack_free(&env->obst, in);
1357
1358         for (n = 0; n < n_regs; ++n) {
1359                 ir_node                   *pred     = rm[n].irn;
1360                 const arch_register_t     *reg      = rm[n].reg;
1361                 arch_register_type_t       add_type = 0;
1362                 ir_node                   *proj;
1363
1364                 /* stupid workaround for now... as not all nodes report register
1365                  * requirements. */
1366                 if (!is_Phi(pred)) {
1367                         const arch_register_req_t *ireq = arch_get_register_req_out(pred);
1368                         if (ireq->type & arch_register_req_type_ignore)
1369                                 add_type |= arch_register_req_type_ignore;
1370                         if (ireq->type & arch_register_req_type_produces_sp)
1371                                 add_type |= arch_register_req_type_produces_sp;
1372                 }
1373
1374                 proj = new_r_Proj(irg, bl, irn, get_irn_mode(pred), n);
1375                 be_node_set_reg_class_in(irn, n, reg->reg_class);
1376                 if (in_req)
1377                         be_set_constr_single_reg_in(irn, n, reg, 0);
1378                 be_set_constr_single_reg_out(irn, n, reg, add_type);
1379                 arch_set_irn_register(proj, reg);
1380
1381                 pmap_insert(regs, (void *) reg, proj);
1382         }
1383
1384         if (mem) {
1385                 *mem = new_r_Proj(irg, bl, irn, mode_M, n);
1386         }
1387
1388         obstack_free(&env->obst, rm);
1389         return irn;
1390 }
1391
1392 /**
1393  * Creates a be_Return for a Return node.
1394  *
1395  * @param @env    the abi environment
1396  * @param irn     the Return node or NULL if there was none
1397  * @param bl      the block where the be_Retun should be placed
1398  * @param mem     the current memory
1399  * @param n_res   number of return results
1400  */
1401 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1402                 ir_node *mem, int n_res)
1403 {
1404         be_abi_call_t    *call     = env->call;
1405         const arch_env_t *arch_env = env->birg->main_env->arch_env;
1406         dbg_info *dbgi;
1407         pmap *reg_map  = pmap_create();
1408         ir_node *keep  = pmap_get(env->keep_map, bl);
1409         int in_max;
1410         ir_node *ret;
1411         int i, n;
1412         unsigned pop;
1413         ir_node **in;
1414         ir_node *stack;
1415         const arch_register_t **regs;
1416         pmap_entry *ent ;
1417
1418         /*
1419                 get the valid stack node in this block.
1420                 If we had a call in that block there is a Keep constructed by process_calls()
1421                 which points to the last stack modification in that block. we'll use
1422                 it then. Else we use the stack from the start block and let
1423                 the ssa construction fix the usage.
1424         */
1425         stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1426         if (keep) {
1427                 stack = get_irn_n(keep, 0);
1428                 kill_node(keep);
1429                 remove_End_keepalive(get_irg_end(env->birg->irg), keep);
1430         }
1431
1432         /* Insert results for Return into the register map. */
1433         for (i = 0; i < n_res; ++i) {
1434                 ir_node *res           = get_Return_res(irn, i);
1435                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1436                 assert(arg->in_reg && "return value must be passed in register");
1437                 pmap_insert(reg_map, (void *) arg->reg, res);
1438         }
1439
1440         /* Add uses of the callee save registers. */
1441         foreach_pmap(env->regs, ent) {
1442                 const arch_register_t *reg = ent->key;
1443                 if (arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1444                         pmap_insert(reg_map, ent->key, ent->value);
1445         }
1446
1447         be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1448
1449         /* Make the Epilogue node and call the arch's epilogue maker. */
1450         create_barrier(env, bl, &mem, reg_map, 1);
1451         call->cb->epilogue(env->cb, bl, &mem, reg_map);
1452
1453         /*
1454                 Maximum size of the in array for Return nodes is
1455                 return args + callee save/ignore registers + memory + stack pointer
1456         */
1457         in_max = pmap_count(reg_map) + n_res + 2;
1458
1459         in   = obstack_alloc(&env->obst, in_max * sizeof(in[0]));
1460         regs = obstack_alloc(&env->obst, in_max * sizeof(regs[0]));
1461
1462         in[0]   = mem;
1463         in[1]   = be_abi_reg_map_get(reg_map, arch_env->sp);
1464         regs[0] = NULL;
1465         regs[1] = arch_env->sp;
1466         n       = 2;
1467
1468         /* clear SP entry, since it has already been grown. */
1469         pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1470         for (i = 0; i < n_res; ++i) {
1471                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1472
1473                 in[n]     = be_abi_reg_map_get(reg_map, arg->reg);
1474                 regs[n++] = arg->reg;
1475
1476                 /* Clear the map entry to mark the register as processed. */
1477                 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1478         }
1479
1480         /* grow the rest of the stuff. */
1481         foreach_pmap(reg_map, ent) {
1482                 if (ent->value) {
1483                         in[n]     = ent->value;
1484                         regs[n++] = ent->key;
1485                 }
1486         }
1487
1488         /* The in array for the new back end return is now ready. */
1489         if (irn != NULL) {
1490                 dbgi = get_irn_dbg_info(irn);
1491         } else {
1492                 dbgi = NULL;
1493         }
1494         /* we have to pop the shadow parameter in in case of struct returns */
1495         pop = call->pop;
1496         ret = be_new_Return(dbgi, env->birg->irg, bl, n_res, pop, n, in);
1497
1498         /* Set the register classes of the return's parameter accordingly. */
1499         for (i = 0; i < n; ++i) {
1500                 if (regs[i] == NULL)
1501                         continue;
1502
1503                 be_node_set_reg_class_in(ret, i, regs[i]->reg_class);
1504         }
1505
1506         /* Free the space of the Epilog's in array and the register <-> proj map. */
1507         obstack_free(&env->obst, in);
1508         pmap_destroy(reg_map);
1509
1510         return ret;
1511 }
1512
1513 typedef struct ent_pos_pair ent_pos_pair;
1514 struct ent_pos_pair {
1515         ir_entity    *ent;   /**< a value param entity */
1516         int          pos;    /**< its parameter number */
1517         ent_pos_pair *next;  /**< for linking */
1518 };
1519
1520 typedef struct lower_frame_sels_env_t {
1521         ent_pos_pair *value_param_list;          /**< the list of all value param entities */
1522         ir_node      *frame;                     /**< the current frame */
1523         const arch_register_class_t *sp_class;   /**< register class of the stack pointer */
1524         const arch_register_class_t *link_class; /**< register class of the link pointer */
1525         ir_type      *value_tp;                  /**< the value type if any */
1526         ir_type      *frame_tp;                  /**< the frame type */
1527         int          static_link_pos;            /**< argument number of the hidden static link */
1528 } lower_frame_sels_env_t;
1529
1530 /**
1531  * Return an entity from the backend for an value param entity.
1532  *
1533  * @param ent  an value param type entity
1534  * @param ctx  context
1535  */
1536 static ir_entity *get_argument_entity(ir_entity *ent, lower_frame_sels_env_t *ctx)
1537 {
1538         ir_entity *argument_ent = get_entity_link(ent);
1539
1540         if (argument_ent == NULL) {
1541                 /* we have NO argument entity yet: This is bad, as we will
1542                 * need one for backing store.
1543                 * Create one here.
1544                 */
1545                 ir_type *frame_tp = ctx->frame_tp;
1546                 unsigned offset   = get_type_size_bytes(frame_tp);
1547                 ir_type  *tp      = get_entity_type(ent);
1548                 unsigned align    = get_type_alignment_bytes(tp);
1549
1550                 offset += align - 1;
1551                 offset &= ~(align - 1);
1552
1553                 argument_ent = copy_entity_own(ent, frame_tp);
1554
1555                 /* must be automatic to set a fixed layout */
1556                 set_entity_allocation(argument_ent, allocation_automatic);
1557                 set_entity_offset(argument_ent, offset);
1558                 offset += get_type_size_bytes(tp);
1559
1560                 set_type_size_bytes(frame_tp, offset);
1561                 set_entity_link(ent, argument_ent);
1562         }
1563         return argument_ent;
1564 }
1565 /**
1566  * Walker: Replaces Sels of frame type and
1567  * value param type entities by FrameAddress.
1568  * Links all used entities.
1569  */
1570 static void lower_frame_sels_walker(ir_node *irn, void *data)
1571 {
1572         lower_frame_sels_env_t *ctx = data;
1573
1574         if (is_Sel(irn)) {
1575                 ir_node *ptr = get_Sel_ptr(irn);
1576
1577                 if (ptr == ctx->frame) {
1578                         ir_entity    *ent = get_Sel_entity(irn);
1579                         ir_node      *bl  = get_nodes_block(irn);
1580                         ir_node      *nw;
1581                         int          pos = 0;
1582                         int          is_value_param = 0;
1583
1584                         if (get_entity_owner(ent) == ctx->value_tp) {
1585                                 is_value_param = 1;
1586
1587                                 /* replace by its copy from the argument type */
1588                                 pos = get_struct_member_index(ctx->value_tp, ent);
1589                                 ent = get_argument_entity(ent, ctx);
1590                         }
1591
1592                         nw = be_new_FrameAddr(ctx->sp_class, current_ir_graph, bl, ctx->frame, ent);
1593                         exchange(irn, nw);
1594
1595                         /* check, if it's a param Sel and if have not seen this entity before */
1596                         if (is_value_param && get_entity_link(ent) == NULL) {
1597                                 ent_pos_pair pair;
1598
1599                                 pair.ent  = ent;
1600                                 pair.pos  = pos;
1601                                 pair.next = NULL;
1602                                 ARR_APP1(ent_pos_pair, ctx->value_param_list, pair);
1603                                 /* just a mark */
1604                                 set_entity_link(ent, ctx->value_param_list);
1605                         }
1606                 }
1607         }
1608 }
1609
1610 /**
1611  * Check if a value parameter is transmitted as a register.
1612  * This might happen if the address of an parameter is taken which is
1613  * transmitted in registers.
1614  *
1615  * Note that on some architectures this case must be handled specially
1616  * because the place of the backing store is determined by their ABI.
1617  *
1618  * In the default case we move the entity to the frame type and create
1619  * a backing store into the first block.
1620  */
1621 static void fix_address_of_parameter_access(be_abi_irg_t *env, ent_pos_pair *value_param_list)
1622 {
1623         be_abi_call_t *call = env->call;
1624         ir_graph      *irg  = env->birg->irg;
1625         ent_pos_pair  *entry, *new_list;
1626         ir_type       *frame_tp;
1627         int           i, n = ARR_LEN(value_param_list);
1628         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1629
1630         new_list = NULL;
1631         for (i = 0; i < n; ++i) {
1632                 int               pos  = value_param_list[i].pos;
1633                 be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
1634
1635                 if (arg->in_reg) {
1636                         DBG((dbg, LEVEL_2, "\targ #%d need backing store\n", pos));
1637                         value_param_list[i].next = new_list;
1638                         new_list = &value_param_list[i];
1639                 }
1640         }
1641         if (new_list != NULL) {
1642                 /* ok, change the graph */
1643                 ir_node *start_bl = get_irg_start_block(irg);
1644                 ir_node *first_bl = NULL;
1645                 ir_node *frame, *imem, *nmem, *store, *mem, *args, *args_bl;
1646                 const ir_edge_t *edge;
1647                 optimization_state_t state;
1648                 unsigned offset;
1649
1650                 foreach_block_succ(start_bl, edge) {
1651                         first_bl = get_edge_src_irn(edge);
1652                         break;
1653                 }
1654                 assert(first_bl && first_bl != start_bl);
1655                 /* we had already removed critical edges, so the following
1656                    assertion should be always true. */
1657                 assert(get_Block_n_cfgpreds(first_bl) == 1);
1658
1659                 /* now create backing stores */
1660                 frame = get_irg_frame(irg);
1661                 imem = get_irg_initial_mem(irg);
1662
1663                 save_optimization_state(&state);
1664                 set_optimize(0);
1665                 nmem = new_r_Proj(irg, start_bl, get_irg_start(irg), mode_M, pn_Start_M);
1666                 restore_optimization_state(&state);
1667
1668                 /* reroute all edges to the new memory source */
1669                 edges_reroute(imem, nmem, irg);
1670
1671                 store   = NULL;
1672                 mem     = imem;
1673                 args    = get_irg_args(irg);
1674                 args_bl = get_nodes_block(args);
1675                 for (entry = new_list; entry != NULL; entry = entry->next) {
1676                         int     i     = entry->pos;
1677                         ir_type *tp   = get_entity_type(entry->ent);
1678                         ir_mode *mode = get_type_mode(tp);
1679                         ir_node *addr;
1680
1681                         /* address for the backing store */
1682                         addr = be_new_FrameAddr(env->arch_env->sp->reg_class, irg, first_bl, frame, entry->ent);
1683
1684                         if (store)
1685                                 mem = new_r_Proj(irg, first_bl, store, mode_M, pn_Store_M);
1686
1687                         /* the backing store itself */
1688                         store = new_r_Store(irg, first_bl, mem, addr,
1689                                             new_r_Proj(irg, args_bl, args, mode, i), 0);
1690                 }
1691                 /* the new memory Proj gets the last Proj from store */
1692                 set_Proj_pred(nmem, store);
1693                 set_Proj_proj(nmem, pn_Store_M);
1694
1695                 /* move all entities to the frame type */
1696                 frame_tp = get_irg_frame_type(irg);
1697                 offset   = get_type_size_bytes(frame_tp);
1698
1699                 /* we will add new entities: set the layout to undefined */
1700                 assert(get_type_state(frame_tp) == layout_fixed);
1701                 set_type_state(frame_tp, layout_undefined);
1702                 for (entry = new_list; entry != NULL; entry = entry->next) {
1703                         ir_entity *ent = entry->ent;
1704
1705                         /* If the entity is still on the argument type, move it to the frame type.
1706                            This happens if the value_param type was build due to compound
1707                            params. */
1708                         if (get_entity_owner(ent) != frame_tp) {
1709                                 ir_type  *tp   = get_entity_type(ent);
1710                                 unsigned align = get_type_alignment_bytes(tp);
1711
1712                                 offset += align - 1;
1713                                 offset &= ~(align - 1);
1714                                 set_entity_owner(ent, frame_tp);
1715                                 add_class_member(frame_tp, ent);
1716                                 /* must be automatic to set a fixed layout */
1717                                 set_entity_allocation(ent, allocation_automatic);
1718                                 set_entity_offset(ent, offset);
1719                                 offset += get_type_size_bytes(tp);
1720                         }
1721                 }
1722                 set_type_size_bytes(frame_tp, offset);
1723                 /* fix the layout again */
1724                 set_type_state(frame_tp, layout_fixed);
1725         }
1726 }
1727
1728 /**
1729  * The start block has no jump, instead it has an initial exec Proj.
1730  * The backend wants to handle all blocks the same way, so we replace
1731  * the out cfg edge with a real jump.
1732  */
1733 static void fix_start_block(ir_graph *irg)
1734 {
1735         ir_node         *initial_X   = get_irg_initial_exec(irg);
1736         ir_node         *start_block = get_irg_start_block(irg);
1737         const ir_edge_t *edge;
1738
1739         assert(is_Proj(initial_X));
1740
1741         foreach_out_edge(initial_X, edge) {
1742                 ir_node *block = get_edge_src_irn(edge);
1743
1744                 if (is_Anchor(block))
1745                         continue;
1746                 if (block != start_block) {
1747                         ir_node *jmp = new_r_Jmp(irg, start_block);
1748
1749                         set_Block_cfgpred(block, get_edge_src_pos(edge), jmp);
1750                         return;
1751                 }
1752         }
1753         panic("Initial exec has no follow block in %+F", irg);
1754 }
1755
1756 /**
1757  * Update the entity of Sels to the outer value parameters.
1758  */
1759 static void update_outer_frame_sels(ir_node *irn, void *env) {
1760         lower_frame_sels_env_t *ctx = env;
1761         ir_node                *ptr;
1762         ir_entity              *ent;
1763         int                    pos = 0;
1764
1765         if (! is_Sel(irn))
1766                 return;
1767         ptr = get_Sel_ptr(irn);
1768         if (! is_arg_Proj(ptr))
1769                 return;
1770         if (get_Proj_proj(ptr) != ctx->static_link_pos)
1771                 return;
1772         ent   = get_Sel_entity(irn);
1773
1774         if (get_entity_owner(ent) == ctx->value_tp) {
1775                 /* replace by its copy from the argument type */
1776                 pos = get_struct_member_index(ctx->value_tp, ent);
1777                 ent = get_argument_entity(ent, ctx);
1778                 set_Sel_entity(irn, ent);
1779
1780                 /* check, if we have not seen this entity before */
1781                 if (get_entity_link(ent) == NULL) {
1782                         ent_pos_pair pair;
1783
1784                         pair.ent  = ent;
1785                         pair.pos  = pos;
1786                         pair.next = NULL;
1787                         ARR_APP1(ent_pos_pair, ctx->value_param_list, pair);
1788                         /* just a mark */
1789                         set_entity_link(ent, ctx->value_param_list);
1790                 }
1791         }
1792 }
1793
1794 /**
1795  * Fix access to outer local variables.
1796  */
1797 static void fix_outer_variable_access(be_abi_irg_t *env,
1798                                       lower_frame_sels_env_t *ctx)
1799 {
1800         int      i;
1801         ir_graph *irg;
1802         (void) env;
1803
1804         for (i = get_class_n_members(ctx->frame_tp) - 1; i >= 0; --i) {
1805                 ir_entity *ent = get_class_member(ctx->frame_tp, i);
1806
1807                 if (! is_method_entity(ent))
1808                         continue;
1809                 if (get_entity_peculiarity(ent) == peculiarity_description)
1810                         continue;
1811
1812                 /*
1813                  * FIXME: find the number of the static link parameter
1814                  * for now we assume 0 here
1815                  */
1816                 ctx->static_link_pos = 0;
1817
1818                 irg = get_entity_irg(ent);
1819                 irg_walk_graph(irg, NULL, update_outer_frame_sels, ctx);
1820         }
1821 }
1822
1823 /**
1824  * Modify the irg itself and the frame type.
1825  */
1826 static void modify_irg(be_abi_irg_t *env)
1827 {
1828         be_abi_call_t *call       = env->call;
1829         const arch_env_t *arch_env= env->birg->main_env->arch_env;
1830         const arch_register_t *sp = arch_env->sp;
1831         ir_graph *irg             = env->birg->irg;
1832         ir_node *start_bl;
1833         ir_node *end;
1834         ir_node *old_mem;
1835         ir_node *new_mem_proj;
1836         ir_node *mem;
1837         ir_type *method_type      = get_entity_type(get_irg_entity(irg));
1838
1839         int n_params;
1840         int i, n;
1841         unsigned j;
1842
1843         reg_node_map_t *rm;
1844         const arch_register_t *fp_reg;
1845         ir_node *frame_pointer;
1846         ir_node *reg_params_bl;
1847         ir_node **args;
1848         ir_node *arg_tuple;
1849         const ir_edge_t *edge;
1850         ir_type *arg_type, *bet_type, *tp;
1851         lower_frame_sels_env_t ctx;
1852         ir_entity **param_map;
1853
1854         DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1855
1856         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1857
1858         /* Must fetch memory here, otherwise the start Barrier gets the wrong
1859          * memory, which leads to loops in the DAG. */
1860         old_mem = get_irg_initial_mem(irg);
1861
1862         irp_reserve_resources(irp, IR_RESOURCE_ENTITY_LINK);
1863
1864         /* set the links of all frame entities to NULL, we use it
1865            to detect if an entity is already linked in the value_param_list */
1866         tp = get_method_value_param_type(method_type);
1867         ctx.value_tp = tp;
1868         if (tp != NULL) {
1869                 /* clear the links of the clone type, let the
1870                    original entities point to its clones */
1871                 for (i = get_struct_n_members(tp) - 1; i >= 0; --i) {
1872                         ir_entity *mem  = get_struct_member(tp, i);
1873                         set_entity_link(mem, NULL);
1874                 }
1875         }
1876
1877         arg_type = compute_arg_type(env, call, method_type, tp, &param_map);
1878
1879         /* Convert the Sel nodes in the irg to frame addr nodes: */
1880         ctx.value_param_list = NEW_ARR_F(ent_pos_pair, 0);
1881         ctx.frame            = get_irg_frame(irg);
1882         ctx.sp_class         = env->arch_env->sp->reg_class;
1883         ctx.link_class       = env->arch_env->link_class;
1884         ctx.frame_tp         = get_irg_frame_type(irg);
1885
1886         /* we will possible add new entities to the frame: set the layout to undefined */
1887         assert(get_type_state(ctx.frame_tp) == layout_fixed);
1888         set_type_state(ctx.frame_tp, layout_undefined);
1889
1890         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1891
1892         /* fix the frame type layout again */
1893         set_type_state(ctx.frame_tp, layout_fixed);
1894
1895         env->regs  = pmap_create();
1896
1897         n_params = get_method_n_params(method_type);
1898         args     = obstack_alloc(&env->obst, n_params * sizeof(args[0]));
1899         memset(args, 0, n_params * sizeof(args[0]));
1900
1901         /*
1902          * for inner function we must now fix access to outer frame entities.
1903          */
1904         fix_outer_variable_access(env, &ctx);
1905
1906         /* Check if a value parameter is transmitted as a register.
1907          * This might happen if the address of an parameter is taken which is
1908          * transmitted in registers.
1909          *
1910          * Note that on some architectures this case must be handled specially
1911          * because the place of the backing store is determined by their ABI.
1912          *
1913          * In the default case we move the entity to the frame type and create
1914          * a backing store into the first block.
1915          */
1916         fix_address_of_parameter_access(env, ctx.value_param_list);
1917
1918         DEL_ARR_F(ctx.value_param_list);
1919         irp_free_resources(irp, IR_RESOURCE_ENTITY_LINK);
1920
1921         /* Fill the argument vector */
1922         arg_tuple = get_irg_args(irg);
1923         foreach_out_edge(arg_tuple, edge) {
1924                 ir_node *irn = get_edge_src_irn(edge);
1925                 if (! is_Anchor(irn)) {
1926                         int nr       = get_Proj_proj(irn);
1927                         args[nr]     = irn;
1928                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1929                 }
1930         }
1931
1932         bet_type = call->cb->get_between_type(env->cb);
1933         stack_frame_init(&env->frame, arg_type, bet_type, get_irg_frame_type(irg), arch_env->stack_dir, param_map);
1934
1935         /* Count the register params and add them to the number of Projs for the RegParams node */
1936         for (i = 0; i < n_params; ++i) {
1937                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1938                 if (arg->in_reg && args[i]) {
1939                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1940                         assert(i == get_Proj_proj(args[i]));
1941
1942                         /* For now, associate the register with the old Proj from Start representing that argument. */
1943                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1944                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1945                 }
1946         }
1947
1948         /* Collect all callee-save registers */
1949         for (i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
1950                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
1951                 for (j = 0; j < cls->n_regs; ++j) {
1952                         const arch_register_t *reg = &cls->regs[j];
1953                         if (arch_register_type_is(reg, callee_save) ||
1954                                         arch_register_type_is(reg, state)) {
1955                                 pmap_insert(env->regs, (void *) reg, NULL);
1956                         }
1957                 }
1958         }
1959
1960         pmap_insert(env->regs, (void *) sp, NULL);
1961         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1962         reg_params_bl   = get_irg_start_block(irg);
1963         env->reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(env->regs));
1964         add_irn_dep(env->reg_params, get_irg_start(irg));
1965
1966         /*
1967          * make proj nodes for the callee save registers.
1968          * memorize them, since Return nodes get those as inputs.
1969          *
1970          * Note, that if a register corresponds to an argument, the regs map contains
1971          * the old Proj from start for that argument.
1972          */
1973
1974         rm = reg_map_to_arr(&env->obst, env->regs);
1975         for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1976                 arch_register_t          *reg      = (void *) rm[i].reg;
1977                 ir_mode                  *mode     = reg->reg_class->mode;
1978                 long                      nr       = i;
1979                 arch_register_req_type_t  add_type = 0;
1980                 ir_node                  *proj;
1981
1982                 if (reg == sp)
1983                         add_type |= arch_register_req_type_produces_sp | arch_register_req_type_ignore;
1984
1985                 assert(nr >= 0);
1986                 proj = new_r_Proj(irg, reg_params_bl, env->reg_params, mode, nr);
1987                 pmap_insert(env->regs, (void *) reg, proj);
1988                 be_set_constr_single_reg_out(env->reg_params, nr, reg, add_type);
1989                 arch_set_irn_register(proj, reg);
1990
1991                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1992         }
1993         obstack_free(&env->obst, rm);
1994
1995         /* create a new initial memory proj */
1996         assert(is_Proj(old_mem));
1997         new_mem_proj = new_r_Proj(irg, get_nodes_block(old_mem),
1998                                   new_r_Unknown(irg, mode_T), mode_M,
1999                                   get_Proj_proj(old_mem));
2000         mem = new_mem_proj;
2001
2002         /* Generate the Prologue */
2003         fp_reg = call->cb->prologue(env->cb, &mem, env->regs, &env->frame.initial_bias);
2004
2005         /* do the stack allocation BEFORE the barrier, or spill code
2006            might be added before it */
2007         env->init_sp = be_abi_reg_map_get(env->regs, sp);
2008         start_bl     = get_irg_start_block(irg);
2009         env->init_sp = be_new_IncSP(sp, irg, start_bl, env->init_sp, BE_STACK_FRAME_SIZE_EXPAND, 0);
2010         be_abi_reg_map_set(env->regs, sp, env->init_sp);
2011
2012         create_barrier(env, start_bl, &mem, env->regs, 0);
2013
2014         env->init_sp = be_abi_reg_map_get(env->regs, sp);
2015         arch_set_irn_register(env->init_sp, sp);
2016
2017         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
2018         set_irg_frame(irg, frame_pointer);
2019         pset_insert_ptr(env->ignore_regs, fp_reg);
2020
2021         /* rewire old mem users to new mem */
2022         set_Proj_pred(new_mem_proj, get_Proj_pred(old_mem));
2023         exchange(old_mem, mem);
2024
2025         set_irg_initial_mem(irg, mem);
2026
2027         /* Now, introduce stack param nodes for all parameters passed on the stack */
2028         for (i = 0; i < n_params; ++i) {
2029                 ir_node *arg_proj = args[i];
2030                 ir_node *repl     = NULL;
2031
2032                 if (arg_proj != NULL) {
2033                         be_abi_call_arg_t *arg;
2034                         ir_type *param_type;
2035                         int     nr = get_Proj_proj(arg_proj);
2036                         ir_mode *mode;
2037
2038                         nr         = MIN(nr, n_params);
2039                         arg        = get_call_arg(call, 0, nr);
2040                         param_type = get_method_param_type(method_type, nr);
2041
2042                         if (arg->in_reg) {
2043                                 repl = pmap_get(env->regs, (void *) arg->reg);
2044                         } else if (arg->on_stack) {
2045                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, irg, reg_params_bl, frame_pointer, arg->stack_ent);
2046
2047                                 /* For atomic parameters which are actually used, we create a Load node. */
2048                                 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
2049                                         ir_mode *mode      = get_type_mode(param_type);
2050                                         ir_mode *load_mode = arg->load_mode;
2051
2052                                         ir_node *load = new_r_Load(irg, reg_params_bl, new_NoMem(), addr, load_mode, cons_floats);
2053                                         repl = new_r_Proj(irg, reg_params_bl, load, load_mode, pn_Load_res);
2054
2055                                         if (mode != load_mode) {
2056                                                 repl = new_r_Conv(irg, reg_params_bl, repl, mode);
2057                                         }
2058                                 } else {
2059                                         /* The stack parameter is not primitive (it is a struct or array),
2060                                          * we thus will create a node representing the parameter's address
2061                                          * on the stack. */
2062                                         repl = addr;
2063                                 }
2064                         }
2065
2066                         assert(repl != NULL);
2067
2068                         /* Beware: the mode of the register parameters is always the mode of the register class
2069                            which may be wrong. Add Conv's then. */
2070                         mode = get_irn_mode(args[i]);
2071                         if (mode != get_irn_mode(repl)) {
2072                                 repl = new_r_Conv(irg, get_irn_n(repl, -1), repl, mode);
2073                         }
2074                         exchange(args[i], repl);
2075                 }
2076         }
2077
2078         /* the arg proj is not needed anymore now and should be only used by the anchor */
2079         assert(get_irn_n_edges(arg_tuple) == 1);
2080         kill_node(arg_tuple);
2081         set_irg_args(irg, new_r_Bad(irg));
2082
2083         /* All Return nodes hang on the End node, so look for them there. */
2084         end = get_irg_end_block(irg);
2085         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
2086                 ir_node *irn = get_Block_cfgpred(end, i);
2087
2088                 if (is_Return(irn)) {
2089                         ir_node *blk = get_nodes_block(irn);
2090                         ir_node *mem = get_Return_mem(irn);
2091                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
2092                         exchange(irn, ret);
2093                 }
2094         }
2095         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
2096            the code is dead and will never be executed. */
2097
2098         obstack_free(&env->obst, args);
2099
2100         /* handle start block here (place a jump in the block) */
2101         fix_start_block(irg);
2102 }
2103
2104 /** Fix the state inputs of calls that still hang on unknowns */
2105 static
2106 void fix_call_state_inputs(be_abi_irg_t *env)
2107 {
2108         const arch_env_t *arch_env = env->arch_env;
2109         int i, n, n_states;
2110         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
2111
2112         /* Collect caller save registers */
2113         n = arch_env_get_n_reg_class(arch_env);
2114         for (i = 0; i < n; ++i) {
2115                 unsigned j;
2116                 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
2117                 for (j = 0; j < cls->n_regs; ++j) {
2118                         const arch_register_t *reg = arch_register_for_index(cls, j);
2119                         if (arch_register_type_is(reg, state)) {
2120                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
2121                         }
2122                 }
2123         }
2124
2125         n = ARR_LEN(env->calls);
2126         n_states = ARR_LEN(stateregs);
2127         for (i = 0; i < n; ++i) {
2128                 int s, arity;
2129                 ir_node *call = env->calls[i];
2130
2131                 arity = get_irn_arity(call);
2132
2133                 /* the state reg inputs are the last n inputs of the calls */
2134                 for (s = 0; s < n_states; ++s) {
2135                         int inp = arity - n_states + s;
2136                         const arch_register_t *reg = stateregs[s];
2137                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
2138
2139                         set_irn_n(call, inp, regnode);
2140                 }
2141         }
2142
2143         DEL_ARR_F(stateregs);
2144 }
2145
2146 /**
2147  * Create a trampoline entity for the given method.
2148  */
2149 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
2150 {
2151         ir_type   *type   = get_entity_type(method);
2152         ident     *old_id = get_entity_ld_ident(method);
2153         ident     *id     = id_mangle3("L", old_id, "$stub");
2154         ir_type   *parent = be->pic_trampolines_type;
2155         ir_entity *ent    = new_entity(parent, old_id, type);
2156         set_entity_ld_ident(ent, id);
2157         set_entity_visibility(ent, visibility_local);
2158         set_entity_variability(ent, variability_uninitialized);
2159
2160         return ent;
2161 }
2162
2163 /**
2164  * Returns the trampoline entity for the given method.
2165  */
2166 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
2167 {
2168         ir_entity *result = pmap_get(env->ent_trampoline_map, method);
2169         if (result == NULL) {
2170                 result = create_trampoline(env, method);
2171                 pmap_insert(env->ent_trampoline_map, method, result);
2172         }
2173
2174         return result;
2175 }
2176
2177 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
2178 {
2179         ident     *old_id = get_entity_ld_ident(entity);
2180         ident     *id     = id_mangle3("L", old_id, "$non_lazy_ptr");
2181         ir_type   *e_type = get_entity_type(entity);
2182         ir_type   *type   = new_type_pointer(id, e_type, mode_P_data);
2183         ir_type   *parent = be->pic_symbols_type;
2184         ir_entity *ent    = new_entity(parent, old_id, type);
2185         set_entity_ld_ident(ent, id);
2186         set_entity_visibility(ent, visibility_local);
2187         set_entity_variability(ent, variability_uninitialized);
2188
2189         return ent;
2190 }
2191
2192 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
2193 {
2194         ir_entity *result = pmap_get(env->ent_pic_symbol_map, entity);
2195         if (result == NULL) {
2196                 result = create_pic_symbol(env, entity);
2197                 pmap_insert(env->ent_pic_symbol_map, entity, result);
2198         }
2199
2200         return result;
2201 }
2202
2203
2204
2205 /**
2206  * Returns non-zero if a given entity can be accessed using a relative address.
2207  */
2208 static int can_address_relative(ir_entity *entity)
2209 {
2210         return get_entity_visibility(entity) != visibility_external_allocated;
2211 }
2212
2213 /** patches SymConsts to work in position independent code */
2214 static void fix_pic_symconsts(ir_node *node, void *data)
2215 {
2216         ir_graph     *irg;
2217         ir_node      *pic_base;
2218         ir_node      *add;
2219         ir_node      *block;
2220         ir_node      *unknown;
2221         ir_mode      *mode;
2222         ir_node      *load;
2223         ir_node      *load_res;
2224         be_abi_irg_t *env = data;
2225         int           arity, i;
2226         be_main_env_t *be = env->birg->main_env;
2227
2228         arity = get_irn_arity(node);
2229         for (i = 0; i < arity; ++i) {
2230                 dbg_info  *dbgi;
2231                 ir_node   *pred = get_irn_n(node, i);
2232                 ir_entity *entity;
2233                 ir_entity *pic_symbol;
2234                 ir_node   *pic_symconst;
2235
2236                 if (!is_SymConst(pred))
2237                         continue;
2238
2239                 entity = get_SymConst_entity(pred);
2240                 block  = get_nodes_block(pred);
2241                 irg    = get_irn_irg(pred);
2242
2243                 /* calls can jump to relative addresses, so we can directly jump to
2244                    the (relatively) known call address or the trampoline */
2245                 if (i == 1 && is_Call(node)) {
2246                         ir_entity *trampoline;
2247                         ir_node   *trampoline_const;
2248
2249                         if (can_address_relative(entity))
2250                                 continue;
2251
2252                         dbgi             = get_irn_dbg_info(pred);
2253                         trampoline       = get_trampoline(be, entity);
2254                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2255                                                                     trampoline, NULL);
2256                         set_irn_n(node, i, trampoline_const);
2257                         continue;
2258                 }
2259
2260                 /* everything else is accessed relative to EIP */
2261                 mode     = get_irn_mode(pred);
2262                 unknown  = new_r_Unknown(irg, mode);
2263                 pic_base = arch_code_generator_get_pic_base(env->birg->cg);
2264
2265                 /* all ok now for locally constructed stuff */
2266                 if (can_address_relative(entity)) {
2267                         ir_node *add = new_r_Add(irg, block, pic_base, pred, mode);
2268
2269                         /* make sure the walker doesn't visit this add again */
2270                         mark_irn_visited(add);
2271                         set_irn_n(node, i, add);
2272                         continue;
2273                 }
2274
2275                 /* get entry from pic symbol segment */
2276                 dbgi         = get_irn_dbg_info(pred);
2277                 pic_symbol   = get_pic_symbol(be, entity);
2278                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2279                                                         pic_symbol, NULL);
2280                 add = new_r_Add(irg, block, pic_base, pic_symconst, mode);
2281                 mark_irn_visited(add);
2282
2283                 /* we need an extra indirection for global data outside our current
2284                    module. The loads are always safe and can therefore float
2285                    and need no memory input */
2286                 load     = new_r_Load(irg, block, new_NoMem(), add, mode, cons_floats);
2287                 load_res = new_r_Proj(irg, block, load, mode, pn_Load_res);
2288
2289                 set_irn_n(node, i, load_res);
2290         }
2291 }
2292
2293 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
2294 {
2295         be_abi_irg_t *env  = XMALLOC(be_abi_irg_t);
2296         ir_node *old_frame = get_irg_frame(birg->irg);
2297         ir_graph *irg      = birg->irg;
2298
2299         pmap_entry *ent;
2300         ir_node *dummy;
2301         optimization_state_t state;
2302         unsigned *limited_bitset;
2303
2304         be_omit_fp      = birg->main_env->options->omit_fp;
2305         be_omit_leaf_fp = birg->main_env->options->omit_leaf_fp;
2306
2307         obstack_init(&env->obst);
2308
2309         env->arch_env    = birg->main_env->arch_env;
2310         env->method_type = get_entity_type(get_irg_entity(irg));
2311         env->call        = be_abi_call_new(env->arch_env->sp->reg_class);
2312         arch_env_get_call_abi(env->arch_env, env->method_type, env->call);
2313
2314         env->ignore_regs  = pset_new_ptr_default();
2315         env->keep_map     = pmap_create();
2316         env->dce_survivor = new_survive_dce();
2317         env->birg         = birg;
2318
2319         env->sp_req.type    = arch_register_req_type_limited;
2320         env->sp_req.cls     = arch_register_get_class(env->arch_env->sp);
2321         limited_bitset      = rbitset_obstack_alloc(&env->obst, env->sp_req.cls->n_regs);
2322         rbitset_set(limited_bitset, arch_register_get_index(env->arch_env->sp));
2323         env->sp_req.limited = limited_bitset;
2324         if (env->arch_env->sp->type & arch_register_type_ignore) {
2325                 env->sp_req.type |= arch_register_req_type_ignore;
2326         }
2327
2328         env->sp_cls_req.type  = arch_register_req_type_normal;
2329         env->sp_cls_req.cls   = arch_register_get_class(env->arch_env->sp);
2330
2331         /* Beware: later we replace this node by the real one, ensure it is not CSE'd
2332            to another Unknown or the stack pointer gets used */
2333         save_optimization_state(&state);
2334         set_optimize(0);
2335         env->init_sp = dummy  = new_r_Unknown(irg, env->arch_env->sp->reg_class->mode);
2336         restore_optimization_state(&state);
2337
2338         FIRM_DBG_REGISTER(env->dbg, "firm.be.abi");
2339
2340         env->calls = NEW_ARR_F(ir_node*, 0);
2341
2342         if (birg->main_env->options->pic) {
2343                 irg_walk_graph(irg, fix_pic_symconsts, NULL, env);
2344         }
2345
2346         /* Lower all call nodes in the IRG. */
2347         process_calls(env);
2348
2349         /*
2350                 Beware: init backend abi call object after processing calls,
2351                 otherwise some information might be not yet available.
2352         */
2353         env->cb = env->call->cb->init(env->call, birg->main_env->arch_env, irg);
2354
2355         /* Process the IRG */
2356         modify_irg(env);
2357
2358         /* fix call inputs for state registers */
2359         fix_call_state_inputs(env);
2360
2361         /* We don't need the keep map anymore. */
2362         pmap_destroy(env->keep_map);
2363         env->keep_map = NULL;
2364
2365         /* calls array is not needed anymore */
2366         DEL_ARR_F(env->calls);
2367         env->calls = NULL;
2368
2369         /* reroute the stack origin of the calls to the true stack origin. */
2370         exchange(dummy, env->init_sp);
2371         exchange(old_frame, get_irg_frame(irg));
2372
2373         /* Make some important node pointers survive the dead node elimination. */
2374         survive_dce_register_irn(env->dce_survivor, &env->init_sp);
2375         foreach_pmap(env->regs, ent) {
2376                 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
2377         }
2378
2379         env->call->cb->done(env->cb);
2380         env->cb = NULL;
2381         return env;
2382 }
2383
2384 void be_abi_free(be_abi_irg_t *env)
2385 {
2386         be_abi_call_free(env->call);
2387         free_survive_dce(env->dce_survivor);
2388         del_pset(env->ignore_regs);
2389         pmap_destroy(env->regs);
2390         obstack_free(&env->obst, NULL);
2391         free(env);
2392 }
2393
2394 void be_abi_put_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, bitset_t *bs)
2395 {
2396         arch_register_t *reg;
2397
2398         for (reg = pset_first(abi->ignore_regs); reg; reg = pset_next(abi->ignore_regs))
2399                 if (reg->reg_class == cls)
2400                         bitset_set(bs, reg->index);
2401 }
2402
2403 void be_abi_set_non_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, unsigned *raw_bitset)
2404 {
2405         unsigned         i;
2406         arch_register_t *reg;
2407
2408         for (i = 0; i < cls->n_regs; ++i) {
2409                 if (arch_register_type_is(&cls->regs[i], ignore))
2410                         continue;
2411
2412                 rbitset_set(raw_bitset, i);
2413         }
2414
2415         for (reg = pset_first(abi->ignore_regs); reg != NULL;
2416              reg = pset_next(abi->ignore_regs)) {
2417                 if (reg->reg_class != cls)
2418                         continue;
2419
2420                 rbitset_clear(raw_bitset, reg->index);
2421         }
2422 }
2423
2424 /* Returns the stack layout from a abi environment. */
2425 const be_stack_layout_t *be_abi_get_stack_layout(const be_abi_irg_t *abi)
2426 {
2427         return &abi->frame;
2428 }
2429
2430 /*
2431
2432   _____ _        ____  _             _
2433  |  ___(_)_  __ / ___|| |_ __ _  ___| | __
2434  | |_  | \ \/ / \___ \| __/ _` |/ __| |/ /
2435  |  _| | |>  <   ___) | || (_| | (__|   <
2436  |_|   |_/_/\_\ |____/ \__\__,_|\___|_|\_\
2437
2438 */
2439
2440 typedef ir_node **node_array;
2441
2442 typedef struct fix_stack_walker_env_t {
2443         node_array sp_nodes;
2444 } fix_stack_walker_env_t;
2445
2446 /**
2447  * Walker. Collect all stack modifying nodes.
2448  */
2449 static void collect_stack_nodes_walker(ir_node *node, void *data)
2450 {
2451         fix_stack_walker_env_t    *env = data;
2452         const arch_register_req_t *req;
2453
2454         if (get_irn_mode(node) == mode_T)
2455                 return;
2456
2457         req = arch_get_register_req_out(node);
2458         if (! (req->type & arch_register_req_type_produces_sp))
2459                 return;
2460
2461         ARR_APP1(ir_node*, env->sp_nodes, node);
2462 }
2463
2464 void be_abi_fix_stack_nodes(be_abi_irg_t *env)
2465 {
2466         be_ssa_construction_env_t senv;
2467         int i, len;
2468         ir_node **phis;
2469         be_irg_t *birg = env->birg;
2470         be_lv_t *lv = be_get_birg_liveness(birg);
2471         fix_stack_walker_env_t walker_env;
2472
2473         walker_env.sp_nodes = NEW_ARR_F(ir_node*, 0);
2474
2475         irg_walk_graph(birg->irg, collect_stack_nodes_walker, NULL, &walker_env);
2476
2477         /* nothing to be done if we didn't find any node, in fact we mustn't
2478          * continue, as for endless loops incsp might have had no users and is bad
2479          * now.
2480          */
2481         len = ARR_LEN(walker_env.sp_nodes);
2482         if (len == 0) {
2483                 DEL_ARR_F(walker_env.sp_nodes);
2484                 return;
2485         }
2486
2487         be_ssa_construction_init(&senv, birg);
2488         be_ssa_construction_add_copies(&senv, walker_env.sp_nodes,
2489                                    ARR_LEN(walker_env.sp_nodes));
2490         be_ssa_construction_fix_users_array(&senv, walker_env.sp_nodes,
2491                                             ARR_LEN(walker_env.sp_nodes));
2492
2493         if (lv != NULL) {
2494                 len = ARR_LEN(walker_env.sp_nodes);
2495                 for (i = 0; i < len; ++i) {
2496                         be_liveness_update(lv, walker_env.sp_nodes[i]);
2497                 }
2498                 be_ssa_construction_update_liveness_phis(&senv, lv);
2499         }
2500
2501         phis = be_ssa_construction_get_new_phis(&senv);
2502
2503         /* set register requirements for stack phis */
2504         len = ARR_LEN(phis);
2505         for (i = 0; i < len; ++i) {
2506                 ir_node *phi = phis[i];
2507                 be_set_phi_reg_req(phi, &env->sp_req, arch_register_req_type_produces_sp);
2508                 arch_set_irn_register(phi, env->arch_env->sp);
2509         }
2510         be_ssa_construction_destroy(&senv);
2511
2512         DEL_ARR_F(walker_env.sp_nodes);
2513 }
2514
2515 /**
2516  * Fix all stack accessing operations in the block bl.
2517  *
2518  * @param env        the abi environment
2519  * @param bl         the block to process
2520  * @param real_bias  the bias value
2521  *
2522  * @return the bias at the end of this block
2523  */
2524 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int real_bias)
2525 {
2526         int               omit_fp  = env->call->flags.bits.try_omit_fp;
2527         ir_node          *irn;
2528         int               wanted_bias = real_bias;
2529
2530         sched_foreach(bl, irn) {
2531                 int ofs;
2532
2533                 /*
2534                    Check, if the node relates to an entity on the stack frame.
2535                    If so, set the true offset (including the bias) for that
2536                    node.
2537                  */
2538                 ir_entity *ent = arch_get_frame_entity(irn);
2539                 if (ent != NULL) {
2540                         int bias   = omit_fp ? real_bias : 0;
2541                         int offset = get_stack_entity_offset(&env->frame, ent, bias);
2542                         arch_set_frame_offset(irn, offset);
2543                         DBG((env->dbg, LEVEL_2, "%F has offset %d (including bias %d)\n",
2544                              ent, offset, bias));
2545                 }
2546
2547                 /*
2548                  * If the node modifies the stack pointer by a constant offset,
2549                  * record that in the bias.
2550                  */
2551                 ofs = arch_get_sp_bias(irn);
2552
2553                 if (be_is_IncSP(irn)) {
2554                         /* fill in real stack frame size */
2555                         if (ofs == BE_STACK_FRAME_SIZE_EXPAND) {
2556                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2557                                 ofs = (int) get_type_size_bytes(frame_type);
2558                                 be_set_IncSP_offset(irn, ofs);
2559                         } else if (ofs == BE_STACK_FRAME_SIZE_SHRINK) {
2560                                 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2561                                 ofs = - (int)get_type_size_bytes(frame_type);
2562                                 be_set_IncSP_offset(irn, ofs);
2563                         } else {
2564                                 if (be_get_IncSP_align(irn)) {
2565                                         /* patch IncSP to produce an aligned stack pointer */
2566                                         ir_type *between_type = env->frame.between_type;
2567                                         int      between_size = get_type_size_bytes(between_type);
2568                                         int      alignment    = 1 << env->arch_env->stack_alignment;
2569                                         int      delta        = (real_bias + ofs + between_size) & (alignment - 1);
2570                                         assert(ofs >= 0);
2571                                         if (delta > 0) {
2572                                                 be_set_IncSP_offset(irn, ofs + alignment - delta);
2573                                                 real_bias += alignment - delta;
2574                                         }
2575                                 } else {
2576                                         /* adjust so real_bias corresponds with wanted_bias */
2577                                         int delta = wanted_bias - real_bias;
2578                                         assert(delta <= 0);
2579                                         if (delta != 0) {
2580                                                 be_set_IncSP_offset(irn, ofs + delta);
2581                                                 real_bias += delta;
2582                                         }
2583                                 }
2584                         }
2585                 }
2586
2587                 real_bias   += ofs;
2588                 wanted_bias += ofs;
2589         }
2590
2591         assert(real_bias == wanted_bias);
2592         return real_bias;
2593 }
2594
2595 /**
2596  * A helper struct for the bias walker.
2597  */
2598 struct bias_walk {
2599         be_abi_irg_t *env;     /**< The ABI irg environment. */
2600         int           start_block_bias;  /**< The bias at the end of the start block. */
2601         int           between_size;
2602         ir_node      *start_block;  /**< The start block of the current graph. */
2603 };
2604
2605 /**
2606  * Block-Walker: fix all stack offsets for all blocks
2607  * except the start block
2608  */
2609 static void stack_bias_walker(ir_node *bl, void *data)
2610 {
2611         struct bias_walk *bw = data;
2612         if (bl != bw->start_block) {
2613                 process_stack_bias(bw->env, bl, bw->start_block_bias);
2614         }
2615 }
2616
2617 /**
2618  * Walker: finally lower all Sels of outer frame or parameter
2619  * entities.
2620  */
2621 static void lower_outer_frame_sels(ir_node *sel, void *ctx) {
2622         be_abi_irg_t *env = ctx;
2623         ir_node      *ptr;
2624         ir_entity    *ent;
2625         ir_type      *owner;
2626
2627         if (! is_Sel(sel))
2628                 return;
2629
2630         ent   = get_Sel_entity(sel);
2631         owner = get_entity_owner(ent);
2632         ptr   = get_Sel_ptr(sel);
2633
2634         if (owner == env->frame.frame_type || owner == env->frame.arg_type) {
2635                 /* found access to outer frame or arguments */
2636                 int offset = get_stack_entity_offset(&env->frame, ent, 0);
2637
2638                 if (offset != 0) {
2639                         ir_node  *bl   = get_nodes_block(sel);
2640                         dbg_info *dbgi = get_irn_dbg_info(sel);
2641                         ir_mode  *mode = get_irn_mode(sel);
2642                         ir_mode  *mode_UInt = get_reference_mode_unsigned_eq(mode);
2643                         ir_node  *cnst = new_r_Const_long(current_ir_graph, mode_UInt, offset);
2644
2645                         ptr = new_rd_Add(dbgi, current_ir_graph, bl, ptr, cnst, mode);
2646                 }
2647                 exchange(sel, ptr);
2648         }
2649 }
2650
2651 void be_abi_fix_stack_bias(be_abi_irg_t *env)
2652 {
2653         ir_graph          *irg = env->birg->irg;
2654         ir_type           *frame_tp;
2655         int               i;
2656         struct bias_walk  bw;
2657
2658         stack_frame_compute_initial_offset(&env->frame);
2659         // stack_layout_dump(stdout, frame);
2660
2661         /* Determine the stack bias at the end of the start block. */
2662         bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), env->frame.initial_bias);
2663         bw.between_size     = get_type_size_bytes(env->frame.between_type);
2664
2665         /* fix the bias is all other blocks */
2666         bw.env = env;
2667         bw.start_block = get_irg_start_block(irg);
2668         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
2669
2670         /* fix now inner functions: these still have Sel node to outer
2671            frame and parameter entities */
2672         frame_tp = get_irg_frame_type(irg);
2673         for (i = get_class_n_members(frame_tp) - 1; i >= 0; --i) {
2674                 ir_entity *ent = get_class_member(frame_tp, i);
2675
2676                 if (is_method_entity(ent) && get_entity_peculiarity(ent) != peculiarity_description) {
2677                         ir_graph *irg = get_entity_irg(ent);
2678
2679                         irg_walk_graph(irg, NULL, lower_outer_frame_sels, env);
2680                 }
2681         }
2682 }
2683
2684 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2685 {
2686         assert(arch_register_type_is(reg, callee_save));
2687         assert(pmap_contains(abi->regs, (void *) reg));
2688         return pmap_get(abi->regs, (void *) reg);
2689 }
2690
2691 ir_node *be_abi_get_ignore_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2692 {
2693         assert(arch_register_type_is(reg, ignore));
2694         assert(pmap_contains(abi->regs, (void *) reg));
2695         return pmap_get(abi->regs, (void *) reg);
2696 }
2697
2698 /**
2699  * Returns non-zero if the ABI has omitted the frame pointer in
2700  * the current graph.
2701  */
2702 int be_abi_omit_fp(const be_abi_irg_t *abi)
2703 {
2704         return abi->call->flags.bits.try_omit_fp;
2705 }