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

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