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

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