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;
79 ir_type *between_type;
81 const arch_register_class_t *cls_addr; /**< register class of the call address */
85 * The ABI information for the current graph.
88 be_abi_call_t *call; /**< The ABI call information. */
90 ir_node *init_sp; /**< The node representing the stack pointer
91 at the start of the function. */
93 pmap *regs; /**< A map of all callee-save and ignore regs to
94 their Projs to the RegParams node. */
95 pmap *keep_map; /**< mapping blocks to keep nodes. */
97 ir_node **calls; /**< flexible array containing all be_Call nodes */
100 static ir_heights_t *ir_heights;
102 /** Flag: if set, try to omit the frame pointer in all routines. */
103 static int be_omit_fp = 1;
105 static ir_node *be_abi_reg_map_get(pmap *map, const arch_register_t *reg)
107 return pmap_get(ir_node, map, reg);
110 static void be_abi_reg_map_set(pmap *map, const arch_register_t* reg,
113 pmap_insert(map, reg, node);
117 * Check if the given register is callee save, ie. will be saved by the callee.
119 static bool arch_register_is_callee_save(
120 const arch_env_t *arch_env,
121 const arch_register_t *reg)
123 if (arch_env->impl->register_saved_by)
124 return arch_env->impl->register_saved_by(reg, /*callee=*/1);
129 * Check if the given register is caller save, ie. must be saved by the caller.
131 static bool arch_register_is_caller_save(
132 const arch_env_t *arch_env,
133 const arch_register_t *reg)
135 if (arch_env->impl->register_saved_by)
136 return arch_env->impl->register_saved_by(reg, /*callee=*/0);
143 _ ____ ___ ____ _ _ _ _
144 / \ | __ )_ _| / ___|__ _| | | |__ __ _ ___| | _____
145 / _ \ | _ \| | | | / _` | | | '_ \ / _` |/ __| |/ / __|
146 / ___ \| |_) | | | |__| (_| | | | |_) | (_| | (__| <\__ \
147 /_/ \_\____/___| \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
149 These callbacks are used by the backend to set the parameters
150 for a specific call type.
154 * Set compare function: compares two ABI call object arguments.
156 static int cmp_call_arg(const void *a, const void *b, size_t n)
158 const be_abi_call_arg_t *p = (const be_abi_call_arg_t*)a;
159 const be_abi_call_arg_t *q = (const be_abi_call_arg_t*)b;
161 return !(p->is_res == q->is_res && p->pos == q->pos && p->callee == q->callee);
165 * Get an ABI call object argument.
167 * @param call the abi call
168 * @param is_res true for call results, false for call arguments
169 * @param pos position of the argument
170 * @param callee context type - if we are callee or caller
172 static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos, int callee)
174 be_abi_call_arg_t arg;
177 memset(&arg, 0, sizeof(arg));
182 hash = is_res * 128 + pos;
184 return set_find(be_abi_call_arg_t, call->params, &arg, sizeof(arg), hash);
188 * Set an ABI call object argument.
190 static void remember_call_arg(be_abi_call_arg_t *arg, be_abi_call_t *call, be_abi_context_t context)
192 unsigned hash = arg->is_res * 128 + arg->pos;
193 if (context & ABI_CONTEXT_CALLEE) {
195 (void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
197 if (context & ABI_CONTEXT_CALLER) {
199 (void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
203 /* Set the flags for a call. */
204 void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
210 /* Sets the number of bytes the stackframe is shrinked by the callee on return */
211 void be_abi_call_set_pop(be_abi_call_t *call, int pop)
217 /* Set register class for call address */
218 void be_abi_call_set_call_address_reg_class(be_abi_call_t *call, const arch_register_class_t *cls)
220 call->cls_addr = cls;
224 void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos,
225 ir_mode *load_mode, unsigned alignment,
226 unsigned space_before, unsigned space_after,
227 be_abi_context_t context)
229 be_abi_call_arg_t arg;
230 memset(&arg, 0, sizeof(arg));
231 assert(alignment > 0 && "Alignment must be greater than 0");
232 arg.load_mode = load_mode;
233 arg.alignment = alignment;
234 arg.space_before = space_before;
235 arg.space_after = space_after;
239 remember_call_arg(&arg, call, context);
242 void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
244 be_abi_call_arg_t arg;
245 memset(&arg, 0, sizeof(arg));
252 remember_call_arg(&arg, call, context);
255 void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
257 be_abi_call_arg_t arg;
258 memset(&arg, 0, sizeof(arg));
265 remember_call_arg(&arg, call, context);
268 /* Get the flags of a ABI call object. */
269 be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
275 * Constructor for a new ABI call object.
277 * @param cls_addr register class of the call address
279 * @return the new ABI call object
281 static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
283 be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
285 call->params = new_set(cmp_call_arg, 16);
287 call->cls_addr = cls_addr;
288 call->flags.try_omit_fp = be_omit_fp;
294 * Destructor for an ABI call object.
296 static void be_abi_call_free(be_abi_call_t *call)
298 del_set(call->params);
303 * Initializes the frame layout from parts
305 * @param frame the stack layout that will be initialized
306 * @param args the stack argument layout type
307 * @param between the between layout type
308 * @param locals the method frame type
310 * @return the initialized stack layout
312 static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
313 ir_type *between, ir_type *locals)
315 frame->arg_type = args;
316 frame->between_type = between;
317 frame->frame_type = locals;
318 frame->initial_offset = 0;
319 frame->initial_bias = 0;
320 frame->order[1] = between;
322 /* typical decreasing stack: locals have the
323 * lowest addresses, arguments the highest */
324 frame->order[0] = locals;
325 frame->order[2] = args;
336 Adjustment of the calls inside a graph.
341 * Transform a call node into a be_Call node.
343 * @param env The ABI environment for the current irg.
344 * @param irn The call node.
345 * @param curr_sp The stack pointer node to use.
346 * @return The stack pointer after the call.
348 static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
350 ir_graph *irg = get_irn_irg(irn);
351 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
352 ir_type *call_tp = get_Call_type(irn);
353 ir_node *call_ptr = get_Call_ptr(irn);
354 size_t n_params = get_method_n_params(call_tp);
355 ir_node *curr_mem = get_Call_mem(irn);
356 ir_node *bl = get_nodes_block(irn);
358 const arch_register_t *sp = arch_env->sp;
359 be_abi_call_t *call = be_abi_call_new(sp->reg_class);
360 ir_mode *mach_mode = sp->reg_class->mode;
361 int n_res = get_method_n_ress(call_tp);
363 ir_node *res_proj = NULL;
364 int n_reg_params = 0;
365 int n_stack_params = 0;
368 const arch_register_t **states = NEW_ARR_F(const arch_register_t*, 0);
369 const arch_register_t **destroyed_regs = NEW_ARR_F(const arch_register_t*, 0);
373 int n_reg_results = 0;
375 int *stack_param_idx;
377 int throws_exception;
382 /* Let the isa fill out the abi description for that call node. */
383 arch_env_get_call_abi(arch_env, call_tp, call);
385 /* Insert code to put the stack arguments on the stack. */
386 assert((size_t)get_Call_n_params(irn) == n_params);
387 stack_param_idx = ALLOCAN(int, n_params);
388 for (p = 0; p < n_params; ++p) {
389 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
392 int arg_size = get_type_size_bytes(get_method_param_type(call_tp, p));
394 stack_size += round_up2(arg->space_before, arg->alignment);
395 stack_size += round_up2(arg_size, arg->alignment);
396 stack_size += round_up2(arg->space_after, arg->alignment);
398 stack_param_idx[n_stack_params++] = p;
402 /* Collect all arguments which are passed in registers. */
403 reg_param_idxs = ALLOCAN(int, n_params);
404 for (p = 0; p < n_params; ++p) {
405 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
406 if (arg && arg->in_reg) {
407 reg_param_idxs[n_reg_params++] = p;
412 * If the stack is decreasing and we do not want to store sequentially,
413 * or someone else allocated the call frame
414 * we allocate as much space on the stack all parameters need, by
415 * moving the stack pointer along the stack's direction.
417 * Note: we also have to do this for stack_size == 0, because we may have
418 * to adjust stack alignment for the call.
420 curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
422 dbgi = get_irn_dbg_info(irn);
423 /* If there are some parameters which shall be passed on the stack. */
424 if (n_stack_params > 0) {
426 ir_node **in = ALLOCAN(ir_node*, n_stack_params+1);
429 curr_mem = get_Call_mem(irn);
430 in[n_in++] = curr_mem;
432 for (i = 0; i < n_stack_params; ++i) {
433 int p = stack_param_idx[i];
434 be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
435 ir_node *param = get_Call_param(irn, p);
436 ir_node *addr = curr_sp;
438 ir_type *param_type = get_method_param_type(call_tp, p);
439 int param_size = get_type_size_bytes(param_type) + arg->space_after;
442 * If we wanted to build the arguments sequentially,
443 * the stack pointer for the next must be incremented,
444 * and the memory value propagated.
446 curr_ofs += arg->space_before;
447 curr_ofs = round_up2(curr_ofs, arg->alignment);
449 /* Make the expression to compute the argument's offset. */
451 ir_mode *constmode = mach_mode;
452 if (mode_is_reference(mach_mode)) {
455 addr = new_r_Const_long(irg, constmode, curr_ofs);
456 addr = new_r_Add(bl, curr_sp, addr, mach_mode);
459 /* Insert a store for primitive arguments. */
460 if (is_atomic_type(param_type)) {
461 ir_node *nomem = get_irg_no_mem(irg);
462 ir_node *mem_input = nomem;
463 ir_node *store = new_rd_Store(dbgi, bl, mem_input, addr, param, cons_none);
464 mem = new_r_Proj(store, mode_M, pn_Store_M);
466 /* Make a mem copy for compound arguments. */
469 assert(mode_is_reference(get_irn_mode(param)));
470 copy = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type);
471 mem = new_r_Proj(copy, mode_M, pn_CopyB_M);
474 curr_ofs += param_size;
479 /* We need the sync only, if we didn't build the stores sequentially. */
480 if (n_stack_params >= 1) {
481 curr_mem = new_r_Sync(bl, n_in, in);
483 curr_mem = get_Call_mem(irn);
487 /* Put caller save into the destroyed set and state registers in the states
489 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
491 const arch_register_class_t *cls = &arch_env->register_classes[i];
492 for (j = 0; j < cls->n_regs; ++j) {
493 const arch_register_t *reg = arch_register_for_index(cls, j);
495 /* even if destroyed all is specified, neither SP nor FP are
496 * destroyed (else bad things will happen) */
497 if (reg == arch_env->sp || reg == arch_env->bp)
500 if (reg->type & arch_register_type_state) {
501 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
502 ARR_APP1(const arch_register_t*, states, reg);
503 /* we're already in the destroyed set so no need for further
507 if (arch_register_is_caller_save(arch_env, reg)) {
508 if (!(reg->type & arch_register_type_ignore)) {
509 ARR_APP1(const arch_register_t*, destroyed_regs, reg);
515 /* search the largest result proj number */
516 res_projs = ALLOCANZ(ir_node*, n_res);
518 foreach_out_edge(irn, edge) {
519 ir_node *irn = get_edge_src_irn(edge);
521 if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
524 foreach_out_edge(irn, res_edge) {
526 ir_node *res = get_edge_src_irn(res_edge);
528 assert(is_Proj(res));
530 proj = get_Proj_proj(res);
531 assert(proj < n_res);
532 assert(res_projs[proj] == NULL);
533 res_projs[proj] = res;
539 /** TODO: this is not correct for cases where return values are passed
540 * on the stack, but no known ABI does this currently...
542 n_reg_results = n_res;
545 in = ALLOCAN(ir_node*, n_reg_params + ARR_LEN(states));
547 /* make the back end call node and set its register requirements. */
548 for (i = 0; i < n_reg_params; ++i) {
549 in[n_ins++] = get_Call_param(irn, reg_param_idxs[i]);
552 /* add state registers ins */
553 for (s = 0; s < ARR_LEN(states); ++s) {
554 const arch_register_t *reg = states[s];
555 const arch_register_class_t *cls = reg->reg_class;
556 ir_node *regnode = new_r_Unknown(irg, cls->mode);
557 in[n_ins++] = regnode;
559 assert(n_ins == (int) (n_reg_params + ARR_LEN(states)));
561 /* ins collected, build the call */
562 throws_exception = ir_throws_exception(irn);
563 if (env->call->flags.call_has_imm && is_SymConst(call_ptr)) {
565 low_call = be_new_Call(dbgi, irg, bl, curr_mem, sp->single_req, curr_sp,
566 sp->single_req, curr_sp,
567 n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
568 n_ins, in, get_Call_type(irn));
569 be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
572 low_call = be_new_Call(dbgi, irg, bl, curr_mem, sp->single_req, curr_sp,
573 call->cls_addr->class_req, call_ptr,
574 n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
575 n_ins, in, get_Call_type(irn));
577 ir_set_throws_exception(low_call, throws_exception);
578 be_Call_set_pop(low_call, call->pop);
580 /* put the call into the list of all calls for later processing */
581 ARR_APP1(ir_node *, env->calls, low_call);
583 /* create new stack pointer */
584 curr_sp = new_r_Proj(low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
585 be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
586 arch_register_req_type_ignore | arch_register_req_type_produces_sp);
587 arch_set_irn_register(curr_sp, sp);
589 /* now handle results */
590 for (i = 0; i < n_res; ++i) {
591 ir_node *proj = res_projs[i];
592 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 0);
594 /* returns values on stack not supported yet */
598 shift the proj number to the right, since we will drop the
599 unspeakable Proj_T from the Call. Therefore, all real argument
600 Proj numbers must be increased by pn_be_Call_first_res
602 long pn = i + pn_be_Call_first_res;
605 ir_type *res_type = get_method_res_type(call_tp, i);
606 ir_mode *mode = get_type_mode(res_type);
607 proj = new_r_Proj(low_call, mode, pn);
610 set_Proj_pred(proj, low_call);
611 set_Proj_proj(proj, pn);
615 /* remove register from destroyed regs */
617 size_t n = ARR_LEN(destroyed_regs);
618 for (j = 0; j < n; ++j) {
619 if (destroyed_regs[j] == arg->reg) {
620 destroyed_regs[j] = destroyed_regs[n-1];
621 ARR_SHRINKLEN(destroyed_regs,n-1);
628 DBG((dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));
630 /* Set the register classes and constraints of the Call parameters. */
631 for (i = 0; i < n_reg_params; ++i) {
632 int index = reg_param_idxs[i];
633 be_abi_call_arg_t *arg = get_call_arg(call, 0, index, 0);
634 assert(arg->reg != NULL);
636 be_set_constr_single_reg_in(low_call, n_be_Call_first_arg + i,
637 arg->reg, arch_register_req_type_none);
640 /* Set the register constraints of the results. */
641 for (i = 0; i < n_res; ++i) {
642 ir_node *proj = res_projs[i];
643 const be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 0);
644 int pn = get_Proj_proj(proj);
647 be_set_constr_single_reg_out(low_call, pn, arg->reg,
648 arch_register_req_type_none);
649 arch_set_irn_register(proj, arg->reg);
651 exchange(irn, low_call);
653 /* kill the ProjT node */
654 if (res_proj != NULL) {
658 /* Make additional projs for the caller save registers
659 and the Keep node which keeps them alive. */
665 int curr_res_proj = pn_be_Call_first_res + n_reg_results;
668 n_ins = ARR_LEN(destroyed_regs) + n_reg_results + 1;
669 in = ALLOCAN(ir_node *, n_ins);
671 /* also keep the stack pointer */
672 set_irn_link(curr_sp, (void*) sp);
675 for (d = 0; d < ARR_LEN(destroyed_regs); ++d) {
676 const arch_register_t *reg = destroyed_regs[d];
677 ir_node *proj = new_r_Proj(low_call, reg->reg_class->mode, curr_res_proj);
679 /* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
680 be_set_constr_single_reg_out(low_call, curr_res_proj, reg,
681 arch_register_req_type_none);
682 arch_set_irn_register(proj, reg);
684 set_irn_link(proj, (void*) reg);
689 for (i = 0; i < n_reg_results; ++i) {
690 ir_node *proj = res_projs[i];
691 const arch_register_t *reg = arch_get_irn_register(proj);
692 set_irn_link(proj, (void*) reg);
697 /* create the Keep for the caller save registers */
698 keep = be_new_Keep(bl, n, in);
699 for (i = 0; i < n; ++i) {
700 const arch_register_t *reg = (const arch_register_t*)get_irn_link(in[i]);
701 be_node_set_reg_class_in(keep, i, reg->reg_class);
705 /* Clean up the stack. */
706 assert(stack_size >= call->pop);
707 stack_size -= call->pop;
709 if (stack_size > 0) {
710 ir_node *mem_proj = NULL;
712 foreach_out_edge(low_call, edge) {
713 ir_node *irn = get_edge_src_irn(edge);
714 if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
721 mem_proj = new_r_Proj(low_call, mode_M, pn_be_Call_M);
722 keep_alive(mem_proj);
725 /* Clean up the stack frame or revert alignment fixes if we allocated it */
726 curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
728 be_abi_call_free(call);
731 DEL_ARR_F(destroyed_regs);
737 * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
739 * @param alignment the minimum stack alignment
740 * @param size the node containing the non-aligned size
741 * @param block the block where new nodes are allocated on
742 * @param dbg debug info for new nodes
744 * @return a node representing the aligned size
746 static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
747 ir_node *block, dbg_info *dbg)
749 if (stack_alignment > 1) {
755 assert(is_po2(stack_alignment));
757 mode = get_irn_mode(size);
758 tv = new_tarval_from_long(stack_alignment-1, mode);
759 irg = get_Block_irg(block);
760 mask = new_r_Const(irg, tv);
761 size = new_rd_Add(dbg, block, size, mask, mode);
763 tv = new_tarval_from_long(-(long)stack_alignment, mode);
764 mask = new_r_Const(irg, tv);
765 size = new_rd_And(dbg, block, size, mask, mode);
771 * The alloca is transformed into a back end alloca node and connected to the stack nodes.
773 static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
775 ir_node *block = get_nodes_block(alloc);
776 ir_graph *irg = get_Block_irg(block);
777 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
778 ir_node *alloc_mem = NULL;
779 ir_node *alloc_res = NULL;
780 ir_type *type = get_Alloc_type(alloc);
787 unsigned stack_alignment;
789 /* all non-stack Alloc nodes should already be lowered before the backend */
790 assert(get_Alloc_where(alloc) == stack_alloc);
792 foreach_out_edge(alloc, edge) {
793 ir_node *irn = get_edge_src_irn(edge);
795 assert(is_Proj(irn));
796 switch (get_Proj_proj(irn)) {
808 /* Beware: currently Alloc nodes without a result might happen,
809 only escape analysis kills them and this phase runs only for object
810 oriented source. We kill the Alloc here. */
811 if (alloc_res == NULL && alloc_mem) {
812 exchange(alloc_mem, get_Alloc_mem(alloc));
816 dbg = get_irn_dbg_info(alloc);
817 count = get_Alloc_count(alloc);
819 /* we might need to multiply the count with the element size */
820 if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
821 ir_mode *mode = get_irn_mode(count);
822 ir_tarval *tv = new_tarval_from_long(get_type_size_bytes(type),
824 ir_node *cnst = new_rd_Const(dbg, irg, tv);
825 size = new_rd_Mul(dbg, block, count, cnst, mode);
830 /* The stack pointer will be modified in an unknown manner.
831 We cannot omit it. */
832 env->call->flags.try_omit_fp = 0;
834 stack_alignment = 1 << arch_env->stack_alignment;
835 size = adjust_alloc_size(stack_alignment, size, block, dbg);
836 new_alloc = be_new_AddSP(arch_env->sp, block, curr_sp, size);
837 set_irn_dbg_info(new_alloc, dbg);
839 if (alloc_mem != NULL) {
843 addsp_mem = new_r_Proj(new_alloc, mode_M, pn_be_AddSP_M);
845 /* We need to sync the output mem of the AddSP with the input mem
846 edge into the alloc node. */
847 ins[0] = get_Alloc_mem(alloc);
849 sync = new_r_Sync(block, 2, ins);
851 exchange(alloc_mem, sync);
854 exchange(alloc, new_alloc);
856 /* fix projnum of alloca res */
857 set_Proj_proj(alloc_res, pn_be_AddSP_res);
859 curr_sp = new_r_Proj(new_alloc, get_irn_mode(curr_sp), pn_be_AddSP_sp);
866 * The Free is transformed into a back end free node and connected to the stack nodes.
868 static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
870 ir_node *block = get_nodes_block(free);
871 ir_graph *irg = get_irn_irg(free);
872 ir_type *type = get_Free_type(free);
873 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
874 ir_mode *sp_mode = arch_env->sp->reg_class->mode;
875 dbg_info *dbg = get_irn_dbg_info(free);
876 ir_node *subsp, *mem, *res, *size, *sync;
878 unsigned stack_alignment;
880 /* all non-stack-alloc Free nodes should already be lowered before the
882 assert(get_Free_where(free) == stack_alloc);
884 /* we might need to multiply the size with the element size */
885 if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
886 ir_tarval *tv = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
887 ir_node *cnst = new_rd_Const(dbg, irg, tv);
888 ir_node *mul = new_rd_Mul(dbg, block, get_Free_count(free),
892 size = get_Free_count(free);
895 stack_alignment = 1 << arch_env->stack_alignment;
896 size = adjust_alloc_size(stack_alignment, size, block, dbg);
898 /* The stack pointer will be modified in an unknown manner.
899 We cannot omit it. */
900 env->call->flags.try_omit_fp = 0;
901 subsp = be_new_SubSP(arch_env->sp, block, curr_sp, size);
902 set_irn_dbg_info(subsp, dbg);
904 mem = new_r_Proj(subsp, mode_M, pn_be_SubSP_M);
905 res = new_r_Proj(subsp, sp_mode, pn_be_SubSP_sp);
907 /* we need to sync the memory */
908 in[0] = get_Free_mem(free);
910 sync = new_r_Sync(block, 2, in);
912 /* and make the AddSP dependent on the former memory */
913 add_irn_dep(subsp, get_Free_mem(free));
916 exchange(free, sync);
923 * Check if a node is somehow data dependent on another one.
924 * both nodes must be in the same basic block.
925 * @param n1 The first node.
926 * @param n2 The second node.
927 * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
929 static int dependent_on(ir_node *n1, ir_node *n2)
931 assert(get_nodes_block(n1) == get_nodes_block(n2));
933 return heights_reachable_in_block(ir_heights, n1, n2);
936 static int cmp_call_dependency(const void *c1, const void *c2)
938 ir_node *n1 = *(ir_node **) c1;
939 ir_node *n2 = *(ir_node **) c2;
943 Classical qsort() comparison function behavior:
944 0 if both elements are equal
945 1 if second is "smaller" that first
946 -1 if first is "smaller" that second
948 if (dependent_on(n1, n2))
951 if (dependent_on(n2, n1))
954 /* The nodes have no depth order, but we need a total order because qsort()
957 * Additionally, we need to respect transitive dependencies. Consider a
958 * Call a depending on Call b and an independent Call c.
959 * We MUST NOT order c > a and b > c. */
960 h1 = get_irn_height(ir_heights, n1);
961 h2 = get_irn_height(ir_heights, n2);
962 if (h1 < h2) return -1;
963 if (h1 > h2) return 1;
964 /* Same height, so use a random (but stable) order */
965 return get_irn_idx(n1) - get_irn_idx(n2);
969 * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
971 static void link_ops_in_block_walker(ir_node *irn, void *data)
973 be_abi_irg_t *env = (be_abi_irg_t*)data;
974 unsigned code = get_irn_opcode(irn);
976 if (code == iro_Call ||
977 (code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
978 (code == iro_Free && get_Free_where(irn) == stack_alloc)) {
979 ir_node *bl = get_nodes_block(irn);
980 void *save = get_irn_link(bl);
982 set_irn_link(irn, save);
983 set_irn_link(bl, irn);
986 if (code == iro_Builtin && get_Builtin_kind(irn) == ir_bk_return_address) {
987 ir_node *param = get_Builtin_param(irn, 0);
988 ir_tarval *tv = get_Const_tarval(param);
989 unsigned long value = get_tarval_long(tv);
990 /* use ebp, so the climbframe algo works... */
992 env->call->flags.try_omit_fp = 0;
999 * Process all Call/Alloc/Free nodes inside a basic block.
1000 * Note that the link field of the block must contain a linked list of all
1001 * nodes inside the Block. We first order this list according to data dependency
1002 * and that connect the nodes together.
1004 static void process_ops_in_block(ir_node *bl, void *data)
1006 be_abi_irg_t *env = (be_abi_irg_t*)data;
1007 ir_node *curr_sp = env->init_sp;
1014 for (irn = (ir_node*)get_irn_link(bl); irn != NULL;
1015 irn = (ir_node*)get_irn_link(irn)) {
1019 nodes = ALLOCAN(ir_node*, n_nodes);
1020 for (irn = (ir_node*)get_irn_link(bl), n = 0; irn != NULL;
1021 irn = (ir_node*)get_irn_link(irn), ++n) {
1025 /* If there were call nodes in the block. */
1030 /* order the call nodes according to data dependency */
1031 qsort(nodes, n_nodes, sizeof(nodes[0]), cmp_call_dependency);
1033 for (i = n_nodes - 1; i >= 0; --i) {
1034 ir_node *irn = nodes[i];
1036 DBG((dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
1037 switch (get_irn_opcode(irn)) {
1039 curr_sp = adjust_call(env, irn, curr_sp);
1042 if (get_Alloc_where(irn) == stack_alloc)
1043 curr_sp = adjust_alloc(env, irn, curr_sp);
1046 if (get_Free_where(irn) == stack_alloc)
1047 curr_sp = adjust_free(env, irn, curr_sp);
1050 panic("invalid call");
1054 /* Keep the last stack state in the block by tying it to Keep node,
1055 * the proj from calls is already kept */
1056 if (curr_sp != env->init_sp &&
1057 !(is_Proj(curr_sp) && be_is_Call(get_Proj_pred(curr_sp)))) {
1059 keep = be_new_Keep(bl, 1, nodes);
1060 pmap_insert(env->keep_map, bl, keep);
1064 set_irn_link(bl, curr_sp);
1068 * Adjust all call nodes in the graph to the ABI conventions.
1070 static void process_calls(ir_graph *const irg, be_abi_irg_t *const abi)
1072 irg_walk_graph(irg, firm_clear_link, link_ops_in_block_walker, abi);
1074 ir_heights = heights_new(irg);
1075 irg_block_walk_graph(irg, NULL, process_ops_in_block, abi);
1076 heights_free(ir_heights);
1080 * Computes the stack argument layout type.
1081 * Changes a possibly allocated value param type by moving
1082 * entities to the stack layout type.
1084 * @param call the current call ABI
1085 * @param method_type the method type
1087 * @return the stack argument layout type
1089 static ir_type *compute_arg_type(ir_graph *irg, be_abi_call_t *call,
1090 ir_type *method_type)
1092 struct obstack *obst = be_get_be_obst(irg);
1093 ir_type *frame_type = get_irg_frame_type(irg);
1094 size_t n_params = get_method_n_params(method_type);
1095 size_t n_frame_members = get_compound_n_members(frame_type);
1096 ir_entity *va_start_entity = NULL;
1102 ir_entity **map = OALLOCNZ(obst, ir_entity*, n_params);
1103 res = new_type_struct(new_id_from_chars("arg_type", 8));
1105 /* collect existing entities for value_param_types */
1106 for (f = n_frame_members; f > 0; ) {
1107 ir_entity *entity = get_compound_member(frame_type, --f);
1110 set_entity_link(entity, NULL);
1111 if (!is_parameter_entity(entity))
1113 num = get_entity_parameter_number(entity);
1114 if (num == IR_VA_START_PARAMETER_NUMBER) {
1115 /* move entity to new arg_type */
1116 set_entity_owner(entity, res);
1117 va_start_entity = entity;
1120 assert(num < n_params);
1121 if (map[num] != NULL)
1122 panic("multiple entities for parameter %u in %+F found", f, irg);
1124 if (num != n_params && get_call_arg(call, 0, num, 1)->in_reg) {
1125 /* don't move this entity */
1130 /* move entity to new arg_type */
1131 set_entity_owner(entity, res);
1134 for (i = 0; i < n_params; ++i) {
1135 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1136 ir_type *param_type = get_method_param_type(method_type, i);
1142 if (entity == NULL) {
1143 /* create a new entity */
1144 entity = new_parameter_entity(res, i, param_type);
1146 ofs += arg->space_before;
1147 ofs = round_up2(ofs, arg->alignment);
1148 set_entity_offset(entity, ofs);
1149 ofs += arg->space_after;
1150 ofs += get_type_size_bytes(param_type);
1151 arg->stack_ent = entity;
1153 if (va_start_entity != NULL) {
1154 set_entity_offset(va_start_entity, ofs);
1156 set_type_size_bytes(res, ofs);
1157 set_type_state(res, layout_fixed);
1163 const arch_register_t *reg;
1167 static int cmp_regs(const void *a, const void *b)
1169 const reg_node_map_t *p = (const reg_node_map_t*)a;
1170 const reg_node_map_t *q = (const reg_node_map_t*)b;
1172 if (p->reg->reg_class == q->reg->reg_class)
1173 return p->reg->index - q->reg->index;
1175 return p->reg->reg_class < q->reg->reg_class ? -1 : +1;
1178 static void reg_map_to_arr(reg_node_map_t *res, pmap *reg_map)
1181 size_t n = pmap_count(reg_map);
1184 foreach_pmap(reg_map, ent) {
1185 res[i].reg = (const arch_register_t*)ent->key;
1186 res[i].irn = (ir_node*)ent->value;
1190 qsort(res, n, sizeof(res[0]), cmp_regs);
1194 * Creates a be_Return for a Return node.
1196 * @param @env the abi environment
1197 * @param irn the Return node or NULL if there was none
1198 * @param bl the block where the be_Retun should be placed
1199 * @param mem the current memory
1200 * @param n_res number of return results
1202 static ir_node *create_be_return(be_abi_irg_t *env, ir_node *irn, ir_node *bl,
1203 ir_node *mem, int n_res)
1205 be_abi_call_t *call = env->call;
1206 ir_graph *irg = get_Block_irg(bl);
1207 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1209 pmap *reg_map = pmap_create();
1210 ir_node *keep = pmap_get(ir_node, env->keep_map, bl);
1217 const arch_register_t **regs;
1221 get the valid stack node in this block.
1222 If we had a call in that block there is a Keep constructed by process_calls()
1223 which points to the last stack modification in that block. we'll use
1224 it then. Else we use the stack from the start block and let
1225 the ssa construction fix the usage.
1227 stack = be_abi_reg_map_get(env->regs, arch_env->sp);
1229 stack = get_irn_n(keep, 0);
1231 remove_End_keepalive(get_irg_end(irg), keep);
1234 /* Insert results for Return into the register map. */
1235 for (i = 0; i < n_res; ++i) {
1236 ir_node *res = get_Return_res(irn, i);
1237 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1238 assert(arg->in_reg && "return value must be passed in register");
1239 pmap_insert(reg_map, (void *) arg->reg, res);
1242 /* Add uses of the callee save registers. */
1243 foreach_pmap(env->regs, ent) {
1244 const arch_register_t *reg = (const arch_register_t*)ent->key;
1245 if ((reg->type & arch_register_type_ignore) || arch_register_is_callee_save(arch_env, reg))
1246 pmap_insert(reg_map, ent->key, ent->value);
1249 be_abi_reg_map_set(reg_map, arch_env->sp, stack);
1252 Maximum size of the in array for Return nodes is
1253 return args + callee save/ignore registers + memory + stack pointer
1255 in_max = pmap_count(reg_map) + n_res + 2;
1257 in = ALLOCAN(ir_node*, in_max);
1258 regs = ALLOCAN(arch_register_t const*, in_max);
1261 in[1] = be_abi_reg_map_get(reg_map, arch_env->sp);
1263 regs[1] = arch_env->sp;
1266 /* clear SP entry, since it has already been grown. */
1267 pmap_insert(reg_map, (void *) arch_env->sp, NULL);
1268 for (i = 0; i < n_res; ++i) {
1269 be_abi_call_arg_t *arg = get_call_arg(call, 1, i, 1);
1271 in[n] = be_abi_reg_map_get(reg_map, arg->reg);
1272 regs[n++] = arg->reg;
1274 /* Clear the map entry to mark the register as processed. */
1275 be_abi_reg_map_set(reg_map, arg->reg, NULL);
1278 /* grow the rest of the stuff. */
1279 foreach_pmap(reg_map, ent) {
1281 in[n] = (ir_node*)ent->value;
1282 regs[n++] = (const arch_register_t*)ent->key;
1286 /* The in array for the new back end return is now ready. */
1288 dbgi = get_irn_dbg_info(irn);
1292 /* we have to pop the shadow parameter in in case of struct returns */
1294 ret = be_new_Return(dbgi, irg, bl, n_res, pop, n, in);
1296 /* Set the register classes of the return's parameter accordingly. */
1297 for (i = 0; i < n; ++i) {
1298 if (regs[i] == NULL)
1301 be_set_constr_single_reg_in(ret, i, regs[i], arch_register_req_type_none);
1304 /* Free the space of the Epilog's in array and the register <-> proj map. */
1305 pmap_destroy(reg_map);
1310 typedef struct lower_frame_sels_env_t {
1311 ir_node *frame; /**< the current frame */
1312 const arch_register_class_t *sp_class; /**< register class of the stack pointer */
1313 } lower_frame_sels_env_t;
1316 * Walker: Replaces Sels of frame type and
1317 * value param type entities by FrameAddress.
1318 * Links all used entities.
1320 static void lower_frame_sels_walker(ir_node *irn, void *data)
1322 lower_frame_sels_env_t *ctx = (lower_frame_sels_env_t*)data;
1325 ir_node *ptr = get_Sel_ptr(irn);
1327 if (ptr == ctx->frame) {
1328 ir_entity *ent = get_Sel_entity(irn);
1329 ir_node *bl = get_nodes_block(irn);
1332 nw = be_new_FrameAddr(ctx->sp_class, bl, ctx->frame, ent);
1339 * The start block has no jump, instead it has an initial exec Proj.
1340 * The backend wants to handle all blocks the same way, so we replace
1341 * the out cfg edge with a real jump.
1343 static void fix_start_block(ir_graph *irg)
1345 ir_node *initial_X = get_irg_initial_exec(irg);
1346 ir_node *start_block = get_irg_start_block(irg);
1347 ir_node *jmp = new_r_Jmp(start_block);
1349 assert(is_Proj(initial_X));
1350 exchange(initial_X, jmp);
1351 set_irg_initial_exec(irg, new_r_Bad(irg, mode_X));
1353 /* merge start block with successor if possible */
1355 foreach_out_edge(jmp, edge) {
1356 ir_node *succ = get_edge_src_irn(edge);
1357 if (!is_Block(succ))
1360 if (get_irn_arity(succ) == 1) {
1361 exchange(succ, start_block);
1369 * Modify the irg itself and the frame type.
1371 static void modify_irg(ir_graph *const irg, be_abi_irg_t *const env)
1373 be_abi_call_t *call = env->call;
1374 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1375 const arch_register_t *sp = arch_env->sp;
1376 ir_type *method_type = get_entity_type(get_irg_entity(irg));
1377 be_irg_t *birg = be_birg_from_irg(irg);
1378 struct obstack *obst = be_get_be_obst(irg);
1379 be_stack_layout_t *stack_layout = be_get_irg_stack_layout(irg);
1382 ir_node *new_mem_proj;
1390 const arch_register_t *fp_reg;
1391 ir_node *frame_pointer;
1395 ir_type *arg_type, *bet_type;
1396 lower_frame_sels_env_t ctx;
1398 DBG((dbg, LEVEL_1, "introducing abi on %+F\n", irg));
1400 old_mem = get_irg_initial_mem(irg);
1402 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1404 arg_type = compute_arg_type(irg, call, method_type);
1406 /* Convert the Sel nodes in the irg to frame addr nodes: */
1407 ctx.frame = get_irg_frame(irg);
1408 ctx.sp_class = arch_env->sp->reg_class;
1410 ir_type *const frame_tp = get_irg_frame_type(irg);
1411 /* layout the stackframe now */
1412 if (get_type_state(frame_tp) == layout_undefined) {
1413 default_layout_compound_type(frame_tp);
1416 /* align stackframe */
1417 unsigned const alignment = 1U << arch_env->stack_alignment;
1418 unsigned const frame_size = round_up2(get_type_size_bytes(frame_tp), alignment);
1419 set_type_size_bytes(frame_tp, frame_size);
1421 env->regs = pmap_create();
1423 n_params = get_method_n_params(method_type);
1424 args = OALLOCNZ(obst, ir_node*, n_params);
1426 be_add_parameter_entity_stores(irg);
1428 irg_walk_graph(irg, lower_frame_sels_walker, NULL, &ctx);
1430 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
1432 /* Fill the argument vector */
1433 arg_tuple = get_irg_args(irg);
1434 foreach_out_edge(arg_tuple, edge) {
1435 ir_node *irn = get_edge_src_irn(edge);
1436 if (! is_Anchor(irn)) {
1437 int nr = get_Proj_proj(irn);
1439 DBG((dbg, LEVEL_2, "\treading arg: %d -> %+F\n", nr, irn));
1443 stack_layout->sp_relative = call->flags.try_omit_fp;
1444 bet_type = call->cb->get_between_type(irg);
1445 stack_frame_init(stack_layout, arg_type, bet_type,
1446 get_irg_frame_type(irg));
1448 /* Count the register params and add them to the number of Projs for the RegParams node */
1449 for (i = 0; i < n_params; ++i) {
1450 be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 1);
1451 if (arg->in_reg && args[i]) {
1452 assert(arg->reg != sp && "cannot use stack pointer as parameter register");
1453 assert(i == get_Proj_proj(args[i]));
1455 /* For now, associate the register with the old Proj from Start representing that argument. */
1456 pmap_insert(env->regs, (void *) arg->reg, args[i]);
1457 DBG((dbg, LEVEL_2, "\targ #%d -> reg %s\n", i, arg->reg->name));
1461 /* Collect all callee-save registers */
1462 for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
1463 const arch_register_class_t *cls = &arch_env->register_classes[i];
1464 for (j = 0; j < cls->n_regs; ++j) {
1465 const arch_register_t *reg = &cls->regs[j];
1466 if ((reg->type & arch_register_type_state) || arch_register_is_callee_save(arch_env, reg)) {
1467 pmap_insert(env->regs, (void *) reg, NULL);
1472 fp_reg = call->flags.try_omit_fp ? arch_env->sp : arch_env->bp;
1473 rbitset_clear(birg->allocatable_regs, fp_reg->global_index);
1475 /* handle start block here (place a jump in the block) */
1476 fix_start_block(irg);
1478 pmap_insert(env->regs, (void *) sp, NULL);
1479 pmap_insert(env->regs, (void *) arch_env->bp, NULL);
1480 start_bl = get_irg_start_block(irg);
1481 ir_node *const start = be_new_Start(NULL, start_bl, pmap_count(env->regs) + 1);
1482 set_irg_start(irg, start);
1485 * make proj nodes for the callee save registers.
1486 * memorize them, since Return nodes get those as inputs.
1488 * Note, that if a register corresponds to an argument, the regs map
1489 * contains the old Proj from start for that argument.
1491 rm = ALLOCAN(reg_node_map_t, pmap_count(env->regs));
1492 reg_map_to_arr(rm, env->regs);
1493 for (i = 0, n = pmap_count(env->regs); i < n; ++i) {
1494 const arch_register_t *reg = rm[i].reg;
1495 ir_mode *mode = reg->reg_class->mode;
1497 arch_register_req_type_t add_type = arch_register_req_type_none;
1501 add_type |= arch_register_req_type_produces_sp;
1502 if (!rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
1503 add_type |= arch_register_req_type_ignore;
1507 proj = new_r_Proj(start, mode, nr + 1);
1508 pmap_insert(env->regs, (void *) reg, proj);
1509 be_set_constr_single_reg_out(start, nr + 1, reg, add_type);
1510 arch_set_irn_register(proj, reg);
1512 DBG((dbg, LEVEL_2, "\tregister save proj #%d -> reg %s\n", nr, reg->name));
1515 /* create a new initial memory proj */
1516 assert(is_Proj(old_mem));
1517 arch_set_irn_register_req_out(start, 0, arch_no_register_req);
1518 new_mem_proj = new_r_Proj(start, mode_M, 0);
1520 set_irg_initial_mem(irg, mem);
1522 env->init_sp = be_abi_reg_map_get(env->regs, sp);
1524 /* set new frame_pointer */
1525 frame_pointer = be_abi_reg_map_get(env->regs, fp_reg);
1526 set_irg_frame(irg, frame_pointer);
1528 /* rewire old mem users to new mem */
1529 exchange(old_mem, mem);
1531 /* keep the mem (for functions with an endless loop = no return) */
1534 set_irg_initial_mem(irg, mem);
1536 /* Now, introduce stack param nodes for all parameters passed on the stack */
1537 for (i = 0; i < n_params; ++i) {
1538 ir_node *arg_proj = args[i];
1539 ir_node *repl = NULL;
1541 if (arg_proj != NULL) {
1542 be_abi_call_arg_t *arg;
1543 ir_type *param_type;
1544 int nr = get_Proj_proj(arg_proj);
1547 nr = MIN(nr, n_params);
1548 arg = get_call_arg(call, 0, nr, 1);
1549 param_type = get_method_param_type(method_type, nr);
1552 repl = pmap_get(ir_node, env->regs, arg->reg);
1554 ir_node *addr = be_new_FrameAddr(sp->reg_class, start_bl, frame_pointer, arg->stack_ent);
1556 /* For atomic parameters which are actually used, we create a Load node. */
1557 if (is_atomic_type(param_type) && get_irn_n_edges(args[i]) > 0) {
1558 ir_mode *mode = get_type_mode(param_type);
1559 ir_mode *load_mode = arg->load_mode;
1560 ir_node *nomem = get_irg_no_mem(irg);
1562 ir_node *load = new_r_Load(start_bl, nomem, addr, load_mode, cons_floats);
1563 repl = new_r_Proj(load, load_mode, pn_Load_res);
1565 if (mode != load_mode) {
1566 repl = new_r_Conv(start_bl, repl, mode);
1569 /* The stack parameter is not primitive (it is a struct or array),
1570 * we thus will create a node representing the parameter's address
1576 assert(repl != NULL);
1578 /* Beware: the mode of the register parameters is always the mode of the register class
1579 which may be wrong. Add Conv's then. */
1580 mode = get_irn_mode(args[i]);
1581 if (mode != get_irn_mode(repl)) {
1582 repl = new_r_Conv(get_nodes_block(repl), repl, mode);
1584 exchange(args[i], repl);
1588 /* the arg proj is not needed anymore now and should be only used by the anchor */
1589 assert(get_irn_n_edges(arg_tuple) == 1);
1590 kill_node(arg_tuple);
1591 set_irg_args(irg, new_r_Bad(irg, mode_T));
1593 /* All Return nodes hang on the End node, so look for them there. */
1594 end = get_irg_end_block(irg);
1595 for (i = 0, n = get_Block_n_cfgpreds(end); i < n; ++i) {
1596 ir_node *irn = get_Block_cfgpred(end, i);
1598 if (is_Return(irn)) {
1599 ir_node *blk = get_nodes_block(irn);
1600 ir_node *mem = get_Return_mem(irn);
1601 ir_node *ret = create_be_return(env, irn, blk, mem, get_Return_n_ress(irn));
1606 /* if we have endless loops here, n might be <= 0. Do NOT create a be_Return then,
1607 the code is dead and will never be executed. */
1610 /** Fix the state inputs of calls that still hang on unknowns */
1611 static void fix_call_state_inputs(ir_graph *const irg, be_abi_irg_t *const env)
1613 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1615 arch_register_t **stateregs = NEW_ARR_F(arch_register_t*, 0);
1617 /* Collect caller save registers */
1618 n = arch_env->n_register_classes;
1619 for (i = 0; i < n; ++i) {
1621 const arch_register_class_t *cls = &arch_env->register_classes[i];
1622 for (j = 0; j < cls->n_regs; ++j) {
1623 const arch_register_t *reg = arch_register_for_index(cls, j);
1624 if (reg->type & arch_register_type_state) {
1625 ARR_APP1(arch_register_t*, stateregs, (arch_register_t *)reg);
1630 n = ARR_LEN(env->calls);
1631 n_states = ARR_LEN(stateregs);
1632 for (i = 0; i < n; ++i) {
1634 ir_node *call = env->calls[i];
1636 arity = get_irn_arity(call);
1638 /* the state reg inputs are the last n inputs of the calls */
1639 for (s = 0; s < n_states; ++s) {
1640 int inp = arity - n_states + s;
1641 const arch_register_t *reg = stateregs[s];
1642 ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
1644 set_irn_n(call, inp, regnode);
1648 DEL_ARR_F(stateregs);
1652 * Create a trampoline entity for the given method.
1654 static ir_entity *create_trampoline(be_main_env_t *be, ir_entity *method)
1656 ir_type *type = get_entity_type(method);
1657 ident *old_id = get_entity_ld_ident(method);
1658 ident *id = id_mangle3("", old_id, "$stub");
1659 ir_type *parent = be->pic_trampolines_type;
1660 ir_entity *ent = new_entity(parent, old_id, type);
1661 set_entity_ld_ident(ent, id);
1662 set_entity_visibility(ent, ir_visibility_private);
1668 * Returns the trampoline entity for the given method.
1670 static ir_entity *get_trampoline(be_main_env_t *env, ir_entity *method)
1672 ir_entity *result = pmap_get(ir_entity, env->ent_trampoline_map, method);
1673 if (result == NULL) {
1674 result = create_trampoline(env, method);
1675 pmap_insert(env->ent_trampoline_map, method, result);
1681 static ir_entity *create_pic_symbol(be_main_env_t *be, ir_entity *entity)
1683 ident *old_id = get_entity_ld_ident(entity);
1684 ident *id = id_mangle3("", old_id, "$non_lazy_ptr");
1685 ir_type *e_type = get_entity_type(entity);
1686 ir_type *type = new_type_pointer(e_type);
1687 ir_type *parent = be->pic_symbols_type;
1688 ir_entity *ent = new_entity(parent, old_id, type);
1689 set_entity_ld_ident(ent, id);
1690 set_entity_visibility(ent, ir_visibility_private);
1695 static ir_entity *get_pic_symbol(be_main_env_t *env, ir_entity *entity)
1697 ir_entity *result = pmap_get(ir_entity, env->ent_pic_symbol_map, entity);
1698 if (result == NULL) {
1699 result = create_pic_symbol(env, entity);
1700 pmap_insert(env->ent_pic_symbol_map, entity, result);
1709 * Returns non-zero if a given entity can be accessed using a relative address.
1711 static int can_address_relative(ir_entity *entity)
1713 return entity_has_definition(entity) && !(get_entity_linkage(entity) & IR_LINKAGE_MERGE);
1716 static ir_node *get_pic_base(ir_graph *irg)
1718 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1719 if (arch_env->impl->get_pic_base == NULL)
1721 return arch_env->impl->get_pic_base(irg);
1724 /** patches SymConsts to work in position independent code */
1725 static void fix_pic_symconsts(ir_node *node, void *data)
1727 ir_graph *irg = get_irn_irg(node);
1728 be_main_env_t *be = be_get_irg_main_env(irg);
1738 arity = get_irn_arity(node);
1739 for (i = 0; i < arity; ++i) {
1741 ir_node *pred = get_irn_n(node, i);
1743 ir_entity *pic_symbol;
1744 ir_node *pic_symconst;
1746 if (!is_SymConst(pred))
1749 entity = get_SymConst_entity(pred);
1750 block = get_nodes_block(pred);
1752 /* calls can jump to relative addresses, so we can directly jump to
1753 the (relatively) known call address or the trampoline */
1754 if (i == 1 && is_Call(node)) {
1755 ir_entity *trampoline;
1756 ir_node *trampoline_const;
1758 if (can_address_relative(entity))
1761 dbgi = get_irn_dbg_info(pred);
1762 trampoline = get_trampoline(be, entity);
1763 trampoline_const = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1765 set_irn_n(node, i, trampoline_const);
1769 /* everything else is accessed relative to EIP */
1770 mode = get_irn_mode(pred);
1771 pic_base = get_pic_base(irg);
1773 /* all ok now for locally constructed stuff */
1774 if (can_address_relative(entity)) {
1775 ir_node *add = new_r_Add(block, pic_base, pred, mode);
1777 /* make sure the walker doesn't visit this add again */
1778 mark_irn_visited(add);
1779 set_irn_n(node, i, add);
1783 /* get entry from pic symbol segment */
1784 dbgi = get_irn_dbg_info(pred);
1785 pic_symbol = get_pic_symbol(be, entity);
1786 pic_symconst = new_rd_SymConst_addr_ent(dbgi, irg, mode_P_code,
1788 add = new_r_Add(block, pic_base, pic_symconst, mode);
1789 mark_irn_visited(add);
1791 /* we need an extra indirection for global data outside our current
1792 module. The loads are always safe and can therefore float
1793 and need no memory input */
1794 load = new_r_Load(block, get_irg_no_mem(irg), add, mode, cons_floats);
1795 load_res = new_r_Proj(load, mode, pn_Load_res);
1797 set_irn_n(node, i, load_res);
1801 void be_abi_introduce(ir_graph *irg)
1803 ir_node *old_frame = get_irg_frame(irg);
1804 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
1805 ir_entity *entity = get_irg_entity(irg);
1806 ir_type *method_type = get_entity_type(entity);
1807 be_irg_t *birg = be_birg_from_irg(irg);
1808 struct obstack *obst = &birg->obst;
1809 ir_node *dummy = new_r_Dummy(irg,
1810 arch_env->sp->reg_class->mode);
1813 /* determine allocatable registers */
1814 assert(birg->allocatable_regs == NULL);
1815 birg->allocatable_regs = rbitset_obstack_alloc(obst, arch_env->n_registers);
1816 for (r = 0; r < arch_env->n_registers; ++r) {
1817 const arch_register_t *reg = &arch_env->registers[r];
1818 if ( !(reg->type & arch_register_type_ignore)) {
1819 rbitset_set(birg->allocatable_regs, r);
1823 /* Break here if backend provides a custom API. */
1825 be_omit_fp = be_options.omit_fp;
1828 env.keep_map = pmap_create();
1829 env.call = be_abi_call_new(arch_env->sp->reg_class);
1830 arch_env_get_call_abi(arch_env, method_type, env.call);
1832 env.init_sp = dummy;
1833 env.calls = NEW_ARR_F(ir_node*, 0);
1837 if (be_options.pic) {
1838 irg_walk_graph(irg, fix_pic_symconsts, NULL, NULL);
1841 /* Lower all call nodes in the IRG. */
1842 process_calls(irg, &env);
1844 /* Process the IRG */
1845 modify_irg(irg, &env);
1847 /* fix call inputs for state registers */
1848 fix_call_state_inputs(irg, &env);
1850 be_abi_call_free(env.call);
1852 /* We don't need the keep map anymore. */
1853 pmap_destroy(env.keep_map);
1855 /* calls array is not needed anymore */
1856 DEL_ARR_F(env.calls);
1858 /* reroute the stack origin of the calls to the true stack origin. */
1859 exchange(dummy, env.init_sp);
1860 exchange(old_frame, get_irg_frame(irg));
1862 pmap_destroy(env.regs);
1865 void be_put_allocatable_regs(const ir_graph *irg,
1866 const arch_register_class_t *cls, bitset_t *bs)
1868 be_irg_t *birg = be_birg_from_irg(irg);
1869 unsigned *allocatable_regs = birg->allocatable_regs;
1872 assert(bitset_size(bs) == cls->n_regs);
1873 bitset_clear_all(bs);
1874 for (i = 0; i < cls->n_regs; ++i) {
1875 const arch_register_t *reg = &cls->regs[i];
1876 if (rbitset_is_set(allocatable_regs, reg->global_index))
1881 unsigned be_get_n_allocatable_regs(const ir_graph *irg,
1882 const arch_register_class_t *cls)
1884 bitset_t *bs = bitset_alloca(cls->n_regs);
1885 be_put_allocatable_regs(irg, cls, bs);
1886 return bitset_popcount(bs);
1889 void be_set_allocatable_regs(const ir_graph *irg,
1890 const arch_register_class_t *cls,
1891 unsigned *raw_bitset)
1893 be_irg_t *birg = be_birg_from_irg(irg);
1894 unsigned *allocatable_regs = birg->allocatable_regs;
1897 rbitset_clear_all(raw_bitset, cls->n_regs);
1898 for (i = 0; i < cls->n_regs; ++i) {
1899 const arch_register_t *reg = &cls->regs[i];
1900 if (rbitset_is_set(allocatable_regs, reg->global_index))
1901 rbitset_set(raw_bitset, i);
1905 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_abi)
1906 void be_init_abi(void)
1908 FIRM_DBG_REGISTER(dbg, "firm.be.abi");