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. */
55 static int cmp_call_arg(const void *a, const void *b, size_t n)
57 const be_abi_call_arg_t *p = a, *q = b;
58 return !(p->is_res == q->is_res && p->pos == q->pos);
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)
63 be_abi_call_arg_t arg;
69 hash = is_res * 100 + pos;
72 ? set_insert(call->params, &arg, sizeof(arg), hash)
73 : set_find(call->params, &arg, sizeof(arg), hash);
76 static INLINE be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
78 return get_or_set_call_arg(call, is_res, pos, 0);
81 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags)
86 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos)
88 be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
91 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
93 be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
97 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
99 be_abi_call_arg_t *arg = get_or_set_call_arg(call, 1, arg_pos, 1);
103 be_abi_call_t *be_abi_call_new(void)
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);
111 void be_abi_call_free(be_abi_call_t *call)
113 del_set(call->params);
117 static INLINE int is_on_stack(be_abi_call_t *call, int pos)
119 be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
120 return arg && !arg->in_reg;
123 static void adjust_call(be_abi_irg_t *env, ir_node *irn)
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);
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;
141 ir_node *res_proj = NULL;
142 int curr_res_proj = -1;
149 const ir_edge_t *edge;
154 /* Let the isa fill out the abi description for that call node. */
155 arch_isa_get_call_abi(isa, mt, call);
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);
165 pos = obstack_finish(obst);
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);
175 low_args = obstack_finish(obst);
177 /* If there are some parameters shich shall be passed on the stack. */
180 int do_seq = (call->flags & BE_ABI_USE_PUSH);
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;
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.
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);
202 for(i = 0; i < n_pos; ++i) {
204 ir_node *param = get_irn_n(irn, p);
205 ir_node *addr = curr_sp;
207 type *param_type = get_method_param_type(mt, p);
208 int param_size = get_type_size_bytes(param_type);
210 /* Make the expression to compute the argument's offset. */
212 addr = new_r_Const_long(irg, bl, mach_mode, curr_ofs);
213 addr = new_r_Add(irg, bl, curr_sp, addr, mach_mode);
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);
222 /* Make a memcopy for compound arguments. */
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);
229 obstack_ptr_grow(obst, mem);
231 curr_ofs += param_size;
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.
240 curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, param_size, be_stack_dir_along);
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
249 pset_insert_ptr(env->stack_ops, curr_sp);
253 in = (ir_node **) obstack_finish(obst);
255 /* We need the sync only, if we didn't build the stores sequentially. */
257 curr_mem = new_r_Sync(irg, bl, n_pos, in);
258 obstack_free(obst, in);
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]);
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);
270 if(is_Proj(irn) && get_irn_mode(irn) == mode_T) {
272 foreach_out_edge(irn, res_edge) {
274 be_abi_call_arg_t *arg;
275 ir_node *res = get_edge_src_irn(res_edge);
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;
283 pset_remove_ptr(caller_save, arg->reg);
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;
296 res_proj = new_r_Proj(irg, bl, irn, mode_T, pn_Call_T_result);
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++));
301 in = (ir_node **) obstack_finish(obst);
302 be_new_Keep(NULL, irg, bl, pset_count(caller_save), in);
303 obstack_free(obst, in);
306 /* Clean up the stack. */
308 ir_node *last_inc_sp;
310 /* Get the result ProjT */
312 res_proj = new_r_Proj(irg, bl, irn, mode_T, pn_Call_T_result);
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);
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);
327 exchange(irn, low_call);
329 be_abi_call_free(call);
330 obstack_free(obst, pos);
332 del_pset(caller_save);
335 static void adjust_call_walker(ir_node *irn, void *data)
337 if(get_irn_opcode(irn) == iro_Call)
338 adjust_call(data, irn);
342 * Walker to implement alloca-style allocations.
343 * They are implemented using an add to the stack pointer
344 * and a copy instruction.
346 static void implement_stack_alloc(be_abi_irg_t *env, ir_node *irn)
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;
353 assert(get_irn_opcode(irn) == iro_Alloc && get_Alloc_where(irn) == stack_alloc);
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);
359 res = be_new_AddSP(isa->sp, env->birg->irg, bl, res, size);
360 pset_insert_ptr(env->stack_ops, res);
362 if(isa->stack_dir < 0)
363 res = be_new_Copy(isa->sp->reg_class, env->birg->irg, bl, res);
368 * Modify the irg itself and the frame type.
370 static void modify_irg(be_abi_irg_t *env)
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);
382 int reg_params_nr = 0;
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;
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);
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]));
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);
412 /* Get the ABI constraints from the ISA */
413 arch_isa_get_call_abi(isa, method_type, call);
416 const arch_register_t **callee_save = env->birg->main_env->callee_save;
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;
425 reg_params = be_new_RegParams(irg, n_reg_param);
426 reg_params_bl = get_nodes_block(reg_params);
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);
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);
439 /* memorize the callee save proj since they will be arguments to the Return nodes. */
440 obstack_ptr_grow(&env->obst, irn);
443 obstack_ptr_grow(&env->obst, NULL);
444 return_params = obstack_finish(&env->obst);
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);
453 /* reroute the edges from the original argument projs to the RegParam ones. */
454 for(i = 0; i < max_arg; ++i) {
456 assert(args_repl != NULL);
457 edges_reroute(args[i], args_repl[i], irg);
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;
467 int nr = get_Proj_proj(arg_proj);
469 nr = MIN(nr, n_params);
470 arg = get_call_arg(call, 0, nr);
471 param_type = get_method_param_type(method_type, nr);
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);
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);
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
492 assert(0 && "struct parameters are not supported");
497 obstack_free(&env->obst, args);
498 be_abi_call_free(call);
501 static void collect_alloca_walker(ir_node *irn, void *data)
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);
508 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
510 be_abi_irg_t *env = malloc(sizeof(env[0]));
513 ir_node **stack_allocs;
516 env->stack_ops = pset_new_ptr(32);
517 env->omit_framepointer = 1;
518 obstack_init(&env->obst);
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);
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;
531 for(i = 0; stack_allocs[i] != NULL; ++i)
532 implement_stack_alloc(env, stack_allocs[i]);
534 irg_walk_graph(env->birg->irg, NULL, adjust_call_walker, &env);
538 void be_abi_fix_stack(be_abi_irg_t *env)
540 pset *origs = pset_new_ptr_default();
542 pset_insert_ptr(origs, env->init_sp);
543 be_ssa_constr_sets(env->birg->dom_front, origs, env->stack_ops);
548 void be_abi_free(be_abi_irg_t *env)
550 del_pset(env->stack_ops);
551 obstack_free(&env->obst, NULL);