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

   1 /*
   2  * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Backend ABI implementation.
  23  * @author      Sebastian Hack, Michael Beck
  24  * @version     $Id$
  25  */
  26 #include "config.h"
  27
  28 #include "obst.h"
  29
  30 #include "irgopt.h"
  31
  32 #include "irgraph_t.h"
  33 #include "irnode_t.h"
  34 #include "ircons_t.h"
  35 #include "iredges_t.h"
  36 #include "irgmod.h"
  37 #include "irgwalk.h"
  38 #include "irprintf_t.h"
  39 #include "irgopt.h"
  40 #include "irbitset.h"
  41 #include "iropt_t.h"
  42 #include "heights.h"
  43 #include "pdeq.h"
  44 #include "irtools.h"
  45 #include "raw_bitset.h"
  46 #include "error.h"
  47 #include "pset_new.h"
  48
  49 #include "be.h"
  50 #include "beabi.h"
  51 #include "bearch.h"
  52 #include "benode.h"
  53 #include "belive_t.h"
  54 #include "besched.h"
  55 #include "beirg.h"
  56 #include "bessaconstr.h"
  57 #include "bemodule.h"
  58 #include "betranshlp.h"
  59
  60 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  61
  62 typedef struct be_abi_call_arg_t {
  63         unsigned is_res   : 1;  /**< 1: the call argument is a return value. 0: it's a call parameter. */
  64         unsigned in_reg   : 1;  /**< 1: this argument is transmitted in registers. */
  65         unsigned on_stack : 1;  /**< 1: this argument is transmitted on the stack. */
  66         unsigned callee   : 1;  /**< 1: someone called us. 0: We call another function */
  67
  68         int                    pos;
  69         const arch_register_t *reg;
  70         ir_entity             *stack_ent;
  71         ir_mode               *load_mode;
  72         unsigned               alignment;    /**< stack alignment */
  73         unsigned               space_before; /**< allocate space before */
  74         unsigned               space_after;  /**< allocate space after */
  75 } be_abi_call_arg_t;
  76
  77 struct be_abi_call_t {
  78         be_abi_call_flags_t          flags;  /**< Flags describing the ABI behavior on calls */
  79         int                          pop;    /**< number of bytes the stack frame is shrinked by the callee on return. */
  80         const be_abi_callbacks_t    *cb;
  81         ir_type                     *between_type;
  82         set                         *params;
  83         const arch_register_class_t *cls_addr; /**< register class of the call address */
  84 };
  85
  86 /**
  87  * The ABI information for the current graph.
  88  */
  89 struct be_abi_irg_t {
  90         be_abi_call_t        *call;         /**< The ABI call information. */
  91
  92         ir_node              *init_sp;      /**< The node representing the stack pointer
  93                                                  at the start of the function. */
  94
  95         ir_node              *start;        /**< The be_Start params node. */
  96         pmap                 *regs;         /**< A map of all callee-save and ignore regs to
  97                                                  their Projs to the RegParams node. */
  98         int                  start_block_bias; /**< The stack bias at the end of the start block. */
  99
 100         pmap                 *keep_map;     /**< mapping blocks to keep nodes. */
 101
 102         ir_node              **calls;       /**< flexible array containing all be_Call nodes */
 103 };
 104
 105 static ir_heights_t *ir_heights;
 106
 107 /** Flag: if set, try to omit the frame pointer in all routines. */
 108 static int be_omit_fp = 1;
 109
 110 static ir_node *be_abi_reg_map_get(pmap *map, const arch_register_t *reg)
 111 {
 112         return (ir_node*)pmap_get(map, reg);
 113 }
 114
 115 static void be_abi_reg_map_set(pmap *map, const arch_register_t* reg,
 116                                ir_node *node)
 117 {
 118         pmap_insert(map, reg, node);
 119 }
 120
 121 /**
 122  * Check if the given register is callee save, ie. will be saved by the callee.
 123  */
 124 static bool arch_register_is_callee_save(
 125         const arch_env_t      *arch_env,
 126         const arch_register_t *reg)
 127 {
 128         if (arch_env->impl->register_saved_by)
 129                 return arch_env->impl->register_saved_by(reg, /*callee=*/1);
 130         return false;
 131 }
 132
 133 /**
 134  * Check if the given register is caller save, ie. must be saved by the caller.
 135  */
 136 static bool arch_register_is_caller_save(
 137         const arch_env_t      *arch_env,
 138         const arch_register_t *reg)
 139 {
 140         if (arch_env->impl->register_saved_by)
 141                 return arch_env->impl->register_saved_by(reg, /*callee=*/0);
 142         return false;
 143 }
 144
 145
 146
 147 /*
 148      _    ____ ___    ____      _ _ _                _
 149     / \  | __ )_ _|  / ___|__ _| | | |__   __ _  ___| | _____
 150    / _ \ |  _ \| |  | |   / _` | | | '_ \ / _` |/ __| |/ / __|
 151   / ___ \| |_) | |  | |__| (_| | | | |_) | (_| | (__|   <\__ \
 152  /_/   \_\____/___|  \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
 153
 154   These callbacks are used by the backend to set the parameters
 155   for a specific call type.
 156 */
 157
 158 /**
 159  * Set compare function: compares two ABI call object arguments.
 160  */
 161 static int cmp_call_arg(const void *a, const void *b, size_t n)
 162 {
 163         const be_abi_call_arg_t *p = (const be_abi_call_arg_t*)a;
 164         const be_abi_call_arg_t *q = (const be_abi_call_arg_t*)b;
 165         (void) n;
 166         return !(p->is_res == q->is_res && p->pos == q->pos && p->callee == q->callee);
 167 }
 168
 169 /**
 170  * Get  an ABI call object argument.
 171  *
 172  * @param call      the abi call
 173  * @param is_res    true for call results, false for call arguments
 174  * @param pos       position of the argument
 175  * @param callee    context type - if we are callee or caller
 176  */
 177 static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos, int callee)
 178 {
 179         be_abi_call_arg_t arg;
 180         unsigned hash;
 181
 182         memset(&arg, 0, sizeof(arg));
 183         arg.is_res = is_res;
 184         arg.pos    = pos;
 185         arg.callee = callee;
 186
 187         hash = is_res * 128 + pos;
 188
 189         return (be_abi_call_arg_t*)set_find(call->params, &arg, sizeof(arg), hash);
 190 }
 191
 192 /**
 193  * Set an ABI call object argument.
 194  */
 195 static void remember_call_arg(be_abi_call_arg_t *arg, be_abi_call_t *call, be_abi_context_t context)
 196 {
 197         unsigned hash = arg->is_res * 128 + arg->pos;
 198         if (context & ABI_CONTEXT_CALLEE) {
 199                 arg->callee = 1;
 200                 set_insert(call->params, arg, sizeof(*arg), hash);
 201         }
 202         if (context & ABI_CONTEXT_CALLER) {
 203                 arg->callee = 0;
 204                 set_insert(call->params, arg, sizeof(*arg), hash);
 205         }
 206 }
 207
 208 /* Set the flags for a call. */
 209 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
 210 {
 211         call->flags = flags;
 212         call->cb    = cb;
 213 }
 214
 215 /* Sets the number of bytes the stackframe is shrinked by the callee on return */
 216 void be_abi_call_set_pop(be_abi_call_t *call, int pop)
 217 {
 218         assert(pop >= 0);
 219         call->pop = pop;
 220 }
 221
 222 /* Set register class for call address */
 223 void be_abi_call_set_call_address_reg_class(be_abi_call_t *call, const arch_register_class_t *cls)
 224 {
 225         call->cls_addr = cls;
 226 }
 227
 228
 229 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos,
 230                              ir_mode *load_mode, unsigned alignment,
 231                              unsigned space_before, unsigned space_after,
 232                              be_abi_context_t context)
 233 {
 234         be_abi_call_arg_t arg;
 235         memset(&arg, 0, sizeof(arg));
 236         assert(alignment > 0 && "Alignment must be greater than 0");
 237         arg.on_stack     = 1;
 238         arg.load_mode    = load_mode;
 239         arg.alignment    = alignment;
 240         arg.space_before = space_before;
 241         arg.space_after  = space_after;
 242         arg.is_res       = 0;
 243         arg.pos          = arg_pos;
 244
 245         remember_call_arg(&arg, call, context);
 246 }
 247
 248 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
 249 {
 250         be_abi_call_arg_t arg;
 251         memset(&arg, 0, sizeof(arg));
 252
 253         arg.in_reg = 1;
 254         arg.reg    = reg;
 255         arg.is_res = 0;
 256         arg.pos    = arg_pos;
 257
 258         remember_call_arg(&arg, call, context);
 259 }
 260
 261 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
 262 {
 263         be_abi_call_arg_t arg;
 264         memset(&arg, 0, sizeof(arg));
 265
 266         arg.in_reg = 1;
 267         arg.reg    = reg;
 268         arg.is_res = 1;
 269         arg.pos    = arg_pos;
 270
 271         remember_call_arg(&arg, call, context);
 272 }
 273
 274 /* Get the flags of a ABI call object. */
 275 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
 276 {
 277         return call->flags;
 278 }
 279
 280 /**
 281  * Constructor for a new ABI call object.
 282  *
 283  * @param cls_addr  register class of the call address
 284  *
 285  * @return the new ABI call object
 286  */
 287 static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
 288 {
 289         be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
 290
 291         call->flags.val  = 0;
 292         call->params     = new_set(cmp_call_arg, 16);
 293         call->cb         = NULL;
 294         call->cls_addr   = cls_addr;
 295
 296         call->flags.bits.try_omit_fp = be_omit_fp;
 297
 298         return call;
 299 }
 300
 301 /**
 302  * Destructor for an ABI call object.
 303  */
 304 static void be_abi_call_free(be_abi_call_t *call)
 305 {
 306         del_set(call->params);
 307         free(call);
 308 }
 309
 310 /**
 311  * Initializes the frame layout from parts
 312  *
 313  * @param frame     the stack layout that will be initialized
 314  * @param args      the stack argument layout type
 315  * @param between   the between layout type
 316  * @param locals    the method frame type
 317  * @param param_map an array mapping method argument positions to the stack argument type
 318  *
 319  * @return the initialized stack layout
 320  */
 321 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
 322                                            ir_type *between, ir_type *locals,
 323                                            ir_entity *param_map[])
 324 {
 325         frame->arg_type       = args;
 326         frame->between_type   = between;
 327         frame->frame_type     = locals;
 328         frame->initial_offset = 0;
 329         frame->initial_bias   = 0;
 330         frame->order[1]       = between;
 331         frame->param_map      = param_map;
 332
 333         /* typical decreasing stack: locals have the
 334          * lowest addresses, arguments the highest */
 335         frame->order[0] = locals;
 336         frame->order[2] = args;
 337         return frame;
 338 }
 339
 340 /*
 341    ____      _ _
 342   / ___|__ _| | |___
 343  | |   / _` | | / __|
 344  | |__| (_| | | \__ \
 345   \____\__,_|_|_|___/
 346
 347   Adjustment of the calls inside a graph.
 348
 349 */
 350
 351 /**
 352  * Transform a call node into a be_Call node.
 353  *
 354  * @param env The ABI environment for the current irg.
 355  * @param irn The call node.
 356  * @param curr_sp The stack pointer node to use.
 357  * @return The stack pointer after the call.
 358  */
 359 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
 360 {
 361         ir_graph *irg              = get_irn_irg(irn);
 362         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
 363         ir_type *call_tp           = get_Call_type(irn);
 364         ir_node *call_ptr          = get_Call_ptr(irn);
 365         size_t   n_params          = get_method_n_params(call_tp);
 366         ir_node *curr_mem          = get_Call_mem(irn);
 367         ir_node *bl                = get_nodes_block(irn);
 368         int stack_size             = 0;
 369         const arch_register_t *sp  = arch_env->sp;
 370         be_abi_call_t *call        = be_abi_call_new(sp->reg_class);
 371         ir_mode *mach_mode         = sp->reg_class->mode;
 372         int no_alloc               = call->flags.bits.frame_is_setup_on_call;
 373         int n_res                  = get_method_n_ress(call_tp);
 374         int do_seq                 = call->flags.bits.store_args_sequential && !no_alloc;
 375
 376         ir_node *res_proj  = NULL;
 377         int n_reg_params   = 0;
 378         int n_stack_params = 0;
 379         int n_ins;
 380
 381         const arch_register_t **states = NEW_ARR_F(const arch_register_t*, 0);
 382         const arch_register_t **destroyed_regs = NEW_ARR_F(const arch_register_t*, 0);
 383         ir_node                *low_call;
 384         ir_node               **in;
 385         ir_node               **res_projs;
 386         int                     n_reg_results = 0;
 387         const ir_edge_t        *edge;
 388         int                    *reg_param_idxs;
 389         int                    *stack_param_idx;
 390         int                     i, n, destroy_all_regs;
 391         int                     throws_exception;
 392         size_t                  s;
 393         size_t                  p;
 394         dbg_info               *dbgi;
 395
 396         /* Let the isa fill out the abi description for that call node. */
 397         arch_env_get_call_abi(arch_env, call_tp, call);
 398
 399         /* Insert code to put the stack arguments on the stack. */
 400         assert(get_Call_n_params(irn) == n_params);
 401         stack_param_idx = ALLOCAN(int, n_params);
 402         for (p = 0; p < n_params; ++p) {
 403                 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
 404                 assert(arg);
 405                 if (arg->on_stack) {
 406                         int arg_size = get_type_size_bytes(get_method_param_type(call_tp, p));
 407
 408                         stack_size += round_up2(arg->space_before, arg->alignment);
 409                         stack_size += round_up2(arg_size, arg->alignment);
 410                         stack_size += round_up2(arg->space_after, arg->alignment);
 411
 412                         stack_param_idx[n_stack_params++] = p;
 413                 }
 414         }
 415
 416         /* Collect all arguments which are passed in registers. */
 417         reg_param_idxs = ALLOCAN(int, n_params);
 418         for (p = 0; p < n_params; ++p) {
 419                 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
 420                 if (arg && arg->in_reg) {
 421                         reg_param_idxs[n_reg_params++] = p;
 422                 }
 423         }
 424
 425         /*
 426          * If the stack is decreasing and we do not want to store sequentially,
 427          * or someone else allocated the call frame
 428          * we allocate as much space on the stack all parameters need, by
 429          * moving the stack pointer along the stack's direction.
 430          *
 431          * Note: we also have to do this for stack_size == 0, because we may have
 432          * to adjust stack alignment for the call.
 433          */
 434         if (!do_seq && !no_alloc) {
 435                 curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
 436         }
 437
 438         dbgi = get_irn_dbg_info(irn);
 439         /* If there are some parameters which shall be passed on the stack. */
 440         if (n_stack_params > 0) {
 441                 int       curr_ofs = 0;
 442                 ir_node **in       = ALLOCAN(ir_node*, n_stack_params+1);
 443                 unsigned  n_in     = 0;
 444
 445                 /* push params in reverse direction because stack grows downwards */
 446                 if (do_seq) {
 447                         for (i = 0; i < n_stack_params >> 1; ++i) {
 448                                 int other  = n_stack_params - i - 1;
 449                                 int tmp    = stack_param_idx[i];
 450                                 stack_param_idx[i]     = stack_param_idx[other];
 451                                 stack_param_idx[other] = tmp;
 452                         }
 453                 }
 454
 455                 curr_mem = get_Call_mem(irn);
 456                 if (! do_seq) {
 457                         in[n_in++] = curr_mem;
 458                 }
 459
 460                 for (i = 0; i < n_stack_params; ++i) {
 461                         int p                  = stack_param_idx[i];
 462                         be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
 463                         ir_node *param         = get_Call_param(irn, p);
 464                         ir_node *addr          = curr_sp;
 465                         ir_node *mem           = NULL;
 466                         ir_type *param_type    = get_method_param_type(call_tp, p);
 467                         int param_size         = get_type_size_bytes(param_type) + arg->space_after;
 468
 469                         /*
 470                          * If we wanted to build the arguments sequentially,
 471                          * the stack pointer for the next must be incremented,
 472                          * and the memory value propagated.
 473                          */
 474                         if (do_seq) {
 475                                 curr_ofs = 0;
 476                                 addr = curr_sp = be_new_IncSP(sp, bl, curr_sp,
 477                                                               param_size + arg->space_before, 0);
 478                                 add_irn_dep(curr_sp, curr_mem);
 479                         } else {
 480                                 curr_ofs += arg->space_before;
 481                                 curr_ofs =  round_up2(curr_ofs, arg->alignment);
 482
 483                                 /* Make the expression to compute the argument's offset. */
 484                                 if (curr_ofs > 0) {
 485                                         ir_mode *constmode = mach_mode;
 486                                         if (mode_is_reference(mach_mode)) {
 487                                                 constmode = mode_Is;
 488                                         }
 489                                         addr = new_r_Const_long(irg, constmode, curr_ofs);
 490                                         addr = new_r_Add(bl, curr_sp, addr, mach_mode);
 491                                 }
 492                         }
 493
 494                         /* Insert a store for primitive arguments. */
 495                         if (is_atomic_type(param_type)) {
 496                                 ir_node *nomem     = get_irg_no_mem(irg);
 497                                 ir_node *mem_input = do_seq ? curr_mem : nomem;
 498                                 ir_node *store     = new_rd_Store(dbgi, bl, mem_input, addr, param, cons_none);
 499                                 mem   = new_r_Proj(store, mode_M, pn_Store_M);
 500                         } else {
 501                                 /* Make a mem copy for compound arguments. */
 502                                 ir_node *copy;
 503
 504                                 assert(mode_is_reference(get_irn_mode(param)));
 505                                 copy = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type);
 506                                 mem = new_r_Proj(copy, mode_M, pn_CopyB_M);
 507                         }
 508
 509                         curr_ofs += param_size;
 510
 511                         if (do_seq)
 512                                 curr_mem = mem;
 513                         else
 514                                 in[n_in++] = mem;
 515                 }
 516
 517                 /* We need the sync only, if we didn't build the stores sequentially. */
 518                 if (! do_seq) {
 519                         if (n_stack_params >= 1) {
 520                                 curr_mem = new_r_Sync(bl, n_in, in);
 521                         } else {
 522                                 curr_mem = get_Call_mem(irn);
 523                         }
 524                 }
 525         }
 526
 527         /* check for the return_twice property */
 528         destroy_all_regs = 0;
 529         if (is_SymConst_addr_ent(call_ptr)) {
 530                 ir_entity *ent = get_SymConst_entity(call_ptr);
 531
 532                 if (get_entity_additional_properties(ent) & mtp_property_returns_twice)
 533                         destroy_all_regs = 1;
 534         } else {
 535                 ir_type *call_tp = get_Call_type(irn);
 536
 537                 if (get_method_additional_properties(call_tp) & mtp_property_returns_twice)
 538                         destroy_all_regs = 1;
 539         }
 540
 541         /* Put caller save into the destroyed set and state registers in the states
 542          * set */
 543         for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
 544                 unsigned j;
 545                 const arch_register_class_t *cls = &arch_env->register_classes[i];
 546                 for (j = 0; j < cls->n_regs; ++j) {
 547                         const arch_register_t *reg = arch_register_for_index(cls, j);
 548
 549                         /* even if destroyed all is specified, neither SP nor FP are
 550                          * destroyed (else bad things will happen) */
 551                         if (reg == arch_env->sp || reg == arch_env->bp)
 552                                 continue;
 553
 554                         if (reg->type & arch_register_type_state) {
 555                                 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
 556                                 ARR_APP1(const arch_register_t*, states, reg);
 557                                 /* we're already in the destroyed set so no need for further
 558                                  * checking */
 559                                 continue;
 560                         }
 561                         if (destroy_all_regs || arch_register_is_caller_save(arch_env, reg)) {
 562                                 if (!(reg->type & arch_register_type_ignore)) {
 563                                         ARR_APP1(const arch_register_t*, destroyed_regs, reg);
 564                                 }
 565                         }
 566                 }
 567         }
 568
 569         /* search the largest result proj number */
 570         res_projs = ALLOCANZ(ir_node*, n_res);
 571
 572         foreach_out_edge(irn, edge) {
 573                 const ir_edge_t *res_edge;
 574                 ir_node         *irn = get_edge_src_irn(edge);
 575
 576                 if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
 577                         continue;
 578
 579                 foreach_out_edge(irn, res_edge) {
 580                         int proj;
 581                         ir_node *res = get_edge_src_irn(res_edge);
 582
 583                         assert(is_Proj(res));
 584
 585                         proj = get_Proj_proj(res);
 586                         assert(proj < n_res);
 587                         assert(res_projs[proj] == NULL);
 588                         res_projs[proj] = res;
 589                 }
 590                 res_proj = irn;
 591                 break;
 592         }
 593
 594         /** TODO: this is not correct for cases where return values are passed
 595          * on the stack, but no known ABI does this currently...
 596          */
 597         n_reg_results = n_res;
 598
 599         n_ins = 0;
 600         in    = ALLOCAN(ir_node*, n_reg_params + ARR_LEN(states));
 601
 602         /* make the back end call node and set its register requirements. */
 603         for (i = 0; i < n_reg_params; ++i) {
 604                 in[n_ins++] = get_Call_param(irn, reg_param_idxs[i]);
 605         }
 606
 607         /* add state registers ins */
 608         for (s = 0; s < ARR_LEN(states); ++s) {
 609                 const arch_register_t       *reg = states[s];
 610                 const arch_register_class_t *cls = reg->reg_class;
 611                 ir_node *regnode = new_r_Unknown(irg, cls->mode);
 612                 in[n_ins++]      = regnode;
 613         }
 614         assert(n_ins == (int) (n_reg_params + ARR_LEN(states)));
 615
 616         /* ins collected, build the call */
 617         throws_exception = ir_throws_exception(irn);
 618         if (env->call->flags.bits.call_has_imm && is_SymConst(call_ptr)) {
 619                 /* direct call */
 620                 low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, curr_sp,
 621                                        n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
 622                                        n_ins, in, get_Call_type(irn));
 623                 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
 624         } else {
 625                 /* indirect call */
 626                 low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, call_ptr,
 627                                        n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
 628                                        n_ins, in, get_Call_type(irn));
 629         }
 630         ir_set_throws_exception(low_call, throws_exception);
 631         be_Call_set_pop(low_call, call->pop);
 632
 633         /* put the call into the list of all calls for later processing */
 634         ARR_APP1(ir_node *, env->calls, low_call);
 635
 636         /* create new stack pointer */
 637         curr_sp = new_r_Proj(low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
 638         be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
 639                         arch_register_req_type_ignore | arch_register_req_type_produces_sp);
 640         arch_set_irn_register(curr_sp, sp);
 641
 642         /* now handle results */
 643         for (i = 0; i < n_res; ++i) {
 644                 ir_node           *proj = res_projs[i];
 645                 be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);
 646                 long               pn   = i + pn_be_Call_first_res;
 647
 648                 /* returns values on stack not supported yet */
 649                 assert(arg->in_reg);
 650
 651                 /*
 652                         shift the proj number to the right, since we will drop the
 653                         unspeakable Proj_T from the Call. Therefore, all real argument
 654                         Proj numbers must be increased by pn_be_Call_first_res
 655                 */
 656                 pn = i + pn_be_Call_first_res;
 657
 658                 if (proj == NULL) {
 659                         ir_type *res_type = get_method_res_type(call_tp, i);
 660                         ir_mode *mode     = get_type_mode(res_type);
 661                         proj              = new_r_Proj(low_call, mode, pn);
 662                         res_projs[i]      = proj;
 663                 } else {
 664                         set_Proj_pred(proj, low_call);
 665                         set_Proj_proj(proj, pn);
 666                 }
 667
 668                 if (arg->in_reg) {
 669                         /* remove register from destroyed regs */
 670                         size_t j;
 671                         size_t n = ARR_LEN(destroyed_regs);
 672                         for (j = 0; j < n; ++j) {
 673                                 if (destroyed_regs[j] == arg->reg) {
 674                                         destroyed_regs[j] = destroyed_regs[n-1];
 675                                         ARR_SHRINKLEN(destroyed_regs,n-1);
 676                                         break;
 677                                 }
 678                         }
 679                 }
 680         }
 681
 682         /*
 683                 Set the register class of the call address to
 684                 the backend provided class (default: stack pointer class)
 685         */
 686         be_node_set_reg_class_in(low_call, n_be_Call_ptr, call->cls_addr);
 687
 688         DBG((dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
 689
 690         /* Set the register classes and constraints of the Call parameters. */
 691         for (i = 0; i < n_reg_params; ++i) {
 692                 int index = reg_param_idxs[i];
 693                 be_abi_call_arg_t *arg = get_call_arg(call, 0, index, 0);
 694                 assert(arg->reg != NULL);
 695
 696                 be_set_constr_single_reg_in(low_call, n_be_Call_first_arg + i,
 697                                             arg->reg, arch_register_req_type_none);
 698         }
 699
 700         /* Set the register constraints of the results. */
 701         for (i = 0; i < n_res; ++i) {
 702                 ir_node                 *proj = res_projs[i];
 703                 const be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);
 704                 int                      pn   = get_Proj_proj(proj);
 705
 706                 assert(arg->in_reg);
 707                 be_set_constr_single_reg_out(low_call, pn, arg->reg,
 708                                              arch_register_req_type_none);
 709                 arch_set_irn_register(proj, arg->reg);
 710         }
 711         exchange(irn, low_call);
 712
 713         /* kill the ProjT node */
 714         if (res_proj != NULL) {
 715                 kill_node(res_proj);
 716         }
 717
 718         /* Make additional projs for the caller save registers
 719            and the Keep node which keeps them alive. */
 720         {
 721                 ir_node               **in, *keep;
 722                 int                   i;
 723                 size_t                d;
 724                 int                   n = 0;
 725                 int                   curr_res_proj = pn_be_Call_first_res + n_reg_results;
 726                 int                   n_ins;
 727
 728                 n_ins = ARR_LEN(destroyed_regs) + n_reg_results + 1;
 729                 in    = ALLOCAN(ir_node *, n_ins);
 730
 731                 /* also keep the stack pointer */
 732                 set_irn_link(curr_sp, (void*) sp);
 733                 in[n++] = curr_sp;
 734
 735                 for (d = 0; d < ARR_LEN(destroyed_regs); ++d) {
 736                         const arch_register_t *reg = destroyed_regs[d];
 737                         ir_node *proj = new_r_Proj(low_call, reg->reg_class->mode, curr_res_proj);
 738
 739                         /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
 740                         be_set_constr_single_reg_out(low_call, curr_res_proj, reg,
 741                                                      arch_register_req_type_none);
 742                         arch_set_irn_register(proj, reg);
 743
 744                         set_irn_link(proj, (void*) reg);
 745                         in[n++] = proj;
 746                         ++curr_res_proj;
 747                 }
 748
 749                 for (i = 0; i < n_reg_results; ++i) {
 750                         ir_node *proj = res_projs[i];
 751                         const arch_register_t *reg = arch_get_irn_register(proj);
 752                         set_irn_link(proj, (void*) reg);
 753                         in[n++] = proj;
 754                 }
 755                 assert(n <= n_ins);
 756
 757                 /* create the Keep for the caller save registers */
 758                 keep = be_new_Keep(bl, n, in);
 759                 for (i = 0; i < n; ++i) {
 760                         const arch_register_t *reg = (const arch_register_t*)get_irn_link(in[i]);
 761                         be_node_set_reg_class_in(keep, i, arch_register_get_class(reg));
 762                 }
 763         }
 764
 765         /* Clean up the stack. */
 766         assert(stack_size >= call->pop);
 767         stack_size -= call->pop;
 768
 769         if (stack_size > 0) {
 770                 ir_node *mem_proj = NULL;
 771
 772                 foreach_out_edge(low_call, edge) {
 773                         ir_node *irn = get_edge_src_irn(edge);
 774                         if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
 775                                 mem_proj = irn;
 776                                 break;
 777                         }
 778                 }
 779
 780                 if (! mem_proj) {
 781                         mem_proj = new_r_Proj(low_call, mode_M, pn_be_Call_M);
 782                         keep_alive(mem_proj);
 783                 }
 784         }
 785         /* Clean up the stack frame or revert alignment fixes if we allocated it */
 786         if (! no_alloc) {
 787                 curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
 788         }
 789
 790         be_abi_call_free(call);
 791
 792         DEL_ARR_F(states);
 793         DEL_ARR_F(destroyed_regs);
 794
 795         return curr_sp;
 796 }
 797
 798 /**
 799  * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
 800  *
 801  * @param alignment  the minimum stack alignment
 802  * @param size       the node containing the non-aligned size
 803  * @param block      the block where new nodes are allocated on
 804  * @param dbg        debug info for new nodes
 805  *
 806  * @return a node representing the aligned size
 807  */
 808 static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
 809                                   ir_node *block, dbg_info *dbg)
 810 {
 811         if (stack_alignment > 1) {
 812                 ir_mode   *mode;
 813                 ir_tarval *tv;
 814                 ir_node   *mask;
 815                 ir_graph  *irg;
 816
 817                 assert(is_po2(stack_alignment));
 818
 819                 mode = get_irn_mode(size);
 820                 tv   = new_tarval_from_long(stack_alignment-1, mode);
 821                 irg  = get_Block_irg(block);
 822                 mask = new_r_Const(irg, tv);
 823                 size = new_rd_Add(dbg, block, size, mask, mode);
 824
 825                 tv   = new_tarval_from_long(-(long)stack_alignment, mode);
 826                 mask = new_r_Const(irg, tv);
 827                 size = new_rd_And(dbg, block, size, mask, mode);
 828         }
 829         return size;
 830 }
 831 /**
 832  * Adjust an alloca.
 833  * The alloca is transformed into a back end alloca node and connected to the stack nodes.
 834  */
 835 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
 836 {
 837         ir_node          *block     = get_nodes_block(alloc);
 838         ir_graph         *irg       = get_Block_irg(block);
 839         const arch_env_t *arch_env  = be_get_irg_arch_env(irg);
 840         ir_node          *alloc_mem = NULL;
 841         ir_node          *alloc_res = NULL;
 842         ir_type          *type      = get_Alloc_type(alloc);
 843         dbg_info         *dbg;
 844
 845         const ir_edge_t *edge;
 846         ir_node *new_alloc;
 847         ir_node *count;
 848         ir_node *size;
 849         ir_node *ins[2];
 850         unsigned stack_alignment;
 851
 852         /* all non-stack Alloc nodes should already be lowered before the backend */
 853         assert(get_Alloc_where(alloc) == stack_alloc);
 854
 855         foreach_out_edge(alloc, edge) {
 856                 ir_node *irn = get_edge_src_irn(edge);
 857
 858                 assert(is_Proj(irn));
 859                 switch (get_Proj_proj(irn)) {
 860                 case pn_Alloc_M:
 861                         alloc_mem = irn;
 862                         break;
 863                 case pn_Alloc_res:
 864                         alloc_res = irn;
 865                         break;
 866                 default:
 867                         break;
 868                 }
 869         }
 870
 871         /* Beware: currently Alloc nodes without a result might happen,
 872            only escape analysis kills them and this phase runs only for object
 873            oriented source. We kill the Alloc here. */
 874         if (alloc_res == NULL && alloc_mem) {
 875                 exchange(alloc_mem, get_Alloc_mem(alloc));
 876                 return curr_sp;
 877         }
 878
 879         dbg   = get_irn_dbg_info(alloc);
 880         count = get_Alloc_count(alloc);
 881
 882         /* we might need to multiply the count with the element size */
 883         if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
 884                 ir_mode   *mode  = get_irn_mode(count);
 885                 ir_tarval *tv    = new_tarval_from_long(get_type_size_bytes(type),
 886                                                         mode);
 887                 ir_node   *cnst = new_rd_Const(dbg, irg, tv);
 888                 size            = new_rd_Mul(dbg, block, count, cnst, mode);
 889         } else {
 890                 size = count;
 891         }
 892
 893         /* The stack pointer will be modified in an unknown manner.
 894            We cannot omit it. */
 895         env->call->flags.bits.try_omit_fp = 0;
 896
 897         stack_alignment = 1 << arch_env->stack_alignment;
 898         size            = adjust_alloc_size(stack_alignment, size, block, dbg);
 899         new_alloc       = be_new_AddSP(arch_env->sp, block, curr_sp, size);
 900         set_irn_dbg_info(new_alloc, dbg);
 901
 902         if (alloc_mem != NULL) {
 903                 ir_node *addsp_mem;
 904                 ir_node *sync;
 905
 906                 addsp_mem = new_r_Proj(new_alloc, mode_M, pn_be_AddSP_M);
 907
 908                 /* We need to sync the output mem of the AddSP with the input mem
 909                    edge into the alloc node. */
 910                 ins[0] = get_Alloc_mem(alloc);
 911                 ins[1] = addsp_mem;
 912                 sync = new_r_Sync(block, 2, ins);
 913
 914                 exchange(alloc_mem, sync);
 915         }
 916
 917         exchange(alloc, new_alloc);
 918
 919         /* fix projnum of alloca res */
 920         set_Proj_proj(alloc_res, pn_be_AddSP_res);
 921
 922         curr_sp = new_r_Proj(new_alloc,  get_irn_mode(curr_sp), pn_be_AddSP_sp);
 923
 924         return curr_sp;
 925 }
 926
 927 /**
 928  * Adjust a Free.
 929  * The Free is transformed into a back end free node and connected to the stack nodes.
 930  */
 931 static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
 932 {
 933         ir_node          *block    = get_nodes_block(free);
 934         ir_graph         *irg      = get_irn_irg(free);
 935         ir_type          *type     = get_Free_type(free);
 936         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
 937         ir_mode          *sp_mode  = arch_env->sp->reg_class->mode;
 938         dbg_info         *dbg      = get_irn_dbg_info(free);
 939         ir_node  *subsp, *mem, *res, *size, *sync;
 940         ir_node *in[2];
 941         unsigned stack_alignment;
 942
 943         /* all non-stack-alloc Free nodes should already be lowered before the
 944          * backend phase */
 945         assert(get_Free_where(free) == stack_alloc);
 946
 947         /* we might need to multiply the size with the element size */
 948         if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
 949                 ir_tarval *tv   = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
 950                 ir_node   *cnst = new_rd_Const(dbg, irg, tv);
 951                 ir_node   *mul  = new_rd_Mul(dbg, block, get_Free_size(free),
 952                                              cnst, mode_Iu);
 953                 size = mul;
 954         } else {
 955                 size = get_Free_size(free);
 956         }
 957
 958         stack_alignment = 1 << arch_env->stack_alignment;
 959         size            = adjust_alloc_size(stack_alignment, size, block, dbg);
 960
 961         /* The stack pointer will be modified in an unknown manner.
 962            We cannot omit it. */
 963         env->call->flags.bits.try_omit_fp = 0;
 964         subsp = be_new_SubSP(arch_env->sp, block, curr_sp, size);
 965         set_irn_dbg_info(subsp, dbg);
 966
 967         mem = new_r_Proj(subsp, mode_M, pn_be_SubSP_M);
 968         res = new_r_Proj(subsp, sp_mode, pn_be_SubSP_sp);
 969
 970         /* we need to sync the memory */
 971         in[0] = get_Free_mem(free);
 972         in[1] = mem;
 973         sync = new_r_Sync(block, 2, in);
 974
 975         /* and make the AddSP dependent on the former memory */
 976         add_irn_dep(subsp, get_Free_mem(free));
 977
 978         /* kill the free */
 979         exchange(free, sync);
 980         curr_sp = res;
 981
 982         return curr_sp;
 983 }
 984
 985 /**
 986  * Check if a node is somehow data dependent on another one.
 987  * both nodes must be in the same basic block.
 988  * @param n1 The first node.
 989  * @param n2 The second node.
 990  * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
 991  */
 992 static int dependent_on(ir_node *n1, ir_node *n2)
 993 {
 994         assert(get_nodes_block(n1) == get_nodes_block(n2));
 995
 996         return heights_reachable_in_block(ir_heights, n1, n2);
 997 }
 998
 999 static int cmp_call_dependency(const void *c1, const void *c2)
1000 {
1001         ir_node *n1 = *(ir_node **) c1;
1002         ir_node *n2 = *(ir_node **) c2;
1003         unsigned h1, h2;
1004
1005         /*
1006                 Classical qsort() comparison function behavior:
1007                 0  if both elements are equal
1008                 1  if second is "smaller" that first
1009                 -1 if first is "smaller" that second
1010         */
1011         if (dependent_on(n1, n2))
1012                 return -1;
1013
1014         if (dependent_on(n2, n1))
1015                 return 1;
1016
1017         /* The nodes have no depth order, but we need a total order because qsort()
1018          * is not stable.
1019          *
1020          * Additionally, we need to respect transitive dependencies. Consider a
1021          * Call a depending on Call b and an independent Call c.
1022          * We MUST NOT order c > a and b > c. */
1023         h1 = get_irn_height(ir_heights, n1);
1024         h2 = get_irn_height(ir_heights, n2);
1025         if (h1 < h2) return -1;
1026         if (h1 > h2) return  1;
1027         /* Same height, so use a random (but stable) order */
1028         return get_irn_idx(n1) - get_irn_idx(n2);
1029 }
1030
1031 /**
1032  * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
1033  * Clears the irg_is_leaf flag if a Call is detected.
1034  */
1035 static void link_ops_in_block_walker(ir_node *irn, void *data)
1036 {
1037         be_abi_irg_t *env  = (be_abi_irg_t*)data;
1038         unsigned      code = get_irn_opcode(irn);
1039
1040         if (code == iro_Call ||
1041            (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
1042            (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
1043                 ir_node *bl       = get_nodes_block(irn);
1044                 void *save        = get_irn_link(bl);
1045
1046                 if (code == iro_Call)
1047                         env->call->flags.bits.irg_is_leaf = 0;
1048
1049                 set_irn_link(irn, save);
1050                 set_irn_link(bl, irn);
1051         }
1052
1053         if (code == iro_Builtin && get_Builtin_kind(irn) == ir_bk_return_address) {
1054                 ir_node       *param = get_Builtin_param(irn, 0);
1055                 ir_tarval     *tv    = get_Const_tarval(param);
1056                 unsigned long  value = get_tarval_long(tv);
1057                 /* use ebp, so the climbframe algo works... */
1058                 if (value > 0) {
1059                         env->call->flags.bits.try_omit_fp = 0;
1060                 }
1061         }
1062 }
1063
1064 /**
1065  * Block-walker:
1066  * Process all Call/Alloc/Free nodes inside a basic block.
1067  * Note that the link field of the block must contain a linked list of all
1068  * nodes inside the Block. We first order this list according to data dependency
1069  * and that connect the nodes together.
1070  */
1071 static void process_ops_in_block(ir_node *bl, void *data)
1072 {
1073         be_abi_irg_t   *env     = (be_abi_irg_t*)data;
1074         ir_node        *curr_sp = env->init_sp;
1075         ir_node        *irn;
1076         ir_node       **nodes;
1077         int             n;
1078         int             n_nodes;
1079
1080         n_nodes = 0;
1081         for (irn = (ir_node*)get_irn_link(bl); irn != NULL;
1082              irn = (ir_node*)get_irn_link(irn)) {
1083                 ++n_nodes;
1084         }
1085
1086         nodes = ALLOCAN(ir_node*, n_nodes);
1087         for (irn = (ir_node*)get_irn_link(bl), n = 0; irn != NULL;
1088              irn = (ir_node*)get_irn_link(irn), ++n) {
1089                 nodes[n] = irn;
1090         }
1091
1092         /* If there were call nodes in the block. */
1093         if (n > 0) {
1094                 ir_node *keep;
1095                 int i;
1096
1097                 /* order the call nodes according to data dependency */
1098                 qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
1099
1100                 for (i = n_nodes - 1; i >= 0; --i) {
1101                         ir_node *irn = nodes[i];
1102
1103                         DBG((dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1104                         switch (get_irn_opcode(irn)) {
1105                         case iro_Call:
1106                                 if (! be_omit_fp) {
1107                                         /* The stack pointer will be modified due to a call. */
1108                                         env->call->flags.bits.try_omit_fp = 0;
1109                                 }
1110                                 curr_sp = adjust_call(env, irn, curr_sp);
1111                                 break;
1112                         case iro_Alloc:
1113                                 if (get_Alloc_where(irn) == stack_alloc)
1114                                         curr_sp = adjust_alloc(env, irn, curr_sp);
1115                                 break;
1116                         case iro_Free:
1117                                 if (get_Free_where(irn) == stack_alloc)
1118                                         curr_sp = adjust_free(env, irn, curr_sp);
1119                                 break;
1120                         default:
1121                                 panic("invalid call");
1122                         }
1123                 }
1124
1125                 /* Keep the last stack state in the block by tying it to Keep node,
1126                  * the proj from calls is already kept */
1127                 if (curr_sp != env->init_sp &&
1128                     !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1129                         nodes[0] = curr_sp;
1130                         keep     = be_new_Keep(bl, 1, nodes);
1131                         pmap_insert(env->keep_map, bl, keep);
1132                 }
1133         }
1134
1135         set_irn_link(bl, curr_sp);
1136 }
1137
1138 /**
1139  * Adjust all call nodes in the graph to the ABI conventions.
1140  */
1141 static void process_calls(ir_graph *irg)
1142 {
1143         be_abi_irg_t *abi = be_get_irg_abi(irg);
1144
1145         abi->call->flags.bits.irg_is_leaf = 1;
1146         irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, abi);
1147
1148         ir_heights = heights_new(irg);
1149         irg_block_walk_graph(irg, NULL, process_ops_in_block, abi);
1150         heights_free(ir_heights);
1151 }
1152
1153 /**
1154  * Computes the stack argument layout type.
1155  * Changes a possibly allocated value param type by moving
1156  * entities to the stack layout type.
1157  *
1158  * @param call          the current call ABI
1159  * @param method_type   the method type
1160  * @param param_map     an array mapping method arguments to the stack layout
1161  *                      type
1162  *
1163  * @return the stack argument layout type
1164  */
1165 static ir_type *compute_arg_type(ir_graph *irg, be_abi_call_t *call,
1166                                                                  ir_type *method_type, ir_entity ***param_map)
1167 {
1168         struct obstack *obst = be_get_be_obst(irg);
1169         ir_type *frame_type      = get_irg_frame_type(irg);
1170         size_t   n_params        = get_method_n_params(method_type);
1171         size_t   n_frame_members = get_compound_n_members(frame_type);
1172         size_t   f;
1173         int      ofs  = 0;
1174
1175         ir_type *res;
1176         size_t i;
1177         ir_entity **map;
1178
1179         *param_map = map = OALLOCNZ(obst, ir_entity*, n_params);
1180         res = new_type_struct(new_id_from_chars("arg_type", 8));
1181
1182         /* collect existing entities for value_param_types */
1183         for (f = n_frame_members; f > 0; ) {
1184                 ir_entity *entity = get_compound_member(frame_type, --f);
1185                 size_t     num;
1186
1187                 set_entity_link(entity, NULL);
1188                 if (!is_parameter_entity(entity))
1189                         continue;
1190                 num = get_entity_parameter_number(entity);
1191                 assert(num < n_params);
1192                 if (map[num] != NULL)
1193                         panic("multiple entities for parameter %u in %+F found", f, irg);
1194
1195                 if (!get_call_arg(call, 0, num, 1)->on_stack) {
1196                         /* don't move this entity */
1197                         continue;
1198                 }
1199
1200                 map[num] = entity;
1201                 /* move entity to new arg_type */
1202                 set_entity_owner(entity, res);
1203         }
1204
1205         for (i = 0; i < n_params; ++i) {
1206                 be_abi_call_arg_t *arg        = get_call_arg(call, 0, i, 1);
1207                 ir_type           *param_type = get_method_param_type(method_type, i);
1208                 ir_entity         *entity;
1209
1210                 if (!arg->on_stack) {
1211                         continue;
1212                 }
1213                 entity = map[i];
1214                 if (entity == NULL) {
1215                         /* create a new entity */
1216                         entity = new_parameter_entity(res, i, param_type);
1217                 }
1218                 ofs += arg->space_before;
1219                 ofs = round_up2(ofs, arg->alignment);
1220                 set_entity_offset(entity, ofs);
1221                 ofs += arg->space_after;
1222                 ofs += get_type_size_bytes(param_type);
1223                 arg->stack_ent = entity;
1224         }
1225         set_type_size_bytes(res, ofs);
1226         set_type_state(res, layout_fixed);
1227         return res;
1228 }
1229
1230 typedef struct {
1231         const arch_register_t *reg;
1232         ir_node *irn;
1233 } reg_node_map_t;
1234
1235 static int cmp_regs(const void *a, const void *b)
1236 {
1237         const reg_node_map_t *p = (const reg_node_map_t*)a;
1238         const reg_node_map_t *q = (const reg_node_map_t*)b;
1239
1240         if (p->reg->reg_class == q->reg->reg_class)
1241                 return p->reg->index - q->reg->index;
1242         else
1243                 return p->reg->reg_class < q->reg->reg_class ? -1 : +1;
1244 }
1245
1246 static void reg_map_to_arr(reg_node_map_t *res, pmap *reg_map)
1247 {
1248         pmap_entry *ent;
1249         size_t n = pmap_count(reg_map);
1250         size_t i = 0;
1251
1252         foreach_pmap(reg_map, ent) {
1253                 res[i].reg = (const arch_register_t*)ent->key;
1254                 res[i].irn = (ir_node*)ent->value;
1255                 i++;
1256         }
1257
1258         qsort(res, n, sizeof(res[0]), cmp_regs);
1259 }
1260
1261 /**
1262  * Creates a be_Return for a Return node.
1263  *
1264  * @param @env  the abi environment
1265  * @param irn   the Return node or NULL if there was none
1266  * @param bl    the block where the be_Retun should be placed
1267  * @param mem   the current memory
1268  * @param n_res number of return results
1269  */
1270 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1271                 ir_node *mem, int n_res)
1272 {
1273         be_abi_call_t    *call     = env->call;
1274         ir_graph         *irg      = get_Block_irg(bl);
1275         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1276         dbg_info *dbgi;
1277         pmap *reg_map  = pmap_create();
1278         ir_node *keep  = (ir_node*)pmap_get(env->keep_map, bl);
1279         size_t in_max;
1280         ir_node *ret;
1281         int i, n;
1282         unsigned pop;
1283         ir_node **in;
1284         ir_node *stack;
1285         const arch_register_t **regs;
1286         pmap_entry *ent;
1287
1288         /*
1289                 get the valid stack node in this block.
1290                 If we had a call in that block there is a Keep constructed by process_calls()
1291                 which points to the last stack modification in that block. we'll use
1292                 it then. Else we use the stack from the start block and let
1293                 the ssa construction fix the usage.
1294         */
1295         stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1296         if (keep) {
1297                 stack = get_irn_n(keep, 0);
1298                 kill_node(keep);
1299                 remove_End_keepalive(get_irg_end(irg), keep);
1300         }
1301
1302         /* Insert results for Return into the register map. */
1303         for (i = 0; i < n_res; ++i) {
1304                 ir_node *res           = get_Return_res(irn, i);
1305                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1306                 assert(arg->in_reg && "return value must be passed in register");
1307                 pmap_insert(reg_map, (void *) arg->reg, res);
1308         }
1309
1310         /* Add uses of the callee save registers. */
1311         foreach_pmap(env->regs, ent) {
1312                 const arch_register_t *reg = (const arch_register_t*)ent->key;
1313                 if ((reg->type & arch_register_type_ignore) || arch_register_is_callee_save(arch_env, reg))
1314                         pmap_insert(reg_map, ent->key, ent->value);
1315         }
1316
1317         be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1318
1319         /*
1320                 Maximum size of the in array for Return nodes is
1321                 return args + callee save/ignore registers + memory + stack pointer
1322         */
1323         in_max = pmap_count(reg_map) + n_res + 2;
1324
1325         in   = ALLOCAN(ir_node*,               in_max);
1326         regs = ALLOCAN(arch_register_t const*, in_max);
1327
1328         in[0]   = mem;
1329         in[1]   = be_abi_reg_map_get(reg_map, arch_env->sp);
1330         regs[0] = NULL;
1331         regs[1] = arch_env->sp;
1332         n       = 2;
1333
1334         /* clear SP entry, since it has already been grown. */
1335         pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1336         for (i = 0; i < n_res; ++i) {
1337                 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1338
1339                 in[n]     = be_abi_reg_map_get(reg_map, arg->reg);
1340                 regs[n++] = arg->reg;
1341
1342                 /* Clear the map entry to mark the register as processed. */
1343                 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1344         }
1345
1346         /* grow the rest of the stuff. */
1347         foreach_pmap(reg_map, ent) {
1348                 if (ent->value) {
1349                         in[n]     = (ir_node*)ent->value;
1350                         regs[n++] = (const arch_register_t*)ent->key;
1351                 }
1352         }
1353
1354         /* The in array for the new back end return is now ready. */
1355         if (irn != NULL) {
1356                 dbgi = get_irn_dbg_info(irn);
1357         } else {
1358                 dbgi = NULL;
1359         }
1360         /* we have to pop the shadow parameter in in case of struct returns */
1361         pop = call->pop;
1362         ret = be_new_Return(dbgi, irg, bl, n_res, pop, n, in);
1363
1364         /* Set the register classes of the return's parameter accordingly. */
1365         for (i = 0; i < n; ++i) {
1366                 if (regs[i] == NULL)
1367                         continue;
1368
1369                 be_set_constr_single_reg_in(ret, i, regs[i], arch_register_req_type_none);
1370         }
1371
1372         /* Free the space of the Epilog's in array and the register <-> proj map. */
1373         pmap_destroy(reg_map);
1374
1375         return ret;
1376 }
1377
1378 typedef struct lower_frame_sels_env_t {
1379         ir_node      *frame;                     /**< the current frame */
1380         const arch_register_class_t *sp_class;   /**< register class of the stack pointer */
1381         const arch_register_class_t *link_class; /**< register class of the link pointer */
1382         ir_type      *frame_tp;                  /**< the frame type */
1383         int          static_link_pos;            /**< argument number of the hidden static link */
1384 } lower_frame_sels_env_t;
1385
1386 /**
1387  * Walker: Replaces Sels of frame type and
1388  * value param type entities by FrameAddress.
1389  * Links all used entities.
1390  */
1391 static void lower_frame_sels_walker(ir_node *irn, void *data)
1392 {
1393         lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1394
1395         if (is_Sel(irn)) {
1396                 ir_node *ptr = get_Sel_ptr(irn);
1397
1398                 if (ptr == ctx->frame) {
1399                         ir_entity    *ent = get_Sel_entity(irn);
1400                         ir_node      *bl  = get_nodes_block(irn);
1401                         ir_node      *nw;
1402
1403                         nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1404                         exchange(irn, nw);
1405                 }
1406         }
1407 }
1408
1409 /**
1410  * The start block has no jump, instead it has an initial exec Proj.
1411  * The backend wants to handle all blocks the same way, so we replace
1412  * the out cfg edge with a real jump.
1413  */
1414 static void fix_start_block(ir_graph *irg)
1415 {
1416         ir_node *initial_X   = get_irg_initial_exec(irg);
1417         ir_node *start_block = get_irg_start_block(irg);
1418         ir_node *jmp         = new_r_Jmp(start_block);
1419
1420         assert(is_Proj(initial_X));
1421         exchange(initial_X, jmp);
1422         set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1423
1424         /* merge start block with successor if possible */
1425         {
1426                 const ir_edge_t *edge;
1427                 foreach_out_edge(jmp, edge) {
1428                         ir_node *succ = get_edge_src_irn(edge);
1429                         if (!is_Block(succ))
1430                                 continue;
1431
1432                         if (get_irn_arity(succ) == 1) {
1433                                 exchange(succ, start_block);
1434                         }
1435                         break;
1436                 }
1437         }
1438 }
1439
1440 /**
1441  * Modify the irg itself and the frame type.
1442  */
1443 static void modify_irg(ir_graph *irg)
1444 {
1445         be_abi_irg_t          *env          = be_get_irg_abi(irg);
1446         be_abi_call_t         *call         = env->call;
1447         const arch_env_t      *arch_env     = be_get_irg_arch_env(irg);
1448         const arch_register_t *sp           = arch_env->sp;
1449         ir_type               *method_type  = get_entity_type(get_irg_entity(irg));
1450         be_irg_t              *birg         = be_birg_from_irg(irg);
1451         struct obstack        *obst         = be_get_be_obst(irg);
1452         be_stack_layout_t     *stack_layout = be_get_irg_stack_layout(irg);
1453         ir_node *end;
1454         ir_node *old_mem;
1455         ir_node *new_mem_proj;
1456         ir_node *mem;
1457
1458         int n_params;
1459         int i, n;
1460         unsigned j;
1461         unsigned frame_size;
1462
1463         reg_node_map_t *rm;
1464         const arch_register_t *fp_reg;
1465         ir_node *frame_pointer;
1466         ir_node *start_bl;
1467         ir_node **args;
1468         ir_node *arg_tuple;
1469         const ir_edge_t *edge;
1470         ir_type *arg_type, *bet_type;
1471         lower_frame_sels_env_t ctx;
1472         ir_entity **param_map;
1473
1474         DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1475
1476         old_mem = get_irg_initial_mem(irg);
1477
1478         irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1479
1480         arg_type = compute_arg_type(irg, call, method_type, &param_map);
1481
1482         /* Convert the Sel nodes in the irg to frame addr nodes: */
1483         ctx.frame            = get_irg_frame(irg);
1484         ctx.sp_class         = arch_env->sp->reg_class;
1485         ctx.link_class       = arch_env->link_class;
1486         ctx.frame_tp         = get_irg_frame_type(irg);
1487
1488         /* layout the stackframe now */
1489         if (get_type_state(ctx.frame_tp) == layout_undefined) {
1490                 default_layout_compound_type(ctx.frame_tp);
1491         }
1492
1493         /* align stackframe to 4 byte */
1494         frame_size = get_type_size_bytes(ctx.frame_tp);
1495         if (frame_size % 4 != 0) {
1496                 set_type_size_bytes(ctx.frame_tp, frame_size + 4 - (frame_size % 4));
1497         }
1498
1499         env->regs  = pmap_create();
1500
1501         n_params = get_method_n_params(method_type);
1502         args     = OALLOCNZ(obst, ir_node*, n_params);
1503
1504         be_add_parameter_entity_stores(irg);
1505
1506         irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1507
1508         irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1509
1510         /* Fill the argument vector */
1511         arg_tuple = get_irg_args(irg);
1512         foreach_out_edge(arg_tuple, edge) {
1513                 ir_node *irn = get_edge_src_irn(edge);
1514                 if (! is_Anchor(irn)) {
1515                         int nr       = get_Proj_proj(irn);
1516                         args[nr]     = irn;
1517                         DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1518                 }
1519         }
1520
1521         stack_layout->sp_relative = call->flags.bits.try_omit_fp;
1522         bet_type = call->cb->get_between_type(irg);
1523         stack_frame_init(stack_layout, arg_type, bet_type,
1524                          get_irg_frame_type(irg), param_map);
1525
1526         /* Count the register params and add them to the number of Projs for the RegParams node */
1527         for (i = 0; i < n_params; ++i) {
1528                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1529                 if (arg->in_reg && args[i]) {
1530                         assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1531                         assert(i == get_Proj_proj(args[i]));
1532
1533                         /* For now, associate the register with the old Proj from Start representing that argument. */
1534                         pmap_insert(env->regs, (void *) arg->reg, args[i]);
1535                         DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1536                 }
1537         }
1538
1539         /* Collect all callee-save registers */
1540         for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1541                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1542                 for (j = 0; j < cls->n_regs; ++j) {
1543                         const arch_register_t *reg = &cls->regs[j];
1544                         if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1545                                 pmap_insert(env->regs, (void *) reg, NULL);
1546                         }
1547                 }
1548         }
1549
1550         fp_reg = call->flags.bits.try_omit_fp ? arch_env->sp : arch_env->bp;
1551         rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1552
1553         /* handle start block here (place a jump in the block) */
1554         fix_start_block(irg);
1555
1556         pmap_insert(env->regs, (void *) sp, NULL);
1557         pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1558         start_bl   = get_irg_start_block(irg);
1559         env->start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1560         set_irg_start(irg, env->start);
1561
1562         /*
1563          * make proj nodes for the callee save registers.
1564          * memorize them, since Return nodes get those as inputs.
1565          *
1566          * Note, that if a register corresponds to an argument, the regs map
1567          * contains the old Proj from start for that argument.
1568          */
1569         rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1570         reg_map_to_arr(rm, env->regs);
1571         for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1572                 const arch_register_t    *reg      = rm[i].reg;
1573                 ir_mode                  *mode     = reg->reg_class->mode;
1574                 long                      nr       = i;
1575                 arch_register_req_type_t  add_type = arch_register_req_type_none;
1576                 ir_node                  *proj;
1577
1578                 if (reg == sp)
1579                         add_type |= arch_register_req_type_produces_sp;
1580                 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1581                         add_type |= arch_register_req_type_ignore;
1582                 }
1583
1584                 assert(nr >= 0);
1585                 proj = new_r_Proj(env->start, mode, nr + 1);
1586                 pmap_insert(env->regs, (void *) reg, proj);
1587                 be_set_constr_single_reg_out(env->start, nr + 1, reg, add_type);
1588                 arch_set_irn_register(proj, reg);
1589
1590                 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1591         }
1592
1593         /* create a new initial memory proj */
1594         assert(is_Proj(old_mem));
1595         arch_set_irn_register_req_out(env->start, 0, arch_no_register_req);
1596         new_mem_proj = new_r_Proj(env->start, mode_M, 0);
1597         mem = new_mem_proj;
1598         set_irg_initial_mem(irg, mem);
1599
1600         env->init_sp = be_abi_reg_map_get(env->regs, sp);
1601
1602         /* set new frame_pointer */
1603         frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1604         set_irg_frame(irg, frame_pointer);
1605
1606         /* rewire old mem users to new mem */
1607         exchange(old_mem, mem);
1608
1609         /* keep the mem (for functions with an endless loop = no return) */
1610         keep_alive(mem);
1611
1612         set_irg_initial_mem(irg, mem);
1613
1614         /* Now, introduce stack param nodes for all parameters passed on the stack */
1615         for (i = 0; i < n_params; ++i) {
1616                 ir_node *arg_proj = args[i];
1617                 ir_node *repl     = NULL;
1618
1619                 if (arg_proj != NULL) {
1620                         be_abi_call_arg_t *arg;
1621                         ir_type *param_type;
1622                         int     nr = get_Proj_proj(arg_proj);
1623                         ir_mode *mode;
1624
1625                         nr         = MIN(nr, n_params);
1626                         arg        = get_call_arg(call, 0, nr, 1);
1627                         param_type = get_method_param_type(method_type, nr);
1628
1629                         if (arg->in_reg) {
1630                                 repl = (ir_node*)pmap_get(env->regs, arg->reg);
1631                         } else if (arg->on_stack) {
1632                                 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1633
1634                                 /* For atomic parameters which are actually used, we create a Load node. */
1635                                 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1636                                         ir_mode *mode      = get_type_mode(param_type);
1637                                         ir_mode *load_mode = arg->load_mode;
1638                                         ir_node *nomem     = get_irg_no_mem(irg);
1639
1640                                         ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1641                                         repl = new_r_Proj(load, load_mode, pn_Load_res);
1642
1643                                         if (mode != load_mode) {
1644                                                 repl = new_r_Conv(start_bl, repl, mode);
1645                                         }
1646                                 } else {
1647                                         /* The stack parameter is not primitive (it is a struct or array),
1648                                          * we thus will create a node representing the parameter's address
1649                                          * on the stack. */
1650                                         repl = addr;
1651                                 }
1652                         }
1653
1654                         assert(repl != NULL);
1655
1656                         /* Beware: the mode of the register parameters is always the mode of the register class
1657                            which may be wrong. Add Conv's then. */
1658                         mode = get_irn_mode(args[i]);
1659                         if (mode != get_irn_mode(repl)) {
1660                                 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1661                         }
1662                         exchange(args[i], repl);
1663                 }
1664         }
1665
1666         /* the arg proj is not needed anymore now and should be only used by the anchor */
1667         assert(get_irn_n_edges(arg_tuple) == 1);
1668         kill_node(arg_tuple);
1669         set_irg_args(irg, new_r_Bad(irg, mode_T));
1670
1671         /* All Return nodes hang on the End node, so look for them there. */
1672         end = get_irg_end_block(irg);
1673         for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1674                 ir_node *irn = get_Block_cfgpred(end, i);
1675
1676                 if (is_Return(irn)) {
1677                         ir_node *blk = get_nodes_block(irn);
1678                         ir_node *mem = get_Return_mem(irn);
1679                         ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1680                         exchange(irn, ret);
1681                 }
1682         }
1683
1684         /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1685            the code is dead and will never be executed. */
1686 }
1687
1688 /** Fix the state inputs of calls that still hang on unknowns */
1689 static void fix_call_state_inputs(ir_graph *irg)
1690 {
1691         be_abi_irg_t     *env      = be_get_irg_abi(irg);
1692         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1693         int i, n, n_states;
1694         arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1695
1696         /* Collect caller save registers */
1697         n = arch_env->n_register_classes;
1698         for (i = 0; i < n; ++i) {
1699                 unsigned j;
1700                 const arch_register_class_t *cls = &arch_env->register_classes[i];
1701                 for (j = 0; j < cls->n_regs; ++j) {
1702                         const arch_register_t *reg = arch_register_for_index(cls, j);
1703                         if (reg->type & arch_register_type_state) {
1704                                 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1705                         }
1706                 }
1707         }
1708
1709         n = ARR_LEN(env->calls);
1710         n_states = ARR_LEN(stateregs);
1711         for (i = 0; i < n; ++i) {
1712                 int s, arity;
1713                 ir_node *call = env->calls[i];
1714
1715                 arity = get_irn_arity(call);
1716
1717                 /* the state reg inputs are the last n inputs of the calls */
1718                 for (s = 0; s < n_states; ++s) {
1719                         int inp = arity - n_states + s;
1720                         const arch_register_t *reg = stateregs[s];
1721                         ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1722
1723                         set_irn_n(call, inp, regnode);
1724                 }
1725         }
1726
1727         DEL_ARR_F(stateregs);
1728 }
1729
1730 /**
1731  * Create a trampoline entity for the given method.
1732  */
1733 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1734 {
1735         ir_type   *type   = get_entity_type(method);
1736         ident     *old_id = get_entity_ld_ident(method);
1737         ident     *id     = id_mangle3("", old_id, "$stub");
1738         ir_type   *parent = be->pic_trampolines_type;
1739         ir_entity *ent    = new_entity(parent, old_id, type);
1740         set_entity_ld_ident(ent, id);
1741         set_entity_visibility(ent, ir_visibility_private);
1742
1743         return ent;
1744 }
1745
1746 /**
1747  * Returns the trampoline entity for the given method.
1748  */
1749 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1750 {
1751         ir_entity *result = (ir_entity*)pmap_get(env->ent_trampoline_map, method);
1752         if (result == NULL) {
1753                 result = create_trampoline(env, method);
1754                 pmap_insert(env->ent_trampoline_map, method, result);
1755         }
1756
1757         return result;
1758 }
1759
1760 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1761 {
1762         ident     *old_id = get_entity_ld_ident(entity);
1763         ident     *id     = id_mangle3("", old_id, "$non_lazy_ptr");
1764         ir_type   *e_type = get_entity_type(entity);
1765         ir_type   *type   = new_type_pointer(e_type);
1766         ir_type   *parent = be->pic_symbols_type;
1767         ir_entity *ent    = new_entity(parent, old_id, type);
1768         set_entity_ld_ident(ent, id);
1769         set_entity_visibility(ent, ir_visibility_private);
1770
1771         return ent;
1772 }
1773
1774 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1775 {
1776         ir_entity *result = (ir_entity*)pmap_get(env->ent_pic_symbol_map, entity);
1777         if (result == NULL) {
1778                 result = create_pic_symbol(env, entity);
1779                 pmap_insert(env->ent_pic_symbol_map, entity, result);
1780         }
1781
1782         return result;
1783 }
1784
1785
1786
1787 /**
1788  * Returns non-zero if a given entity can be accessed using a relative address.
1789  */
1790 static int can_address_relative(ir_entity *entity)
1791 {
1792         return get_entity_visibility(entity) != ir_visibility_external
1793                 && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1794 }
1795
1796 static ir_node *get_pic_base(ir_graph *irg)
1797 {
1798         const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1799         if (arch_env->impl->get_pic_base == NULL)
1800                 return NULL;
1801         return arch_env->impl->get_pic_base(irg);
1802 }
1803
1804 /** patches SymConsts to work in position independent code */
1805 static void fix_pic_symconsts(ir_node *node, void *data)
1806 {
1807         ir_graph         *irg = get_irn_irg(node);
1808         be_main_env_t    *be  = be_get_irg_main_env(irg);
1809         ir_node          *pic_base;
1810         ir_node          *add;
1811         ir_node          *block;
1812         ir_mode          *mode;
1813         ir_node          *load;
1814         ir_node          *load_res;
1815         int               arity, i;
1816         (void) data;
1817
1818         arity = get_irn_arity(node);
1819         for (i = 0; i < arity; ++i) {
1820                 dbg_info  *dbgi;
1821                 ir_node   *pred = get_irn_n(node, i);
1822                 ir_entity *entity;
1823                 ir_entity *pic_symbol;
1824                 ir_node   *pic_symconst;
1825
1826                 if (!is_SymConst(pred))
1827                         continue;
1828
1829                 entity = get_SymConst_entity(pred);
1830                 block  = get_nodes_block(pred);
1831
1832                 /* calls can jump to relative addresses, so we can directly jump to
1833                    the (relatively) known call address or the trampoline */
1834                 if (i == 1 && is_Call(node)) {
1835                         ir_entity *trampoline;
1836                         ir_node   *trampoline_const;
1837
1838                         if (can_address_relative(entity))
1839                                 continue;
1840
1841                         dbgi             = get_irn_dbg_info(pred);
1842                         trampoline       = get_trampoline(be, entity);
1843                         trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1844                                                                     trampoline);
1845                         set_irn_n(node, i, trampoline_const);
1846                         continue;
1847                 }
1848
1849                 /* everything else is accessed relative to EIP */
1850                 mode     = get_irn_mode(pred);
1851                 pic_base = get_pic_base(irg);
1852
1853                 /* all ok now for locally constructed stuff */
1854                 if (can_address_relative(entity)) {
1855                         ir_node *add = new_r_Add(block, pic_base, pred, mode);
1856
1857                         /* make sure the walker doesn't visit this add again */
1858                         mark_irn_visited(add);
1859                         set_irn_n(node, i, add);
1860                         continue;
1861                 }
1862
1863                 /* get entry from pic symbol segment */
1864                 dbgi         = get_irn_dbg_info(pred);
1865                 pic_symbol   = get_pic_symbol(be, entity);
1866                 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1867                                                         pic_symbol);
1868                 add = new_r_Add(block, pic_base, pic_symconst, mode);
1869                 mark_irn_visited(add);
1870
1871                 /* we need an extra indirection for global data outside our current
1872                    module. The loads are always safe and can therefore float
1873                    and need no memory input */
1874                 load     = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1875                 load_res = new_r_Proj(load, mode, pn_Load_res);
1876
1877                 set_irn_n(node, i, load_res);
1878         }
1879 }
1880
1881 void be_abi_introduce(ir_graph *irg)
1882 {
1883         be_abi_irg_t     *env         = XMALLOCZ(be_abi_irg_t);
1884         ir_node          *old_frame   = get_irg_frame(irg);
1885         be_options_t     *options     = be_get_irg_options(irg);
1886         const arch_env_t *arch_env    = be_get_irg_arch_env(irg);
1887         ir_entity        *entity      = get_irg_entity(irg);
1888         ir_type          *method_type = get_entity_type(entity);
1889         be_irg_t         *birg        = be_birg_from_irg(irg);
1890         struct obstack   *obst        = &birg->obst;
1891         ir_node          *dummy       = new_r_Dummy(irg,
1892                                                     arch_env->sp->reg_class->mode);
1893         unsigned          r;
1894
1895         /* determine allocatable registers */
1896         assert(birg->allocatable_regs == NULL);
1897         birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1898         for (r = 0; r < arch_env->n_registers; ++r) {
1899                 const arch_register_t *reg = &arch_env->registers[r];
1900                 if ( !(reg->type & arch_register_type_ignore)) {
1901                         rbitset_set(birg->allocatable_regs, r);
1902                 }
1903         }
1904
1905         /* break here if backend provides a custom API.
1906          * Note: we shouldn't have to setup any be_abi_irg_t* stuff at all,
1907          * but need more cleanup to make this work
1908          */
1909         be_set_irg_abi(irg, env);
1910
1911         be_omit_fp      = options->omit_fp;
1912
1913         env->keep_map     = pmap_create();
1914         env->call         = be_abi_call_new(arch_env->sp->reg_class);
1915         arch_env_get_call_abi(arch_env, method_type, env->call);
1916
1917         env->init_sp = dummy;
1918         env->calls   = NEW_ARR_F(ir_node*, 0);
1919
1920         edges_assure(irg);
1921
1922         if (options->pic) {
1923                 irg_walk_graph(irg, fix_pic_symconsts, NULL, env);
1924         }
1925
1926         /* Lower all call nodes in the IRG. */
1927         process_calls(irg);
1928
1929         /* Process the IRG */
1930         modify_irg(irg);
1931
1932         /* fix call inputs for state registers */
1933         fix_call_state_inputs(irg);
1934
1935         /* We don't need the keep map anymore. */
1936         pmap_destroy(env->keep_map);
1937         env->keep_map = NULL;
1938
1939         /* calls array is not needed anymore */
1940         DEL_ARR_F(env->calls);
1941         env->calls = NULL;
1942
1943         /* reroute the stack origin of the calls to the true stack origin. */
1944         exchange(dummy, env->init_sp);
1945         exchange(old_frame, get_irg_frame(irg));
1946
1947         pmap_destroy(env->regs);
1948         env->regs = NULL;
1949 }
1950
1951 void be_abi_free(ir_graph *irg)
1952 {
1953         be_abi_irg_t *env = be_get_irg_abi(irg);
1954
1955         if (env->call != NULL)
1956                 be_abi_call_free(env->call);
1957         assert(env->regs == NULL);
1958         free(env);
1959
1960         be_set_irg_abi(irg, NULL);
1961 }
1962
1963 void be_put_allocatable_regs(const ir_graph *irg,
1964                              const arch_register_class_t *cls, bitset_t *bs)
1965 {
1966         be_irg_t *birg             = be_birg_from_irg(irg);
1967         unsigned *allocatable_regs = birg->allocatable_regs;
1968         unsigned  i;
1969
1970         assert(bitset_size(bs) == cls->n_regs);
1971         bitset_clear_all(bs);
1972         for (i = 0; i < cls->n_regs; ++i) {
1973                 const arch_register_t *reg = &cls->regs[i];
1974                 if (rbitset_is_set(allocatable_regs, reg->global_index))
1975                         bitset_set(bs, i);
1976         }
1977 }
1978
1979 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1980                                    const arch_register_class_t *cls)
1981 {
1982         bitset_t *bs = bitset_alloca(cls->n_regs);
1983         be_put_allocatable_regs(irg, cls, bs);
1984         return bitset_popcount(bs);
1985 }
1986
1987 void be_set_allocatable_regs(const ir_graph *irg,
1988                              const arch_register_class_t *cls,
1989                              unsigned *raw_bitset)
1990 {
1991         be_irg_t *birg             = be_birg_from_irg(irg);
1992         unsigned *allocatable_regs = birg->allocatable_regs;
1993         unsigned  i;
1994
1995         rbitset_clear_all(raw_bitset, cls->n_regs);
1996         for (i = 0; i < cls->n_regs; ++i) {
1997                 const arch_register_t *reg = &cls->regs[i];
1998                 if (rbitset_is_set(allocatable_regs, reg->global_index))
1999                         rbitset_set(raw_bitset, i);
2000         }
2001 }
2002
2003 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
2004 void be_init_abi(void)
2005 {
2006         FIRM_DBG_REGISTER(dbg, "firm.be.abi");
2007 }