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 in registers. */
64 unsigned on_stack : 1; /**< 1: this argument is transmitted on the stack. */
65 unsigned callee : 1; /**< 1: someone called us. 0: We call another function */
68 const arch_register_t *reg;
71 unsigned alignment; /**< stack alignment */
72 unsigned space_before; /**< allocate space before */
73 unsigned space_after; /**< allocate space after */
76 struct be_abi_call_t {
77 be_abi_call_flags_t flags; /**< Flags describing the ABI behavior on calls */
78 int pop; /**< number of bytes the stack frame is shrinked by the callee on return. */
79 const be_abi_callbacks_t *cb;
80 ir_type *between_type;
82 const arch_register_class_t *cls_addr; /**< register class of the call address */
86 * The ABI information for the current graph.
89 be_abi_call_t *call; /**< The ABI call information. */
91 ir_node *init_sp; /**< The node representing the stack pointer
92 at the start of the function. */
94 ir_node *start; /**< The be_Start params node. */
95 pmap *regs; /**< A map of all callee-save and ignore regs to
96 their Projs to the RegParams node. */
97 int start_block_bias; /**< The stack bias at the end of the start block. */
99 pmap *keep_map; /**< mapping blocks to keep nodes. */
101 ir_node **calls; /**< flexible array containing all be_Call nodes */
104 static ir_heights_t *ir_heights;
106 /** Flag: if set, try to omit the frame pointer in all routines. */
107 static int be_omit_fp = 1;
109 static ir_node *be_abi_reg_map_get(pmap *map, const arch_register_t *reg)
111 return pmap_get(ir_node, map, reg);
114 static void be_abi_reg_map_set(pmap *map, const arch_register_t* reg,
117 pmap_insert(map, reg, node);
121 * Check if the given register is callee save, ie. will be saved by the callee.
123 static bool arch_register_is_callee_save(
124 const arch_env_t *arch_env,
125 const arch_register_t *reg)
127 if (arch_env->impl->register_saved_by)
128 return arch_env->impl->register_saved_by(reg, /*callee=*/1);
133 * Check if the given register is caller save, ie. must be saved by the caller.
135 static bool arch_register_is_caller_save(
136 const arch_env_t *arch_env,
137 const arch_register_t *reg)
139 if (arch_env->impl->register_saved_by)
140 return arch_env->impl->register_saved_by(reg, /*callee=*/0);
147 _ ____ ___ ____ _ _ _ _
148 / \ | __ )_ _| / ___|__ _| | | |__ __ _ ___| | _____
149 / _ \ | _ \| | | | / _` | | | '_ \ / _` |/ __| |/ / __|
150 / ___ \| |_) | | | |__| (_| | | | |_) | (_| | (__| <\__ \
151 /_/ \_\____/___| \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
153 These callbacks are used by the backend to set the parameters
154 for a specific call type.
158 * Set compare function: compares two ABI call object arguments.
160 static int cmp_call_arg(const void *a, const void *b, size_t n)
162 const be_abi_call_arg_t *p = (const be_abi_call_arg_t*)a;
163 const be_abi_call_arg_t *q = (const be_abi_call_arg_t*)b;
165 return !(p->is_res == q->is_res && p->pos == q->pos && p->callee == q->callee);
169 * Get an ABI call object argument.
171 * @param call the abi call
172 * @param is_res true for call results, false for call arguments
173 * @param pos position of the argument
174 * @param callee context type - if we are callee or caller
176 static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos, int callee)
178 be_abi_call_arg_t arg;
181 memset(&arg, 0, sizeof(arg));
186 hash = is_res * 128 + pos;
188 return (be_abi_call_arg_t*)set_find(call->params, &arg, sizeof(arg), hash);
192 * Set an ABI call object argument.
194 static void remember_call_arg(be_abi_call_arg_t *arg, be_abi_call_t *call, be_abi_context_t context)
196 unsigned hash = arg->is_res * 128 + arg->pos;
197 if (context & ABI_CONTEXT_CALLEE) {
199 set_insert(call->params, arg, sizeof(*arg), hash);
201 if (context & ABI_CONTEXT_CALLER) {
203 set_insert(call->params, arg, sizeof(*arg), hash);
207 /* Set the flags for a call. */
208 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
214 /* Sets the number of bytes the stackframe is shrinked by the callee on return */
215 void be_abi_call_set_pop(be_abi_call_t *call, int pop)
221 /* Set register class for call address */
222 void be_abi_call_set_call_address_reg_class(be_abi_call_t *call, const arch_register_class_t *cls)
224 call->cls_addr = cls;
228 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos,
229 ir_mode *load_mode, unsigned alignment,
230 unsigned space_before, unsigned space_after,
231 be_abi_context_t context)
233 be_abi_call_arg_t arg;
234 memset(&arg, 0, sizeof(arg));
235 assert(alignment > 0 && "Alignment must be greater than 0");
237 arg.load_mode = load_mode;
238 arg.alignment = alignment;
239 arg.space_before = space_before;
240 arg.space_after = space_after;
244 remember_call_arg(&arg, call, context);
247 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
249 be_abi_call_arg_t arg;
250 memset(&arg, 0, sizeof(arg));
257 remember_call_arg(&arg, call, context);
260 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
262 be_abi_call_arg_t arg;
263 memset(&arg, 0, sizeof(arg));
270 remember_call_arg(&arg, call, context);
273 /* Get the flags of a ABI call object. */
274 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
280 * Constructor for a new ABI call object.
282 * @param cls_addr register class of the call address
284 * @return the new ABI call object
286 static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
288 be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
291 call->params = new_set(cmp_call_arg, 16);
293 call->cls_addr = cls_addr;
295 call->flags.bits.try_omit_fp = be_omit_fp;
301 * Destructor for an ABI call object.
303 static void be_abi_call_free(be_abi_call_t *call)
305 del_set(call->params);
310 * Initializes the frame layout from parts
312 * @param frame the stack layout that will be initialized
313 * @param args the stack argument layout type
314 * @param between the between layout type
315 * @param locals the method frame type
317 * @return the initialized stack layout
319 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
320 ir_type *between, ir_type *locals)
322 frame->arg_type = args;
323 frame->between_type = between;
324 frame->frame_type = locals;
325 frame->initial_offset = 0;
326 frame->initial_bias = 0;
327 frame->order[1] = between;
329 /* typical decreasing stack: locals have the
330 * lowest addresses, arguments the highest */
331 frame->order[0] = locals;
332 frame->order[2] = args;
343 Adjustment of the calls inside a graph.
348 * Transform a call node into a be_Call node.
350 * @param env The ABI environment for the current irg.
351 * @param irn The call node.
352 * @param curr_sp The stack pointer node to use.
353 * @return The stack pointer after the call.
355 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
357 ir_graph *irg = get_irn_irg(irn);
358 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
359 ir_type *call_tp = get_Call_type(irn);
360 ir_node *call_ptr = get_Call_ptr(irn);
361 size_t n_params = get_method_n_params(call_tp);
362 ir_node *curr_mem = get_Call_mem(irn);
363 ir_node *bl = get_nodes_block(irn);
365 const arch_register_t *sp = arch_env->sp;
366 be_abi_call_t *call = be_abi_call_new(sp->reg_class);
367 ir_mode *mach_mode = sp->reg_class->mode;
368 int n_res = get_method_n_ress(call_tp);
370 ir_node *res_proj = NULL;
371 int n_reg_params = 0;
372 int n_stack_params = 0;
375 const arch_register_t **states = NEW_ARR_F(const arch_register_t*, 0);
376 const arch_register_t **destroyed_regs = NEW_ARR_F(const arch_register_t*, 0);
380 int n_reg_results = 0;
381 const ir_edge_t *edge;
383 int *stack_param_idx;
385 int throws_exception;
390 /* Let the isa fill out the abi description for that call node. */
391 arch_env_get_call_abi(arch_env, call_tp, call);
393 /* Insert code to put the stack arguments on the stack. */
394 assert(get_Call_n_params(irn) == n_params);
395 stack_param_idx = ALLOCAN(int, n_params);
396 for (p = 0; p < n_params; ++p) {
397 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
400 int arg_size = get_type_size_bytes(get_method_param_type(call_tp, p));
402 stack_size += round_up2(arg->space_before, arg->alignment);
403 stack_size += round_up2(arg_size, arg->alignment);
404 stack_size += round_up2(arg->space_after, arg->alignment);
406 stack_param_idx[n_stack_params++] = p;
410 /* Collect all arguments which are passed in registers. */
411 reg_param_idxs = ALLOCAN(int, n_params);
412 for (p = 0; p < n_params; ++p) {
413 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
414 if (arg && arg->in_reg) {
415 reg_param_idxs[n_reg_params++] = p;
420 * If the stack is decreasing and we do not want to store sequentially,
421 * or someone else allocated the call frame
422 * we allocate as much space on the stack all parameters need, by
423 * moving the stack pointer along the stack's direction.
425 * Note: we also have to do this for stack_size == 0, because we may have
426 * to adjust stack alignment for the call.
428 curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
430 dbgi = get_irn_dbg_info(irn);
431 /* If there are some parameters which shall be passed on the stack. */
432 if (n_stack_params > 0) {
434 ir_node **in = ALLOCAN(ir_node*, n_stack_params+1);
437 curr_mem = get_Call_mem(irn);
438 in[n_in++] = curr_mem;
440 for (i = 0; i < n_stack_params; ++i) {
441 int p = stack_param_idx[i];
442 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
443 ir_node *param = get_Call_param(irn, p);
444 ir_node *addr = curr_sp;
446 ir_type *param_type = get_method_param_type(call_tp, p);
447 int param_size = get_type_size_bytes(param_type) + arg->space_after;
450 * If we wanted to build the arguments sequentially,
451 * the stack pointer for the next must be incremented,
452 * and the memory value propagated.
454 curr_ofs += arg->space_before;
455 curr_ofs = round_up2(curr_ofs, arg->alignment);
457 /* Make the expression to compute the argument's offset. */
459 ir_mode *constmode = mach_mode;
460 if (mode_is_reference(mach_mode)) {
463 addr = new_r_Const_long(irg, constmode, curr_ofs);
464 addr = new_r_Add(bl, curr_sp, addr, mach_mode);
467 /* Insert a store for primitive arguments. */
468 if (is_atomic_type(param_type)) {
469 ir_node *nomem = get_irg_no_mem(irg);
470 ir_node *mem_input = nomem;
471 ir_node *store = new_rd_Store(dbgi, bl, mem_input, addr, param, cons_none);
472 mem = new_r_Proj(store, mode_M, pn_Store_M);
474 /* Make a mem copy for compound arguments. */
477 assert(mode_is_reference(get_irn_mode(param)));
478 copy = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type);
479 mem = new_r_Proj(copy, mode_M, pn_CopyB_M);
482 curr_ofs += param_size;
487 /* We need the sync only, if we didn't build the stores sequentially. */
488 if (n_stack_params >= 1) {
489 curr_mem = new_r_Sync(bl, n_in, in);
491 curr_mem = get_Call_mem(irn);
495 /* Put caller save into the destroyed set and state registers in the states
497 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
499 const arch_register_class_t *cls = &arch_env->register_classes[i];
500 for (j = 0; j < cls->n_regs; ++j) {
501 const arch_register_t *reg = arch_register_for_index(cls, j);
503 /* even if destroyed all is specified, neither SP nor FP are
504 * destroyed (else bad things will happen) */
505 if (reg == arch_env->sp || reg == arch_env->bp)
508 if (reg->type & arch_register_type_state) {
509 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
510 ARR_APP1(const arch_register_t*, states, reg);
511 /* we're already in the destroyed set so no need for further
515 if (arch_register_is_caller_save(arch_env, reg)) {
516 if (!(reg->type & arch_register_type_ignore)) {
517 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
523 /* search the largest result proj number */
524 res_projs = ALLOCANZ(ir_node*, n_res);
526 foreach_out_edge(irn, edge) {
527 const ir_edge_t *res_edge;
528 ir_node *irn = get_edge_src_irn(edge);
530 if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
533 foreach_out_edge(irn, res_edge) {
535 ir_node *res = get_edge_src_irn(res_edge);
537 assert(is_Proj(res));
539 proj = get_Proj_proj(res);
540 assert(proj < n_res);
541 assert(res_projs[proj] == NULL);
542 res_projs[proj] = res;
548 /** TODO: this is not correct for cases where return values are passed
549 * on the stack, but no known ABI does this currently...
551 n_reg_results = n_res;
554 in = ALLOCAN(ir_node*, n_reg_params + ARR_LEN(states));
556 /* make the back end call node and set its register requirements. */
557 for (i = 0; i < n_reg_params; ++i) {
558 in[n_ins++] = get_Call_param(irn, reg_param_idxs[i]);
561 /* add state registers ins */
562 for (s = 0; s < ARR_LEN(states); ++s) {
563 const arch_register_t *reg = states[s];
564 const arch_register_class_t *cls = reg->reg_class;
565 ir_node *regnode = new_r_Unknown(irg, cls->mode);
566 in[n_ins++] = regnode;
568 assert(n_ins == (int) (n_reg_params + ARR_LEN(states)));
570 /* ins collected, build the call */
571 throws_exception = ir_throws_exception(irn);
572 if (env->call->flags.bits.call_has_imm && is_SymConst(call_ptr)) {
574 low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, curr_sp,
575 n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
576 n_ins, in, get_Call_type(irn));
577 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
580 low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, call_ptr,
581 n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
582 n_ins, in, get_Call_type(irn));
584 ir_set_throws_exception(low_call, throws_exception);
585 be_Call_set_pop(low_call, call->pop);
587 /* put the call into the list of all calls for later processing */
588 ARR_APP1(ir_node *, env->calls, low_call);
590 /* create new stack pointer */
591 curr_sp = new_r_Proj(low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
592 be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
593 arch_register_req_type_ignore | arch_register_req_type_produces_sp);
594 arch_set_irn_register(curr_sp, sp);
596 /* now handle results */
597 for (i = 0; i < n_res; ++i) {
598 ir_node *proj = res_projs[i];
599 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 0);
600 long pn = i + pn_be_Call_first_res;
602 /* returns values on stack not supported yet */
606 shift the proj number to the right, since we will drop the
607 unspeakable Proj_T from the Call. Therefore, all real argument
608 Proj numbers must be increased by pn_be_Call_first_res
610 pn = i + pn_be_Call_first_res;
613 ir_type *res_type = get_method_res_type(call_tp, i);
614 ir_mode *mode = get_type_mode(res_type);
615 proj = new_r_Proj(low_call, mode, pn);
618 set_Proj_pred(proj, low_call);
619 set_Proj_proj(proj, pn);
623 /* remove register from destroyed regs */
625 size_t n = ARR_LEN(destroyed_regs);
626 for (j = 0; j < n; ++j) {
627 if (destroyed_regs[j] == arg->reg) {
628 destroyed_regs[j] = destroyed_regs[n-1];
629 ARR_SHRINKLEN(destroyed_regs,n-1);
637 Set the register class of the call address to
638 the backend provided class (default: stack pointer class)
640 be_node_set_reg_class_in(low_call, n_be_Call_ptr, call->cls_addr);
642 DBG((dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
644 /* Set the register classes and constraints of the Call parameters. */
645 for (i = 0; i < n_reg_params; ++i) {
646 int index = reg_param_idxs[i];
647 be_abi_call_arg_t *arg = get_call_arg(call, 0, index, 0);
648 assert(arg->reg != NULL);
650 be_set_constr_single_reg_in(low_call, n_be_Call_first_arg + i,
651 arg->reg, arch_register_req_type_none);
654 /* Set the register constraints of the results. */
655 for (i = 0; i < n_res; ++i) {
656 ir_node *proj = res_projs[i];
657 const be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 0);
658 int pn = get_Proj_proj(proj);
661 be_set_constr_single_reg_out(low_call, pn, arg->reg,
662 arch_register_req_type_none);
663 arch_set_irn_register(proj, arg->reg);
665 exchange(irn, low_call);
667 /* kill the ProjT node */
668 if (res_proj != NULL) {
672 /* Make additional projs for the caller save registers
673 and the Keep node which keeps them alive. */
679 int curr_res_proj = pn_be_Call_first_res + n_reg_results;
682 n_ins = ARR_LEN(destroyed_regs) + n_reg_results + 1;
683 in = ALLOCAN(ir_node *, n_ins);
685 /* also keep the stack pointer */
686 set_irn_link(curr_sp, (void*) sp);
689 for (d = 0; d < ARR_LEN(destroyed_regs); ++d) {
690 const arch_register_t *reg = destroyed_regs[d];
691 ir_node *proj = new_r_Proj(low_call, reg->reg_class->mode, curr_res_proj);
693 /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
694 be_set_constr_single_reg_out(low_call, curr_res_proj, reg,
695 arch_register_req_type_none);
696 arch_set_irn_register(proj, reg);
698 set_irn_link(proj, (void*) reg);
703 for (i = 0; i < n_reg_results; ++i) {
704 ir_node *proj = res_projs[i];
705 const arch_register_t *reg = arch_get_irn_register(proj);
706 set_irn_link(proj, (void*) reg);
711 /* create the Keep for the caller save registers */
712 keep = be_new_Keep(bl, n, in);
713 for (i = 0; i < n; ++i) {
714 const arch_register_t *reg = (const arch_register_t*)get_irn_link(in[i]);
715 be_node_set_reg_class_in(keep, i, arch_register_get_class(reg));
719 /* Clean up the stack. */
720 assert(stack_size >= call->pop);
721 stack_size -= call->pop;
723 if (stack_size > 0) {
724 ir_node *mem_proj = NULL;
726 foreach_out_edge(low_call, edge) {
727 ir_node *irn = get_edge_src_irn(edge);
728 if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
735 mem_proj = new_r_Proj(low_call, mode_M, pn_be_Call_M);
736 keep_alive(mem_proj);
739 /* Clean up the stack frame or revert alignment fixes if we allocated it */
740 curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
742 be_abi_call_free(call);
745 DEL_ARR_F(destroyed_regs);
751 * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
753 * @param alignment the minimum stack alignment
754 * @param size the node containing the non-aligned size
755 * @param block the block where new nodes are allocated on
756 * @param dbg debug info for new nodes
758 * @return a node representing the aligned size
760 static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
761 ir_node *block, dbg_info *dbg)
763 if (stack_alignment > 1) {
769 assert(is_po2(stack_alignment));
771 mode = get_irn_mode(size);
772 tv = new_tarval_from_long(stack_alignment-1, mode);
773 irg = get_Block_irg(block);
774 mask = new_r_Const(irg, tv);
775 size = new_rd_Add(dbg, block, size, mask, mode);
777 tv = new_tarval_from_long(-(long)stack_alignment, mode);
778 mask = new_r_Const(irg, tv);
779 size = new_rd_And(dbg, block, size, mask, mode);
785 * The alloca is transformed into a back end alloca node and connected to the stack nodes.
787 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
789 ir_node *block = get_nodes_block(alloc);
790 ir_graph *irg = get_Block_irg(block);
791 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
792 ir_node *alloc_mem = NULL;
793 ir_node *alloc_res = NULL;
794 ir_type *type = get_Alloc_type(alloc);
797 const ir_edge_t *edge;
802 unsigned stack_alignment;
804 /* all non-stack Alloc nodes should already be lowered before the backend */
805 assert(get_Alloc_where(alloc) == stack_alloc);
807 foreach_out_edge(alloc, edge) {
808 ir_node *irn = get_edge_src_irn(edge);
810 assert(is_Proj(irn));
811 switch (get_Proj_proj(irn)) {
823 /* Beware: currently Alloc nodes without a result might happen,
824 only escape analysis kills them and this phase runs only for object
825 oriented source. We kill the Alloc here. */
826 if (alloc_res == NULL && alloc_mem) {
827 exchange(alloc_mem, get_Alloc_mem(alloc));
831 dbg = get_irn_dbg_info(alloc);
832 count = get_Alloc_count(alloc);
834 /* we might need to multiply the count with the element size */
835 if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
836 ir_mode *mode = get_irn_mode(count);
837 ir_tarval *tv = new_tarval_from_long(get_type_size_bytes(type),
839 ir_node *cnst = new_rd_Const(dbg, irg, tv);
840 size = new_rd_Mul(dbg, block, count, cnst, mode);
845 /* The stack pointer will be modified in an unknown manner.
846 We cannot omit it. */
847 env->call->flags.bits.try_omit_fp = 0;
849 stack_alignment = 1 << arch_env->stack_alignment;
850 size = adjust_alloc_size(stack_alignment, size, block, dbg);
851 new_alloc = be_new_AddSP(arch_env->sp, block, curr_sp, size);
852 set_irn_dbg_info(new_alloc, dbg);
854 if (alloc_mem != NULL) {
858 addsp_mem = new_r_Proj(new_alloc, mode_M, pn_be_AddSP_M);
860 /* We need to sync the output mem of the AddSP with the input mem
861 edge into the alloc node. */
862 ins[0] = get_Alloc_mem(alloc);
864 sync = new_r_Sync(block, 2, ins);
866 exchange(alloc_mem, sync);
869 exchange(alloc, new_alloc);
871 /* fix projnum of alloca res */
872 set_Proj_proj(alloc_res, pn_be_AddSP_res);
874 curr_sp = new_r_Proj(new_alloc, get_irn_mode(curr_sp), pn_be_AddSP_sp);
881 * The Free is transformed into a back end free node and connected to the stack nodes.
883 static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
885 ir_node *block = get_nodes_block(free);
886 ir_graph *irg = get_irn_irg(free);
887 ir_type *type = get_Free_type(free);
888 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
889 ir_mode *sp_mode = arch_env->sp->reg_class->mode;
890 dbg_info *dbg = get_irn_dbg_info(free);
891 ir_node *subsp, *mem, *res, *size, *sync;
893 unsigned stack_alignment;
895 /* all non-stack-alloc Free nodes should already be lowered before the
897 assert(get_Free_where(free) == stack_alloc);
899 /* we might need to multiply the size with the element size */
900 if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
901 ir_tarval *tv = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
902 ir_node *cnst = new_rd_Const(dbg, irg, tv);
903 ir_node *mul = new_rd_Mul(dbg, block, get_Free_count(free),
907 size = get_Free_count(free);
910 stack_alignment = 1 << arch_env->stack_alignment;
911 size = adjust_alloc_size(stack_alignment, size, block, dbg);
913 /* The stack pointer will be modified in an unknown manner.
914 We cannot omit it. */
915 env->call->flags.bits.try_omit_fp = 0;
916 subsp = be_new_SubSP(arch_env->sp, block, curr_sp, size);
917 set_irn_dbg_info(subsp, dbg);
919 mem = new_r_Proj(subsp, mode_M, pn_be_SubSP_M);
920 res = new_r_Proj(subsp, sp_mode, pn_be_SubSP_sp);
922 /* we need to sync the memory */
923 in[0] = get_Free_mem(free);
925 sync = new_r_Sync(block, 2, in);
927 /* and make the AddSP dependent on the former memory */
928 add_irn_dep(subsp, get_Free_mem(free));
931 exchange(free, sync);
938 * Check if a node is somehow data dependent on another one.
939 * both nodes must be in the same basic block.
940 * @param n1 The first node.
941 * @param n2 The second node.
942 * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
944 static int dependent_on(ir_node *n1, ir_node *n2)
946 assert(get_nodes_block(n1) == get_nodes_block(n2));
948 return heights_reachable_in_block(ir_heights, n1, n2);
951 static int cmp_call_dependency(const void *c1, const void *c2)
953 ir_node *n1 = *(ir_node **) c1;
954 ir_node *n2 = *(ir_node **) c2;
958 Classical qsort() comparison function behavior:
959 0 if both elements are equal
960 1 if second is "smaller" that first
961 -1 if first is "smaller" that second
963 if (dependent_on(n1, n2))
966 if (dependent_on(n2, n1))
969 /* The nodes have no depth order, but we need a total order because qsort()
972 * Additionally, we need to respect transitive dependencies. Consider a
973 * Call a depending on Call b and an independent Call c.
974 * We MUST NOT order c > a and b > c. */
975 h1 = get_irn_height(ir_heights, n1);
976 h2 = get_irn_height(ir_heights, n2);
977 if (h1 < h2) return -1;
978 if (h1 > h2) return 1;
979 /* Same height, so use a random (but stable) order */
980 return get_irn_idx(n1) - get_irn_idx(n2);
984 * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
986 static void link_ops_in_block_walker(ir_node *irn, void *data)
988 be_abi_irg_t *env = (be_abi_irg_t*)data;
989 unsigned code = get_irn_opcode(irn);
991 if (code == iro_Call ||
992 (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
993 (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
994 ir_node *bl = get_nodes_block(irn);
995 void *save = get_irn_link(bl);
997 set_irn_link(irn, save);
998 set_irn_link(bl, irn);
1001 if (code == iro_Builtin && get_Builtin_kind(irn) == ir_bk_return_address) {
1002 ir_node *param = get_Builtin_param(irn, 0);
1003 ir_tarval *tv = get_Const_tarval(param);
1004 unsigned long value = get_tarval_long(tv);
1005 /* use ebp, so the climbframe algo works... */
1007 env->call->flags.bits.try_omit_fp = 0;
1014 * Process all Call/Alloc/Free nodes inside a basic block.
1015 * Note that the link field of the block must contain a linked list of all
1016 * nodes inside the Block. We first order this list according to data dependency
1017 * and that connect the nodes together.
1019 static void process_ops_in_block(ir_node *bl, void *data)
1021 be_abi_irg_t *env = (be_abi_irg_t*)data;
1022 ir_node *curr_sp = env->init_sp;
1029 for (irn = (ir_node*)get_irn_link(bl); irn != NULL;
1030 irn = (ir_node*)get_irn_link(irn)) {
1034 nodes = ALLOCAN(ir_node*, n_nodes);
1035 for (irn = (ir_node*)get_irn_link(bl), n = 0; irn != NULL;
1036 irn = (ir_node*)get_irn_link(irn), ++n) {
1040 /* If there were call nodes in the block. */
1045 /* order the call nodes according to data dependency */
1046 qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
1048 for (i = n_nodes - 1; i >= 0; --i) {
1049 ir_node *irn = nodes[i];
1051 DBG((dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1052 switch (get_irn_opcode(irn)) {
1055 /* The stack pointer will be modified due to a call. */
1056 env->call->flags.bits.try_omit_fp = 0;
1058 curr_sp = adjust_call(env, irn, curr_sp);
1061 if (get_Alloc_where(irn) == stack_alloc)
1062 curr_sp = adjust_alloc(env, irn, curr_sp);
1065 if (get_Free_where(irn) == stack_alloc)
1066 curr_sp = adjust_free(env, irn, curr_sp);
1069 panic("invalid call");
1073 /* Keep the last stack state in the block by tying it to Keep node,
1074 * the proj from calls is already kept */
1075 if (curr_sp != env->init_sp &&
1076 !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1078 keep = be_new_Keep(bl, 1, nodes);
1079 pmap_insert(env->keep_map, bl, keep);
1083 set_irn_link(bl, curr_sp);
1087 * Adjust all call nodes in the graph to the ABI conventions.
1089 static void process_calls(ir_graph *irg)
1091 be_abi_irg_t *abi = be_get_irg_abi(irg);
1093 irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, abi);
1095 ir_heights = heights_new(irg);
1096 irg_block_walk_graph(irg, NULL, process_ops_in_block, abi);
1097 heights_free(ir_heights);
1101 * Computes the stack argument layout type.
1102 * Changes a possibly allocated value param type by moving
1103 * entities to the stack layout type.
1105 * @param call the current call ABI
1106 * @param method_type the method type
1108 * @return the stack argument layout type
1110 static ir_type *compute_arg_type(ir_graph *irg, be_abi_call_t *call,
1111 ir_type *method_type)
1113 struct obstack *obst = be_get_be_obst(irg);
1114 ir_type *frame_type = get_irg_frame_type(irg);
1115 size_t n_params = get_method_n_params(method_type);
1116 size_t n_frame_members = get_compound_n_members(frame_type);
1117 ir_entity *va_start_entity = NULL;
1123 ir_entity **map = OALLOCNZ(obst, ir_entity*, n_params);
1124 res = new_type_struct(new_id_from_chars("arg_type", 8));
1126 /* collect existing entities for value_param_types */
1127 for (f = n_frame_members; f > 0; ) {
1128 ir_entity *entity = get_compound_member(frame_type, --f);
1131 set_entity_link(entity, NULL);
1132 if (!is_parameter_entity(entity))
1134 num = get_entity_parameter_number(entity);
1135 if (num == IR_VA_START_PARAMETER_NUMBER) {
1136 /* move entity to new arg_type */
1137 set_entity_owner(entity, res);
1138 va_start_entity = entity;
1141 assert(num < n_params);
1142 if (map[num] != NULL)
1143 panic("multiple entities for parameter %u in %+F found", f, irg);
1145 if (num != n_params && !get_call_arg(call, 0, num, 1)->on_stack) {
1146 /* don't move this entity */
1151 /* move entity to new arg_type */
1152 set_entity_owner(entity, res);
1155 for (i = 0; i < n_params; ++i) {
1156 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1157 ir_type *param_type = get_method_param_type(method_type, i);
1160 if (!arg->on_stack) {
1164 if (entity == NULL) {
1165 /* create a new entity */
1166 entity = new_parameter_entity(res, i, param_type);
1168 ofs += arg->space_before;
1169 ofs = round_up2(ofs, arg->alignment);
1170 set_entity_offset(entity, ofs);
1171 ofs += arg->space_after;
1172 ofs += get_type_size_bytes(param_type);
1173 arg->stack_ent = entity;
1175 if (va_start_entity != NULL) {
1176 set_entity_offset(va_start_entity, ofs);
1178 set_type_size_bytes(res, ofs);
1179 set_type_state(res, layout_fixed);
1185 const arch_register_t *reg;
1189 static int cmp_regs(const void *a, const void *b)
1191 const reg_node_map_t *p = (const reg_node_map_t*)a;
1192 const reg_node_map_t *q = (const reg_node_map_t*)b;
1194 if (p->reg->reg_class == q->reg->reg_class)
1195 return p->reg->index - q->reg->index;
1197 return p->reg->reg_class < q->reg->reg_class ? -1 : +1;
1200 static void reg_map_to_arr(reg_node_map_t *res, pmap *reg_map)
1203 size_t n = pmap_count(reg_map);
1206 foreach_pmap(reg_map, ent) {
1207 res[i].reg = (const arch_register_t*)ent->key;
1208 res[i].irn = (ir_node*)ent->value;
1212 qsort(res, n, sizeof(res[0]), cmp_regs);
1216 * Creates a be_Return for a Return node.
1218 * @param @env the abi environment
1219 * @param irn the Return node or NULL if there was none
1220 * @param bl the block where the be_Retun should be placed
1221 * @param mem the current memory
1222 * @param n_res number of return results
1224 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1225 ir_node *mem, int n_res)
1227 be_abi_call_t *call = env->call;
1228 ir_graph *irg = get_Block_irg(bl);
1229 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1231 pmap *reg_map = pmap_create();
1232 ir_node *keep = pmap_get(ir_node, env->keep_map, bl);
1239 const arch_register_t **regs;
1243 get the valid stack node in this block.
1244 If we had a call in that block there is a Keep constructed by process_calls()
1245 which points to the last stack modification in that block. we'll use
1246 it then. Else we use the stack from the start block and let
1247 the ssa construction fix the usage.
1249 stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1251 stack = get_irn_n(keep, 0);
1253 remove_End_keepalive(get_irg_end(irg), keep);
1256 /* Insert results for Return into the register map. */
1257 for (i = 0; i < n_res; ++i) {
1258 ir_node *res = get_Return_res(irn, i);
1259 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1260 assert(arg->in_reg && "return value must be passed in register");
1261 pmap_insert(reg_map, (void *) arg->reg, res);
1264 /* Add uses of the callee save registers. */
1265 foreach_pmap(env->regs, ent) {
1266 const arch_register_t *reg = (const arch_register_t*)ent->key;
1267 if ((reg->type & arch_register_type_ignore) || arch_register_is_callee_save(arch_env, reg))
1268 pmap_insert(reg_map, ent->key, ent->value);
1271 be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1274 Maximum size of the in array for Return nodes is
1275 return args + callee save/ignore registers + memory + stack pointer
1277 in_max = pmap_count(reg_map) + n_res + 2;
1279 in = ALLOCAN(ir_node*, in_max);
1280 regs = ALLOCAN(arch_register_t const*, in_max);
1283 in[1] = be_abi_reg_map_get(reg_map, arch_env->sp);
1285 regs[1] = arch_env->sp;
1288 /* clear SP entry, since it has already been grown. */
1289 pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1290 for (i = 0; i < n_res; ++i) {
1291 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1293 in[n] = be_abi_reg_map_get(reg_map, arg->reg);
1294 regs[n++] = arg->reg;
1296 /* Clear the map entry to mark the register as processed. */
1297 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1300 /* grow the rest of the stuff. */
1301 foreach_pmap(reg_map, ent) {
1303 in[n] = (ir_node*)ent->value;
1304 regs[n++] = (const arch_register_t*)ent->key;
1308 /* The in array for the new back end return is now ready. */
1310 dbgi = get_irn_dbg_info(irn);
1314 /* we have to pop the shadow parameter in in case of struct returns */
1316 ret = be_new_Return(dbgi, irg, bl, n_res, pop, n, in);
1318 /* Set the register classes of the return's parameter accordingly. */
1319 for (i = 0; i < n; ++i) {
1320 if (regs[i] == NULL)
1323 be_set_constr_single_reg_in(ret, i, regs[i], arch_register_req_type_none);
1326 /* Free the space of the Epilog's in array and the register <-> proj map. */
1327 pmap_destroy(reg_map);
1332 typedef struct lower_frame_sels_env_t {
1333 ir_node *frame; /**< the current frame */
1334 const arch_register_class_t *sp_class; /**< register class of the stack pointer */
1335 const arch_register_class_t *link_class; /**< register class of the link pointer */
1336 ir_type *frame_tp; /**< the frame type */
1337 int static_link_pos; /**< argument number of the hidden static link */
1338 } lower_frame_sels_env_t;
1341 * Walker: Replaces Sels of frame type and
1342 * value param type entities by FrameAddress.
1343 * Links all used entities.
1345 static void lower_frame_sels_walker(ir_node *irn, void *data)
1347 lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1350 ir_node *ptr = get_Sel_ptr(irn);
1352 if (ptr == ctx->frame) {
1353 ir_entity *ent = get_Sel_entity(irn);
1354 ir_node *bl = get_nodes_block(irn);
1357 nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1364 * The start block has no jump, instead it has an initial exec Proj.
1365 * The backend wants to handle all blocks the same way, so we replace
1366 * the out cfg edge with a real jump.
1368 static void fix_start_block(ir_graph *irg)
1370 ir_node *initial_X = get_irg_initial_exec(irg);
1371 ir_node *start_block = get_irg_start_block(irg);
1372 ir_node *jmp = new_r_Jmp(start_block);
1374 assert(is_Proj(initial_X));
1375 exchange(initial_X, jmp);
1376 set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1378 /* merge start block with successor if possible */
1380 const ir_edge_t *edge;
1381 foreach_out_edge(jmp, edge) {
1382 ir_node *succ = get_edge_src_irn(edge);
1383 if (!is_Block(succ))
1386 if (get_irn_arity(succ) == 1) {
1387 exchange(succ, start_block);
1395 * Modify the irg itself and the frame type.
1397 static void modify_irg(ir_graph *irg)
1399 be_abi_irg_t *env = be_get_irg_abi(irg);
1400 be_abi_call_t *call = env->call;
1401 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1402 const arch_register_t *sp = arch_env->sp;
1403 ir_type *method_type = get_entity_type(get_irg_entity(irg));
1404 be_irg_t *birg = be_birg_from_irg(irg);
1405 struct obstack *obst = be_get_be_obst(irg);
1406 be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
1409 ir_node *new_mem_proj;
1415 unsigned frame_size;
1418 const arch_register_t *fp_reg;
1419 ir_node *frame_pointer;
1423 const ir_edge_t *edge;
1424 ir_type *arg_type, *bet_type;
1425 lower_frame_sels_env_t ctx;
1427 DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1429 old_mem = get_irg_initial_mem(irg);
1431 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1433 arg_type = compute_arg_type(irg, call, method_type);
1435 /* Convert the Sel nodes in the irg to frame addr nodes: */
1436 ctx.frame = get_irg_frame(irg);
1437 ctx.sp_class = arch_env->sp->reg_class;
1438 ctx.link_class = arch_env->link_class;
1439 ctx.frame_tp = get_irg_frame_type(irg);
1441 /* layout the stackframe now */
1442 if (get_type_state(ctx.frame_tp) == layout_undefined) {
1443 default_layout_compound_type(ctx.frame_tp);
1446 /* align stackframe to 4 byte */
1447 frame_size = get_type_size_bytes(ctx.frame_tp);
1448 if (frame_size % 4 != 0) {
1449 set_type_size_bytes(ctx.frame_tp, frame_size + 4 - (frame_size % 4));
1452 env->regs = pmap_create();
1454 n_params = get_method_n_params(method_type);
1455 args = OALLOCNZ(obst, ir_node*, n_params);
1457 be_add_parameter_entity_stores(irg);
1459 irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1461 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1463 /* Fill the argument vector */
1464 arg_tuple = get_irg_args(irg);
1465 foreach_out_edge(arg_tuple, edge) {
1466 ir_node *irn = get_edge_src_irn(edge);
1467 if (! is_Anchor(irn)) {
1468 int nr = get_Proj_proj(irn);
1470 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1474 stack_layout->sp_relative = call->flags.bits.try_omit_fp;
1475 bet_type = call->cb->get_between_type(irg);
1476 stack_frame_init(stack_layout, arg_type, bet_type,
1477 get_irg_frame_type(irg));
1479 /* Count the register params and add them to the number of Projs for the RegParams node */
1480 for (i = 0; i < n_params; ++i) {
1481 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1482 if (arg->in_reg && args[i]) {
1483 assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1484 assert(i == get_Proj_proj(args[i]));
1486 /* For now, associate the register with the old Proj from Start representing that argument. */
1487 pmap_insert(env->regs, (void *) arg->reg, args[i]);
1488 DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1492 /* Collect all callee-save registers */
1493 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1494 const arch_register_class_t *cls = &arch_env->register_classes[i];
1495 for (j = 0; j < cls->n_regs; ++j) {
1496 const arch_register_t *reg = &cls->regs[j];
1497 if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1498 pmap_insert(env->regs, (void *) reg, NULL);
1503 fp_reg = call->flags.bits.try_omit_fp ? arch_env->sp : arch_env->bp;
1504 rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1506 /* handle start block here (place a jump in the block) */
1507 fix_start_block(irg);
1509 pmap_insert(env->regs, (void *) sp, NULL);
1510 pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1511 start_bl = get_irg_start_block(irg);
1512 env->start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1513 set_irg_start(irg, env->start);
1516 * make proj nodes for the callee save registers.
1517 * memorize them, since Return nodes get those as inputs.
1519 * Note, that if a register corresponds to an argument, the regs map
1520 * contains the old Proj from start for that argument.
1522 rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1523 reg_map_to_arr(rm, env->regs);
1524 for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1525 const arch_register_t *reg = rm[i].reg;
1526 ir_mode *mode = reg->reg_class->mode;
1528 arch_register_req_type_t add_type = arch_register_req_type_none;
1532 add_type |= arch_register_req_type_produces_sp;
1533 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1534 add_type |= arch_register_req_type_ignore;
1538 proj = new_r_Proj(env->start, mode, nr + 1);
1539 pmap_insert(env->regs, (void *) reg, proj);
1540 be_set_constr_single_reg_out(env->start, nr + 1, reg, add_type);
1541 arch_set_irn_register(proj, reg);
1543 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1546 /* create a new initial memory proj */
1547 assert(is_Proj(old_mem));
1548 arch_set_irn_register_req_out(env->start, 0, arch_no_register_req);
1549 new_mem_proj = new_r_Proj(env->start, mode_M, 0);
1551 set_irg_initial_mem(irg, mem);
1553 env->init_sp = be_abi_reg_map_get(env->regs, sp);
1555 /* set new frame_pointer */
1556 frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1557 set_irg_frame(irg, frame_pointer);
1559 /* rewire old mem users to new mem */
1560 exchange(old_mem, mem);
1562 /* keep the mem (for functions with an endless loop = no return) */
1565 set_irg_initial_mem(irg, mem);
1567 /* Now, introduce stack param nodes for all parameters passed on the stack */
1568 for (i = 0; i < n_params; ++i) {
1569 ir_node *arg_proj = args[i];
1570 ir_node *repl = NULL;
1572 if (arg_proj != NULL) {
1573 be_abi_call_arg_t *arg;
1574 ir_type *param_type;
1575 int nr = get_Proj_proj(arg_proj);
1578 nr = MIN(nr, n_params);
1579 arg = get_call_arg(call, 0, nr, 1);
1580 param_type = get_method_param_type(method_type, nr);
1583 repl = pmap_get(ir_node, env->regs, arg->reg);
1584 } else if (arg->on_stack) {
1585 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1587 /* For atomic parameters which are actually used, we create a Load node. */
1588 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1589 ir_mode *mode = get_type_mode(param_type);
1590 ir_mode *load_mode = arg->load_mode;
1591 ir_node *nomem = get_irg_no_mem(irg);
1593 ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1594 repl = new_r_Proj(load, load_mode, pn_Load_res);
1596 if (mode != load_mode) {
1597 repl = new_r_Conv(start_bl, repl, mode);
1600 /* The stack parameter is not primitive (it is a struct or array),
1601 * we thus will create a node representing the parameter's address
1607 assert(repl != NULL);
1609 /* Beware: the mode of the register parameters is always the mode of the register class
1610 which may be wrong. Add Conv's then. */
1611 mode = get_irn_mode(args[i]);
1612 if (mode != get_irn_mode(repl)) {
1613 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1615 exchange(args[i], repl);
1619 /* the arg proj is not needed anymore now and should be only used by the anchor */
1620 assert(get_irn_n_edges(arg_tuple) == 1);
1621 kill_node(arg_tuple);
1622 set_irg_args(irg, new_r_Bad(irg, mode_T));
1624 /* All Return nodes hang on the End node, so look for them there. */
1625 end = get_irg_end_block(irg);
1626 for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1627 ir_node *irn = get_Block_cfgpred(end, i);
1629 if (is_Return(irn)) {
1630 ir_node *blk = get_nodes_block(irn);
1631 ir_node *mem = get_Return_mem(irn);
1632 ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1637 /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1638 the code is dead and will never be executed. */
1641 /** Fix the state inputs of calls that still hang on unknowns */
1642 static void fix_call_state_inputs(ir_graph *irg)
1644 be_abi_irg_t *env = be_get_irg_abi(irg);
1645 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1647 arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1649 /* Collect caller save registers */
1650 n = arch_env->n_register_classes;
1651 for (i = 0; i < n; ++i) {
1653 const arch_register_class_t *cls = &arch_env->register_classes[i];
1654 for (j = 0; j < cls->n_regs; ++j) {
1655 const arch_register_t *reg = arch_register_for_index(cls, j);
1656 if (reg->type & arch_register_type_state) {
1657 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1662 n = ARR_LEN(env->calls);
1663 n_states = ARR_LEN(stateregs);
1664 for (i = 0; i < n; ++i) {
1666 ir_node *call = env->calls[i];
1668 arity = get_irn_arity(call);
1670 /* the state reg inputs are the last n inputs of the calls */
1671 for (s = 0; s < n_states; ++s) {
1672 int inp = arity - n_states + s;
1673 const arch_register_t *reg = stateregs[s];
1674 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1676 set_irn_n(call, inp, regnode);
1680 DEL_ARR_F(stateregs);
1684 * Create a trampoline entity for the given method.
1686 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1688 ir_type *type = get_entity_type(method);
1689 ident *old_id = get_entity_ld_ident(method);
1690 ident *id = id_mangle3("", old_id, "$stub");
1691 ir_type *parent = be->pic_trampolines_type;
1692 ir_entity *ent = new_entity(parent, old_id, type);
1693 set_entity_ld_ident(ent, id);
1694 set_entity_visibility(ent, ir_visibility_private);
1700 * Returns the trampoline entity for the given method.
1702 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1704 ir_entity *result = pmap_get(ir_entity, env->ent_trampoline_map, method);
1705 if (result == NULL) {
1706 result = create_trampoline(env, method);
1707 pmap_insert(env->ent_trampoline_map, method, result);
1713 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1715 ident *old_id = get_entity_ld_ident(entity);
1716 ident *id = id_mangle3("", old_id, "$non_lazy_ptr");
1717 ir_type *e_type = get_entity_type(entity);
1718 ir_type *type = new_type_pointer(e_type);
1719 ir_type *parent = be->pic_symbols_type;
1720 ir_entity *ent = new_entity(parent, old_id, type);
1721 set_entity_ld_ident(ent, id);
1722 set_entity_visibility(ent, ir_visibility_private);
1727 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1729 ir_entity *result = pmap_get(ir_entity, env->ent_pic_symbol_map, entity);
1730 if (result == NULL) {
1731 result = create_pic_symbol(env, entity);
1732 pmap_insert(env->ent_pic_symbol_map, entity, result);
1741 * Returns non-zero if a given entity can be accessed using a relative address.
1743 static int can_address_relative(ir_entity *entity)
1745 return entity_has_definition(entity) && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1748 static ir_node *get_pic_base(ir_graph *irg)
1750 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1751 if (arch_env->impl->get_pic_base == NULL)
1753 return arch_env->impl->get_pic_base(irg);
1756 /** patches SymConsts to work in position independent code */
1757 static void fix_pic_symconsts(ir_node *node, void *data)
1759 ir_graph *irg = get_irn_irg(node);
1760 be_main_env_t *be = be_get_irg_main_env(irg);
1770 arity = get_irn_arity(node);
1771 for (i = 0; i < arity; ++i) {
1773 ir_node *pred = get_irn_n(node, i);
1775 ir_entity *pic_symbol;
1776 ir_node *pic_symconst;
1778 if (!is_SymConst(pred))
1781 entity = get_SymConst_entity(pred);
1782 block = get_nodes_block(pred);
1784 /* calls can jump to relative addresses, so we can directly jump to
1785 the (relatively) known call address or the trampoline */
1786 if (i == 1 && is_Call(node)) {
1787 ir_entity *trampoline;
1788 ir_node *trampoline_const;
1790 if (can_address_relative(entity))
1793 dbgi = get_irn_dbg_info(pred);
1794 trampoline = get_trampoline(be, entity);
1795 trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1797 set_irn_n(node, i, trampoline_const);
1801 /* everything else is accessed relative to EIP */
1802 mode = get_irn_mode(pred);
1803 pic_base = get_pic_base(irg);
1805 /* all ok now for locally constructed stuff */
1806 if (can_address_relative(entity)) {
1807 ir_node *add = new_r_Add(block, pic_base, pred, mode);
1809 /* make sure the walker doesn't visit this add again */
1810 mark_irn_visited(add);
1811 set_irn_n(node, i, add);
1815 /* get entry from pic symbol segment */
1816 dbgi = get_irn_dbg_info(pred);
1817 pic_symbol = get_pic_symbol(be, entity);
1818 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1820 add = new_r_Add(block, pic_base, pic_symconst, mode);
1821 mark_irn_visited(add);
1823 /* we need an extra indirection for global data outside our current
1824 module. The loads are always safe and can therefore float
1825 and need no memory input */
1826 load = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1827 load_res = new_r_Proj(load, mode, pn_Load_res);
1829 set_irn_n(node, i, load_res);
1833 void be_abi_introduce(ir_graph *irg)
1835 be_abi_irg_t *env = XMALLOCZ(be_abi_irg_t);
1836 ir_node *old_frame = get_irg_frame(irg);
1837 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1838 ir_entity *entity = get_irg_entity(irg);
1839 ir_type *method_type = get_entity_type(entity);
1840 be_irg_t *birg = be_birg_from_irg(irg);
1841 struct obstack *obst = &birg->obst;
1842 ir_node *dummy = new_r_Dummy(irg,
1843 arch_env->sp->reg_class->mode);
1846 /* determine allocatable registers */
1847 assert(birg->allocatable_regs == NULL);
1848 birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1849 for (r = 0; r < arch_env->n_registers; ++r) {
1850 const arch_register_t *reg = &arch_env->registers[r];
1851 if ( !(reg->type & arch_register_type_ignore)) {
1852 rbitset_set(birg->allocatable_regs, r);
1856 /* break here if backend provides a custom API.
1857 * Note: we shouldn't have to setup any be_abi_irg_t* stuff at all,
1858 * but need more cleanup to make this work
1860 be_set_irg_abi(irg, env);
1862 be_omit_fp = be_options.omit_fp;
1864 env->keep_map = pmap_create();
1865 env->call = be_abi_call_new(arch_env->sp->reg_class);
1866 arch_env_get_call_abi(arch_env, method_type, env->call);
1868 env->init_sp = dummy;
1869 env->calls = NEW_ARR_F(ir_node*, 0);
1873 if (be_options.pic) {
1874 irg_walk_graph(irg, fix_pic_symconsts, NULL, env);
1877 /* Lower all call nodes in the IRG. */
1880 /* Process the IRG */
1883 /* fix call inputs for state registers */
1884 fix_call_state_inputs(irg);
1886 /* We don't need the keep map anymore. */
1887 pmap_destroy(env->keep_map);
1888 env->keep_map = NULL;
1890 /* calls array is not needed anymore */
1891 DEL_ARR_F(env->calls);
1894 /* reroute the stack origin of the calls to the true stack origin. */
1895 exchange(dummy, env->init_sp);
1896 exchange(old_frame, get_irg_frame(irg));
1898 pmap_destroy(env->regs);
1902 void be_abi_free(ir_graph *irg)
1904 be_abi_irg_t *env = be_get_irg_abi(irg);
1906 if (env->call != NULL)
1907 be_abi_call_free(env->call);
1908 assert(env->regs == NULL);
1911 be_set_irg_abi(irg, NULL);
1914 void be_put_allocatable_regs(const ir_graph *irg,
1915 const arch_register_class_t *cls, bitset_t *bs)
1917 be_irg_t *birg = be_birg_from_irg(irg);
1918 unsigned *allocatable_regs = birg->allocatable_regs;
1921 assert(bitset_size(bs) == cls->n_regs);
1922 bitset_clear_all(bs);
1923 for (i = 0; i < cls->n_regs; ++i) {
1924 const arch_register_t *reg = &cls->regs[i];
1925 if (rbitset_is_set(allocatable_regs, reg->global_index))
1930 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1931 const arch_register_class_t *cls)
1933 bitset_t *bs = bitset_alloca(cls->n_regs);
1934 be_put_allocatable_regs(irg, cls, bs);
1935 return bitset_popcount(bs);
1938 void be_set_allocatable_regs(const ir_graph *irg,
1939 const arch_register_class_t *cls,
1940 unsigned *raw_bitset)
1942 be_irg_t *birg = be_birg_from_irg(irg);
1943 unsigned *allocatable_regs = birg->allocatable_regs;
1946 rbitset_clear_all(raw_bitset, cls->n_regs);
1947 for (i = 0; i < cls->n_regs; ++i) {
1948 const arch_register_t *reg = &cls->regs[i];
1949 if (rbitset_is_set(allocatable_regs, reg->global_index))
1950 rbitset_set(raw_bitset, i);
1954 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
1955 void be_init_abi(void)
1957 FIRM_DBG_REGISTER(dbg, "firm.be.abi");