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

   1 /**
   2  * ABI lowering.
   3  *
   4  *
   5  *
   6  */
   7
   8 #include "firm_config.h"
   9 #include "obst.h"
  10
  11 #include "type.h"
  12
  13 #include "irgraph_t.h"
  14 #include "irnode_t.h"
  15 #include "ircons_t.h"
  16 #include "iredges_t.h"
  17 #include "irgmod.h"
  18 #include "irgwalk.h"
  19
  20 #include "be.h"
  21 #include "beabi.h"
  22 #include "bearch.h"
  23 #include "benode_t.h"
  24
  25 #define MAX(x, y) ((x) > (y) ? (x) : (y))
  26 #define MIN(x, y) ((x) < (y) ? (x) : (y))
  27
  28 typedef struct _be_abi_call_arg_t {
  29         unsigned is_res : 1;
  30         unsigned in_reg : 1;
  31
  32         int pos;
  33         const arch_register_t *reg;
  34 } be_abi_call_arg_t;
  35
  36 struct _be_abi_call_t {
  37         be_abi_call_flags_t flags;
  38         set *params;
  39 };
  40
  41 struct _be_abi_irg_t {
  42         struct obstack      obst;
  43         be_irg_t            *birg;
  44         ir_node             *init_sp;      /**< The node representing the stack pointer
  45                                                                              at the start of the function. */
  46
  47         pset                *stack_ops;    /**< Contains all nodes modifying the stack pointer. */
  48         pset                *ignore_regs;  /**< Contains all registers which shall be ignored
  49                                                                              during register allocation. */
  50
  51         unsigned omit_framepointer: 1;     /**< If one, the frame(base-)pointer can be used
  52                                                                              as an ordinary register. */
  53 };
  54
  55 static int cmp_call_arg(const void *a, const void *b, size_t n)
  56 {
  57         const be_abi_call_arg_t *p = a, *q = b;
  58         return !(p->is_res == q->is_res && p->pos == q->pos);
  59 }
  60
  61 static be_abi_call_arg_t *get_or_set_call_arg(be_abi_call_t *call, int is_res, int pos, int do_insert)
  62 {
  63         be_abi_call_arg_t arg;
  64         unsigned hash;
  65
  66         arg.is_res = is_res;
  67         arg.pos    = pos;
  68
  69         hash = is_res * 100 + pos;
  70
  71         return do_insert
  72                 ? set_insert(call->params, &arg, sizeof(arg), hash)
  73                 : set_find(call->params, &arg, sizeof(arg), hash);
  74 }
  75
  76 static INLINE be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
  77 {
  78         return get_or_set_call_arg(call, is_res, pos, 0);
  79 }
  80
  81 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags)
  82 {
  83         call->flags = flags;
  84 }
  85
  86 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos)
  87 {
  88         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
  89 }
  90
  91 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
  92 {
  93         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
  94         arg->reg = reg;
  95 }
  96
  97 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
  98 {
  99         be_abi_call_arg_t *arg = get_or_set_call_arg(call, 1, arg_pos, 1);
 100         arg->reg = reg;
 101 }
 102
 103 be_abi_call_t *be_abi_call_new(void)
 104 {
 105         be_abi_call_t *call = malloc(sizeof(call[0]));
 106         call->flags  = BE_ABI_NONE;
 107         call->params = new_set(cmp_call_arg, 16);
 108         return call;
 109 }
 110
 111 void be_abi_call_free(be_abi_call_t *call)
 112 {
 113         del_set(call->params);
 114         free(call);
 115 }
 116
 117 static INLINE int is_on_stack(be_abi_call_t *call, int pos)
 118 {
 119         be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
 120         return arg && !arg->in_reg;
 121 }
 122
 123 static void adjust_call(be_abi_irg_t *env, ir_node *irn)
 124 {
 125         ir_graph *irg             = env->birg->irg;
 126         const arch_isa_t *isa     = env->birg->main_env->arch_env->isa;
 127         be_abi_call_t *call       = be_abi_call_new();
 128         ir_type *mt               = get_Call_type(irn);
 129         int n_params              = get_method_n_params(mt);
 130         ir_node *curr_sp          = get_irg_frame(irg);
 131         ir_node *curr_mem         = get_Call_mem(irn);
 132         ir_node *bl               = get_nodes_block(irn);
 133         pset *results             = pset_new_ptr(8);
 134         pset *caller_save         = pset_new_ptr(8);
 135         int stack_size            = 0;
 136         int stack_dir             = arch_isa_stack_dir(isa);
 137         const arch_register_t *sp = arch_isa_sp(isa);
 138         ir_mode *mach_mode        = sp->reg_class->mode;
 139         struct obstack *obst      = &env->obst;
 140
 141         ir_node *res_proj = NULL;
 142         int curr_res_proj = -1;
 143         int n_low_args    = 0;
 144         int n_pos         = 0;
 145
 146         ir_node *low_call;
 147         ir_node **in;
 148         ir_node *sp_proj;
 149         const ir_edge_t *edge;
 150         int *low_args;
 151         int *pos;
 152         int i, n;
 153
 154         /* Let the isa fill out the abi description for that call node. */
 155         arch_isa_get_call_abi(isa, mt, call);
 156
 157         /* Insert code to put the stack arguments on the stack. */
 158         for(i = get_irn_arity(irn); i >= 0; --i) {
 159                 if(is_on_stack(call, i)) {
 160                         stack_size += get_type_size_bytes(get_method_param_type(mt, i));
 161                         obstack_int_grow(obst, i);
 162                         n_pos++;
 163                 }
 164         }
 165         pos = obstack_finish(obst);
 166
 167         /* Collect all arguments which are passed in registers. */
 168         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 169                 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 170                 if(arg && arg->in_reg) {
 171                         obstack_int_grow(obst, i);
 172                         n_low_args++;
 173                 }
 174         }
 175         low_args = obstack_finish(obst);
 176
 177         /* If there are some parameters shich shall be passed on the stack. */
 178         if(n_pos > 0) {
 179                 int curr_ofs      = 0;
 180                 int do_seq        = (call->flags & BE_ABI_USE_PUSH);
 181
 182                 /* Reverse list of stack parameters if call arguments are from left to right */
 183                 if(call->flags & BE_ABI_LEFT_TO_RIGHT) {
 184                         for(i = 0; i < n_pos / 2; ++i) {
 185                                 int other  = n_pos - i - 1;
 186                                 int tmp    = pos[i];
 187                                 pos[i]     = pos[other];
 188                                 pos[other] = tmp;
 189                         }
 190                 }
 191
 192                 /*
 193                  * If the stack is decreasing and we do not want to store sequentially,
 194                  * we allocate as much space on the stack all parameters need, by
 195                  * moving the stack pointer along the stack's direction.
 196                  */
 197                 if(stack_dir < 0 && !do_seq) {
 198                         curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, stack_size, be_stack_dir_along);
 199                         pset_insert_ptr(env->stack_ops, curr_sp);
 200                 }
 201
 202                 for(i = 0; i < n_pos; ++i) {
 203                         int p            = pos[i];
 204                         ir_node *param   = get_irn_n(irn, p);
 205                         ir_node *addr    = curr_sp;
 206                         ir_node *mem     = NULL;
 207                         type *param_type = get_method_param_type(mt, p);
 208                         int param_size   = get_type_size_bytes(param_type);
 209
 210                         /* Make the expression to compute the argument's offset. */
 211                         if(curr_ofs > 0) {
 212                                 addr = new_r_Const_long(irg, bl, mach_mode, curr_ofs);
 213                                 addr = new_r_Add(irg, bl, curr_sp, addr, mach_mode);
 214                         }
 215
 216                         /* Insert a store for primitive arguments. */
 217                         if(is_Primitive_type(param_type)) {
 218                                 mem = new_r_Store(irg, bl, curr_mem, addr, param);
 219                                 mem = new_r_Proj(irg, bl, mem, mode_M, pn_Store_M);
 220                         }
 221
 222                         /* Make a memcopy for compound arguments. */
 223                         else {
 224                                 assert(mode_is_reference(get_irn_mode(param)));
 225                                 mem = new_r_CopyB(irg, bl, curr_mem, addr, param, param_type);
 226                                 mem = new_r_Proj(irg, bl, mem, mode_M, pn_CopyB_M_regular);
 227                         }
 228
 229                         obstack_ptr_grow(obst, mem);
 230
 231                         curr_ofs += param_size;
 232
 233                         /*
 234                         * If we wanted to build the arguments sequentially,
 235                         * the stack pointer for the next must be incremented,
 236                         * and the memory value propagated.
 237                         */
 238                         if(do_seq) {
 239                                 curr_ofs = 0;
 240                                 curr_sp  = be_new_IncSP(sp, irg, bl, curr_sp, param_size, be_stack_dir_along);
 241                                 curr_mem = mem;
 242
 243                                 /*
 244                                  * only put the first IncSP to the stack fixup set since the other
 245                                  * ones are correctly connected to other nodes and do not need
 246                                  * to be fixed.
 247                                  */
 248                                 if(i == 0)
 249                                         pset_insert_ptr(env->stack_ops, curr_sp);
 250                         }
 251                 }
 252
 253                 in = (ir_node **) obstack_finish(obst);
 254
 255                 /* We need the sync only, if we didn't build the stores sequentially. */
 256                 if(!do_seq)
 257                         curr_mem = new_r_Sync(irg, bl, n_pos, in);
 258                 obstack_free(obst, in);
 259         }
 260
 261         /* Collect caller save registers */
 262         for(i = 0; env->birg->main_env->caller_save[i]; ++i)
 263                 pset_insert_ptr(caller_save, env->birg->main_env->caller_save[i]);
 264
 265         /* search the greatest result proj number */
 266         foreach_out_edge(irn, edge) {
 267                 const ir_edge_t *res_edge;
 268                 ir_node *irn = get_edge_src_irn(edge);
 269
 270                 if(is_Proj(irn) && get_irn_mode(irn) == mode_T) {
 271                         res_proj = irn;
 272                         foreach_out_edge(irn, res_edge) {
 273                                 int proj;
 274                                 be_abi_call_arg_t *arg;
 275                                 ir_node *res = get_edge_src_irn(res_edge);
 276
 277                                 assert(is_Proj(res));
 278                                 proj = get_Proj_proj(res);
 279                                 arg = get_call_arg(call, 1, proj);
 280                                 if(proj > curr_res_proj)
 281                                         curr_res_proj = proj;
 282                                 if(arg->in_reg)
 283                                         pset_remove_ptr(caller_save, arg->reg);
 284                         }
 285                 }
 286         }
 287         curr_res_proj++;
 288
 289         /* Make additional projs for the caller save registers
 290            and the Keep node which keeps them alive. */
 291         if(pset_count(caller_save) > 0) {
 292                 const arch_register_t *reg;
 293                 ir_node **in;
 294
 295                 if(!res_proj)
 296                         res_proj = new_r_Proj(irg, bl, irn, mode_T, pn_Call_T_result);
 297
 298                 for(reg = pset_first(caller_save); reg; reg = pset_next(caller_save))
 299                         obstack_ptr_grow(obst, new_r_Proj(irg, bl, res_proj, reg->reg_class->mode, curr_res_proj++));
 300
 301                 in = (ir_node **) obstack_finish(obst);
 302                 be_new_Keep(NULL, irg, bl, pset_count(caller_save), in);
 303                 obstack_free(obst, in);
 304         }
 305
 306         /* Clean up the stack. */
 307         if(stack_size > 0) {
 308                 ir_node *last_inc_sp;
 309
 310                 /* Get the result ProjT */
 311                 if(!res_proj)
 312                         res_proj = new_r_Proj(irg, bl, irn, mode_T, pn_Call_T_result);
 313
 314                 /* Make a Proj for the stack pointer. */
 315                 sp_proj     = new_r_Proj(irg, bl, res_proj, sp->reg_class->mode, curr_res_proj++);
 316                 last_inc_sp = be_new_IncSP(sp, irg, bl, sp_proj, stack_size, be_stack_dir_against);
 317                 pset_insert_ptr(env->stack_ops, last_inc_sp);
 318         }
 319
 320         /* at last make the backend call node and set its register requirements. */
 321         for(i = 0; i < n_low_args; ++i)
 322                 obstack_ptr_grow(obst, get_irn_n(irn, low_args[i]));
 323         in = obstack_finish(obst);
 324         low_call = be_new_Call(irg, bl, curr_mem, curr_sp, get_Call_ptr(irn), curr_res_proj, n_low_args, in);
 325         obstack_free(obst, in);
 326
 327         exchange(irn, low_call);
 328
 329         be_abi_call_free(call);
 330         obstack_free(obst, pos);
 331         del_pset(results);
 332         del_pset(caller_save);
 333 }
 334
 335 static void adjust_call_walker(ir_node *irn, void *data)
 336 {
 337         if(get_irn_opcode(irn) == iro_Call)
 338                 adjust_call(data, irn);
 339 }
 340
 341 /**
 342  * Walker to implement alloca-style allocations.
 343  * They are implemented using an add to the stack pointer
 344  * and a copy instruction.
 345  */
 346 static void implement_stack_alloc(be_abi_irg_t *env, ir_node *irn)
 347 {
 348         const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
 349         ir_node *bl           = get_nodes_block(irn);
 350         ir_node *res          = env->init_sp;
 351         ir_node *size;
 352
 353         assert(get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc);
 354
 355         size = get_Alloc_size(irn);
 356         if(isa->stack_dir > 0)
 357                 res = be_new_Copy(isa->sp->reg_class, env->birg->irg, bl, res);
 358
 359         res = be_new_AddSP(isa->sp, env->birg->irg, bl, res, size);
 360         pset_insert_ptr(env->stack_ops, res);
 361
 362         if(isa->stack_dir < 0)
 363                 res = be_new_Copy(isa->sp->reg_class, env->birg->irg, bl, res);
 364
 365 }
 366
 367 /**
 368  * Modify the irg itself and the frame type.
 369  */
 370 static void modify_irg(be_abi_irg_t *env)
 371 {
 372         be_abi_call_t *call       = be_abi_call_new();
 373         const arch_isa_t *isa     = env->birg->main_env->arch_env->isa;
 374         ir_graph *irg             = env->birg->irg;
 375         ir_node *bl               = get_irg_start_block(irg);
 376         ir_node *arg_tuple        = get_irg_args(irg);
 377         type *method_type         = get_entity_type(get_irg_entity(irg));
 378         int n_params              = get_method_n_params(method_type);
 379         const arch_register_t *sp = arch_isa_sp(isa);
 380
 381         int max_arg = 0;
 382         int reg_params_nr = 0;
 383         int n_reg_param   = 0;
 384
 385         int i, j, n;
 386         ir_node *proj_sp;
 387         ir_node *frame_pointer;
 388         ir_node *reg_params, *reg_params_bl;
 389         ir_node **args, **args_repl, **return_params;
 390         const ir_edge_t *edge;
 391
 392
 393         /* Find the maximum proj number of the argument tuple proj */
 394         foreach_out_edge(arg_tuple, edge)  {
 395                 ir_node *irn = get_edge_src_irn(edge);
 396                 int nr       = get_Proj_proj(irn);
 397                 max_arg      = MAX(max_arg, nr);
 398         }
 399         max_arg += 1;
 400         args      = obstack_alloc(&env->obst, max_arg * sizeof(args[0]));
 401         args_repl = obstack_alloc(&env->obst, max_arg * sizeof(args[0]));
 402         memset(args, 0, max_arg * sizeof(args[0]));
 403         memset(args_repl, 0, max_arg * sizeof(args[0]));
 404
 405         /* Fill the argument vector */
 406         foreach_out_edge(arg_tuple, edge) {
 407                 ir_node *irn = get_edge_src_irn(edge);
 408                 int nr       = get_Proj_proj(irn);
 409                 args[nr]     = irn;
 410         }
 411
 412         /* Get the ABI constraints from the ISA */
 413         arch_isa_get_call_abi(isa, method_type, call);
 414
 415         {
 416                 const arch_register_t **callee_save = env->birg->main_env->callee_save;
 417                 int n_reg_param = 0;
 418
 419                 /* Count the register params and add them to the number of projs for the RegParams node */
 420                 for(i = 0; i < n_params; ++i) {
 421                         be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
 422                         n_reg_param += arg->in_reg;
 423                 }
 424
 425                 reg_params_bl = get_irg_start_block(irg);
 426                 reg_params    = be_new_RegParams(irg, reg_params_bl, n_reg_param);
 427                 reg_params_nr = 0;
 428
 429                 proj_sp       = new_r_Proj(irg, reg_params_bl, reg_params, sp->reg_class->mode, reg_params_nr);
 430                 be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), sp);
 431                 reg_params_nr++;
 432
 433                 /* Make Projs for the callee save registers. */
 434                 for(i = 0; callee_save[i] != NULL; ++i, ++reg_params_nr) {
 435                         const arch_register_t *reg = callee_save[i];
 436                         ir_node *irn = new_r_Proj(irg, reg_params_bl, reg_params, reg->reg_class->mode, reg_params_nr);
 437                         be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), reg);
 438
 439                         /* memorize the callee save proj since they will be arguments to the Return nodes. */
 440                         obstack_ptr_grow(&env->obst, irn);
 441                 }
 442
 443                 obstack_ptr_grow(&env->obst, NULL);
 444                 return_params = obstack_finish(&env->obst);
 445         }
 446
 447         /* If we can omit the frame pointer, the stack pointer will become the frame pointer */
 448         env->init_sp = be_new_IncSP(sp, irg, reg_params_bl, proj_sp, 0, be_stack_dir_along);
 449         /* memorize this node for later fix up */
 450         frame_pointer = env->omit_framepointer ? env->init_sp : be_new_Copy(sp->reg_class, irg, reg_params_bl, proj_sp);
 451         set_irg_frame(irg, frame_pointer);
 452
 453         /* reroute the edges from the original argument projs to the RegParam ones. */
 454         for(i = 0; i < max_arg; ++i) {
 455                 if(args[i]) {
 456                         assert(args_repl != NULL);
 457                         edges_reroute(args[i], args_repl[i], irg);
 458                 }
 459         }
 460
 461         /* Now, introduce stack param nodes for all parameters passed on the stack */
 462         for(i = 0; i < max_arg; ++i) {
 463                 ir_node *arg_proj = args[i];
 464                 if(arg_proj != NULL) {
 465                         be_abi_call_arg_t *arg;
 466                         ir_type *param_type;
 467                         int nr = get_Proj_proj(arg_proj);
 468
 469                         nr         = MIN(nr, n_params);
 470                         arg        = get_call_arg(call, 0, nr);
 471                         param_type = get_method_param_type(method_type, nr);
 472
 473                         if(arg->in_reg) {
 474                                 args_repl[i] = new_r_Proj(irg, reg_params_bl, reg_params, get_irn_mode(arg_proj), reg_params_nr);
 475                                 be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), arg->reg);
 476                                 reg_params_nr++;
 477                         }
 478
 479                         /* when the (stack) parameter is primitive, we insert a StackParam
 480                            node representing the load of that parameter */
 481                         else if(is_Primitive_type(param_type)) {
 482                                 ir_mode *mode                    = get_type_mode(param_type);
 483                                 const arch_register_class_t *cls = arch_isa_get_reg_class_for_mode(isa, mode);
 484                                 // TODO: Correct offset computation!
 485                                 args_repl[i] = be_new_StackParam(cls, irg, reg_params_bl, mode, frame_pointer, 0);
 486                         }
 487
 488                         /* The stack parameter is not primitive (it is a struct or array),
 489                            we thus will create a node representing the parameter's address
 490                            on the stack. */
 491                         else {
 492                                 assert(0 && "struct parameters are not supported");
 493                         }
 494                 }
 495         }
 496
 497         obstack_free(&env->obst, args);
 498         be_abi_call_free(call);
 499 }
 500
 501 static void collect_alloca_walker(ir_node *irn, void *data)
 502 {
 503         be_abi_irg_t *env = data;
 504         if(get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc)
 505                 obstack_ptr_grow(&env->obst, irn);
 506 }
 507
 508 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
 509 {
 510         be_abi_irg_t *env = malloc(sizeof(env[0]));
 511
 512         int i;
 513         ir_node **stack_allocs;
 514
 515         env->birg        = birg;
 516         env->stack_ops   = pset_new_ptr(32);
 517         env->omit_framepointer = 1;
 518         obstack_init(&env->obst);
 519
 520         /* search for stack allocation nodes and record them */
 521         irg_walk_graph(env->birg->irg, collect_alloca_walker, NULL, env);
 522         obstack_ptr_grow(&env->obst, NULL);
 523         stack_allocs = obstack_finish(&env->obst);
 524
 525         /* If there are stack allocations in the irg, we need a frame pointer */
 526         if(stack_allocs[0] != NULL)
 527                 env->omit_framepointer = 0;
 528
 529         modify_irg(env);
 530
 531         for(i = 0; stack_allocs[i] != NULL; ++i)
 532                 implement_stack_alloc(env, stack_allocs[i]);
 533
 534         irg_walk_graph(env->birg->irg, NULL, adjust_call_walker, &env);
 535         return env;
 536 }
 537
 538 void be_abi_fix_stack(be_abi_irg_t *env)
 539 {
 540         pset *origs = pset_new_ptr_default();
 541
 542         pset_insert_ptr(origs, env->init_sp);
 543         be_ssa_constr_sets(env->birg->dom_front, origs, env->stack_ops);
 544         del_pset(origs);
 545 }
 546
 547
 548 void be_abi_free(be_abi_irg_t *env)
 549 {
 550         del_pset(env->stack_ops);
 551         obstack_free(&env->obst, NULL);
 552         free(env);
 553 }