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

   1 /**
   2  * ABI lowering.
   3  *
   4  * @author Sebastian Hack
   5  * @date 7.3.2005
   6  */
   7
   8 #ifdef HAVE_CONFIG_H
   9 # include "config.h"
  10 #endif
  11 #include "obst.h"
  12
  13 #include "type.h"
  14 #include "irgopt.h"
  15
  16 #include "irgraph_t.h"
  17 #include "irnode_t.h"
  18 #include "ircons_t.h"
  19 #include "iredges_t.h"
  20 #include "irgmod.h"
  21 #include "irgwalk.h"
  22 #include "irprintf_t.h"
  23 #include "irgopt.h"
  24
  25 #include "be.h"
  26 #include "beabi.h"
  27 #include "bearch.h"
  28 #include "benode_t.h"
  29 #include "belive_t.h"
  30 #include "besched_t.h"
  31
  32 #define MAX(x, y) ((x) > (y) ? (x) : (y))
  33 #define MIN(x, y) ((x) < (y) ? (x) : (y))
  34
  35 typedef struct _be_abi_call_arg_t {
  36         unsigned is_res   : 1;
  37         unsigned in_reg   : 1;
  38         unsigned on_stack : 1;
  39
  40         int pos;
  41         const arch_register_t *reg;
  42         entity *stack_ent;
  43 } be_abi_call_arg_t;
  44
  45 struct _be_abi_call_t {
  46         be_abi_call_flags_t flags;
  47         const be_abi_callbacks_t *cb;
  48         type *between_type;
  49         set *params;
  50 };
  51
  52 #define N_FRAME_TYPES 3
  53
  54 typedef struct _be_stack_frame_t {
  55         type *arg_type;
  56         type *between_type;
  57         type *frame_type;
  58
  59         type *order[N_FRAME_TYPES];        /**< arg, between and frame types ordered. */
  60
  61         int initial_offset;
  62         int stack_dir;
  63 } be_stack_frame_t;
  64
  65 struct _be_stack_slot_t {
  66         struct _be_stack_frame_t *frame;
  67         entity *ent;
  68 };
  69
  70 struct _be_abi_irg_t {
  71         struct obstack       obst;
  72         firm_dbg_module_t    *dbg;          /**< The debugging module. */
  73         be_stack_frame_t     *frame;        /**< The stack frame model. */
  74         const be_irg_t       *birg;         /**< The back end IRG. */
  75         const arch_isa_t     *isa;          /**< The isa. */
  76         survive_dce_t        *dce_survivor;
  77
  78         be_abi_call_t        *call;         /**< The ABI call information. */
  79         type                 *method_type;  /**< The type of the method of the IRG. */
  80
  81         ir_node              *init_sp;      /**< The node representing the stack pointer
  82                                                                              at the start of the function. */
  83
  84         ir_node              *reg_params;   /**< The reg params node. */
  85         pmap                 *regs;         /**< A map of all callee-save and ignore regs to
  86                                                                                         their Projs to the RegParams node. */
  87
  88         pset                 *stack_phis;   /**< The set of all Phi nodes inserted due to
  89                                                                                         stack pointer modifying nodes. */
  90
  91         int                  start_block_bias;  /**< The stack bias at the end of the start block. */
  92
  93         void                 *cb;           /**< ABI Callback self pointer. */
  94
  95         arch_irn_handler_t irn_handler;
  96         arch_irn_ops_t     irn_ops;
  97 };
  98
  99 #define abi_offset_of(type,member) ((char *) &(((type *) 0)->member) - (char *) 0)
 100 #define abi_get_relative(ptr, member) ((void *) ((char *) (ptr) - abi_offset_of(be_abi_irg_t, member)))
 101 #define get_abi_from_handler(ptr) abi_get_relative(ptr, irn_handler)
 102 #define get_abi_from_ops(ptr)     abi_get_relative(ptr, irn_ops)
 103
 104 /* Forward, since be need it in be_abi_introduce(). */
 105 static const arch_irn_ops_if_t abi_irn_ops;
 106 static const arch_irn_handler_t abi_irn_handler;
 107
 108 /*
 109      _    ____ ___    ____      _ _ _                _
 110     / \  | __ )_ _|  / ___|__ _| | | |__   __ _  ___| | _____
 111    / _ \ |  _ \| |  | |   / _` | | | '_ \ / _` |/ __| |/ / __|
 112   / ___ \| |_) | |  | |__| (_| | | | |_) | (_| | (__|   <\__ \
 113  /_/   \_\____/___|  \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
 114
 115   These callbacks are used by the backend to set the parameters
 116   for a specific call type.
 117 */
 118
 119 static int cmp_call_arg(const void *a, const void *b, size_t n)
 120 {
 121         const be_abi_call_arg_t *p = a, *q = b;
 122         return !(p->is_res == q->is_res && p->pos == q->pos);
 123 }
 124
 125 static be_abi_call_arg_t *get_or_set_call_arg(be_abi_call_t *call, int is_res, int pos, int do_insert)
 126 {
 127         be_abi_call_arg_t arg;
 128         unsigned hash;
 129
 130         memset(&arg, 0, sizeof(arg));
 131         arg.is_res = is_res;
 132         arg.pos    = pos;
 133
 134         hash = is_res * 100 + pos;
 135
 136         return do_insert
 137                 ? set_insert(call->params, &arg, sizeof(arg), hash)
 138                 : set_find(call->params, &arg, sizeof(arg), hash);
 139 }
 140
 141 static INLINE be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
 142 {
 143         return get_or_set_call_arg(call, is_res, pos, 0);
 144 }
 145
 146 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
 147 {
 148         call->flags        = flags;
 149         call->cb           = cb;
 150 }
 151
 152 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos)
 153 {
 154         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
 155         arg->on_stack = 1;
 156 }
 157
 158 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
 159 {
 160         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
 161         arg->in_reg = 1;
 162         arg->reg = reg;
 163 }
 164
 165 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
 166 {
 167         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 1, arg_pos, 1);
 168         arg->in_reg = 1;
 169         arg->reg = reg;
 170 }
 171
 172 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
 173 {
 174         return call->flags;
 175 }
 176
 177 be_abi_call_t *be_abi_call_new(void)
 178 {
 179         be_abi_call_t *call = malloc(sizeof(call[0]));
 180         call->flags.val  = 0;
 181         call->params     = new_set(cmp_call_arg, 16);
 182         call->cb         = NULL;
 183         return call;
 184 }
 185
 186 void be_abi_call_free(be_abi_call_t *call)
 187 {
 188         del_set(call->params);
 189         free(call);
 190 }
 191
 192 /*
 193   _____                           _   _                 _ _ _
 194  |  ___| __ __ _ _ __ ___   ___  | | | | __ _ _ __   __| | (_)_ __   __ _
 195  | |_ | '__/ _` | '_ ` _ \ / _ \ | |_| |/ _` | '_ \ / _` | | | '_ \ / _` |
 196  |  _|| | | (_| | | | | | |  __/ |  _  | (_| | | | | (_| | | | | | | (_| |
 197  |_|  |_|  \__,_|_| |_| |_|\___| |_| |_|\__,_|_| |_|\__,_|_|_|_| |_|\__, |
 198                                                                     |___/
 199
 200   Handling of the stack frame. It is composed of three types:
 201   1) The type of the arguments which are pushed on the stack.
 202   2) The "between type" which consists of stuff the call of the
 203      function pushes on the stack (like the return address and
 204          the old base pointer for ia32).
 205   3) The Firm frame type which consists of all local variables
 206      and the spills.
 207 */
 208
 209 static int get_stack_entity_offset(be_stack_frame_t *frame, entity *ent, int bias)
 210 {
 211         type *t = get_entity_owner(ent);
 212         int ofs = get_entity_offset_bytes(ent);
 213
 214         int i, index;
 215
 216         /* Find the type the entity is contained in. */
 217         for(index = 0; index < N_FRAME_TYPES; ++index) {
 218                 if(frame->order[index] == t)
 219                         break;
 220         }
 221
 222         /* Add the size of all the types below the one of the entity to the entity's offset */
 223         for(i = 0; i < index; ++i)
 224                 ofs += get_type_size_bytes(frame->order[i]);
 225
 226         /* correct the offset by the initial position of the frame pointer */
 227         ofs -= frame->initial_offset;
 228
 229         /* correct the offset with the current bias. */
 230         ofs += bias;
 231
 232         return ofs;
 233 }
 234
 235 static entity *search_ent_with_offset(type *t, int offset)
 236 {
 237         int i, n;
 238
 239         for(i = 0, n = get_class_n_members(t); i < n; ++i) {
 240                 entity *ent = get_class_member(t, i);
 241                 if(get_entity_offset_bytes(ent) == offset)
 242                         return ent;
 243         }
 244
 245         return NULL;
 246 }
 247
 248 static int stack_frame_compute_initial_offset(be_stack_frame_t *frame)
 249 {
 250         type   *base = frame->stack_dir < 0 ? frame->between_type : frame->frame_type;
 251         entity *ent  = search_ent_with_offset(base, 0);
 252         frame->initial_offset = 0;
 253         frame->initial_offset = get_stack_entity_offset(frame, ent, 0);
 254         return frame->initial_offset;
 255 }
 256
 257 static be_stack_frame_t *stack_frame_init(be_stack_frame_t *frame, type *args, type *between, type *locals, int stack_dir)
 258 {
 259         frame->arg_type       = args;
 260         frame->between_type   = between;
 261         frame->frame_type     = locals;
 262         frame->initial_offset = 0;
 263         frame->stack_dir      = stack_dir;
 264         frame->order[1]       = between;
 265
 266         if(stack_dir > 0) {
 267                 frame->order[0] = args;
 268                 frame->order[2] = locals;
 269         }
 270
 271         else {
 272                 frame->order[0] = locals;
 273                 frame->order[2] = args;
 274         }
 275
 276         return frame;
 277 }
 278
 279 static void stack_frame_dump(FILE *file, be_stack_frame_t *frame)
 280 {
 281         int i, j, n;
 282
 283         ir_fprintf(file, "initial offset: %d\n", frame->initial_offset);
 284         for(j = 0; j < N_FRAME_TYPES; ++j) {
 285                 type *t = frame->order[j];
 286
 287                 ir_fprintf(file, "type %d: %Fm size: %d\n", j, t, get_type_size_bytes(t));
 288                 for(i = 0, n = get_class_n_members(t); i < n; ++i) {
 289                         entity *ent = get_class_member(t, i);
 290                         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));
 291                 }
 292         }
 293 }
 294
 295 /**
 296  * If irn is a Sel node computing the address of an entity
 297  * on the frame type return the entity, else NULL.
 298  */
 299 static INLINE entity *get_sel_ent(ir_node *irn)
 300 {
 301         if(get_irn_opcode(irn) == iro_Sel
 302                 && get_Sel_ptr(irn) == get_irg_frame(get_irn_irg(irn))) {
 303
 304                 return get_Sel_entity(irn);
 305         }
 306
 307         return NULL;
 308 }
 309
 310 /**
 311  * Walker: Replaces Loads, Stores and Sels of frame type entities
 312  * by FrameLoad, FrameStore and FrameAdress.
 313  */
 314 static void lower_frame_sels_walker(ir_node *irn, void *data)
 315 {
 316         ir_node *nw  = NULL;
 317         entity *ent = get_sel_ent(irn);
 318
 319         if(ent != NULL) {
 320                 be_abi_irg_t *env = data;
 321                 ir_node *bl       = get_nodes_block(irn);
 322                 ir_graph *irg     = get_irn_irg(bl);
 323                 ir_node *frame    = get_irg_frame(irg);
 324
 325                 nw = be_new_FrameAddr(env->isa->sp->reg_class, irg, bl, frame, ent);
 326         }
 327
 328         if(nw != NULL)
 329                 exchange(irn, nw);
 330 }
 331
 332 static INLINE int is_on_stack(be_abi_call_t *call, int pos)
 333 {
 334         be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
 335         return arg && !arg->in_reg;
 336 }
 337
 338 /*
 339    ____      _ _
 340   / ___|__ _| | |___
 341  | |   / _` | | / __|
 342  | |__| (_| | | \__ \
 343   \____\__,_|_|_|___/
 344
 345   Adjustment of the calls inside a graph.
 346
 347 */
 348
 349 /**
 350  * Transform a call node.
 351  * @param env The ABI environment for the current irg.
 352  * @param irn The call node.
 353  * @param curr_sp The stack pointer node to use.
 354  * @return The stack pointer after the call.
 355  */
 356 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
 357 {
 358         ir_graph *irg             = env->birg->irg;
 359         const arch_isa_t *isa     = env->birg->main_env->arch_env->isa;
 360         be_abi_call_t *call       = be_abi_call_new();
 361         ir_type *mt               = get_Call_type(irn);
 362         ir_node *call_ptr         = get_Call_ptr(irn);
 363         int n_params              = get_method_n_params(mt);
 364         ir_node *curr_mem         = get_Call_mem(irn);
 365         ir_node *bl               = get_nodes_block(irn);
 366         pset *results             = pset_new_ptr(8);
 367         pset *caller_save         = pset_new_ptr(8);
 368         int stack_size            = 0;
 369         int stack_dir             = arch_isa_stack_dir(isa);
 370         const arch_register_t *sp = arch_isa_sp(isa);
 371         ir_mode *mach_mode        = sp->reg_class->mode;
 372         struct obstack *obst      = &env->obst;
 373         ir_node *no_mem           = get_irg_no_mem(irg);
 374
 375         ir_node *res_proj = NULL;
 376         int curr_res_proj = pn_Call_max;
 377         int n_low_args    = 0;
 378         int n_pos         = 0;
 379
 380         ir_node *low_call;
 381         ir_node **in;
 382         ir_node **res_projs;
 383         const ir_edge_t *edge;
 384         int *low_args;
 385         int *pos;
 386         int i, n;
 387
 388         /* Let the isa fill out the abi description for that call node. */
 389         arch_isa_get_call_abi(isa, mt, call);
 390
 391         /* Insert code to put the stack arguments on the stack. */
 392         assert(get_Call_n_params(irn) == n_params);
 393         for(i = 0; i < n_params; ++i) {
 394                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 395                 assert(arg);
 396                 if(arg->on_stack) {
 397                         stack_size += get_type_size_bytes(get_method_param_type(mt, i));
 398                         obstack_int_grow(obst, i);
 399                         n_pos++;
 400                 }
 401         }
 402         pos = obstack_finish(obst);
 403
 404         /* Collect all arguments which are passed in registers. */
 405         for(i = 0, n = get_Call_n_params(irn); i < n; ++i) {
 406                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 407                 if(arg && arg->in_reg) {
 408                         obstack_int_grow(obst, i);
 409                         n_low_args++;
 410                 }
 411         }
 412         low_args = obstack_finish(obst);
 413
 414         /* If there are some parameters which shall be passed on the stack. */
 415         if(n_pos > 0) {
 416                 int curr_ofs      = 0;
 417                 int do_seq        = call->flags.bits.store_args_sequential;
 418
 419                 /* Reverse list of stack parameters if call arguments are from left to right */
 420                 if(call->flags.bits.left_to_right) {
 421                         for(i = 0; i < n_pos / 2; ++i) {
 422                                 int other  = n_pos - i - 1;
 423                                 int tmp    = pos[i];
 424                                 pos[i]     = pos[other];
 425                                 pos[other] = tmp;
 426                         }
 427                 }
 428
 429                 /*
 430                  * If the stack is decreasing and we do not want to store sequentially,
 431                  * we allocate as much space on the stack all parameters need, by
 432                  * moving the stack pointer along the stack's direction.
 433                  */
 434                 if(stack_dir < 0 && !do_seq) {
 435                         curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, no_mem, stack_size, be_stack_dir_along);
 436                 }
 437
 438                 assert(mode_is_reference(mach_mode) && "machine mode must be pointer");
 439                 for(i = 0; i < n_pos; ++i) {
 440                         int p            = pos[i];
 441                         ir_node *param   = get_Call_param(irn, p);
 442                         ir_node *addr    = curr_sp;
 443                         ir_node *mem     = NULL;
 444                         type *param_type = get_method_param_type(mt, p);
 445                         int param_size   = get_type_size_bytes(param_type);
 446
 447                         /* Make the expression to compute the argument's offset. */
 448                         if(curr_ofs > 0) {
 449                                 addr = new_r_Const_long(irg, bl, mode_Is, curr_ofs);
 450                                 addr = new_r_Add(irg, bl, curr_sp, addr, mach_mode);
 451                         }
 452
 453                         /* Insert a store for primitive arguments. */
 454                         if(is_atomic_type(param_type)) {
 455                                 mem = new_r_Store(irg, bl, curr_mem, addr, param);
 456                                 mem = new_r_Proj(irg, bl, mem, mode_M, pn_Store_M);
 457                         }
 458
 459                         /* Make a memcopy for compound arguments. */
 460                         else {
 461                                 assert(mode_is_reference(get_irn_mode(param)));
 462                                 mem = new_r_CopyB(irg, bl, curr_mem, addr, param, param_type);
 463                                 mem = new_r_Proj(irg, bl, mem, mode_M, pn_CopyB_M_regular);
 464                         }
 465
 466                         obstack_ptr_grow(obst, mem);
 467
 468                         curr_ofs += param_size;
 469
 470                         /*
 471                         * If we wanted to build the arguments sequentially,
 472                         * the stack pointer for the next must be incremented,
 473                         * and the memory value propagated.
 474                         */
 475                         if(do_seq) {
 476                                 curr_ofs = 0;
 477                                 curr_sp  = be_new_IncSP(sp, irg, bl, curr_sp, no_mem, param_size, be_stack_dir_along);
 478                                 curr_mem = mem;
 479                         }
 480                 }
 481
 482                 in = (ir_node **) obstack_finish(obst);
 483
 484                 /* We need the sync only, if we didn't build the stores sequentially. */
 485                 if(!do_seq)
 486                         curr_mem = new_r_Sync(irg, bl, n_pos, in);
 487                 obstack_free(obst, in);
 488         }
 489
 490         /* Collect caller save registers */
 491         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
 492                 int j;
 493                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
 494                 for(j = 0; j < cls->n_regs; ++j) {
 495                         const arch_register_t *reg = arch_register_for_index(cls, j);
 496                         if(arch_register_type_is(reg, caller_save))
 497                                 pset_insert_ptr(caller_save, (void *) reg);
 498                 }
 499         }
 500
 501         /* search the greatest result proj number */
 502         foreach_out_edge(irn, edge) {
 503                 const ir_edge_t *res_edge;
 504                 ir_node *irn = get_edge_src_irn(edge);
 505
 506                 if(is_Proj(irn) && get_irn_mode(irn) == mode_T) {
 507                         res_proj = irn;
 508                         foreach_out_edge(irn, res_edge) {
 509                                 int proj;
 510                                 be_abi_call_arg_t *arg;
 511                                 ir_node *res = get_edge_src_irn(res_edge);
 512
 513                                 assert(is_Proj(res));
 514
 515                                 proj = get_Proj_proj(res);
 516                                 arg = get_call_arg(call, 1, proj);
 517
 518                                 /*
 519                                         shift the proj number to the right, since we will drop the
 520                                         unspeakable Proj_T from the Call. Therefore, all real argument
 521                                         Proj numbers must be increased by pn_Call_max
 522                                 */
 523                                 proj += pn_Call_max;
 524                                 set_Proj_proj(res, proj);
 525                                 obstack_ptr_grow(obst, res);
 526
 527                                 if(proj > curr_res_proj)
 528                                         curr_res_proj = proj;
 529                                 if(arg->in_reg)
 530                                         pset_remove_ptr(caller_save, arg->reg);
 531                         }
 532                 }
 533         }
 534         curr_res_proj++;
 535         obstack_ptr_grow(obst, NULL);
 536         res_projs = obstack_finish(obst);
 537
 538         /* make the back end call node and set its register requirements. */
 539         for(i = 0; i < n_low_args; ++i)
 540                 obstack_ptr_grow(obst, get_Call_param(irn, low_args[i]));
 541
 542         in = obstack_finish(obst);
 543         if(env->call->flags.bits.call_has_imm && get_irn_opcode(call_ptr) == iro_SymConst) {
 544                 low_call = be_new_Call(irg, bl, curr_mem, curr_sp, curr_sp, curr_res_proj, n_low_args, in);
 545                 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
 546         }
 547
 548         else
 549                 low_call = be_new_Call(irg, bl, curr_mem, curr_sp, call_ptr, curr_res_proj, n_low_args, in);
 550
 551         /* Set the register classes and constraints of the Call parameters. */
 552         for(i = 0; i < n_low_args; ++i) {
 553                 int index = low_args[i];
 554                 be_abi_call_arg_t *arg = get_call_arg(call, 0, index);
 555                 assert(arg->reg != NULL);
 556                 be_set_constr_single_reg(low_call, index, arg->reg);
 557         }
 558
 559         /* Set the register constraints of the results. */
 560         for(i = 0; res_projs[i]; ++i) {
 561                 ir_node *irn                 = res_projs[i];
 562                 int proj                     = get_Proj_proj(irn);
 563
 564                 /* Correct Proj number since it has been adjusted! (see above) */
 565                 const be_abi_call_arg_t *arg = get_call_arg(call, 1, proj - pn_Call_max);
 566
 567                 assert(arg->in_reg);
 568                 be_set_constr_single_reg(low_call, BE_OUT_POS(proj), arg->reg);
 569         }
 570         obstack_free(obst, in);
 571         exchange(irn, low_call);
 572
 573         /* redirect the result projs to the lowered call instead of the Proj_T */
 574         for(i = 0; res_projs[i]; ++i)
 575                 set_Proj_pred(res_projs[i], low_call);
 576
 577         /* Make additional projs for the caller save registers
 578            and the Keep node which keeps them alive. */
 579         if(pset_count(caller_save) > 0) {
 580                 const arch_register_t *reg;
 581                 ir_node **in, *keep;
 582                 int i, n;
 583
 584                 for(reg = pset_first(caller_save), n = 0; reg; reg = pset_next(caller_save), ++n) {
 585                         ir_node *proj = new_r_Proj(irg, bl, low_call, reg->reg_class->mode, curr_res_proj++);
 586
 587                         /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
 588                         set_irn_link(proj, (void *) reg);
 589                         obstack_ptr_grow(obst, proj);
 590                 }
 591
 592                 in   = (ir_node **) obstack_finish(obst);
 593                 keep = be_new_Keep(NULL, irg, bl, n, in);
 594                 for(i = 0; i < n; ++i) {
 595                         const arch_register_t *reg = get_irn_link(in[i]);
 596                         be_node_set_reg_class(keep, i, reg->reg_class);
 597                 }
 598                 obstack_free(obst, in);
 599         }
 600
 601         /* Clean up the stack. */
 602         if(stack_size > 0) {
 603                 ir_node *mem_proj = NULL;
 604
 605                 foreach_out_edge(low_call, edge) {
 606                         ir_node *irn = get_edge_src_irn(edge);
 607                         if(is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
 608                                 mem_proj = irn;
 609                                 break;
 610                         }
 611                 }
 612
 613                 if(!mem_proj)
 614                         mem_proj = new_r_Proj(irg, bl, low_call, mode_M, pn_Call_M);
 615
 616                 /* Make a Proj for the stack pointer. */
 617                 curr_sp     = be_new_IncSP(sp, irg, bl, curr_sp, mem_proj, stack_size, be_stack_dir_against);
 618         }
 619
 620         be_abi_call_free(call);
 621         obstack_free(obst, pos);
 622         del_pset(results);
 623         del_pset(caller_save);
 624
 625         return curr_sp;
 626 }
 627
 628 /**
 629  * Adjust an alloca.
 630  * The alloca is transformed into a back end alloca node and connected to the stack nodes.
 631  */
 632 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
 633 {
 634         if(get_Alloc_where(alloc) == stack_alloc) {
 635                 ir_node *bl        = get_nodes_block(alloc);
 636                 ir_graph *irg      = get_irn_irg(bl);
 637                 ir_node *alloc_mem = NULL;
 638                 ir_node *alloc_res = NULL;
 639
 640                 const ir_edge_t *edge;
 641                 ir_node *new_alloc;
 642
 643                 env->call->flags.bits.try_omit_fp = 0;
 644
 645                 new_alloc = be_new_AddSP(env->isa->sp, irg, bl, curr_sp, get_Alloc_size(alloc));
 646
 647                 foreach_out_edge(alloc, edge) {
 648                         ir_node *irn = get_edge_src_irn(edge);
 649
 650                         assert(is_Proj(irn));
 651                         switch(get_Proj_proj(irn)) {
 652                         case pn_Alloc_M:
 653                                 alloc_mem = irn;
 654                                 break;
 655                         case pn_Alloc_res:
 656                                 alloc_res = irn;
 657                                 break;
 658                         default:
 659                                 break;
 660                         }
 661                 }
 662
 663                 assert(alloc_res != NULL);
 664                 exchange(alloc_res, env->isa->stack_dir < 0 ? new_alloc : curr_sp);
 665
 666                 if(alloc_mem != NULL)
 667                         exchange(alloc_mem, new_r_NoMem(irg));
 668
 669                 curr_sp = new_alloc;
 670         }
 671
 672         return curr_sp;
 673 }
 674
 675 /**
 676  * Walker for dependent_on().
 677  * This function searches a node tgt recursively from a given node
 678  * but is restricted to the given block.
 679  * @return 1 if tgt was reachable from curr, 0 if not.
 680  */
 681 static int check_dependence(ir_node *curr, ir_node *tgt, ir_node *bl, unsigned long visited_nr)
 682 {
 683         int n, i;
 684
 685         if(get_irn_visited(curr) >= visited_nr)
 686                 return 0;
 687
 688         set_irn_visited(curr, visited_nr);
 689         if(get_nodes_block(curr) != bl)
 690                 return 0;
 691
 692         if(curr == tgt)
 693                 return 1;
 694
 695         for(i = 0, n = get_irn_arity(curr); i < n; ++i) {
 696                 if(check_dependence(get_irn_n(curr, i), tgt, bl, visited_nr))
 697                         return 1;
 698         }
 699
 700         return 0;
 701 }
 702
 703 /**
 704  * Check if a node is somehow data dependent on another one.
 705  * both nodes must be in the same basic block.
 706  * @param n1 The first node.
 707  * @param n2 The second node.
 708  * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
 709  */
 710 static int dependent_on(ir_node *n1, ir_node *n2)
 711 {
 712         ir_node *bl   = get_nodes_block(n1);
 713         ir_graph *irg = get_irn_irg(bl);
 714         long vis_nr   = get_irg_visited(irg) + 1;
 715
 716         assert(bl == get_nodes_block(n2));
 717         set_irg_visited(irg, vis_nr);
 718         return check_dependence(n1, n2, bl, vis_nr);
 719 }
 720
 721 static int cmp_call_dependecy(const void *c1, const void *c2)
 722 {
 723         ir_node *n1 = *(ir_node **) c1;
 724         ir_node *n2 = *(ir_node **) c2;
 725
 726         /*
 727                 Classical qsort() comparison function behavior:
 728                 0  if both elements are equal
 729                 1  if second is "smaller" that first
 730                 -1 if first is "smaller" that second
 731         */
 732         return n1 == n2 ? 0 : (dependent_on(n1, n2) ? -1 : 1);
 733 }
 734
 735 static void link_calls_in_block_walker(ir_node *irn, void *data)
 736 {
 737         if(is_Call(irn)) {
 738                 be_abi_irg_t *env = data;
 739                 ir_node *bl       = get_nodes_block(irn);
 740                 void *save        = get_irn_link(bl);
 741
 742                 env->call->flags.bits.irg_is_leaf = 0;
 743
 744                 set_irn_link(irn, save);
 745                 set_irn_link(bl, irn);
 746         }
 747 }
 748
 749 /**
 750  * Process all call nodes inside a basic block.
 751  * Note that the link field of the block must contain a linked list of all
 752  * Call nodes inside the block. We first order this list according to data dependency
 753  * and that connect the calls together.
 754  */
 755 static void process_calls_in_block(ir_node *bl, void *data)
 756 {
 757         be_abi_irg_t *env = data;
 758         ir_node *curr_sp  = env->init_sp;
 759         ir_node *irn;
 760         int n;
 761
 762         for(irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
 763                 obstack_ptr_grow(&env->obst, irn);
 764
 765         /* If there were call nodes in the block. */
 766         if(n > 0) {
 767                 ir_node **nodes;
 768                 int i;
 769
 770                 nodes = obstack_finish(&env->obst);
 771
 772                 /* order the call nodes according to data dependency */
 773                 qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependecy);
 774
 775                 for(i = n - 1; i >= 0; --i) {
 776                         ir_node *irn = nodes[i];
 777
 778                         switch(get_irn_opcode(irn)) {
 779                         case iro_Call:
 780                                 curr_sp = adjust_call(env, irn, curr_sp);
 781                                 break;
 782                         case iro_Alloc:
 783                                 curr_sp = adjust_alloc(env, irn, curr_sp);
 784                                 break;
 785                         default:
 786                                 break;
 787                         }
 788                 }
 789
 790                 obstack_free(&env->obst, nodes);
 791
 792                 /* Keep the last stack state in the block by tying it to Keep node */
 793                 nodes[0] = curr_sp;
 794                 be_new_Keep(env->isa->sp->reg_class, get_irn_irg(bl), bl, 1, nodes);
 795         }
 796
 797         set_irn_link(bl, curr_sp);
 798 }
 799
 800 /**
 801  * Adjust all call nodes in the graph to the ABI conventions.
 802  */
 803 static void process_calls(be_abi_irg_t *env)
 804 {
 805         ir_graph *irg = env->birg->irg;
 806
 807         env->call->flags.bits.irg_is_leaf = 1;
 808         irg_walk_graph(irg, firm_clear_link, link_calls_in_block_walker, env);
 809         irg_block_walk_graph(irg, NULL, process_calls_in_block, env);
 810 }
 811
 812 static void collect_return_walker(ir_node *irn, void *data)
 813 {
 814         if(get_irn_opcode(irn) == iro_Return) {
 815                 struct obstack *obst = data;
 816                 obstack_ptr_grow(obst, irn);
 817         }
 818 }
 819
 820 static ir_node *setup_frame(be_abi_irg_t *env)
 821 {
 822         const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
 823         const arch_register_t *sp = isa->sp;
 824         const arch_register_t *bp = isa->bp;
 825         be_abi_call_flags_bits_t flags = env->call->flags.bits;
 826         ir_graph *irg      = env->birg->irg;
 827         ir_node *bl        = get_irg_start_block(irg);
 828         ir_node *no_mem    = get_irg_no_mem(irg);
 829         ir_node *old_frame = get_irg_frame(irg);
 830         ir_node *stack     = pmap_get(env->regs, (void *) sp);
 831         ir_node *frame     = pmap_get(env->regs, (void *) bp);
 832
 833         int stack_nr       = get_Proj_proj(stack);
 834
 835         if(flags.try_omit_fp) {
 836                 stack = be_new_IncSP(sp, irg, bl, stack, no_mem, BE_STACK_FRAME_SIZE, be_stack_dir_along);
 837                 frame = stack;
 838         }
 839
 840         else {
 841                 frame = be_new_Copy(bp->reg_class, irg, bl, stack);
 842
 843                 be_node_set_flags(frame, -1, arch_irn_flags_dont_spill);
 844                 if(!flags.fp_free) {
 845                         be_set_constr_single_reg(frame, -1, bp);
 846                         be_node_set_flags(frame, -1, arch_irn_flags_ignore);
 847                         arch_set_irn_register(env->birg->main_env->arch_env, frame, bp);
 848                 }
 849
 850                 stack = be_new_IncSP(sp, irg, bl, stack, frame, BE_STACK_FRAME_SIZE, be_stack_dir_along);
 851         }
 852
 853         be_node_set_flags(env->reg_params, -(stack_nr + 1), arch_irn_flags_ignore);
 854         env->init_sp = stack;
 855         set_irg_frame(irg, frame);
 856         edges_reroute(old_frame, frame, irg);
 857
 858         return frame;
 859 }
 860
 861 static void clearup_frame(be_abi_irg_t *env, ir_node *ret, pmap *reg_map, struct obstack *obst)
 862 {
 863         const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
 864         const arch_register_t *sp = isa->sp;
 865         const arch_register_t *bp = isa->bp;
 866         ir_graph *irg      = env->birg->irg;
 867         ir_node *ret_mem   = get_Return_mem(ret);
 868         ir_node *frame     = get_irg_frame(irg);
 869         ir_node *bl        = get_nodes_block(ret);
 870         ir_node *stack     = get_irn_link(bl);
 871
 872         pmap_entry *ent;
 873
 874         if(env->call->flags.bits.try_omit_fp) {
 875                 stack = be_new_IncSP(sp, irg, bl, stack, ret_mem, BE_STACK_FRAME_SIZE, be_stack_dir_against);
 876         }
 877
 878         else {
 879                 stack = be_new_SetSP(sp, irg, bl, stack, frame, ret_mem);
 880                 be_set_constr_single_reg(stack, -1, sp);
 881                 be_node_set_flags(stack, -1, arch_irn_flags_ignore);
 882         }
 883
 884         pmap_foreach(env->regs, ent) {
 885                 const arch_register_t *reg = ent->key;
 886                 ir_node *irn               = ent->value;
 887
 888                 if(reg == sp)
 889                         obstack_ptr_grow(&env->obst, stack);
 890                 else if(reg == bp)
 891                         obstack_ptr_grow(&env->obst, frame);
 892                 else if(arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
 893                         obstack_ptr_grow(obst, irn);
 894         }
 895 }
 896
 897 static ir_type *compute_arg_type(be_abi_irg_t *env, be_abi_call_t *call, ir_type *method_type)
 898 {
 899         int dir  = env->call->flags.bits.left_to_right ? 1 : -1;
 900         int inc  = env->birg->main_env->arch_env->isa->stack_dir * dir;
 901         int n    = get_method_n_params(method_type);
 902         int curr = inc > 0 ? 0 : n - 1;
 903         int ofs  = 0;
 904
 905         char buf[128];
 906         ir_type *res;
 907         int i;
 908
 909         snprintf(buf, sizeof(buf), "%s_arg_type", get_entity_name(get_irg_entity(env->birg->irg)));
 910         res = new_type_class(new_id_from_str(buf));
 911
 912         for(i = 0; i < n; ++i, curr += inc) {
 913                 type *param_type       = get_method_param_type(method_type, curr);
 914                 be_abi_call_arg_t *arg = get_call_arg(call, 0, curr);
 915
 916                 if(arg->on_stack) {
 917                         snprintf(buf, sizeof(buf), "param_%d", i);
 918                         arg->stack_ent = new_entity(res, new_id_from_str(buf), param_type);
 919                         set_entity_offset_bytes(arg->stack_ent, ofs);
 920                         ofs += get_type_size_bytes(param_type);
 921                 }
 922         }
 923
 924         set_type_size_bytes(res, ofs);
 925         return res;
 926 }
 927
 928 static void create_register_perms(const arch_isa_t *isa, ir_graph *irg, ir_node *bl, pmap *regs)
 929 {
 930         int i, j, n;
 931         struct obstack obst;
 932
 933         obstack_init(&obst);
 934
 935         /* Create a Perm after the RegParams node to delimit it. */
 936         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
 937                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
 938                 ir_node *perm;
 939                 ir_node **in;
 940                 int n_regs;
 941
 942                 for(n_regs = 0, j = 0; j < cls->n_regs; ++j) {
 943                         const arch_register_t *reg = &cls->regs[j];
 944                         ir_node *irn = pmap_get(regs, (void *) reg);
 945
 946                         if(irn && !arch_register_type_is(reg, ignore)) {
 947                                 n_regs++;
 948                                 obstack_ptr_grow(&obst, irn);
 949                                 set_irn_link(irn, (void *) reg);
 950                         }
 951                 }
 952
 953                 obstack_ptr_grow(&obst, NULL);
 954                 in = obstack_finish(&obst);
 955                 if(n_regs > 0) {
 956                         perm = be_new_Perm(cls, irg, bl, n_regs, in);
 957                         for(j = 0; j < n_regs; ++j) {
 958                                 ir_node *arg = in[j];
 959                                 arch_register_t *reg = get_irn_link(arg);
 960                                 pmap_insert(regs, reg, arg);
 961                                 be_set_constr_single_reg(perm, BE_OUT_POS(j), reg);
 962                         }
 963                 }
 964                 obstack_free(&obst, in);
 965         }
 966
 967         obstack_free(&obst, NULL);
 968 }
 969
 970 typedef struct {
 971         const arch_register_t *reg;
 972         ir_node *irn;
 973 } reg_node_map_t;
 974
 975 static int cmp_regs(const void *a, const void *b)
 976 {
 977         const reg_node_map_t *p = a;
 978         const reg_node_map_t *q = b;
 979
 980         if(p->reg->reg_class == q->reg->reg_class)
 981                 return p->reg->index - q->reg->index;
 982         else
 983                 return p->reg->reg_class - q->reg->reg_class;
 984 }
 985
 986 static reg_node_map_t *reg_map_to_arr(struct obstack *obst, pmap *reg_map)
 987 {
 988         pmap_entry *ent;
 989         int n = pmap_count(reg_map);
 990         int i = 0;
 991         reg_node_map_t *res = obstack_alloc(obst, n * sizeof(res[0]));
 992
 993         pmap_foreach(reg_map, ent) {
 994                 res[i].reg = ent->key;
 995                 res[i].irn = ent->value;
 996                 i++;
 997         }
 998
 999         qsort(res, n, sizeof(res[0]), cmp_regs);
1000         return res;
1001 }
1002
1003 static void create_barrier(be_abi_irg_t *env, ir_node *bl, ir_node **mem, pmap *regs, int in_req)
1004 {
1005         ir_graph *irg = env->birg->irg;
1006         int i, j, n;
1007         int n_regs = pmap_count(regs);
1008         ir_node *irn;
1009         ir_node **in;
1010         reg_node_map_t *rm;
1011
1012         rm = reg_map_to_arr(&env->obst, regs);
1013
1014         for(i = 0, n = 0; i < n_regs; ++i, ++n)
1015                 obstack_ptr_grow(&env->obst, rm[i].irn);
1016
1017         if(mem) {
1018                 obstack_ptr_grow(&env->obst, *mem);
1019                 n++;
1020         }
1021
1022         in = (ir_node **) obstack_finish(&env->obst);
1023         irn = be_new_Barrier(env->birg->irg, bl, n, in);
1024         obstack_free(&env->obst, in);
1025
1026         for(n = 0; n < n_regs; ++n) {
1027                 int pos = BE_OUT_POS(n);
1028                 ir_node *proj;
1029                 const arch_register_t *reg = rm[n].reg;
1030
1031                 proj = new_r_Proj(env->birg->irg, bl, irn, get_irn_mode(rm[i].irn), n);
1032                 if(in_req)
1033                         be_set_constr_single_reg(irn, n, reg);
1034                 be_set_constr_single_reg(irn, pos, reg);
1035                 be_node_set_reg_class(irn, pos, reg->reg_class);
1036                 arch_set_irn_register(env->birg->main_env->arch_env, proj, reg);
1037                 if(arch_register_type_is(reg, ignore))
1038                         be_node_set_flags(irn, pos, arch_irn_flags_ignore);
1039
1040                 pmap_insert(regs, (void *) reg, proj);
1041         }
1042
1043         if(mem) {
1044                 *mem = new_r_Proj(env->birg->irg, bl, irn, mode_M, n);
1045         }
1046
1047         obstack_free(&env->obst, rm);
1048 }
1049
1050 /**
1051  * Modify the irg itself and the frame type.
1052  */
1053 static void modify_irg(be_abi_irg_t *env)
1054 {
1055         firm_dbg_module_t *dbg    = env->dbg;
1056         be_abi_call_t *call       = env->call;
1057         const arch_isa_t *isa     = env->birg->main_env->arch_env->isa;
1058         const arch_register_t *sp = arch_isa_sp(isa);
1059         ir_graph *irg             = env->birg->irg;
1060         ir_node *bl               = get_irg_start_block(irg);
1061         ir_node *end              = get_irg_end_block(irg);
1062         ir_node *arg_tuple        = get_irg_args(irg);
1063         ir_node *no_mem           = get_irg_no_mem(irg);
1064         type *method_type         = get_entity_type(get_irg_entity(irg));
1065         pset *dont_save           = pset_new_ptr(8);
1066         pmap *reg_proj_map        = pmap_create();
1067         int n_params              = get_method_n_params(method_type);
1068         int max_arg               = 0;
1069         int arg_offset            = 0;
1070
1071         int i, j, n;
1072
1073         reg_node_map_t *rm;
1074         const arch_register_t *fp_reg;
1075         ir_node *frame_pointer;
1076         ir_node *reg_params_bl;
1077         ir_node **args;
1078         const ir_edge_t *edge;
1079         ir_type *arg_type, *bet_type;
1080
1081         pmap_entry *ent;
1082         bitset_t *used_proj_nr;
1083
1084         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1085
1086         /* Convert the Sel nodes in the irg to frame load/store/addr nodes. */
1087         irg_walk_graph(irg, lower_frame_sels_walker, NULL, env);
1088
1089         env->frame = obstack_alloc(&env->obst, sizeof(env->frame[0]));
1090         env->regs  = pmap_create();
1091
1092         /* Find the maximum proj number of the argument tuple proj */
1093         foreach_out_edge(arg_tuple, edge)  {
1094                 ir_node *irn = get_edge_src_irn(edge);
1095                 int nr       = get_Proj_proj(irn);
1096                 max_arg      = MAX(max_arg, nr);
1097         }
1098         max_arg = MAX(max_arg + 1, n_params);
1099         args        = obstack_alloc(&env->obst, max_arg * sizeof(args[0]));
1100         memset(args, 0, max_arg * sizeof(args[0]));
1101         used_proj_nr = bitset_alloca(1024);
1102
1103         /* Fill the argument vector */
1104         foreach_out_edge(arg_tuple, edge) {
1105                 ir_node *irn = get_edge_src_irn(edge);
1106                 int nr       = get_Proj_proj(irn);
1107                 args[nr]     = irn;
1108                 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1109         }
1110
1111         arg_type = compute_arg_type(env, call, method_type);
1112         bet_type = call->cb->get_between_type(env->cb);
1113         stack_frame_init(env->frame, arg_type, bet_type, get_irg_frame_type(irg), isa->stack_dir);
1114
1115         /* Count the register params and add them to the number of Projs for the RegParams node */
1116         for(i = 0; i < n_params; ++i) {
1117                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1118                 if(arg->in_reg && args[i]) {
1119                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1120                         assert(i == get_Proj_proj(args[i]));
1121
1122                         /* For now, associate the register with the old Proj from Start representing that argument. */
1123                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1124                         bitset_set(used_proj_nr, i);
1125                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1126                 }
1127         }
1128
1129         /* Collect all callee-save registers */
1130         for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
1131                 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
1132                 for(j = 0; j < cls->n_regs; ++j) {
1133                         const arch_register_t *reg = &cls->regs[j];
1134                         if(arch_register_type_is(reg, callee_save))
1135                                 pmap_insert(env->regs, (void *) reg, NULL);
1136                 }
1137         }
1138
1139         pmap_insert(env->regs, (void *) sp, NULL);
1140         pmap_insert(env->regs, (void *) isa->bp, NULL);
1141         reg_params_bl   = get_irg_start_block(irg);
1142         env->reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(env->regs));
1143
1144         /*
1145          * make proj nodes for the callee save registers.
1146          * memorize them, since Return nodes get those as inputs.
1147          *
1148          * Note, that if a register corresponds to an argument, the regs map contains
1149          * the old Proj from start for that argument.
1150          */
1151
1152         rm = reg_map_to_arr(&env->obst, env->regs);
1153         for(i = 0, n = pmap_count(env->regs); i < n; ++i) {
1154                 arch_register_t *reg = (void *) rm[i].reg;
1155                 ir_node *arg_proj    = rm[i].irn;
1156                 ir_node *proj;
1157                 ir_mode *mode        = arg_proj ? get_irn_mode(arg_proj) : reg->reg_class->mode;
1158                 long nr              = i;
1159                 int pos              = BE_OUT_POS((int) nr);
1160
1161                 assert(nr >= 0);
1162                 bitset_set(used_proj_nr, nr);
1163                 proj = new_r_Proj(irg, reg_params_bl, env->reg_params, mode, nr);
1164                 pmap_insert(env->regs, (void *) reg, proj);
1165                 be_set_constr_single_reg(env->reg_params, pos, reg);
1166                 arch_set_irn_register(env->birg->main_env->arch_env, proj, reg);
1167
1168                 /*
1169                  * If the register is an ignore register,
1170                  * The Proj for that register shall also be ignored during register allocation.
1171                  */
1172                 if(arch_register_type_is(reg, ignore))
1173                         be_node_set_flags(env->reg_params, pos, arch_irn_flags_ignore);
1174
1175                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1176         }
1177         obstack_free(&env->obst, rm);
1178
1179         /* Generate the Prologue */
1180         fp_reg = call->cb->prologue(env->cb, env->regs);
1181         create_barrier(env, bl, NULL, env->regs, 0);
1182         env->init_sp  = pmap_get(env->regs, (void *) sp);
1183         env->init_sp  = be_new_IncSP(sp, irg, bl, env->init_sp, no_mem, BE_STACK_FRAME_SIZE, be_stack_dir_along);
1184         arch_set_irn_register(env->birg->main_env->arch_env, env->init_sp, sp);
1185         pmap_insert(env->regs, (void *) sp, env->init_sp);
1186         frame_pointer = pmap_get(env->regs, (void *) fp_reg);
1187         set_irg_frame(irg, frame_pointer);
1188
1189         /* Now, introduce stack param nodes for all parameters passed on the stack */
1190         for(i = 0; i < max_arg; ++i) {
1191                 ir_node *arg_proj = args[i];
1192                 ir_node *repl     = NULL;
1193
1194                 if(arg_proj != NULL) {
1195                         be_abi_call_arg_t *arg;
1196                         ir_type *param_type;
1197                         int nr = get_Proj_proj(arg_proj);
1198
1199                         nr         = MIN(nr, n_params);
1200                         arg        = get_call_arg(call, 0, nr);
1201                         param_type = get_method_param_type(method_type, nr);
1202
1203                         if(arg->in_reg) {
1204                                 repl = pmap_get(env->regs, (void *) arg->reg);
1205                         }
1206
1207                         else if(arg->on_stack) {
1208                                 /* For atomic parameters which are actually used, we create a StackParam node. */
1209                                 if(is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1210                                         ir_mode *mode                    = get_type_mode(param_type);
1211                                         const arch_register_class_t *cls = arch_isa_get_reg_class_for_mode(isa, mode);
1212                                         repl = be_new_StackParam(cls, isa->bp->reg_class, irg, reg_params_bl, mode, frame_pointer, arg->stack_ent);
1213                                 }
1214
1215                                 /* The stack parameter is not primitive (it is a struct or array),
1216                                 we thus will create a node representing the parameter's address
1217                                 on the stack. */
1218                                 else {
1219                                         repl = be_new_FrameAddr(sp->reg_class, irg, reg_params_bl, frame_pointer, arg->stack_ent);
1220                                 }
1221                         }
1222
1223                         assert(repl != NULL);
1224                         edges_reroute(args[i], repl, irg);
1225                 }
1226         }
1227
1228         /* All Return nodes hang on the End node, so look for them there. */
1229         for(i = 0, n = get_irn_arity(end); i < n; ++i) {
1230                 ir_node *irn = get_irn_n(end, i);
1231
1232                 if(get_irn_opcode(irn) == iro_Return) {
1233                         ir_node *bl    = get_nodes_block(irn);
1234                         int n_res      = get_Return_n_ress(irn);
1235                         pmap *reg_map  = pmap_create();
1236                         ir_node *mem   = get_Return_mem(irn);
1237                         ir_node *ret;
1238                         int i, n;
1239                         ir_node **in;
1240
1241                         pmap_insert(reg_map, (void *) sp, pmap_get(env->regs, (void *) sp));
1242
1243                         /* Insert results for Return into the register map. */
1244                         for(i = 0; i < n_res; ++i) {
1245                                 ir_node *res           = get_Return_res(irn, i);
1246                                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1247                                 assert(arg->in_reg && "return value must be passed in register");
1248                                 pmap_insert(reg_map, (void *) arg->reg, res);
1249                         }
1250
1251                         /* Add uses of the callee save registers. */
1252                         pmap_foreach(env->regs, ent) {
1253                                 const arch_register_t *reg = ent->key;
1254                                 if(arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1255                                         pmap_insert(reg_map, ent->key, ent->value);
1256                         }
1257
1258                         /* Make the Epilogue node and call the arch's epilogue maker. */
1259                         create_barrier(env, bl, &mem, reg_map, 1);
1260                         call->cb->epilogue(env->cb, bl, &mem, reg_map);
1261
1262                         obstack_ptr_grow(&env->obst, mem);
1263                         obstack_ptr_grow(&env->obst, pmap_get(reg_map, (void *) sp));
1264
1265                         /* clear SP entry, since it has already been grown. */
1266                         pmap_insert(reg_map, (void *) sp, NULL);
1267                         for(i = 0; i < n_res; ++i) {
1268                                 ir_node *res           = get_Return_res(irn, i);
1269                                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1270
1271                                 obstack_ptr_grow(&env->obst, pmap_get(reg_map, (void *) arg->reg));
1272
1273                                 /* Clear the map entry to mark the register as processed. */
1274                                 pmap_insert(reg_map, (void *) arg->reg, NULL);
1275                         }
1276
1277                         /* grow the rest of the stuff. */
1278                         pmap_foreach(reg_map, ent) {
1279                                 if(ent->value)
1280                                         obstack_ptr_grow(&env->obst, ent->value);
1281                         }
1282
1283                         /* The in array for the new back end return is now ready. */
1284                         n   = obstack_object_size(&env->obst) / sizeof(in[0]);
1285                         in  = obstack_finish(&env->obst);
1286                         ret = be_new_Return(irg, bl, n, in);
1287
1288                         /* Free the space of the Epilog's in array and the register <-> proj map. */
1289                         obstack_free(&env->obst, in);
1290                         exchange(irn, ret);
1291                         pmap_destroy(reg_map);
1292                 }
1293         }
1294
1295         obstack_free(&env->obst, args);
1296 }
1297
1298 /**
1299  * Walker: puts all Alloc(stack_alloc) on a obstack
1300  */
1301 static void collect_alloca_walker(ir_node *irn, void *data)
1302 {
1303         be_abi_irg_t *env = data;
1304         if(get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc)
1305                 obstack_ptr_grow(&env->obst, irn);
1306 }
1307
1308 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
1309 {
1310         be_abi_irg_t *env  = xmalloc(sizeof(env[0]));
1311         ir_node *old_frame = get_irg_frame(birg->irg);
1312         ir_graph *irg      = birg->irg;
1313
1314         pmap_entry *ent;
1315         ir_node *dummy;
1316
1317         env->isa           = birg->main_env->arch_env->isa;
1318         env->method_type   = get_entity_type(get_irg_entity(irg));
1319         env->call          = be_abi_call_new();
1320         arch_isa_get_call_abi(env->isa, env->method_type, env->call);
1321
1322         env->dce_survivor     = new_survive_dce();
1323         env->birg             = birg;
1324         env->dbg              = firm_dbg_register("firm.be.abi");
1325         env->stack_phis       = pset_new_ptr(16);
1326         env->init_sp = dummy  = new_r_Unknown(irg, env->isa->sp->reg_class->mode);
1327
1328         env->cb = env->call->cb->init(env->call, env->isa, irg);
1329
1330         obstack_init(&env->obst);
1331
1332         memcpy(&env->irn_handler, &abi_irn_handler, sizeof(abi_irn_handler));
1333         env->irn_ops.impl = &abi_irn_ops;
1334
1335         /* Lower all call nodes in the IRG. */
1336         process_calls(env);
1337
1338         /* Process the IRG */
1339         modify_irg(env);
1340
1341         /* reroute the stack origin of the calls to the true stack origin. */
1342         edges_reroute(dummy, env->init_sp, irg);
1343         edges_reroute(old_frame, get_irg_frame(irg), irg);
1344
1345         /* Make some important node pointers survive the dead node elimination. */
1346         survive_dce_register_irn(env->dce_survivor, &env->init_sp);
1347         pmap_foreach(env->regs, ent)
1348                 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
1349
1350         arch_env_push_irn_handler(env->birg->main_env->arch_env, &env->irn_handler);
1351
1352         env->call->cb->done(env->cb);
1353         be_liveness(irg);
1354         return env;
1355 }
1356
1357 void be_abi_free(be_abi_irg_t *env)
1358 {
1359         free_survive_dce(env->dce_survivor);
1360         del_pset(env->stack_phis);
1361         pmap_destroy(env->regs);
1362         obstack_free(&env->obst, NULL);
1363         arch_env_pop_irn_handler(env->birg->main_env->arch_env);
1364         free(env);
1365 }
1366
1367
1368 /*
1369
1370   _____ _        ____  _             _
1371  |  ___(_)_  __ / ___|| |_ __ _  ___| | __
1372  | |_  | \ \/ / \___ \| __/ _` |/ __| |/ /
1373  |  _| | |>  <   ___) | || (_| | (__|   <
1374  |_|   |_/_/\_\ |____/ \__\__,_|\___|_|\_\
1375
1376 */
1377
1378 static void collect_stack_nodes_walker(ir_node *irn, void *data)
1379 {
1380         pset *s = data;
1381
1382         if(be_is_AddSP(irn)     || be_is_IncSP(irn)     || be_is_SetSP(irn))
1383                 pset_insert_ptr(s, irn);
1384 }
1385
1386 void be_abi_fix_stack_nodes(be_abi_irg_t *env)
1387 {
1388         dom_front_info_t *df;
1389         pset *stack_nodes;
1390
1391         /* We need dominance frontiers for fix up */
1392         df = be_compute_dominance_frontiers(env->birg->irg);
1393         stack_nodes = pset_new_ptr(16);
1394         pset_insert_ptr(stack_nodes, env->init_sp);
1395         irg_walk_graph(env->birg->irg, collect_stack_nodes_walker, NULL, stack_nodes);
1396         be_ssa_constr_set_phis(df, stack_nodes, env->stack_phis);
1397         del_pset(stack_nodes);
1398
1399         /* Liveness could have changed due to Phi nodes. */
1400         be_liveness(env->birg->irg);
1401
1402         /* free these dominance frontiers */
1403         be_free_dominance_frontiers(df);
1404 }
1405
1406 /**
1407  * Translates a direction of an IncSP node (either be_stack_dir_against, or ...along)
1408  * into -1 or 1, respectively.
1409  * @param irn The node.
1410  * @return 1, if the direction of the IncSP was along, -1 if against.
1411  */
1412 static int get_dir(ir_node *irn)
1413 {
1414         return 1 - 2 * (be_get_IncSP_direction(irn) == be_stack_dir_against);
1415 }
1416
1417 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int bias)
1418 {
1419         const arch_env_t *aenv = env->birg->main_env->arch_env;
1420         ir_node *irn;
1421         int start_bias = bias;
1422         int omit_fp    = env->call->flags.bits.try_omit_fp;
1423
1424         sched_foreach(bl, irn) {
1425
1426                 /*
1427                         If the node modifies the stack pointer by a constant offset,
1428                         record that in the bias.
1429                 */
1430                 if(be_is_IncSP(irn)) {
1431                         int ofs = be_get_IncSP_offset(irn);
1432                         int dir = get_dir(irn);
1433
1434                         if(ofs == BE_STACK_FRAME_SIZE) {
1435                                 ofs = get_type_size_bytes(get_irg_frame_type(env->birg->irg));
1436                                 be_set_IncSP_offset(irn, ofs);
1437                         }
1438
1439                         if(omit_fp)
1440                                 bias += dir * ofs;
1441                 }
1442
1443                 /*
1444                         Else check, if the node relates to an entity on the stack frame.
1445                         If so, set the true offset (including the bias) for that
1446                         node.
1447                 */
1448                 else {
1449                         entity *ent = arch_get_frame_entity(aenv, irn);
1450                         if(ent) {
1451                                 int offset = get_stack_entity_offset(env->frame, ent, bias);
1452                                 arch_set_frame_offset(aenv, irn, offset);
1453                                 DBG((env->dbg, LEVEL_2, "%F has offset %d\n", ent, offset));
1454                         }
1455                 }
1456         }
1457
1458         return bias;
1459 }
1460
1461 /**
1462  * A helper struct for the bias walker.
1463  */
1464 struct bias_walk {
1465         be_abi_irg_t *env;     /**< The ABI irg environment. */
1466         int start_block_bias;  /**< The bias at the end of the start block. */
1467 };
1468
1469 static void stack_bias_walker(ir_node *bl, void *data)
1470 {
1471         if(bl != get_irg_start_block(get_irn_irg(bl))) {
1472                 struct bias_walk *bw = data;
1473                 process_stack_bias(bw->env, bl, bw->start_block_bias);
1474         }
1475 }
1476
1477 void be_abi_fix_stack_bias(be_abi_irg_t *env)
1478 {
1479         ir_graph *irg  = env->birg->irg;
1480         struct bias_walk bw;
1481
1482         stack_frame_compute_initial_offset(env->frame);
1483         // stack_frame_dump(stdout, env->frame);
1484
1485         /* Determine the stack bias at the and of the start block. */
1486         bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), 0);
1487
1488         /* fix the bias is all other blocks */
1489         bw.env = env;
1490         irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
1491 }
1492
1493 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
1494 {
1495         assert(arch_register_type_is(reg, callee_save));
1496         assert(pmap_contains(abi->regs, (void *) reg));
1497         return pmap_get(abi->regs, (void *) reg);
1498 }
1499
1500 /*
1501   _____ _____  _   _   _    _                 _ _
1502  |_   _|  __ \| \ | | | |  | |               | | |
1503    | | | |__) |  \| | | |__| | __ _ _ __   __| | | ___ _ __
1504    | | |  _  /| . ` | |  __  |/ _` | '_ \ / _` | |/ _ \ '__|
1505   _| |_| | \ \| |\  | | |  | | (_| | | | | (_| | |  __/ |
1506  |_____|_|  \_\_| \_| |_|  |_|\__,_|_| |_|\__,_|_|\___|_|
1507
1508   for Phi nodes which are created due to stack modifying nodes
1509   such as IncSP, AddSP and SetSP.
1510
1511   These Phis are always to be ignored by the reg alloc and are
1512   fixed on the SP register of the ISA.
1513 */
1514
1515 static const void *abi_get_irn_ops(const arch_irn_handler_t *handler, const ir_node *irn)
1516 {
1517         const be_abi_irg_t *abi = get_abi_from_handler(handler);
1518         const void *res = NULL;
1519
1520         if(is_Phi(irn) && pset_find_ptr(abi->stack_phis, (void *) irn))
1521                 res = &abi->irn_ops;
1522
1523         return res;
1524 }
1525
1526 static void be_abi_limited(void *data, bitset_t *bs)
1527 {
1528         be_abi_irg_t *abi = data;
1529         bitset_clear_all(bs);
1530         bitset_set(bs, abi->isa->sp->index);
1531 }
1532
1533 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)
1534 {
1535         be_abi_irg_t *abi          = get_abi_from_ops(self);
1536         const arch_register_t *reg = abi->isa->sp;
1537
1538         memset(req, 0, sizeof(req[0]));
1539
1540         if(pos == BE_OUT_POS(0)) {
1541                 req->cls         = reg->reg_class;
1542                 req->type        = arch_register_req_type_limited;
1543                 req->limited     = be_abi_limited;
1544                 req->limited_env = abi;
1545         }
1546
1547         else if(pos >= 0 && pos < get_irn_arity(irn)) {
1548                 req->cls  = reg->reg_class;
1549                 req->type = arch_register_req_type_normal;
1550         }
1551
1552         return req;
1553 }
1554
1555 static void abi_set_irn_reg(const void *self, ir_node *irn, const arch_register_t *reg)
1556 {
1557 }
1558
1559 static const arch_register_t *abi_get_irn_reg(const void *self, const ir_node *irn)
1560 {
1561         const be_abi_irg_t *abi = get_abi_from_ops(self);
1562         return abi->isa->sp;
1563 }
1564
1565 static arch_irn_class_t abi_classify(const void *_self, const ir_node *irn)
1566 {
1567         return arch_irn_class_normal;
1568 }
1569
1570 static arch_irn_flags_t abi_get_flags(const void *_self, const ir_node *irn)
1571 {
1572         return arch_irn_flags_ignore;
1573 }
1574
1575 static entity *abi_get_frame_entity(const void *_self, const ir_node *irn)
1576 {
1577         return NULL;
1578 }
1579
1580 static void abi_set_stack_bias(const void *_self, ir_node *irn, int bias)
1581 {
1582 }
1583
1584 static const arch_irn_ops_if_t abi_irn_ops = {
1585         abi_get_irn_reg_req,
1586         abi_set_irn_reg,
1587         abi_get_irn_reg,
1588         abi_classify,
1589         abi_get_flags,
1590         abi_get_frame_entity,
1591         abi_set_stack_bias
1592 };
1593
1594 static const arch_irn_handler_t abi_irn_handler = {
1595         abi_get_irn_ops
1596 };