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