8 #include "firm_config.h"
13 #include "irgraph_t.h"
16 #include "iredges_t.h"
24 #include "besched_t.h"
26 #define MAX(x, y) ((x) > (y) ? (x) : (y))
27 #define MIN(x, y) ((x) < (y) ? (x) : (y))
29 typedef struct _be_abi_call_arg_t {
34 const arch_register_t *reg;
37 struct _be_abi_call_t {
38 be_abi_call_flags_t flags;
43 struct _be_abi_irg_t {
49 ir_node *init_sp; /**< The node representing the stack pointer
50 at the start of the function. */
52 pset *stack_ops; /**< Contains all nodes modifying the stack pointer. */
53 pset *ignore_regs; /**< Contains all registers which shall be ignored
54 during register allocation. */
59 unsigned dedicated_fp : 1;
60 unsigned left_to_right : 1;
62 firm_dbg_module_t *dbg; /**< The debugging module. */
65 static int cmp_call_arg(const void *a, const void *b, size_t n)
67 const be_abi_call_arg_t *p = a, *q = b;
68 return !(p->is_res == q->is_res && p->pos == q->pos);
71 static be_abi_call_arg_t *get_or_set_call_arg(be_abi_call_t *call, int is_res, int pos, int do_insert)
73 be_abi_call_arg_t arg;
79 hash = is_res * 100 + pos;
82 ? set_insert(call->params, &arg, sizeof(arg), hash)
83 : set_find(call->params, &arg, sizeof(arg), hash);
86 static INLINE be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
88 return get_or_set_call_arg(call, is_res, pos, 0);
91 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, unsigned arg_gap)
94 call->arg_gap = arg_gap;
97 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos)
99 be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
102 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
104 be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
108 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
110 be_abi_call_arg_t *arg = get_or_set_call_arg(call, 1, arg_pos, 1);
114 be_abi_call_t *be_abi_call_new(void)
116 be_abi_call_t *call = malloc(sizeof(call[0]));
117 call->flags = BE_ABI_NONE;
118 call->params = new_set(cmp_call_arg, 16);
122 void be_abi_call_free(be_abi_call_t *call)
124 del_set(call->params);
128 static INLINE int is_on_stack(be_abi_call_t *call, int pos)
130 be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
131 return arg && !arg->in_reg;
134 static void adjust_call(be_abi_irg_t *env, ir_node *irn)
136 ir_graph *irg = env->birg->irg;
137 const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
138 be_abi_call_t *call = be_abi_call_new();
139 ir_type *mt = get_Call_type(irn);
140 int n_params = get_method_n_params(mt);
141 ir_node *curr_sp = get_irg_frame(irg);
142 ir_node *curr_mem = get_Call_mem(irn);
143 ir_node *bl = get_nodes_block(irn);
144 pset *results = pset_new_ptr(8);
145 pset *caller_save = pset_new_ptr(8);
147 int stack_dir = arch_isa_stack_dir(isa);
148 const arch_register_t *sp = arch_isa_sp(isa);
149 ir_mode *mach_mode = sp->reg_class->mode;
150 struct obstack *obst = &env->obst;
152 ir_node *res_proj = NULL;
153 int curr_res_proj = -1;
160 const ir_edge_t *edge;
165 /* Let the isa fill out the abi description for that call node. */
166 arch_isa_get_call_abi(isa, mt, call);
168 /* Insert code to put the stack arguments on the stack. */
169 for(i = get_irn_arity(irn); i >= 0; --i) {
170 if(is_on_stack(call, i)) {
171 stack_size += get_type_size_bytes(get_method_param_type(mt, i));
172 obstack_int_grow(obst, i);
176 pos = obstack_finish(obst);
178 /* Collect all arguments which are passed in registers. */
179 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
180 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
181 if(arg && arg->in_reg) {
182 obstack_int_grow(obst, i);
186 low_args = obstack_finish(obst);
188 /* If there are some parameters shich shall be passed on the stack. */
191 int do_seq = (call->flags & BE_ABI_USE_PUSH);
193 /* Reverse list of stack parameters if call arguments are from left to right */
194 if(call->flags & BE_ABI_LEFT_TO_RIGHT) {
195 for(i = 0; i < n_pos / 2; ++i) {
196 int other = n_pos - i - 1;
204 * If the stack is decreasing and we do not want to store sequentially,
205 * we allocate as much space on the stack all parameters need, by
206 * moving the stack pointer along the stack's direction.
208 if(stack_dir < 0 && !do_seq) {
209 curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, stack_size, be_stack_dir_along);
210 pset_insert_ptr(env->stack_ops, curr_sp);
213 for(i = 0; i < n_pos; ++i) {
215 ir_node *param = get_irn_n(irn, p);
216 ir_node *addr = curr_sp;
218 type *param_type = get_method_param_type(mt, p);
219 int param_size = get_type_size_bytes(param_type);
221 /* Make the expression to compute the argument's offset. */
223 addr = new_r_Const_long(irg, bl, mach_mode, curr_ofs);
224 addr = new_r_Add(irg, bl, curr_sp, addr, mach_mode);
227 /* Insert a store for primitive arguments. */
228 if(is_Primitive_type(param_type)) {
229 mem = new_r_Store(irg, bl, curr_mem, addr, param);
230 mem = new_r_Proj(irg, bl, mem, mode_M, pn_Store_M);
233 /* Make a memcopy for compound arguments. */
235 assert(mode_is_reference(get_irn_mode(param)));
236 mem = new_r_CopyB(irg, bl, curr_mem, addr, param, param_type);
237 mem = new_r_Proj(irg, bl, mem, mode_M, pn_CopyB_M_regular);
240 obstack_ptr_grow(obst, mem);
242 curr_ofs += param_size;
245 * If we wanted to build the arguments sequentially,
246 * the stack pointer for the next must be incremented,
247 * and the memory value propagated.
251 curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, param_size, be_stack_dir_along);
255 * only put the first IncSP to the stack fixup set since the other
256 * ones are correctly connected to other nodes and do not need
260 pset_insert_ptr(env->stack_ops, curr_sp);
264 in = (ir_node **) obstack_finish(obst);
266 /* We need the sync only, if we didn't build the stores sequentially. */
268 curr_mem = new_r_Sync(irg, bl, n_pos, in);
269 obstack_free(obst, in);
272 /* Collect caller save registers */
273 for(i = 0; env->birg->main_env->caller_save[i]; ++i)
274 pset_insert_ptr(caller_save, env->birg->main_env->caller_save[i]);
276 /* search the greatest result proj number */
277 foreach_out_edge(irn, edge) {
278 const ir_edge_t *res_edge;
279 ir_node *irn = get_edge_src_irn(edge);
281 if(is_Proj(irn) && get_irn_mode(irn) == mode_T) {
283 foreach_out_edge(irn, res_edge) {
285 be_abi_call_arg_t *arg;
286 ir_node *res = get_edge_src_irn(res_edge);
288 assert(is_Proj(res));
289 proj = get_Proj_proj(res);
290 arg = get_call_arg(call, 1, proj);
291 if(proj > curr_res_proj)
292 curr_res_proj = proj;
294 pset_remove_ptr(caller_save, arg->reg);
300 /* Make additional projs for the caller save registers
301 and the Keep node which keeps them alive. */
302 if(pset_count(caller_save) > 0) {
303 const arch_register_t *reg;
307 res_proj = new_r_Proj(irg, bl, irn, mode_T, pn_Call_T_result);
309 for(reg = pset_first(caller_save); reg; reg = pset_next(caller_save))
310 obstack_ptr_grow(obst, new_r_Proj(irg, bl, res_proj, reg->reg_class->mode, curr_res_proj++));
312 in = (ir_node **) obstack_finish(obst);
313 be_new_Keep(NULL, irg, bl, pset_count(caller_save), in);
314 obstack_free(obst, in);
317 /* Clean up the stack. */
319 ir_node *last_inc_sp;
321 /* Get the result ProjT */
323 res_proj = new_r_Proj(irg, bl, irn, mode_T, pn_Call_T_result);
325 /* Make a Proj for the stack pointer. */
326 sp_proj = new_r_Proj(irg, bl, res_proj, sp->reg_class->mode, curr_res_proj++);
327 last_inc_sp = be_new_IncSP(sp, irg, bl, sp_proj, stack_size, be_stack_dir_against);
328 pset_insert_ptr(env->stack_ops, last_inc_sp);
331 /* at last make the backend call node and set its register requirements. */
332 for(i = 0; i < n_low_args; ++i)
333 obstack_ptr_grow(obst, get_irn_n(irn, low_args[i]));
334 in = obstack_finish(obst);
335 low_call = be_new_Call(irg, bl, curr_mem, curr_sp, get_Call_ptr(irn), curr_res_proj, n_low_args, in);
336 obstack_free(obst, in);
338 exchange(irn, low_call);
340 be_abi_call_free(call);
341 obstack_free(obst, pos);
343 del_pset(caller_save);
346 static void adjust_call_walker(ir_node *irn, void *data)
348 if(get_irn_opcode(irn) == iro_Call)
349 adjust_call(data, irn);
353 * Walker to implement alloca-style allocations.
354 * They are implemented using an add to the stack pointer
355 * and a copy instruction.
357 static void implement_stack_alloc(be_abi_irg_t *env, ir_node *irn)
359 const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
360 ir_node *bl = get_nodes_block(irn);
361 ir_node *res = env->init_sp;
364 assert(get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc);
366 size = get_Alloc_size(irn);
367 if(isa->stack_dir > 0)
368 res = be_new_Copy(isa->sp->reg_class, env->birg->irg, bl, res);
370 res = be_new_AddSP(isa->sp, env->birg->irg, bl, res, size);
371 pset_insert_ptr(env->stack_ops, res);
373 if(isa->stack_dir < 0)
374 res = be_new_Copy(isa->sp->reg_class, env->birg->irg, bl, res);
378 static void collect_return_walker(ir_node *irn, void *data)
380 if(get_irn_opcode(irn) == iro_Return) {
381 struct obstack *obst = data;
382 obstack_ptr_grow(obst, irn);
387 * Modify the irg itself and the frame type.
389 static void modify_irg(be_abi_irg_t *env)
391 be_abi_call_t *call = be_abi_call_new();
392 const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
393 ir_graph *irg = env->birg->irg;
394 ir_node *bl = get_irg_start_block(irg);
395 ir_node *end = get_irg_end_block(irg);
396 ir_node *arg_tuple = get_irg_args(irg);
397 type *method_type = get_entity_type(get_irg_entity(irg));
398 int n_params = get_method_n_params(method_type);
399 const arch_register_t *sp = arch_isa_sp(isa);
402 int reg_params_nr = 0;
403 ir_node *proj_sp = NULL;
408 ir_node *frame_pointer;
409 ir_node *reg_params, *reg_params_bl;
410 ir_node **args, **args_repl;
411 const ir_edge_t *edge;
413 pmap *regs = pmap_create();
416 firm_dbg_module_t *dbg = env->dbg;
418 DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
420 /* Find the maximum proj number of the argument tuple proj */
421 foreach_out_edge(arg_tuple, edge) {
422 ir_node *irn = get_edge_src_irn(edge);
423 int nr = get_Proj_proj(irn);
424 max_arg = MAX(max_arg, nr);
427 args = obstack_alloc(&env->obst, max_arg * sizeof(args[0]));
428 args_repl = obstack_alloc(&env->obst, max_arg * sizeof(args[0]));
429 memset(args, 0, max_arg * sizeof(args[0]));
430 memset(args_repl, 0, max_arg * sizeof(args[0]));
432 /* Fill the argument vector */
433 foreach_out_edge(arg_tuple, edge) {
434 ir_node *irn = get_edge_src_irn(edge);
435 int nr = get_Proj_proj(irn);
437 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
440 /* Get the ABI constraints from the ISA */
441 arch_isa_get_call_abi(isa, method_type, call);
443 /* Count the register params and add them to the number of Projs for the RegParams node */
444 for(i = 0; i < n_params; ++i) {
445 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
447 assert(arg->reg != sp && "cannot use stack pointer as parameter register");
448 pmap_insert(regs, (void *) arg->reg, NULL);
449 DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
453 /* Collect all callee-save registers */
454 for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
455 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
456 for(j = 0; j < cls->n_regs; ++j) {
457 const arch_register_t *reg = &cls->regs[j];
458 if(arch_register_type_is(reg, callee_save))
459 pmap_insert(regs, (void *) reg, NULL);
463 /* The stack pointer must also be saved but not necessarily be marked as callee save */
464 pmap_insert(regs, (void *) sp, NULL);
466 reg_params_bl = get_irg_start_block(irg);
467 reg_params = be_new_RegParams(irg, reg_params_bl, pmap_count(regs));
471 * make proj nodes for the callee save registers.
472 * memorize them, since Return nodes get those as inputs.
474 for(ent = pmap_first(regs); ent; ent = pmap_next(regs)) {
475 arch_register_t *reg = ent->key;
476 ent->value = new_r_Proj(irg, reg_params_bl, reg_params, reg->reg_class->mode, reg_params_nr);
477 be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), reg);
480 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", reg_params_nr - 1, reg->name));
483 proj_sp = pmap_get(regs, (void *) sp);
484 assert(proj_sp != NULL && "There must be a Proj for the stack pointer");
487 /* This is the stack pointer add/sub which allocates the frame. remind it for later fix up. */
488 env->init_sp = be_new_IncSP(sp, irg, reg_params_bl, proj_sp, 0, be_stack_dir_along);
489 frame_pointer = env->init_sp;
493 env->init_sp = proj_sp;
494 frame_pointer = be_new_Copy(sp->reg_class, irg, reg_params_bl, proj_sp);
497 /* Set the new frame pointer. */
498 exchange(get_irg_frame(irg), frame_pointer);
499 set_irg_frame(irg, frame_pointer);
501 /* compute the start offset for the stack parameters. */
505 int inc_dir = isa->stack_dir * (env->left_to_right ? 1 : -1);
507 for(i = 0; i < n_params; ++i) {
508 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
510 arg_size += get_type_size_bytes(get_method_param_type(method_type, i));
513 arg_offset = -isa->stack_dir * call->arg_gap + env->left_to_right * arg_size;
515 /* Now, introduce stack param nodes for all parameters passed on the stack */
516 for(i = 0; i < max_arg; ++i) {
517 ir_node *arg_proj = args[i];
518 if(arg_proj != NULL) {
519 be_abi_call_arg_t *arg;
521 int nr = get_Proj_proj(arg_proj);
523 nr = MIN(nr, n_params);
524 arg = get_call_arg(call, 0, nr);
525 param_type = get_method_param_type(method_type, nr);
528 args_repl[i] = new_r_Proj(irg, reg_params_bl, reg_params, get_irn_mode(arg_proj), reg_params_nr);
529 be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), arg->reg);
533 /* when the (stack) parameter is primitive, we insert a StackParam
534 node representing the load of that parameter */
536 int size = get_type_size_bytes(param_type) * isa->stack_dir;
541 if(is_atomic_type(param_type)) {
542 ir_mode *mode = get_type_mode(param_type);
543 const arch_register_class_t *cls = arch_isa_get_reg_class_for_mode(isa, mode);
544 args_repl[i] = be_new_StackParam(cls, irg, reg_params_bl, mode, frame_pointer, arg_offset);
547 /* The stack parameter is not primitive (it is a struct or array),
548 we thus will create a node representing the parameter's address
551 assert(0 && "struct parameters are not supported");
561 /* reroute the edges from the original argument projs to the RegParam ones. */
562 for(i = 0; i < max_arg; ++i) {
563 if(args[i] != NULL) {
564 assert(args_repl[i] != NULL);
565 edges_reroute(args[i], args_repl[i], irg);
569 /* All Return nodes hang on the End node, so look for them there. */
570 for(i = 0, n = get_irn_arity(end); i < n; ++i) {
571 ir_node *irn = get_irn_n(end, i);
573 if(get_irn_opcode(irn) == iro_Return) {
574 ir_node *bl = get_nodes_block(irn);
579 /* collect all arguments of the return */
580 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
581 obstack_ptr_grow(&env->obst, get_irn_n(irn, i));
583 /* Add the Proj nodes representing the caller save registers. */
584 for(ent = pmap_first(regs); ent; ent = pmap_next(regs), ++n) {
585 const arch_register_t *reg = ent->key;
586 ir_node *irn = ent->value;
589 * If the register is the stack pointer,
590 * add the fix up code. Either add the size of the stack
591 * frame if we omitted the frame pointer or move the
592 * frame pointer back to the stack register.
596 irn = be_new_Copy(sp->reg_class, irg, bl, frame_pointer);
597 be_set_constr_single_reg(irn, -1, sp);
601 irn = be_new_IncSP(sp, irg, bl, proj_sp, 0, be_stack_dir_against);
603 obstack_ptr_grow(&env->obst, irn);
606 /* The in array for the new back end return is now ready. */
607 in = obstack_finish(&env->obst);
608 ret = be_new_Return(irg, bl, n, in);
609 edges_reroute(irn, ret, irg);
610 obstack_free(&env->obst, in);
614 obstack_free(&env->obst, args);
615 be_abi_call_free(call);
619 static void collect_alloca_walker(ir_node *irn, void *data)
621 be_abi_irg_t *env = data;
622 if(get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc)
623 obstack_ptr_grow(&env->obst, irn);
626 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
628 be_abi_irg_t *env = malloc(sizeof(env[0]));
631 ir_node **stack_allocs;
633 env->method_type = get_entity_type(get_irg_entity(birg->irg));
634 env->call = be_abi_call_new();
635 arch_isa_get_call_abi(birg->main_env->arch_env->isa, env->method_type, env->call);
637 env->omit_fp = (env->call->flags & BE_ABI_TRY_OMIT_FRAME_POINTER) != 0;
638 env->dedicated_fp = (env->call->flags & BE_ABI_FRAME_POINTER_DEDICATED) != 0;
639 env->left_to_right = (env->call->flags & BE_ABI_LEFT_TO_RIGHT) != 0;
641 env->stack_ops = pset_new_ptr(32);
642 env->dbg = firm_dbg_register("firm.be.abi");
643 obstack_init(&env->obst);
645 /* search for stack allocation nodes and record them */
646 irg_walk_graph(env->birg->irg, collect_alloca_walker, NULL, env);
647 obstack_ptr_grow(&env->obst, NULL);
648 stack_allocs = obstack_finish(&env->obst);
650 /* If there are stack allocations in the irg, we need a frame pointer */
651 if(stack_allocs[0] != NULL)
656 for(i = 0; stack_allocs[i] != NULL; ++i)
657 implement_stack_alloc(env, stack_allocs[i]);
659 irg_walk_graph(env->birg->irg, NULL, adjust_call_walker, &env);
663 static void collect_stack_nodes(ir_node *irn, void *data)
667 switch(be_get_irn_opcode(irn)) {
670 pset_insert_ptr(s, irn);
674 void be_abi_fix_stack_nodes(be_abi_irg_t *env)
676 dom_front_info_t *df;
679 /* We need dominance frontiers for fix up */
680 df = be_compute_dominance_frontiers(env->birg->irg);
682 stack_ops = pset_new_ptr_default();
683 pset_insert_ptr(env->stack_ops, env->init_sp);
684 irg_walk_graph(env->birg->irg, collect_stack_nodes, NULL, stack_ops);
685 be_ssa_constr_set(df, stack_ops);
688 /* free these dominance frontiers */
689 be_free_dominance_frontiers(df);
692 static int get_dir(ir_node *irn)
694 return 1 - 2 * (be_get_IncSP_direction(irn) == be_stack_dir_against);
697 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int bias)
699 const arch_env_t *aenv = env->birg->main_env->arch_env;
701 int start_bias = bias;
703 sched_foreach(bl, irn) {
704 if(be_is_IncSP(irn)) {
705 int ofs = be_get_IncSP_offset(irn);
706 int dir = get_dir(irn);
708 if(ofs == BE_STACK_FRAME_SIZE) {
709 ofs = get_type_size_bytes(get_irg_frame_type(env->birg->irg));
710 be_set_IncSP_offset(irn, ofs);
717 arch_set_stack_bias(aenv, irn, bias);
723 static void stack_bias_walker(ir_node *bl, void *data)
725 if(bl != get_irg_start_block(get_irn_irg(bl))) {
726 be_abi_irg_t *env = data;
727 process_stack_bias(env, bl, env->start_block_bias);
731 void be_abi_fix_stack_bias(be_abi_irg_t *env)
733 ir_graph *irg = env->birg->irg;
735 /* Determine the stack bias at the and of the start block. */
736 env->start_block_bias = process_stack_bias(env, get_irg_start_block(irg), 0);
738 /* fix the bias is all other blocks */
739 irg_block_walk_graph(irg, stack_bias_walker, NULL, env);
742 void be_abi_free(be_abi_irg_t *env)
744 del_pset(env->stack_ops);
745 obstack_free(&env->obst, NULL);