2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Backend ABI implementation.
23 * @author Sebastian Hack, Michael Beck
33 #include "irgraph_t.h"
36 #include "iredges_t.h"
39 #include "irprintf_t.h"
45 #include "raw_bitset.h"
54 #include "besched_t.h"
56 #include "bessaconstr.h"
58 typedef struct _be_abi_call_arg_t {
59 unsigned is_res : 1; /**< 1: the call argument is a return value. 0: it's a call parameter. */
60 unsigned in_reg : 1; /**< 1: this argument is transmitted in registers. */
61 unsigned on_stack : 1; /**< 1: this argument is transmitted on the stack. */
64 const arch_register_t *reg;
67 unsigned alignment; /**< stack alignment */
68 unsigned space_before; /**< allocate space before */
69 unsigned space_after; /**< allocate space after */
72 struct _be_abi_call_t {
73 be_abi_call_flags_t flags; /**< Flags describing the ABI behavior on calls */
74 int pop; /**< number of bytes the stack frame is shrinked by the callee on return. */
75 const be_abi_callbacks_t *cb;
76 ir_type *between_type;
78 const arch_register_class_t *cls_addr; /**< register class of the call address */
82 * The ABI information for the current birg.
84 struct _be_abi_irg_t {
86 be_irg_t *birg; /**< The back end IRG. */
87 const arch_env_t *arch_env;
88 survive_dce_t *dce_survivor;
90 be_abi_call_t *call; /**< The ABI call information. */
91 ir_type *method_type; /**< The type of the method of the IRG. */
93 ir_node *init_sp; /**< The node representing the stack pointer
94 at the start of the function. */
96 ir_node *reg_params; /**< The reg params node. */
97 pmap *regs; /**< A map of all callee-save and ignore regs to
98 their Projs to the RegParams node. */
100 int start_block_bias; /**< The stack bias at the end of the start block. */
102 void *cb; /**< ABI Callback self pointer. */
104 pmap *keep_map; /**< mapping blocks to keep nodes. */
105 pset *ignore_regs; /**< Additional registers which shall be ignored. */
107 ir_node **calls; /**< flexible array containing all be_Call nodes */
109 arch_register_req_t sp_req;
110 arch_register_req_t sp_cls_req;
112 be_stack_layout_t frame; /**< The stack frame model. */
114 DEBUG_ONLY(firm_dbg_module_t *dbg;) /**< The debugging module. */
117 static heights_t *ir_heights;
119 /** Flag: if set, try to omit the frame pointer in all routines. */
120 static int be_omit_fp = 1;
122 /** Flag: if set, try to omit the frame pointer in leaf routines only. */
123 static int be_omit_leaf_fp = 1;
126 _ ____ ___ ____ _ _ _ _
127 / \ | __ )_ _| / ___|__ _| | | |__ __ _ ___| | _____
128 / _ \ | _ \| | | | / _` | | | '_ \ / _` |/ __| |/ / __|
129 / ___ \| |_) | | | |__| (_| | | | |_) | (_| | (__| <\__ \
130 /_/ \_\____/___| \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
132 These callbacks are used by the backend to set the parameters
133 for a specific call type.
137 * Set compare function: compares two ABI call object arguments.
139 static int cmp_call_arg(const void *a, const void *b, size_t n)
141 const be_abi_call_arg_t *p = a, *q = b;
143 return !(p->is_res == q->is_res && p->pos == q->pos);
147 * Get an ABI call object argument.
149 * @param call the abi call
150 * @param is_res true for call results, false for call arguments
151 * @param pos position of the argument
153 static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
155 be_abi_call_arg_t arg;
158 memset(&arg, 0, sizeof(arg));
162 hash = is_res * 128 + pos;
164 return set_find(call->params, &arg, sizeof(arg), hash);
168 * Set an ABI call object argument.
170 * @param call the abi call
171 * @param is_res true for call results, false for call arguments
172 * @param pos position of the argument
174 static be_abi_call_arg_t *create_call_arg(be_abi_call_t *call, int is_res, int pos)
176 be_abi_call_arg_t arg;
179 memset(&arg, 0, sizeof(arg));
183 hash = is_res * 128 + pos;
185 return set_insert(call->params, &arg, sizeof(arg), hash);
188 /* Set the flags for a call. */
189 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
195 /* Sets the number of bytes the stackframe is shrinked by the callee on return */
196 void be_abi_call_set_pop(be_abi_call_t *call, int pop)
202 /* Set register class for call address */
203 void be_abi_call_set_call_address_reg_class(be_abi_call_t *call, const arch_register_class_t *cls)
205 call->cls_addr = cls;
209 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos, ir_mode *load_mode, unsigned alignment, unsigned space_before, unsigned space_after)
211 be_abi_call_arg_t *arg = create_call_arg(call, 0, arg_pos);
213 arg->load_mode = load_mode;
214 arg->alignment = alignment;
215 arg->space_before = space_before;
216 arg->space_after = space_after;
217 assert(alignment > 0 && "Alignment must be greater than 0");
220 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
222 be_abi_call_arg_t *arg = create_call_arg(call, 0, arg_pos);
227 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
229 be_abi_call_arg_t *arg = create_call_arg(call, 1, arg_pos);
234 /* Get the flags of a ABI call object. */
235 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
241 * Constructor for a new ABI call object.
243 * @param cls_addr register class of the call address
245 * @return the new ABI call object
247 static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
249 be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
252 call->params = new_set(cmp_call_arg, 16);
254 call->cls_addr = cls_addr;
256 call->flags.bits.try_omit_fp = be_omit_fp | be_omit_leaf_fp;
262 * Destructor for an ABI call object.
264 static void be_abi_call_free(be_abi_call_t *call)
266 del_set(call->params);
272 | ___| __ __ _ _ __ ___ ___ | | | | __ _ _ __ __| | (_)_ __ __ _
273 | |_ | '__/ _` | '_ ` _ \ / _ \ | |_| |/ _` | '_ \ / _` | | | '_ \ / _` |
274 | _|| | | (_| | | | | | | __/ | _ | (_| | | | | (_| | | | | | | (_| |
275 |_| |_| \__,_|_| |_| |_|\___| |_| |_|\__,_|_| |_|\__,_|_|_|_| |_|\__, |
278 Handling of the stack frame. It is composed of three types:
279 1) The type of the arguments which are pushed on the stack.
280 2) The "between type" which consists of stuff the call of the
281 function pushes on the stack (like the return address and
282 the old base pointer for ia32).
283 3) The Firm frame type which consists of all local variables
287 static int get_stack_entity_offset(be_stack_layout_t *frame, ir_entity *ent,
290 ir_type *t = get_entity_owner(ent);
291 int ofs = get_entity_offset(ent);
295 /* Find the type the entity is contained in. */
296 for (index = 0; index < N_FRAME_TYPES; ++index) {
297 if (frame->order[index] == t)
299 /* Add the size of all the types below the one of the entity to the entity's offset */
300 ofs += get_type_size_bytes(frame->order[index]);
303 /* correct the offset by the initial position of the frame pointer */
304 ofs -= frame->initial_offset;
306 /* correct the offset with the current bias. */
313 * Retrieve the entity with given offset from a frame type.
315 static ir_entity *search_ent_with_offset(ir_type *t, int offset)
319 for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
320 ir_entity *ent = get_compound_member(t, i);
321 if (get_entity_offset(ent) == offset)
328 static int stack_frame_compute_initial_offset(be_stack_layout_t *frame)
330 ir_type *base = frame->stack_dir < 0 ? frame->between_type : frame->frame_type;
331 ir_entity *ent = search_ent_with_offset(base, 0);
333 frame->initial_offset = ent ? get_stack_entity_offset(frame, ent, 0) : 0;
335 return frame->initial_offset;
339 * Initializes the frame layout from parts
341 * @param frame the stack layout that will be initialized
342 * @param args the stack argument layout type
343 * @param between the between layout type
344 * @param locals the method frame type
345 * @param stack_dir the stack direction: < 0 decreasing, > 0 increasing addresses
346 * @param param_map an array mapping method argument positions to the stack argument type
348 * @return the initialized stack layout
350 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
351 ir_type *between, ir_type *locals, int stack_dir,
352 ir_entity *param_map[])
354 frame->arg_type = args;
355 frame->between_type = between;
356 frame->frame_type = locals;
357 frame->initial_offset = 0;
358 frame->initial_bias = 0;
359 frame->stack_dir = stack_dir;
360 frame->order[1] = between;
361 frame->param_map = param_map;
364 frame->order[0] = args;
365 frame->order[2] = locals;
368 /* typical decreasing stack: locals have the
369 * lowest addresses, arguments the highest */
370 frame->order[0] = locals;
371 frame->order[2] = args;
377 /** Dumps the stack layout to file. */
378 static void stack_layout_dump(FILE *file, be_stack_layout_t *frame)
382 ir_fprintf(file, "initial offset: %d\n", frame->initial_offset);
383 for (j = 0; j < N_FRAME_TYPES; ++j) {
384 ir_type *t = frame->order[j];
386 ir_fprintf(file, "type %d: %F size: %d\n", j, t, get_type_size_bytes(t));
387 for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
388 ir_entity *ent = get_compound_member(t, i);
389 ir_fprintf(file, "\t%F int ofs: %d glob ofs: %d\n", ent, get_entity_offset_bytes(ent), get_stack_entity_offset(frame, ent, 0));
396 * Returns non-zero if the call argument at given position
397 * is transfered on the stack.
399 static inline int is_on_stack(be_abi_call_t *call, int pos)
401 be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
402 return arg && !arg->in_reg;
412 Adjustment of the calls inside a graph.
417 * Transform a call node into a be_Call node.
419 * @param env The ABI environment for the current irg.
420 * @param irn The call node.
421 * @param curr_sp The stack pointer node to use.
422 * @return The stack pointer after the call.
424 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
426 ir_graph *irg = env->birg->irg;
427 const arch_env_t *arch_env = env->birg->main_env->arch_env;
428 ir_type *call_tp = get_Call_type(irn);
429 ir_node *call_ptr = get_Call_ptr(irn);
430 int n_params = get_method_n_params(call_tp);
431 ir_node *curr_mem = get_Call_mem(irn);
432 ir_node *bl = get_nodes_block(irn);
434 int stack_dir = arch_env->stack_dir;
435 const arch_register_t *sp = arch_env->sp;
436 be_abi_call_t *call = be_abi_call_new(sp->reg_class);
437 ir_mode *mach_mode = sp->reg_class->mode;
438 struct obstack *obst = &env->obst;
439 int no_alloc = call->flags.bits.frame_is_setup_on_call;
440 int n_res = get_method_n_ress(call_tp);
441 int do_seq = call->flags.bits.store_args_sequential && !no_alloc;
443 ir_node *res_proj = NULL;
444 int n_reg_params = 0;
445 int n_stack_params = 0;
448 pset_new_t destroyed_regs, states;
449 pset_new_iterator_t iter;
453 int n_reg_results = 0;
454 const arch_register_t *reg;
455 const ir_edge_t *edge;
457 int *stack_param_idx;
458 int i, n, destroy_all_regs;
461 pset_new_init(&destroyed_regs);
462 pset_new_init(&states);
464 /* Let the isa fill out the abi description for that call node. */
465 arch_env_get_call_abi(arch_env, call_tp, call);
467 /* Insert code to put the stack arguments on the stack. */
468 assert(get_Call_n_params(irn) == n_params);
469 for (i = 0; i < n_params; ++i) {
470 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
473 int arg_size = get_type_size_bytes(get_method_param_type(call_tp, i));
475 stack_size += round_up2(arg->space_before, arg->alignment);
476 stack_size += round_up2(arg_size, arg->alignment);
477 stack_size += round_up2(arg->space_after, arg->alignment);
478 obstack_int_grow(obst, i);
482 stack_param_idx = obstack_finish(obst);
484 /* Collect all arguments which are passed in registers. */
485 for (i = 0; i < n_params; ++i) {
486 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
487 if (arg && arg->in_reg) {
488 obstack_int_grow(obst, i);
492 reg_param_idxs = obstack_finish(obst);
495 * If the stack is decreasing and we do not want to store sequentially,
496 * or someone else allocated the call frame
497 * we allocate as much space on the stack all parameters need, by
498 * moving the stack pointer along the stack's direction.
500 * Note: we also have to do this for stack_size == 0, because we may have
501 * to adjust stack alignment for the call.
503 if (stack_dir < 0 && !do_seq && !no_alloc) {
504 curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
507 dbgi = get_irn_dbg_info(irn);
508 /* If there are some parameters which shall be passed on the stack. */
509 if (n_stack_params > 0) {
513 * Reverse list of stack parameters if call arguments are from left to right.
514 * We must them reverse again if they are pushed (not stored) and the stack
515 * direction is downwards.
517 if (call->flags.bits.left_to_right ^ (do_seq && stack_dir < 0)) {
518 for (i = 0; i < n_stack_params >> 1; ++i) {
519 int other = n_stack_params - i - 1;
520 int tmp = stack_param_idx[i];
521 stack_param_idx[i] = stack_param_idx[other];
522 stack_param_idx[other] = tmp;
526 curr_mem = get_Call_mem(irn);
528 obstack_ptr_grow(obst, curr_mem);
531 for (i = 0; i < n_stack_params; ++i) {
532 int p = stack_param_idx[i];
533 be_abi_call_arg_t *arg = get_call_arg(call, 0, p);
534 ir_node *param = get_Call_param(irn, p);
535 ir_node *addr = curr_sp;
537 ir_type *param_type = get_method_param_type(call_tp, p);
538 int param_size = get_type_size_bytes(param_type) + arg->space_after;
541 * If we wanted to build the arguments sequentially,
542 * the stack pointer for the next must be incremented,
543 * and the memory value propagated.
547 addr = curr_sp = be_new_IncSP(sp, bl, curr_sp, param_size + arg->space_before, 0);
548 add_irn_dep(curr_sp, curr_mem);
551 curr_ofs += arg->space_before;
552 curr_ofs = round_up2(curr_ofs, arg->alignment);
554 /* Make the expression to compute the argument's offset. */
556 ir_mode *constmode = mach_mode;
557 if (mode_is_reference(mach_mode)) {
560 addr = new_r_Const_long(irg, constmode, curr_ofs);
561 addr = new_r_Add(bl, curr_sp, addr, mach_mode);
565 /* Insert a store for primitive arguments. */
566 if (is_atomic_type(param_type)) {
568 ir_node *mem_input = do_seq ? curr_mem : new_NoMem();
569 store = new_rd_Store(dbgi, bl, mem_input, addr, param, 0);
570 mem = new_r_Proj(bl, store, mode_M, pn_Store_M);
573 /* Make a mem copy for compound arguments. */
577 assert(mode_is_reference(get_irn_mode(param)));
578 copy = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type);
579 mem = new_r_Proj(bl, copy, mode_M, pn_CopyB_M_regular);
582 curr_ofs += param_size;
587 obstack_ptr_grow(obst, mem);
590 in = (ir_node **) obstack_finish(obst);
592 /* We need the sync only, if we didn't build the stores sequentially. */
594 if (n_stack_params >= 1) {
595 curr_mem = new_r_Sync(bl, n_stack_params + 1, in);
597 curr_mem = get_Call_mem(irn);
600 obstack_free(obst, in);
603 /* check for the return_twice property */
604 destroy_all_regs = 0;
605 if (is_SymConst_addr_ent(call_ptr)) {
606 ir_entity *ent = get_SymConst_entity(call_ptr);
608 if (get_entity_additional_properties(ent) & mtp_property_returns_twice)
609 destroy_all_regs = 1;
611 ir_type *call_tp = get_Call_type(irn);
613 if (get_method_additional_properties(call_tp) & mtp_property_returns_twice)
614 destroy_all_regs = 1;
617 /* Put caller save into the destroyed set and state registers in the states set */
618 for (i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
620 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
621 for (j = 0; j < cls->n_regs; ++j) {
622 const arch_register_t *reg = arch_register_for_index(cls, j);
624 if (destroy_all_regs || arch_register_type_is(reg, caller_save)) {
625 if (! arch_register_type_is(reg, ignore))
626 pset_new_insert(&destroyed_regs, (void *) reg);
628 if (arch_register_type_is(reg, state)) {
629 pset_new_insert(&destroyed_regs, (void*) reg);
630 pset_new_insert(&states, (void*) reg);
635 if (destroy_all_regs) {
636 /* even if destroyed all is specified, neither SP nor FP are destroyed (else bad things will happen) */
637 pset_new_remove(&destroyed_regs, arch_env->sp);
638 pset_new_remove(&destroyed_regs, arch_env->bp);
641 /* search the largest result proj number */
642 res_projs = ALLOCANZ(ir_node*, n_res);
644 foreach_out_edge(irn, edge) {
645 const ir_edge_t *res_edge;
646 ir_node *irn = get_edge_src_irn(edge);
648 if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
651 foreach_out_edge(irn, res_edge) {
653 ir_node *res = get_edge_src_irn(res_edge);
655 assert(is_Proj(res));
657 proj = get_Proj_proj(res);
658 assert(proj < n_res);
659 assert(res_projs[proj] == NULL);
660 res_projs[proj] = res;
666 /** TODO: this is not correct for cases where return values are passed
667 * on the stack, but no known ABI does this currently...
669 n_reg_results = n_res;
671 /* make the back end call node and set its register requirements. */
672 for (i = 0; i < n_reg_params; ++i) {
673 obstack_ptr_grow(obst, get_Call_param(irn, reg_param_idxs[i]));
676 /* add state registers ins */
677 foreach_pset_new(&states, reg, iter) {
678 const arch_register_class_t *cls = arch_register_get_class(reg);
680 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
681 ir_fprintf(stderr, "Adding %+F\n", regnode);
683 ir_node *regnode = new_r_Unknown(irg, arch_register_class_mode(cls));
684 obstack_ptr_grow(obst, regnode);
686 n_ins = n_reg_params + pset_new_size(&states);
688 in = obstack_finish(obst);
690 /* ins collected, build the call */
691 if (env->call->flags.bits.call_has_imm && is_SymConst(call_ptr)) {
693 low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, curr_sp,
694 n_reg_results + pn_be_Call_first_res + pset_new_size(&destroyed_regs),
695 n_ins, in, get_Call_type(irn));
696 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
699 low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, call_ptr,
700 n_reg_results + pn_be_Call_first_res + pset_new_size(&destroyed_regs),
701 n_ins, in, get_Call_type(irn));
703 be_Call_set_pop(low_call, call->pop);
705 /* put the call into the list of all calls for later processing */
706 ARR_APP1(ir_node *, env->calls, low_call);
708 /* create new stack pointer */
709 curr_sp = new_r_Proj(bl, low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
710 be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
711 arch_register_req_type_ignore | arch_register_req_type_produces_sp);
712 arch_set_irn_register(curr_sp, sp);
714 /* now handle results */
715 for (i = 0; i < n_res; ++i) {
717 ir_node *proj = res_projs[i];
718 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
720 /* returns values on stack not supported yet */
724 shift the proj number to the right, since we will drop the
725 unspeakable Proj_T from the Call. Therefore, all real argument
726 Proj numbers must be increased by pn_be_Call_first_res
728 pn = i + pn_be_Call_first_res;
731 ir_type *res_type = get_method_res_type(call_tp, i);
732 ir_mode *mode = get_type_mode(res_type);
733 proj = new_r_Proj(bl, low_call, mode, pn);
736 set_Proj_pred(proj, low_call);
737 set_Proj_proj(proj, pn);
741 pset_new_remove(&destroyed_regs, arg->reg);
746 Set the register class of the call address to
747 the backend provided class (default: stack pointer class)
749 be_node_set_reg_class_in(low_call, be_pos_Call_ptr, call->cls_addr);
751 DBG((env->dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
753 /* Set the register classes and constraints of the Call parameters. */
754 for (i = 0; i < n_reg_params; ++i) {
755 int index = reg_param_idxs[i];
756 be_abi_call_arg_t *arg = get_call_arg(call, 0, index);
757 assert(arg->reg != NULL);
759 be_set_constr_single_reg_in(low_call, be_pos_Call_first_arg + i,
763 /* Set the register constraints of the results. */
764 for (i = 0; i < n_res; ++i) {
765 ir_node *proj = res_projs[i];
766 const be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
767 int pn = get_Proj_proj(proj);
770 be_set_constr_single_reg_out(low_call, pn, arg->reg, 0);
771 arch_set_irn_register(proj, arg->reg);
773 obstack_free(obst, in);
774 exchange(irn, low_call);
776 /* kill the ProjT node */
777 if (res_proj != NULL) {
781 /* Make additional projs for the caller save registers
782 and the Keep node which keeps them alive. */
784 const arch_register_t *reg;
788 int curr_res_proj = pn_be_Call_first_res + n_reg_results;
789 pset_new_iterator_t iter;
791 /* also keep the stack pointer */
793 set_irn_link(curr_sp, (void*) sp);
794 obstack_ptr_grow(obst, curr_sp);
796 foreach_pset_new(&destroyed_regs, reg, iter) {
797 ir_node *proj = new_r_Proj(bl, low_call, reg->reg_class->mode, curr_res_proj);
799 /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
800 be_set_constr_single_reg_out(low_call, curr_res_proj, reg, 0);
801 arch_set_irn_register(proj, reg);
803 set_irn_link(proj, (void*) reg);
804 obstack_ptr_grow(obst, proj);
809 for (i = 0; i < n_reg_results; ++i) {
810 ir_node *proj = res_projs[i];
811 const arch_register_t *reg = arch_get_irn_register(proj);
812 set_irn_link(proj, (void*) reg);
813 obstack_ptr_grow(obst, proj);
817 /* create the Keep for the caller save registers */
818 in = (ir_node **) obstack_finish(obst);
819 keep = be_new_Keep(NULL, bl, n, in);
820 for (i = 0; i < n; ++i) {
821 const arch_register_t *reg = get_irn_link(in[i]);
822 be_node_set_reg_class_in(keep, i, reg->reg_class);
824 obstack_free(obst, in);
827 /* Clean up the stack. */
828 assert(stack_size >= call->pop);
829 stack_size -= call->pop;
831 if (stack_size > 0) {
832 ir_node *mem_proj = NULL;
834 foreach_out_edge(low_call, edge) {
835 ir_node *irn = get_edge_src_irn(edge);
836 if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
843 mem_proj = new_r_Proj(bl, low_call, mode_M, pn_be_Call_M_regular);
844 keep_alive(mem_proj);
847 /* Clean up the stack frame or revert alignment fixes if we allocated it */
849 curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
852 be_abi_call_free(call);
853 obstack_free(obst, stack_param_idx);
855 pset_new_destroy(&states);
856 pset_new_destroy(&destroyed_regs);
862 * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
864 * @param alignment the minimum stack alignment
865 * @param size the node containing the non-aligned size
866 * @param block the block where new nodes are allocated on
867 * @param dbg debug info for new nodes
869 * @return a node representing the aligned size
871 static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
872 ir_node *block, dbg_info *dbg)
874 if (stack_alignment > 1) {
880 assert(is_po2(stack_alignment));
882 mode = get_irn_mode(size);
883 tv = new_tarval_from_long(stack_alignment-1, mode);
884 irg = get_Block_irg(block);
885 mask = new_r_Const(irg, tv);
886 size = new_rd_Add(dbg, block, size, mask, mode);
888 tv = new_tarval_from_long(-(long)stack_alignment, mode);
889 mask = new_r_Const(irg, tv);
890 size = new_rd_And(dbg, block, size, mask, mode);
896 * The alloca is transformed into a back end alloca node and connected to the stack nodes.
898 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
907 const ir_edge_t *edge;
908 ir_node *new_alloc, *size, *addr, *ins[2];
909 unsigned stack_alignment;
911 assert(get_Alloc_where(alloc) == stack_alloc);
913 block = get_nodes_block(alloc);
914 irg = get_Block_irg(block);
917 type = get_Alloc_type(alloc);
919 foreach_out_edge(alloc, edge) {
920 ir_node *irn = get_edge_src_irn(edge);
922 assert(is_Proj(irn));
923 switch (get_Proj_proj(irn)) {
935 /* Beware: currently Alloc nodes without a result might happen,
936 only escape analysis kills them and this phase runs only for object
937 oriented source. We kill the Alloc here. */
938 if (alloc_res == NULL && alloc_mem) {
939 exchange(alloc_mem, get_Alloc_mem(alloc));
943 dbg = get_irn_dbg_info(alloc);
944 size = get_Alloc_size(alloc);
946 /* we might need to multiply the size with the element size */
947 if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
948 ir_mode *mode = get_irn_mode(size);
949 tarval *tv = new_tarval_from_long(get_type_size_bytes(type),
951 ir_node *cnst = new_rd_Const(dbg, irg, tv);
952 size = new_rd_Mul(dbg, block, size, cnst, mode);
955 /* The stack pointer will be modified in an unknown manner.
956 We cannot omit it. */
957 env->call->flags.bits.try_omit_fp = 0;
959 stack_alignment = 1 << env->arch_env->stack_alignment;
960 size = adjust_alloc_size(stack_alignment, size, block, dbg);
961 new_alloc = be_new_AddSP(env->arch_env->sp, block, curr_sp, size);
962 set_irn_dbg_info(new_alloc, dbg);
964 if (alloc_mem != NULL) {
968 addsp_mem = new_r_Proj(block, new_alloc, mode_M, pn_be_AddSP_M);
970 /* We need to sync the output mem of the AddSP with the input mem
971 edge into the alloc node. */
972 ins[0] = get_Alloc_mem(alloc);
974 sync = new_r_Sync(block, 2, ins);
976 exchange(alloc_mem, sync);
979 exchange(alloc, new_alloc);
981 /* fix projnum of alloca res */
982 set_Proj_proj(alloc_res, pn_be_AddSP_res);
985 curr_sp = new_r_Proj(block, new_alloc, get_irn_mode(curr_sp),
993 * The Free is transformed into a back end free node and connected to the stack nodes.
995 static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
999 ir_node *subsp, *mem, *res, *size, *sync;
1003 unsigned stack_alignment;
1006 assert(get_Free_where(free) == stack_alloc);
1008 block = get_nodes_block(free);
1009 irg = get_irn_irg(block);
1010 type = get_Free_type(free);
1011 sp_mode = env->arch_env->sp->reg_class->mode;
1012 dbg = get_irn_dbg_info(free);
1014 /* we might need to multiply the size with the element size */
1015 if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
1016 tarval *tv = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
1017 ir_node *cnst = new_rd_Const(dbg, irg, tv);
1018 ir_node *mul = new_rd_Mul(dbg, block, get_Free_size(free),
1022 size = get_Free_size(free);
1025 stack_alignment = 1 << env->arch_env->stack_alignment;
1026 size = adjust_alloc_size(stack_alignment, size, block, dbg);
1028 /* The stack pointer will be modified in an unknown manner.
1029 We cannot omit it. */
1030 env->call->flags.bits.try_omit_fp = 0;
1031 subsp = be_new_SubSP(env->arch_env->sp, block, curr_sp, size);
1032 set_irn_dbg_info(subsp, dbg);
1034 mem = new_r_Proj(block, subsp, mode_M, pn_be_SubSP_M);
1035 res = new_r_Proj(block, subsp, sp_mode, pn_be_SubSP_sp);
1037 /* we need to sync the memory */
1038 in[0] = get_Free_mem(free);
1040 sync = new_r_Sync(block, 2, in);
1042 /* and make the AddSP dependent on the former memory */
1043 add_irn_dep(subsp, get_Free_mem(free));
1046 exchange(free, sync);
1052 /* the following function is replaced by the usage of the heights module */
1055 * Walker for dependent_on().
1056 * This function searches a node tgt recursively from a given node
1057 * but is restricted to the given block.
1058 * @return 1 if tgt was reachable from curr, 0 if not.
1060 static int check_dependence(ir_node *curr, ir_node *tgt, ir_node *bl)
1064 if (get_nodes_block(curr) != bl)
1070 /* Phi functions stop the recursion inside a basic block */
1071 if (! is_Phi(curr)) {
1072 for (i = 0, n = get_irn_arity(curr); i < n; ++i) {
1073 if (check_dependence(get_irn_n(curr, i), tgt, bl))
1083 * Check if a node is somehow data dependent on another one.
1084 * both nodes must be in the same basic block.
1085 * @param n1 The first node.
1086 * @param n2 The second node.
1087 * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
1089 static int dependent_on(ir_node *n1, ir_node *n2)
1091 assert(get_nodes_block(n1) == get_nodes_block(n2));
1093 return heights_reachable_in_block(ir_heights, n1, n2);
1096 static int cmp_call_dependency(const void *c1, const void *c2)
1098 ir_node *n1 = *(ir_node **) c1;
1099 ir_node *n2 = *(ir_node **) c2;
1102 Classical qsort() comparison function behavior:
1103 0 if both elements are equal
1104 1 if second is "smaller" that first
1105 -1 if first is "smaller" that second
1107 if (dependent_on(n1, n2))
1110 if (dependent_on(n2, n1))
1113 /* The nodes have no depth order, but we need a total order because qsort()
1115 return get_irn_idx(n1) - get_irn_idx(n2);
1119 * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
1120 * Clears the irg_is_leaf flag if a Call is detected.
1122 static void link_ops_in_block_walker(ir_node *irn, void *data)
1124 be_abi_irg_t *env = data;
1125 ir_opcode code = get_irn_opcode(irn);
1127 if (code == iro_Call ||
1128 (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
1129 (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
1130 ir_node *bl = get_nodes_block(irn);
1131 void *save = get_irn_link(bl);
1133 if (code == iro_Call)
1134 env->call->flags.bits.irg_is_leaf = 0;
1136 set_irn_link(irn, save);
1137 set_irn_link(bl, irn);
1140 if (code == iro_Builtin && get_Builtin_kind(irn) == ir_bk_return_address) {
1141 ir_node *param = get_Builtin_param(irn, 0);
1142 tarval *tv = get_Const_tarval(param);
1143 unsigned long value = get_tarval_long(tv);
1144 /* use ebp, so the climbframe algo works... */
1146 env->call->flags.bits.try_omit_fp = 0;
1153 * Process all Call/Alloc/Free nodes inside a basic block.
1154 * Note that the link field of the block must contain a linked list of all
1155 * Call nodes inside the Block. We first order this list according to data dependency
1156 * and that connect the calls together.
1158 static void process_ops_in_block(ir_node *bl, void *data)
1160 be_abi_irg_t *env = data;
1161 ir_node *curr_sp = env->init_sp;
1165 for (irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
1166 obstack_ptr_grow(&env->obst, irn);
1168 /* If there were call nodes in the block. */
1174 nodes = obstack_finish(&env->obst);
1176 /* order the call nodes according to data dependency */
1177 qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependency);
1179 for (i = n - 1; i >= 0; --i) {
1180 ir_node *irn = nodes[i];
1182 DBG((env->dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1183 switch (get_irn_opcode(irn)) {
1186 /* The stack pointer will be modified due to a call. */
1187 env->call->flags.bits.try_omit_fp = 0;
1189 curr_sp = adjust_call(env, irn, curr_sp);
1192 if (get_Alloc_where(irn) == stack_alloc)
1193 curr_sp = adjust_alloc(env, irn, curr_sp);
1196 if (get_Free_where(irn) == stack_alloc)
1197 curr_sp = adjust_free(env, irn, curr_sp);
1200 panic("invalid call");
1205 obstack_free(&env->obst, nodes);
1207 /* Keep the last stack state in the block by tying it to Keep node,
1208 * the proj from calls is already kept */
1209 if (curr_sp != env->init_sp &&
1210 !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1212 keep = be_new_Keep(env->arch_env->sp->reg_class, bl, 1, nodes);
1213 pmap_insert(env->keep_map, bl, keep);
1217 set_irn_link(bl, curr_sp);
1218 } /* process_ops_in_block */
1221 * Adjust all call nodes in the graph to the ABI conventions.
1223 static void process_calls(be_abi_irg_t *env)
1225 ir_graph *irg = env->birg->irg;
1227 env->call->flags.bits.irg_is_leaf = 1;
1228 irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, env);
1230 ir_heights = heights_new(env->birg->irg);
1231 irg_block_walk_graph(irg, NULL, process_ops_in_block, env);
1232 heights_free(ir_heights);
1236 * Computes the stack argument layout type.
1237 * Changes a possibly allocated value param type by moving
1238 * entities to the stack layout type.
1240 * @param env the ABI environment
1241 * @param call the current call ABI
1242 * @param method_type the method type
1243 * @param val_param_tp the value parameter type, will be destroyed
1244 * @param param_map an array mapping method arguments to the stack layout type
1246 * @return the stack argument layout type
1248 static ir_type *compute_arg_type(be_abi_irg_t *env, be_abi_call_t *call,
1249 ir_type *method_type, ir_type *val_param_tp,
1250 ir_entity ***param_map)
1252 int dir = env->call->flags.bits.left_to_right ? 1 : -1;
1253 int inc = env->birg->main_env->arch_env->stack_dir * dir;
1254 int n = get_method_n_params(method_type);
1255 int curr = inc > 0 ? 0 : n - 1;
1261 ident *id = get_entity_ident(get_irg_entity(env->birg->irg));
1264 *param_map = map = obstack_alloc(&env->obst, n * sizeof(ir_entity *));
1265 res = new_type_struct(id_mangle_u(id, new_id_from_chars("arg_type", 8)));
1266 for (i = 0; i < n; ++i, curr += inc) {
1267 ir_type *param_type = get_method_param_type(method_type, curr);
1268 be_abi_call_arg_t *arg = get_call_arg(call, 0, curr);
1271 if (arg->on_stack) {
1272 if (val_param_tp != NULL) {
1273 /* the entity was already created, create a copy in the param type */
1274 ir_entity *val_ent = get_method_value_param_ent(method_type, i);
1275 arg->stack_ent = copy_entity_own(val_ent, res);
1276 set_entity_link(val_ent, arg->stack_ent);
1277 set_entity_link(arg->stack_ent, NULL);
1278 /* must be automatic to set a fixed layout */
1279 set_entity_allocation(arg->stack_ent, allocation_automatic);
1281 /* create a new entity */
1282 snprintf(buf, sizeof(buf), "param_%d", i);
1283 arg->stack_ent = new_entity(res, new_id_from_str(buf), param_type);
1285 ofs += arg->space_before;
1286 ofs = round_up2(ofs, arg->alignment);
1287 set_entity_offset(arg->stack_ent, ofs);
1288 ofs += arg->space_after;
1289 ofs += get_type_size_bytes(param_type);
1290 map[i] = arg->stack_ent;
1293 set_type_size_bytes(res, ofs);
1294 set_type_state(res, layout_fixed);
1299 const arch_register_t *reg;
1303 static int cmp_regs(const void *a, const void *b)
1305 const reg_node_map_t *p = a;
1306 const reg_node_map_t *q = b;
1308 if (p->reg->reg_class == q->reg->reg_class)
1309 return p->reg->index - q->reg->index;
1311 return p->reg->reg_class - q->reg->reg_class;
1314 static reg_node_map_t *reg_map_to_arr(struct obstack *obst, pmap *reg_map)
1317 int n = pmap_count(reg_map);
1319 reg_node_map_t *res = obstack_alloc(obst, n * sizeof(res[0]));
1321 foreach_pmap(reg_map, ent) {
1322 res[i].reg = ent->key;
1323 res[i].irn = ent->value;
1327 qsort(res, n, sizeof(res[0]), cmp_regs);
1332 * Creates a barrier.
1334 static ir_node *create_barrier(be_abi_irg_t *env, ir_node *bl, ir_node **mem, pmap *regs, int in_req)
1336 int n_regs = pmap_count(regs);
1342 rm = reg_map_to_arr(&env->obst, regs);
1344 for (n = 0; n < n_regs; ++n)
1345 obstack_ptr_grow(&env->obst, rm[n].irn);
1348 obstack_ptr_grow(&env->obst, *mem);
1352 in = (ir_node **) obstack_finish(&env->obst);
1353 irn = be_new_Barrier(bl, n, in);
1354 obstack_free(&env->obst, in);
1356 for (n = 0; n < n_regs; ++n) {
1357 ir_node *pred = rm[n].irn;
1358 const arch_register_t *reg = rm[n].reg;
1359 arch_register_type_t add_type = 0;
1362 /* stupid workaround for now... as not all nodes report register
1364 if (!is_Phi(pred)) {
1365 const arch_register_req_t *ireq = arch_get_register_req_out(pred);
1366 if (ireq->type & arch_register_req_type_ignore)
1367 add_type |= arch_register_req_type_ignore;
1368 if (ireq->type & arch_register_req_type_produces_sp)
1369 add_type |= arch_register_req_type_produces_sp;
1372 proj = new_r_Proj(bl, irn, get_irn_mode(pred), n);
1373 be_node_set_reg_class_in(irn, n, reg->reg_class);
1375 be_set_constr_single_reg_in(irn, n, reg, 0);
1376 be_set_constr_single_reg_out(irn, n, reg, add_type);
1377 arch_set_irn_register(proj, reg);
1379 pmap_insert(regs, (void *) reg, proj);
1383 *mem = new_r_Proj(bl, irn, mode_M, n);
1386 obstack_free(&env->obst, rm);
1391 * Creates a be_Return for a Return node.
1393 * @param @env the abi environment
1394 * @param irn the Return node or NULL if there was none
1395 * @param bl the block where the be_Retun should be placed
1396 * @param mem the current memory
1397 * @param n_res number of return results
1399 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1400 ir_node *mem, int n_res)
1402 be_abi_call_t *call = env->call;
1403 const arch_env_t *arch_env = env->birg->main_env->arch_env;
1405 pmap *reg_map = pmap_create();
1406 ir_node *keep = pmap_get(env->keep_map, bl);
1413 const arch_register_t **regs;
1417 get the valid stack node in this block.
1418 If we had a call in that block there is a Keep constructed by process_calls()
1419 which points to the last stack modification in that block. we'll use
1420 it then. Else we use the stack from the start block and let
1421 the ssa construction fix the usage.
1423 stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1425 stack = get_irn_n(keep, 0);
1427 remove_End_keepalive(get_irg_end(env->birg->irg), keep);
1430 /* Insert results for Return into the register map. */
1431 for (i = 0; i < n_res; ++i) {
1432 ir_node *res = get_Return_res(irn, i);
1433 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1434 assert(arg->in_reg && "return value must be passed in register");
1435 pmap_insert(reg_map, (void *) arg->reg, res);
1438 /* Add uses of the callee save registers. */
1439 foreach_pmap(env->regs, ent) {
1440 const arch_register_t *reg = ent->key;
1441 if (arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
1442 pmap_insert(reg_map, ent->key, ent->value);
1445 be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1447 /* Make the Epilogue node and call the arch's epilogue maker. */
1448 create_barrier(env, bl, &mem, reg_map, 1);
1449 call->cb->epilogue(env->cb, bl, &mem, reg_map);
1452 Maximum size of the in array for Return nodes is
1453 return args + callee save/ignore registers + memory + stack pointer
1455 in_max = pmap_count(reg_map) + n_res + 2;
1457 in = obstack_alloc(&env->obst, in_max * sizeof(in[0]));
1458 regs = obstack_alloc(&env->obst, in_max * sizeof(regs[0]));
1461 in[1] = be_abi_reg_map_get(reg_map, arch_env->sp);
1463 regs[1] = arch_env->sp;
1466 /* clear SP entry, since it has already been grown. */
1467 pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1468 for (i = 0; i < n_res; ++i) {
1469 be_abi_call_arg_t *arg = get_call_arg(call, 1, i);
1471 in[n] = be_abi_reg_map_get(reg_map, arg->reg);
1472 regs[n++] = arg->reg;
1474 /* Clear the map entry to mark the register as processed. */
1475 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1478 /* grow the rest of the stuff. */
1479 foreach_pmap(reg_map, ent) {
1482 regs[n++] = ent->key;
1486 /* The in array for the new back end return is now ready. */
1488 dbgi = get_irn_dbg_info(irn);
1492 /* we have to pop the shadow parameter in in case of struct returns */
1494 ret = be_new_Return(dbgi, env->birg->irg, bl, n_res, pop, n, in);
1496 /* Set the register classes of the return's parameter accordingly. */
1497 for (i = 0; i < n; ++i) {
1498 if (regs[i] == NULL)
1501 be_node_set_reg_class_in(ret, i, regs[i]->reg_class);
1504 /* Free the space of the Epilog's in array and the register <-> proj map. */
1505 obstack_free(&env->obst, in);
1506 pmap_destroy(reg_map);
1511 typedef struct ent_pos_pair ent_pos_pair;
1512 struct ent_pos_pair {
1513 ir_entity *ent; /**< a value param entity */
1514 int pos; /**< its parameter number */
1515 ent_pos_pair *next; /**< for linking */
1518 typedef struct lower_frame_sels_env_t {
1519 ent_pos_pair *value_param_list; /**< the list of all value param entities */
1520 ir_node *frame; /**< the current frame */
1521 const arch_register_class_t *sp_class; /**< register class of the stack pointer */
1522 const arch_register_class_t *link_class; /**< register class of the link pointer */
1523 ir_type *value_tp; /**< the value type if any */
1524 ir_type *frame_tp; /**< the frame type */
1525 int static_link_pos; /**< argument number of the hidden static link */
1526 } lower_frame_sels_env_t;
1529 * Return an entity from the backend for an value param entity.
1531 * @param ent an value param type entity
1532 * @param ctx context
1534 static ir_entity *get_argument_entity(ir_entity *ent, lower_frame_sels_env_t *ctx)
1536 ir_entity *argument_ent = get_entity_link(ent);
1538 if (argument_ent == NULL) {
1539 /* we have NO argument entity yet: This is bad, as we will
1540 * need one for backing store.
1543 ir_type *frame_tp = ctx->frame_tp;
1544 unsigned offset = get_type_size_bytes(frame_tp);
1545 ir_type *tp = get_entity_type(ent);
1546 unsigned align = get_type_alignment_bytes(tp);
1548 offset += align - 1;
1549 offset &= ~(align - 1);
1551 argument_ent = copy_entity_own(ent, frame_tp);
1553 /* must be automatic to set a fixed layout */
1554 set_entity_allocation(argument_ent, allocation_automatic);
1555 set_entity_offset(argument_ent, offset);
1556 offset += get_type_size_bytes(tp);
1558 set_type_size_bytes(frame_tp, offset);
1559 set_entity_link(ent, argument_ent);
1561 return argument_ent;
1564 * Walker: Replaces Sels of frame type and
1565 * value param type entities by FrameAddress.
1566 * Links all used entities.
1568 static void lower_frame_sels_walker(ir_node *irn, void *data)
1570 lower_frame_sels_env_t *ctx = data;
1573 ir_node *ptr = get_Sel_ptr(irn);
1575 if (ptr == ctx->frame) {
1576 ir_entity *ent = get_Sel_entity(irn);
1577 ir_node *bl = get_nodes_block(irn);
1580 int is_value_param = 0;
1582 if (get_entity_owner(ent) == ctx->value_tp) {
1585 /* replace by its copy from the argument type */
1586 pos = get_struct_member_index(ctx->value_tp, ent);
1587 ent = get_argument_entity(ent, ctx);
1590 nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1593 /* check, if it's a param Sel and if have not seen this entity before */
1594 if (is_value_param && get_entity_link(ent) == NULL) {
1600 ARR_APP1(ent_pos_pair, ctx->value_param_list, pair);
1602 set_entity_link(ent, ctx->value_param_list);
1609 * Check if a value parameter is transmitted as a register.
1610 * This might happen if the address of an parameter is taken which is
1611 * transmitted in registers.
1613 * Note that on some architectures this case must be handled specially
1614 * because the place of the backing store is determined by their ABI.
1616 * In the default case we move the entity to the frame type and create
1617 * a backing store into the first block.
1619 static void fix_address_of_parameter_access(be_abi_irg_t *env, ent_pos_pair *value_param_list)
1621 be_abi_call_t *call = env->call;
1622 ir_graph *irg = env->birg->irg;
1623 ent_pos_pair *entry, *new_list;
1625 int i, n = ARR_LEN(value_param_list);
1626 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1629 for (i = 0; i < n; ++i) {
1630 int pos = value_param_list[i].pos;
1631 be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
1634 DBG((dbg, LEVEL_2, "\targ #%d need backing store\n", pos));
1635 value_param_list[i].next = new_list;
1636 new_list = &value_param_list[i];
1639 if (new_list != NULL) {
1640 /* ok, change the graph */
1641 ir_node *start_bl = get_irg_start_block(irg);
1642 ir_node *first_bl = NULL;
1643 ir_node *frame, *imem, *nmem, *store, *mem, *args, *args_bl;
1644 const ir_edge_t *edge;
1645 optimization_state_t state;
1648 foreach_block_succ(start_bl, edge) {
1649 first_bl = get_edge_src_irn(edge);
1652 assert(first_bl && first_bl != start_bl);
1653 /* we had already removed critical edges, so the following
1654 assertion should be always true. */
1655 assert(get_Block_n_cfgpreds(first_bl) == 1);
1657 /* now create backing stores */
1658 frame = get_irg_frame(irg);
1659 imem = get_irg_initial_mem(irg);
1661 save_optimization_state(&state);
1663 nmem = new_r_Proj(start_bl, get_irg_start(irg), mode_M, pn_Start_M);
1664 restore_optimization_state(&state);
1666 /* reroute all edges to the new memory source */
1667 edges_reroute(imem, nmem, irg);
1671 args = get_irg_args(irg);
1672 args_bl = get_nodes_block(args);
1673 for (entry = new_list; entry != NULL; entry = entry->next) {
1675 ir_type *tp = get_entity_type(entry->ent);
1676 ir_mode *mode = get_type_mode(tp);
1679 /* address for the backing store */
1680 addr = be_new_FrameAddr(env->arch_env->sp->reg_class, first_bl, frame, entry->ent);
1683 mem = new_r_Proj(first_bl, store, mode_M, pn_Store_M);
1685 /* the backing store itself */
1686 store = new_r_Store(first_bl, mem, addr,
1687 new_r_Proj(args_bl, args, mode, i), 0);
1689 /* the new memory Proj gets the last Proj from store */
1690 set_Proj_pred(nmem, store);
1691 set_Proj_proj(nmem, pn_Store_M);
1693 /* move all entities to the frame type */
1694 frame_tp = get_irg_frame_type(irg);
1695 offset = get_type_size_bytes(frame_tp);
1697 /* we will add new entities: set the layout to undefined */
1698 assert(get_type_state(frame_tp) == layout_fixed);
1699 set_type_state(frame_tp, layout_undefined);
1700 for (entry = new_list; entry != NULL; entry = entry->next) {
1701 ir_entity *ent = entry->ent;
1703 /* If the entity is still on the argument type, move it to the frame type.
1704 This happens if the value_param type was build due to compound
1706 if (get_entity_owner(ent) != frame_tp) {
1707 ir_type *tp = get_entity_type(ent);
1708 unsigned align = get_type_alignment_bytes(tp);
1710 offset += align - 1;
1711 offset &= ~(align - 1);
1712 set_entity_owner(ent, frame_tp);
1713 add_class_member(frame_tp, ent);
1714 /* must be automatic to set a fixed layout */
1715 set_entity_allocation(ent, allocation_automatic);
1716 set_entity_offset(ent, offset);
1717 offset += get_type_size_bytes(tp);
1720 set_type_size_bytes(frame_tp, offset);
1721 /* fix the layout again */
1722 set_type_state(frame_tp, layout_fixed);
1727 * The start block has no jump, instead it has an initial exec Proj.
1728 * The backend wants to handle all blocks the same way, so we replace
1729 * the out cfg edge with a real jump.
1731 static void fix_start_block(ir_graph *irg)
1733 ir_node *initial_X = get_irg_initial_exec(irg);
1734 ir_node *start_block = get_irg_start_block(irg);
1735 const ir_edge_t *edge;
1737 assert(is_Proj(initial_X));
1739 foreach_out_edge(initial_X, edge) {
1740 ir_node *block = get_edge_src_irn(edge);
1742 if (is_Anchor(block))
1744 if (block != start_block) {
1745 ir_node *jmp = new_r_Jmp(start_block);
1747 set_Block_cfgpred(block, get_edge_src_pos(edge), jmp);
1751 panic("Initial exec has no follow block in %+F", irg);
1755 * Update the entity of Sels to the outer value parameters.
1757 static void update_outer_frame_sels(ir_node *irn, void *env) {
1758 lower_frame_sels_env_t *ctx = env;
1765 ptr = get_Sel_ptr(irn);
1766 if (! is_arg_Proj(ptr))
1768 if (get_Proj_proj(ptr) != ctx->static_link_pos)
1770 ent = get_Sel_entity(irn);
1772 if (get_entity_owner(ent) == ctx->value_tp) {
1773 /* replace by its copy from the argument type */
1774 pos = get_struct_member_index(ctx->value_tp, ent);
1775 ent = get_argument_entity(ent, ctx);
1776 set_Sel_entity(irn, ent);
1778 /* check, if we have not seen this entity before */
1779 if (get_entity_link(ent) == NULL) {
1785 ARR_APP1(ent_pos_pair, ctx->value_param_list, pair);
1787 set_entity_link(ent, ctx->value_param_list);
1793 * Fix access to outer local variables.
1795 static void fix_outer_variable_access(be_abi_irg_t *env,
1796 lower_frame_sels_env_t *ctx)
1802 for (i = get_class_n_members(ctx->frame_tp) - 1; i >= 0; --i) {
1803 ir_entity *ent = get_class_member(ctx->frame_tp, i);
1805 if (! is_method_entity(ent))
1807 if (get_entity_peculiarity(ent) == peculiarity_description)
1811 * FIXME: find the number of the static link parameter
1812 * for now we assume 0 here
1814 ctx->static_link_pos = 0;
1816 irg = get_entity_irg(ent);
1817 irg_walk_graph(irg, NULL, update_outer_frame_sels, ctx);
1822 * Modify the irg itself and the frame type.
1824 static void modify_irg(be_abi_irg_t *env)
1826 be_abi_call_t *call = env->call;
1827 const arch_env_t *arch_env= env->birg->main_env->arch_env;
1828 const arch_register_t *sp = arch_env->sp;
1829 ir_graph *irg = env->birg->irg;
1833 ir_node *new_mem_proj;
1835 ir_type *method_type = get_entity_type(get_irg_entity(irg));
1842 const arch_register_t *fp_reg;
1843 ir_node *frame_pointer;
1844 ir_node *reg_params_bl;
1847 const ir_edge_t *edge;
1848 ir_type *arg_type, *bet_type, *tp;
1849 lower_frame_sels_env_t ctx;
1850 ir_entity **param_map;
1852 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg;)
1854 DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1856 /* Must fetch memory here, otherwise the start Barrier gets the wrong
1857 * memory, which leads to loops in the DAG. */
1858 old_mem = get_irg_initial_mem(irg);
1860 irp_reserve_resources(irp, IR_RESOURCE_ENTITY_LINK);
1862 /* set the links of all frame entities to NULL, we use it
1863 to detect if an entity is already linked in the value_param_list */
1864 tp = get_method_value_param_type(method_type);
1867 /* clear the links of the clone type, let the
1868 original entities point to its clones */
1869 for (i = get_struct_n_members(tp) - 1; i >= 0; --i) {
1870 ir_entity *mem = get_struct_member(tp, i);
1871 set_entity_link(mem, NULL);
1875 arg_type = compute_arg_type(env, call, method_type, tp, ¶m_map);
1877 /* Convert the Sel nodes in the irg to frame addr nodes: */
1878 ctx.value_param_list = NEW_ARR_F(ent_pos_pair, 0);
1879 ctx.frame = get_irg_frame(irg);
1880 ctx.sp_class = env->arch_env->sp->reg_class;
1881 ctx.link_class = env->arch_env->link_class;
1882 ctx.frame_tp = get_irg_frame_type(irg);
1884 /* we will possible add new entities to the frame: set the layout to undefined */
1885 assert(get_type_state(ctx.frame_tp) == layout_fixed);
1886 set_type_state(ctx.frame_tp, layout_undefined);
1888 irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1890 /* fix the frame type layout again */
1891 set_type_state(ctx.frame_tp, layout_fixed);
1893 env->regs = pmap_create();
1895 n_params = get_method_n_params(method_type);
1896 args = obstack_alloc(&env->obst, n_params * sizeof(args[0]));
1897 memset(args, 0, n_params * sizeof(args[0]));
1900 * for inner function we must now fix access to outer frame entities.
1902 fix_outer_variable_access(env, &ctx);
1904 /* Check if a value parameter is transmitted as a register.
1905 * This might happen if the address of an parameter is taken which is
1906 * transmitted in registers.
1908 * Note that on some architectures this case must be handled specially
1909 * because the place of the backing store is determined by their ABI.
1911 * In the default case we move the entity to the frame type and create
1912 * a backing store into the first block.
1914 fix_address_of_parameter_access(env, ctx.value_param_list);
1916 DEL_ARR_F(ctx.value_param_list);
1917 irp_free_resources(irp, IR_RESOURCE_ENTITY_LINK);
1919 /* Fill the argument vector */
1920 arg_tuple = get_irg_args(irg);
1921 foreach_out_edge(arg_tuple, edge) {
1922 ir_node *irn = get_edge_src_irn(edge);
1923 if (! is_Anchor(irn)) {
1924 int nr = get_Proj_proj(irn);
1926 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1930 bet_type = call->cb->get_between_type(env->cb);
1931 stack_frame_init(&env->frame, arg_type, bet_type, get_irg_frame_type(irg), arch_env->stack_dir, param_map);
1933 /* Count the register params and add them to the number of Projs for the RegParams node */
1934 for (i = 0; i < n_params; ++i) {
1935 be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
1936 if (arg->in_reg && args[i]) {
1937 assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1938 assert(i == get_Proj_proj(args[i]));
1940 /* For now, associate the register with the old Proj from Start representing that argument. */
1941 pmap_insert(env->regs, (void *) arg->reg, args[i]);
1942 DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1946 /* Collect all callee-save registers */
1947 for (i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
1948 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
1949 for (j = 0; j < cls->n_regs; ++j) {
1950 const arch_register_t *reg = &cls->regs[j];
1951 if (arch_register_type_is(reg, callee_save) ||
1952 arch_register_type_is(reg, state)) {
1953 pmap_insert(env->regs, (void *) reg, NULL);
1958 pmap_insert(env->regs, (void *) sp, NULL);
1959 pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1960 reg_params_bl = get_irg_start_block(irg);
1961 env->reg_params = be_new_RegParams(reg_params_bl, pmap_count(env->regs));
1962 add_irn_dep(env->reg_params, get_irg_start(irg));
1965 * make proj nodes for the callee save registers.
1966 * memorize them, since Return nodes get those as inputs.
1968 * Note, that if a register corresponds to an argument, the regs map contains
1969 * the old Proj from start for that argument.
1972 rm = reg_map_to_arr(&env->obst, env->regs);
1973 for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1974 arch_register_t *reg = (void *) rm[i].reg;
1975 ir_mode *mode = reg->reg_class->mode;
1977 arch_register_req_type_t add_type = 0;
1981 add_type |= arch_register_req_type_produces_sp | arch_register_req_type_ignore;
1984 proj = new_r_Proj(reg_params_bl, env->reg_params, mode, nr);
1985 pmap_insert(env->regs, (void *) reg, proj);
1986 be_set_constr_single_reg_out(env->reg_params, nr, reg, add_type);
1987 arch_set_irn_register(proj, reg);
1989 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1991 obstack_free(&env->obst, rm);
1993 /* create a new initial memory proj */
1994 assert(is_Proj(old_mem));
1995 new_mem_proj = new_r_Proj(get_nodes_block(old_mem),
1996 new_r_Unknown(irg, mode_T), mode_M,
1997 get_Proj_proj(old_mem));
2000 /* Generate the Prologue */
2001 fp_reg = call->cb->prologue(env->cb, &mem, env->regs, &env->frame.initial_bias);
2003 /* do the stack allocation BEFORE the barrier, or spill code
2004 might be added before it */
2005 env->init_sp = be_abi_reg_map_get(env->regs, sp);
2006 start_bl = get_irg_start_block(irg);
2007 env->init_sp = be_new_IncSP(sp, start_bl, env->init_sp, BE_STACK_FRAME_SIZE_EXPAND, 0);
2008 be_abi_reg_map_set(env->regs, sp, env->init_sp);
2010 create_barrier(env, start_bl, &mem, env->regs, 0);
2012 env->init_sp = be_abi_reg_map_get(env->regs, sp);
2013 arch_set_irn_register(env->init_sp, sp);
2015 frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
2016 set_irg_frame(irg, frame_pointer);
2017 pset_insert_ptr(env->ignore_regs, fp_reg);
2019 /* rewire old mem users to new mem */
2020 set_Proj_pred(new_mem_proj, get_Proj_pred(old_mem));
2021 exchange(old_mem, mem);
2023 set_irg_initial_mem(irg, mem);
2025 /* Now, introduce stack param nodes for all parameters passed on the stack */
2026 for (i = 0; i < n_params; ++i) {
2027 ir_node *arg_proj = args[i];
2028 ir_node *repl = NULL;
2030 if (arg_proj != NULL) {
2031 be_abi_call_arg_t *arg;
2032 ir_type *param_type;
2033 int nr = get_Proj_proj(arg_proj);
2036 nr = MIN(nr, n_params);
2037 arg = get_call_arg(call, 0, nr);
2038 param_type = get_method_param_type(method_type, nr);
2041 repl = pmap_get(env->regs, (void *) arg->reg);
2042 } else if (arg->on_stack) {
2043 ir_node *addr = be_new_FrameAddr(sp->reg_class, reg_params_bl, frame_pointer, arg->stack_ent);
2045 /* For atomic parameters which are actually used, we create a Load node. */
2046 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
2047 ir_mode *mode = get_type_mode(param_type);
2048 ir_mode *load_mode = arg->load_mode;
2050 ir_node *load = new_r_Load(reg_params_bl, new_NoMem(), addr, load_mode, cons_floats);
2051 repl = new_r_Proj(reg_params_bl, load, load_mode, pn_Load_res);
2053 if (mode != load_mode) {
2054 repl = new_r_Conv(reg_params_bl, repl, mode);
2057 /* The stack parameter is not primitive (it is a struct or array),
2058 * we thus will create a node representing the parameter's address
2064 assert(repl != NULL);
2066 /* Beware: the mode of the register parameters is always the mode of the register class
2067 which may be wrong. Add Conv's then. */
2068 mode = get_irn_mode(args[i]);
2069 if (mode != get_irn_mode(repl)) {
2070 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
2072 exchange(args[i], repl);
2076 /* the arg proj is not needed anymore now and should be only used by the anchor */
2077 assert(get_irn_n_edges(arg_tuple) == 1);
2078 kill_node(arg_tuple);
2079 set_irg_args(irg, new_r_Bad(irg));
2081 /* All Return nodes hang on the End node, so look for them there. */
2082 end = get_irg_end_block(irg);
2083 for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
2084 ir_node *irn = get_Block_cfgpred(end, i);
2086 if (is_Return(irn)) {
2087 ir_node *blk = get_nodes_block(irn);
2088 ir_node *mem = get_Return_mem(irn);
2089 ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
2093 /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
2094 the code is dead and will never be executed. */
2096 obstack_free(&env->obst, args);
2098 /* handle start block here (place a jump in the block) */
2099 fix_start_block(irg);
2102 /** Fix the state inputs of calls that still hang on unknowns */
2104 void fix_call_state_inputs(be_abi_irg_t *env)
2106 const arch_env_t *arch_env = env->arch_env;
2108 arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
2110 /* Collect caller save registers */
2111 n = arch_env_get_n_reg_class(arch_env);
2112 for (i = 0; i < n; ++i) {
2114 const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
2115 for (j = 0; j < cls->n_regs; ++j) {
2116 const arch_register_t *reg = arch_register_for_index(cls, j);
2117 if (arch_register_type_is(reg, state)) {
2118 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
2123 n = ARR_LEN(env->calls);
2124 n_states = ARR_LEN(stateregs);
2125 for (i = 0; i < n; ++i) {
2127 ir_node *call = env->calls[i];
2129 arity = get_irn_arity(call);
2131 /* the state reg inputs are the last n inputs of the calls */
2132 for (s = 0; s < n_states; ++s) {
2133 int inp = arity - n_states + s;
2134 const arch_register_t *reg = stateregs[s];
2135 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
2137 set_irn_n(call, inp, regnode);
2141 DEL_ARR_F(stateregs);
2145 * Create a trampoline entity for the given method.
2147 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
2149 ir_type *type = get_entity_type(method);
2150 ident *old_id = get_entity_ld_ident(method);
2151 ident *id = id_mangle3("L", old_id, "$stub");
2152 ir_type *parent = be->pic_trampolines_type;
2153 ir_entity *ent = new_entity(parent, old_id, type);
2154 set_entity_ld_ident(ent, id);
2155 set_entity_visibility(ent, visibility_local);
2156 set_entity_variability(ent, variability_uninitialized);
2162 * Returns the trampoline entity for the given method.
2164 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
2166 ir_entity *result = pmap_get(env->ent_trampoline_map, method);
2167 if (result == NULL) {
2168 result = create_trampoline(env, method);
2169 pmap_insert(env->ent_trampoline_map, method, result);
2175 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
2177 ident *old_id = get_entity_ld_ident(entity);
2178 ident *id = id_mangle3("L", old_id, "$non_lazy_ptr");
2179 ir_type *e_type = get_entity_type(entity);
2180 ir_type *type = new_type_pointer(id, e_type, mode_P_data);
2181 ir_type *parent = be->pic_symbols_type;
2182 ir_entity *ent = new_entity(parent, old_id, type);
2183 set_entity_ld_ident(ent, id);
2184 set_entity_visibility(ent, visibility_local);
2185 set_entity_variability(ent, variability_uninitialized);
2190 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
2192 ir_entity *result = pmap_get(env->ent_pic_symbol_map, entity);
2193 if (result == NULL) {
2194 result = create_pic_symbol(env, entity);
2195 pmap_insert(env->ent_pic_symbol_map, entity, result);
2204 * Returns non-zero if a given entity can be accessed using a relative address.
2206 static int can_address_relative(ir_entity *entity)
2208 return get_entity_visibility(entity) != visibility_external_allocated;
2211 /** patches SymConsts to work in position independent code */
2212 static void fix_pic_symconsts(ir_node *node, void *data)
2222 be_abi_irg_t *env = data;
2224 be_main_env_t *be = env->birg->main_env;
2226 arity = get_irn_arity(node);
2227 for (i = 0; i < arity; ++i) {
2229 ir_node *pred = get_irn_n(node, i);
2231 ir_entity *pic_symbol;
2232 ir_node *pic_symconst;
2234 if (!is_SymConst(pred))
2237 entity = get_SymConst_entity(pred);
2238 block = get_nodes_block(pred);
2239 irg = get_irn_irg(pred);
2241 /* calls can jump to relative addresses, so we can directly jump to
2242 the (relatively) known call address or the trampoline */
2243 if (i == 1 && is_Call(node)) {
2244 ir_entity *trampoline;
2245 ir_node *trampoline_const;
2247 if (can_address_relative(entity))
2250 dbgi = get_irn_dbg_info(pred);
2251 trampoline = get_trampoline(be, entity);
2252 trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2254 set_irn_n(node, i, trampoline_const);
2258 /* everything else is accessed relative to EIP */
2259 mode = get_irn_mode(pred);
2260 unknown = new_r_Unknown(irg, mode);
2261 pic_base = arch_code_generator_get_pic_base(env->birg->cg);
2263 /* all ok now for locally constructed stuff */
2264 if (can_address_relative(entity)) {
2265 ir_node *add = new_r_Add(block, pic_base, pred, mode);
2267 /* make sure the walker doesn't visit this add again */
2268 mark_irn_visited(add);
2269 set_irn_n(node, i, add);
2273 /* get entry from pic symbol segment */
2274 dbgi = get_irn_dbg_info(pred);
2275 pic_symbol = get_pic_symbol(be, entity);
2276 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
2278 add = new_r_Add(block, pic_base, pic_symconst, mode);
2279 mark_irn_visited(add);
2281 /* we need an extra indirection for global data outside our current
2282 module. The loads are always safe and can therefore float
2283 and need no memory input */
2284 load = new_r_Load(block, new_NoMem(), add, mode, cons_floats);
2285 load_res = new_r_Proj(block, load, mode, pn_Load_res);
2287 set_irn_n(node, i, load_res);
2291 be_abi_irg_t *be_abi_introduce(be_irg_t *birg)
2293 be_abi_irg_t *env = XMALLOC(be_abi_irg_t);
2294 ir_node *old_frame = get_irg_frame(birg->irg);
2295 ir_graph *irg = birg->irg;
2299 optimization_state_t state;
2300 unsigned *limited_bitset;
2302 be_omit_fp = birg->main_env->options->omit_fp;
2303 be_omit_leaf_fp = birg->main_env->options->omit_leaf_fp;
2305 obstack_init(&env->obst);
2307 env->arch_env = birg->main_env->arch_env;
2308 env->method_type = get_entity_type(get_irg_entity(irg));
2309 env->call = be_abi_call_new(env->arch_env->sp->reg_class);
2310 arch_env_get_call_abi(env->arch_env, env->method_type, env->call);
2312 env->ignore_regs = pset_new_ptr_default();
2313 env->keep_map = pmap_create();
2314 env->dce_survivor = new_survive_dce();
2317 env->sp_req.type = arch_register_req_type_limited;
2318 env->sp_req.cls = arch_register_get_class(env->arch_env->sp);
2319 limited_bitset = rbitset_obstack_alloc(&env->obst, env->sp_req.cls->n_regs);
2320 rbitset_set(limited_bitset, arch_register_get_index(env->arch_env->sp));
2321 env->sp_req.limited = limited_bitset;
2322 if (env->arch_env->sp->type & arch_register_type_ignore) {
2323 env->sp_req.type |= arch_register_req_type_ignore;
2326 env->sp_cls_req.type = arch_register_req_type_normal;
2327 env->sp_cls_req.cls = arch_register_get_class(env->arch_env->sp);
2329 /* Beware: later we replace this node by the real one, ensure it is not CSE'd
2330 to another Unknown or the stack pointer gets used */
2331 save_optimization_state(&state);
2333 env->init_sp = dummy = new_r_Unknown(irg, env->arch_env->sp->reg_class->mode);
2334 restore_optimization_state(&state);
2336 FIRM_DBG_REGISTER(env->dbg, "firm.be.abi");
2338 env->calls = NEW_ARR_F(ir_node*, 0);
2340 if (birg->main_env->options->pic) {
2341 irg_walk_graph(irg, fix_pic_symconsts, NULL, env);
2344 /* Lower all call nodes in the IRG. */
2348 Beware: init backend abi call object after processing calls,
2349 otherwise some information might be not yet available.
2351 env->cb = env->call->cb->init(env->call, birg->main_env->arch_env, irg);
2353 /* Process the IRG */
2356 /* fix call inputs for state registers */
2357 fix_call_state_inputs(env);
2359 /* We don't need the keep map anymore. */
2360 pmap_destroy(env->keep_map);
2361 env->keep_map = NULL;
2363 /* calls array is not needed anymore */
2364 DEL_ARR_F(env->calls);
2367 /* reroute the stack origin of the calls to the true stack origin. */
2368 exchange(dummy, env->init_sp);
2369 exchange(old_frame, get_irg_frame(irg));
2371 /* Make some important node pointers survive the dead node elimination. */
2372 survive_dce_register_irn(env->dce_survivor, &env->init_sp);
2373 foreach_pmap(env->regs, ent) {
2374 survive_dce_register_irn(env->dce_survivor, (ir_node **) &ent->value);
2377 env->call->cb->done(env->cb);
2382 void be_abi_free(be_abi_irg_t *env)
2384 be_abi_call_free(env->call);
2385 free_survive_dce(env->dce_survivor);
2386 del_pset(env->ignore_regs);
2387 pmap_destroy(env->regs);
2388 obstack_free(&env->obst, NULL);
2392 void be_abi_put_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, bitset_t *bs)
2394 arch_register_t *reg;
2396 for (reg = pset_first(abi->ignore_regs); reg; reg = pset_next(abi->ignore_regs))
2397 if (reg->reg_class == cls)
2398 bitset_set(bs, reg->index);
2401 void be_abi_set_non_ignore_regs(be_abi_irg_t *abi, const arch_register_class_t *cls, unsigned *raw_bitset)
2404 arch_register_t *reg;
2406 for (i = 0; i < cls->n_regs; ++i) {
2407 if (arch_register_type_is(&cls->regs[i], ignore))
2410 rbitset_set(raw_bitset, i);
2413 for (reg = pset_first(abi->ignore_regs); reg != NULL;
2414 reg = pset_next(abi->ignore_regs)) {
2415 if (reg->reg_class != cls)
2418 rbitset_clear(raw_bitset, reg->index);
2422 /* Returns the stack layout from a abi environment. */
2423 const be_stack_layout_t *be_abi_get_stack_layout(const be_abi_irg_t *abi)
2431 | ___(_)_ __ / ___|| |_ __ _ ___| | __
2432 | |_ | \ \/ / \___ \| __/ _` |/ __| |/ /
2433 | _| | |> < ___) | || (_| | (__| <
2434 |_| |_/_/\_\ |____/ \__\__,_|\___|_|\_\
2438 typedef ir_node **node_array;
2440 typedef struct fix_stack_walker_env_t {
2441 node_array sp_nodes;
2442 } fix_stack_walker_env_t;
2445 * Walker. Collect all stack modifying nodes.
2447 static void collect_stack_nodes_walker(ir_node *node, void *data)
2449 fix_stack_walker_env_t *env = data;
2450 const arch_register_req_t *req;
2452 if (get_irn_mode(node) == mode_T)
2455 req = arch_get_register_req_out(node);
2456 if (! (req->type & arch_register_req_type_produces_sp))
2459 ARR_APP1(ir_node*, env->sp_nodes, node);
2462 void be_abi_fix_stack_nodes(be_abi_irg_t *env)
2464 be_ssa_construction_env_t senv;
2467 be_irg_t *birg = env->birg;
2468 be_lv_t *lv = be_get_birg_liveness(birg);
2469 fix_stack_walker_env_t walker_env;
2471 walker_env.sp_nodes = NEW_ARR_F(ir_node*, 0);
2473 irg_walk_graph(birg->irg, collect_stack_nodes_walker, NULL, &walker_env);
2475 /* nothing to be done if we didn't find any node, in fact we mustn't
2476 * continue, as for endless loops incsp might have had no users and is bad
2479 len = ARR_LEN(walker_env.sp_nodes);
2481 DEL_ARR_F(walker_env.sp_nodes);
2485 be_ssa_construction_init(&senv, birg);
2486 be_ssa_construction_add_copies(&senv, walker_env.sp_nodes,
2487 ARR_LEN(walker_env.sp_nodes));
2488 be_ssa_construction_fix_users_array(&senv, walker_env.sp_nodes,
2489 ARR_LEN(walker_env.sp_nodes));
2492 len = ARR_LEN(walker_env.sp_nodes);
2493 for (i = 0; i < len; ++i) {
2494 be_liveness_update(lv, walker_env.sp_nodes[i]);
2496 be_ssa_construction_update_liveness_phis(&senv, lv);
2499 phis = be_ssa_construction_get_new_phis(&senv);
2501 /* set register requirements for stack phis */
2502 len = ARR_LEN(phis);
2503 for (i = 0; i < len; ++i) {
2504 ir_node *phi = phis[i];
2505 be_set_phi_reg_req(phi, &env->sp_req, arch_register_req_type_produces_sp);
2506 arch_set_irn_register(phi, env->arch_env->sp);
2508 be_ssa_construction_destroy(&senv);
2510 DEL_ARR_F(walker_env.sp_nodes);
2514 * Fix all stack accessing operations in the block bl.
2516 * @param env the abi environment
2517 * @param bl the block to process
2518 * @param real_bias the bias value
2520 * @return the bias at the end of this block
2522 static int process_stack_bias(be_abi_irg_t *env, ir_node *bl, int real_bias)
2524 int omit_fp = env->call->flags.bits.try_omit_fp;
2526 int wanted_bias = real_bias;
2528 sched_foreach(bl, irn) {
2532 Check, if the node relates to an entity on the stack frame.
2533 If so, set the true offset (including the bias) for that
2536 ir_entity *ent = arch_get_frame_entity(irn);
2538 int bias = omit_fp ? real_bias : 0;
2539 int offset = get_stack_entity_offset(&env->frame, ent, bias);
2540 arch_set_frame_offset(irn, offset);
2541 DBG((env->dbg, LEVEL_2, "%F has offset %d (including bias %d)\n",
2542 ent, offset, bias));
2546 * If the node modifies the stack pointer by a constant offset,
2547 * record that in the bias.
2549 ofs = arch_get_sp_bias(irn);
2551 if (be_is_IncSP(irn)) {
2552 /* fill in real stack frame size */
2553 if (ofs == BE_STACK_FRAME_SIZE_EXPAND) {
2554 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2555 ofs = (int) get_type_size_bytes(frame_type);
2556 be_set_IncSP_offset(irn, ofs);
2557 } else if (ofs == BE_STACK_FRAME_SIZE_SHRINK) {
2558 ir_type *frame_type = get_irg_frame_type(env->birg->irg);
2559 ofs = - (int)get_type_size_bytes(frame_type);
2560 be_set_IncSP_offset(irn, ofs);
2562 if (be_get_IncSP_align(irn)) {
2563 /* patch IncSP to produce an aligned stack pointer */
2564 ir_type *between_type = env->frame.between_type;
2565 int between_size = get_type_size_bytes(between_type);
2566 int alignment = 1 << env->arch_env->stack_alignment;
2567 int delta = (real_bias + ofs + between_size) & (alignment - 1);
2570 be_set_IncSP_offset(irn, ofs + alignment - delta);
2571 real_bias += alignment - delta;
2574 /* adjust so real_bias corresponds with wanted_bias */
2575 int delta = wanted_bias - real_bias;
2578 be_set_IncSP_offset(irn, ofs + delta);
2589 assert(real_bias == wanted_bias);
2594 * A helper struct for the bias walker.
2597 be_abi_irg_t *env; /**< The ABI irg environment. */
2598 int start_block_bias; /**< The bias at the end of the start block. */
2600 ir_node *start_block; /**< The start block of the current graph. */
2604 * Block-Walker: fix all stack offsets for all blocks
2605 * except the start block
2607 static void stack_bias_walker(ir_node *bl, void *data)
2609 struct bias_walk *bw = data;
2610 if (bl != bw->start_block) {
2611 process_stack_bias(bw->env, bl, bw->start_block_bias);
2616 * Walker: finally lower all Sels of outer frame or parameter
2619 static void lower_outer_frame_sels(ir_node *sel, void *ctx) {
2620 be_abi_irg_t *env = ctx;
2628 ent = get_Sel_entity(sel);
2629 owner = get_entity_owner(ent);
2630 ptr = get_Sel_ptr(sel);
2632 if (owner == env->frame.frame_type || owner == env->frame.arg_type) {
2633 /* found access to outer frame or arguments */
2634 int offset = get_stack_entity_offset(&env->frame, ent, 0);
2637 ir_node *bl = get_nodes_block(sel);
2638 dbg_info *dbgi = get_irn_dbg_info(sel);
2639 ir_mode *mode = get_irn_mode(sel);
2640 ir_mode *mode_UInt = get_reference_mode_unsigned_eq(mode);
2641 ir_node *cnst = new_r_Const_long(current_ir_graph, mode_UInt, offset);
2643 ptr = new_rd_Add(dbgi, bl, ptr, cnst, mode);
2649 void be_abi_fix_stack_bias(be_abi_irg_t *env)
2651 ir_graph *irg = env->birg->irg;
2654 struct bias_walk bw;
2656 stack_frame_compute_initial_offset(&env->frame);
2657 // stack_layout_dump(stdout, frame);
2659 /* Determine the stack bias at the end of the start block. */
2660 bw.start_block_bias = process_stack_bias(env, get_irg_start_block(irg), env->frame.initial_bias);
2661 bw.between_size = get_type_size_bytes(env->frame.between_type);
2663 /* fix the bias is all other blocks */
2665 bw.start_block = get_irg_start_block(irg);
2666 irg_block_walk_graph(irg, stack_bias_walker, NULL, &bw);
2668 /* fix now inner functions: these still have Sel node to outer
2669 frame and parameter entities */
2670 frame_tp = get_irg_frame_type(irg);
2671 for (i = get_class_n_members(frame_tp) - 1; i >= 0; --i) {
2672 ir_entity *ent = get_class_member(frame_tp, i);
2674 if (is_method_entity(ent) && get_entity_peculiarity(ent) != peculiarity_description) {
2675 ir_graph *irg = get_entity_irg(ent);
2677 irg_walk_graph(irg, NULL, lower_outer_frame_sels, env);
2682 ir_node *be_abi_get_callee_save_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2684 assert(arch_register_type_is(reg, callee_save));
2685 assert(pmap_contains(abi->regs, (void *) reg));
2686 return pmap_get(abi->regs, (void *) reg);
2689 ir_node *be_abi_get_ignore_irn(be_abi_irg_t *abi, const arch_register_t *reg)
2691 assert(arch_register_type_is(reg, ignore));
2692 assert(pmap_contains(abi->regs, (void *) reg));
2693 return pmap_get(abi->regs, (void *) reg);
2697 * Returns non-zero if the ABI has omitted the frame pointer in
2698 * the current graph.
2700 int be_abi_omit_fp(const be_abi_irg_t *abi)
2702 return abi->call->flags.bits.try_omit_fp;