8 #include "firm_config.h"
13 #include "irgraph_t.h"
16 #include "iredges_t.h"
25 #define MAX(x, y) ((x) > (y) ? (x) : (y))
26 #define MIN(x, y) ((x) < (y) ? (x) : (y))
28 typedef struct _be_abi_call_arg_t {
33 const arch_register_t *reg;
36 struct _be_abi_call_t {
37 be_abi_call_flags_t flags;
41 struct _be_abi_irg_t {
44 ir_node *init_sp; /**< The node representing the stack pointer
45 at the start of the function. */
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. */
51 unsigned omit_framepointer: 1; /**< If one, the frame(base-)pointer can be used
52 as an ordinary register. */
54 firm_dbg_module_t *dbg; /**< The debugging module. */
57 static int cmp_call_arg(const void *a, const void *b, size_t n)
59 const be_abi_call_arg_t *p = a, *q = b;
60 return !(p->is_res == q->is_res && p->pos == q->pos);
63 static be_abi_call_arg_t *get_or_set_call_arg(be_abi_call_t *call, int is_res, int pos, int do_insert)
65 be_abi_call_arg_t arg;
71 hash = is_res * 100 + pos;
74 ? set_insert(call->params, &arg, sizeof(arg), hash)
75 : set_find(call->params, &arg, sizeof(arg), hash);
78 static INLINE be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
80 return get_or_set_call_arg(call, is_res, pos, 0);
83 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags)
88 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos)
90 be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
93 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
95 be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
99 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
101 be_abi_call_arg_t *arg = get_or_set_call_arg(call, 1, arg_pos, 1);
105 be_abi_call_t *be_abi_call_new(void)
107 be_abi_call_t *call = malloc(sizeof(call[0]));
108 call->flags = BE_ABI_NONE;
109 call->params = new_set(cmp_call_arg, 16);
113 void be_abi_call_free(be_abi_call_t *call)
115 del_set(call->params);
119 static INLINE int is_on_stack(be_abi_call_t *call, int pos)
121 be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
122 return arg && !arg->in_reg;
125 static void adjust_call(be_abi_irg_t *env, ir_node *irn)
127 ir_graph *irg = env->birg->irg;
128 const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
129 be_abi_call_t *call = be_abi_call_new();
130 ir_type *mt = get_Call_type(irn);
131 int n_params = get_method_n_params(mt);
132 ir_node *curr_sp = get_irg_frame(irg);
133 ir_node *curr_mem = get_Call_mem(irn);
134 ir_node *bl = get_nodes_block(irn);
135 pset *results = pset_new_ptr(8);
136 pset *caller_save = pset_new_ptr(8);
138 int stack_dir = arch_isa_stack_dir(isa);
139 const arch_register_t *sp = arch_isa_sp(isa);
140 ir_mode *mach_mode = sp->reg_class->mode;
141 struct obstack *obst = &env->obst;
143 ir_node *res_proj = NULL;
144 int curr_res_proj = -1;
151 const ir_edge_t *edge;
156 /* Let the isa fill out the abi description for that call node. */
157 arch_isa_get_call_abi(isa, mt, call);
159 /* Insert code to put the stack arguments on the stack. */
160 for(i = get_irn_arity(irn); i >= 0; --i) {
161 if(is_on_stack(call, i)) {
162 stack_size += get_type_size_bytes(get_method_param_type(mt, i));
163 obstack_int_grow(obst, i);
167 pos = obstack_finish(obst);
169 /* Collect all arguments which are passed in registers. */
170 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
171 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
172 if(arg && arg->in_reg) {
173 obstack_int_grow(obst, i);
177 low_args = obstack_finish(obst);
179 /* If there are some parameters shich shall be passed on the stack. */
182 int do_seq = (call->flags & BE_ABI_USE_PUSH);
184 /* Reverse list of stack parameters if call arguments are from left to right */
185 if(call->flags & BE_ABI_LEFT_TO_RIGHT) {
186 for(i = 0; i < n_pos / 2; ++i) {
187 int other = n_pos - i - 1;
195 * If the stack is decreasing and we do not want to store sequentially,
196 * we allocate as much space on the stack all parameters need, by
197 * moving the stack pointer along the stack's direction.
199 if(stack_dir < 0 && !do_seq) {
200 curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, stack_size, be_stack_dir_along);
201 pset_insert_ptr(env->stack_ops, curr_sp);
204 for(i = 0; i < n_pos; ++i) {
206 ir_node *param = get_irn_n(irn, p);
207 ir_node *addr = curr_sp;
209 type *param_type = get_method_param_type(mt, p);
210 int param_size = get_type_size_bytes(param_type);
212 /* Make the expression to compute the argument's offset. */
214 addr = new_r_Const_long(irg, bl, mach_mode, curr_ofs);
215 addr = new_r_Add(irg, bl, curr_sp, addr, mach_mode);
218 /* Insert a store for primitive arguments. */
219 if(is_Primitive_type(param_type)) {
220 mem = new_r_Store(irg, bl, curr_mem, addr, param);
221 mem = new_r_Proj(irg, bl, mem, mode_M, pn_Store_M);
224 /* Make a memcopy for compound arguments. */
226 assert(mode_is_reference(get_irn_mode(param)));
227 mem = new_r_CopyB(irg, bl, curr_mem, addr, param, param_type);
228 mem = new_r_Proj(irg, bl, mem, mode_M, pn_CopyB_M_regular);
231 obstack_ptr_grow(obst, mem);
233 curr_ofs += param_size;
236 * If we wanted to build the arguments sequentially,
237 * the stack pointer for the next must be incremented,
238 * and the memory value propagated.
242 curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, param_size, be_stack_dir_along);
246 * only put the first IncSP to the stack fixup set since the other
247 * ones are correctly connected to other nodes and do not need
251 pset_insert_ptr(env->stack_ops, curr_sp);
255 in = (ir_node **) obstack_finish(obst);
257 /* We need the sync only, if we didn't build the stores sequentially. */
259 curr_mem = new_r_Sync(irg, bl, n_pos, in);
260 obstack_free(obst, in);
263 /* Collect caller save registers */
264 for(i = 0; env->birg->main_env->caller_save[i]; ++i)
265 pset_insert_ptr(caller_save, env->birg->main_env->caller_save[i]);
267 /* search the greatest result proj number */
268 foreach_out_edge(irn, edge) {
269 const ir_edge_t *res_edge;
270 ir_node *irn = get_edge_src_irn(edge);
272 if(is_Proj(irn) && get_irn_mode(irn) == mode_T) {
274 foreach_out_edge(irn, res_edge) {
276 be_abi_call_arg_t *arg;
277 ir_node *res = get_edge_src_irn(res_edge);
279 assert(is_Proj(res));
280 proj = get_Proj_proj(res);
281 arg = get_call_arg(call, 1, proj);
282 if(proj > curr_res_proj)
283 curr_res_proj = proj;
285 pset_remove_ptr(caller_save, arg->reg);
291 /* Make additional projs for the caller save registers
292 and the Keep node which keeps them alive. */
293 if(pset_count(caller_save) > 0) {
294 const arch_register_t *reg;
298 res_proj = new_r_Proj(irg, bl, irn, mode_T, pn_Call_T_result);
300 for(reg = pset_first(caller_save); reg; reg = pset_next(caller_save))
301 obstack_ptr_grow(obst, new_r_Proj(irg, bl, res_proj, reg->reg_class->mode, curr_res_proj++));
303 in = (ir_node **) obstack_finish(obst);
304 be_new_Keep(NULL, irg, bl, pset_count(caller_save), in);
305 obstack_free(obst, in);
308 /* Clean up the stack. */
310 ir_node *last_inc_sp;
312 /* Get the result ProjT */
314 res_proj = new_r_Proj(irg, bl, irn, mode_T, pn_Call_T_result);
316 /* Make a Proj for the stack pointer. */
317 sp_proj = new_r_Proj(irg, bl, res_proj, sp->reg_class->mode, curr_res_proj++);
318 last_inc_sp = be_new_IncSP(sp, irg, bl, sp_proj, stack_size, be_stack_dir_against);
319 pset_insert_ptr(env->stack_ops, last_inc_sp);
322 /* at last make the backend call node and set its register requirements. */
323 for(i = 0; i < n_low_args; ++i)
324 obstack_ptr_grow(obst, get_irn_n(irn, low_args[i]));
325 in = obstack_finish(obst);
326 low_call = be_new_Call(irg, bl, curr_mem, curr_sp, get_Call_ptr(irn), curr_res_proj, n_low_args, in);
327 obstack_free(obst, in);
329 exchange(irn, low_call);
331 be_abi_call_free(call);
332 obstack_free(obst, pos);
334 del_pset(caller_save);
337 static void adjust_call_walker(ir_node *irn, void *data)
339 if(get_irn_opcode(irn) == iro_Call)
340 adjust_call(data, irn);
344 * Walker to implement alloca-style allocations.
345 * They are implemented using an add to the stack pointer
346 * and a copy instruction.
348 static void implement_stack_alloc(be_abi_irg_t *env, ir_node *irn)
350 const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
351 ir_node *bl = get_nodes_block(irn);
352 ir_node *res = env->init_sp;
355 assert(get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc);
357 size = get_Alloc_size(irn);
358 if(isa->stack_dir > 0)
359 res = be_new_Copy(isa->sp->reg_class, env->birg->irg, bl, res);
361 res = be_new_AddSP(isa->sp, env->birg->irg, bl, res, size);
362 pset_insert_ptr(env->stack_ops, res);
364 if(isa->stack_dir < 0)
365 res = be_new_Copy(isa->sp->reg_class, env->birg->irg, bl, res);
370 * Modify the irg itself and the frame type.
372 static void modify_irg(be_abi_irg_t *env)
374 be_abi_call_t *call = be_abi_call_new();
375 const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
376 ir_graph *irg = env->birg->irg;
377 ir_node *bl = get_irg_start_block(irg);
378 ir_node *arg_tuple = get_irg_args(irg);
379 type *method_type = get_entity_type(get_irg_entity(irg));
380 int n_params = get_method_n_params(method_type);
381 const arch_register_t *sp = arch_isa_sp(isa);
384 int reg_params_nr = 0;
385 ir_node *proj_sp = NULL;
388 ir_node *frame_pointer;
389 ir_node *reg_params, *reg_params_bl;
390 ir_node **args, **args_repl, **return_params;
391 const ir_edge_t *edge;
392 const arch_register_t *reg;
394 pset *callee_save = pset_new_ptr_default();
395 pset *regs = pset_new_ptr_default();
397 firm_dbg_module_t *dbg = env->dbg;
399 DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
401 /* Find the maximum proj number of the argument tuple proj */
402 foreach_out_edge(arg_tuple, edge) {
403 ir_node *irn = get_edge_src_irn(edge);
404 int nr = get_Proj_proj(irn);
405 max_arg = MAX(max_arg, nr);
408 args = obstack_alloc(&env->obst, max_arg * sizeof(args[0]));
409 args_repl = obstack_alloc(&env->obst, max_arg * sizeof(args[0]));
410 memset(args, 0, max_arg * sizeof(args[0]));
411 memset(args_repl, 0, max_arg * sizeof(args[0]));
413 /* Fill the argument vector */
414 foreach_out_edge(arg_tuple, edge) {
415 ir_node *irn = get_edge_src_irn(edge);
416 int nr = get_Proj_proj(irn);
418 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
421 /* Get the ABI constraints from the ISA */
422 arch_isa_get_call_abi(isa, method_type, call);
424 /* Count the register params and add them to the number of projs for the RegParams node */
425 for(i = 0; i < n_params; ++i) {
426 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
428 assert(arg->reg != sp && "cannot use stack pointer as parameter register");
429 pset_insert_ptr(regs, arg->reg);
430 DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
434 /* Collect all callee-save registers which are not used as parameter registers. */
435 for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
436 const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
437 for(j = 0; j < cls->n_regs; ++j) {
438 const arch_register_t *reg = &cls->regs[j];
439 if(arch_register_type_is(reg, callee_save) && !pset_find_ptr(regs, reg))
440 pset_insert_ptr(callee_save, reg);
444 pset_insert_ptr(callee_save, sp);
446 reg_params_bl = get_irg_start_block(irg);
447 reg_params = be_new_RegParams(irg, reg_params_bl, pset_count(regs) + pset_count(callee_save));
451 * make proj nodes for the callee save registers.
452 * memorize them, since Return nodes get those as inputs.
454 for(reg = pset_first(callee_save); reg; reg = pset_next(callee_save)) {
455 ir_node *irn = new_r_Proj(irg, reg_params_bl, reg_params, reg->reg_class->mode, reg_params_nr);
456 be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), reg);
457 obstack_ptr_grow(&env->obst, irn);
460 DBG((dbg, LEVEL_2, "\tcallee save proj #%d -> reg %s\n", reg_params_nr - 1, reg->name));
462 /* detect the proj of the stack register and memorize it. */
466 obstack_ptr_grow(&env->obst, NULL);
467 return_params = obstack_finish(&env->obst);
469 assert(proj_sp != NULL && "There must be a Proj for the stack pointer");
471 /* This is the stack pointer add/sub which allocates the frame. remind it for later fixup. */
472 env->init_sp = be_new_IncSP(sp, irg, reg_params_bl, proj_sp, 0, be_stack_dir_along);
475 * if we can omit the frame pointer (use it as an ordinary register), the stack pointer becomes
476 * the frame pointer, else we have to copy the current stack pointer to the frame pointer
478 frame_pointer = env->omit_framepointer ? env->init_sp : be_new_Copy(sp->reg_class, irg, reg_params_bl, proj_sp);
479 set_irg_frame(irg, frame_pointer);
481 /* Now, introduce stack param nodes for all parameters passed on the stack */
482 for(i = 0; i < max_arg; ++i) {
483 ir_node *arg_proj = args[i];
484 if(arg_proj != NULL) {
485 be_abi_call_arg_t *arg;
487 int nr = get_Proj_proj(arg_proj);
489 nr = MIN(nr, n_params);
490 arg = get_call_arg(call, 0, nr);
491 param_type = get_method_param_type(method_type, nr);
494 args_repl[i] = new_r_Proj(irg, reg_params_bl, reg_params, get_irn_mode(arg_proj), reg_params_nr);
495 be_set_constr_single_reg(reg_params, -(reg_params_nr + 1), arg->reg);
499 /* when the (stack) parameter is primitive, we insert a StackParam
500 node representing the load of that parameter */
501 else if(is_atomic_type(param_type)) {
502 ir_mode *mode = get_type_mode(param_type);
503 const arch_register_class_t *cls = arch_isa_get_reg_class_for_mode(isa, mode);
504 // TODO: Correct offset computation!
505 args_repl[i] = be_new_StackParam(cls, irg, reg_params_bl, mode, frame_pointer, 0);
508 /* The stack parameter is not primitive (it is a struct or array),
509 we thus will create a node representing the parameter's address
512 assert(0 && "struct parameters are not supported");
517 /* reroute the edges from the original argument projs to the RegParam ones. */
518 for(i = 0; i < max_arg; ++i) {
519 if(args[i] != NULL) {
520 assert(args_repl[i] != NULL);
521 edges_reroute(args[i], args_repl[i], irg);
525 obstack_free(&env->obst, args);
526 be_abi_call_free(call);
528 del_pset(callee_save);
532 static void collect_alloca_walker(ir_node *irn, void *data)
534 be_abi_irg_t *env = data;
535 if(get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc)
536 obstack_ptr_grow(&env->obst, irn);
539 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
541 be_abi_irg_t *env = malloc(sizeof(env[0]));
544 ir_node **stack_allocs;
546 env->omit_framepointer = 1;
548 env->stack_ops = pset_new_ptr(32);
549 env->dbg = firm_dbg_register("firm.be.abi");
550 obstack_init(&env->obst);
552 /* search for stack allocation nodes and record them */
553 irg_walk_graph(env->birg->irg, collect_alloca_walker, NULL, env);
554 obstack_ptr_grow(&env->obst, NULL);
555 stack_allocs = obstack_finish(&env->obst);
557 /* If there are stack allocations in the irg, we need a frame pointer */
558 if(stack_allocs[0] != NULL)
559 env->omit_framepointer = 0;
563 for(i = 0; stack_allocs[i] != NULL; ++i)
564 implement_stack_alloc(env, stack_allocs[i]);
566 irg_walk_graph(env->birg->irg, NULL, adjust_call_walker, &env);
570 void be_abi_fix_stack(be_abi_irg_t *env)
572 pset *origs = pset_new_ptr_default();
573 dom_front_info_t *df = be_compute_dominance_frontiers(env->birg->irg);
575 pset_insert_ptr(origs, env->init_sp);
576 be_ssa_constr_sets(df, origs, env->stack_ops);
578 be_free_dominance_frontiers(df);
582 void be_abi_free(be_abi_irg_t *env)
584 del_pset(env->stack_ops);
585 obstack_free(&env->obst, NULL);