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