2 * Copyright (C) 1995-2011 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
31 #include "irgraph_t.h"
34 #include "iredges_t.h"
37 #include "irprintf_t.h"
44 #include "raw_bitset.h"
55 #include "bessaconstr.h"
57 #include "betranshlp.h"
59 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
61 typedef struct be_abi_call_arg_t {
62 unsigned is_res : 1; /**< 1: the call argument is a return value. 0: it's a call parameter. */
63 unsigned in_reg : 1; /**< 1: this argument is transmitted 1: in registers, 0: on stack. */
64 unsigned callee : 1; /**< 1: someone called us. 0: We call another function */
67 const arch_register_t *reg;
70 unsigned alignment; /**< stack alignment */
71 unsigned space_before; /**< allocate space before */
72 unsigned space_after; /**< allocate space after */
75 struct be_abi_call_t {
76 be_abi_call_flags_t flags; /**< Flags describing the ABI behavior on calls */
77 int pop; /**< number of bytes the stack frame is shrinked by the callee on return. */
78 const be_abi_callbacks_t *cb;
80 const arch_register_class_t *cls_addr; /**< register class of the call address */
84 * The ABI information for the current graph.
87 be_abi_call_t *call; /**< The ABI call information. */
89 ir_node *init_sp; /**< The node representing the stack pointer
90 at the start of the function. */
92 pmap *regs; /**< A map of all callee-save and ignore regs to
93 their Projs to the RegParams node. */
94 pmap *keep_map; /**< mapping blocks to keep nodes. */
96 ir_node **calls; /**< flexible array containing all be_Call nodes */
99 static ir_heights_t *ir_heights;
101 static ir_node *be_abi_reg_map_get(pmap *map, const arch_register_t *reg)
103 return pmap_get(ir_node, map, reg);
106 static void be_abi_reg_map_set(pmap *map, const arch_register_t* reg,
109 pmap_insert(map, reg, node);
113 * Check if the given register is callee save, ie. will be saved by the callee.
115 static bool arch_register_is_callee_save(
116 const arch_env_t *arch_env,
117 const arch_register_t *reg)
119 if (arch_env->impl->register_saved_by)
120 return arch_env->impl->register_saved_by(reg, /*callee=*/1);
125 * Check if the given register is caller save, ie. must be saved by the caller.
127 static bool arch_register_is_caller_save(
128 const arch_env_t *arch_env,
129 const arch_register_t *reg)
131 if (arch_env->impl->register_saved_by)
132 return arch_env->impl->register_saved_by(reg, /*callee=*/0);
139 _ ____ ___ ____ _ _ _ _
140 / \ | __ )_ _| / ___|__ _| | | |__ __ _ ___| | _____
141 / _ \ | _ \| | | | / _` | | | '_ \ / _` |/ __| |/ / __|
142 / ___ \| |_) | | | |__| (_| | | | |_) | (_| | (__| <\__ \
143 /_/ \_\____/___| \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
145 These callbacks are used by the backend to set the parameters
146 for a specific call type.
150 * Set compare function: compares two ABI call object arguments.
152 static int cmp_call_arg(const void *a, const void *b, size_t n)
154 const be_abi_call_arg_t *p = (const be_abi_call_arg_t*)a;
155 const be_abi_call_arg_t *q = (const be_abi_call_arg_t*)b;
157 return !(p->is_res == q->is_res && p->pos == q->pos && p->callee == q->callee);
161 * Get an ABI call object argument.
163 * @param call the abi call
164 * @param is_res true for call results, false for call arguments
165 * @param pos position of the argument
166 * @param callee context type - if we are callee or caller
168 static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos, int callee)
170 be_abi_call_arg_t arg;
173 memset(&arg, 0, sizeof(arg));
178 hash = is_res * 128 + pos;
180 return set_find(be_abi_call_arg_t, call->params, &arg, sizeof(arg), hash);
184 * Set an ABI call object argument.
186 static void remember_call_arg(be_abi_call_arg_t *arg, be_abi_call_t *call, be_abi_context_t context)
188 unsigned hash = arg->is_res * 128 + arg->pos;
189 if (context & ABI_CONTEXT_CALLEE) {
191 (void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
193 if (context & ABI_CONTEXT_CALLER) {
195 (void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
199 /* Set the flags for a call. */
200 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
206 /* Sets the number of bytes the stackframe is shrinked by the callee on return */
207 void be_abi_call_set_pop(be_abi_call_t *call, int pop)
213 /* Set register class for call address */
214 void be_abi_call_set_call_address_reg_class(be_abi_call_t *call, const arch_register_class_t *cls)
216 call->cls_addr = cls;
220 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos,
221 ir_mode *load_mode, unsigned alignment,
222 unsigned space_before, unsigned space_after,
223 be_abi_context_t context)
225 be_abi_call_arg_t arg;
226 memset(&arg, 0, sizeof(arg));
227 assert(alignment > 0 && "Alignment must be greater than 0");
228 arg.load_mode = load_mode;
229 arg.alignment = alignment;
230 arg.space_before = space_before;
231 arg.space_after = space_after;
235 remember_call_arg(&arg, call, context);
238 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
240 be_abi_call_arg_t arg;
241 memset(&arg, 0, sizeof(arg));
248 remember_call_arg(&arg, call, context);
251 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
253 be_abi_call_arg_t arg;
254 memset(&arg, 0, sizeof(arg));
261 remember_call_arg(&arg, call, context);
264 /* Get the flags of a ABI call object. */
265 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
271 * Constructor for a new ABI call object.
273 * @param cls_addr register class of the call address
275 * @return the new ABI call object
277 static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
279 be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
281 call->params = new_set(cmp_call_arg, 16);
283 call->cls_addr = cls_addr;
284 call->flags.try_omit_fp = be_options.omit_fp;
290 * Destructor for an ABI call object.
292 static void be_abi_call_free(be_abi_call_t *call)
294 del_set(call->params);
299 * Initializes the frame layout from parts
301 * @param frame the stack layout that will be initialized
302 * @param args the stack argument layout type
303 * @param between the between layout type
304 * @param locals the method frame type
306 * @return the initialized stack layout
308 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
309 ir_type *between, ir_type *locals)
311 frame->arg_type = args;
312 frame->between_type = between;
313 frame->frame_type = locals;
314 frame->initial_offset = 0;
315 frame->initial_bias = 0;
316 frame->order[1] = between;
318 /* typical decreasing stack: locals have the
319 * lowest addresses, arguments the highest */
320 frame->order[0] = locals;
321 frame->order[2] = args;
332 Adjustment of the calls inside a graph.
337 * Transform a call node into a be_Call node.
339 * @param env The ABI environment for the current irg.
340 * @param irn The call node.
341 * @param curr_sp The stack pointer node to use.
342 * @return The stack pointer after the call.
344 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
346 ir_graph *irg = get_irn_irg(irn);
347 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
348 ir_type *call_tp = get_Call_type(irn);
349 ir_node *call_ptr = get_Call_ptr(irn);
350 size_t n_params = get_method_n_params(call_tp);
351 ir_node *curr_mem = get_Call_mem(irn);
352 ir_node *bl = get_nodes_block(irn);
354 const arch_register_t *sp = arch_env->sp;
355 be_abi_call_t *call = be_abi_call_new(sp->reg_class);
356 ir_mode *mach_mode = sp->reg_class->mode;
357 int n_res = get_method_n_ress(call_tp);
359 ir_node *res_proj = NULL;
360 int n_reg_params = 0;
361 int n_stack_params = 0;
364 const arch_register_t **states = NEW_ARR_F(const arch_register_t*, 0);
365 const arch_register_t **destroyed_regs = NEW_ARR_F(const arch_register_t*, 0);
369 int n_reg_results = 0;
371 int *stack_param_idx;
373 int throws_exception;
378 /* Let the isa fill out the abi description for that call node. */
379 arch_env_get_call_abi(arch_env, call_tp, call);
381 /* Insert code to put the stack arguments on the stack. */
382 assert((size_t)get_Call_n_params(irn) == n_params);
383 stack_param_idx = ALLOCAN(int, n_params);
384 for (p = 0; p < n_params; ++p) {
385 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
388 int arg_size = get_type_size_bytes(get_method_param_type(call_tp, p));
390 stack_size += round_up2(arg->space_before, arg->alignment);
391 stack_size += round_up2(arg_size, arg->alignment);
392 stack_size += round_up2(arg->space_after, arg->alignment);
394 stack_param_idx[n_stack_params++] = p;
398 /* Collect all arguments which are passed in registers. */
399 reg_param_idxs = ALLOCAN(int, n_params);
400 for (p = 0; p < n_params; ++p) {
401 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
402 if (arg && arg->in_reg) {
403 reg_param_idxs[n_reg_params++] = p;
408 * If the stack is decreasing and we do not want to store sequentially,
409 * or someone else allocated the call frame
410 * we allocate as much space on the stack all parameters need, by
411 * moving the stack pointer along the stack's direction.
413 * Note: we also have to do this for stack_size == 0, because we may have
414 * to adjust stack alignment for the call.
416 curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
418 dbgi = get_irn_dbg_info(irn);
419 /* If there are some parameters which shall be passed on the stack. */
420 if (n_stack_params > 0) {
422 ir_node **in = ALLOCAN(ir_node*, n_stack_params+1);
425 curr_mem = get_Call_mem(irn);
426 in[n_in++] = curr_mem;
428 for (i = 0; i < n_stack_params; ++i) {
429 int p = stack_param_idx[i];
430 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
431 ir_node *param = get_Call_param(irn, p);
432 ir_node *addr = curr_sp;
434 ir_type *param_type = get_method_param_type(call_tp, p);
435 int param_size = get_type_size_bytes(param_type) + arg->space_after;
438 * If we wanted to build the arguments sequentially,
439 * the stack pointer for the next must be incremented,
440 * and the memory value propagated.
442 curr_ofs += arg->space_before;
443 curr_ofs = round_up2(curr_ofs, arg->alignment);
445 /* Make the expression to compute the argument's offset. */
447 ir_mode *constmode = mach_mode;
448 if (mode_is_reference(mach_mode)) {
451 addr = new_r_Const_long(irg, constmode, curr_ofs);
452 addr = new_r_Add(bl, curr_sp, addr, mach_mode);
455 /* Insert a store for primitive arguments. */
456 if (is_atomic_type(param_type)) {
457 ir_node *nomem = get_irg_no_mem(irg);
458 ir_node *mem_input = nomem;
459 ir_node *store = new_rd_Store(dbgi, bl, mem_input, addr, param, cons_none);
460 mem = new_r_Proj(store, mode_M, pn_Store_M);
462 /* Make a mem copy for compound arguments. */
465 assert(mode_is_reference(get_irn_mode(param)));
466 copy = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type);
467 mem = new_r_Proj(copy, mode_M, pn_CopyB_M);
470 curr_ofs += param_size;
475 /* We need the sync only, if we didn't build the stores sequentially. */
476 if (n_stack_params >= 1) {
477 curr_mem = new_r_Sync(bl, n_in, in);
479 curr_mem = get_Call_mem(irn);
483 /* Put caller save into the destroyed set and state registers in the states
485 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
487 const arch_register_class_t *cls = &arch_env->register_classes[i];
488 for (j = 0; j < cls->n_regs; ++j) {
489 const arch_register_t *reg = arch_register_for_index(cls, j);
491 /* even if destroyed all is specified, neither SP nor FP are
492 * destroyed (else bad things will happen) */
493 if (reg == arch_env->sp || reg == arch_env->bp)
496 if (reg->type & arch_register_type_state) {
497 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
498 ARR_APP1(const arch_register_t*, states, reg);
499 /* we're already in the destroyed set so no need for further
503 if (arch_register_is_caller_save(arch_env, reg)) {
504 if (!(reg->type & arch_register_type_ignore)) {
505 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
511 /* search the largest result proj number */
512 res_projs = ALLOCANZ(ir_node*, n_res);
514 foreach_out_edge(irn, edge) {
515 ir_node *irn = get_edge_src_irn(edge);
517 if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
520 foreach_out_edge(irn, res_edge) {
522 ir_node *res = get_edge_src_irn(res_edge);
524 assert(is_Proj(res));
526 proj = get_Proj_proj(res);
527 assert(proj < n_res);
528 assert(res_projs[proj] == NULL);
529 res_projs[proj] = res;
535 /** TODO: this is not correct for cases where return values are passed
536 * on the stack, but no known ABI does this currently...
538 n_reg_results = n_res;
541 in = ALLOCAN(ir_node*, n_reg_params + ARR_LEN(states));
543 /* make the back end call node and set its register requirements. */
544 for (i = 0; i < n_reg_params; ++i) {
545 in[n_ins++] = get_Call_param(irn, reg_param_idxs[i]);
548 /* add state registers ins */
549 for (s = 0; s < ARR_LEN(states); ++s) {
550 const arch_register_t *reg = states[s];
551 const arch_register_class_t *cls = reg->reg_class;
552 ir_node *regnode = new_r_Unknown(irg, cls->mode);
553 in[n_ins++] = regnode;
555 assert(n_ins == (int) (n_reg_params + ARR_LEN(states)));
557 /* ins collected, build the call */
558 throws_exception = ir_throws_exception(irn);
559 if (env->call->flags.call_has_imm && is_SymConst(call_ptr)) {
561 low_call = be_new_Call(dbgi, irg, bl, curr_mem, sp->single_req, curr_sp,
562 sp->single_req, curr_sp,
563 n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
564 n_ins, in, get_Call_type(irn));
565 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
568 low_call = be_new_Call(dbgi, irg, bl, curr_mem, sp->single_req, curr_sp,
569 call->cls_addr->class_req, call_ptr,
570 n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
571 n_ins, in, get_Call_type(irn));
573 ir_set_throws_exception(low_call, throws_exception);
574 be_Call_set_pop(low_call, call->pop);
576 /* put the call into the list of all calls for later processing */
577 ARR_APP1(ir_node *, env->calls, low_call);
579 /* create new stack pointer */
580 curr_sp = new_r_Proj(low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
581 be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
582 arch_register_req_type_ignore | arch_register_req_type_produces_sp);
583 arch_set_irn_register(curr_sp, sp);
585 /* now handle results */
586 for (i = 0; i < n_res; ++i) {
587 ir_node *proj = res_projs[i];
588 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 0);
590 /* returns values on stack not supported yet */
594 shift the proj number to the right, since we will drop the
595 unspeakable Proj_T from the Call. Therefore, all real argument
596 Proj numbers must be increased by pn_be_Call_first_res
598 long pn = i + pn_be_Call_first_res;
601 ir_type *res_type = get_method_res_type(call_tp, i);
602 ir_mode *mode = get_type_mode(res_type);
603 proj = new_r_Proj(low_call, mode, pn);
606 set_Proj_pred(proj, low_call);
607 set_Proj_proj(proj, pn);
611 /* remove register from destroyed regs */
613 size_t n = ARR_LEN(destroyed_regs);
614 for (j = 0; j < n; ++j) {
615 if (destroyed_regs[j] == arg->reg) {
616 destroyed_regs[j] = destroyed_regs[n-1];
617 ARR_SHRINKLEN(destroyed_regs,n-1);
624 DBG((dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
626 /* Set the register classes and constraints of the Call parameters. */
627 for (i = 0; i < n_reg_params; ++i) {
628 int index = reg_param_idxs[i];
629 be_abi_call_arg_t *arg = get_call_arg(call, 0, index, 0);
630 assert(arg->reg != NULL);
632 be_set_constr_single_reg_in(low_call, n_be_Call_first_arg + i,
633 arg->reg, arch_register_req_type_none);
636 /* Set the register constraints of the results. */
637 for (i = 0; i < n_res; ++i) {
638 ir_node *proj = res_projs[i];
639 const be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 0);
640 int pn = get_Proj_proj(proj);
643 be_set_constr_single_reg_out(low_call, pn, arg->reg,
644 arch_register_req_type_none);
645 arch_set_irn_register(proj, arg->reg);
647 exchange(irn, low_call);
649 /* kill the ProjT node */
650 if (res_proj != NULL) {
654 /* Make additional projs for the caller save registers
655 and the Keep node which keeps them alive. */
661 int curr_res_proj = pn_be_Call_first_res + n_reg_results;
664 n_ins = ARR_LEN(destroyed_regs) + n_reg_results + 1;
665 in = ALLOCAN(ir_node *, n_ins);
667 /* also keep the stack pointer */
668 set_irn_link(curr_sp, (void*) sp);
671 for (d = 0; d < ARR_LEN(destroyed_regs); ++d) {
672 const arch_register_t *reg = destroyed_regs[d];
673 ir_node *proj = new_r_Proj(low_call, reg->reg_class->mode, curr_res_proj);
675 /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
676 be_set_constr_single_reg_out(low_call, curr_res_proj, reg,
677 arch_register_req_type_none);
678 arch_set_irn_register(proj, reg);
680 set_irn_link(proj, (void*) reg);
685 for (i = 0; i < n_reg_results; ++i) {
686 ir_node *proj = res_projs[i];
687 const arch_register_t *reg = arch_get_irn_register(proj);
688 set_irn_link(proj, (void*) reg);
693 /* create the Keep for the caller save registers */
694 keep = be_new_Keep(bl, n, in);
695 for (i = 0; i < n; ++i) {
696 const arch_register_t *reg = (const arch_register_t*)get_irn_link(in[i]);
697 be_node_set_reg_class_in(keep, i, reg->reg_class);
701 /* Clean up the stack. */
702 assert(stack_size >= call->pop);
703 stack_size -= call->pop;
705 if (stack_size > 0) {
706 ir_node *mem_proj = NULL;
708 foreach_out_edge(low_call, edge) {
709 ir_node *irn = get_edge_src_irn(edge);
710 if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
717 mem_proj = new_r_Proj(low_call, mode_M, pn_be_Call_M);
718 keep_alive(mem_proj);
721 /* Clean up the stack frame or revert alignment fixes if we allocated it */
722 curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
724 be_abi_call_free(call);
727 DEL_ARR_F(destroyed_regs);
733 * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
735 * @param alignment the minimum stack alignment
736 * @param size the node containing the non-aligned size
737 * @param block the block where new nodes are allocated on
738 * @param dbg debug info for new nodes
740 * @return a node representing the aligned size
742 static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
743 ir_node *block, dbg_info *dbg)
745 if (stack_alignment > 1) {
751 assert(is_po2(stack_alignment));
753 mode = get_irn_mode(size);
754 tv = new_tarval_from_long(stack_alignment-1, mode);
755 irg = get_Block_irg(block);
756 mask = new_r_Const(irg, tv);
757 size = new_rd_Add(dbg, block, size, mask, mode);
759 tv = new_tarval_from_long(-(long)stack_alignment, mode);
760 mask = new_r_Const(irg, tv);
761 size = new_rd_And(dbg, block, size, mask, mode);
767 * The alloca is transformed into a back end alloca node and connected to the stack nodes.
769 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
771 ir_node *block = get_nodes_block(alloc);
772 ir_graph *irg = get_Block_irg(block);
773 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
774 ir_node *alloc_mem = NULL;
775 ir_node *alloc_res = NULL;
776 ir_type *type = get_Alloc_type(alloc);
783 unsigned stack_alignment;
785 /* all non-stack Alloc nodes should already be lowered before the backend */
786 assert(get_Alloc_where(alloc) == stack_alloc);
788 foreach_out_edge(alloc, edge) {
789 ir_node *irn = get_edge_src_irn(edge);
791 assert(is_Proj(irn));
792 switch (get_Proj_proj(irn)) {
804 /* Beware: currently Alloc nodes without a result might happen,
805 only escape analysis kills them and this phase runs only for object
806 oriented source. We kill the Alloc here. */
807 if (alloc_res == NULL && alloc_mem) {
808 exchange(alloc_mem, get_Alloc_mem(alloc));
812 dbg = get_irn_dbg_info(alloc);
813 count = get_Alloc_count(alloc);
815 /* we might need to multiply the count with the element size */
816 if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
817 ir_mode *mode = get_irn_mode(count);
818 ir_tarval *tv = new_tarval_from_long(get_type_size_bytes(type),
820 ir_node *cnst = new_rd_Const(dbg, irg, tv);
821 size = new_rd_Mul(dbg, block, count, cnst, mode);
826 /* The stack pointer will be modified in an unknown manner.
827 We cannot omit it. */
828 env->call->flags.try_omit_fp = 0;
830 stack_alignment = 1 << arch_env->stack_alignment;
831 size = adjust_alloc_size(stack_alignment, size, block, dbg);
832 new_alloc = be_new_AddSP(arch_env->sp, block, curr_sp, size);
833 set_irn_dbg_info(new_alloc, dbg);
835 if (alloc_mem != NULL) {
839 addsp_mem = new_r_Proj(new_alloc, mode_M, pn_be_AddSP_M);
841 /* We need to sync the output mem of the AddSP with the input mem
842 edge into the alloc node. */
843 ins[0] = get_Alloc_mem(alloc);
845 sync = new_r_Sync(block, 2, ins);
847 exchange(alloc_mem, sync);
850 exchange(alloc, new_alloc);
852 /* fix projnum of alloca res */
853 set_Proj_proj(alloc_res, pn_be_AddSP_res);
855 curr_sp = new_r_Proj(new_alloc, get_irn_mode(curr_sp), pn_be_AddSP_sp);
862 * The Free is transformed into a back end free node and connected to the stack nodes.
864 static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
866 ir_node *block = get_nodes_block(free);
867 ir_graph *irg = get_irn_irg(free);
868 ir_type *type = get_Free_type(free);
869 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
870 ir_mode *sp_mode = arch_env->sp->reg_class->mode;
871 dbg_info *dbg = get_irn_dbg_info(free);
872 ir_node *subsp, *mem, *res, *size, *sync;
874 unsigned stack_alignment;
876 /* all non-stack-alloc Free nodes should already be lowered before the
878 assert(get_Free_where(free) == stack_alloc);
880 /* we might need to multiply the size with the element size */
881 if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
882 ir_tarval *tv = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
883 ir_node *cnst = new_rd_Const(dbg, irg, tv);
884 ir_node *mul = new_rd_Mul(dbg, block, get_Free_count(free),
888 size = get_Free_count(free);
891 stack_alignment = 1 << arch_env->stack_alignment;
892 size = adjust_alloc_size(stack_alignment, size, block, dbg);
894 /* The stack pointer will be modified in an unknown manner.
895 We cannot omit it. */
896 env->call->flags.try_omit_fp = 0;
897 subsp = be_new_SubSP(arch_env->sp, block, curr_sp, size);
898 set_irn_dbg_info(subsp, dbg);
900 mem = new_r_Proj(subsp, mode_M, pn_be_SubSP_M);
901 res = new_r_Proj(subsp, sp_mode, pn_be_SubSP_sp);
903 /* we need to sync the memory */
904 in[0] = get_Free_mem(free);
906 sync = new_r_Sync(block, 2, in);
908 /* and make the AddSP dependent on the former memory */
909 add_irn_dep(subsp, get_Free_mem(free));
912 exchange(free, sync);
919 * Check if a node is somehow data dependent on another one.
920 * both nodes must be in the same basic block.
921 * @param n1 The first node.
922 * @param n2 The second node.
923 * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
925 static int dependent_on(ir_node *n1, ir_node *n2)
927 assert(get_nodes_block(n1) == get_nodes_block(n2));
929 return heights_reachable_in_block(ir_heights, n1, n2);
932 static int cmp_call_dependency(const void *c1, const void *c2)
934 ir_node *n1 = *(ir_node **) c1;
935 ir_node *n2 = *(ir_node **) c2;
939 Classical qsort() comparison function behavior:
940 0 if both elements are equal
941 1 if second is "smaller" that first
942 -1 if first is "smaller" that second
944 if (dependent_on(n1, n2))
947 if (dependent_on(n2, n1))
950 /* The nodes have no depth order, but we need a total order because qsort()
953 * Additionally, we need to respect transitive dependencies. Consider a
954 * Call a depending on Call b and an independent Call c.
955 * We MUST NOT order c > a and b > c. */
956 h1 = get_irn_height(ir_heights, n1);
957 h2 = get_irn_height(ir_heights, n2);
958 if (h1 < h2) return -1;
959 if (h1 > h2) return 1;
960 /* Same height, so use a random (but stable) order */
961 return get_irn_idx(n1) - get_irn_idx(n2);
965 * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
967 static void link_ops_in_block_walker(ir_node *irn, void *data)
969 be_abi_irg_t *env = (be_abi_irg_t*)data;
970 unsigned code = get_irn_opcode(irn);
972 if (code == iro_Call ||
973 (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
974 (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
975 ir_node *bl = get_nodes_block(irn);
976 void *save = get_irn_link(bl);
978 set_irn_link(irn, save);
979 set_irn_link(bl, irn);
982 if (code == iro_Builtin && get_Builtin_kind(irn) == ir_bk_return_address) {
983 ir_node *param = get_Builtin_param(irn, 0);
984 ir_tarval *tv = get_Const_tarval(param);
985 unsigned long value = get_tarval_long(tv);
986 /* use ebp, so the climbframe algo works... */
988 env->call->flags.try_omit_fp = 0;
995 * Process all Call/Alloc/Free nodes inside a basic block.
996 * Note that the link field of the block must contain a linked list of all
997 * nodes inside the Block. We first order this list according to data dependency
998 * and that connect the nodes together.
1000 static void process_ops_in_block(ir_node *bl, void *data)
1002 be_abi_irg_t *env = (be_abi_irg_t*)data;
1003 ir_node *curr_sp = env->init_sp;
1010 for (irn = (ir_node*)get_irn_link(bl); irn != NULL;
1011 irn = (ir_node*)get_irn_link(irn)) {
1015 nodes = ALLOCAN(ir_node*, n_nodes);
1016 for (irn = (ir_node*)get_irn_link(bl), n = 0; irn != NULL;
1017 irn = (ir_node*)get_irn_link(irn), ++n) {
1021 /* If there were call nodes in the block. */
1026 /* order the call nodes according to data dependency */
1027 qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
1029 for (i = n_nodes - 1; i >= 0; --i) {
1030 ir_node *irn = nodes[i];
1032 DBG((dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1033 switch (get_irn_opcode(irn)) {
1035 curr_sp = adjust_call(env, irn, curr_sp);
1038 if (get_Alloc_where(irn) == stack_alloc)
1039 curr_sp = adjust_alloc(env, irn, curr_sp);
1042 if (get_Free_where(irn) == stack_alloc)
1043 curr_sp = adjust_free(env, irn, curr_sp);
1046 panic("invalid call");
1050 /* Keep the last stack state in the block by tying it to Keep node,
1051 * the proj from calls is already kept */
1052 if (curr_sp != env->init_sp &&
1053 !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1055 keep = be_new_Keep(bl, 1, nodes);
1056 pmap_insert(env->keep_map, bl, keep);
1060 set_irn_link(bl, curr_sp);
1064 * Adjust all call nodes in the graph to the ABI conventions.
1066 static void process_calls(ir_graph *const irg, be_abi_irg_t *const abi)
1068 irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, abi);
1070 ir_heights = heights_new(irg);
1071 irg_block_walk_graph(irg, NULL, process_ops_in_block, abi);
1072 heights_free(ir_heights);
1076 * Computes the stack argument layout type.
1077 * Changes a possibly allocated value param type by moving
1078 * entities to the stack layout type.
1080 * @param call the current call ABI
1081 * @param method_type the method type
1083 * @return the stack argument layout type
1085 static ir_type *compute_arg_type(ir_graph *irg, be_abi_call_t *call,
1086 ir_type *method_type)
1088 struct obstack *obst = be_get_be_obst(irg);
1089 ir_type *frame_type = get_irg_frame_type(irg);
1090 size_t n_params = get_method_n_params(method_type);
1091 size_t n_frame_members = get_compound_n_members(frame_type);
1092 ir_entity *va_start_entity = NULL;
1098 ir_entity **map = OALLOCNZ(obst, ir_entity*, n_params);
1099 res = new_type_struct(new_id_from_chars("arg_type", 8));
1101 /* collect existing entities for value_param_types */
1102 for (f = n_frame_members; f > 0; ) {
1103 ir_entity *entity = get_compound_member(frame_type, --f);
1106 set_entity_link(entity, NULL);
1107 if (!is_parameter_entity(entity))
1109 num = get_entity_parameter_number(entity);
1110 if (num == IR_VA_START_PARAMETER_NUMBER) {
1111 /* move entity to new arg_type */
1112 set_entity_owner(entity, res);
1113 va_start_entity = entity;
1116 assert(num < n_params);
1117 if (map[num] != NULL)
1118 panic("multiple entities for parameter %u in %+F found", f, irg);
1120 if (num != n_params && get_call_arg(call, 0, num, 1)->in_reg) {
1121 /* don't move this entity */
1126 /* move entity to new arg_type */
1127 set_entity_owner(entity, res);
1130 for (i = 0; i < n_params; ++i) {
1131 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1132 ir_type *param_type = get_method_param_type(method_type, i);
1138 if (entity == NULL) {
1139 /* create a new entity */
1140 entity = new_parameter_entity(res, i, param_type);
1142 ofs += arg->space_before;
1143 ofs = round_up2(ofs, arg->alignment);
1144 set_entity_offset(entity, ofs);
1145 ofs += arg->space_after;
1146 ofs += get_type_size_bytes(param_type);
1147 arg->stack_ent = entity;
1149 if (va_start_entity != NULL) {
1150 set_entity_offset(va_start_entity, ofs);
1152 set_type_size_bytes(res, ofs);
1153 set_type_state(res, layout_fixed);
1159 const arch_register_t *reg;
1163 static int cmp_regs(const void *a, const void *b)
1165 const reg_node_map_t *p = (const reg_node_map_t*)a;
1166 const reg_node_map_t *q = (const reg_node_map_t*)b;
1168 if (p->reg->reg_class == q->reg->reg_class)
1169 return p->reg->index - q->reg->index;
1171 return p->reg->reg_class < q->reg->reg_class ? -1 : +1;
1174 static void reg_map_to_arr(reg_node_map_t *res, pmap *reg_map)
1177 size_t n = pmap_count(reg_map);
1180 foreach_pmap(reg_map, ent) {
1181 res[i].reg = (const arch_register_t*)ent->key;
1182 res[i].irn = (ir_node*)ent->value;
1186 qsort(res, n, sizeof(res[0]), cmp_regs);
1190 * Creates a be_Return for a Return node.
1192 * @param @env the abi environment
1193 * @param irn the Return node or NULL if there was none
1194 * @param bl the block where the be_Retun should be placed
1195 * @param mem the current memory
1196 * @param n_res number of return results
1198 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1199 ir_node *mem, int n_res)
1201 be_abi_call_t *call = env->call;
1202 ir_graph *irg = get_Block_irg(bl);
1203 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1205 pmap *reg_map = pmap_create();
1206 ir_node *keep = pmap_get(ir_node, env->keep_map, bl);
1213 const arch_register_t **regs;
1217 get the valid stack node in this block.
1218 If we had a call in that block there is a Keep constructed by process_calls()
1219 which points to the last stack modification in that block. we'll use
1220 it then. Else we use the stack from the start block and let
1221 the ssa construction fix the usage.
1223 stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1225 stack = get_irn_n(keep, 0);
1227 remove_End_keepalive(get_irg_end(irg), keep);
1230 /* Insert results for Return into the register map. */
1231 for (i = 0; i < n_res; ++i) {
1232 ir_node *res = get_Return_res(irn, i);
1233 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1234 assert(arg->in_reg && "return value must be passed in register");
1235 pmap_insert(reg_map, (void *) arg->reg, res);
1238 /* Add uses of the callee save registers. */
1239 foreach_pmap(env->regs, ent) {
1240 const arch_register_t *reg = (const arch_register_t*)ent->key;
1241 if ((reg->type & arch_register_type_ignore) || arch_register_is_callee_save(arch_env, reg))
1242 pmap_insert(reg_map, ent->key, ent->value);
1245 be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1248 Maximum size of the in array for Return nodes is
1249 return args + callee save/ignore registers + memory + stack pointer
1251 in_max = pmap_count(reg_map) + n_res + 2;
1253 in = ALLOCAN(ir_node*, in_max);
1254 regs = ALLOCAN(arch_register_t const*, in_max);
1257 in[1] = be_abi_reg_map_get(reg_map, arch_env->sp);
1259 regs[1] = arch_env->sp;
1262 /* clear SP entry, since it has already been grown. */
1263 pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1264 for (i = 0; i < n_res; ++i) {
1265 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1267 in[n] = be_abi_reg_map_get(reg_map, arg->reg);
1268 regs[n++] = arg->reg;
1270 /* Clear the map entry to mark the register as processed. */
1271 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1274 /* grow the rest of the stuff. */
1275 foreach_pmap(reg_map, ent) {
1277 in[n] = (ir_node*)ent->value;
1278 regs[n++] = (const arch_register_t*)ent->key;
1282 /* The in array for the new back end return is now ready. */
1284 dbgi = get_irn_dbg_info(irn);
1288 /* we have to pop the shadow parameter in in case of struct returns */
1290 ret = be_new_Return(dbgi, irg, bl, n_res, pop, n, in);
1292 /* Set the register classes of the return's parameter accordingly. */
1293 for (i = 0; i < n; ++i) {
1294 if (regs[i] == NULL)
1297 be_set_constr_single_reg_in(ret, i, regs[i], arch_register_req_type_none);
1300 /* Free the space of the Epilog's in array and the register <-> proj map. */
1301 pmap_destroy(reg_map);
1306 typedef struct lower_frame_sels_env_t {
1307 ir_node *frame; /**< the current frame */
1308 const arch_register_class_t *sp_class; /**< register class of the stack pointer */
1309 } lower_frame_sels_env_t;
1312 * Walker: Replaces Sels of frame type and
1313 * value param type entities by FrameAddress.
1314 * Links all used entities.
1316 static void lower_frame_sels_walker(ir_node *irn, void *data)
1318 lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1321 ir_node *ptr = get_Sel_ptr(irn);
1323 if (ptr == ctx->frame) {
1324 ir_entity *ent = get_Sel_entity(irn);
1325 ir_node *bl = get_nodes_block(irn);
1328 nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1335 * The start block has no jump, instead it has an initial exec Proj.
1336 * The backend wants to handle all blocks the same way, so we replace
1337 * the out cfg edge with a real jump.
1339 static void fix_start_block(ir_graph *irg)
1341 ir_node *initial_X = get_irg_initial_exec(irg);
1342 ir_node *start_block = get_irg_start_block(irg);
1343 ir_node *jmp = new_r_Jmp(start_block);
1345 assert(is_Proj(initial_X));
1346 exchange(initial_X, jmp);
1347 set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1349 /* merge start block with successor if possible */
1351 foreach_out_edge(jmp, edge) {
1352 ir_node *succ = get_edge_src_irn(edge);
1353 if (!is_Block(succ))
1356 if (get_irn_arity(succ) == 1) {
1357 exchange(succ, start_block);
1365 * Modify the irg itself and the frame type.
1367 static void modify_irg(ir_graph *const irg, be_abi_irg_t *const env)
1369 be_abi_call_t *call = env->call;
1370 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1371 const arch_register_t *sp = arch_env->sp;
1372 ir_type *method_type = get_entity_type(get_irg_entity(irg));
1373 be_irg_t *birg = be_birg_from_irg(irg);
1374 struct obstack *obst = be_get_be_obst(irg);
1375 be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
1378 ir_node *new_mem_proj;
1386 const arch_register_t *fp_reg;
1387 ir_node *frame_pointer;
1391 ir_type *arg_type, *bet_type;
1392 lower_frame_sels_env_t ctx;
1394 DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1396 old_mem = get_irg_initial_mem(irg);
1398 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1400 arg_type = compute_arg_type(irg, call, method_type);
1402 /* Convert the Sel nodes in the irg to frame addr nodes: */
1403 ctx.frame = get_irg_frame(irg);
1404 ctx.sp_class = arch_env->sp->reg_class;
1406 ir_type *const frame_tp = get_irg_frame_type(irg);
1407 /* layout the stackframe now */
1408 if (get_type_state(frame_tp) == layout_undefined) {
1409 default_layout_compound_type(frame_tp);
1412 /* align stackframe */
1413 unsigned const alignment = 1U << arch_env->stack_alignment;
1414 unsigned const frame_size = round_up2(get_type_size_bytes(frame_tp), alignment);
1415 set_type_size_bytes(frame_tp, frame_size);
1417 env->regs = pmap_create();
1419 n_params = get_method_n_params(method_type);
1420 args = OALLOCNZ(obst, ir_node*, n_params);
1422 be_add_parameter_entity_stores(irg);
1424 irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1426 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1428 /* Fill the argument vector */
1429 arg_tuple = get_irg_args(irg);
1430 foreach_out_edge(arg_tuple, edge) {
1431 ir_node *irn = get_edge_src_irn(edge);
1432 if (! is_Anchor(irn)) {
1433 int nr = get_Proj_proj(irn);
1435 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1439 stack_layout->sp_relative = call->flags.try_omit_fp;
1440 bet_type = call->cb->get_between_type(irg);
1441 stack_frame_init(stack_layout, arg_type, bet_type,
1442 get_irg_frame_type(irg));
1444 /* Count the register params and add them to the number of Projs for the RegParams node */
1445 for (i = 0; i < n_params; ++i) {
1446 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1447 if (arg->in_reg && args[i]) {
1448 assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1449 assert(i == get_Proj_proj(args[i]));
1451 /* For now, associate the register with the old Proj from Start representing that argument. */
1452 pmap_insert(env->regs, (void *) arg->reg, args[i]);
1453 DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1457 /* Collect all callee-save registers */
1458 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1459 const arch_register_class_t *cls = &arch_env->register_classes[i];
1460 for (j = 0; j < cls->n_regs; ++j) {
1461 const arch_register_t *reg = &cls->regs[j];
1462 if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1463 pmap_insert(env->regs, (void *) reg, NULL);
1468 fp_reg = call->flags.try_omit_fp ? arch_env->sp : arch_env->bp;
1469 rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1471 /* handle start block here (place a jump in the block) */
1472 fix_start_block(irg);
1474 pmap_insert(env->regs, (void *) sp, NULL);
1475 pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1476 start_bl = get_irg_start_block(irg);
1477 ir_node *const start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1478 set_irg_start(irg, start);
1481 * make proj nodes for the callee save registers.
1482 * memorize them, since Return nodes get those as inputs.
1484 * Note, that if a register corresponds to an argument, the regs map
1485 * contains the old Proj from start for that argument.
1487 rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1488 reg_map_to_arr(rm, env->regs);
1489 for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1490 const arch_register_t *reg = rm[i].reg;
1491 ir_mode *mode = reg->reg_class->mode;
1493 arch_register_req_type_t add_type = arch_register_req_type_none;
1497 add_type |= arch_register_req_type_produces_sp;
1498 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1499 add_type |= arch_register_req_type_ignore;
1503 proj = new_r_Proj(start, mode, nr + 1);
1504 pmap_insert(env->regs, (void *) reg, proj);
1505 be_set_constr_single_reg_out(start, nr + 1, reg, add_type);
1506 arch_set_irn_register(proj, reg);
1508 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1511 /* create a new initial memory proj */
1512 assert(is_Proj(old_mem));
1513 arch_set_irn_register_req_out(start, 0, arch_no_register_req);
1514 new_mem_proj = new_r_Proj(start, mode_M, 0);
1516 set_irg_initial_mem(irg, mem);
1518 env->init_sp = be_abi_reg_map_get(env->regs, sp);
1520 /* set new frame_pointer */
1521 frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1522 set_irg_frame(irg, frame_pointer);
1524 /* rewire old mem users to new mem */
1525 exchange(old_mem, mem);
1527 /* keep the mem (for functions with an endless loop = no return) */
1530 set_irg_initial_mem(irg, mem);
1532 /* Now, introduce stack param nodes for all parameters passed on the stack */
1533 for (i = 0; i < n_params; ++i) {
1534 ir_node *arg_proj = args[i];
1535 ir_node *repl = NULL;
1537 if (arg_proj != NULL) {
1538 be_abi_call_arg_t *arg;
1539 ir_type *param_type;
1540 int nr = get_Proj_proj(arg_proj);
1543 nr = MIN(nr, n_params);
1544 arg = get_call_arg(call, 0, nr, 1);
1545 param_type = get_method_param_type(method_type, nr);
1548 repl = pmap_get(ir_node, env->regs, arg->reg);
1550 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1552 /* For atomic parameters which are actually used, we create a Load node. */
1553 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1554 ir_mode *mode = get_type_mode(param_type);
1555 ir_mode *load_mode = arg->load_mode;
1556 ir_node *nomem = get_irg_no_mem(irg);
1558 ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1559 repl = new_r_Proj(load, load_mode, pn_Load_res);
1561 if (mode != load_mode) {
1562 repl = new_r_Conv(start_bl, repl, mode);
1565 /* The stack parameter is not primitive (it is a struct or array),
1566 * we thus will create a node representing the parameter's address
1572 assert(repl != NULL);
1574 /* Beware: the mode of the register parameters is always the mode of the register class
1575 which may be wrong. Add Conv's then. */
1576 mode = get_irn_mode(args[i]);
1577 if (mode != get_irn_mode(repl)) {
1578 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1580 exchange(args[i], repl);
1584 /* the arg proj is not needed anymore now and should be only used by the anchor */
1585 assert(get_irn_n_edges(arg_tuple) == 1);
1586 kill_node(arg_tuple);
1587 set_irg_args(irg, new_r_Bad(irg, mode_T));
1589 /* All Return nodes hang on the End node, so look for them there. */
1590 end = get_irg_end_block(irg);
1591 for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1592 ir_node *irn = get_Block_cfgpred(end, i);
1594 if (is_Return(irn)) {
1595 ir_node *blk = get_nodes_block(irn);
1596 ir_node *mem = get_Return_mem(irn);
1597 ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1602 /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1603 the code is dead and will never be executed. */
1606 /** Fix the state inputs of calls that still hang on unknowns */
1607 static void fix_call_state_inputs(ir_graph *const irg, be_abi_irg_t *const env)
1609 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1611 arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1613 /* Collect caller save registers */
1614 n = arch_env->n_register_classes;
1615 for (i = 0; i < n; ++i) {
1617 const arch_register_class_t *cls = &arch_env->register_classes[i];
1618 for (j = 0; j < cls->n_regs; ++j) {
1619 const arch_register_t *reg = arch_register_for_index(cls, j);
1620 if (reg->type & arch_register_type_state) {
1621 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1626 n = ARR_LEN(env->calls);
1627 n_states = ARR_LEN(stateregs);
1628 for (i = 0; i < n; ++i) {
1630 ir_node *call = env->calls[i];
1632 arity = get_irn_arity(call);
1634 /* the state reg inputs are the last n inputs of the calls */
1635 for (s = 0; s < n_states; ++s) {
1636 int inp = arity - n_states + s;
1637 const arch_register_t *reg = stateregs[s];
1638 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1640 set_irn_n(call, inp, regnode);
1644 DEL_ARR_F(stateregs);
1648 * Create a trampoline entity for the given method.
1650 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1652 ir_type *type = get_entity_type(method);
1653 ident *old_id = get_entity_ld_ident(method);
1654 ident *id = id_mangle3("", old_id, "$stub");
1655 ir_type *parent = be->pic_trampolines_type;
1656 ir_entity *ent = new_entity(parent, old_id, type);
1657 set_entity_ld_ident(ent, id);
1658 set_entity_visibility(ent, ir_visibility_private);
1664 * Returns the trampoline entity for the given method.
1666 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1668 ir_entity *result = pmap_get(ir_entity, env->ent_trampoline_map, method);
1669 if (result == NULL) {
1670 result = create_trampoline(env, method);
1671 pmap_insert(env->ent_trampoline_map, method, result);
1677 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1679 ident *old_id = get_entity_ld_ident(entity);
1680 ident *id = id_mangle3("", old_id, "$non_lazy_ptr");
1681 ir_type *e_type = get_entity_type(entity);
1682 ir_type *type = new_type_pointer(e_type);
1683 ir_type *parent = be->pic_symbols_type;
1684 ir_entity *ent = new_entity(parent, old_id, type);
1685 set_entity_ld_ident(ent, id);
1686 set_entity_visibility(ent, ir_visibility_private);
1691 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1693 ir_entity *result = pmap_get(ir_entity, env->ent_pic_symbol_map, entity);
1694 if (result == NULL) {
1695 result = create_pic_symbol(env, entity);
1696 pmap_insert(env->ent_pic_symbol_map, entity, result);
1705 * Returns non-zero if a given entity can be accessed using a relative address.
1707 static int can_address_relative(ir_entity *entity)
1709 return entity_has_definition(entity) && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1712 static ir_node *get_pic_base(ir_graph *irg)
1714 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1715 if (arch_env->impl->get_pic_base == NULL)
1717 return arch_env->impl->get_pic_base(irg);
1720 /** patches SymConsts to work in position independent code */
1721 static void fix_pic_symconsts(ir_node *node, void *data)
1723 ir_graph *irg = get_irn_irg(node);
1724 be_main_env_t *be = be_get_irg_main_env(irg);
1734 arity = get_irn_arity(node);
1735 for (i = 0; i < arity; ++i) {
1737 ir_node *pred = get_irn_n(node, i);
1739 ir_entity *pic_symbol;
1740 ir_node *pic_symconst;
1742 if (!is_SymConst(pred))
1745 entity = get_SymConst_entity(pred);
1746 block = get_nodes_block(pred);
1748 /* calls can jump to relative addresses, so we can directly jump to
1749 the (relatively) known call address or the trampoline */
1750 if (i == 1 && is_Call(node)) {
1751 ir_entity *trampoline;
1752 ir_node *trampoline_const;
1754 if (can_address_relative(entity))
1757 dbgi = get_irn_dbg_info(pred);
1758 trampoline = get_trampoline(be, entity);
1759 trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1761 set_irn_n(node, i, trampoline_const);
1765 /* everything else is accessed relative to EIP */
1766 mode = get_irn_mode(pred);
1767 pic_base = get_pic_base(irg);
1769 /* all ok now for locally constructed stuff */
1770 if (can_address_relative(entity)) {
1771 ir_node *add = new_r_Add(block, pic_base, pred, mode);
1773 /* make sure the walker doesn't visit this add again */
1774 mark_irn_visited(add);
1775 set_irn_n(node, i, add);
1779 /* get entry from pic symbol segment */
1780 dbgi = get_irn_dbg_info(pred);
1781 pic_symbol = get_pic_symbol(be, entity);
1782 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1784 add = new_r_Add(block, pic_base, pic_symconst, mode);
1785 mark_irn_visited(add);
1787 /* we need an extra indirection for global data outside our current
1788 module. The loads are always safe and can therefore float
1789 and need no memory input */
1790 load = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1791 load_res = new_r_Proj(load, mode, pn_Load_res);
1793 set_irn_n(node, i, load_res);
1797 void be_abi_introduce(ir_graph *irg)
1799 ir_node *old_frame = get_irg_frame(irg);
1800 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1801 ir_entity *entity = get_irg_entity(irg);
1802 ir_type *method_type = get_entity_type(entity);
1803 be_irg_t *birg = be_birg_from_irg(irg);
1804 struct obstack *obst = &birg->obst;
1805 ir_node *dummy = new_r_Dummy(irg,
1806 arch_env->sp->reg_class->mode);
1809 /* determine allocatable registers */
1810 assert(birg->allocatable_regs == NULL);
1811 birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1812 for (r = 0; r < arch_env->n_registers; ++r) {
1813 const arch_register_t *reg = &arch_env->registers[r];
1814 if ( !(reg->type & arch_register_type_ignore)) {
1815 rbitset_set(birg->allocatable_regs, r);
1819 /* Break here if backend provides a custom API. */
1822 env.keep_map = pmap_create();
1823 env.call = be_abi_call_new(arch_env->sp->reg_class);
1824 arch_env_get_call_abi(arch_env, method_type, env.call);
1826 env.init_sp = dummy;
1827 env.calls = NEW_ARR_F(ir_node*, 0);
1831 if (be_options.pic) {
1832 irg_walk_graph(irg, fix_pic_symconsts, NULL, NULL);
1835 /* Lower all call nodes in the IRG. */
1836 process_calls(irg, &env);
1838 /* Process the IRG */
1839 modify_irg(irg, &env);
1841 /* fix call inputs for state registers */
1842 fix_call_state_inputs(irg, &env);
1844 be_abi_call_free(env.call);
1846 /* We don't need the keep map anymore. */
1847 pmap_destroy(env.keep_map);
1849 /* calls array is not needed anymore */
1850 DEL_ARR_F(env.calls);
1852 /* reroute the stack origin of the calls to the true stack origin. */
1853 exchange(dummy, env.init_sp);
1854 exchange(old_frame, get_irg_frame(irg));
1856 pmap_destroy(env.regs);
1859 void be_put_allocatable_regs(const ir_graph *irg,
1860 const arch_register_class_t *cls, bitset_t *bs)
1862 be_irg_t *birg = be_birg_from_irg(irg);
1863 unsigned *allocatable_regs = birg->allocatable_regs;
1866 assert(bitset_size(bs) == cls->n_regs);
1867 bitset_clear_all(bs);
1868 for (i = 0; i < cls->n_regs; ++i) {
1869 const arch_register_t *reg = &cls->regs[i];
1870 if (rbitset_is_set(allocatable_regs, reg->global_index))
1875 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1876 const arch_register_class_t *cls)
1878 bitset_t *bs = bitset_alloca(cls->n_regs);
1879 be_put_allocatable_regs(irg, cls, bs);
1880 return bitset_popcount(bs);
1883 void be_set_allocatable_regs(const ir_graph *irg,
1884 const arch_register_class_t *cls,
1885 unsigned *raw_bitset)
1887 be_irg_t *birg = be_birg_from_irg(irg);
1888 unsigned *allocatable_regs = birg->allocatable_regs;
1891 rbitset_clear_all(raw_bitset, cls->n_regs);
1892 for (i = 0; i < cls->n_regs; ++i) {
1893 const arch_register_t *reg = &cls->regs[i];
1894 if (rbitset_is_set(allocatable_regs, reg->global_index))
1895 rbitset_set(raw_bitset, i);
1899 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
1900 void be_init_abi(void)
1902 FIRM_DBG_REGISTER(dbg, "firm.be.abi");