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

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